Les algorithmes génétiques

Une population plutôt qu'une solution

Le squelette chercher(initiale, voisin, cout, accepter, iterations) du chapitre sur la recherche locale tient quatre choses : une solution courante, un voisin tiré à partir d'elle, une règle qui décide de s'y déplacer ou non, et le souvenir de la meilleure solution vue. Le recuit simulé a changé la règle, la recherche tabou a ajouté une mémoire et pris le voisinage entier. Toutes ces méthodes ont gardé la même charpente : elles partent d'une solution et la font bouger.

Un algorithme génétique n'en garde qu'une seule pièce, la meilleure solution vue. Il n'y a plus une solution courante, il y en a cent. Il n'y a plus de voisin : un enfant a deux parents, il n'est le voisin d'aucun des deux au sens du chapitre 7. Il n'y a plus de règle d'acceptation : chaque génération remplace la précédente. À la place, quatre gestes, répétés génération après génération.

Pourquoi croiser ? Une bonne tournée est faite de morceaux bien enchaînés : un groupe de trous voisins percés à la suite, un passage qui longe un bord sans zigzaguer. Deux tournées différentes ont chacune ses bons morceaux, que l'autre n'a pas. Le croisement essaie de les réunir dans un même enfant, la sélection fait que les tournées porteuses de bons morceaux se reproduisent plus souvent, et la mutation apporte de temps en temps quelque chose qu'aucun parent n'avait. Le croisement n'a rien de magique : le chapitre le montre, sur deux bonnes tournées différentes, il donne le plus souvent un enfant plus long que ses deux parents. C'est la répétition, avec une sélection qui garde les meilleurs, qui fait avancer.

Le chromosome : la représentation d'abord

Tout ce que fait un algorithme génétique se définit sur le chromosome, comme un voisinage se définit sur une représentation. Pour la tournée, c'est l'ordre des trous, une permutation : le choix du premier chapitre. Ici, ce choix devient plus exigeant. Il ne suffit plus qu'un objet soit valide : le mélange de deux objets valides doit l'être aussi. Une représentation qui survit à la retouche d'un voisin peut très bien ne pas survivre au croisement.

Le croisement le plus simple casse la tournée

Le croisement des chaînes de zéros et de uns est celui qu'on imagine d'abord, le croisement à un point : couper les deux parents au même endroit, prendre le début de l'un et la fin de l'autre. Sur dix zéros et uns, il donne toujours dix zéros et uns. Sur une permutation, il en va autrement. Le bloc suivant ouvre sur un exemple à huit gènes, A à H, puis prend deux tournées de la plaque P-217 (deux optimums locaux de descentes 2-opt, comme au chapitre 7). La fonction valider_ordre est l'équivalent Python du validerOrdre du moteur des figures : chaque gène exactement une fois, aucun de trop, aucun de moins.

Le petit exemple montre l'essentiel. Coupés après le troisième gène, les parents ABCDEFGH et CGEAFHBD donnent ABCAFHBD : A et B y sont deux fois, E et G ont disparu. Sur la plaque, le résultat est le même : le début du parent A jusqu'à la troisième position et la fin du parent B donnent une tournée où T11 est percé deux fois et T9 jamais. Ce n'est pas un malheur de cet exemple : sur les onze coupes possibles, trois seulement donnent une tournée, et ce sont celles où les deux parents commencent (ou finissent) par les mêmes trous. La raison est simple : une coupe après $c$ gènes donne une permutation seulement si les $c$ premiers gènes des deux parents forment le même ensemble, ce qui arrive avec la probabilité $1 / \binom{n}{c}$ pour des parents tirés au hasard. Avec des parents tirés au hasard, 2,1 % des enfants sont des tournées valides (le calcul exact donne 1,94 %), et 0,06 % sur soixante trous : à peu près aucun.

L'order crossover

L'order crossover, ou OX, est un croisement écrit pour les permutations. Il garde intact un morceau du premier parent et complète avec les autres gènes dans l'ordre où le second parent les rencontre.

Sur l'exemple à huit gènes, avec les coupes 3 et 6, le segment de A est DEF.

L'étape 2 se lit sur B, à partir de la position 6 : B, D, C, G, E, A, F, H. Le segment contient D, E et F, qu'on saute ; il reste B, C, G, A, H. À l'étape 3, B et C prennent les places 6 et 7, puis, en revenant au début, G, A et H prennent les places 0, 1 et 2.

L'enfant est GAHDEFBC : une permutation, quels que soient les parents et les coupes. En Python, la lecture de B à partir de la position $j$ tient en b[j:] + b[:j], et la dernière ligne de croisement_ox place les gènes restants : les n - j premiers occupent les places après le segment, les suivants les places du début.

Sur la plaque P-217, le bloc de la section précédente fait l'essai. Avec les coupes 3 et 8, l'enfant OX mesure 645,65 mm, plus court que ses deux parents (659,78 et 667,03 mm) : deux optimums locaux ont donné une tournée plus courte que chacun d'eux. Sur les 78 coupes possibles, aucun enfant n'est invalide, mais deux seulement sont plus courts que les deux parents. Enfin, croisement_ox(parent_a, parent_a, 3, 8) redonne parent_a : croiser deux copies ne produit rien de neuf, ce qui servira quand la population aura perdu sa diversité.

La figure suivante fait faire ces essais. Le lecteur choisit deux parents et deux coupes, et voit le croisement à un point et l'OX produire chacun un enfant, avec ses défauts et sa longueur.

La représentation décide de l'opérateur, et pas seulement pour la tournée. Le tableau reprend les problèmes de Valdrome.

La mutation

Le croisement ne fabrique que des combinaisons de ce que la population contient déjà. Si aucun individu n'a l'arête entre T5 et T11, aucun croisement ne la créera : un enfant ne reçoit que des arêtes de ses deux parents, à part celles qui se forment aux jointures. La mutation apporte ce qui manque : elle modifie un enfant au hasard, un peu.

L'inversion est le plus souvent préférable pour une tournée, pour la raison qui a fait le succès du 2-opt : elle change peu de trajets, donc peu la longueur. Une mutation trop brutale défait ce que le croisement a construit, comme un recuit trop chaud. Un taux nul prive la population de tout ce qu'elle n'a pas déjà. Le bon taux se mesure, ce que fait la section « La boucle complète ».

La sélection : qui a le droit de se reproduire

Si les parents étaient tirés au hasard, la population ne s'améliorerait guère : rien ne favoriserait les courtes tournées. La sélection donne plus d'enfants aux meilleurs. La plus simple à écrire et à comprendre est le tournoi.

Le tournoi ne compare que des coûts deux à deux : il ne dépend pas de leur échelle. La sélection « à la roulette », où l'on tire un individu avec une probabilité proportionnelle à sa qualité, en dépend : une constante ajoutée à tous les coûts en change les probabilités. La taille $k$ règle la pression de sélection, c'est-à-dire à quel point la reproduction est réservée aux meilleurs. Avec $k = 1$, il n'y a aucune pression : c'est un tirage au hasard. Avec $k$ grand, presque tous les parents viennent du haut du classement.

Dans une population de $N$ individus classés du meilleur au pire, l'individu de rang $r$ (le meilleur a le rang 0) gagne un tournoi de $k$ candidats avec la probabilité

car il gagne quand le plus petit rang tiré est $r$ : tous les candidats ont un rang au moins $r$, et l'un d'eux exactement. Le bloc suivant la calcule pour cent individus, la vérifie par tirage, et donne aussi la part des parents pris parmi les dix meilleurs.

Un tournoi de trois candidats désigne le meilleur individu pour 2,97 % des parents, soit trois fois plus qu'un tirage au hasard, et un individu parmi les dix meilleurs pour 27,1 % des parents, contre 10 % au hasard. Avec dix candidats, deux parents sur trois viennent des dix meilleurs. Le dernier de la population, lui, ne gagne pratiquement jamais dès que $k \ge 3$ : sa chance est $(1/N)^k$.

La boucle complète

Il reste à assembler les pièces. L'algorithme est générationnel : à chaque génération, toute la population est remplacée, sauf une petite élite de meilleurs individus qui passe telle quelle, c'est l'élitisme. Il garantit que la meilleure tournée de la génération ne peut pas être perdue par malchance.

Le budget se compte en évaluations, comme aux chapitres 8 et 9 : la population de départ coûte taille évaluations, chaque génération taille - elite. Le bloc suivant contient toute la boucle pour la plaque P-217, et deux premières mesures : cinquante individus sur cinq graines, puis l'absence de mutation, l'échange et l'inversion comparés sur trente individus et 3 000 évaluations, la mesure annoncée à la section « La mutation ». Les tableaux de ce chapitre se lisent avec cinq graines seulement, pour que chaque bloc tourne en quelques secondes : ils montrent des tendances, pas des écarts établis.

Avec 10 000 évaluations, soit environ deux cents générations de cinquante individus, quatre graines sur cinq trouvent 633,23 mm, l'optimum de P-217, et la cinquième s'arrête à 645,65 mm : l'algorithme fonctionne, sur une plaque de douze trous. Le tableau des mutations se lit de haut en bas.

• Sans mutation, aucune graine ne trouve l'optimum : la médiane est à 754,79 mm, loin des 633,23 mm de l'optimum, et la pire des cinq à 787,21.
• L'inversion est meilleure que l'échange à taux égal : à 30 %, trois graines sur cinq trouvent l'optimum contre aucune, et la médiane est de 633,23 mm contre 673,26.
• Un taux trop haut ne vaut pas mieux : à 100 %, l'inversion ne trouve plus l'optimum sur aucune graine, avec une médiane de 647,35 mm. Sur cinq graines, l'écart avec 30 % est plausible, il n'est pas établi.

Cette dernière question annonce la section suivante : à budget égal, plus la population est grande, moins elle a le temps d'évoluer.

Taille de la population, diversité et convergence prématurée

Il reste trois réglages à comprendre : la taille de la population, ce qu'il advient quand tous les individus se ressemblent, et comment le voir. Pour le voir, il faut une mesure.

Une tournée et son inverse sont à distance zéro : c'est la même tournée, comme l'a noté le premier chapitre (un ordre et son inverse mesurent la même chose). Le bloc suivant reprend les pièces de la boucle complète, mesure d'abord la taille de la population, puis suit la diversité génération après génération dans trois réglages.

La taille de la population se lit dans le premier tableau : cinq graines, 3 000 évaluations pour toutes. À budget fixé, plus la population est grande, moins elle a de générations, et plus les résultats se dégradent : avec 10 individus (373 générations), trois graines sur cinq trouvent l'optimum et la médiane est de 633,23 mm ; avec 100 (29 générations), une seule, à 645,65 mm de médiane ; avec 300, neuf générations seulement, aucune graine et 698,34 mm ; avec 1 000, deux générations, ce qui ne laisse presque rien à la sélection, et 751,10 mm. Sur douze trous, une petite population suffit. À budget fixé, une population trop grande n'a pas le temps d'évoluer.

La convergence prématurée se lit dans les trois réglages suivants. Sans mutation, la diversité tombe à zéro en une vingtaine de générations, avec un tournoi de 7 comme avec un tournoi de 3 : sur la graine 0, tous les individus sont devenus des copies d'une même tournée, à 756,6 mm dans le premier cas, 879,2 mm dans le second, loin des 633,23 mm de l'optimum. Croiser deux copies redonne la copie, et sans mutation plus rien ne peut apparaître : la population est morte, sur une tournée médiocre. Aucune des cinq graines n'atteint l'optimum, dans aucun des deux réglages (médianes de 776,97 et 806,54 mm). Avec une mutation de 30 %, la diversité baisse aussi (79 %, 17 % puis 10 % aux générations 1, 20 et 100) mais ne s'éteint pas : la mutation en réinjecte, elle remonte à 15 % à la génération 149, et trois graines sur cinq trouvent l'optimum.

La diversité est pour l'algorithme génétique ce que la température est pour le recuit : la réserve de hasard qui permet de s'échapper. Elle baisse toujours, c'est le principe de la sélection. Le réglage consiste à ce qu'elle baisse assez lentement pour que la population ait trouvé de bonnes tournées avant d'être devenue uniforme.

La découpe de barres : une représentation indirecte

Le deuxième problème de Valdrome, la découpe de vingt pièces dans des barres de 6 000 mm, semble se prêter mal à un croisement. Représenter la solution par « pour chaque pièce, sa barre » donne des enfants qui posent les pièces de 2 920, 2 820 et 2 600 mm dans la même barre. Le remède est une représentation indirecte : le chromosome n'est pas le rangement, c'est un ordre des pièces, et un décodeur en fait un rangement. Ici, le décodeur est la règle du chapitre 6 : First Fit, qui met chaque pièce, dans l'ordre donné, dans la première barre où elle tient encore.

Un ordre de pièces est une permutation, comme un ordre de perçage. Le même OX et les mêmes mutations s'appliquent, et toute permutation se décode en un rangement réalisable : aucune barre ne déborde, aucune pièce n'est oubliée. Le décodeur porte la contrainte, comme la troisième représentation du premier chapitre, celle qui lançait chaque commande « si elle tient encore ». Le coût est le nombre de barres du rangement décodé.

Deux vérifications s'imposent avant de chercher. La représentation n'oublie-t-elle aucune solution ? Il existe des ordres qui se décodent en un rangement optimal (lister les pièces barre après barre d'un rangement quelconque : First Fit n'utilise alors jamais plus de barres que lui) : l'algorithme peut donc atteindre les 5 barres de l'optimum. Et l'ordre choisi par le chapitre 6, la longueur décroissante, n'est qu'un ordre parmi 20! : il donne 6 barres. Le bloc suivant applique le même algorithme génétique, avec un coût qui compte les barres.

First Fit Decreasing, un seul ordre, fait 6 barres. Sur 10 000 ordres tirés au hasard, 97,1 % donnent aussi 6 barres, et 288 (2,9 %) en donnent 5, la borne et l'optimum du chapitre 4. L'algorithme génétique trouve 5 barres sur les cinq graines, avec 1 000 évaluations, et un ordre qui se décode en 5 barres laisse seulement 500 mm libres au total (110, 10, 60, 150 et 170) : c'est un rangement optimal.

Mais lire le dernier résultat honnêtement : le meilleur de 1 000 ordres tirés au hasard trouve aussi 5 barres sur les cinq graines. Un ordre sur 35 environ se décode en 5 barres, donc 1 000 tirages n'y manquent presque jamais. Sur cette instance de vingt pièces, la recherche est facile, et le génétique n'a rien apporté que le hasard n'aurait trouvé. Ce que la découpe apprend est ailleurs : la représentation indirecte rend le croisement inoffensif, et tout problème dont une solution se décode depuis un ordre (ordonnancement, découpe, tournées de véhicules) en profite. Une instance plus grande départagerait le hasard et l'algorithme, mais elle n'est pas celle de Valdrome.

Sur la grande plaque, honnêtement

Douze trous se résolvent sans effort : l'algorithme génétique y trouve l'optimum. La vraie question se pose sur la plaque P-600, soixante trous, dont l'optimum, 2 788,70 mm, est démontré. La figure suivante fait régler la population et lancer l'évolution. Elle part de tournées tirées au hasard, environ cinq fois plus longues que la meilleure, et montre la meilleure tournée, la courbe du meilleur coût et du coût moyen par génération, et la diversité. Aucune référence n'est donnée avant l'essai.

Le génétique seul, puis le mémétique

Le budget se compte en évaluations, comme au chapitre 8, à deux niveaux déjà mesurés : 100 000 évaluations sur les graines 0 à 9, celles du recuit et des redémarrages du chapitre 12 ; 353 800 sur les graines 0 à 4, les cinq premières graines de jugement du tabou et des redémarrages du chapitre 9. Le bloc suivant reprend toutes les pièces pour P-600 : le génétique seul, avec le réglage de départ de la figure (cent individus, un tournoi de trois, une élite de deux, une inversion à 30 %), puis le même algorithme avec une recherche locale sur chaque individu, expliquée plus bas. Un bloc du site s'arrête au bout de huit secondes, et le génétique seul, qui évalue une tournée entière par enfant, demande de l'ordre de la minute aux budgets des chapitres 12 et 9 : le bloc ne le lance qu'à 10 000 évaluations, sur trois graines. Les lignes du tableau marquées « précalculé » viennent du même code, lancé hors du navigateur.

Sur ses 10 000 évaluations, cent générations de cent individus, le génétique seul est à plus de deux fois l'optimum : 6 397,9 mm de médiane (129,4 % au-dessus de 2 788,70 mm), de 5 609,4 à 6 867,8 mm selon la graine. Les soixante trous sont trop nombreux pour que le croisement et la mutation, seuls, en tirent vite de bonnes tournées. Un budget plus grand aide beaucoup, sans suffire, comme le montre le tableau plus bas.

Le génétique seul est mauvais pour une raison que le chapitre a déjà donnée : le croisement OX conserve des morceaux de tournée, mais ne raccourcit rien de façon systématique (sur les 78 coupes de P-217, deux enfants seulement battent leurs parents). Les enfants sont des tournées où des trajets se coupent, et il faut des générations pour les démêler un à un. La recherche locale du chapitre 7 sait faire cela très bien, en quelques milliers de tirages. L'idée est de réunir les deux : le génétique fabrique des points de départ diversifiés, la recherche locale les affine. On parle d'algorithme mémétique.

Concrètement, chaque individu créé, initial ou enfant, reçoit essais tirages de la descente du chapitre 7 (un voisin 2-opt tiré, gardé s'il raccourcit), et chaque tirage compte pour une évaluation : c'est la fonction ameliorer, et la boucle ne change presque pas. La population tombe à six individus, avec 2 000 tirages par individu sous un budget de 100 000, et 5 000 sous 353 800. Ce réglage a été choisi à part, sur les graines 100 à 114 : en balayant 6, 10 et 20 individus et 500 à 5 000 tirages, les médianes vont de 2,9 % à 12,3 % à 100 000 évaluations, et de 1,2 % à 5,1 % à 353 800. Le réglage pèse autant que la méthode, et celui retenu est le meilleur du balayage, ou presque.

La dernière ligne du bloc donne au mémétique une médiane à 0,5 % de l'optimum sur les graines 0 à 4. Le tableau réunit les résultats.

Les pourcentages sont les écarts à l'optimum démontré, 2 788,70 mm. Ce qu'on en tire, avec son cadre.

• Le génétique seul perd sur cette plaque : 17,1 % de médiane à 100 000 évaluations, contre 2,2 % pour le recuit ; 6,4 % à 353 800, contre 3,3 % et 1,9 % pour les redémarrages et le tabou. Il n'est pas adapté à une tournée de soixante trous.
• Hybridé, il remonte : 3,7 % à 100 000 évaluations, encore derrière le recuit ; à 353 800, 0,5 % sur cinq graines et 1,1 % sur dix, devant le tabou et les redémarrages du chapitre 9, au niveau du recuit à 300 000 évaluations du chapitre 12 (1,5 %). Aucune méthode ne gagne à tout budget.
• Ce que le tableau ne démontre pas. Cinq graines donnent une médiane fragile (celle du mémétique passe de 0,5 % à 1,1 % de cinq à dix graines) ; un seul voisinage, une seule plaque, et un réglage plus soigné pour le mémétique que pour les autres méthodes : le mémétique égale ou dépasse le tabou dans ces conditions, rien de plus.
• Une évaluation n'est pas une évaluation. Celle du génétique mesure une tournée entière, soixante et une distances ; celle d'un voisin 2-opt, quatre. À évaluations égales, le génétique seul dépense beaucoup plus de calcul, et perd quand même : il ne tient pas dans les huit secondes d'un bloc, le mémétique si.

Les erreurs d'un débutant

Mettre en pratique