La recherche tabou

Quand la descente s'arrête

Le chapitre sur la recherche locale a posé la règle de la descente : tant qu'un voisin est meilleur, s'y installer ; sinon, s'arrêter. Sur les dix ordres de fabrication de la machine, avec l'échange de deux ordres pour mouvement (45 voisins), la descente au meilleur voisin part de l'ordre d'écriture, à 45 heures de retard, et s'arrête en trois pas sur l'ordre suivant :

Total : 18 heures. Aucun échange ne descend en dessous de 18, et pourtant le chapitre sur les heuristiques constructives a déjà montré qu'un meilleur ordre existe. Regarder de plus près ce que la descente refuse. Elle refuse les voisins qui ne sont pas strictement meilleurs : six échanges laissent le total à 18 heures, deux le montent à 19, tous les autres font pire. Or un voisin à 18 heures n'est pas un cul-de-sac : c'est un autre ordre d'où d'autres échanges sont possibles. La descente ne le voit pas, parce que sa règle d'arrêt est « aucun voisin strictement meilleur ». Des solutions de même coût, reliées d'échange en échange, forment un palier : la descente ne s'y engage jamais, la recherche tabou s'y promène.

Une heure de plus, et l'échange n'a aucune raison d'être pris par une descente. C'est précisément ce que la recherche tabou accepte de faire.

Prendre le meilleur voisin, même moins bon

Cette règle change la nature de la recherche. Une descente ne peut que descendre : elle s'arrête au fond du premier creux. Une recherche qui prend le meilleur voisin quoi qu'il arrive remonte de l'autre côté du creux, et peut retomber dans un creux voisin, plus profond.

Elle a un défaut évident. Quand on vient de quitter la solution $s$ pour un voisin $s'$ moins bon, quel est le meilleur voisin de $s'$ ? Très souvent, $s$ elle-même : c'est un voisin de $s'$ (le même mouvement, à l'envers), et elle est meilleure que tous les autres. La recherche y retourne, puis repart vers $s'$, puis revient : elle cycle, en deux pas, sur deux solutions. Sans autre précaution, prendre le meilleur voisin ne fait pas sortir du creux, cela fait osciller sur son bord.

La mémoire : ce qu'on rend tabou

L'idée est de noter ce qu'on vient de faire, et d'interdire de le défaire pendant quelque temps. Reste à décider ce qu'on note.

Sur un échange, l'attribut naturel est la paire d'ordres échangés. Échanger O3 et O5 rend tabou de les échanger de nouveau, et défaire un échange, c'est échanger les mêmes deux ordres : le retour en arrière est exactement ce que la mémoire interdit. Les autres problèmes de Valdrome ont chacun leur attribut.

Deux autres choix sont possibles et se rencontrent : mémoriser les deux arêtes retirées d'une tournée et interdire de les remettre, ou mémoriser la solution entière. Le second est le plus simple à écrire, et le moins bon.

À l'inverse, un attribut trop grossier interdit trop. Rendre tabou « l'ordre O3 » tout entier, c'est interdire les neuf échanges qui le concernent, et le voisinage, déjà petit, se vide. Le bon attribut est le plus fin qui empêche encore de défaire ce qu'on vient de faire.

Combien de temps : la durée tabou

Un interdit qui dure toujours ferait mourir la recherche : à force d'interdire, il ne resterait plus aucun mouvement. Chaque interdit est donc temporaire.

La durée est le réglage de la méthode, et il se lit dans les deux sens.

• Trop courte : la recherche ne s'éloigne pas assez. Elle sort du creux, fait un ou deux pas, puis l'interdit expire et elle y retombe : elle tourne en rond sur un petit nombre de solutions.
• Trop longue : la recherche s'interdit trop. À chaque pas, une grande partie des mouvements est tabou ; le meilleur mouvement autorisé est de plus en plus mauvais, et le coût courant s'envole loin de tout ce qui est intéressant. Si la durée atteint la taille du voisinage, tout finit par devenir tabou (sauf ce que l'aspiration libère) et la recherche est bloquée.

Aucune durée n'est bonne partout. Elle se règle par rapport à la taille du voisinage (45 échanges ne demandent pas la même mémoire que 1 769 mouvements 2-opt), et se mesure : plusieurs durées, plusieurs départs, et on garde celle qui rapporte.

Le critère d'aspiration

Une liste tabou est un interdit aveugle : elle interdit un mouvement pour ce qu'il est, pas pour ce qu'il donne. Or il arrive qu'un mouvement tabou mène à une solution meilleure que toutes celles vues jusqu'ici. L'interdire serait absurde : il n'y a aucun risque de tourner en rond en découvrant une solution qu'on n'a jamais vue.

Cette précision compte. Comparer au coût courant autoriserait tout mouvement qui améliore la solution du moment, ce qui inclurait le retour vers la solution qu'on vient de quitter : la mémoire ne servirait plus à rien.

À manipuler : la recherche tabou pas à pas

La figure suivante fait mener la recherche sur les dix ordres de fabrication. À chaque pas, elle montre tous les échanges classés par coût : les mouvements tabous sont barrés, le prochain mouvement est marqué, et l'aspiration est signalée quand elle joue. La liste tabou se remplit d'une paire par pas et se vide au rythme de sa durée. La courbe trace le coût courant (trait plein) et le meilleur coût vu (tirets).

Le squelette, deuxième forme

Le squelette chercher du chapitre sur la recherche locale tire un voisin, décide de l'accepter, et recommence. Il convient à la descente aux tirages et au recuit simulé. Le tabou examine tout le voisinage : il ne tire rien, il compare. Le squelette a donc une seconde forme, qui prend non plus une fonction voisin mais une fonction voisinage.

Ce qui change tient en peu de lignes. Le voisinage devient un générateur qui fournit, pour chaque voisin, l'attribut du mouvement qui y mène ; la boucle regarde tous les voisins, écarte les mouvements tabous (sauf aspiration), et garde le meilleur ; puis elle inscrit l'attribut du mouvement pris dans la mémoire. La descente au meilleur voisin est la même forme sans mémoire : elle s'arrête quand le meilleur voisin n'améliore plus. Le code suivant met les deux formes côte à côte, et les fait tourner sur la machine. Sa seconde partie, sous le commentaire « Suite : l'effet de la durée », sert à la section d'après.

Le premier résultat rappelle la recherche locale : la forme 1 en descente, avec mille tirages, s'arrête à 20, 17, 18, 17 ou 20 heures selon la graine, et il faut plusieurs graines pour en tirer un ordre correct. Le deuxième, la descente de la forme 2, est sans hasard et s'arrête à 18 heures en trois pas. Le troisième est le tabou, avec une mémoire de cinq pas, en cinquante pas : 17 heures. Le tableau qui suit le détaille. Les pas 3 à 10 restent à 18 heures : la recherche se promène sur le palier, sans que le coût bouge, en changeant de solution à chaque pas grâce à la liste tabou, qui l'empêche de repasser aussitôt sur la solution précédente. Au pas 11, un échange que la descente n'aurait jamais vu, parce qu'il exige d'être sur une autre solution de ce palier, fait descendre à 17.

Deux chiffres méritent d'être comparés. La descente de la forme 2 évalue 180 voisins pour aboutir à 18 heures. Le tabou en évalue 2 250 pour arriver à 17 : un pas de tabou coûte autant qu'un pas de descente, et il en faut davantage, ce que le budget doit prévoir.

Lire l'effet de la durée sur la machine

Le programme de la section précédente refait cette lecture dans sa seconde partie, sous le commentaire « Suite : l'effet de la durée » : la même recherche de cinquante pas, avec des durées tabou de 0 à 40, en relevant ce que chacune trouve, quand, et combien de solutions différentes elle visite. Il fait aussi jouer l'aspiration sur un départ tiré au hasard. Rien à recopier : la fonction chercher_voisinage, le coût et le voisinage sont ceux de la première partie.

Le tableau qu'imprime cette seconde partie se lit en trois blocs. De 0 à 4 pas de mémoire, la recherche ne dépasse jamais 18 heures : elle ne sort pas du palier, et le nombre de solutions distinctes sur cinquante pas est petit : 5 sans mémoire, 9 avec une mémoire d'un pas, 19 avec une mémoire de quatre. Elle tourne en rond, sur un petit nombre d'ordres, sans jamais sortir de la région. À partir de 5 pas de mémoire, elle trouve 17 heures au pas 11, et cela ne change plus avec des durées plus longues. La dernière colonne montre pourtant que toutes les durées ne se valent pas : le coût courant moyen, de 17,45 heures pour une mémoire de cinq pas, monte à 19,07 pour dix, 26,00 pour vingt-cinq et 40,95 pour quarante. Trop de mémoire empêche la recherche de rester dans la région intéressante : il lui faut prendre, pas après pas, des échanges de plus en plus mauvais parce que les bons sont tabous.

Le second essai montre l'aspiration. Depuis l'ordre tiré au hasard par la graine 17, à 88 heures de retard, avec une mémoire de sept pas, la recherche trouve 17 heures au pas 36 avec l'aspiration, et 18 heures sans. Au pas 36, le meilleur échange était tabou ; comme il donnait une solution meilleure que toutes celles déjà vues, l'aspiration l'a libéré. Sans elle, la recherche s'est privée de ce mouvement-là, et a fini sur le palier à 18 heures. L'aspiration est rare : depuis l'ordre d'écriture, avec des durées de 1 à 15 pas et cent pas, elle ne joue jamais, et sur 2 100 lancements au hasard (300 départs tirés avec les graines 0 à 299, sept durées de 3 à 10 pas, quarante pas chacun, mesurés à part) elle joue dans 77 seulement. Elle change alors le résultat 15 fois : 13 fois en mieux, 2 fois en moins bien.

Sortir d'un piège sur la tournée

Le chapitre sur la recherche locale a laissé une tournée à 647,35 mm de P-217 (T1, T7, T9, T11, T10, T8, T3, T12, T2, T6, T5, T4), obtenue par la descente 2-opt depuis l'ordre d'écriture : un optimum local des trois voisinages, à deux pour cent de l'optimum. Aucune descente n'en sort. La recherche tabou, avec le 2-opt pour voisinage et les deux trous aux extrémités du segment retourné pour attribut, le peut-elle ?

Sans mémoire, la recherche fait exactement ce que le raisonnement de la section précédente annonçait : à 649,96 mm au premier pas, elle revient à 647,35 mm au second, puis recommence. Deux solutions, à l'infini. Avec une mémoire d'un ou de deux pas, elle visite un peu plus de solutions (4, puis 6 en soixante pas) sans jamais trouver mieux que 647,35 mm : les interdits expirent avant qu'elle ait pu contourner le creux. Avec trois pas, elle trouve 633,23 mm au pas 20 ; avec quatre et plus, au pas 8. La tournée obtenue est l'optimum de P-217, celui des chapitres précédents. La recherche l'atteint ici en évaluant 65 voisins par pas, soit 520 voisins pour huit pas, alors que la force brute avait 479 001 600 ordres à essayer. Regarder les coûts du parcours avec une mémoire de cinq pas : 649,96, 657,03, 669,45, 669,45, 672,90, puis 642,90, 635,83 et 633,23. La recherche s'éloigne de plus de 25 mm de l'optimum local avant de retomber dans un creux plus profond : c'est ce qu'une descente ne fait jamais. Une durée qui sort du piège n'est pas pour autant celle qui explore le plus : avec cinq pas de mémoire, la recherche trouve l'optimum au pas 8, puis tourne en rond sur seize solutions seulement en soixante pas, contre 44 avec quatre pas de mémoire.

Le coût d'un pas est de 65 voisins évalués. Le code ci-dessus recalcule pour chacun la longueur entière de la tournée, treize distances ; le chapitre sur la recherche locale a montré qu'il suffit de quatre distances pour en déduire la variation. Sur soixante trous, le voisinage passe à 1 769 mouvements, et ce raccourci devient nécessaire : le code de la section suivante remplace alors le coût par sa variation.

Sur la grande plaque, honnêtement

Sur P-600, un pas de tabou évalue 1 769 mouvements 2-opt, soit vingt-sept fois plus que sur P-217. Rien n'est écrit d'avance : mieux vaut mesurer que deviner. La méthode de comparaison honnête est celle posée au chapitre sur le recuit simulé : au moins dix graines, la meilleure, la médiane et la pire des valeurs obtenues, un budget égal dans une unité dite, l'écart à l'optimum démontré (2 788,70 mm), et des réglages faits sur d'autres graines que celles qui jugent. Ici, le budget est le nombre de voisins évalués : 200 pas de tabou à 1 769 voisins, soit 353 800 évaluations. Les redémarrages du chapitre sur la recherche locale reçoivent le même budget : autant de descentes complètes, depuis des ordres tirés au hasard, que ce budget en permet, dans les deux variantes du chapitre sur le recuit (la descente au meilleur voisin, et celle qui prend le premier voisin qui raccourcit). Tous les lancements d'une même graine partent du même ordre au hasard.

Il y a deux jeux de graines, et ce n'est pas un détail. La durée tabou est le seul réglage du tabou : le programme l'essaie d'abord sur dix graines de réglage (100 à 109) et garde la meilleure. Puis il juge le tabou ainsi réglé, contre les redémarrages, sur vingt autres graines (0 à 19), jamais vues pendant le réglage. Il note aussi le temps de calcul de chaque méthode.

Ce site arrête un programme Python au bout de huit secondes, et le programme complet, une centaine de lancements, en demande une quarantaine. Le code ci-dessous est donc lancé sur une graine de chaque sorte, pour voir le mécanisme ; les deux lignes qui fixent les graines, REGLAGE et JUGEMENT, deviennent range(100, 110) et range(20) dans le programme complet, dont le tableau qui suit est le résultat, calculé à part, sur un Python installé.

Le programme complet donne, sur les vingt graines de jugement, les résultats suivants (les temps de calcul dépendent de l'ordinateur) :

Le réglage. Sur les dix graines de réglage, une mémoire de 5 pas est nettement moins bonne (médiane 2 881,90 mm, à 3,3 % de l'optimum) que 30 ou 90 pas (2 838,97 et 2 856,28 mm, à 1,8 % et 2,4 %). Le programme retient 30 pas, la médiane la plus basse des trois. Il n'y a pourtant rien à conclure de l'écart entre 30 et 90 pas : la durée de 30 pas, mesurée à part sur cinq lots de dix graines (0 à 9, 10 à 19, 20 à 29, 100 à 109 et 110 à 119), donne des médianes de 2 838 à 2 874 mm, et les 17 mm qui séparent 30 et 90 pas sont de cet ordre. Sur cette plaque, les bonnes durées forment une plage large, de 30 à 90 pas pour 1 769 voisins, et seule une durée trop courte perd, comme sur la machine.

Le jugement, à évaluations égales. Le tabou réglé a la médiane la plus basse (2 857,93 mm, à 2,5 % de l'optimum, contre 3,2 % et 2,9 % pour les redémarrages), sa meilleure valeur atteint l'optimum et sa pire (2 931,02 mm) est meilleure que celles des redémarrages. Mais l'avance sur la médiane est de 12 à 20 mm, et graine par graine le tabou fait mieux que les redémarrages sur 13 graines seulement sur 20, dans les deux variantes : un pile ou face donnerait 13 ou plus environ une fois sur huit. C'est une avance plausible, pas établie.

Le jugement, à temps de calcul égal. L'avance disparaît. Chaque voisin évalué passe aussi par la mémoire (sa clé, la consultation du dictionnaire) : à nombre égal de voisins évalués, le tabou demande de l'ordre d'une fois et demie plus de temps que la descente (dernière colonne du programme, de 1,3 à 1,9 fois selon les mesures et l'ordinateur, mesurées par le programme complet). Avec 125 pas au lieu de 200, il met à peu près le même temps que les redémarrages, et sa médiane (2 874,38 mm) se range entre les leurs. Le classement dépend de l'unité du budget, évaluations ou secondes, comme le montre aussi le chapitre sur le recuit.

Une leçon de méthode : ne pas régler et évaluer sur les mêmes tirages. Choisir la meilleure de trois durées sur cinq graines, puis annoncer le résultat sur ces mêmes cinq graines, c'est annoncer le meilleur de trois essais : le hasard de ces graines a désigné la durée, et il est compté comme un mérite de la méthode. Ici, la durée de 30 pas fait 1,8 % de l'optimum sur les graines qui l'ont choisie et 2,5 % sur les graines de jugement. Cet écart ne prouve pas à lui seul un excès d'optimisme, d'autres lots de graines auraient pu donner l'inverse, mais il montre la taille du hasard des graines, et pourquoi le chiffre du jugement est le seul à annoncer.

Ce que ces chiffres autorisent à dire : sur P-600, à 353 800 évaluations et avec une durée réglée à part, le tabou est un peu devant les redémarrages sur la médiane, sans que vingt graines l'établissent, et cette avance ne survit pas à un budget compté en secondes. Ce qu'ils n'autorisent pas : dire que 30 est la bonne durée, que le tabou bat les redémarrages en général, ou que le résultat vaut pour une autre plaque, un autre voisinage ou un autre budget. Les budgets et les graines ne sont pas non plus ceux du chapitre sur le recuit (300 000 évaluations, dix graines) : ces deux tableaux ne permettent pas de comparer le tabou et le recuit, il faudrait une comparaison faite pour eux deux, avec le même budget, les mêmes graines et le même soin de réglage. Pour trancher, il faudrait plus de graines, plusieurs plaques et plusieurs budgets.

Les erreurs d'un débutant

Exercices type

La méthode

1. Choisir la représentation et le voisinage, comme pour une descente, et compter les voisins.
2. Choisir l'attribut du mouvement : le plus fin qui reconnaît un retour en arrière (la paire d'éléments échangés, les extrémités d'un segment retourné). Le normaliser, pour que le retour ait la même clé que l'aller.
3. Écrire le voisinage comme un générateur de couples (attribut, voisin).
4. Fixer la durée tabou par rapport à la taille du voisinage, en pas, et tenir la mémoire à jour : un dictionnaire attribut -> dernier pas interdit.
5. Écrire le pas : examiner tout le voisinage, écarter les mouvements tabous sauf aspiration (comparée à la meilleure solution vue), prendre le meilleur, même moins bon, l'inscrire dans la mémoire.
6. Garder la meilleure solution vue et la rendre, pas la dernière.
7. Régler, puis juger : essayer plusieurs durées sur au moins dix graines de réglage, garder la meilleure, puis juger sur d'autres graines (au moins dix, vingt si le calcul le permet), à budget égal en voisins évalués, contre des redémarrages dans leurs deux variantes. Rendre la meilleure, la médiane, la pire, et regarder aussi le temps de calcul.
8. Juger par une borne ou un optimum connu, et annoncer l'écart.

Synthèse

• La descente s'arrête sur un optimum local. La recherche tabou en sort en prenant toujours le meilleur voisin, même moins bon, et en gardant la meilleure solution vue.
• Sans mémoire, cette règle cycle : elle revient à la solution qu'elle vient de quitter, puis y retourne. Sur P-217, deux solutions à 649,96 et 647,35 mm, à l'infini.
• La liste tabou mémorise l'attribut du mouvement pris, pas la solution entière : la paire d'éléments échangés, les deux trous aux extrémités d'un segment. Il faut le normaliser pour que le retour en ait la même clé que l'aller.
• La durée tabou est le nombre de pas d'un interdit. Trop courte, la recherche tourne en rond (sur la machine, 18 heures sans sortie jusqu'à 4 pas de mémoire, 17 heures à partir de 5). Trop longue, elle s'interdit trop (le coût courant moyen passe de 17,45 à 40,95 heures) et peut se bloquer.
• Le critère d'aspiration lève un interdit si le mouvement donne une solution strictement meilleure que la meilleure vue.
• Le squelette a deux formes. La forme 1, chercher(initiale, voisin, cout, accepter, iterations), tire un voisin (descente aux tirages, recuit). La forme 2, chercher_voisinage(initiale, voisinage, cout, iterations, duree_tabou), examine tout un voisinage de couples (attribut, voisin) (descente au meilleur voisin, tabou).
• Sur P-217, un tabou 2-opt sort du piège à 647,35 mm et trouve 633,23 mm, l'optimum. Sur P-600, à 353 800 voisins évalués, un tabou réglé sur d'autres graines (30 pas) a une médiane de 2 857,93 mm sur vingt graines, contre 2 877,67 et 2 869,86 mm pour les deux variantes de redémarrages : une avance modeste, que vingt graines n'établissent pas, et qui disparaît à temps de calcul égal.
• Comparer des méthodes, c'est au moins dix graines, la meilleure, la médiane et la pire, un budget égal dans une unité dite (évaluations ou secondes, la conclusion peut changer), et des réglages faits sur d'autres graines que celles qui jugent.

Et ensuite

La recherche tabou explore avec une mémoire à court terme et sans hasard. Le recuit simulé explore avec un hasard maîtrisé et sans mémoire. Les chapitres suivants sortent du moule commun : au lieu d'une solution qu'on retouche, une population de solutions qui se croisent ou qui se laissent guider par des traces. Pour la représentation et le coût, le chapitre 1 ; pour les voisinages et la descente, la recherche locale ; pour juger une valeur sans connaître l'optimum, les bornes.