4.3.2 Les métaheuristiques
Depuis environ, une quarantaine d'années, sont apparues
des approches de résolution plus générale, qui peuvent
donc, moyennant la fixation de certaines paramètres et quelques
adaptations, s'appliquent à une large classe de problèmes
d'optimisation, ces méthodes sont dites heuristiques de haut niveau ou
métaheuristiques (dérivées de la composition de deux mots
grecs : « heuriskien » qui signifie trouver,
et « Méta » qui signifie dans un
niveau supérieur).
La polyvalence, l'efficacité concrète et la
relative simplicité des métaheuristiques, leur ont
conféré une popularité et une extension remarquables
durant ces 25 dernières années. Leur efficacité
dépend néanmoins du soin apporté à la fixation des
paramètres et à l'adap-tation du problème traité,
leur principe et parfois inspiré d'observations réalisées
dans des domaines totalement différents que celui de l'optimisation sous
contraintes, c'est le cas pour les métaheuristiques de type «
recuit simulé », « algorithme génétique »
et « algorithme de colonies de fourmis ».
Les métaheuristiques sont des méthodes dites
stochastiques, fondées sur des règles d'évo-lution
probabilistes, contrairement aux méthodes déterministes qui
s'appuient sur les propriétés mathématiques. On
désigne deux stratégies de recherche des métaheuristiques
:
L'intensification ou exploitation: on entend
l'exploitation de l'information rassemblée par le système
à un moment donné. C'est ce qui permet l'amélioration de
la valeur d'une solution trouvée dans un certain voisinage, i.e, permet
d'examiner en profondeur une zone particulier de l'espace de recherche.
La diversification ou exploration: on entend
au contraire, l'exploration de l'espace de recherche encore inconnu. Elle est
généralement obtenue par des processus stochastiques.i.e., permet
d'orienter la recherche vers des nouvelles zones (autorisés) dans
l'espace de recherche.
68
4.4. LE RECUIT SIMULÉ
Les métaheuristiques peuvent être classées
de nombreuses façons. On peut cependant distinguer:
Les métaheuristiques à parcours
Les métaheuristiques les plus classiques sont celles
fondées sur la notion de parcours. Ces algorithmes partent d'une
solution initiale (obtenue par une méthode de résolution, ou par
tirage aléatoire) et construisent une trajectoire dans l'espace des
solutions en tentant de se diriger vers des meilleurs solutions. La
méthode du recuit simulé (SA), recherche tabou (TS) et recherche
à voisinage variables (VNS) sont des exemples typiques de ce type de
métaheuristiques.
Les métaheuristiques à
populations
Ces méthodes utilisent la notion de population: elles
manipulent un ensemble de solutions en parallèle. Chaque
élément de population parcourt un certain nombre de solutions
dans l'ensemble local. Les algorithmes génétiques et Les
algorithmes de colonies de fourmis présentent les exemples les plus
connus des méthodes qui travaillent avec une population.
Dans ce qui suit, nous détaillerons la méthode
recuit simulé et celle des algorithmes génétiques.
| 
