4.5. Les méta- heuristiques
Les métas- heuristiques sont apparues dans les
années 1980 et forment une famille d'algorithmes d'optimisation visant
à résoudre des problèmes d'optimisation difficile, pour
lesquels on ne connaît pas de méthode classique plus efficace.
Elles sont généralement utilisées comme des
méthodes génériques pouvant optimiser une large gamme de
problèmes différents, sans nécessiter de changements
profonds dans l'algorithme employé [5,18,19,20,21].
Etymologiquement parlant de ce mot est composé dans un
premier temps du préfixe méta qui signifie « au
delà »ou « plus haut » en grec puis de
« heuristique » qui signifie
« trouver ». Cette décomposition permet de
facilement comprendre le but premier de ces algorithmes : trouver des
solutions à des problèmes en utilisant plusieurs (méta)
heuristiques.
Métas- heuristiques utilisent des processus
aléatoires comme moyens de récolter de l'information et de faire
face à des problèmes comme l'explosion combinatoire. En plus de
cette base stochastique, les méta- heuristiques sont
généralement itératives, c'est-à-dire qu'un
même schéma de recherche est appliqué plusieurs fois au
cours de l'optimisation, et directes, c'est-à-dire qu'elles n'utilisent
pas l'information du gradient de la fonction objectif. Elles tirent en
particulier leur intérêt de leur capacité à
éviter les optima locaux, soit en acceptant une dégradation de la
fonction objectif au cours de leur progression, soit en utilisant une
population de points comme méthode de recherche.
Les méta- heuristiques, du fait de leur capacité
à être utilisées sur un grand nombre de problèmes
différents, se prêtent facilement à des extensions. Pour
illustrer cette caractéristique, citons notamment :
*L'optimisation multi objectif (dites aussi
multicritère) [22], ou il faut optimiser plusieurs objectifs
contradictoires. La recherche vise alors non pas à trouver un optimum
global, mais un ensemble d'optima «au sens de Pareto» formant la
«surface de compromis» du problème.
*L'optimisation multimodale, ou l'on cherche un ensemble des
meilleurs optima globaux et/ou locaux.
*L'optimisation de problèmes bruités, où
il existe une incertitude sur le calcul de la fonction objectif. Incertitude
dont il faut alors tenir comptes dans la recherche de l'optimum.
*L'optimisation dynamique, ou la fonction objectif varie dans
le temps. Il faut alors approcher au mieux l'optimum à chaque pas de
temps.
*La parallélisation, ou l'on cherche à
accélérer la vitesse de l'optimisation en répartissant la
charge de calcul sur des unités fonctionnant de concert. Le
problème revient alors à adapter les métas- heuristiques
pour qu'elles soient distribuées.
*L'hybridation, qui vise à tirer parti des avantages
respectifs de méta- heuristiques différentes en les combinant
[22,23].
Enfin, la grande vitalité de ce domaine de recherche ne
doit pas faire oublier qu'un des intérêts majeurs des
métas- heuristiques est leur facilité d'utilisation dans des
problèmes concrets. L'utilisateur est généralement
demandeur de méthodes efficaces permettant d'atteindre un optimum avec
une précision acceptable dans un temps raisonnable. Un des enjeux de la
conception des métas- heuristiques est donc de faciliter le choix d'une
méthode et de simplifier son réglage pour l'adapter à un
problème donné.
4.5.1. Organisation
générale
D'une manière générale, les méta-
heuristiques s'articulent autour de trois notions [22]:
Diversification /exploration :
désigne les processus visant à récolter de l'information
sur le problème optimisé.
L'intensification/exploitation :
vise à utiliser l'information déjà récoltée
pour définir et parcourir les zones intéressantes de l'espace de
recherche.
La mémoire : est le
support de l'apprentissage, qui permet à l'algorithme de ne tenir compte
que des zones ou l'optimum global est susceptible de se trouver, évitant
ainsi les optimums locaux.
Les métas- heuristiques progressent de façon
itérative, en alternant des phases d'intensification, de diversification
et d'apprentissage. L'état de départ est souvent choisi
aléatoirement, l'algorithme se déroulant ensuite jusqu'à
ce qu'un critère d'arrêt soit atteint.
| 
