La recherche locale

Partir d'une solution et la retoucher

Le chapitre sur les heuristiques constructives a construit des solutions d'un seul jet : le plus proche voisin pour la plaque, le rangement par longueur décroissante pour les barres, une règle de priorité pour la machine. Chaque règle décide vite et ne revient jamais sur une décision. La recherche locale fait l'inverse : elle prend une solution déjà complète, quelle qu'en soit l'origine, et la modifie par de petits changements.

Sur la plaque P-217, le plus proche voisin donne l'ordre T1, T7, T10, T11, T5, T6, T12, T8, T3, T2, T9, T4. Les dernières étapes traversent la plaque pour aller chercher T2, puis reviennent vers T9 et T4 qu'on avait laissés derrière soi : la règle, qui ne regarde que le trou le plus proche, s'est acculée. Une retouche possible : retourner le passage T8, T3, T2, ce qui donne T1, T7, T10, T11, T5, T6, T12, T2, T3, T8, T9, T4.

Presque 28 mm de gagnés, en ne touchant que deux trajets. L'idée tient dans cette phrase : pour juger une retouche, il suffit de regarder ce qu'elle change.

Un mouvement ne se définit pas sur « la solution » en général : il se définit sur sa représentation, celle qu'a posée le premier chapitre. Permuter deux éléments d'une permutation donne encore une permutation, donc encore une tournée valide. Changer un bit d'une sélection de commandes donne encore une sélection, mais pas toujours une sélection qui tient dans la capacité. Le voisinage est donc la moitié de la représentation : deux voisinages sur la même représentation donnent deux recherches différentes.

Le voisinage : trois façons de retoucher un ordre

Pour un ordre de perçage, trois mouvements reviennent partout.

Un exemple sur cinq trous, l'ordre 1, 2, 3, 4, 5 :

Les trois mouvements ne se valent pas. L'échange change jusqu'à quatre trajets, l'insertion trois, le 2-opt deux seulement. Un mouvement qui change peu de trajets change peu la longueur : c'est ce qu'on attend d'un « petit » changement, et ce qui rend le 2-opt bien adapté aux tournées.

Chaque voisinage a une taille, et elle se compte. Pour $n$ trous, il y a $n(n-1)/2$ paires de positions, donc $n(n-1)/2$ échanges. L'insertion offre $(n-1)^2$ mouvements, car déplacer un trou d'une position vers la suivante revient à déplacer le suivant d'une position vers la précédente, et on ne le compte qu'une fois. Le 2-opt offre $n(n-1)/2 - 1$ mouvements : retourner tout l'ordre redonne la même tournée parcourue à l'envers, ce n'est pas un voisin. Le code les énumère et les compte.

Pour les douze trous de P-217, 66 échanges, 121 insertions et 65 mouvements 2-opt : quelques centaines de voisins au plus, qu'on examine en un clin d'œil. Pour une plaque de soixante trous, il y en a 1 770, 3 481 et 1 769. Le voisinage grossit comme le carré du nombre de trous, alors que l'espace des solutions grossit comme sa factorielle : on explore toujours une infime partie de l'espace, mais on l'explore là où la solution courante a des chances d'être améliorée.

Les autres problèmes de Valdrome ont les leurs, et le tableau suivant les met côte à côte. Dans chaque cas, le voisinage se lit sur la représentation posée au premier chapitre.

Le 2-opt : défaire un croisement

Le mouvement de la tournée, c'est le 2-opt. Il a une propriété géométrique qui fait son succès.

Prenons deux trajets d'une tournée qui se croisent, l'un de $a$ à $b$, l'autre de $c$ à $d$. Retirer ces deux trajets sépare la tournée en deux morceaux ; on peut les recoller de deux manières, et une seule redonne une tournée d'un seul tenant : $a$ vers $c$ et $b$ vers $d$, ce qui retourne le segment entre $b$ et $c$. Dans le plan, en distance euclidienne, la somme des deux nouveaux trajets est strictement plus courte que celle des deux anciens, par l'inégalité triangulaire : les deux trajets qui se croisent sont les diagonales d'un quadrilatère convexe, et la somme des diagonales dépasse celle de deux côtés opposés. Une tournée où deux trajets se croisent n'est jamais optimale, et le 2-opt sait la raccourcir.

La réciproque est fausse : une tournée peut n'avoir aucun croisement et se laisser encore améliorer, ou l'être par un mouvement qui ne défait aucun croisement. Le 2-opt est un voisinage, pas seulement une chasse aux croisements.

Le calcul de la longueur du voisin est plus économique qu'il n'y paraît. Retourner le segment de la position $i$ à la position $j$ ne change que deux trajets, de $a$ à $b$ et de $c$ à $d$, où $a$ est le point avant la position $i$, $b$ celui en position $i$, $c$ celui en position $j$ et $d$ celui qui suit. Le reste de la tournée est lu à l'envers ou non, la distance est la même dans les deux sens : rien d'autre ne bouge. La variation de longueur vaut

où $\mathrm{dist}$ est la distance entre deux points (le dist du code qui suit) : une tournée de soixante trous se juge ainsi en quatre distances au lieu de soixante et une. Le code vérifie que les deux calculs concordent sur le mouvement retouché plus haut.

Le voisin est évalué en quatre distances, alors que le recalcul complet en demande treize. Sur une grande plaque l'écart devient considérable, et c'est ce qui rend le 2-opt praticable : une descente évalue des dizaines de milliers de voisins.

La figure suivante fait retoucher la tournée à la main. Elle part du plus proche voisin. Choisir deux arêtes de la tournée, en cliquant dessus, fait apparaître ce que le mouvement retirerait, ce qu'il ajouterait, et sa variation de longueur ; il ne s'applique que sur demande. On peut aussi changer de voisinage, ou lancer la descente entière.

La descente

Une descente répète un même geste : examiner les voisins de la solution courante, se déplacer vers un voisin meilleur, recommencer ; elle s'arrête quand aucun voisin n'est meilleur. Deux variantes se distinguent par la façon de choisir le voisin.

La première fait des pas peu coûteux et souvent nombreux ; la seconde, des pas plus coûteux et moins nombreux. Aucune n'est plus juste que l'autre : elles s'arrêtent parfois sur des solutions différentes, et le code suivant les compare sur la plaque, depuis deux points de départ. Ses deux dernières parties servent aux deux sections suivantes.

Le premier tableau qui s'affiche est riche, et il faut le lire avec méthode. Depuis le plus proche voisin, le 2-opt descend de 692,06 à 633,23 mm en trois pas au meilleur voisin (692,06, puis 664,14, puis 635,83, puis 633,23) et en cinq au premier voisin : les deux arrivent au même endroit. L'échange, lui, s'arrête à 661,53 mm, en deux pas. Depuis l'ordre d'écriture, tout change : le 2-opt s'arrête à 647,35 mm, l'échange à 724,18 mm au premier voisin et à 688,22 mm au meilleur, et l'insertion, selon la variante, à 633,23 ou à 647,35 mm. Le résultat d'une descente dépend de trois choses : le point de départ, le voisinage, et la variante.

La dernière colonne, « voisins évalués », compte le travail total, et elle ne donne pas toujours raison à la première variante : par pas, le premier voisin coûte moins, mais il faut plus de pas. Depuis l'ordre d'écriture, le 2-opt évalue 574 voisins au premier voisin contre 455 au meilleur, alors que l'insertion en évalue 524 contre 1 089 : au total, le premier voisin n'est pas toujours le moins cher.

L'optimum local

Une descente s'arrête quand aucun voisin n'est meilleur. Ce n'est pas la même chose que « la solution est la meilleure ».

Le bloc de code de la section précédente le montre sur P-217, dans sa seconde partie, sous le titre « optimums locaux » : il fait descendre par le 2-opt depuis l'ordre d'écriture, puis compte, pour chacun des trois voisinages, les voisins qui raccourcissent encore la tournée obtenue. Rien à recopier : le préambule (plaque, voisinages, descente) est le même.

Deux constats. D'abord, la tournée T1, T7, T9, T11, T10, T8, T3, T12, T2, T6, T5, T4 mesure 647,35 mm : aucun voisin ne la raccourcit, quel que soit le voisinage, et pourtant la meilleure tournée de P-217 mesure 633,23 mm, deux pour cent de moins. On est piégé : pour la sortir de là, il faudrait passer par des tournées plus longues, ce qu'une descente refuse par construction. Ensuite, la tournée à 661,53 mm, optimum local pour l'échange, ne l'est pas pour le 2-opt : un seul mouvement de plus la ramène à 633,23 mm. Un optimum local n'est pas une propriété de la tournée, c'est une propriété de la tournée et du voisinage.

Sur une grande plaque

Douze trous se retouchent à la main. Pour éprouver la méthode, Valdrome a une plaque plus grande, P-600 : soixante trous sur une plaque de 600 par 400 mm, l'outil partant de l'origine et y revenant, à 30 mm par seconde comme sur P-217. Ses coordonnées, entières en millimètres, sont engendrées par une formule reproductible, un générateur congruentiel de graine 598 : chacun peut la regénérer, elle ne change jamais. La graine 598 est la première en dessous de 600 pour laquelle aucun trou n'a deux voisins exactement à la même distance, ce qui rendrait le plus proche voisin ambigu. La figure suivante fait retoucher cette plaque. Le nombre de voisins y est grand, et le compteur « Qui raccourcissent » montre l'état de la descente. Aucune référence n'est donnée avant l'essai.

Le code suivant engendre la plaque, applique le plus proche voisin, puis le 2-opt au meilleur voisin avec la variation en quatre distances, et enfin cinquante descentes depuis des ordres tirés au hasard (graine 598). Sa dernière partie calcule deux bornes, commentées plus bas.

Le plus proche voisin mesure 3 588,87 mm, le 2-opt le ramène à 2 944,01 mm en treize pas, soit 18 % de moins. Ce n'est plus une affaire de coup d'œil. Quelle est la distance à l'optimum ? Pour soixante trous, la force brute est hors de question, mais un solveur exact y parvient : milp, celui du chapitre 3, alimenté par une formulation de la tournée que ce parcours ne détaille pas (une variable 0 ou 1 par arête, exactement deux arêtes en chaque point, puis des coupes qui interdisent les tournées en plusieurs boucles, ajoutées au fur et à mesure tant que la solution en comporte plusieurs), démontre que la meilleure tournée de P-600 mesure 2 788,70 mm. Il faut quelques tours de résolution, de moins d'une seconde chacun : cela tient à la taille de cette instance, et le chapitre 3 a montré que l'exact explose quand elle grossit. Ce n'est pas une « meilleure connue » : c'est l'optimum, prouvé. Le plus proche voisin est donc à 28,7 % de l'optimum, le plus proche voisin suivi du 2-opt à 5,6 %, et la meilleure des cinquante descentes (graine 598) à 0,8 %.

Deux bornes simples, que la dernière partie du bloc précédent calcule avec networkx, encadrent l'optimum par en dessous sans rien résoudre. Une tournée privée d'une arête est un arbre couvrant, donc l'arbre couvrant minimal de la plaque, départ compris, est une borne inférieure. Le 1-arbre la resserre : l'arbre couvrant minimal des trous seuls, plus les deux plus courts trajets du départ, car la tournée arrive au départ et en repart.

L'arbre couvrant minimal vaut 2 286,36 mm et le 1-arbre 2 439,15 mm, soit 87,5 % de l'optimum. Ce sont des bornes lâches, comme celles du chapitre 3 avant la relaxation, mais elles s'obtiennent en une fraction de seconde et sans connaître l'optimum. Avec le 1-arbre pour seule référence, le 2-opt depuis le plus proche voisin (2 944,01 mm) est garanti à au plus 20,7 % de l'optimum, et la meilleure des cinquante descentes (2 810,44 mm) à au plus 15,2 % : l'écart garanti du chapitre 3, sans avoir résolu le problème.

Les redémarrages

Une descente s'arrête dans le premier creux qu'elle rencontre, et le creux dépend du point de départ. Il y en a plusieurs, plus ou moins profonds. L'idée des redémarrages multiples est de ne pas parier sur un seul départ : on lance plusieurs descentes, chacune depuis une solution de départ différente (typiquement tirée au hasard), et on garde le meilleur optimum local rencontré. C'est la plus simple des stratégies pour sortir d'un creux, et elle est étonnamment efficace quand la descente est rapide.

Le code de ces essais est déjà écrit : c'est la dernière partie du bloc de la section « La descente », sous le titre # ---- Suite : les redemarrages. Rien à recopier : la plaque, les trois voisinages et la descente sont ceux de plus haut. Pour chacun des trois voisinages, il lance cent descentes au meilleur voisin depuis cent ordres tirés au hasard, compte les optimums locaux distincts, puis détaille les plus fréquents pour le 2-opt.

Sur P-217, cent descentes 2-opt depuis cent ordres tirés au hasard (graine 217) se répartissent en sept optimums locaux différents, du meilleur (633,23 mm, atteint 38 fois) au pire (679,32 mm). Le voisinage compte autant que le nombre d'essais, et ce n'est pas sa taille qui décide : l'échange (66 voisins) est plus grand que le 2-opt (65), et pourtant ses descentes ne trouvent la meilleure tournée que 6 fois sur 100 et se dispersent sur 49 optimums locaux, jusqu'à 779,42 mm, parce qu'un échange de deux trous éloignés change quatre trajets d'un coup. L'insertion (121 voisins, trois trajets changés) la trouve 62 fois. Dans tous les cas, le meilleur des essais est meilleur que la moyenne des essais : c'est ce que les redémarrages achètent, en temps de calcul.

La figure suivante le fait sentir sur P-600, où les creux sont nombreux. Chaque descente est lancée depuis un ordre tiré au hasard, et son optimum local est rangé dans un histogramme.

Les chiffres du texte (meilleure, médiane et pire des cinquante descentes de P-600, plus haut) sont ceux d'une graine fixée, 598 : ils se rejouent en Python à l'identique, mais ceux de la figure varient d'un lecteur à l'autre, et d'une série à l'autre.

Les redémarrages ont un défaut : chaque descente repart de zéro, et ne profite pas de ce que les précédentes ont trouvé. Les chapitres suivants reprennent l'idée par un autre bout : ne plus s'arrêter dans un creux, mais se donner le moyen d'en sortir.

Le squelette commun

Presque toutes les méthodes de ce parcours ont la même charpente : une solution courante, un voisin tiré, un coût mesuré, une décision de s'y déplacer ou non, et le souvenir de la meilleure solution vue. Le tabou en garde l'esprit mais examine tout le voisinage à chaque pas (une seconde forme, au chapitre 7), et les algorithmes génétiques et les fourmis en sortent tout à fait. Écrire cette charpente une fois évite de la réécrire à chaque chapitre.

chercher fait quatre choses, dans cet ordre, autant de fois que demandé : tirer un voisin de la solution courante, le mesurer, décider de l'accepter, et retenir la meilleure solution rencontrée. Rien d'autre. Trois pièces changent d'un problème à l'autre, et ce sont celles qu'on a apprises à poser :

La quatrième pièce, accepter, est ici la plus simple qui soit : la descente est le cas où l'on n'accepte un voisin que s'il est strictement meilleur. C'est elle qui, avec un nombre suffisant d'itérations, s'arrête dans un optimum local. Le squelette tire un voisin au hasard plutôt que de parcourir tout le voisinage : la descente devient ainsi une suite de tirages en nombre fixé, et non une boucle qui s'arrête d'elle-même. Avec assez d'itérations, elle a essayé presque tous les voisins de la solution où elle s'est arrêtée, et la longue série de tirages sans progrès en est la signature.

Lire la dernière ligne du tableau affiché : la même charpente, sans y toucher, retouche une tournée, un planning de machine et une affectation. Les résultats varient d'une graine à l'autre, parce que chaque graine tire des voisins dans un autre ordre, et donc s'arrête dans un autre optimum local. Sur l'affectation, ils s'étalent de 99 à 112 minutes alors que la meilleure affectation en vaut 95 : la descente n'y trouve l'optimum sur aucune des cinq graines, ce qui rappelle à quoi servent les redémarrages.

Les erreurs d'un débutant

Exercices type

La méthode

1. Choisir la représentation et vérifier qu'un mouvement lui reste fidèle : une permutation reste une permutation.
2. Choisir un voisinage et compter ses voisins. Trop petit, la descente se bloque ; trop grand, chaque pas coûte trop.
3. Écrire le coût du voisin par la variation seule quand c'est possible (quatre distances pour un 2-opt), et la vérifier contre un recalcul complet.
4. Construire une solution de départ par une règle simple : plus proche voisin, rangement par longueur décroissante, priorité.
5. Descendre : premier voisin ou meilleur voisin, jusqu'à l'optimum local. Compter les pas et les voisins évalués.
6. Redémarrer depuis plusieurs départs, et rendre le meilleur, la moyenne et le pire.
7. Juger le résultat par une borne ou par un optimum connu, et annoncer l'écart.
8. Passer par le squelette chercher quand on veut changer la règle d'acceptation : la descente est le cas accepter = seulement si meilleur.

Synthèse

• La recherche locale part d'une solution complète et la retouche par de petits mouvements ; les solutions obtenues sont ses voisins, et leur ensemble est le voisinage.
• Un mouvement se définit sur la représentation. Sur une permutation : l'échange ($n(n-1)/2$ voisins), l'insertion ($(n-1)^2$) et le 2-opt ($n(n-1)/2 - 1$).
• Le 2-opt retourne un segment et ne remplace que deux trajets : sa variation se calcule en quatre distances, et il défait tout croisement, car en distance euclidienne une tournée qui se croise n'est jamais optimale.
• Une descente s'installe sur un voisin meilleur jusqu'à n'en plus trouver : au premier voisin qui améliore, ou au meilleur voisin.
• Elle s'arrête sur un optimum local, qui n'est en général pas l'optimum : sur P-217, 647,35 mm contre 633,23 mm.
• L'optimum local dépend du voisinage (un optimum d'échange n'en est pas un pour le 2-opt) et du point de départ.
• Les redémarrages lancent plusieurs descentes depuis des départs différents et gardent le meilleur : sur P-600, la meilleure de cinquante est à 0,8 % de l'optimum démontré, 2 788,70 mm, alors que la médiane est à 5,3 %.
• Le squelette chercher(initiale, voisin, cout, accepter, iterations) sert à tout problème : seuls la représentation, le voisin et le coût changent, et la descente est le cas accepter = seulement si meilleur.
• Le recuit simulé ne changera que accepter ; le tabou ajoutera une mémoire ; le génétique et les fourmis sortiront du moule.

Et ensuite

La descente est rapide et se bloque. Le chapitre suivant garde le squelette et n'y change que la règle d'acceptation : accepter parfois un voisin moins bon, avec une probabilité qui décroît, c'est le recuit simulé. Pour situer ce que vaut une tournée sans connaître l'optimum, les bornes du chapitre 3 servent de règle ; pour la représentation et le coût, le chapitre 1.