Métaheuristiques

Voici ce qu’on trouve sur WikipédiA

Une métaheuristique est un algorithme d’optimisation visant à résoudre des problèmes d’opti-
misation difficiles pour lesquels on ne connaît pas de méthode classique plus efficace. Les méta-
heuristiques sont généralement des algorithmes stochastiques itératifs, qui progressent vers un
optimum global. Elles se comportent comme des algorithmes de recherche, tentant d’apprendre
les caractéristiques d’un problème afin d’en trouver une approximation de la meilleure solution.
Il existe un grand nombre de métaheuristiques différentes, allant de la simple Recherche Locale
à des algorithmes complexes de recherche globale. Ces méthodes utilisent cependant un haut ni-
veau d’abstraction, leur permettant d’être adaptées à une large gamme de problèmes différents.
En d’autres termes, ces algorithmes se veulent 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é.
Voici ce qu’on trouve sur le site Web Metaheuristics Network (http ://www.metaheuristics.org)
A metaheuristic is a set of concepts that can be used to define heuristic methods that can be
applied to a wide set of different problems. In other words, a metaheuristic can be seen as a
general algorithmic framework which can be applied to different optimization problems with
relatively few modifications to make them adapted to a specific problem.
Il n’existe pas de définition qui fasse l’unanimité, mais tous s’accordent sur les points suivants :
• Les métaheuristiques sont des stratégies permettant de guider la recherche d’une solution
optimale.
• Le but visé par les métaheuristiques est d’explorer l’espace de recherche efficacement 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 à des processus d’apprentissage complexes.
• Les métaheuristiques sont en général non-déterministes et ne donnent aucune garantie d’opti-
malité.
• Les métaheuristiques peuvent contenir des mécanismes qui permettent d’éviter d’être bloqué
dans des régions de l’espace de recherche.
• Les concepts de base des métaheuristiques peuvent être décrit de manière abstraite, sans faire
appel à un problème spécifique.
• Les métaheuristiques peuvent faire appel à 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.
Soit S un ensemble de solutions à un problème d’optimisation et soit f une fonction qui mesure
la qualité f (s) de chaque solution s ∈ S. Le but des métaheuristiques est de déterminer une
solution s ∈ S de valeur f (s) minimale. En d’autres termes, le problème est de déterminer la
valeur suivante : min f (s)
s∈S

et éventuellement également d’exhiber une solution ayant cette valeur.

Un voisinage est une fonction N qui associe un sous-ensemble de S à tout solution s ∈ S. Une
solution s0 ∈ N (s) est dite voisine de s. Une solution s ∈ S est un minimum local relativement
à N si f (s) ≤ f (s0 ) pour tout s0 ∈ N (s), alors qu’il s’agit d’un minimum global si f (s) ≤ f (s0 )
pour tout s ∈ S.
Les métaheuristiques sacrifient la garantie d’optimalité ou d’approximation avec, en contrepartie,
l’espoir de trouver très rapidement de bonnes solutions dans S.

1
Plusieurs classifications possibles
On peut faire la différence entre les métaheuristiques qui s’inspirent de phénomènes naturels
et celles qui ne s’en inspirent pas. Par exemple, les algorithmes génétiques et les algorithmes des
fourmis s’inspirent respectivement de la théorie de l’évolution et du comportement de fourmis à
la recherche de nourriture. Une telle classification ne semble cependant pas très utile et est parfois
difficile à réaliser. En effet, il existe de nombreuses métaheuristiques récentes qu’il est difficile de
classer dans l’une des 2 catégories. Certains se demanderont par exemple si l’utilisation d’une
mémoire dans la méthode Tabou n’est pas directement inspirée de la nature.
On peut également distinguer les métaheuristiques qui travaillent avec une population de so-
lutions de celles qui ne manipulent qu’une solution à la fois. Les méthodes qui tentent itérati-
vement d’améliorer une solution sont appelées méthodes de Recherche Locale (et parfois aussi
méthodes de trajectoire). La méthode Tabou, le Recuit Simulé et la Recherche à Voisinages Va-
riables sont des exemples typiques de méthodes de Recherche Locale. Ces méthodes construisent
une trajectoire dans l’espace S des solutions en tentant de se diriger vers des solutions opti-
males. L’exemple le plus connu de méthode qui travaille avec une population de solutions est
l’algorithme génétique.
Les métaheuristiques peuvent également être classées selon leur manière d’utiliser la fonction
objectif. Les métaheuristiques dites statiques travaillent directement sur la fonction objectif f
alors que d’autres, dites dynamiques, font usage d’une fonction g obtenue à partir de f en
ajoutant quelques composantes qui permettent de modifier la topologie de l’espace des solutions,
ces composantes additionnelles pouvant varier durant le processus de recherche.
Certaines métaheuristiques font usage de l’historique de la recherche, alors que d’autres n’ont
aucune mémoire du passé. Les algorithmes sans mémoire sont des processus markoviens puisque
l’action à réaliser est totalement déterminée par la situation courante. L’usage de l’historique de
la recherche peut être fait de diverses manières. On différentie généralement les méthodes ayant
une mémoire à court terme de celles qui ont une mémoire à long terme.
Mentionnons également que certaines métaheuristiques utilisent les concepts additionnels tels
que la diversification et l’intensification. Par diversification, on entend généralement une
exploration très large de l’espace de recherche, alors que le terme intensification vient mettre
l’accent sur l’exploitation de l’information accumulée durant la recherche. Il est important de
bien doser l’usage de ces deux ingrédients afin que l’exploration puisse rapidement identifier des
régions de l’espace de recherche qui contiennent des solutions de bonne qualité, sans perdre trop
de temps à exploiter des régions moins prometteuses.
Dans ce qui suit, nous allons nous appuyer sur la classification qui distingue les méthodes de
Recherche Locale des méthodes basées sur des populations de solutions.

Quelques méthodes de Recherche Locale

Les méthodes de Recherche Locale ont ceci en commun que l’ensemble S est l’ensemble des points
pouvant être visités durant la recherche, le voisinage N donne les règles de déplacement dans cet
espace, et la fonction f induit une topologie sur S. La méthode la plus simple est l’algorithme
de descente qui peut être décrit comme suit :
1. choisir une solution s ∈ S ;
2. déterminer une solution s0 qui minimise f dans N (s) ;
3. si f (s0 ) < f (s) alors poser s ← s0 et retourner à 2., sinon STOP.
Une variante consiste à parcourir N (s) au point 2. et à choisir la première solution s0 rencontrée
telle que f (s0 ) < f (s) (pour autant qu’une telle solution existe). Le principal défaut des méthodes
de descente est qu’elles s’arrêtent au premier minimum local rencontré. Tel que déjà mentionné,
un minimum local pour une structure de voisinage ne l’est pas forcément pour une autre structure.
Le choix de N peut donc avoir une grand influence sur l’efficacité d’une méthode de descente.

2
Pour éviter d’être bloqué au premier minimum local rencontré, on peut décider d’accepter, sous
certaines conditions, de se déplacer d’une solution s vers une solution voisine s0 ∈ N (S) telle que
f (s0 ) ≥ f (s). C’est ce que font les méthodes que nous décrivons ci-dessous. Commençons par le
Recuit Simulé (Kirkpatrick, Gelatt, Vecchi, 1983) qui peut être décrit comme suit.
Choisir une solution s ∈ S ainsi qu’une température initiale T ;
Tant que aucun critère d’arrêt n’est satisfait faire
Choisir aléatoirement une solution s0 ∈ N (s) ;
Générer un nombre réel aléatoire r ∈ [0, 1] ;
Si r < p(T, s, s0 ) alors poser s ← s0 ;
Mettre à jour T ;
Fin du tant que
f (s)−f (s0 )
En général, on définit p(T, s, s0 ) = e T (qui est la distribution de Boltzmann). Ainsi :
• si f (s ) ≤ f (s) alors p(T, s, s ) ≥ 1 > r, ce qui signifie qu’on accepte s0 ;
0 0

• si T a une très grand valeur, alors p(T, s, s0 ) ∼ = 1 et s0 est donc très probablement acceptée ;
• si T ∼= 0 et f (s) < f (s ), alors p(T, s, s ) ∼
0 0
= 0 et s0 est donc très probablement refusée.
La température initiale doit être élevée afin de faciliter les déplacements dans S au début de la
recherche. Puis, T est graduellement réduite jusqu’à atteindre une valeur proche de 0. Pour fixer
la température initiale, on peut générer une centaine de solutions voisines à la solution initiale et
choisir une valeur de T qui donnerait une proportion fixée ρ de solutions qui seraient acceptées.
Aarts, Korst et Laarhoven ont démontré en 1997 que sous certaines conditions de décroissance de
la température, l’algorithme du Recuit Simulé converge en probabilité vers un optimum global
lorsque le nombre d’itérations tend vers l’infini. Plus précisément, soit P (k) la probabilité que
l’optimum global soit trouvé après k itérations, et soit Tk la température à la k e itération. Les
auteurs susmentionnés ont démontré qu’il existe L ∈ R tel que
∞
X L
lim P (k) = 1 ⇔ e Tk = ∞.
k→∞
1 k=1
On peut, par exemple, définir Tk = log2 (k−1+c) où c est une constante. Mais de telles stratégies
de décroissance de la température sont trop lentes et nécessitent des temps de calcul astrono-
miques avant d’atteindre la convergence vers l’optimum global. En pratique, on préfère donc
utiliser d’autres stratégies qui ne garantissent plus la convergence vers l’optimum global, mais
qui convergent plus rapidement vers un état stable. La méthode la plus utilisée consiste à définir
Tk+1 = αTk où α est un nombre réel choisi entre 0 et 1 (typiquement α = 0.95).
La décroissance de la température peut également être réalisée par paliers. Certains préconisent
l’utilisation de stratégies non monotones. On peut ainsi rehausser la température lorsque la
recherche semble bloquée dans une région de l’espace de recherche. On peut alors considérer
une grande augmentation de la température comme un processus de diversification alors que la
décroissance de la température correspond à un processus d’intensification.

Décroissance linéaire Décroissance par paliers Fonction non monotone

La méthode du Recuit Simulé est une méthode sans mémoire. On peut facilement l’améliorer
en rajoutant une mémoire à long terme qui stocke la meilleure solution rencontrée. En effet,
l’algorithme du Recuit Simulé décrit ci-dessus peut converger vers une solution s∗ en ayant visité
auparavant une solution s de valeur f (s) < f (s∗ ). Il est donc naturel de mémoriser la meilleure
solution rencontrée durant le processus de recherche.
Le critère d’arrêt peut être une limite sur le temps ou sur le nombre d’itérations sans modification
de la solution courante. Si on stocke la meilleure solution rencontrée s∗ , on peut décider de stopper
la recherche dès qu’un certain nombre d’itérations a été effectué sans amélioration de s∗ .

3
L’un des principaux défauts de la méthode du Recuit Simulé est le choix aléatoire du voisin
s0 dans N (s). On peut donc être proche de l’optimum et passer juste à côté sans le voir. La
Recherche Tabou n’a pas ce défaut. Elle a été proposée par Glover en 1986.
Le principe de la Recherche Tabou est de choisir à chaque itération la meilleure solution s0 ∈ N (s),
même si f (s0 ) > f (s). Lorsqu’on atteint un minimum local s par rapport au voisinage N , la
Recherche Tabou va donc se déplacer vers une solution s0 de valeur f (s0 ) ≥ f (s). Le danger est
alors de revenir à s puisque, en génŕal, s ∈ N (s0 ) et f (s) ≤ f (s0 ). Pour éviter de tourner ainsi en
rond, on crée une liste T qui mémorise les dernières solutions visitées et interdit tout déplacement
vers une solution de cette liste. Cette liste T est appelée liste Tabou. Les solutions ne demeurent
dans T que pour un nombre limité d’itérations. La liste T est donc une mémoire à court terme.
Si une solution s0 est dans T on dit que s0 est une solution taboue. De même, tout mouvement
qui nous mène de la solution courante à une solution de T est appelé mouvement tabou.
La mémorisation de solutions dans T demande typiquement beaucoup de place mémoire, et il
peut être difficile de vérifier si une solution donnée est dans T . C’est la principale raison pour
laquelle certains préfèrent mémoriser des attributs ou des modifications de solutions. Ainsi, on
peut interdire de visiter une solution présentant un attribut appartenant à T . Ou alors, on peut
interdire une solution s0 si le mouvement qui permet de se rendre de la solution courante s vers la
solution voisine s0 est un mouvement appartenant à la liste T . La mémorisation de ces attributs
ou modifications permet certes un gain en place mémoire. Mais elle n’a pas que des avantages :
• Il se peut que l’on visite une même solution à plusieurs reprises, à intervalles plus petits que
|T |. À titre d’illustration, supposons que l’on cherche à ordonner les 4 premières lettres de
l’alphabet. Pour passer d’un ordre à un autre, on permute les positions de 2 lettres et on
rend tabou une nouvelle permutation de ces deux lettres. On pourrait donc avoir la suite de
solutions suivante :
abcd → bacd → bcad → dcab → acdb → abdc → abcd.
Les permutations qui ont été effectuées sont ab, ac, bd, ad, bc et cd. On voit donc qu’aucune
permutation n’a été réalisée deux fois et on retombe cependant sur la solution initiale.
• Il se peut que la liste T interdise la visite de solutions qui n’ont jamais été visitées (de telles so-
lutions pouvant être des optima globaux). Par exemple, supposons à nouveau que l’on cherche
à ordonner les 4 premières lettres de l’alphabet. Comme ci-dessus, on permute les positions de
2 lettres pour se déplacer d’une solution à une autre et on rend tabou une nouvelle permutation
de ces 2 lettres. On pourrait avoir la suite de solutions suivante :
abcd → bacd → dacb → dcab.
On a permuté les lettres ab, bd et ac. Si |T | ≥ 3, on n’a donc pas le droit de permuter ab, et
on interdit donc la solution dcba qui pourrait être la solution optimale.
Pour éviter le 2me défaut mentionné ci-dessus, il est d’usage de lever le statut tabou d’une solution
si celle-ci satisfait certains critères d’aspiration. En règle générale, le statut tabou d’un solution
est levé si celle-ci est meilleure que la meilleure solution s∗ rencontrée jusqu’ici. Étant donnée
une solution courante s, définissons l’ensemble NT (s) comme l’ensemble des solutions de N (s)
vers lesquelles la Recherche Tabou accepte de se diriger. L’ensemble NT (s) contient donc toutes
les solutions qui ne sont pas taboues ainsi que celles qui le sont, mais dont le statut tabou est
levé en raison du critère d’aspiration. Ainsi :
NT (s) = {s0 ∈ N (s) | s0 ∈
/ T ou f (s0 ) < f (s∗ )}.
L’algorithme de Recherche Tabou peut être décrit comme suit.
Choisir une solution s ∈ S , poser T ← ∅ et s∗ ← s ;
Tant que aucun critère d’arrêt n’est satisfait faire
Déterminer une solution s0 qui minimise f dans NT (S) ;
Si f (s0 ) < f (s∗ ) alors poser s∗ ← s0 ;
Poser s ← s0 et mettre à jour T ;
Fin du tant que
4
Comme critère d’arrêt on peut par exemple fixer un nombre maximum d’itérations sans amélio-
ration de s∗ , ou on peut fixer un temps limite après lequel la recherche doit s’arrêter. Certains
préconisent l’utilisation d’une liste Tabou de longueur variable (Taillard, 1991). D’autres pré-
fèrent les listes Tabou réactives (Battiti et Tecchiolli, 1994) dont la taille varie selon les résultats
de la recherche. Ainsi, si des solutions sont visitées de manière répétée (à intervalle > |T |) alors
on peut augmenter la longueur de la liste, ce qui aura pour effet de diversifier la recherche. Aussi,
si la solution courante n’est que rarement améliorée, on peut décider d’intensifier la recherche
autour de la meilleure solution rencontrée s∗ , ce qui peut se faire en diminuant la longueur de la
liste Tabou.
La liste Tabou est une mémoire à court terme. On peut rajouter une mémoire à plus long terme.
Quatre types de mémoire sont alors envisageables :
• Les mémoires basées sur la récence mémorisent pour chaque solution (attribut ou mouvement)
l’itération la plus récente qui l’impliquait. On peut par exemple favoriser les mouvements vers
des solutions contenant des attributs peu récents, afin d’éviter de rester bloquer dans une
même région de l’espace de recherche.
• Les mémoires basées sur la fréquence mémorisent le nombre de fois que les solutions (attributs
ou mouvements) ont été visitées. Cette information permet d’identifier les régions de S qui
ont été le plus visitées. On peut exploiter cette information pour diversifier la recherche.
• Les mémoires basées sur la qualité mémorisent les meilleures solutions rencontrées afin d’iden-
tifier les composantes communes de ces solutions. On peut ensuite faire usage de cette infor-
mation pour créer de nouvelles solutions qui contiennent autant que possible ces apparemment
bonnes composantes.
• Les mémoires basées sur l’influence mémorisent les choix qui se sont avérés les plus judicieux
ou les plus critiques durant le processus de recherche. Ceci permet d’essayer de répéter les
bons choix et d’éviter de répéter les mêmes erreurs.
L’algorithme de descente, le Recuit Simulé et la Recherche Tabou sont probablement les méthodes
de Recherche Locale les plus connues et les plus utilisées. Il existe cependant d’autres méthodes
ayant également leur cote de popularité. Nous en décrivons trois. La première, appelée GRASP
(pour Greedy Randomized Adaptive Search Procedure), a été proposée par Feo et Resende en
1995. C’est une procédure itérative composée de deux phases : une phase constructive et une
phase d’amélioration.
• En supposant qu’une solution est constituée d’un ensemble de composantes, la phase construc-
tive génère une solution pas à pas, en ajoutant à chaque étape une nouvelle composante. La
composante rajoutée est choisie dans une liste de candidats. Chaque composante est évaluée à
l’aide d’un critère heuristique qui permet de mesurer le bénéfice qu’on peut espérer en rajou-
tant cette composante à la solution partielle courante. La liste de candidats, notée RCL (pour
Restricted Candidate List) contient les R meilleures composantes selon ce critère.
• La phase d’amélioration consiste généralement en l’application de l’algorithme de descente,
du Recuit Simulé ou de la Recherche Tabou.
L’algorithme GRASP peut être décrit comme suit.
Poser f ∗ ← ∞ (valeur de la meilleure solution rencontrée)
Tant que aucun critère d’arrêt n’est satisfait faire
Poser s ← ∅ ;
Tant que la solution courante s est partielle (et donc non complète) faire
Déterminer la liste RCL des R meilleures composantes pouvant être rajoutées à s ;
Choisir alétoirement une composante dans RCL et la rajouter à s ;
Fin du tant que
Appliquer une Recherche Locale, en partant de s, pour obtenir une solution s0 ;
Si f (s0 ) < f ∗ alors poser s∗ ← s0 et f ∗ ← f (s0 ) ;
Fin du tant que
5
À titre d’exemple, pour le problème du voyageur de commerce, on peut rajouter une ville après
l’autre pour créer une tournée. L’insertion d’une ville dans une tournée partielle est évaluée en
mesurant la longueur du détour occasionné par le rajout de la ville.
La longueur R de la liste RCL joue un rôle particulièrement important. Si on pose R = 1, la
phase constructive est un algorithme glouton qui choisit à chaque étape la meilleure composante.
Si on fixe R égal au nombre de composantes pouvant être rajoutées, on a alors un algorithme
constructif purement aléatoire. Certains préconisent l’utilisation d’une même valeur R durant
tout l’algorithme. D’autres préfèrent faire varier ce paramètre de manière adaptative.
La méthode GRASP est simple à mettre en place (surtout si on utilise l’algorithme de descente
comme Recherche Locale). Pour qu’elle soit efficace, il est important d’utiliser une méthode
constructive capable de générer des solutions dans des régions différentes de l’espace de recherche.
Une autre méthode populaire de Recherche Locale est la Recherche à Voisinages Variables
(RVV) proposée par Mladenovic et Hansen en 1997. Cet algorithme utilise méthodiquement
plusieurs types de voisinages. Soit L = (N 1 , . . . , N ` ) une liste finie de voisinages, où N t (s) est
l’ensemble des solutions dans le te voisinage de s. Dans la plupart des méthodes de Recherche
Locale, on a ` = 1, alors que ` > 1 pour la RVV.
Les voisinages de la liste L sont utilisés comme suit. Étant donnée une solution initiale s, on
génère une solution voisine s0 ∈ N 1 (s) et on lui applique une procédure de Recherche Locale afin
d’obtenir une solution s00 . Si f (s00 ) < f (s), alors s00 devient la nouvelle solution courante s et on
génère une nouvelle solution voisine dans N 1 (s). Sinon, la solution courante s n’est pas modifiée
et on change de voisinage en générant une solution s0 ∈ N 2 (s). Plus généralement, on change de
voisinage à chaque fois que l’un d’entre eux n’est pas parvenu, après application de la procédure
de Recherche Locale, à améliorer la solution courante s. Par contre, dès qu’un voisinage permet
d’améliorer s, alors on recommence le processus avec le premier voisinage de la liste L. La RVV
peut donc être décrite comme suit.
Choisir une solution s ∈ S et poser t = 1 ;
Tant que aucun critère d’arrêt n’est satisfait faire
Choisir aléatoirement une solution s0 ∈ N t (s) ;
Appliquer une Recherche Locale en partant de s0 pour obtenir une solution s00 ;
Si f (s00 ) < f (s) alors poser s ← s00 et t ← 0 ;
Si t < ` alors poser t ← t + 1, sinon poser t ← 1 ;
Fin du tant que
Le fait d’utiliser plusieurs voisinages permet de diversifier l’exploration de S afin d’accéder à un
plus grand nombre de régions intéressantes, ce qui conduit à une méthode plus robuste que le
Recuit Simulé ou la Recherche Tabou. Le voisinage utilisé dans la Recherche Locale n’est pas
forcément le voisinage courant N t . Il peut même s’agir d’une structure de voisinage totalement
différente des voisinages de la liste L.
Considérons une fonction d qui mesure une distance d(s, s0 ) entre 2 solutions quelconques de S.
On peut par exemple définir d(s, s0 ) comme étant égal au nombre de composantes qui diffèrent
dans s et s0 . Soit Dt la distance moyenne entre toutes les paires s, s0 de solutions avec s0 ∈ N t (s).
Certains préfèrent choisir des structures de voisinages telles que les Dt croissent avec t. Une telle
stratégie permet de diversifier la recherche lorsqu’on est bloqué dans une région de l’espace de
recherche. D’autres préfèrent choisir des voisinages tels que les Dt sont décroissants lorsque t
croît. Ceci permet d’imiter la stratégie du Recuit Simulé, où l’on tente d’abord de déterminer
une bonne région, puis on intensifie petit à petit la recherche dans cette région.
Pour qu’une Recherche à Voisinages Variables soit efficace, il est recommandé d’utiliser des
structures de voisinage qui soient complémentaires en ce sens qu’un minimum local pour un
voisinage ne l’est pas forcément pour un autre.

6
Exemple. Considérons un problème de coloration des sommets d’un graphe G = (V, E). Supposons
que S soit l’ensemble des fonctions s : V → N. Une arête est dite en conflit si ses deux extrémités
u et v sont de même couleur (c’est-à-dire) s(u) = s(v)). De même, un sommet est dit en conflit
s’il est l’extrémité d’une arête en conflit. Considérons la fonction f qui compte le nombre d’arêtes
en conflit. Étant donnée une solution s, considérons les 2 voisinages suivants :
• N 1 consiste à changer la couleur d’un sommet en conflit, la nouvelle couleur devant être l’une
des couleurs utilisées dans le graphe.
• N 2 consiste à choisir un sommet v en conflit, à donner à v une couleur i différente de s(v) mais
présente sur au moins un sommet qui lui est adjacent, à choisir ensuite un sommet w voisin
de v et ayant la couleur i, et à donner la couleur s(v) à w. En d’autres termes, ce deuxième
voisinage permute les couleurs de v et w, où v et w sont adjacents, v est en conflit, et l’arête
reliant v et w n’est pas en conflit.
La figure ci-dessous illustre le fait qu’un minimum local pour un voisinage ne l’est pas forcément
pour l’autre. N1 N2

f(s')=2 f(s)=2 f(s')=0

f(s')=3 f(s)=4 f(s')=4

Comme dernier exemple de Recherche Locale, citons la Recherche Locale Guidée proposée
par Voudouris en 1997. Elle consiste à faire varier la fonction objectif durant le processus de
recherche, le but étant de rendre les minima locaux déjà visités moins attractifs. Le principe est
illustré ci-dessous.
fonction objectif

espace de solutions

Notons A = {A1 , . . . , Am } un ensemble de m attributs qui permettent de discriminer les solutions

de S. Par exemple, pour la coloration des sommets d’un graphe, on peut associer un attribut
à chaque arête du graphe et on dira qu’une coloration a l’attribut Ae si et seulement l’arête e
est en conflit dans la solution. Pour le problème du voyageur de commerce, on peut associer un
attribut à chaque arête e du graphe et dire qu’une tournée possède l’attribut Ae si e fait partie
de la tournée. Soit wi le poids de l’attribut Ai et définissons δi (s) = 1 si s possède l’attribut Ai ,
et δi (s) = 0 sinon. La Recherche Locale Guidée utilise la fonction objectif suivante :
m
X
g(s) = f (s) + λ wi δi (s)
i=1
où λ est un paramètre qui permet de faire varier l’importance du deuxième terme de cette
fonction. On peut modifier les poids wi au cours de l’algorithme. En règle général, lorsqu’on se
déplace d’une solution s vers une solution voisine s0 , on augmente le poids des attributs de s0 .
Différentes stratégies de modifications de poids sont possibles.
La Recherche Locale Guidée peut être décrite comme suit.
Choisir une solution s ∈ S et poser s∗ ← s ;
Tant que aucun critère d’arrêt n’est satisfait faire
Appliquer une Recherche Locale en partant de s, avec g comme fonction objectif ;
Soit s0 la solution résultant de cette recherche. Mettre à jour les poinds wi et poser s ← s0 ;
Si f (s) < f (s∗ ) alors poser s∗ ← s ;
Fin du tant que
7
 Méthodes basées sur des populations
Les méthodes basées sur des populations de solutions, aussi appelées méthodes évolutives,
font évoluer une population d’individus selon des règles bien précises. Ces méthodes alternent
entre des périodes d’adaptation individuelle et des périodes de coopération durant lesquelles les
individus échangent de l’information. Une méthode évolutive peut être décrite comme suit.
Générer une population initiale d’individus ;
Tant que aucun critère d’arrêt n’est satisfait faire
Exécuter une procédure de coopération ;
Exécuter une procédure d’adaptation individuelle ;
Fin du tant que
Les principales caractéristiques qui permettent de faire la différence entre diverses méthodes
évolutives sont les suivantes.
• Types d’individus. Les individus qui évoluent dans une méthode basée sur des populations
ne sont pas nécessairement des solutions. Il peut s’agir de morceaux de solutions ou d’objets
que l’on peut facilement transformer en solutions. Par exemple, pour un problème de tournées
de véhicules, un individu peut être la tournée d’un véhicule qui visite un sous-ensemble de
clients alors qu’une solution est un ensemble de tournées (et donc d’individus) qui visitent
tous les clients. Pour la coloration de graphes, chaque permutation des sommets peut être
considérée comme un individu. En appliquant l’algorithme séquentiel de coloration, on peut
transformer une permutation en une coloration et donc un individu en une solution.
• Type d’évolution. À chaque itération d’une méthode évolutive, de nouveaux individus sont
créés et la population de l’itération suivante sera ainsi constituée d’anciens individus (qui
auront survécu) et de nouveaux individus. La méthode évolutive doit indiquer comment décider
de la survie des individus et comment choisir les nouveaux individus qui vont entrer dans
la population. Lorsqu’on toute la population est modifiée d’une itération à l’autre (c’est-à-
dire que seuls les nouveaux individus sont conservés pour l’itération suivante), on parle de
remplacement générationnel. Par contre, si une partie seulement de la population varie d’une
itération à la suivante, on parle de remplacement stationnaire (steady state). La plupart des
méthodes évolutives utilisent des populations de taille fixe p, et on décide généralement de
garder les p meilleurs individus (parmi l’union des anciens et des nouveaux). Des populations
de taille variable (où on décide par exemple de manière aléatoire de la survie des individus)
sont cependant également possibles.
• Structure de voisinage. À chaque individu on associe un sous-ensemble d’autres individus
avec lesquels il peut échanger de l’information. Si chaque individu peut communiquer avec
tous les autres individus de la population, on parle de population non structurée. Par contre,
si chaque individu ne peut communiquer qu’avec un sous-ensemble d’individus, on parle de
population structurée. Les structures les plus communes sont la grille et le cercle.

structure structure
en grille en cercle
• Sources d’information. Le nombre d’individus qui coopèrent pour créer un nouvel individu
est souvent égal à 2. On parle alors de parents qui génèrent des enfants. On peut cependant
également combiner plus de 2 solutions pour créer des enfants. Certaines méthodes évolutives
utilisent par exemple l’information contenue dans toute la population pour créer un nouvel
individu. D’autres méthodes utilisent même toutes les populations de toutes les itérations
précédentes pour créer des enfants : on dit alors que la source d’information est l’historique
de la recherche. Par historique on entend généralement toute information qui ne peut pas être
obtenue en analysant les individus de la population courante ; la connaissance des compositions
des populations précédentes est nécessaire pour accéder à cette information.

8
 • Irréalisabilité. Un individu est un objet défini avec des règles bien précises. En combinant
des individus pour en créer de nouveaux, il se peut que le nouvel objet résultant de l’échange
d’information ne soit pas un individu admissible. Par exemple, supposons qu’un individu soit
une coloration sans conflit des sommets d’un graphe. Étant données deux colorations c1 et
c2 , on peut combiner celles-ci pour en créer une nouvelle en choisissant la couleur de chaque
sommet aléatoirement dans c1 ou c2 . Une telle coloration peut avoir des conflits et n’est donc
pas nécessairement admissible. Dans une telle situation, on peut réagir d’au moins 3 façons :
- rejeter le nouvel individu ;
- accepter le nouvel individu en pénalisant la non-admissibilité dans la fonction objectif ;
- utiliser une procédure de combinaisons qui évite la création d’individus non admissibles.
• Intensification. Lorsqu’on peut localiser l’information pertinente qui rend un individu meilleur
qu’un autre, il faut développer des procédures de coopération qui créent des enfants en combi-
nant adéquatement les informations pertinentes de chacun des parents. La phase d’adaptation
individuelle n’est alors pas indispensable au bon fonctionnement de la méthode évolutive.
C’est le cas par exemple pour les problèmes de tournées de véhicules où la bonne qualité d’une
solution peut être expliquée par l’utilisation d’arcs de faible coût. Cependant, pour de nom-
breux problèmes, une telle information pertinente est difficile à localiser. Par exemple, si π1
et π2 sont deux permutations des sommets d’un graphe et si c1 et c2 sont les deux colorations
résultant de l’algorithme séquentiel de coloration, avec c1 utilisant moins de couleurs que c2 , il
est difficile de localiser dans π1 les raisons qui font que cette permutation est meilleure que π2 .
Il est donc également difficile de transmettre une information pertinente lors de la phase de
coopération. Il est alors important d’utiliser une bonne procédure d’adaptation individuelle.
On a en général recours à une Recherche Locale qui est appliquée à chaque nouvel individu
de la population afin d’explorer les régions de l’espace de recherche qui leur sont proches.
• Diversification. Une difficulté majeure rencontrée lors de l’utilisation des méthodes évolutives
est leur convergence prématurée. Certains utilisent des procédures de bruitage qui modifient
légèrement les individus de manière aléatoire. Ce bruitage est appliqué indépendamment sur
chaque individu. Il diffère de l’utilisation d’une Recherche Locale par le fait que son effet sur la
qualité de la solution n’est pas prévisible. L’opérateur de bruitage le plus connu est la mutation
des algorithmes génétiques. Au lieu de modifier les individus aléatoirement, certains préfèrent
créer de nouveaux individus différents de ceux déjà rencontrés en faisant usage d’une mémoire
à long terme basée, par exemple, sur la récence ou la fréquence.
La méthode évolutive la plus connue est inspirée de la théorie de l’évolution et des processus
biologiques qui permettent à des organismes de s’adapter à leur environnement. Il s’agit de
l’algorithme génétique qui a été proposé dans le milieu des années 60 (Holland, 1962 ; Re-
chenberg, 1965 ; Fogel et al, 1966). L’algorithme décrit ci-dessous est une variante possible (il en
existe d’autres). Une description des sept caractéristiques est également donnée.
Générer une population initiale P0 de p ≥ 2 individus et poser i ← 0 ;
Tant que aucun critère d’arrêt n’est satisfait faire
Poser i ← i + 1 et Pi ← ∅ ;
Répéter p fois les 2 lignes suivantes
Créer une enfant E en croisant 2 individus I1 et I2 de Pi−1 ;
Appliquer une opérateur de mutation à E et rajouter l’enfant ainsi modifié à Pi ;
Fin du tant que
Types d’individus : il s’agit en général de solutions ;
Type d’évolution : remplacement générationnel avec une population de taille constante ;
Structure de voisinage : population possiblement structurée
Sources d’information : deux parents ;
Irréalisabilité : l’opérateur de croisement évite la création de solutions non admissibles ;
Intensification : aucune ;
Diversification : mutation.
9
La recherche dispersée (scatter search) a été proposée par Glover en 1977. Elle consiste à
générer un ensemble Di de points dispersés à partir d’un ensemble Ri de points de références.
Ces points dispersés sont obtenus en effectuant tout d’abord des combinaisons linéaires des points
de référence, avec possiblement des coefficients négatifs (ce qui veut dire que les points résultant
peuvent être à l’extérieur de l’enveloppe convexe des Ri . Si des points de l’ensemble Ci résultant de
ces combinaisons linéaires ne sont pas admissibles, on leur applique une procédure de réparation
pour obtenir un ensemble Ai de points admissibles. Les points de Ai sont finalement optimisés à
l’aide d’une Recherche Locale pour obtenir l’ensemble Di des points dispersés. Le nouvel ensemble
Ri+1 de points de référence est obtenu en sélectionnant des points dans Ri ∪ Di . Le pseudo-code
et les caractéristiques de cette méthode sont donnés ci-dessous.
Générer une population initiale R0 de p ≥ 2 individus et poser i ← 0 ;
Tant que aucun critère d’arrêt n’est satisfait faire
Créer un ensemble Ci de points en effectuant des combinaisons linéaires des points de Ri ;
Réparer les points non admissibles de Ci pour obtenir un ensemble Ai admissible ;
Appliquer une Recherche Locale sur chaque point de Ai ; soit Di l’ensemble résultant ;
Créer Ri+1 en sélectionnant p points dans Ri ∪ Di , et poser i ← i + 1 ;
Fin du tant que
Types d’individus : des solutions admissibles ;
Type d’évolution : remplacement stationnaire avec une population de taille constante ;
Structure de voisinage : population non structurée ;
Sources d’information : au moins deux parents ;
Irréalisabilité : les points non admissibles sont réparés ;
Intensification : Recherche Locale ;
Diversification : combinaison non convexe des points de référence.
La méthode à mémoire adaptative a été proposée par Rochat et Taillard en 1995. Elle
fonctionne avec une mémoire centrale chargée de stocker les composantes des meilleures solutions
rencontrées. Ces composantes sont combinées afin de créer de nouvelles solutions qui sont réparés
si elle ne sont pas admissibles. Une Recherche Locale est ensuite appliquée et les composantes de
la solution ainsi obtenue sont considérées pour éventuellement faire partie de la mémoire centrale.
Au début de la recherche, la mémoire centrale contient des composantes provenant de solutions
très diverses et le processus de combinaison aura donc tendance à créer une diversité de nouvelles
solutions. Plus la recherche avance, et plus la mémoire centrale aura tendance à ne mémoriser
que les composantes d’un sous-ensemble très restreint de solutions. La recherche devient donc
petit à petit un processus d’intensification. Le pseudo-code et les caractéristiques de la méthode
à mémoire adaptative sont donnés ci-dessous.
Générer un ensemble de solutions et introduire leurs composantes dans la mémoire centrale ;
Tant que aucun critère d’arrêt n’est satisfait faire
Combiner les composantes de la mémoire centrale pour créer de nouvelles solutions ;
Réparer, si nécessaire, les solutions non admissibles ainsi générée ;
Appliquer une Recherche Locale sur chaque nouvelle solution admissible ;
Mettre à jour la mémoire centrale en ôtant certaines composantes et en y insérant
certaines provenant des nouvelles solutions générées ;
Fin du tant que
Types d’individus : des composantes de solutions admissibles ;
Type d’évolution : remplacement stationnaire avec une population de taille constante ;
Structure de voisinage : population non structurée ;
Sources d’information : au moins deux parents ;
Irréalisabilité : les solutions non admissibles sont réparées ;
Intensification : Recherche Locale et intensification implicite durant les dernières itérations ;
Diversification : diversification implicite durant les premières itérations.

10
L’optimisation par colonies de fourmis (Ant Colony Optimisation) est une méthode évolutive
inspirée du comportement des fourmis à la recherche de nourriture. Cet algorithme a été proposé
par Dorigo en 1992. Il est connu que les fourmis sont capables de déterminer le chemin le plus court
entre leur nid et une source de nourriture. Ceci est possible grâce à la phéromone, une substance
que les fourmis déposent sur le sol lorsqu’elles de déplacent. Lorsqu’une fourmi doit choisir entre
deux directions, elle choisit avec une plus grande probabilité celle comportant une plus forte
concentration de phéromone. C’est ce processus coopératif qu’on tente d’imiter. Chaque fourmi
est un algorithme constructif qui génère des solutions. Soit D(s) l’ensemble des décisions possibles
que peut prendre une fourmi pour compléter une solution partielle s. La décision d ∈ D(s) qu’elle
choisira dépendra de deux facteurs, à savoir la force gloutonne et la trace :
• la force gloutonne est une valeur ηd (s) qui représente l’intérêt qu’a la fourmi à prendre la
décision d étant donnée la solution partielle s. En général, cette valeur est proportionnelle à
la qualité de la nouvelle solution partielle obtenue en prenant la décision d.
• la trace τd représente l’intérêt historique qu’a la fourmi de prendre la décision d. Plus cette
quantité est grande, plus il a été intéressant dans le passé de prendre cette décision.
Étant donné un paramètre α ∈ R+ qui donne plus ou moins d’importance à la trace, la fourmi
va prendre la décision d avec une probabilité p(s, d) définie comme suit :
ηd (s)τdα
p(s, d) = P α
e∈D(s) ηe (s)τe
Lorsqu’une fourmi a complété la construction de sa solution, elle laisse une trace sur le chemin
emprunté. Cette trace est proportionnelle à la qualité de la solution construite. Un processus
d’évaporation de la trace permet d’oublier les choix réalisés dans un lointain passé et de donner
plus d’importance aux choix réalisés plus récemment. Plus précisément, soit ρ ∈]0, 1[ un para-
mètre d’évaporation, soit A l’ensemble des fourmis, et soit f (a) la valeur de la solution produite
par la fourmi a ∈ A. La qualité de la solution produite par la fourmi a est donc inversement
proportionnelle à f (a). La mise à jour de la trace sur la décision d est réalisée comme suit :
X
τd = (1 − ρ)τd + c ∆d (a)
a∈A
 1
f (a)
si la fourmi a a réalisé le choix d
où c ∈ R+ est une constante et ∆d (a) =
0 sinon
Le pseudo-code et les caractéristiques d’une optimisation par colonies de fourmis sont donnés
ci-dessous.
Poser τd ← 0 pour toute décision d possible ;
Tant que aucun critère d’arrêt n’est satisfait faire
Construire |A| solutions en tenant compte de la force gloutonne et de la trace ;
Mettre à jour les traces τd ainsi que la meilleure solution rencontrée ;
Fin du tant que
Types d’individus : solutions admissibles obtenues à l’aide d’un algorithme constructif ;
Type d’évolution : remplacement générationnel avec une population de taille constante ;
Structure de voisinage : population non structurée ;
Sources d’information : historique de la recherche (mémorisé dans la trace) ;
Irréalisabilité : l’algorithme constructif ne produit pas de solution non admissible ;
Intensification : aucune ;
Diversification : aucune.
Cet algorithme peut être amélioré de diverses manières. On peut par exemple appliquer une
Recherche Locale sur chaque solution produite par l’algorithme constructif (processus d’inten-
sification). Certains chercheurs suggèrent de prendre un certain pourcentage de décisions en ne
tenant compte que de la force gloutonne (les autres décisions étant prises en combinant la force
gloutonne et la trace). Il existe de multiples autres variations.

11
La tendance actuelle est d’avoir recours à des algorithmes dits hybrides. Il existe plusieurs types
d’hybridations possibles :
• on peut utiliser une Recherche Locale dans les méthodes évolutives (c’est ce que nous avons
déjà fait à multiples reprises). L’avantage est que la Recherche Locale réduit le danger de
passer à côté d’une solution optimale sans la voir. En règle générale, une méthode évolutive est
excellente pour détecter de bonnes régions dans l’espace de recherche alors qu’une Recherche
Locale explore efficacement les régions prometteuses.
• on peut exécuter en parallèle diverses métaheuristiques, voire même plusieurs fois la même
métaheuristique mais avec divers paramètres. Ces processus parallèles communiquent entre
eux régulièrement pour échanger de l’information sur leurs résultats partiels.
• on peut combiner les métaheuristiques avec des méthodes exactes. Une métaheuristique peut
par exemple fournir des bornes à une méthode de type branch-and-bound. Aussi, une méthode
exacte peut donner lieu à une technique efficace pour la détermination du meilleur voisin
d’une solution (ce qui peut s’avérer plus judicieux que de choisir la meilleure solution parmi
un échantillon de voisins).
Pour terminer ce chapitre, voici quelques principes qui permettent de guider le processus d’ad-
patation d’une métaheuristique à un problème concret.
Pour la Recherche Locale
Principe 1 : afin de faciliter la génération d’une solution voisine, il ne faut pas hésiter à travailler
dans l’espace des solutions non admissibles ou partielles, en modifiant, au besoin, la fonction
objectif à optimiser
Principe 2 : il devrait être possible d’atteindre une solution optimale en partant de n’importe
quelle solution initiale.
Principe 3 : afin de bien pouvoir guider la recherche d’une solution optimale dans S, il est
important que les solutions s0 ∈ N (s), voisines de s, ne soient pas trop différentes de s.
Principe 4 : il ne faut pas hésiter à donner du relief à l’espace des solutions. Ainsi, si deux
solutions s1 et s2 ont apparemment la même valeur pour l’objectif que l’on optimise, il se peut
que s1 soit plus susceptible que s2 de mener la Recherche Locale vers une solution optimale, et
il ne faut alors pas hésiter à rajouter une composante dans la fonction objectif qui reflète cet
avantage qu’a s1 sur s2 .
Principe 5 : pour des questions d’efficacité et permettre ainsi un très grand nombre d’itérations
en un temps raisonnable, il est préférable de définir des voisinages qui permettent l’évaluation
d’une solution voisine en ne calculant que l’écart de valeur par rapport à la solution courante
(calcul incrémental).
Principe 6 : une solution s0 ∈ N (s), voisine de s, ne doit pas contenir les mêmes défauts que
s. La solution voisine doit être obtenue en modifiant une partie de s qui est responsable de sa
valeur f (s).

Pour les méthodes évolutives

Principe 7 : durant la phase de coopération, ce sont des informations pertinentes qui doivent
être échangées, plutôt que des parties choisies aléatoirement dans chaque individu.
Principe 8 : les bonnes informations échangées par des individus parents doivent se retrouver
dans les individus enfants.
Principe 9 : l’intensification est un ingrédient nécessaire aux méthodes évolutives pour qu’elles
soient compétitives avec d’autres métaheuristiques. Le plus souvent, cette intensification est
réalisée à l’aide d’une Recherche Locale.
Principe 10 : il est important de préserver la diversité des individus dans la population, pour
éviter une convergence prématurée vers une population contenant des individus presque tous
identiques entre eux.

12