5.3 Métaheuristiques[9]
Présentation:
On parle de méta, du grec << au-delà
>> (comprendre ici << à un plus haut niveau >> ),
heuristique, qui signifie << trouver >> . En effet, ces algorithmes
se veulent des méthodes génétiques pouvant optimiser une
large gamme de problèmes différents, sans nécessiter de
changements profonds dans l'algorithme employé.
Une terminologie légèrement différente
considère que les métaheuristiques sont une forme d'algorithmes
d'optimisation stochastique, hybridés avec une recherche locale. Le
terme <<méta>> est donc pris au sens on les algorithmes
peuvent regrouper plusieurs heuristiques. On rencontre cette définition
essentiellement dans la littérature concernant les algorithmes
évolutionnaires, on elle est utilisée pour désigner une
spécialisation. Dans le cadre de la première terminologie, un
algorithme évolutionnaire hybridé avec une recherche locale sera
plutôt désigné sous le terme d'algorithme
mémétique (révolutionnaire) tel que l'algorithme
génétique.
Les métaheuristiques sont souvent inspirées par
des systèmes naturels, qu'ils soient pris en physique (cas du recuit
simulé), en biologie de l'évolution (cas des algorithmes
génétiques) ou encore en éthologie (cas des algorithmes de
colonies de fourmis ou de l'optimisation par essaims particulaires).
Le but d'une métaheuristique est de résoudre un
problème d'optimisation donné: elle cherche un objet
mathématique (une permutation, un vecteur, etc.) minimisant (ou
maximisant) une fonction objectif, qui décrit la qualité d'une
solution au problème.
L'ensemble des solutions possibles forme l'espace de
recherche. L'espace de recherche est au minimum borné, mais peut
être également limité par un ensemble de contraintes.
Les métaheuristiques manipulent une ou plusieurs
solutions, à la recherche de l'optimum, la meilleure solution au
problème. Les itérations successives doivent permettre de passer
d'une solution de mauvaise qualité à la solution la plus proche
de l'optimale. L'algorithme s'arrête après avoir atteint un
critère d'arrêt, consistant généralement en
l'atteinte du temps d'exécution imparti ou en une précision
demandée.
Une solution ou un ensemble de solutions est parfois
appelé un état, que la méta-
heuristique fait évoluer via des transitions ou des
mouvements. Si une nouvelle solution est construite a partir d'une solution
existante, elle est sa voisine. Le choix du voisinage et de la structure de
donnée le représentant peut être crucial.
Lorsqu'une solution est associée a une seule valeur, on
parle de problème mono-objectif, lorsqu'elle est associée a
plusieurs valeurs, de problème multi-objectifs (ou
multi-critères). Dans ce dernier cas, on recherche un ensemble de
solutions non dominées (le << front de Pareto >> ),
solutions parmi lesquelles on ne peut décider si une solution est
meilleure qu'une autre, aucune n'étant systématiquement
inférieure aux autres sur tous les objectifs.
Dans certains cas, le but recherché est explicitement
de trouver un ensemble d'optimums << satisfaisants >> .
L'algorithme doit alors trouver l'ensemble des solutions de bonne
qualité, sans nécessairement se limiter au seul optimum: on parle
de méthodes multimodales.
Pour résumer ces définitions, on peut dire que les
propriétés fondamentales des métaheuristiques sont les
suivantes:
- Les métaheuristiques sont des stratégies qui
permettent de guider la recherche d'une solution optimale
- Le but visé par les métaheuristiques est
d'explorer l'espace de recherche effi cacement afin de déterminer des
solutions (presque) optimales.
- Les techniques qui constituent des algorithmes de type
métaheuristique vont de la simple procédure de recherche locale a
des processus d'apprentissage complexes.
- Les métaheuristiques sont en général
non-déterministes et ne donnent aucune garantie d'optimalité
- Les métaheuristiques peuvent contenir des
mécanismes qui permettent d'éviter d'être bloqué
dans des régions de l'espace d recherche.
- Les concepts de base des métaheuristiques peuvent
être décrit de manière abstraite, sans faire appel a un
problème spécifique.
- Les métaheuristiques peuvent faire appel a des
heuristiques qui tiennent compte de la spécificité du
problème traité, mais ces heuristiques sont
contrôlées par une stratégie de niveau supérieur.
- Les métaheuristiques peuvent faire usage de
l'expérience accumulée durant la recherche
de l'optimum, pour mieux guider la suite du processus de
recherche.
| 
