GRASP et colonies de fourmis

Reconstruire plutôt que retoucher

Le plus proche voisin du chapitre 6 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 7, 8 et 9 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, avec une règle moins catégorique, qui tire le trou suivant parmi les trous proches au lieu de prendre le plus proche. Chaque exécution donne alors une tournée différente et plausible : la règle n'est plus une réponse, c'est une loi de tirage sur les tournées. Reste à savoir 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 7, 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 8 et 9, le budget se compte en évaluations : un candidat examiné, ou un voisin évalué par une descente, compte pour une.

Les deux méthodes ont chacune un paramètre nommé alpha, qui n'a pas le même sens : dans GRASP, un nombre entre 0 et 1 qui règle la largeur d'une liste ; dans une colonie, un exposant qui règle le poids de la phéromone. Le texte écrit « alpha de la liste » quand une confusion est possible.

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

La liste restreinte

GRASP est l'acronyme anglais de Greedy Randomized Adaptive Search Procedure : une procédure de recherche gloutonne (elle construit un élément à la fois, en préférant ce qui paraît le mieux), randomisée (le hasard choisit parmi les bons candidats), adaptative (la liste des bons candidats est recalculée à chaque pas), suivie d'une recherche locale, et répétée.

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 6, 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 7, 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 7 à 9 : 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 7, écrite avec numpy : les variations des 1 769 voisins 2-opt d'un balayage de soixante trous sont calculées d'un coup, et le meilleur est retenu ; le résultat et le compte des évaluations sont ceux de la version à boucles. Le budget de GRASP compte tout ce qui est examiné, les 1 830 candidats d'une construction comme les voisins de la descente, et 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 7). À 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 : 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 7), 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 8). 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 répétition coûte 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, sur un plateau large, de 0,02 à 0,2 : le tableau ne dit pas que 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. Construire un ordre entièrement au hasard puis descendre, en répétant, c'est ce que font les redémarrages du chapitre 7 : GRASP à alpha 1 est les redémarrages, et le chapitre 12 les mesure au même budget, à 4,6 %. Tout l'intérêt de la méthode est dans la valeur intermédiaire de alpha, un compromis entre la diversité des constructions et leur qualité de départ, qui se règle en mesurant et dépend du problème : sur douze trous, le meilleur alpha est 0.

Certaines versions de GRASP fixent la liste par un nombre de candidats (les k plus proches) plutôt que par un seuil. Le seuil s'adapte à l'écart entre les candidats, le nombre non : sur des distances très inégales, comme celles d'une plaque de trous, le seuil suit mieux la géométrie.

Les colonies de fourmis

La fourmi et la trace

Les fourmis réelles cherchent leur nourriture au hasard et rentrent en laissant une trace chimique, la phéromone, que les suivantes tendent à suivre. Une piste courte est parcourue plus souvent dans le même temps : elle se renforce, pendant que les pistes délaissées s'évaporent, et la colonie finit par emprunter le chemin court sans que personne décide. 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 : on voit la mémoire collective 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 131 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 6). 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 : seules changent la construction et la place du dépôt. 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 laisse presque plus 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, plus bas.

À 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, que le chapitre 12 mesure au même budget, 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, la phéromone portant sur les couples (position, ordre de fabrication).

Combien de temps une piste délaissée reste-t-elle attirante ? La question décide de la vitesse à laquelle une colonie se fige, et la réponse la plus naturelle est fausse.

Les fourmis sur la grande plaque

Sur P-600, une fourmi examine 1 830 candidats : un budget de 300 000 évaluations couvre 163 fourmis, soit seize itérations complètes 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. Le rapport entre l'arête la plus chargée et la moins chargée ne dépasse donc jamais $2n$, 120 sur soixante trous : aucune arête ne devient négligeable, et 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 7 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. Le budget compte les candidats des fourmis et les voisins de la descente. Le début du code (la plaque, les distances, la descente) reprend celui du bloc de GRASP, puisque chaque bloc s'exécute seul.

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, de 42 à 62 mm. À un million d'évaluations (le même code avec BUDGET = 1_000_000, exécuté hors du navigateur, qui interrompt un bloc trop long), l'écart reste de cet ordre, 1,0 % contre 1,2 %. Le réglage 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, que des essais préalables sur des graines de réglage avaient préféré à 2 et à 3.

Comparer honnêtement, à budget égal

La méthode de comparaison est celle que pose le chapitre 12 : 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 met côte à côte, pour les mêmes dix graines (0 à 9) et les mêmes budgets, les méthodes de ce chapitre, le recuit et les redémarrages, que le chapitre 12 mesure. 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 : les redémarrages 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 dans le budget.

Ce que ces chiffres autorisent à dire.

• Les fourmis seules perdent, et nettement : l'Ant System est encore à 10,9 % à un million d'évaluations, Max-Min à 5,9 %.
• 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), moins que l'écart entre la meilleure et la pire graine d'une même ligne (de 42 à 84 mm) : ils sont à égalité.
• À un million, le recuit passe devant (0,3 % contre 0,9 % et 1,0 %). 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.
• 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, et sur les postes les redémarrages trouvent l'optimum quand les fourmis ne le trouvent pas.

Le cadre fait partie du résultat : une seule plaque, un seul voisinage, dix graines, un alpha réglé à 300 000 évaluations puis gardé à un million, et un budget en évaluations, alors qu'une évaluation de fourmi (un poids, un tirage) ne coûte pas ce que coûte un voisin 2-opt (quatre distances). Rien de cela ne dit que les fourmis sont inutiles : on les emploie pour le routage dans des réseaux, où la mémoire s'adapte pendant que la recherche continue. Mais sur les données 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 7 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 9 en a changé la forme, pas cette hypothèse. GRASP et les fourmis la rejettent.

chercher(initiale, voisin, cout, accepter, iterations)                    # chapitres 7 et 8 : une solution courante
chercher_voisinage(initiale, voisinage, cout, iterations, duree_tabou)    # chapitre 9 : 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, et la descente qui suit remplace voisin et accepter. Dans une colonie, la mémoire est un objet à part, la matrice de phéromone, qu'on ne « retouche » pas : 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. Les algorithmes génétiques du chapitre 10 en donnaient une autre version, où la mémoire est une population.

Les erreurs d'un débutant

Mettre en pratique