Chapitre 6. Les solutions par l’évolution
p. 153-185
Texte intégral
LA GÉNÉTIQUE
1Quand les organismes vivants se reproduisent, leur progéniture hérite des traits caractéristiques de leurs géniteurs. Les humains ont des bébés, les mouches pondent des oeufs qui, à maturité, deviennent d’autres mouches, et les graines des pommes poussent pour devenir des pommiers. Les traits spécifiques qu’ont en commun ces groupes d’organismes déterminent leur espèce. Ce dernier terme a une signification précise pour les biologistes, qui ont répertorié et décrit plus de trois millions d’espèces. Mais, familièrement, une espèce est un groupe d’individus (plantes, animaux, insectes, etc.) qui présentent une structure et un comportement très semblables et qui peuvent se reproduire entre eux.
2Longtemps, on a pensé que les espèces étaient immuables, que chaque espèce animale ou végétale avait toujours été dans le passé telle qu’on la voit aujourd’hui. Mais, il y a quelque 150 ans, dans De l’origine des espèces par voie de sélection naturelle, le naturaliste anglais Charles Darwin formula la théorie révolutionnaire que tous les organismes vivants proviennent de formes de vie apparues sur la terre dans un passé très lointain. (La théorie de Darwin, publiée en 1859, portait un sous-titre plus évocateur d’un essai socialement inacceptable que d’un travail en sciences naturelles : « La préservation des races favorisées dans la lutte pour la vie ».) Depuis Darwin, une espèce est désormais considérée comme une population soumise à des changements dynamiques et formée d’individus eux aussi changeants, dont certains peuvent éventuellement évoluer en d’autres espèces. Les mécanismes principaux par lesquels cette évolution se produit sont la sélection naturelle et la mutation, l’une et l’autre étant intimement reliées aux processus qui permettent aux parents de transmettre à leurs descendants certaines caractéristiques.
3L’étude scientifique de la façon dont les traits héréditaires sont transmis des parents à leur progéniture s’appelle la génétique. Le père de cette branche de la biologie est incontestablement le moine autrichien Gregor Mendel, qui en a découvert les lois fondamentales après avoir observé la reproduction des plants de petits pois. Dans un pur esprit scientifique, il prépara une série d’expériences ingénieuses pour vérifier ses hypothèses ; il fut aussi le premier à faire appel à des concepts mathématiques dans la recherche en biologie. Les idées de Mendel étaient indéniablement avant-gardistes. Son apport fondamental n’a pas été reconnu avant 1900, soit seize ans après sa mort et plus de trente ans après la publication de ses découvertes dans une revue scientifique. Mais si Mendel ne réussit pas à convaincre ses contemporains, il resta persuadé de la justesse de ses conjectures. « Mon temps viendra », aurait-il dit peu avant sa mort.
4Et son temps arriva. Nous savons aujourd’hui que les traits héréditaires tels que la couleur des yeux chez les animaux ou la forme des feuilles des plantes sont transmis à la génération suivante comme des « unités » discrètes ou gènes (c’était l’idée originale de Mendel). Les gènes sont disposés dans un ordre précis sur certaines parties du noyau d’une cellule appelées chromosomes, porteurs physiques de l’information héréditaire. Le nombre total de gènes dans la cellule varie de 5 ou 10 (un virus) à 100 000 (la cellule humaine). Chacune de ces unités héréditaires contient de l’information biologique codée sur elle—comment produire une certaine protéine, par exemple. La position d’un gène dans le chromosome est en règle générale liée à une fonction ou caractéristique particulière de l’organisme, par exemple la couleur des yeux. Une tension artérielle exceptionnellement haute chez certaines personnes a récemment été associée à certains gènes, gènes que les chercheurs essaient d’isoler.
5Les formes différentes d’un même gène constituent ses allèles. Par exemple, rouge et blanc sont les noms des deux allèles du gène qui déterminent la couleur des yeux des drosophiles ou mouches du vinaigre. Certains organismes animaux et végétaux plus complexes dépendent d’une structure génétique diploïde ou structure génétique à double hélice dans laquelle les chromosomes se présentent par paires. Chacun des deux chromosomes homologues situés dans la paire contient de l’information pour les mêmes fonctions. Dans la cellule humaine, il y a 23 paires de chromosome.
6Dans les applications des idées génétiques au calcul, il est pratique d’imaginer un « chromosome » abstrait comme une chaîne finie de n symboles représentant les « gènes ». Chaque gène peut apparaître sous plusieurs formes—ses allèles. Par exemple, si les allèles sont des bits (0 ou 1), alors un chromosome est un mot binaire tel que
71101100010110100
8Ici, n = 16 ; le premier gène est 1 et le 15e gène est 0.
LES POPULATIONS ET LA SÉLECTION NATURELLE
9Une population est un groupe d’individus de la même espèce, vivant et se multipliant dans un isolement relatif par rapport aux autres groupes— une colonie de lapins sauvages dans une certaine île, par exemple. À cause de la reproduction et de la mort, la composition du groupe change constamment. Chaque membre d’une population possède à la fois un génotype et un phénotype. Un génotype est l’ensemble particulier des gènes dont l’individu est porteur ; un phénotype désigne l’apparence physique réelle ou les caractéristiques visibles de celui-ci. La relation entre les deux est complexe, le phénotype d’un individu étant déterminé par son héritage (génotype) mais aussi partiellement par son milieu. Il peut sembler évident que les gènes n’existent que pour favoriser la reproduction des phénotypes. Mais certains biologistes ont soutenu que les desseins de la nature vont dans un tout autre sens : les oiseaux, les vaches et les humains sont des mécanismes que les gènes ont inventés pour se perpétuer eux-mêmes, autrement dit nous n’existerions que pour nos gènes, et non pas l’inverse.
10La population interagit avec son milieu et est modifiée par lui (les conditions climatiques, les ressources alimentaires, les prédateurs, les autres populations et ainsi de suite). Puisque les organismes varient dans leurs caractéristiques physiques (phénotype), certains individus (et leurs gènes) ont plus de chances de survivre que d’autres dans un milieu donné. Ainsi, le milieu sélectionne implicitement qui doit vivre et qui doit mourir. Pour augmenter ses chances de survie, la population a sa propre stratégie : l’adaptation. L’incapacité à s’adapter se paye à fort prix : par l’extinction.
11L’adaptation ne procède pas d’une manière arbitraire, en mettant à l’essai des phénotypes au hasard jusqu’à tomber fortuitement sur le meilleur. Il s’agit plutôt d’un processus graduel, par lequel les bons individus sont progressivement modifiés pour en produire de meilleurs. Darwin a défini la sélection naturelle comme étant la conservation des variations favorables et le rejet de celles qui sont nuisibles. Par conséquent, les organismes bien adaptés survivent et se reproduisent, et transmettent à leurs descendants leur précieuse information génétique, alors que ceux qui s’adaptent moins bien sont éliminés. D’où la survie du plus apte, idée clé dans les arguments évolutionnistes de Darwin. Sur plusieurs générations, les proportions relatives des différents phénotypes dans une population changeront à l’avantage de ceux qui sont les mieux adaptés. (Mais ici se cache une tautologie : l’adaptabilité d’un individu se définit par sa capacité à jouer le jeu de la survie ; or ceux qui survivent sont les plus aptes à... survivre ; donc...).
12Comme les véhicules physiques de l’hérédité sont les chromosomes, c’est à ce niveau que l’évolution opère en vue de modifier les caractéristiques des individus. Certaines combinaisons d’allèles pour différents gènes peuvent augmenter considérablement la performance du phénotype. On peut ainsi percevoir l’adaptation comme la recherche des « bonnes » associations d’allèles au moyen de changements dans la constitution génétique. De tels changements génétiques se produisent au moyen de processus dans lesquels le hasard joue un rôle fondamental. Ce fait constitue le principe directeur pour l’application des idées évolutionnistes à l’informatique.
13La totalité des chromosomes dont sont porteurs les membres d’une population constitue le pool chromosomique (ou génétique). Ceci correspond en règle générale à une fraction infiniment petite de tous les chromosomes imaginables. Dans le cas des chromosomes humains, il faudrait plus de deux milliards de chiffres pour écrire en notation décimale le nombre de variétés possibles. Il n’y a pas d’inconvénient à imaginer que l’adaptation puisse se faire par étapes discrètes, ou « générations ». Ainsi, si C(t) est le pool chromosomique à un moment donné t, alors C(t+1) constituera, une génération plus tard, la totalité des chromosomes dans la population. En général, C(t+1) contiendra de nouveaux chromosomes aussi bien que d’autres qui sont déjà dans C(f), tandis que certains chromosomes dans C(t) pourront être perdus. De nouveaux chromosomes peuvent être créés à partir des anciens et ce, de différentes manières : des éléments génétiques peuvent être perdus, réarrangés, échangés ou ajoutés.
14Pour les besoins de la modélisation de l’évolution, les deux processus les plus pertinents de la variation chromosomique sont le croisement (cross over) et la mutation. Au cours du croisement, des segments de deux chromosomes différents échangent leurs positions respectives, en séparant certains traits et en reliant d’autres dans de nouvelles—et peut-être bénéfiques— associations (voir figue 3.8). Un tel échange de matériel génétique arrive lorsque le sperme et l’ovule fusionnent Les mutations sont des changements dans la constitution génétique d’un chromosome qui se produisent spontanément durant la reproduction des cellules ou qui sont causés par la radiation, par des produits chimiques ou par d’autres agents externes. Les mutations ajoutent une touche de hasard aux variations dans le pool génétique : sans elles, l’évolution pourrait être limitée. Les équivalents abstraits du croisement et des mutations jouent un rôle fondamental dans l’efficacité des algorithmes « génétiques » que nous allons présenter maintenant.
MODÉLISER L’ÉVOLUTION
15L’adaptation des populations naturelles vise à améliorer les chances de survie du groupe. De leur côté, les modèles informatiques de l’évolution cherchent surtout à « engendrer » un individu exceptionnel dont le « code génétique » représente la solution optimale ou presque optimale d’un problème. Mais pour accroître la probabilité qu’un tel événement se produise, le modèle doit peu à peu améliorer la qualité moyenne de « générations » entières de solutions potentielles, exactement comme c’est le cas pour la biologie. Ci-après, nous donnons un exemple très simple de ce processus, reportant à plus tard une analyse détaillée du modèle.
16Notre problème consiste à trouver le nombre entier x entre o et 127 pour lequel une fonction mystérieuse f(x)—qui sera révélée plus tard— prend sa valeur maximale. Chacun des nombres 0, 1, 2,..., 126, 127 est une solution potentielle. Biologiquement parlant, ils sont les phénotypes possibles de l’espèce. (Pour ne pas compliquer l’exemple, nous avons restreint le nombre de solutions potentielles à quelques douzaines. Dans une situation réelle, où le nombre de possibilités serait astronomique, il est hors de question d’essayer de découvrir le maximum par le calcul systématique de toutes les valeurs f(x) de la fonction.) On peut considérer la fonction f comme mesurant l’« adaptabilité » d’une solution potentielle x, à savoir comment x a réussi dans le « milieu ». Plus grand est le score f(x), meilleure est la qualité du phénotype x. Notre but est alors de trouver un x dont l’adaptabilité est la plus grande possible.
17La représentation graphique de/apparaît dans la figure 3.9. Comme c’est le cas pour n’importe quelle fonction d’adaptabilité, le graphe comporte plusieurs sommets et plusieurs creux. Les plus hauts sommets correspondent aux meilleurs individus, c’est-à-dire aux solutions optimales. Les autres sommets sont des maximums locaux, à savoir les meilleures solutions pour les valeurs de x restreintes à un certain voisinage. Nous pouvons constater qu’il y a deux solutions optimales, x = 42 et x = 85. Bien entendu, dans n’importe quel problème non banal le graphe de la fonction d’adaptabilité ne peut pas être tracé, et encore moins examiné, si bien que nous ne possédons aucun indice concernant l’identité des plus aptes ou dans quelle région les chercher. Tout ce que nous pouvons faire, c’est tester les solutions individuelles par rapport à leur adaptabilité et utiliser au mieux cette information pour « engendrer » de meilleures solutions. Dans ce qui suit, nous allons mettre en évidence une méthode de résolution qui ne suppose aucune connaissance de/autre que la possibilité de calculer les valeurs f(x) une à la fois.
18La stratégie d’un algorithme génétique est basée sur les mécanismes de la sélection naturelle et de l’évolution. Sa mise en œuvre requiert normalement des ressources de calcul considérables pour stocker les données, automatiser les opérations et accélérer l’horloge évolutionniste. Après certaines étapes préliminaires (codage, sélection du pool de solution initial, etc.), le plan évolutionniste procède de manière cyclique, pour produire une nouvelle « génération » de solutions potentielles après chaque cycle. Une combinaison de hasard et de « reproduction » contrôlés favorisera à la longue l’apparition d’excellentes solutions, peut-être après des milliers de générations. Mais il n’est pas garanti que le modèle produira une solution optimale ou presque optimale. La raison de la réussite éventuelle du processus repose sur des arguments statistiques plutôt que sur une preuve mathématique exacte. Néanmoins, il y a de solides témoignages expérimentaux selon lesquels, dans de bonnes conditions, le modèle fonctionne pour certains types de problèmes. Voici les principales phases de l’algorithme.
191. le codage. Nous précisons d’abord un « code génétique » pour chaque solution potentielle x. Ceci peut se faire en écrivant le nombre x dans la base 2. Par exemple, si x =13, alors son code sera la chaîne binaire 1101 ; si x =65, son code sera 1000001. (Le codage binaire est basé sur les puissances de 2. Ainsi, 13 est représenté par la chaîne binaire 1101 parce que 1x23 + lx22 + 0x21 +1x 20 = 8 + 4 + 0 + 1 = 13.)
202. la population initiale. Un petit ensemble de chaînes est choisi au hasard dans le pool de solution pour former la population initiale, ou génération 0 ; sur cet ensemble, l’adaptabilité f(x) de chaque x est évaluée. La composition d’une population initiale de six chaînes est donnée ci-dessous.
213. le clonage. Deux chaînes ou plus de la population actuelle sont choisies au hasard pour « s’accoupler ». Pour favoriser la reproduction des individus les plus performants, la probabilité qu’une chaîne soit choisie est proportionnelle à son adaptabilité. Dans l’exemple ci-dessus, l’adaptabilité de la chaîne S2 est deux fois celle de la chaîne S6. Donc S2 a deux fois plus de chances que S6 d’être sélectionnée. Des copies, ou clones, des chaînes sélectionnées sont fabriquées, celles-ci constituant toutes le pool de reproduction.
224. la reproduction. Les chaînes qui s’accouplent (disons et S2) échangent des segments de gènes consécutifs par croisement pour créer deux enfants ; par exemple, ils peuvent échanger leurs trois derniers gènes :
PARENTS | ENFANTS |
0 0 0 0 1 0 1 | 0 0 0 0 1 1 0 |
0 1 0 0 1 1 0 | 0 1 0 0 1 0 1 |
23La longueur et la position des segments permutables sont déterminées par le hasard chaque fois qu’un accouplement a lieu. Dans l’exemple cidessus, les chaînes ont échangé leurs gènes no 5 à 7.
245. la mise à jour de la population. La progéniture qui résulte de l’accouplement remplace soit des chaînes dont l’adaptabilité est faible soit des membres de la population choisis au hasard, selon le choix du schéma particulier de mise à jour. Si nous supposons que les chaînes à remplacer sont s, et S6, alors la composition de la génération suivante est montrée ci-dessous (une procédé de décodage s’applique à chaque chaîne avant le calcul de son adaptabilité) :
25Il est à remarquer que, dans cette nouvelle génération, une solution d’adaptabilité 5 est survenue (x =37), qui est la meilleure jusqu’à présent. Dès lors, l’adaptabilité moyenne de la population est désormais de 2,83 ( =17/6), mieux que la moyenne de 2,50 de la génération précédente. Toutefois, ces améliorations locales après une seule génération ne sont pas significatives et ne fournissent aucune indication comme quoi le modèle marcherait selon l’optique souhaitée. Ce n’est qu’après de multiples répétitions des étapes 3 à 5 que le procédé produira probablement une chaîne d’adaptabilité supérieure. Nous analyserons plus tard les hypothèses sous-jacentes et les explications possibles des résultats que l’on espère tirer du modèle.
LECONS ET QUESTIONS
26Nous allons maintenant révéler la vraie nature de la fonction d’adaptabilité telle que représentée dans la figure 3.9. Ce qui semble être une fonction arbitraire compte en fait le nombre de fois que les 0 et les 1 alternent dans le code génétique de x. Plus précisément, l’adaptabilité de x est le nombre d’apparitions des sous-chaînes « 01 » ou « 10 » dans la chaîne qui représente x. Par exemple, f(34) = 4 parce dans l’encodage de 34, à savoir 0100100, « 01 » et « 10 » apparaissent deux fois chacun. Donc, la qualité (l’adaptabilité) d’un phénotype x se reflète de façon directe dans son code génétique.
27Or cette situation est assez exceptionnelle en raison de la nature artificielle de notre problème. Dans une application réelle—quand les chaînes encodent des programmes informatiques, par exemple—il n’y a pas de moyen simple pour déterminer quelles combinaisons d’allèles correspondent aux solutions de qualité supérieure. Seuls le temps et le milieu sont en mesure de le dire. Si nous le savions dès le début, nous pourrions alors construire les chaînes optimales tout de suite et il ne serait pas nécessaire de simuler l’évolution. En d’autres termes, la sélection naturelle serait remplacée par le génie génétique. Dans l’exemple ci-dessus, si nous avions su que plus les o et les 1 s’entrelacent, meilleures sont les chaînes, nous aurions tout de suite trouvé les chaînes dont l’adaptabilité est optimale en faisant alterner à chaque position : 1010101 (ce qui correspond au phénotype x =85) et 0101010 (x =42).
28Même en présence d’un schème de codage favorable, il existe un facteur qui pourrait empêcher le plan de produire une solution optimale : le manque de diversité génétique suffisante. Le modèle ci-dessus crée de nouvelles combinaisons génétiques par croisement. Mais, s’il arrive que toutes les chaînes dans la population initiale ont le même allèle dans une certaine position, ce trait génétique persistera durant toutes les générations futures. Par exemple, si toutes les chaînes du pool initial se terminent par 0, alors aucune quantité de croisements ne parviendra jamais à produire une chaîne se terminant par 1, la solution optimale 1010101 ne pouvant être obtenue. Dans le cas où les deux dernières positions de chaque chaîne initiale sont 0, les deux solutions optimales seront hors de portée de l’évolution. Inspirés de la nature, les algorithmes évolutionnistes, d’une manière générale, comportent aussi un opérateur de mutation pour s’assurer contre la stagnation génétique.
29Notre exemple tout simple a illustré les aspects les plus marquants des algorithmes génétiques :
le codage. Les solutions potentielles sont représentées par leur « code génétique », sous forme, par exemple, de chaînes binaires.
le pool des solutions. Un petit nombre de chaînes forment une « populationlation » de solutions potentielles dont l’algorithme se sert pour chercher de meilleures solutions.
le test de performance. La qualité d’une solution est évaluée par un nombre qui représente son « adaptabilité ».
la variation. De nouvelles combinaisons génétiques sont créées, par exemple, par croisement (« reproduction sexuelle »).
la sélection. Ceux qui sont performants ont plus de chances de se reproduire que ceux qui ne le sont pas.
l'évolution. Les individus nouvellement créés remplacent certaines chaînes du pool des solutions (ou toutes) pour former la prochaine génération.
le non-déterminisme. Certaines opérations comportent des choix aléatoires ou des règles fondées sur la probabilité.
la mutation. Des changements locaux aléatoires (mais non fréquents) peuvent se produire dans le code génétique pour accroître la diversité.
30Variation, sélection, évolution. Une stratégie séduisante, surtout quand nous faisons face à un problème pour lequel n’est connue aucune méthode efficace de solution. Mais beaucoup de questions subsistent : quel est le codage approprié des solutions ? comment pouvons-nous mesurer l’adaptabilité ? combien de temps mettra une solution optimale ou presque optimale pour apparaître et à quoi la reconnaîtra-t-on ? le procédé donnera-t-il le résultat escompté ? Ce sont là, en effet, de très bonnes questions, tellement bonnes que la seule réponse honnête que nous puissions donner est que, en général, nous ne savons pas. Ce qui ne signifie pas qu’il n’y a pas de réponses partielles ou même des réponses complètes et très satisfaisantes dans certains cas, comme nous allons le démontrer dans les sections qui suivent.
LE CADRE MATHÉMATIQUE
La théorie devrait nous fournir des moyens de prévision et de contrôle qui ne soient pas suggérés directement par des compilations de données ou par du simple bricolage.
(John H. Holland)1.
31Le métissage et la sélection naturelle sont présents spontanément dans le monde vivant. Depuis longtemps, les êtres humains ont compris l’utilité de ces mécanismes et les ont reproduits en vue de créer de meilleures récoltes ou d’obtenir... des fleurs exotiques. L’évolution biologique a aussi inspiré un mathématicien américain, mais dans un but différent, à savoir celui de développer des organismes supérieurs. Son ambition, en imitant les plans de la nature, fut de « produire » des solutions efficaces à certains problèmes complexes, et plus particulièrement à ceux qui résistent généralement aux méthodes de solution traditionnelles.
32John Holland pourrait être décrit comme un esprit universel ou un scientifique multidisciplinaire. Titulaire de diplômes en physique, en mathématiques et en sciences de la communication, il est professeur de psychologie, de génie électrique et d’informatique à l’Université du Michigan. La publication en 1975 de son livre Adaptation in Natural and Artificial Systems2 marqua le lancement officiel de l’algorithme génétique, technique de simulation de l’évolution sur ordinateur, qu’il avait commencé à mettre au point durant les années 60. Le livre de Holland a constitué, depuis, un cadre mathématique pour l’étude théorique et la mise en œuvre de stratégies adaptatives. Ces processus jouent un rôle fondamental non seulement en biologie mais également dans des domaines aussi divers que la psychologie, l’économie, le calcul numérique et l’intelligence artificielle.
33Comme cela fut le cas pour les ensembles flous, il fallut un certain temps avant que le potentiel de ces nouvelles idées soit totalement apprécié. Pendant plusieurs années, la recherche sur les systèmes adaptatifs fut surtout le fait de Holland et de ses étudiants, jusqu’à ce que l’intérêt pour ce genre de techniques commence à se répandre au milieu des années 80. On estime que le nombre de chercheurs qui étudient aujourd’hui les algorithmes génétiques s’élève à quelques centaines. Il existe d’ailleurs un consortium interdisciplinaire, le Santa Fe Institute, qui se consacre à l’étude de ces systèmes, les appliquant aussi bien à l’économie qu’à l’écologie. Pour donner au lecteur un aperçu de la façon dont les algorithmes génétiques fonctionnent, nous allons recourir à des métaphores géométriques.
LA RECHERCHE DANS L’ESPACE
34L’emploi d’un algorithme génétique pour résoudre un problème donné requiert des opérations préliminaires, à commencer par l’encodage des solution potentielles dans un format qui ressemble à la façon dont l’information est contenue dans un chromosome—un choix populaire consiste à représenter chaque solution possible comme une chaîne binaire. Il est également nécessaire de pouvoir évaluer de façon raisonnable la « qualité » des solutions. Ceci se fait habituellement en assignant à chaque solution possible un nombre unique, son adaptabilité, ce qui a pour effet de ranger les solutions sur une échelle linéaire. Le choix d’un système de codage et d’une fonction d’adaptabilité convenables n’est pas aussi facile qu’il semble ; ils sont peut-être les parties les plus cruciales et les plus difficiles de tout le processus.
35Imaginons que la collection de toutes les solutions forme une surface plane, chaque solution (encodée comme une chaîne binaire) devenant un point sur ce plan. (Bien qu’elle soit une image commode, une telle représentation présuppose que l’ensemble des solutions potentielles possède une structure plutôt simple.) Cette surface plane s’appelle l’espace de recherche. En cherchant parmi ses points, nous espérons repérer les chaînes de grande adaptabilité qui encodent les meilleures solutions de notre problème (nous parlerons indifféremment de « points » ou de « chaînes »). Il est bon de rappeler que le nombre de solutions possibles est d’habitude tellement grand qu’une recherche systématique, chaîne par chaîne, est hors de question.
36Imaginons maintenant une seconde surface, irrégulière, qui ressemble à un paysage de pics et de vallées flottant au-dessus de l’espace de recherche. Posé directement au-dessus de chaque chaîne s, il y a un point de ce paysage. L’espace qui sépare l’un et l’autre est proportionnel à l’adaptabilité de s : plus le point est haut, meilleure est la qualité de la solution encodée par s. Notre but est de repérer les chaînes au-dessus desquelles la surface d’adaptabilité est la plus élevée possible. Ceci serait facile si nous pouvions « voir » réellement les sommets du paysage. Mais, naturellement, nous ne le pouvons pas, de sorte que la recherche doit être menée entièrement au ras du sol, c’est-à-dire par l’intermédiaire des propriétés des chaînes elles-mêmes.
37Puisque la « population » initiale des chaînes est choisie au hasard, ces chaînes seront réparties n’importe comment dans l’espace de recherche. L’algorithme génétique est conçu pour que les futures « générations » soient surtout composées de chaînes qui se trouvent dans les régions de l’espace de haute adaptabilité. La clé de l’efficacité de l’algorithme réside dans son parallélisme implicite, propriété qui lui permet d’explorer de vastes régions de l’espace de recherche tandis qu’il manipule relativement peu de chaînes.
LES SCHÉMAS
38Une des hypothèses fondamentales qui sous-tend un algorithme génétique est que le secret du succès d’une chaîne est caché dans son code génétique, bien que nous ne puissions jamais savoir où exactement. En exploitant les similitudes structurales parmi les chaînes à haute adaptabilité, l’algorithme rend plus probable l’apparition de chaînes à adaptabilité encore plus haute. Et, ainsi, des configurations d’allèles, connues sous le nom de schémas, jouent un rôle central dans la stratégie de la recherche. L’objet à long terme de l’algorithme est de favoriser la prolifération des « bons » schémas parmi la population des chaînes.
39Un schéma est une configuration particulière d’allèles dans certaines positions d’une chaîne. Par exemple, le schéma 00**1****1 indique que la chaîne doit commencer par deux 0 et avoir un 1 dans les cinquième et dixième positions ; l’astérisque (*) dans les emplacements qui restent se veut le symbole de « sans importance », ce qui signifie en d’autres mots que l’un ou l’autre allèle—0 ou 1—peut apparaître ici. Chaque schéma décrit une certaine région du plan de recherche, à savoir l’ensemble de ces chaînes conformes au schéma dans les positions spécifiées. Le schéma ci-dessus comprend 6 positions du genre « sans importance » ; donc, il décrit un ensemble de 64 ( =26) chaînes qui inclut 0000111111 et 0001110001 mais non 0100111111. (Le nombre 64 est obtenu par l’application d’un principe de dénombrement. Les lecteurs qui ne sont pas au courant de ces techniques ne manquent rien d’important, à moins qu’ils ne veuillent par eux-mêmes vérifier nos calculs !)
40Inversement, une chaîne donnée de longueur k est un exemple de 2k schémas différents. Par exemple, 1001101000 est décrite par 210 ( = 1024) schémas. Ils incluent 1*********,10 *******0, * 00 * 101 ***, et ainsi de suite. Comme l’a fait remarquer Holland, lorsqu’on calcule l’adaptabilité d’une chaîne, on obtient également de l’information sur les 2k schémas qui décrivent la chaîne. Ainsi, une chaîne de qualité supérieure fournit de l’information sur la position possible des régions de haute adaptabilité dans l’espace de recherche. Cette caractéristique de l’algorithme— le fait de tester de nombreux schémas en testant une seule chaîne—équivaut à effectuer de nombreux calculs en parallèle.
41Il y a une notion d’adaptabilité associée à chaque schéma, à savoir la valeur moyenne d’adaptabilité de toutes les chaînes qui, dans la population, correspondent au schéma. En sélectionnant les chaînes pour l’accouplement avec une probabilité proportionnelle à leur adaptabilité, l’algorithme favorise la reproduction des schémas de haute adaptabilité. Ainsi, en arrière-plan de la population de chaînes toujours variable, une recherche concomitante a lieu : la chasse aux schémas les plus performants. En utilisant des arguments probabilistes, Holland a évalué dans quelle mesure on peut s’attendre à ce que le nombre de chaînes correspondant à un schéma donné change d’une génération à l’autre. Dans son théorème des schémas, appelé aussi théorème fondamental des algorithmes génétiques, Holland démontre qu’un schéma proliférera d’autant plus vite qu’il contient—mise à part sa haute adaptabilité—un petit nombre d’allèles spécifiques et que ceux-ci sont près les uns des autres. Par exemple, **1*01**** contient trois allèles spécifiques qui se répartissent sur quatre positions. La petite répartition réduit la probabilité que le schéma soit perturbé durant le croisement.
42On appelle briques les courtes séquences de gènes avec des valeurs particulières. Les « bonnes » briques sont celles dont la présence est un indicateur statistique de la haute adaptabilité du chromosome. En favorisant la recombinaison des chaînes les plus adaptées, l’algorithme augmente la probabilité que les bonnes briques de différents chromosomes se retrouvent dans un même chromosome. En supposant que l’abondance de bonnes briques soit une bonne chose, alors des chaînes exceptionnelles devront apparaître si le temps nécessaire leur est accordé. Mais, comme le temps équivaut au temps machine, et que cette denrée a un prix, il y a une limite pratique au temps pendant lequel on pourra laisser tourner l’algorithme. À ce sujet, il est grand temps, si nous voulons mesurer la marge qui existe entre la théorie et la pratique, de passer à une véritable application.
LE DILEMME DU PRISONNIER
Au lieu de poser une question compliquée (comme doivent l’être toutes les questions importantes d’ordre psychologique) et de proposer une réponse très simple (souvent sous la forme de oui, non ou peut-être), on devrait essayer de poser une question très simple (comme : « Que fera quelqu’un devant un choix entre deux possibilités ? ») et tirer une avalanche de réponses riches et complexes.
(Réflexion du mathématicien Anatol Rapoport sur la méthode expérimentale en psychologie)3.
43Le dilemme du prisonnier est le surnom donné à un jeu tout simple entre deux personnes, jeu pour lequel il n’y a pas de solution satisfaisante, en ce sens que la stratégie rationnelle mène à un résultat qui est pire pour les deux joueurs que s’ils faisaient des choix « irrationnels ». Le nom a été inspiré par l’hypothétique situation critique de deux suspects d’un crime (effectivement commis par chacun) gardés dans deux cellules séparées. La police leur promet l’immunité si, en échange, chacun des deux fait une déposition contre l’autre. Tant qu’il en va de l’intérêt individuel pour chacun d’avouer, indépendamment de ce que fait l’autre, l’intérêt commun est de garder le silence.
44Les règles du jeu sont assez simples. Chaque joueur a deux cartes étiquetées C (pour coopération) et D (comme dans défection). Un tour consiste à faire jouer aux deux personnes (simultanément) l’une des deux cartes. Un résultat est associé à chaque tour, résultat qui peut être une récompense ou une amende, selon la décision de chacun des deux de jouer telle ou telle carte. Si les deux joueurs jouent la carte C, ils reçoivent chacun 8 points ; si, au lieu, ils jouent D, chacun des deux perd 3 points. Dans le cas où ils jouent deux cartes différentes, celui qui joue la carte D gagne 10 points, tandis que celui qui a joué la carte C reçoit une amende de 10 points. Il va sans dire que les joueurs n’ont, d’aucune façon, la permission de communiquer entre eux. Un nombre convenu de tours joués successivement (disons, cent) constitue une partie.
45Les différents résultats peuvent être interprétés à la lumière de la situation qui a inspiré le nom du jeu. Si le prisonnier A cède à la tentation et accepte le marché, alors que B refuse de confesser son crime, dans ce cas la tentation est payante et A est relâché (T = +10 points pour A), tandis que B—le « dindon de la farce »—reçoit une sentence sévère (P =-10 points pour B). Si les deux avouent, il s’en tirent avec une peine plus légère (P =-3 points chacun) pour avoir collaboré avec la police. Mais si aucun des deux prisonniers ne se dégonfle, la police ne possède aucun élément qui lui permette de les retenir : elle doit les libérer tous les deux. Les suspects sont alors récompensés pour avoir coopéré l’un avec l’autre (R =+ 8 points chacun).
46La connaissance des règles du résultat ne permet à aucun des deux joueurs de concevoir à priori une stratégie gagnante. La conséquence du choix d’une carte par joueur—entraînant une récompense ou une amende—dépend du choix imprévisible de l’autre. Néanmoins—et ceci constitue un aspect intéressant du jeu—, l’histoire des tours passés, connue des deux joueurs, peut leur servir à orienter leurs décisions futures. Dans le jargon technique de la théorie des jeux, un jeu à somme nulle est un jeu dans lequel un joueur ne peut gagner qu’aux dépens de l’autre ; autrement dit, le gain de l’un égale la perte de l’autre, de sorte que la somme (algébrique) des points attribués aux deux joueurs lors de n’importe quel tour est toujours égale à zéro. Le dilemme du prisonnier n’est pas, pour cette raison, un jeu à somme nulle, puisque les deux joueurs peuvent gagner (ou perdre) des points dans un tour donné.
47Le nombre de points pour la tentation (T), le marché de dupe (F) [dindon de la farce], la punition (P) et la récompense (P) peuvent être répartis de différentes façons et les stratégies de jeu peuvent varier en conséquence. Ceci a été confirmé par une série d’expériences menées à l’Université du Michigan, dans les années 60, avec des étudiants engagés comme joueurs. Une de ces expériences, par exemple, montra que lorsque la récompense attachée à la coopération était augmentée de R = 1 à R =9, les autres résultats restant les mêmes, la carte C (c’est-à-dire la coopération) sortait selon une fréquence moyenne qui passait de 46 à 73 %.
JOUER LE JEU
48Le dilemme du prisonnier a servi aux psychologues pour étudier le comportement humain dans des situations comportant l’alternative coopération/défection, et aux spécialistes des sciences politiques qui s’intéressent à la dynamique des conflits internationaux. Les tournois sur ordinateurs ont opposé différentes stratégies de jeu les unes aux autres. Le plan de jeu « coup pour coup » (tit for tat) est une des stratégies les plus efficaces, malgré sa simplicité désarmante. Elle commence par la coopération au premier tour et par la suite joue ce que l’adversaire a fait dans l’essai précédent, autrement dit elle récompense la coopération par la coopération et punit la défection par la défection. Cette stratégie du « coup pour coup » fut la gagnante au classement général dans un concours d’ordinateurs organisé en 1979 à l’Université du Michigan par Robert Axelrod, spécialiste des sciences politiques et expert de la résolution des conflits. Un total de 62 stratégies, dont certaines plutôt complexes, furent présentées par des experts de la théorie des jeux, par des mordus d’informatique et par des professeurs de différentes disciplines scientifiques. On avait également présenté la stratégie du « laisser faire le hasard », c’est-à-dire jouer C ou D à l’aveuglette avec une égale probabilité. Toutes furent battues par la recette toute simple du « coup pour coup » proposée par le mathématicien Anatol Rapoport.
49Les succès d’un plan de jeu aussi simple intrigua Axelrod, qui se demanda si on ne pouvait pas découvrir d’autres stratégies tout aussi puissantes à l’aide d’un algorithme génétique. Il commença par formuler les stratégies possibles sous la forme de règles de décision. Chacune de ces règles détermine la décision du joueur à partir des résultats des trois tours précédents. Les stratégies sont ensuite encodées comme des chaînes binaires (chromosomes).
50Chaque tour comporte quatre résultats possibles : CC, CD, DC et DD, puisque chaque personne peut jouer soit C soit D. Si nous représentons ces résultats par R, F, T et P, alors une séquence de trois tours devient une chaîne de trois lettres. Par exemple, DC, DC, CC deviennent TTR. Chacune de ces 64 ( =43) chaînes peut s’interpréter comme un nombre de 0 à 63 écrit dans la base 4, avec la correspondance suivante entre les lettres et les nombres : R =0, F =1, T = 2 et P =3. De cette manière, un rang entre 0 et 63 est assigné à chaque séquence de trois tours. Par exemple, la séquence des tours DC, DC, CC est d’abord écrite comme la chaîne TTR et devient ensuite 220 (dans la base 4), qui à son tour décode (dans la base 10) comme dans 2x42 + 2x41+ 0x1 = 32+8 + 0 = 40 ( = le rang de la séquence).
51Pour chaque séquence de trois tours, il y a une règle qui dicte au joueur son prochain mouvement. Par exemple, TTR → D signifie : si la séquence TTR a été jouée, alors veuillez jouer D. Une stratégie particulière consiste ensuite en un ensemble de 64 règles (les gènes) qui est codé comme un mot binaire (un chromosome). Chaque bit encode la réponse du joueur, 0 (= C) ou 1 (= D), et sa position dans le mot correspond au rang de la séquence de trois tours qui a été jouée auparavant. Un exemple va illustrer le principe de codage :
52Rang : 012... 40 ... 62 63
53Bit : 100 ... 1 ... 0 1
54Le mot binaire ci-dessus décode selon l’ensemble de règles suivant (stratégie) :
Le rang Les trois derniers essais La carte à jouer
0 | RRR | → | D |
1 | RRF | → | C |
2 | RRT | → | C |
… | … | … | |
… | … | … | |
40 | TTR | → | D |
… | … | … | |
62 | PPT | → | C |
63 | PPP | → | D |
55À vrai dire, chaque mot binaire contient également six autres bits pour représenter le comportement présumé des joueurs à l’ouverture de la partie (c’est-à-dire pendant les trois premiers tours). Par conséquent, 011000 indique que les résultats des trois premiers tours sont, dans l’ordre, CD, DC et CC. Chaque chromosome est pour cette raison un mot de 70 bits, dont les six premiers gènes (bits) représentent l’ouverture de la partie et le reste encode une stratégie particulière. Un calcul rapide montre que le nombre total de chromosomes (c’est-à-dire la taille de l’espace de recherche) Excède1021, ce qui correspond à peu près à dix mille fois l’âge estimé de l’univers en secondes.
56À ce sujet, il faut noter que, dans la situation présente, les chromosomes ne représentent pas des solutions à un problème, mais encodent plutôt des règles de comportement. Dans un sens, nous essayons, en effet, de résoudre un problème : celui de faire en sorte que la machine apprenne à jouer à ce jeu (et à gagner). Mais, contrairement à un problème typique d’optimisation, celui d’apprendre à des machines ne possède pas de solution optimale bien définie. La situation ressemble à l’adaptation d’organismes réels à un milieu hostile. Quoique certains individus s’adaptent mieux que d’autres (par exemple, ils peuvent courir plus vite), il n’existe pas de mesure absolue de l’adaptabilité ou une idée de ce qu’est « le meilleur » phénotype. De la même façon, l’adaptabilité des chromosomes d’Axelrod ne peut pas être évaluée par une formule mathématique précise. La qualité d’une stratégie particulière pour jouer à ce jeu ne peut être mise à l’épreuve qu’en... jouant à ce jeu.
L’ÉVOLUTION DES STRATÉGIES
57Axelrod constitua un « environnement » pour mettre à l’épreuve les stratégies, ou plutôt les chaînes qui les encodent. Huit adversaires furent choisis parmi les participants du tournoi d’ordinateurs ; ils étaient considérés comme représentatifs des 62 concurrents. Chacune de ces huit stratégies joua une partie de 151 tours contre la chaîne G à évaluer. L’adaptabilité de G fut ensuite calculée comme la moyenne pondérée des points marquées par G dans chacune des huit parties (le choix des poids reflétait la force relative des adversaires, telle qu’elle fut établie par leur rang dans le tournoi).
58Travaillant avec une population d’à peine 20 chaînes—rappelons qu’il y en a des quintillions—et après seulement 50 générations, l’algorithme génétique était capable d’apprendre des ensembles de règles, dont la performance moyenne était aussi efficace que celle du plan « coup pour coup », le tenant du titre. Dans 11 des 40 séries (50 générations constituent une série), certaines stratégies battirent même celle du « coup pour coup ». Axelrod lui-même s’émerveilla de ce résultat :
Dans ces onze séries, la population a élaboré des stratégies qui parviennent à exploiter un des huit représentants (adversaires) au prix d’une coopération un peu moindre avec deux autres. Mais le résultat global est un gain en efficacité.
59Il ajoutait :
Ceci est une réalisation remarquable parce que, pour être capable d’obtenir cette efficacité accrue, une règle [c’est-à-dire une stratégie] doit pouvoir faire trois choses. D’abord, elle doit pouvoir distinguer entre un adversaire et un autre en se basant seulement sur le comportement spontané ou induit de l’autre joueur. Deuxièmement, elle doit pouvoir ajuster son propre comportement en vue d’exploiter un adversaire perçu comme joueur exploitable. Troisièmement—et c’est ce qui est peut-être le plus difficile—, il faut qu’elle puisse réaliser cette distinction et cette exploitation sans trop se mettre en difficulté avec les autres adversaires. Aucune des stratégies soumises au départ du tournoi n’est parvenue à en faire autant4.
60Mais Axelrod fit aussi remarquer que l'algorithme génétique parvenait à trouver des stratégies hautement efficaces alors que celles-ci avaient évolué dans un environnement particulier (celui qui était constitué des huit stratégies sélectionnées parmi celles du tournoi), mais que ces stratégies pourraient ne pas être aussi « robustes » que celle du « coup pour coup » dans d’autres environnements. « En somme, concluait-il, l’algorithme génétique est très bon dans ce que la vraie évolution fait si bien elle-même : élaborer des adaptations hautement spécialisées pour des niches écologiques spécifiques. »
ENSEIGNER À APPRENDRE AUX MACHINES
61Le succès d’un algorithme génétique dans la recherche de stratégies gagnantes pour le dilemme du prisonnier n’est pas tout à fait surprenant. Ces algorithmes avaient déjà démontré leurs capacités dans des circonstances semblables en aidant à la programmation de certains systèmes classificateurs. Ces derniers sont des ensembles de règles, à peu près comparables aux systèmes experts, pour accomplir des tâches précises telles que la reconnaissance des formes. Les règles dans un système classificateur forment une population qui évolue sur la base de stimuli et de renforcement provenant de son environnent. L’objet de cette évolution est d’« apprendre » quelles sont les réponses les plus appropriées à un stimulus donné.
62L’une des principales raisons de la mise au point des premiers algorithmes génétiques était précisément de construire des machines capables d’apprendre à faire des choses non mécaniques telles que reconnaître des objets, prendre des décisions et contrôler des processus. Étant donné que personne ne savait comment programmer un ordinateur pour qu’il puisse accomplir ce type de tâche, l’idée de rendre la machine capable d’apprendre par elle-même était une alternative naturelle. C’est cette idée fondamentale qui fut à l’origine des réseaux de neurones dont nous avons traité dans le chapitre précédent.
63La conception de systèmes d’apprentissage était également sous-jacente à la première application pratique de la logique floue. Au début des années 70, au Queen Mary College de Londres, Abe Mamdani et son étudiant Seto Assilian tentèrent de simuler une machine industrielle simple (une machine à vapeur) avec un programme informatique, pendant qu’un autre programme essayait d’apprendre à la faire fonctionner par tâtonnement. Le programme de contrôle—ainsi le voulait la théorie—devait réussir de mieux en mieux en tirant parti de ses erreurs. Malheureusement (ou peut-être heureusement), le plan ne marcha pas comme prévu, même après que les chercheurs eurent remplacé la simulation par la machine réelle. C’est pourquoi ils abandonnèrent l’idée d’un système d’apprentissage et décidèrent d’essayer une autre approche : ils écrivirent quelques règles heuristiques pour le contrôle du système, puis se servirent de la notion d’ensemble flou de Zadeh pour l’encodage des règles dans un programme informatique. On fournissait ainsi à la machine, directement, par voie empirique, la connaissance pratique d’un opérateur humain. Cette technique se révéla étonnamment efficace et fraya la voie aux nombreuses applications futures du contrôle flou.
64Les algorithmes génétiques et les réseaux de neurones diffèrent par leur façon d’aborder la conception de machines qui peuvent apprendre à exécuter des tâches « intelligentes ». Tandis que les premiers favorisent la naissance des meilleures stratégies par le moyen de la compétition, de la sélection et de l’évolution, les réseaux de neurones, eux, apprennent par les exemples et par l’expérience, avec ou sans supervision humaine. Les systèmes flous, de leur côté, produisent des stratégies basées non pas sur l’expérience mais sur leur capacité à comprendre des instructions ; leur connaissance est donc communiquée plutôt qu’acquise.
LE QI ET L’ADAPTABILITÉ
65Qu’est-ce que l’intelligence ? Les réponses à cette question fascinante ne manquent pas, ce qui prouve que les philosophes, les psychologues et les scientifiques en général sont toujours à la recherche de la bonne réponse. Le généticien Daniel Cohen estime que le mot intelligence décrit la faculté de comprendre notre environnement : elle serait donc une notion relative parce que dépendant de notre éducation. Pour Alain Connes, mathématicien français et lauréat en 1982 de la médaille Fields (le prix Nobel des mathématiques), le concept d’intelligence défie toute définition générale. À cet effet, il croit que les tests de quotient intellectuel ne font qu’évaluer la capacité du sujet à deviner ce que les auteurs du test considèrent comme étant l’expression de l’intelligence.
66Quelle que soit sa nature exacte, l’intelligence pourrait concerner non seulement les choses que les cerveaux (humains ou non) peuvent faire, mais aussi de la façon dont ils s’y prennent pour les faire. Des calculateurs humains peuvent exécuter des opérations arithmétiques complexes en un temps incroyablement court ; ils semblent ne suivre aucune démarche : le résultat ne fait que surgir dans leur esprit après quelques secondes. Aussi impressionnante qu’elle puisse être, une telle habileté n’est pas normalement considérée comme une preuve d’« intelligence ». Deep Blue, l’ordinateur d’IBM, parvint à battre le meilleur joueur d’échec que l’humanité pouvait lui opposer, le champion russe Garry Kasparov. Mais la manière dont elle accomplit son exploit était tout sauf intelligente. Avant de faire un mouvement, le programme de Deep Blue soupèse des millions d’options, même si dans n’importe quelle situation de jeu, il n’y a qu’une douzaine de mouvements qui méritent vraiment d’être considérés. Parcourir systématiquement plusieurs millions de manœuvres uniquement pour les éliminer ne correspond pas à l’idée que nous nous faisons de l’intelligence. Sans oublier le fait qu’on doit dire à l’ordinateur qu’une reine vaut plus qu’un cavalier, ainsi que d’autres choses tout aussi évidentes qu’il n’est pas en mesure de découvrir par lui-même.
67Bien que Deep Blue ait battu Kasparov dans la partie d’ouverture du match de 1996, le champion mondial demeura invaincu par la suite, gagnant trois parties et faisant match nul dans les deux autres. Il ne faut pas s’étonner que Kasparov ait finalement pris l’avantage. Malgré sa mémoire et sa vitesse prodigieuses, l’ordinateur à la fin fut défait par les connaissances que le joueur humain avait accumulées face au style de jeu mécanique, donc prévisible, de la machine. Si elle veut gagner, Deep Blue doit comporter dans son programme une part d’imprévisibilité inhérente, car, autrement, si son adversaire répète les mouvements qui l’ont menée à la victoire lors d’une rencontre, il est assuré de gagner chaque partie subséquente.
68Dans le match de 1997, les choses se passèrent différemment : la machine (sans doute à l’aide d’un programme perfectionné) l’emporta sur Kasparov. Ce résultat fut accueilli avec des prévisions presque apocalyptiques, comme s’il s’agissait de la fin du jeu d’échecs ou le début de la fin de l’humanité. Nombreux sont ceux qui ne comprirent pas que le match était en fait un affrontement entre des êtres humains, à savoir Kasparov contre l’équipe d’IBM, chaque camp disposant de moyens passablement différents (ce point de vue est confirmé par le fait que c’était un homme— et non la machine—qui effectuait les mouvements sur l’échiquier).
69L’ignorance de la nature exacte de l’intelligence n’a pas dissuadé certaines personnes d’essayer de la mesurer. En 1904, le psychologue britannique Charles Spearman employa des techniques statistiques pour déterminer un nombre qu’il appela le facteur général d’intelligence. D’après Spearman, ce nombre, désigné par le symbole g, saisit une vraie propriété dans la tête, et peut être mesuré par des tests conçus à cette fin. Bien sûr, les psychométriciens, les spécialistes des sciences humaines et autres penseurs du même genre, ne sont pas tous d’accord avec ce point de vue. Les sceptiques rejettent g comme étant une fiction, le produit d’une représentation mathématique particulière de données expérimentales.
70Dans son livre The Mismeasure of Man5, le célèbre biologiste Stephen Jay Gould argumente contre l’illusion qui consiste à considérer l’intelligence comme une chose innée, qui se mesure sur une échelle unique. Il termine son chapitre sur l’irréalité de g en citant John Stuart Mill : « On a toujours eu une forte tendance à croire que tout ce qui se voit attribuer un nom doit être une entité ou un être doté d’une existence autonome. Au cas où on ne pourrait pas trouver une entité réelle à laquelle correspond le nom, les gens ne supposeraient pas pour autant qu’elle n’existe pas, mais ils s’imagineraient plutôt qu'elle est quelque chose de particulièrement abstrus et mystérieux. » C’est la prémisse selon laquelle une certaine qualité peut être saisie par un nombre unique qui soutient la notion même d’adaptabilité, idée centrale des algorithmes génétiques. Toutefois, même si on accepte ce principe, la façon précise dont ce nombre peut être calculé demeure un obstacle majeur dans de nombreuses situations pratiques. De semblables questions se posent presque chaque fois que des modèles mathématiques sont construits. En fin de compte, la question de savoir si oui ou non cela a du sens de mesurer un attribut complexe sur une échelle linéaire peut être tranchée moins par des considération philosophiques que par la performance du modèle.
LES SOLUTIONS APPROCHÉES
71Les mathématiciens considéreront le problème du commis voyageur comme résolu le jour où quelqu’un aura trouvé un algorithme efficace qui puisse calculer (du moins en principe) le tour le plus court pour des exemples de n’importe quelle taille. Mais, étant donné qu’on a prouvé, comme nous l’avons vu au chapitre 3, que le problème est NP-complet, la plupart des experts, convaincus qu’il n’existe aucune solution générale, se sont tournés vers la construction d’algorithmes qui calculent de bonnes approximations dans un délai raisonnable. L’une des raisons pour lesquelles la solution du problème de 7397 villes (mentionné au chapitre 5) a nécessité des années de calcul réside dans le fait que, comme l’algorithme devait calculer un itinéraire optimal, la plus grande partie du temps de calcul était consacré à vérifier ce caractère optimal (autre confirmation pratique du caractère coûteux de la précision). Des méthodes par approximation, par ailleurs, ont comme objectif le calcul d’un tour un peu plus long que le circuit optimal, mais que l’on peut obtenir en un temps relativement court, même pour un grand nombre de villes. La plupart du temps, de telles solutions approchées sont pratiquement aussi bonnes que la réponse optimale, difficile à atteindre— et certainement d’un bien meilleur rapport efficacité-coût.
72On appelle heuristiques les stratégies, ou les ensembles de règles, conçues pour trouver des circuits quasi optimaux plutôt que des solutions exactes. Un exemple très simple est l’heuristique du voisin-le-plus-proche, basée sur la règle de sens commun qui consiste à toujours se rendre dans la ville non visitée la plus proche. La stratégie est la suivante : on part de n’importe quelle ville ; on choisit comme deuxième destination la ville la plus proche ; on choisit ensuite comme troisième ville celle qui est la plus proche de la deuxième et qui n’a pas déjà été visitée ; et on continue de la même façon. Quand on a fini de passer par chaque ville, on complète le tour en revenant au point de départ. L’heuristique s’accompagne, en règle générale, d’une sorte d’analyse qui permet à l’utilisateur d’estimer la qualité de l’approximation. Par exemple, s’il y a 10n villes, l’heuristique du voisin-le-plus-proche construit un tour dont la longueur ne sera pas plus de (n+1)/2 fois la longueur du tour optimal. Pour 100 villes, cela donne une solution approchée qui sera, au pire, 50 % plus longue que le tour le plus court (mais dans la pratique elle n’est généralement éloignée du but que d’environ 25 %). Les meilleures heuristiques, qui peu à peu construisent une solution par une sorte processus de croissance, parviennent à s’approcher du tour optimal avec un écart de 10 à 15 %, et ce dans un délai relativement court.
73Une performance encore meilleure peut être obtenue par les techniques dites d’optimisation locale, qui consistent à améliorer sans cesse une solution approchée en opérant des changements locaux. Un classique, dans cette catégorie, est l’algorithme inventé par Shen Lin et Brian Kernigham des Laboratoires Bell au début des années 706. Grâce à cet algorithme— ou à certaines de ses versions améliorées—, on peut calculer des solutions à des problèmes portant sur un million de villes, solutions qui, à 1 ou 2 % près, atteignent le niveau optimal. Un autre exemple d’optimisation locale, célèbre et plus direct, est l’heuristique à deux options (2-opting heuristic, en anglais). À partir d’un tour donné, celle-ci construit un autre itinéraire par une interversion, ou échange, qui consiste à inverser l’ordre de deux ou de plusieurs villes consécutives. Par exemple, si la suite 45612873 représente l’itinéraire initial de huit villes, inverser l’ordre des quatre dernières villes aboutit à l’itinéraire 45613782. La seule condition quant au choix des villes est que l’inversion produise un tour plus court. Géométriquement, un échange à deux options enlève d’abord deux côtés du graphe qui représente le tour et ensuite relie de nouveau les deux pièces selon l’autre façon possible (figure 3.10). L’algorithme continue d’exécuter lés échanges à deux options sur des tours successivement plus courts jusqu’à ce que plus aucun autre échange n’ait lieu qui pourrait diminuer la longueur de l’itinéraire.
LES PIÈCES LOCAUX
74La qualité de la solution définitive obtenue par les applications de l’heuristique à deux options dépend en grande partie de la qualité du tour de départ. Ceci constitue un inconvénient commun à beaucoup de techniques d’optimisation (sur une grande variété de problèmes, et pas seulement sur le PCV) désignées par l’expression piège du minimum local. La figure 3.11 illustre schématiquement la situation. Imaginez-vous en train d’explorer, les yeux bandés, un paysage inconnu dont vous cherchez le fond de la vallée la plus profonde. Une technique de recherche locale est comparable à l’analyse des seuls points à proximité et à un déplacement dans la direction de la pente descendante la plus escarpée. Si vous commencez à chercher au point A, vous serez alors entraîné à descendre le versant qui conduit au point B. Quand le point B est atteint, il n’y a plus d’amélioration possible, car, à ce moment-là, vous ne pouvez plus que monter. La recherche s’arrêtera, même si des points plus bas, tels que C, existent ailleurs. Le point B est appelé minimum local parce qu’il est le point le plus bas dans une certaine région. Le minimum vrai, ou global, est C—le point le plus bas dans l’espace entier. Le minimum global est aussi un minimum local, mais la réciproque est généralement fausse. Des « paysages » compliqués, résultant de problèmes pratiques, peuvent comporter des milliers de minimums locaux trompeurs.
75Comme moyen de contourner les pièges locaux pour le PCV, Shen Lin7 suggéra, dès 1965, l’idée simple de répéter la recherche locale plusieurs fois, en commençant chaque fois par un tour choisi au hasard, jusqu’à ce que l’on soit sûr que tous les tours optimaux locaux aient été trouvés. Quand l’idée des recherches locales répétées suggérée par Lin est combinée aux opérateurs génétiques de sélection, de croisement et de mutation, on obtient un procédé de calcul qui produit certains des algorithmes les plus performants pour le PCV.
LES ALGORITHMES GÉNÉTIQUES ET LE PCV
76La première tentative sérieuse pour employer les stratégies génétiques dans la résolution du problème du commis voyageur remonte au milieu des années 80, lorsque R. M. Brady, au Cavendish Laboratory de Cambridge (G.-B.), appliqua ce qu’il nomma des « stratégies d’optimisation glanées au sein de l’évolution biologique » à un modeste exemple de 64 villes du PCV8. Un des procédés de Brady consista à améliorer sans cesse un tour initial par ce qui équivaut à des essais de mutations : une section de la route est choisie au hasard et l’ordre du passage dans les villes est inversé, mais seulement si ceci raccourcit le tour. Brady obtint un meilleur résultat en divisant le temps de calcul entre deux tentatives de solution indépendantes et en choisissant la meilleure des deux à la fin de l’opération. Afin d’évaluer l’effet de la compétition, il modifia plus tard ce procédé, de telle sorte que, à intervalles réguliers, la meilleure des deux solutions remplace la plus faible. « Étrangement, écrit-il, cette stratégie compétitive était beaucoup moins bonne que l’autre. Selon notre interprétation, dans les étapes initiales de l’optimisation, la réussite n’était pas en corrélation étroite avec une réussite ultérieure, parce la diversité était réduite. » Il conclut en faisant remarquer que « si une stratégie doit favoriser la plus efficace des solutions, elle devra être conçue pour ne pas réduire drastiquement la diversité ». La leçon à retenir est qu’un plan évolutionniste qui aide les individus faibles à survivre peut présenter un avantage à long terme.
LE JEU DE L’ACCOUPLEMENT
77Si les circuits sont codés d’une façon directe, c’est-à-dire comme des listes de villes, un croisement ordinaire ne produira pas, généralement, un nouveau tour—plus long ou plus court ; en fait, il ne produira aucun tour. Par exemple, l’échange des deux derniers « gènes » de 12348756 et 76813245 donne, respectivement, 12348745 et 76813256. Dans les deux nouvelles listes, il manque une ville et une autre apparaît deux fois, de sorte qu’aucun des deux résultats ne représente un véritable tour.
78De nombreux moyens pour éviter la création de faux tours résultant de l’accouplement ont été proposés. La solution de Brady était d’abord de chercher, dans les deux chaînes des parents, des sous-chaînes passant par les mêmes villes selon un ordre différent et variant en longueur de 8 à 32 (si aucune sous-chaîne de cette sorte n’était trouvée, l’accouplement n’avait tout simplement pas lieu). Par exemple, 123465789 et 925436871 contiennent toutes les deux des sous-chaînes comprenant les villes 2,3, 4,5 et 6. Ensuite, les longueurs des deux parcours sont calculées et la sous-chaîne avec la plus courte remplace l’autre. En se reportant à l’exemple ci-dessus, supposons que la distance 23 + 34 + 46 + 65 se révèle plus courte que 25 + 54 + 43 + 36 ; alors les deux enfants seront 123465789 (inchangé) et 923465871. L’accouplement n’a pas été tenté souvent—une fois par 2000 mutations aléatoires—en raison du temps de calcul requis par la recherche des points de croisement possibles.
79Une autre stratégie d’accouplement plus élaborée a été inventée par trois informaticiens. Elle faisait partie de ce qu’on a appelé « un progrès substantiel du rendement des algorithmes génétiques »9. En 1988, H. Mühlenbein, M. Georges-Schleuter et O. Krämer10 introduisirent un nouvel algorithme génétique pour le PCV, algorithme dont ils se servirent pour trouver une solution approchée à un problème de 442 villes—la meilleure solution jusqu’à maintenant de ce problème particulier. Leur algorithme fut conçu pour être exécuté sur un ordinateur d’architecture en parallèle, chaque chromosome (c’est-à-dire chaque tour) dans la population étant affecté à un processeur différent.
UNE IDÉE QUI REVIENT À LA MODE
Une idée n’est jamais examinée dans toutes ses ramifications et une opinion n’a jamais toutes les chances qu’elle mérite.
(Paul Feyerabend)11.
80Avant de décrire le procédé de Mühlenbein en détail, revenons aux idées qui ont inspiré les premiers algorithmes génétiques. Un des principes de base était que seule l’information contenue dans les gènes des parents peut être transmise à leur progéniture. Les caractéristiques qu’un individu, ou phénotype, acquiert durant son existence ne font donc pas partie des traits transmissibles. Un exemple classique de caractéristique acquise sont les muscles qu’un forgeron a développés en exerçant son métier. Selon la génétique moderne, l’information nécessaire pour développer de tels muscles ne peut être transmise à sa progéniture. Si les enfants veulent poursuivre le métier de leur père, ils devront développer leurs muscles à partir de zéro. Bien sûr, on peut discuter sur le fait de savoir si cet état de choses est bon ou mauvais. De grosses et fortes mains seraient un atout pour un futur forgeron, mais si l’enfant décidait de devenir pianiste ? Ainsi, une trop grande dépendance à l’égard d’une connaissance toute faite pourrait affaiblir chez un individu sa capacité à apprendre par lui-même (et à s’adapter).
81L’idée que les traits acquis peuvent être héréditaires fut défendue par Jean-Baptiste de Monet, chevalier de Lamarck, qui vécut de 1744 à 1829. Lamarck se fit connaître par ses travaux sur les plantes et sur les invertébrés, mais surtout par sa conception de l’évolution, appelée lamarckisme. Sa théorie est fondée sur l’idée parfaitement plausible que les plantes et les animaux évoluent en s’ajustant aux changements survenus dans leur environnement, et que de tels changements peuvent être transmis à la génération suivante. Les idées de Lamarck se heurtèrent à la théorie de l’évolution de Darwin, théorie très répandue selon laquelle les variations dans les traits se produisent de façon aléatoire dans les chromosomes et non pas en réaction directe aux changements survenus dans le milieu.
82Beaucoup de conceptions de Lamarck, telles que la création spontanée de la vie, se révélèrent absolument fausses. Mais il continua d’avoir des disciples jusqu’en plein XXe siècle. Un de ceux-ci fut l’agronome russe Trofim Lysenko, qui convainquit Staline de dénoncer la génétique comme contraire aux principes du matérialisme dialectique et d’ériger le lamarckisme en doctrine officielle. Les meilleurs généticiens soviétiques furent congédiés, emprisonnés ou exilés. Ce qui entraîna un recul grave dans la recherche génétique en URSS. Cela eut pour conséquence de discréditer davantage le nom de Lamarck, celui-ci étant associé à ce fiasco scientifique.
83Toutefois, le lamarckisme peut avoir un rôle à jouer dans l’adaptation des systèmes artificiels. Si, pour résoudre le PCV, des algorithmes génétiques doivent être compétitifs, il semble alors inévitable d’inclure une sorte d’ingrédient lamarckien. Dans un tel projet, la sélection et le croisement n’ont lieu qu’après que chaque individu dans la population « ait fait son possible », c’est-à-dire ait calculé un minimum local en se servant d’une technique d’optimisation (celle des deux options, par exemple). Ce qui revient à laisser les traits favorables acquis dans l’« expérience » (optimisation locale) se transmettre à la génération suivante.
UNE SOLUTION GÉNÉTIQUE POUR LE PCV
L’évolution n’est pas destin, elle est occasion.
Sa trajectoire n’est pas prévisible, mais on peut la maîtriser.
Mühlenbein, M. Georges-Schlbuter et O. Krämer12.
84H. Mühlenbein et ses collaborateurs ont décrit leur algorithme comme un moyen de sauter des minimums locaux à des minimums locaux encore meilleurs. En voici les principales étapes :
851. la population initiale. 16 tours sont sélectionnés au hasard et attribués à 16 différents processeurs.
862. L’amélioration de l’adaptabilité. Chaque processeur calcule une solution optimale locale f commençant par son tour actuel t (t’est l’itinéraire de longueur minimale qui peut être obtenu par l'application répétée des échanges à deux options). Les nouvelles et meilleures solutions t'remplacent les tours originels t.
873. La sélection de partenaires d’accouplement. Les processeurs sont interconnectés comme dans une grille, de telle sorte que chacun d’eux ait quatre voisins. Au moment de la reproduction, chaque processeur accouple son tour (le donneur) avec celui d’un autre processeur (le receveur). Ce dernier est choisi parmi cinq tours possibles : les quatre voisins du receveur en plus du plus court tour dans toute la population. Ces cinq donneurs potentiels ont les probabilités de 30, 25, 20, 15 et 10 % d’être sélectionnés : plus le tour du donneur est court, plus grande est sa probabilité.
884. le croisement. Une sous-chaîne du donneur est choisie au hasard (la longueur de la sous-chaîne devant être située entre 10 et la moitié du nombre de villes). L’unique enfant de l’accouplement commence par la sous-chaîne du donneur suivie du reste des villes selon leur ordre de parution dans le receveur, tel qu’illustré ci-dessous :
890123456789 (donneur) 7109365824(receveur)
903456710982 (enfant)
915. le critere d’arret. Les 16 tours (enfants) résultant des 16 accouplements forment une nouvelle génération. Si un certain nombre (prédéterminé) de générations sont passées sans avoir amélioré la meilleure solution s (c’est-à-dire le tour le plus court), qui est la meilleure de toutes, l’algorithme s’arrête et retourne s comme étant « la » solution. Dans le cas contraire, les étapes 2 à 5 sont répétées.
92Il n’est peut-être pas surprenant que la qualité de la solution et la vitesse de l’évolution augmentent avec la taille de la population, qui varie de 2 à 24 dans les différentes exécutions de l’algorithme. Des expériences par d’autres chercheurs suggèrent que pour un temps de calcul donné, la qualité de la solution peut être également améliorée par le recours à une technique d’optimisation locale plus puissante. Ce facteur semble être plus important que la taille de la population, au point qu’un récent algorithme génétique produisit des résultats de haute qualité avec une population d’un seul individu13. Dans ce cas, l’accouplement n’est plus possible et la variation doit se faire seulement par des mutations aléatoires. Ironiquement, on a imputé l’échec des premières tentatives pour combiner informatique et évolution à une dépendance exclusive vis-à-vis de la mutation. « Au tournant des années 60, [ces tentatives] échouèrent parce qu’elles se fiaient trop aux textes de biologie de l’époque et comptaient sur les mutations plutôt que sur l’accouplement pour générer de nouvelles combinaisons de gènes », écrivit John Holland dans un article paru en 199214.
93Dans la conclusion de leur rapport, les membres de l’équipe de Mühlenbein réfléchissent au rôle des systèmes naturels comme source d’inspiration pour les modèles artificiels. « En réglant les algorithmes d’évolution, écrivent-ils, nous avons trouvé que souvent les meilleurs choix de paramètres sont ceux qui ressemblent le plus à ceux que Ton trouve dans la nature. » Par exemple, ils observent que leurs algorithmes génétiques fonctionnent mieux avec deux parents qu’avec trois ou plus. « Des algorithmes évolutionnistes peuvent facilement être créés, concluent-ils, mais leur comportement est complexe. L’évolution n’est pas destin, elle est occasion ! Sa trajectoire n’est pas prévisible, mais on peut la maîtriser. » Les deux dernières phrases se font l’écho d’une philosophie qui imprègne la méthode du calcul souple : en l’absence d’une théorie exacte, il se peut que nous ne puissions pas prédire l’avenir, mais nous pouvons encore le maîtriser.
Notes de bas de page
1 J. H. Holland, Adapation in Natural and Artificial Systems, Cambridge (MA), MIT Press, 1992.
2 Ibidem.
3 A. Rapoport et A. M. Chammah, Prisoner’s Dilemma, University of Michigan Press, 1965, p. vii.
4 R. Axelrod, « The Evolution of Strategies in the Iterated Prisoner’s Dilemma », dans L. Davis (éd.), Genetic Algorithms and Simulated Annealing, Londres, Pitman, 1987, pp. 32-41.
5 S. Jay Gould, The Mismeasure of Man, New York, Norton, 1991.
6 S. Lin et B. Kernighan, « An Effective Heuristic Algorithm for the Traveling Salesman Problem », dans Operation Research, 21,498, (1973).
7 S. Lin, « Computer Solutions of the Traveling Salesman Problem », dans Bell Systems Technical Journal, 44, 2245 (1965).
8 R. M. Brady, « Optimization Strategies Gleaned from Biological Evolution », dans Nature, vol. 317 (oct. 1985), pp. 804-806.
9 D. S. Johnson et L. A. McGeoch, « The TSP: A Case Study », dans E. H. L. Aarts et J. K. Lenstra (éds.), Local Search in Combinatorial Optimization, New York, John Wiley & Sons, 1997.
10 H. Mühlenbein, M. Georges-Schleuter et O. Krämer, « Evolution Algorithms in Combinatorial Optimization », dans Parallel Computing, 7 (1988), pp. 65-68.
11 P. Feyerabend, dans Against Method, Londres, NLB, 1975, p. 49.
12 H. Mühlenbein, M. Georges-Schleuter et O. Krämer, « Evolution Algorithms in Combinatorial Optimization », dans Parallel Computing, 7 (1988), pp. 65-68.
13 O. Martin, S. W. Otto et E. W. Felten, « Large-Step Markov Chains for the TSP Incorporating Local Search Heuristics », dans Operations Research Letters, 11 (1992), pp. 219-224.
14 J. H. Holland, « Genetic Algorithms », dans Scientific American, 1992, pp. 66-72.
Le texte seul est utilisable sous licence Licence OpenEdition Books. Les autres éléments (illustrations, fichiers annexes importés) sont « Tous droits réservés », sauf mention contraire.
Guide méthodologique universitaire
Un programme en 12 semaines
Aude Jimenez et Jamal-Eddine Tadlaoui
2011
Éloge du flou
Aux frontières des mathématiques et de l’intelligence artificielle
Arturo Sangalli
2001