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 5. 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 presque toujours un enfant plus long que le plus court de ses 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, voyons ce qu'il donne. 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 5). 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 tournées médiocres ont donné une meilleure tournée. 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 la section « La boucle complète » fait.

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 6 et 7 : la population de départ coûte taille évaluations, chaque génération taille - elite. Le bloc suivant contient toute la boucle, avec les pièces de la section précédente pour la plaque P-217, et deux premières mesures. La première fait évoluer cinquante individus sur cinq graines. La seconde compare l'absence de mutation, l'échange et l'inversion à plusieurs taux, sur cinq graines, trente individus et 3 000 évaluations : c'est la mesure annoncée à la section précédente. 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, et ce chapitre y reviendra.

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 4 : 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 4, 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 3. 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 mesure comme au chapitre 6, en évaluations, avec les budgets des deux chapitres précédents : 100 000 sur dix graines (0 à 9) pour le recuit et les redémarrages du chapitre 6, 353 800 sur cinq graines (0 à 4) pour les redémarrages et le tabou du chapitre 7. Le bloc suivant reprend toutes les pièces pour la plaque 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 mutation par inversion à 30 %), puis le même algorithme avec une recherche locale sur chaque individu, expliquée plus bas.

Une limite du navigateur. Un bloc Python y est interrompu au bout de huit secondes, et le génétique seul, qui évalue une tournée entière à chaque enfant, ne tient pas dans ce délai aux budgets des chapitres 6 et 7 : dix graines à 100 000 évaluations, ou cinq à 353 800, demandent de l'ordre de la minute en Python ordinaire, et davantage dans le navigateur. Le bloc ne lance donc le génétique seul qu'à 10 000 évaluations, sur trois graines. Les lignes du tableau qui donnent le génétique seul aux budgets du chapitre, et le mémétique à 100 000 évaluations, sont précalculées, avec ce même code lancé à part (budget=100_000 sur dix graines, budget=353_800 sur cinq), et le tableau les marque comme telles.

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 : le calcul fait à part à 100 000 évaluations donne une médiane à 17,1 % de l'optimum, et à 353 800 évaluations, le budget des chapitres 5 et 7, une médiane à 6,4 % sur cinq graines. Il reste derrière le recuit, les redémarrages et le tabou.

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 5 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 squelette chercher : un voisin 2-opt est tiré, gardé s'il raccourcit, jamais sinon. Ces tirages comptent dans le budget, une évaluation chacun : c'est le paramètre essais de evoluer, avec la fonction ameliorer : la boucle ne change presque pas. Avec une population de six individus, la recherche locale change ce que cherche la population : 2 000 tirages par individu sous un budget de 100 000, 5 000 sous un budget de 353 800. Ce réglage a été fait à part, sur d'autres graines (100 à 114), pour ne pas juger sur les graines de réglage : 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 compte autant que la méthode, et les valeurs retenues ici sont proches des meilleures de ce balayage.

La dernière ligne du bloc donne le résultat au budget du chapitre 7, sur ses cinq graines : le mémétique arrive à 0,5 % de médiane (1,1 % sur dix graines, calcul à part). À 100 000 évaluations, calcul à part lui aussi, il arrive à 3,7 % de médiane, contre 17,1 % pour le génétique seul : il remonte de plus de treize points, mais reste derrière le recuit (2,2 %), qui est ici la méthode la mieux adaptée à ce budget. 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 : de très loin à 100 000 évaluations (17,1 % de médiane, contre 2,2 % pour le recuit), et encore à 353 800 (6,4 %, contre 3,3 % pour les redémarrages et 1,9 % pour le tabou). Il n'est pas adapté à une tournée de soixante trous, et le dire est la première conclusion honnête de ce chapitre.
• Hybridé, il remonte : à 353 800 évaluations sa médiane (0,5 % sur cinq graines, 1,1 % sur dix) passe devant le tabou (1,9 %) et les redémarrages (3,3 %) du chapitre 7, et se place au niveau du recuit à 300 000 évaluations du chapitre 6 (1,5 %). À 100 000 évaluations, en revanche, il reste derrière le recuit. Aucune méthode ne gagne à tout budget.
• Ce que le tableau ne démontre pas. Cinq graines pour les lignes à 353 800 évaluations donnent une médiane fragile (le mémétique passe de 0,5 % à 1,1 % de médiane en passant de cinq à dix graines), et dix pour les lignes à 100 000. Un seul voisinage (le 2-opt), une seule plaque, un réglage choisi à part sur d'autres graines pour le mémétique, et des réglages plus sommaires pour les autres méthodes : rien n'autorise à dire que le mémétique bat le tabou, seulement qu'il l'égale ou le dépasse dans ces conditions.
• Une évaluation n'est pas une évaluation. Le budget compte pareil une évaluation d'une tournée entière du génétique (soixante et une distances) et une évaluation d'un voisin 2-opt (quatre distances). À évaluations égales, le génétique seul dépense en fait beaucoup plus de calcul que les autres méthodes, et perd quand même : le temps de calcul, que les blocs ne mesurent pas ici mais que le délai du navigateur suffit à rendre sensible (le génétique seul ne tient pas dans huit secondes, le mémétique oui), le montre. Mesurer aussi un budget en temps donnerait une comparaison plus proche de celle d'un atelier.

Les erreurs d'un débutant

Exercices type

La méthode

1. Choisir le chromosome, et lister ce qu'il peut contenir d'impossible : c'est la représentation du premier chapitre.
2. Choisir un croisement et une mutation écrits pour ce chromosome, et vérifier qu'ils rendent un objet valide (valider_ordre sur des centaines d'enfants).
3. Écrire la sélection (un tournoi de deux ou trois candidats pour commencer) et l'élitisme (quelques individus).
4. Régler le budget en évaluations, compter les générations qu'il permet, et en déduire la taille de la population.
5. Mesurer la diversité génération après génération, et se méfier d'une population qui devient uniforme avant d'avoir trouvé de bonnes tournées.
6. Garder et rendre la meilleure solution vue, pas la dernière génération.
7. Hybrider avec la recherche locale quand le voisinage est bon marché : quelques milliers de tirages par enfant, et une population petite.
8. Comparer honnêtement : plusieurs graines, meilleure, médiane et pire, à budget égal, avec l'écart à l'optimum ou à la borne, et des réglages faits sur d'autres graines.

Synthèse

• Un algorithme génétique garde une population de solutions et la fait évoluer par sélection, croisement, mutation et remplacement : il sort du moule du squelette chercher, qui n'a ni population ni croisement.
• Le chromosome est la représentation. Le croisement à un point casse une permutation : sur P-217, 2,1 % des enfants de parents au hasard sont des tournées. L'order crossover recopie un segment du premier parent et complète dans l'ordre du second : toujours une permutation.
• Croiser deux tournées prises au hasard donne presque toujours un enfant plus long : sur 78 coupes, deux enfants seulement sont plus courts que leurs deux parents. La sélection et la répétition font avancer.
• La mutation apporte ce que la population n'a pas : l'inversion, qui est un 2-opt tiré au hasard, vaut mieux que l'échange ; sans mutation, aucune graine n'atteint l'optimum de P-217.
• La sélection par tournoi règle la pression : un tournoi de trois donne trois fois plus de parents aux meilleurs qu'un tirage au hasard, un tournoi de dix presque toute la reproduction aux dix meilleurs. L'élitisme garde le meilleur, mais la meilleure solution vue est toujours gardée.
• Le budget se compte en évaluations : à budget fixé, une population trop grande n'a pas le temps d'évoluer (300 individus, 9 générations pour 3 000 évaluations).
• La diversité est la distance moyenne entre individus. Quand elle tombe à zéro trop tôt, c'est la convergence prématurée : sans mutation, elle atteint zéro en une vingtaine de générations sur une tournée médiocre.
• Une représentation indirecte (un ordre de pièces décodé par First Fit) rend toute solution réalisable : sur la découpe, l'algorithme trouve 5 barres, ce que le hasard trouve aussi, la recherche étant facile sur vingt pièces.
• Sur P-600, à 100 000 évaluations, le génétique seul est à 17,1 % de l'optimum démontré (médiane de dix graines, calcul fait à part), très loin du recuit (2,2 %). Hybridé avec la recherche locale (algorithme mémétique), il tombe à 3,7 %, et à 0,5 % à 353 800 évaluations (cinq graines, 1,1 % sur dix), devant le tabou du chapitre 7 (1,9 %). Aucune méthode ne gagne à tout budget, et le génétique seul n'est pas ce qui marche.

Et ensuite

Le recuit, le tabou et le génétique, qui ont chacun leur idée, se mesurent maintenant sur le même terrain : les chapitres suivants ajoutent les fourmis, qui construisent des solutions à partir de traces, puis comparent l'ensemble des méthodes, entre elles et avec un solveur. Pour la représentation, le chapitre 1 ; pour le squelette dont le génétique sort et la recherche locale qu'il emploie, le chapitre 5 ; pour la méthode de comparaison honnête, le chapitre 6.