LA VIE ARTIFICIELLE: LES ALGORITHMES GÉNÉTIQUES
Évolution
La vie est apparue sur la terre il y a plusieurs milliards
d´années sous la forme d´organismes unicellulaires très simples.
La très grande diversité, le haut niveau d´organisation des
espèces végétales et animales que nous connaissons aujourd´hui
(sans compter les autres formes de vie qui pourraient exister
ailleurs ou, même, la vie artificielle) ne peut s´expliquer
que par un processus appelé l´Évolution.
Jusqu´à une époque récente le Vitalisme
attribuait la vie à un "principe actif" (Aristote) qui faisait
apparaitre de la vie spontanément à partir de la
matière inerte.
Lamarck (1744-1829) est le véritable père de l´Évolutionisme.
Il montra que les êtres évoluent du plus simple au plus complexe,
leurs organes se modifiant en fonction de leur usage et de leur
environnement. Il postula aussi que les caractères acquis étaient
héréditaires, position qui fut ensuite contredite par l´expérience.
En 1959 Charles Darwin
(1809-1882) publia son ouvrage fameux L´origine des espèces
dans lequel il montre que les espèces descendent les unes des autres
par une lente évolution, ce fut le Transformisme. Une
variabilité ontologique existe au niveau des individus (tous
différents les uns des autres), mais une variabilité phylogénétique
existe également au niveau d´une espèce, comme modifications
du patrimoine génétique transmis sous la forme de l´action du milieu
et de mutations aléatoires.
Le Darwinisme n´est pas finaliste, à la différence du Lamarckisme.
Pour Lamarck le cou de la giraffe s´est allongé "pour pouvoir
brouter les feuilles sur les branches élevées des arbres", pour
Darwin les ancêtres de la giraffe avaient des cous de longueurs
variables, ceux qui avaient le plus long étaient avantagés par hasard
et se sont reproduits prioritairement, sans qu´aucun plan prédéfini
ne l´ait imposé.
En 1830 apparut le Néodarwinisme avec Gregor Mendle (1822-1884)
qui posa les bases de la génétique moderne (confirmée par la
découverte de l´ADN) et qui peut se résumer ainsi:
1) L´évolution est le résultat d´une lente évolution de populations
d´individus au cours des générations.
2) Un matériel génétique héréditaire est la mémoire de cette
évolution, celle-ci se modifie sans cesse par croisements
et par mutations aléatoires.
3) La Sélection Naturelle ne permet qu´aux individus
les mieux adaptés de se reproduire et donc de transmettre les
gènes qui "réussissent" (ce qui est très différent de l´idée d´une
évolution qui aurait un but et un plan pour le réaliser).
Deux processus sont à l´oeuvre dans l´évolution: D´abord la
variation au niveau du génotype et la sélection au
niveau de la population en ne conservant que les individus les
mieux adaptés à leur environnement. L´évolution n´est que la
répétition d´une variation-sélection sans cesse répétée.
Il est essentiel de comprendre qu´il n´y a aucun programme,
ni aucune intention de la part de la nature, dans le processus
de l´évolution, mais seulement une modification causée par
l´adaptation.
On s´est naturellement posé la question de savoir s´il ne
serait pas possible de simuler sur ordinateur une méthode qui
réussit si bien dans la réalite. Le principal obstacle vient
de ce que cette méthode n´est pas algorithmique mais émergente,
et comment écrire des algorithmes pour construire des méthodes
non algorithmiques ? Cette contradiction n´est qu´apparente, en fait
rien n´empêche un système de se dépasser lui-même. Par exemple
les langages évolués de l´informatique ont pour but de se passer
du langage machine alors même que leur compilation génére un
tel langage binaire. De même est-il possible de concevoir, sur
le modèle du vivant, des algorithmes simulant la génétique: Ce
sont les algorithmes génétiques.
Les algorithmes génétiques
Définition
Pour un exposé général sur les algorithmes génétiques on peut se
reporter au cours
L´Évolutionnisme en Image de Synthèse )
nous résumons dans ce paragraphe.
Un algorithme génétique est essentiellement un algorithme
d´exploration utilisant les mécanismes de la sélection
naturelle et de la génétique. En favorisant la survie des structures
les mieux adaptées et en échangeant des informations de façon
pseudo-aléatoires, ils reproduisent certaines stratégies du vivant.
Partant d´une population initiale d´êtres artificiels munis de
propriétés d´autoreproduction par combinaisons sélectives de leurs matériels
génétiques, le développement de générations successives fait émerger
des individus particulièrement bien adaptés pouvant même présenter
des caractères innovants par rapport aux données de base.
Les algorithmes génétiques ont été développés par John
Holland dans les années 70 [Holland 75] à l´Universite du Michigan pour
expliquer les processus d´adaptation des systèmes naturels et
concevoir des systèmes artificiels possédant les mêmes propriétés.
Ils se caractérisent par une grande robustesse (tolérance aux pannes)
et une remarquable adaptabilité (à des environnements inconnus et
changeants).
Là ou les méthodes analytiques
traditionnelles échouent, les algorithmes génétiques,
par l´arbitraire du codage et l´absence d´hypothèse quant
aux solutions possibles aux problèmes posés, constituent des
heuristiques innovatrices. Dans la mesure où ils sont
capables de résoudre des problèmes dont on ne connait pas les solutions
(soit parce qu´elles seraient trop compliquées à expliciter, soit
parce qu´il n´y en aurait pas) ou même des problèmes mal posés, ils
sont tout à fait utilisables dans le domaine de la création artistique.
Les arts du numérique, jusqu´à maintenant coincés dans de vieux
schémas (le réalisme photographique, le scénario cinématographique,
le déterminisme, l´archaisme et la rigidité des outils, ...),
reprennent une nouvelle jeunesse avec l´interactivité, les
nouveaux moyens de diffusions (Internet) et leur ouverture
à la science et aux technologies contemporaines (les neurosciences,
la vie artificielle, ...).
Les algorithmes génétiques simples
Un algorithmes génétiques simples n´utilise que trois
opérateurs de base:
La reproduction
Le croisement
Et la mutation
Le but est d´optimiser une certaine fonction dite
d´adaptation. Le matériel génétique est représenté sous
forme de chaînes (de caractères ou binaires).
L´opérateur de reproduction revient à copier une chaîne avec
une probabilité proportionnelle à son adaptation (qui est
donnée par la fonction d´adaptation).
Les individus sélectionnés par la reproduction sont appariés
aléatoirement et leurs génotypes sont sectionnés en un point
(ou en plusieurs) aléatoirement, puis mélangés en croisant
les segments pour générer un génotype enfant héritant des
deux parents.
La mutation est un changement aléatoire (beaucoup plus rare)
de certains gènes, elle a pour but d´éviter l´apparition
d´élites qui sont des groupes d´individus excellents
mais incapables d´évoluer.
Les schèmes
Sur des chaînes binaires par exemple il est facile de
constater que la distribution des 0 et des 1 n´est pas
étrangère à la conservation de certaines propriétés de cette
chaîne lors d´un croisement. Pour étudier cela on définit
la notion de schème comme étant le représentant de
l´ensemble des chaînes pour lesquelles un gène n´est pas précisisé
(joker). Par exemple le schème (1***0) représente les chaînes
(10000), (10010), (10100), (10110), (11000), (11010), (11100) et (11110).
Il est évident que ce schème est détruit par les coupures ayant lieu
aux positions 1, 2 et 3. Alors que le schème (**01*) n´est
détruit que par les coupures en 1 et 2. Ce dernier schème est
donc plus stable que le premier.
On définit la longueur utile
d´un schème comme étant la distance entre la première et la
dernière position instanciée, par exemple:
l(010*1**) = 4 - 0 = 4
l(*1*****) = 1 - 1 = 0
On définit aussi l´ordre d´un schème comme étant le nombre
de positions instanciées, par exemple:
o(010*1) = 4
o(*****) = 0
L´influence de la longueur utile et de l´ordre d´un schème sur
sa transmission est donnée par
le Théorème des schèmes:
Les schèmes de petite longueur utile, d´ordre faible et de
performence au-dessus de la moyenne font l´objet d´un nombre
de tests exponentiellement croissant au cours des générations
successives de la population.
Ce théorème montre qu´un algorithme génétique travaillant
sur n structures à chaque génération traite en fait un nombre de
l´ordre de de n3 schèmes, Holland a parlé à ce sujet de
parallélisme implicite.
Utilisation des algorithmes génétiques
Les algorithmes génétiques sont une méthode d´optimisation
de type évolutionniste consistant à coder des solutions
potentielles d´un problème en chaînes de caractères. Ainsi pour
résoudre un problème dont on ne connait ni la solution ni même un
algorithme de résolution on construit une population de solutions
approchées, toutes fausses, mais en leur permettant d´évoluer par
croisements et mutations en optimisant une certaine fonction
d´adaptation. Au cours des générations successives apparaissent
des individus qui résolvent moins mal le problème et, au bout
d´un grand nombre de générations peuvent apparaitre des individus
résolvant le mieux possible le problème. Remarquons que ce
problème peut ne pas avoir de solution, l´algorithme génétique
fournit alors la meilleure réponse approchée.
La première apparition des algorithmes génétiques est
due à Bagley, 1967, lorsqu´il étudiait la programmation
des jeux, il introduisit aussi la notion d´autorégulation
en codant les probabilités de croisement et de mutation dans les
chromosomes eux-mêmes.
En 9170 Cavicchio a appliqué les algorithmes génétiques au
problème de la reconnaissance de formes, plus précisément
il utilise une population de détecteurs de formes capables de
reconnaitre des architectures particulières.
En 1971 Hollstein applique les algorithmes génétiques à
l´optimisation de fonctions mathématiques.
En 1972 Bosworth, Foo et Zeigler utilisèrent des alphabets de
grande taille sur des chaînes composées de paramètres réels, ce
qui a pour effet de réduire l´effet du parallélisme implicite
défini par Holland. En général un alphabet minimum est toujours préférable,
d´autre part utiliser des flotants au lieu de caractères non signifiants
fait perdre aux algorithmes génétiques toute la puissance que leur
confère le fait de travailler sur un codage arbitraire
du problème posé plutôt que sur une interprétation de celui-ci,
interprétation qui contient implicitement des informations sur une
solution encore inconnue.
En 1975 Holland publie Adaptation in natural and artificial
systems et De Jong termine sa thèse Analysis of the Behavior
of a class of genetic adaptative systems qui reste une référence
en la matière (l´optimisation de fonction).
Aujourd´hui les algorithmes génétiques sont utilisés dans
les problèmes d´optimisation industrielle, dans les problèmes de
recherche operationnelle, dans la reconnaissance de forme
et en économie.
De nombreuses applications sont actuellement à l´étude en robotique.
L´imagerie médicale utilise les algorithmes génétiques
dans les problèmes d´alignement des images obtenues par plusieurs
procédés différents ou à des temps différents.
Dans le domaine artistique citons les travaux de Karl Sims:
évolution de créatures virtuelles
Genetics Images et
Las Meninas de Michael Tolson.
La programmation génétique
Les algorithmes génétiques travaillent sur des chaînes de
longueur fixe. En 1967 Bagley avait dejà évoqué la possibilité
de coder des probabilités. En 1992 Koza [Koza 92, 94] proposa
d´appliquer la méthode évolutionniste à des populations de
programmes: Il s´agissait de faire se croiser et muter des
programmes censés résoudre un problème,
renouvellant ainsi la programmation automatique.
La difficulté résidant dans l´encodage
d´un programme dans un chaîne est résolu par l´emploi du
langage LISP qui a la particularité de représenter aussi
bien le code que les structures de données sous la forme
d´un
arbre
La figure suivante montre comment
une expression arithmétique, en l´occurrence 3 + 5,
peut s´écrire en une S-expression (+ 3 5) elle-même
représentée par un arbre:
La figure suivante montre comment réaliser des croisements
de programmes en échangeant des sous-arbres dans des arbres qui
les représentent.
Programmes sélectionnés
Programmes croisés