GRASP et colonies de fourmis

Reconstruire plutôt que retoucher

Le plus proche voisin du chapitre 4 est une règle sans hésitation : depuis un trou, elle va au plus proche. Aux égalités près, que le nom du trou départage, elle rend la même tournée à chaque exécution. Les chapitres 5, 6 et 7 ont gardé cette tournée comme point de départ et l'ont retouchée : une solution courante, un voisin tiré ou examiné, une décision de s'y déplacer.

Il y a une autre manière d'employer le hasard : ne plus retoucher, et recommencer à construire. Il suffit de rendre la règle moins catégorique. Au lieu du trou le plus proche, un trou tiré parmi les trous proches. Chaque exécution donne alors une tournée différente, plausible, dont la longueur varie d'un tirage à l'autre : la règle n'est plus une réponse, c'est une loi de tirage sur les tournées. Reste la vraie question du chapitre : que faire de ces tirages successifs ?

Deux réponses.

• GRASP ne garde rien. Chaque tournée tirée est aussitôt améliorée par une recherche locale, comme au chapitre 5, puis le tirage suivant repart de zéro. Seule la meilleure tournée rencontrée survit.
• Les colonies de fourmis gardent une trace. Une tournée tirée dépose une quantité de « phéromone » sur les arêtes qu'elle emprunte, d'autant plus grande qu'elle est courte, et les tirages suivants penchent vers les arêtes chargées. La mémoire n'est pas une solution : c'est une matrice de nombres, partagée par toutes les fourmis.

Une construction est bon marché. Sur P-217 elle examine 78 candidats (douze trous possibles au premier pas, puis onze, et ainsi de suite jusqu'à un), sur la plaque de soixante trous 1 830. Comme aux chapitres 6 et 7, le budget se compte en évaluations : un candidat examiné, ou un voisin évalué par une descente, compte pour une. C'est ce qui permettra de comparer honnêtement.

GRASP : un glouton dont le choix est tiré au hasard

La liste restreinte

GRASP est l'acronyme anglais de Greedy Randomized Adaptive Search Procedure, « procédure de recherche gloutonne, randomisée et adaptative ». Chaque mot dit un morceau de la méthode. Gloutonne : elle construit un élément à la fois, en préférant ce qui paraît le mieux. Randomisée : ce « mieux » n'est pas appliqué à la lettre, le hasard choisit parmi les bons candidats. Adaptative : la liste des bons candidats est recalculée à chaque pas, d'après ce qui est déjà posé. Procédure de recherche : le tout est suivi d'une recherche locale, et répété.

Le paramètre alpha se lit comme un curseur. À 0, la liste ne garde que le plus proche : c'est la règle du chapitre 4, avec le même départage des égalités. À 1, elle garde tous les trous restants : c'est un ordre tiré au hasard. Entre les deux, plus alpha est grand, plus la liste est longue et plus le tirage est libre. Attention à l'échelle : la liste se mesure en fraction de l'écart $c_{\max} - c_{\min}$ des candidats qui restent, et cet écart vaut souvent plusieurs centaines de millimètres sur la grande plaque. Les valeurs de alpha qui comptent sont donc petites, quelques centièmes.

Une répétition de GRASP est une construction suivie de la descente 2-opt au meilleur voisin du chapitre 5, depuis la tournée construite, jusqu'à un optimum local. GRASP fait autant de répétitions que le budget en permet, et rend la meilleure tournée. Il n'y a ni solution courante ni voisin tiré : la construction fait l'exploration, la recherche locale fait la retouche.

Une répétition, pas à pas

La figure suivante rejoue une répétition sur la plaque P-217. Le lecteur règle alpha, pose les trous un par un en voyant à chaque pas la liste des candidats et celui que le hasard a tiré, puis regarde la recherche locale améliorer la tournée construite. Chaque répétition terminée s'ajoute à un histogramme et à un tableau qui garde les résultats de chaque valeur de alpha essayée. La meilleure tournée connue n'est donnée qu'à la demande.

GRASP sur soixante trous

Douze trous se suivent à la main. Pour éprouver la méthode, voici la plaque P-600 des chapitres 5 à 7 : soixante trous engendrés par une formule, sur 600 par 400 mm. La liste des candidats y devient longue, et le tableau n'en montre que les plus proches. La figure garde les résultats de chaque valeur de alpha essayée, pour les comparer ; aucune référence n'est donnée avant l'essai.

Le code, et l'effet de alpha mesuré

Le code suivant réunit les deux plaques. La descente est celle du chapitre 5, écrite avec numpy : à chaque pas, les variations de tous les voisins 2-opt sont calculées d'un coup, puis le meilleur est retenu. Le résultat est le même que celui de la version à boucles (2 944,01 mm depuis le plus proche voisin de P-600), et le compte des évaluations aussi : un voisin évalué par mouvement du balayage, 1 769 par balayage sur soixante trous. Le budget de GRASP compte tout ce qui est examiné : les candidats de la construction, 1 830 par tournée sur soixante trous, et les voisins de la descente. Une répétition qui ne tient plus dans le budget est abandonnée.

Les trois premiers pas, avec alpha à 0,2 et la graine 1, montrent la règle au travail. Depuis le départ, douze candidats : T1 est à 25 mm, T7 à 76 mm. Le seuil de la liste vaut $25 + 0{,}2 \times (208 - 25)$, soit 62 mm : seul T1 y entre, et il est tiré. Au deuxième pas, depuis T1, T7 (52 mm) et T9 (67 mm) sont dans la liste, pas T10 (81 mm), et le hasard prend T7. Au troisième, T10 et T9 sont à égalité à 30 mm, T11 à 42 mm : les trois sont dans la liste, et le hasard tire T9. Sans le hasard, la règle aurait pris T10 (le nom départage l'égalité) : c'est ce que fait alpha nul.

Sur douze trous, le glouton pur suffit. Le tableau de la plaque P-217 porte sur cent répétitions par valeur de alpha. À alpha nul, il n'y a qu'une tournée distincte, et la recherche locale la mène à l'optimum, 633,23 mm, cent fois sur cent : depuis le plus proche voisin, le 2-opt y arrive en trois pas (chapitre 5). À alpha 0,1, les cent répétitions donnent 58 constructions différentes, et seules 32 arrivent à l'optimum ; à alpha 1, 52 sur 100. Le hasard est ici un handicap : il retrouve moins souvent ce que le glouton trouvait toujours. GRASP ne sert à rien quand le glouton suivi de la recherche locale arrive déjà au bout.

Sur soixante trous, il ne suffit plus. Le glouton pur suivi du 2-opt s'arrête à 2 944,01 mm, à 5,6 % de l'optimum démontré, 2 788,70 mm (chapitre 5), et il s'y arrête toujours : à alpha nul, les onze répétitions que permet le budget refont la même tournée, et 300 000 évaluations donnent un seul résultat. Le réglage de alpha se fait sur les graines 100 à 107, à 300 000 évaluations, et le jugement sur d'autres graines, 0 à 9 (règle du chapitre 6). Voici le tableau de réglage.

Trois lectures. La construction se dégrade vite : de 3 589 mm à alpha nul à 14 809 mm à alpha 1, où elle n'est plus qu'un ordre au hasard. La recherche locale rattrape la qualité : la longueur moyenne après 2-opt reste entre 2 911 et 2 944 mm quelle que soit la valeur de alpha, l'écart entre deux lignes étant du même ordre que celui entre deux graines. Mais elle le paie : depuis un ordre au hasard, une descente demande 107 638 évaluations, quatre fois plus que depuis une construction proche du plus proche voisin (26 596), et à budget égal on ne fait que 2 répétitions au lieu de 11. Un alpha trop grand ne fait pas perdre en qualité par répétition, il fait perdre en nombre de répétitions. Un alpha nul n'en fait perdre aucune, mais elles sont toutes identiques : dès 0,02, la médiane (2 849,0) passe 95 mm sous celle du glouton pur.

Le meilleur des cinq réglages est 0,05, dont la médiane est la plus basse. Le plateau est large, de 0,02 à 0,2, et la médiane de 0,2 (2 873,6) n'est pas très loin de celle de 0,05 : ne pas lire ce tableau comme « 0,05 est le bon alpha ». Jugé sur les graines 0 à 9, alpha 0,05 donne une meilleure tournée à 2 797,4 mm, une médiane à 2 827,1 mm (1,4 % de l'optimum) et une pire à 2 881,8 mm ; alpha 1 donne 2 805,2, 2 901,4 (4,0 %) et 2 977,4 mm. Ce dernier résultat est celui des redémarrages du chapitre 5, qui étaient à 4,6 % dans la comparaison du chapitre 6 : construire un ordre entièrement au hasard puis descendre, en répétant, c'est exactement cela. GRASP à alpha 1 est les redémarrages ; le reste de l'intérêt de la méthode est dans la valeur intermédiaire de alpha.

Les colonies de fourmis

La fourmi et la trace

Les fourmis réelles cherchent leur nourriture au hasard, et rentrent en laissant derrière elles une trace chimique, la phéromone. Les suivantes penchent pour les pistes marquées. Une piste courte est parcourue plus souvent dans le même temps : elle se renforce. La phéromone s'évapore, et les pistes qu'on cesse d'emprunter s'effacent. Personne ne décide de rien, et la colonie finit par emprunter le chemin court. L'optimisation retient de cette histoire trois ingrédients : des constructions tirées au hasard, une trace laissée en proportion de la qualité, une trace qui s'efface.

Quatre réglages, dont chacun a un rôle et un extrême qui casse quelque chose.

Au départ, la phéromone vaut $m / L_0$ sur toute arête, où $L_0$ est la longueur de la tournée du plus proche voisin : $m$ fourmis aussi bonnes que la règle gloutonne, toutes d'accord sur une arête, y déposeraient exactement cette quantité. Le nombre exact compte moins que ce rapport, celui d'un dépôt à ce qui est déjà sur l'arête : il décide de la vitesse à laquelle la colonie apprend.

Le choix d'une fourmi, en chiffres

Un exemple à la main, sur la plaque de Valdrome. Une fourmi est au trou T7 en (70 ; 30), et il lui reste trois trous à choisir : T10 en (100 ; 30), à 30 mm, T9 en (70 ; 60), à 30 mm, et T11 en (100 ; 60). La phéromone vaut 0,02 sur l'arête vers T10, 0,05 vers T9 et 0,01 vers T11.

Trois probabilités pour un même choix. Avec les deux ingrédients, T9 l'emporte deux fois sur trois, et T11, plus loin et moins chargé, a une chance sur quinze. Sans la visibilité, la phéromone seule donne 62,5 % à T9. Sans la phéromone, T9 et T10 sont à égalité et T11 vaut 20 %. C'est le produit des deux qui décide, et les exposants qui règlent lequel des deux pèse le plus.

Douze trous, itération après itération

La figure suivante fait mener une colonie sur la plaque P-217. Chaque arête est d'autant plus épaisse qu'elle porte de phéromone : c'est la mémoire collective qui se forme, et on la voit se former. Les tournées des fourmis de la dernière itération sont tracées en fins pointillés, et la meilleure tournée vue en tirets épais. La courbe suit la longueur des tournées ; la seconde courbe suit la part de la phéromone qui repose sur les arêtes de la meilleure tournée, quantité qui vaut 17 % quand elle est répartie également et 100 % si tout est sur elle.

Le code, et ce que les réglages changent

Le code suivant est l'Ant System sur les douze trous. La fonction roulette tire un rang avec une probabilité proportionnelle à son poids : un nombre entre 0 et le total, puis on cumule les poids jusqu'à le dépasser. La fonction colonie suit exactement les quatre étapes de la définition, et son journal garde, à chaque itération, la meilleure longueur, la moyenne de l'itération et la part de la phéromone sur la meilleure tournée.

Le premier constat porte sur la visibilité. Depuis le départ, avec une phéromone uniforme, la probabilité de T1, à 25 mm, vaut 8 % à bêta 0 (tous les trous sont équiprobables), 31 % à bêta 1 et 90 % à bêta 3 : la visibilité tire les fourmis vers le plus proche, et bêta règle la force de cette traction.

Le deuxième constat est la mémoire qui se forme. Sur les trente itérations de la graine 0, la meilleure tournée vaut 683,8 mm jusqu'à la cinquième itération, 635,8 mm à la dixième, et n'en bouge plus. La part de la phéromone sur ses arêtes est de 17 % au départ (13 arêtes sur 78), de 24 % après la première itération, de 47 % à la cinquième et de 66 % à la trentième. En revanche, sur les itérations affichées, la moyenne des fourmis reste entre 744 et 828 mm : les fourmis explorent encore, la colonie ne s'est pas réduite à une tournée. La mémoire est un biais, pas une décision.

Le troisième est le tableau des réglages, où chaque ligne change un seul réglage de la ligne de référence, sur huit graines.

Ce qu'on peut lire, et ce qu'on ne peut pas. La visibilité est le levier le plus fort : sans elle, la colonie perd 130 mm sur la médiane, elle tire des ordres presque au hasard. La mémoire compte : alpha 0 perd 18 mm, soit 2,9 % de l'optimum de P-217, 633,23 mm (chapitre 4). Une évaporation trop forte fait oublier : à 0,9, la colonie perd 15 mm. Deux fourmis ne suffisent pas : elles coûtent cinq fois moins et perdent 51 mm. En revanche, la différence entre 649,1 et 652,7 mm, entre une évaporation de 0,5 et de 0,05, n'est pas un résultat : une médiane de huit graines bouge de quelques millimètres d'un jeu de graines à l'autre. Et aucun réglage n'atteint l'optimum dans ce tableau : une colonie sans recherche locale reste à 2,5 % de lui en médiane, alors que GRASP à alpha nul l'atteignait cent fois sur cent. (Un essai plus long, 300 itérations sur vingt graines, ne l'atteint pas davantage : la meilleure colonie s'arrête à 635,83 mm.)

La même idée sur les postes des opérateurs

Rien n'oblige la fourmi à construire une tournée. Pour les huit opérateurs et les huit postes du chapitre 1, la représentation est poste_de[i], une permutation. Une fourmi affecte les opérateurs un par un, dans l'ordre 0 à 7, chacun à un poste encore libre ; la phéromone est sur les couples (opérateur, poste), une matrice de huit lignes et huit colonnes, non symétrique cette fois ; la visibilité est l'inverse du temps. Ce sont les mêmes quatre étapes, et seules changent la construction et la place du dépôt, comme seuls le voisin et le coût changeaient d'un problème à l'autre au chapitre 5. La roulette est ici celle de la bibliothèque : hasard.choices(libres, poids) tire un élément avec une probabilité proportionnelle à son poids, comme la fonction roulette du code précédent.

Les 600 fourmis de la graine 0 (soixante itérations de dix) rendent une affectation à 98 minutes, pour un optimum de 95. Le plus instructif est la matrice : pour six opérateurs sur huit, plus de 97 % de la phéromone de la ligne repose sur un seul poste. La colonie s'est figée : une ligne dont la phéromone est presque entièrement sur un poste ne laissera plus jamais une fourmi en choisir un autre, et l'exploration s'est éteinte sur une affectation qui n'est pas la meilleure. C'est le risque de toute mémoire qui ne s'efface pas assez vite, et c'est la raison d'être des bornes de la variante Max-Min.

À budget égal, le résultat est net. À 1 000 évaluations, les colonies réglées sur les graines 100 à 109 ne trouvent l'optimum sur aucune des vingt graines, avec une médiane à 105 minutes et une pire à 115. À 3 000, la médiane est de 101 minutes, la pire de 109, toujours 0 fois sur 20. Les redémarrages du chapitre 6, à budget égal, l'atteignent 15 fois sur 20 à 1 000 évaluations et 20 fois sur 20 à 3 000, avec une médiane de 95. Les fourmis perdent, et nettement. L'espace ne compte que 40 320 affectations, les descentes y sont bon marché, et une mémoire n'a pas le temps de se former en quelques dizaines de fourmis. L'ordonnancement de la machine se traiterait de la même façon, avec la phéromone sur les couples (position, ordre de fabrication) ; il n'est pas repris ici, l'affectation suffit à montrer que la représentation change et que les quatre étapes restent.

Les fourmis sur la grande plaque

Sur P-600, une fourmi examine 1 830 candidats : un budget de 300 000 évaluations ne permet que 163 fourmis, seize itérations de dix. C'est peu pour qu'une mémoire se forme. Le code suivant compare l'Ant System à ses deux variantes, sur dix graines, à budget égal. La variante Max-Min (MMAS en anglais) change deux choses : seule la meilleure fourmi de l'itération dépose, et la phéromone est bornée entre $h / (2n)$ et $h = 1 / (\rho L^*)$, où $L^*$ est la meilleure longueur vue. Une arête ne tombe donc jamais à zéro, et aucune ne domine sans partage : la colonie ne peut pas se figer comme celle des opérateurs. La phéromone y démarre à sa borne haute. La troisième ligne, Max-Min et 2-opt, améliore la meilleure tournée de l'itération par la descente 2-opt du chapitre 5 avant de la déposer. La dernière remet alpha à 0 dans cette version : la même colonie, sans mémoire, pour mesurer ce que la phéromone apporte. Les poids d'une itération sont calculés une fois, puisque la phéromone ne bouge pas pendant que les fourmis construisent, et le budget compte les candidats des fourmis et les voisins de la descente. Le début du code (la plaque, la matrice des distances, la descente) est celui du bloc de GRASP, repris tel quel : chaque bloc s'exécute seul, il faut donc le répéter.

Le tableau donne, à 300 000 évaluations, les écarts à l'optimum démontré de 2 788,70 mm.

Trois lectures. Max-Min fait mieux que l'Ant System (9,6 % contre 12,0 %), ce qui justifie la variante : quand la mémoire ne se nourrit que de la meilleure fourmi, elle se concentre sur ce qui marche. Mais c'est la recherche locale qui fait basculer : de 9,6 % à 1,2 %. La mémoire, elle, pèse peu : remettre alpha à 0 dans la version qui gagne coûte 10 mm de médiane (1,2 % contre 1,6 %), moins que l'écart entre la meilleure et la pire graine d'une même ligne, une quarantaine de millimètres. À un million d'évaluations (le même code avec BUDGET = 1_000_000, exécuté hors du navigateur, dont le moteur interrompt un bloc trop long), l'écart reste de cet ordre : 2 815,3 mm avec mémoire, 2 822,6 mm sans, soit 1,0 % et 1,2 %. Le réglage n'est pas plus poussé que celui du recuit : il se fait, pour chaque variante, sur les graines 100 à 104, parmi trois essais qui ne diffèrent que par le nombre de fourmis et l'évaporation. Bêta vaut 5 dans les trois, plus que les 3 de la colonie sur douze trous : des essais préalables, sur des graines de réglage, l'avaient préféré à 2 et à 3 pour l'Ant System. À un million d'évaluations, le réglage retient dix fourmis et une évaporation de 0,1 pour les variantes avec 2-opt.

Comparer honnêtement, à budget égal

La méthode de comparaison est celle du chapitre 6 : plusieurs graines, la meilleure, la médiane et la pire, un budget égal en évaluations, un écart à l'optimum démontré, et des réglages faits sur d'autres graines que celles qui jugent. Le tableau reprend, pour les mêmes dix graines (0 à 9) et les mêmes budgets, les lignes du chapitre 6 et celles de ce chapitre. Chaque cellule donne la meilleure, la médiane et la pire tournée, puis l'écart de la médiane à l'optimum de 2 788,70 mm. Une réserve de méthode : les redémarrages du chapitre 6 comptent une descente interrompue pour ce qu'elle a atteint, alors que GRASP et les colonies abandonnent la répétition qui ne tient plus, règle du chapitre 7.

Ce que ces chiffres autorisent à dire.

• Les fourmis seules perdent, et nettement. L'Ant System est à 12,0 % à 300 000 évaluations et encore à 10,9 % à un million : il gagne peu à recevoir plus de budget, la construction seule ne suffit pas à descendre. Max-Min descend à 5,9 % à un million, mais reste loin derrière.
• Ce qui gagne est une construction suivie d'une recherche locale. À 300 000 évaluations, le recuit, GRASP à alpha 0,05 et les fourmis avec 2-opt ont des médianes à une dizaine de millimètres l'une de l'autre (2 821,8, 2 827,1 et 2 831,9 mm), un écart plus petit que celui entre la meilleure et la pire graine d'une même ligne (de 42 à 84 mm). Ils sont à égalité, et le classement de ce tableau ne dit rien de plus.
• À un million, le recuit passe devant (0,3 % contre 0,9 % pour GRASP et 1,0 % pour les fourmis avec 2-opt). GRASP et les fourmis avec 2-opt recommencent chaque fois d'une tournée construite : plus de budget leur donne plus de répétitions, pas de meilleures répétitions. Le recuit, lui, raffine une même solution.
• Un alpha mal réglé coûte cher. GRASP à alpha nul reste à 5,6 % quel que soit le budget, et à alpha 1 il refait les redémarrages : 4,0 % à 300 000 évaluations.
• La mémoire des fourmis apporte peu ici. Avec 2-opt, la version sans phéromone est à 1,6 % contre 1,2 % à 300 000 évaluations, et à 1,2 % contre 1,0 % à un million.
• Sur douze trous et sur huit postes, le tableau est autre. Le glouton suivi du 2-opt trouve l'optimum de P-217 cent fois sur cent ; sur les postes, les redémarrages trouvent l'optimum quand les fourmis ne le trouvent pas. Aucune méthode ne gagne partout.

Ce que ce chapitre ne dit pas non plus : que les fourmis sont inutiles. Elles ont été conçues pour des problèmes de tournées et de routage, on les emploie aussi pour le routage dans des réseaux, où la mémoire s'adapte pendant que la recherche continue, et la variante Max-Min avec recherche locale est un concurrent sérieux du recuit. Mais sur la plaque et les postes de Valdrome, à ces budgets, ce que la mémoire ajoute est faible devant ce que la recherche locale apporte.

Ce que ces méthodes changent au squelette

Le squelette du chapitre 5, chercher(initiale, voisin, cout, accepter, iterations), suppose une solution courante : on part d'une solution, on en tire un voisin, on décide de s'y déplacer. Le tabou du chapitre 7 en a changé la forme, sans changer cette hypothèse. GRASP et les fourmis la rejettent, et les pièces changent.

chercher(initiale, voisin, cout, accepter, iterations)                    # chapitres 5 et 6 : une solution courante
chercher_voisinage(initiale, voisinage, cout, iterations, duree_tabou)    # chapitre 7 : idem, et une mémoire de mouvements
grasp(construire, ameliorer, cout, budget)                                # GRASP : pas de solution courante, pas de mémoire
colonie(construire_selon, deposer, evaporer, cout, budget)                # fourmis : une mémoire, qui n'est pas une solution

Dans GRASP, il n'y a plus de initiale : chaque répétition construit la sienne. Il n'y a plus de voisin tiré ni de accepter : la descente qui suit la construction est celle du chapitre 5. Dans une colonie, la mémoire est un objet à part, la matrice de phéromone. Elle n'est pas une solution, on ne peut pas la « retoucher » : elle est mise à jour par des solutions entières, celles des fourmis, puis lue par les constructions suivantes. C'est un changement de nature : la recherche n'est plus une marche d'une solution à une autre, c'est une boucle entre une loi de tirage et ses résultats. Le chapitre suivant en donne une autre version, où la mémoire est une population.

Les erreurs d'un débutant

Exercices type

La méthode

1. Écrire la règle gloutonne du problème : la construction élément par élément, avec son coût de candidat et son départage des égalités.
2. La randomiser par une liste restreinte (alpha, avec la valeur 0 qui redonne la règle) ou par des probabilités (phéromone et visibilité).
3. Ajouter la recherche locale du chapitre 5 après chaque construction, ou seulement sur la meilleure de chaque itération quand elle coûte cher.
4. Compter le budget en évaluations, construction comprise, et le donner avec le résultat.
5. Régler alpha (ou alpha, bêta, l'évaporation et le nombre de fourmis) sur d'autres graines que celles qui jugent, en cherchant le plateau plutôt que le meilleur point.
6. Surveiller la diversité : nombre de tournées distinctes pour GRASP, moyenne des fourmis et part de la phéromone pour une colonie.
7. Comparer à budget égal, sur plusieurs graines, avec la meilleure, la médiane et la pire, et l'écart à l'optimum ou à une borne.
8. Dire ce qui perd, y compris sa propre méthode.

Synthèse

• GRASP et les fourmis recommencent à construire au lieu de retoucher : la règle gloutonne devient une loi de tirage sur les tournées, et il n'y a plus de solution courante.
• GRASP tire chaque trou dans une liste restreinte (les candidats à moins de $c_{\min} + \alpha (c_{\max} - c_{\min})$ du plus proche), améliore la construction par une descente 2-opt, et répète. Alpha nul est le plus proche voisin, alpha 1 un ordre au hasard.
• Sur P-600, alpha nul refait toujours la même tournée (2 944,01 mm) ; alpha 1 refait les redémarrages, avec des descentes quatre fois plus coûteuses ; une petite valeur, 0,05, donne 2 827,1 mm en médiane à 300 000 évaluations. Sur P-217, le glouton pur suivi du 2-opt trouve l'optimum cent fois sur cent : le hasard y est un handicap.
• Une colonie de fourmis garde une matrice de phéromone. Chaque fourmi choisit son trou suivant avec une probabilité proportionnelle à $\tau^{\alpha}\,\eta^{\beta}$, la phéromone puissance alpha fois la visibilité (l'inverse de la distance) puissance bêta ; la phéromone s'évapore, puis chaque fourmi dépose $1/L$ : le dépôt suit la qualité.
• La visibilité est le levier le plus fort ; la mémoire aide (18 mm sur P-217) mais un excès la fige, comme sur les postes des opérateurs, où la phéromone se concentre sur un poste et arrête l'exploration.
• Sans recherche locale, les fourmis perdent : 12,0 % de l'optimum à 300 000 évaluations sur P-600, 9,6 % avec la variante Max-Min. Avec la descente 2-opt sur la meilleure de l'itération, 1,2 %.
• À 300 000 évaluations, le recuit, GRASP et les fourmis avec 2-opt sont à égalité (1,2 à 1,5 %), et à un million le recuit passe devant (0,3 % contre 0,9 et 1,0 %). La mémoire des fourmis pèse peu ; sur les postes, les redémarrages gagnent.
• Ces méthodes sortent du squelette : la mémoire d'une colonie est une matrice mise à jour par des solutions entières, pas une solution que l'on retouche.

Et ensuite

Ni GRASP ni les fourmis ne gardent de solution courante, mais elles restent des méthodes qui construisent : la mémoire des fourmis est une matrice, celle de GRASP est nulle. Les algorithmes génétiques font un pas de plus : ils manient une population de solutions complètes, qui se croisent et se mutent. Pour la méthode de comparaison honnête, le chapitre 6 ; pour la descente 2-opt qui suit chaque construction, la recherche locale ; pour la règle gloutonne qu'on randomise, les heuristiques constructives. Le dernier chapitre du parcours reprend toutes ces méthodes côte à côte.