Vie Artificielle

Introduction aux Algorithmes génétiques.

    La physique, la biologie, mais aussi l'économie ou la sociologie sont couramment confrontées au problème classique de l'optimisation. "L'économie d'intention scientifique" comme l'appelait François Perroux, le dernier grand économiste français, s'est même fait une spécialité de la résolution de ce type de problème¹. D'une manière générale, une partie importante des développements mathématiques au cours notamment du XVIII^éme Siècle a été consacrée à ce sujet (souvenez vous de vos cours d'analyse de Terminale et de ces incessantes questions sur l'annulation de la dérivée d'une fonction !).

     Les méthodes purement analytiques ont largement fait leurs preuves. Elles souffrent toutefois d'une faiblesse rédhibitoire : le monde n'est que très exceptionnellement régi par ces magnifiques fonctions continues et dérivables auxquelles nous ont habitué nos professeurs².

     D'autres méthodes combinant analyse mathématique et recherche aléatoire ont permit de dépasser cette limitation. Imaginez une région montagneuse dans laquelle on disperse un certain nombre de petits robots. Ces robots ont la capacité de suivre systématiquement le chemin le plus raide. Arrivé à un sommet, chaque robot s'immobilise en déclarant avoir découvert l'optimum. Ce type de méthode est très efficace, mais rien ne garantit que l'optimum a été atteint. On se heurte à l'obstacle majeur du volume de données engendré par les phénomènes étudiés. Cette procédure ne peut s'appliquer qu'à des espaces de recherche réduits.

     Vous vous demandez peut-être ce que viennent faire ces considérations dans un texte censé traiter de la Vie Artificielle. Le lien existe pourtant, et est même relativement évident.

A- Evolution et optimisation.

     Nous voici 45 millions d'années en arrière auprès d'un Basilosaurus :

     Le Basilosaurus était une sorte de prototype de baleine d'environ 15 mètres pour 5 tonnes. Encore doté d'une tête et de pattes postérieures, il se déplaçait grâce à des mouvements ondulatoires et chassait de petites proies³. Ses membres antérieurs étaient réduits à de courtes nageoires avec une articulation au niveau du coude.

     Les déplacements dans un milieu aussi visqueux que l'eau nécessitent de gros efforts. Les individus concernés doivent absorber suffisamment d'énergie pour vaincre la résistance du milieu et contrôler leur trajectoire. La patte courte et articulée n'est pas vraiment adaptée à la nage⁴, elle ne joue que très imparfaitement son rôle de stabilisateur. Pour se faire, un double phénomène doit se produire : le raccourcissement du "bras", associé à la fixation de l'articulation du coude, et l'allongement des doigts (hyperphalangie) qui vont former la base de la nageoire.

     L'image précédente montre que deux des doigts du dauphin commun sont hypertrophiés au détriment du reste du membre.

     Le basilosaurus était un chasseur, il devait être rapide et précis. Au cours des temps, croisements et mutations génétiques se sont multipliés. Des individus disposant de pattes plus courtes et de doigts allongés sont apparus. Ils se déplaçaient plus rapidement et plus précisément, et en conséquence, étaient susceptibles de vivre plus longtemps et d'avoir une descendance beaucoup plus nombreuse que leurs congénères. Les générations se succédant, cette amélioration s'est poursuivie pour aboutir à la formation de nageoires modernes.

    Dans le même temps, des mutations générales concernant le profil hydrodynamique de ce qui était le Basilosaurus, se sont poursuivies : la tête s'est intégrée dans le corps, le profil s'est affiné, la nageoire caudale s'est renforcée ... Au final, un individu parfaitement adapté aux contraintes du milieu aqueux a émergé.

     Cette adaptation au milieu, cette optimisation morphologique est si parfaite qu'à l'heure actuelle, la ressemblance entre le requin, le dauphin ou le sous-marin est frappante. Pourtant le premier est un poisson cartilagineux (Chondrichthyen) dont l'origine remonte au dévonien (- 400 millions d'années) soit bien avant l'apparition du premier mammifère dont descendent les cétacés⁵.

     Les mécanismes darwiniens sont donc à l'origine d'un processus d'optimisation⁶, optimisation hydrodynamique pour les poissons et autres animaux marins, aérodynamiques pour les ptérodactyles, les oiseaux ou les chauves souris ...

    Cette constatation est à la base des algorithmes génétiques.

B- Evolution et Algorithmes génétiques.

     C'est au début des années 1960 que John Holland de l'Université du Michigan a commencé à s'intéresser à ce qui allait devenir les algorithmes génétiques. Ses travaux ont trouvé un premier aboutissement en 1975 avec la publication de Adaptation in Natural and Artificial System⁷.

     Holland poursuivait un double objectif : améliorer la compréhension des processus naturels d'adaptation, et concevoir des systèmes artificiels possédant des propriétés similaires aux systèmes naturels⁸.

     L'idée fondamentale est la suivante : le pool génétique d'une population donnée contient potentiellement la solution, ou plutôt une meilleure solution, à un problème adaptatif donné. Cette solution n'est pas exprimée car la combinaison génétique sur laquelle elle repose est dispersée chez plusieurs individus. Ce n'est que par l'association de ces combinaisons génétiques au cours de la reproduction que la solution pourra s'exprimer. Trivialement, on pourrait par exemple considérer que le raccourcissement de la patte et l'allongement des doigts chez le basilosaurus supposent l'expression de deux "gènes" différents. Ces "gènes" n'existent simultanément chez aucun individu. Lors de la reproduction et de la recombinaison génétique associée, un individu hérite, par hasard, d'un ce ces gènes de chacun de ses parents : sa patte est désormais proche de la nageoire.

         L'originalité des travaux de Holland repose en particulier sur le fait qu'il n'a pas considéré les seules mutations comme source d'évolution mais aussi et surtout les phénomènes de croisement⁹ (crossover) : c'est en croisant les solutions potentielles existant au sein du pool génétique que l'on peut se rapprocher de l'optimum.

C- Fonctionnement d'un Algorithme Génétique.

     Afin d'illustrer notre raisonnement, nous allons nous placer dans un monde où la génétique est très simplifiée. Les "chromosomes" codent un ensemble de caractéristiques liées. La codification se fait à travers des "gènes" programmant l'activation (l'expression) ou la désactivation d'un caractère.

     Examinons le pool génétique d'une population de quatre basilosaurus appartenant à ce monde. On considérera le "chromosome" qui code la longueur des membres antérieurs. Chez ces animaux imaginaires, les caractéristiques de longueur de la patte d'une part et des doigts d'autre part, sont codées sur quatre "gènes". Les deux premiers correspondent à la patte, les deux autres aux doigts.

     Dans notre représentation du génome, le cercle sur fond bleu représente l'expression d'un caractère, la croix sur fond vert son absence d'expression. Le génome idéal correspond à des pattes courtes (deux premiers "gènes" verts) et des doigts longs (gènes bleus), soit : .

    Le pool génétique de notre population est le suivant :

    Au cours de la reproduction, les chromosomes se croisent. Dans trois cas sur quatre, le croisement s'est opéré au centre du génome. Pour D', il s'est opéré après le premier "gène" de C, il a donc hérité de trois "gènes" de D.

     Le lien existant entre degré d'adaptation et probabilité de reproduction se traduit par une tendance à l'élévation du degré d'adaptation moyen de la population ; dans notre cas, il passe de 7 à 10.

     Au cours du cycle de reproduction suivant, C' et D' vont avoir un descendant commun :

     Le nouvel individu a hérité du génome recherché : ses pattes sont devenues des nageoires.

     On voit par là que le principe de fonctionnement d'un algorithme génétique est simple :

1. Codage du problème sous forme d'une chaîne binaire ;
2. Génération aléatoire d'une population. Celle-ci contient un pool génétique qui représente un ensemble de solutions possibles ;
3. Calcul d'une valeur d'adaptation pour chaque individu. Elle sera fonction directe de la proximité des différents individus avec l'objectif ;
4. Sélection des individus devant se reproduire en fonction de leurs parts respectives dans l'adaptation globale ;
5. Croisement des génomes des parents ;
6. Sur la base de ce nouveau pool génétique, on repart à partir du point 3.

     On peut également exprimer le fonctionnement d'un algorithme génétique en se référant aux notions de génotypes (GTYPE) et phénotypes (PTYPE)¹⁰ :

1. On sélectionne des paires de GTYPE en fonction de l'adaptation de leurs PTYPE respectifs ;
2. On applique les opérateurs génétiques (reproduction, croisement et mutation) pour créer de nouveaux GTYPE ;
3. On développe les GTYPE pour obtenir les PTYPE de la nouvelle génération et on repart en 1.

     Reproduction et croisement sont à la base des algorithmes génétiques. Il existe toutefois un troisième opérateur : la mutation. En effet, au sein d'un pool génétique donné, même important, il est possible que la solution recherchée ne soit pas présente. L'opérateur de mutation permet l'émergence de nouvelles configurations génétiques, en élargissant le pool, ces mutations améliorent les possibilités de trouver une solution optimale. D'autres opérateurs sont également possibles comme l'inversion mais nous n'en traiterons pas ici.

D- Adaptation et Sélection : le problème du rééchelonnement.

     Nous avons vu plus haut que dans un AG, la méthode "classique" veut que la probabilité de reproduction soit fonction directe de la part de l'individu dans le niveau d'adaptation global de la population. On simule ainsi la pression adaptative de l'environnement.

     L'utilisation de cette méthode pose toutefois deux grands types de problèmes:

1. Un "super-individu" étant trop souvent sélectionné, la population tend à converger vers son génome. La diversité du pool génétique est alors trop réduite pour que l'AG puisse progresser.
2. Au fur et à mesure que l'AG avance, les différences de niveau d'adaptation entre les individus tendent à s'estomper. Les meilleurs ont alors sensiblement la même probabilité de sélection que les autres et l'AG ne progresse plus.

     Pour palier à ces problèmes, il est possible d'effectuer différents types de transformation aux valeurs d'adaptation. On relèvera quatre méthodes principales:

1- Fenêtrage : Pour chaque individu, on réduit sa valeur d'adaptation de la valeur d'adaptation du pire individu. Ceci permet de renforcer les individus les plus forts au détriment des plus faibles.

2- Exponentiel : Proposée par S.R. Ladd¹¹, cette méthode consiste à prendre la racine carrée des valeurs d'adaptation augmentée de 1. Ceci permet de réduire l'influence des individus les plus forts.

3- Transformation Linéaire : On applique une transformation linéaire à chaque valeur, soit f ' = a.f + b. Là encore, on réduit ainsi la valeur des individus les plus forts.

4- Linéarisation : Les valeurs d'adaptation sont linéarisées. Par exemple, sur une population de 10 biomorphs, le premier individu aura 100, le second 90, 80 ... Le dernier individu aura 10. On s'affranchit ainsi des contraintes du calcul direct. Même si les différences entre individus sont très faibles, ou très fortes, l'écart entre les probabilités de reproduction ne dépend plus que du classement de l'individu.

     Pour illustrer le fonctionnement de ces méthodes, prenons une population de quatre individus et examinons l'effet des rééchelonnements. pour chaque individu, nous donnons la valeur d'adaptation et la probabilité de sélection correspondante.

     Le fenêtrage élimine les individus les plus faibles - la probabilité passe à 0 - et stimule les plus forts, on passe ici pour le meilleur de 50 à 67 %.

     L'exponentielle aplatit la distribution. Elle est très utile quand un super individu (soit un individu dont la probabilité de sélection est très importante) induit une convergence trop rapide.

     La transformation linéaire joue, à un degré moindre, le même rôle que l'exponentielle.

     Enfin la linéarisation est neutre vis à vis de la distribution des valeurs d'adaptation, elle ne dépend que du classement. Elle s'affranchit aussi bien des super-individus que d'une distribution trop homogène.

Conclusion

    Les AG sont des systèmes originaux, s'inspirant du fonctionnement présumé du vivant¹². La méthode utilisée est très différente des algorithmes classiques d'optimisation. On retient quatre points principaux¹³ :

1. Utilisation d'un codage des paramètres, et non des paramètres eux-mêmes ;
2. Travail sur une population de points, au lieu d'un point unique ;
3. Utilisation des seules valeurs de la fonction à optimiser, et non de leur dérivée ou d'une autre connaissance auxiliaire ;
4. Utilisation de fonctions de transition probabilistes, non déterministes.

     Il est important de comprendre que le fonctionnement d'un tel algorithme ne garantit nullement la réussite. Nous sommes en présence d'un système stochastique et la probabilité existe qu'un pool génétique soit trop éloigné de la solution, ou, par exemple, qu'une convergence trop rapide bloque le processus d'évolution. Ces algorithmes n'en sont pas moins extrêmement performants, leur utilisation se développe dans des domaines aussi divers que la prévision boursière, l'ordonnancement des systèmes de production ou la programmation des robots d'assemblage dans l'industrie automobile.

1- Le paradigme dominant de l'Economie Politique, dit "néo-classique", celui qui inspire le libéralisme, n'est en fait en grande partie qu'une ode magnifique aux mathématiques de l'optimisation.

2- C'est là tout l'objet de la "révolution de la non linéarité" qui bouleverse la science contemporaine.

3- S.J. Gould et al., Le livre de la vie, Seuil, Science ouverte, 1993, pp.186 ss.

4- On pense que le basilosaurus se reproduisait à terre, ses pattes conservaient donc une certaine utilité. Harrison R, Bryden M.M. dir., Baleines, dauphins et marsouins. Bordas, 1989.

5- Ce phénomène, connu sous le nom de convergence évolutive, est très courant. Dans le cas présent, on pourrait également citer l'Ichthyosaure, reptile marin du secondaire dont la morphologie était proche du requin et du dauphin.

6- Il est important de comprendre que si l'évolution induit une optimisation, elle n'est en aucune manière à la recherche d'un optimum absolu. Rien ne prouve dans le darwinisme que les individus en général et l'homme en particulier sont des optima. Le rôle de la contingence au cours de l'évolution est par trop important pour que l'on puisse parler d'un quelconque optimum.

7- Holland J.H., Adaptation in natural and artificial system, Ann Arbor, The University of Michigan Press, 1975.

8- Goldberg D., Algorithmes génétiques, Addison-Wesley, 1994.

9- Emmeche C., Garden in the Machine. The Emerging Science of Artificial Life, Princeton University Press, 1994, pp. 114 ss.

10- Heudin J.C., La Vie Artificielle, Hermès, 1994, pp. 91 ss.

11- S.R. Ladd, Genetic Algorithm in C++, 1999-2000. Downloadable book. http://www.coyotegulch.com.

12- La "programmation biologique" ne se limite pas aux AG, un autre cas bien connu est celui des réseaux de neurones.

13- Goldberg D, idem, pp. 8 ss.

Jean-Philippe Rennard    Avril 2000
http://www.rennard.org/alife
alife@rennard.org

Copyright : Ce texte est mis à la disposition du public à seule fin pédagogique. Il est libre pour tout usage personnel. En cas d'usage public non commercial, je vous demande d'en citer l'origine et l'auteur. Tout usage commercial est formellement interdit hors accord écrit de ma part.