Complexité des problèmes et heuristiques
187
Cette transformation est appelée 2-opt.
Pour qu'une fonction de voisinage soit intéressante, il faut qu'elle observe deux
conditions :
- elle doit être susceptible de fournir de proche en proche toutes les solutions du
problème,
- elle doit être réversible : si
Cette notion de voisinage introduit une méthode générale de recherche d'une bonne
solution : il s'agit de la méthode d'amélioration itérative :
a) On part d'une solution initiale .
b) On cherche dans le voisinage de
une solution qui améliore la fonction (cette
recherche peut prendre plusieurs formes : exhaustive - on cherche tous les voisins et on
prend le meilleur, systématique - on ne cherche pas tous les voisins mais ceux donnés
par une règle définie à l'avance, aléatoire (on tire un voisin au hasard) .
c) On remplace
si
est en effet meilleur et on recommence en .
d) On s'arrête lorsque l'on ne trouve pas dans le voisinage de
de solutions
améliorantes.
Il est clair que cette méthode (qui peut être fort longue) a l'inconvénient d'aboutir dans
un certain nombre de cas à un minimum local (l'algorithme du simplexe, qui appartient
bien à cette classe de méthode, avec une fonction de voisinage consistant à échanger une
variable de base et une variable hors base ne comporte pas cet inconvénient : il permet
d'obtenir à coup sûr l'optimum).
C'est pourquoi des techniques ont été imaginées pour « sortir » d'un optimum local
obtenu par amélioration itérative. La plus connue est constituée par le recuit simulé.
8.2.3.1. Le recuit simulé
Cette méthode, mise au point au début des années quatre-vingt aux Etats Unis et en
Slovaquie, est fondée tout d'abord sur une idée intéressante et simple à la fois, qui mixe
en quelque sorte les principes d'exploration combinatoire et la simulation aléatoire : on
adopte la méthode générale d'amélioration itérative, mais pour éviter de se faire
« piéger » par un minimum local, on accepte des itérations qui dégradent -
provisoirement espère-t-on - la fonction économique, mais non systématiquement : on ne
le fait qu'en fonction de certaines probabilités.
Quant au terme de recuit simulé, il vient d'une analogie avec la thermodynamique et la
métallurgie. Pour obtenir un cristal, état d'énergie minimale du matériau, on le porte à
une température élevée et on diminue cette dernière. Le résultat obtenu dépend de la
vitesse de refroidissement : si cette dernière est très élevée, on obtient un état métastable,
correspondant à un minimum local d'énergie ; c'est le phénomène de la trempe, qui
conduit à des matériaux très résistants. Si on veut au contraire obtenir la structure
cristalline, il faut faire baisser la température lentement.
187
Cette transformation est appelée 2-opt.
Pour qu'une fonction de voisinage soit intéressante, il faut qu'elle observe deux
conditions :
- elle doit être susceptible de fournir de proche en proche toutes les solutions du
problème,
- elle doit être réversible : si
Cette notion de voisinage introduit une méthode générale de recherche d'une bonne
solution : il s'agit de la méthode d'amélioration itérative :
a) On part d'une solution initiale .
b) On cherche dans le voisinage de
une solution qui améliore la fonction (cette
recherche peut prendre plusieurs formes : exhaustive - on cherche tous les voisins et on
prend le meilleur, systématique - on ne cherche pas tous les voisins mais ceux donnés
par une règle définie à l'avance, aléatoire (on tire un voisin au hasard) .
c) On remplace
si
est en effet meilleur et on recommence en .
d) On s'arrête lorsque l'on ne trouve pas dans le voisinage de
de solutions
améliorantes.
Il est clair que cette méthode (qui peut être fort longue) a l'inconvénient d'aboutir dans
un certain nombre de cas à un minimum local (l'algorithme du simplexe, qui appartient
bien à cette classe de méthode, avec une fonction de voisinage consistant à échanger une
variable de base et une variable hors base ne comporte pas cet inconvénient : il permet
d'obtenir à coup sûr l'optimum).
C'est pourquoi des techniques ont été imaginées pour « sortir » d'un optimum local
obtenu par amélioration itérative. La plus connue est constituée par le recuit simulé.
8.2.3.1. Le recuit simulé
Cette méthode, mise au point au début des années quatre-vingt aux Etats Unis et en
Slovaquie, est fondée tout d'abord sur une idée intéressante et simple à la fois, qui mixe
en quelque sorte les principes d'exploration combinatoire et la simulation aléatoire : on
adopte la méthode générale d'amélioration itérative, mais pour éviter de se faire
« piéger » par un minimum local, on accepte des itérations qui dégradent -
provisoirement espère-t-on - la fonction économique, mais non systématiquement : on ne
le fait qu'en fonction de certaines probabilités.
Quant au terme de recuit simulé, il vient d'une analogie avec la thermodynamique et la
métallurgie. Pour obtenir un cristal, état d'énergie minimale du matériau, on le porte à
une température élevée et on diminue cette dernière. Le résultat obtenu dépend de la
vitesse de refroidissement : si cette dernière est très élevée, on obtient un état métastable,
correspondant à un minimum local d'énergie ; c'est le phénomène de la trempe, qui
conduit à des matériaux très résistants. Si on veut au contraire obtenir la structure
cristalline, il faut faire baisser la température lentement.