GÉNÉRALITÉS
La génétique
Qu´est-ce qu´est la génétique ?
Un être vivant se distingue facilement d´un objet inerte de par
sa forme, ses fonctions et, surtout, par le fait qu´il est capable
de se reproduire. Ainsi la notion de vivant est-elle intimement
liée à celle de mort (des individus) et d´évolution (d´une population).
La reproduction ne concerne pas seulement une population, mais encore
chaque individu qui la compose. En effet tout être vivant est un
système ouvert échangeant de l´énergie avec son environnement et sa
stabilité repose sur la prolifération incessante des cellules qui le
constituent.
Mais la permanence d´un individu, comme d´une population, n´est
maintenue qu´au prix d´une variation qui constitue une autre
propriété fondamentale de la vie et qui a été mise en évidence par
Gregor MENDEL au milieu du XIXe siècle avec les lois de
l´hérédité.
Celles-ci s´expliquent par la notion de gène qui est un segment de
molécules d´acide désoxyribonucléique (ADN) servant de modèle
pour coder la synthèse des molécules protéiniques.
La génétique, qui étudie la reproduction et la variation, pose le
problème de l´évolution.
La variation
Les variations acquises (comme le brunissement de la peau au soleil)
ne sont pas héréditaires (contrairement a ce que stipule le LAMARCKISME).
Elles ne correspondent qu´à des variations des potentialités de
l´organisme, celles-ci seules étant transmissibles.
Les mutations apparaissent comme facteur de variation dans
la reproduction par divisions cellulaire (la mitose) qui, sans elle,
donnerait lieu à une population de clones. Une mutation est un accident
aléatoire survenu lors d´une reproduction conforme dont la fréquence
est faible (de l´ordre de 1/10000 chez l´homme).
Le recombinaison génétique apparait chez les organismes supérieurs
à reproduction sexuée. Dans ce cas la variation ne résulte pas de la
modification accidentelle d´un modèle (comme l´est la mutation), mais
d´un échange entre deux modèles différents. Sauf pour les vrais jumeaux
(issus d´un oeuf unique), deux enfants ayant les mêmes parents sont toujours
différents.
La théorie chromosomique de l´hérédité
Gregor MENDEL (1822-1884) expérimenta des croisements entre deux espèces
de pois, les pois ronds et les pois ridés, et en déduisit des lois
qui portent son nom:
La première loi stipule que la première
génération est uniforme, c´est à dire que tous les pois présentent le
caractère de l´un des parents, ici ce sont tous des pois ronds (on dit que
le caractère rond est dominant).
La
deuxième loi concerne la deuxième génération, issue par croisement
de cette première génération uniforme: Elle n´est plus uniforme et
le caractère "pois ridé" est repparu avec la fréquence de 1/4. Les
autres pois, dans la proportion 3/4, sont ronds mais ne sont pas
génétiquement uniformes et 1/3 des pois issus par autofécondation
sont ronds (identiques à ceux de la variété parentale pure),
les deux autres tiers sont ridés et pourront fournir 3/4 de pois ronds
et 1/4 de pois ridés (identiques à ceux de la première génération).
À partir des pois ridés de la deuxième génération on ne peut obtenir,
par autofécondation, que des pois ridés. En résumé, la deuxième
génération est composée de 3 types de pois: Les deux types purs en
proportion 1/4 pour les pois ronds et 1/4 pour les pois ridés, et
un type, en proportion 1/2, pouvant reconstiter la première génération.
Ces proportions simples suggèrent des lois statistiques. Les gènes
contiennent les caractères des organismes et peuvent se reproduire
à l´identique (copie) ou subire des mutations. La figure 1-1 illustre
les lois de MENDEL: R désigne les pois ronds et r les pois ridés. Les
R/R et r/r désignent les deux homozygotes. R/r rt r/R désignent
les deux hétérozygotes.
Parents
Gamètes
1e génération
Gamètes
2ème generation
Figure 1-1: Les lois de MENDEL
Chez les organismes
supérieurs la reproduction sexuée est réalisée par des cellules
spéciales appelées gamètes. L´union d´un gamète mâle et d´un
gamète femelle produit un zygote (ou oeuf), cellule originelle à
partir de laquelle se développera un individu. Si les deux gamètes
sont identiques l´individu est dit homozygote,
sinon il est dit hétérozygote. Lors de la reproduction,
chaque individu tirant au hasard un gamète mâle et un gamète femelle
il se produira 1/4 de chacun des deux types d´homozygotes et 1/2
d´hétérozygotes.
Lorsque les parents différent par plus qu´une alternative, la
formation des gamètes chez les hétérozygotes est réalisée indépendamment
pour chaque couple d´opposition. Ainsi le croisement de deux
variétés de pois, l´une à pois ridés et jaunes et l´autre à pois
ronds et verts, donne une première génération uniforme de pois
ronds et jaunes (jaune étant dominant par rapport à vert) correspondant
à un génotype d´hétérozygotes d´ordre 2 R/r J/v. Il se formera ensuite
4 types de gamètes RJ, Rv, rJ, rv en nombres égaux. Lors de la
reproduction leur appariement aléatoire produira 9 génotypes
regroupés en 4 phénotypes: RJ,Rv,rJ et rv de probabilités respectives
9/16, 3/16, 3/16 et 1/16. Ce principe se généralise
sans difficulté à un nombre quelconque d´alternatives.
L´évolutionnisme
La théorie de l´évolution
La notion d´évolution apparaît la première fois avec LAMARCK
en 1809. En 1858 Charles DARWIN propose une théorie pour expliquer
la genèse des espèces par filiation directe et continue: La
Sélection Naturelle favorisant la reproduction des individus
les mieux adaptés. Les preuves de l´évolution sont aujourd´hui
irréfutables, et seules certaines sectes et une partie de l´extrême droite
(en particulier pour ce qui y est de la notion de "race")
ne l´acceptent pas.
Le Lamarckisme
LAMARCK est le père de l´évolutionnisme, il dit que les êtres
évoluent des plus simples (les infusoires) aux plus complexes (les mammifères)
et énonce deux lois:
1) "Dans tout animal qui n´a point dépassé le terme de ses
développements, l´emploi plus fréquent et soutenu d´un organe quelconque
fortifie peu à peu cet organe, le développe, l´agrandit et lui donne une
puissance proportionnée à la durée de cet emploi; tandis que le défaut
constant d´usage de tel organe l´affaiblit insensiblement, le détériore,
diminue progressivement ses facultés et finit par le faire disparaître."
2) Les caractéres acquis sont héréditaires. Cette deuxième loi a été
contredite par l´expérience: Les caractères acquis ne sont pas
transmissibles.
Le Darwinisme
DARWNIN inventa le Transformisme vers 1830 en observant que
des espèces isolées dans des iles évoluaient différemment des mêmes
espèces restées sur le continent.
1) Dans une espèce donnée les jeunes sont tous différents entre eux
et ne ressemblent pas exactement à leurs parents. D´autre part il existe
une variabilité acquise due aux changements du milieu, et il existe aussi
une variabilité imprévisible due aux mutations.
2) La sélection artificielle fortifie les caractères choisis.
3) La sélection naturelle a les mêmes effets que la sélection artificielle.
4) La sélection est le résultat de la compétition entre individus,
ou entre espèces, pour survivre, trouver de la nourriture.
5) La sélection travaille sur des caractères arbitraires, le seul
critère étant que ce caractère donne un certain avantage à l´individu
qui le possède.
La sélection naturelle aboutit à la survivance des plus aptes et
à la disparition des autres.
Les algorithmes génétiques
Les machines et la vie
On a déja vu la différence entre les
ordinateurs
classiques et le cerveau humain,
et on a montré à cette occasion que la simulation du fonctionnement du système
nerveux par des réseaux neuronaux ouvrait la voie à un nouveau
mode de pensée, le connexionnisme, par opposition à la pensée
algorithmique.
De même, on pourrait s´inspirer de la façon dont la nature trouve des
solutions à des problèmes de survie, pour
construire des machines qui découvriraient les réponses à des questions
sans passer par l´écriture d´un algorithme.
Dans les années soixante dix John HOLLAND inventa les algorithmes
génétiques dans ce but.
Remarquons que qualifier d´"algorithme" une méthode visant
à se passer justement des algorithmes n´est contradictoire qu´en apparence:
Il ne s´agit en effet que d´éviter au programmeur de passer par l´écriture
d´un algorithme particulier pour chaque problème.
Qu´est ce qu´est un algorithme génétique ?
Un algorithme génétique est caractérisé par:
1) Les solutions qu´il trouve n´ont pas été codées par le programmeur
mais découlent directement du fonctionnement de l´algorithme lui-même.
2) Il peut être appliqué à toute une classe de problèmes n´ayant
que peu de rapport avec le problème initial.
3) Pour ce faire l´algorithme traite des populations de solutions
(construites aléatoirement, donc peu performantes) qu´il fait
évoluer par croisements et mutations en sélectionnant celles qui
répondent le mieux à une certaine fonction d´adaptation. La théorie
de l´évolution stipule que de telles populations s´améliorent au cours
de leurs reproductions et que, au bout d´un certain temps, apparaissent
des solutions optimales. Il s´agit de construire des solutions à
partir de leurs génomes qui définissent la façon dont elles se comportent et,
donc, la façon dont elles sont évaluées. De tels génomes sont modélisés
par des chaînes de bits et un problème important est celui de leur codage.
Les algorithmes génétiques sont des méthodes
d´optimisation.À la différence des méthodes classiques qui ne peuvent
résoudre que les problèmes parfaitement bien posés, les algorithmes
génétiques peuvent résoudre des problèmes mal posés et c´est la raison
pour laquelle nous les étudieront dans le cadre de la création artistique.
Ce sont des algorithmes d´exploration faisant appel à la sélection
et à la génétique. Ils favorisent les organismes les mieux adaptés
par un échange aléatoire d´information et ne sont pas sans rappeler la
façon dont les êtres vivants procédent pour résoudre des problèmes.
Leur principale application est l´amélioration de la robustesse
des systèmes artificiels devant évoluer dans un environnement
imprévisible, on en attend aussi une amélioration des connaissances
sur les systèmes naturels. L´auto-réparation, l´auto-guidage et la
reproduction, qui sont des caractéristiques du vivant, sont étendus
aux systèmes artificiels diminuant d´autant leur coût en terme
de maintenance. Il est tentant de s´inspirer de la nature, qui réussit
si bien dans ce domanie, et c´est ce qu´a fait John HOLLAND
[HOLLAND 1975]. Ils s´appliquent aujourd´hui dans le monde des
affaires, dans le domaine militaire, en recherche scientifique, en
ingéniérie et aussi dans le domaine artistique [SIMS 1991, 1994].
Méthodes d´optimisation
Optimisation
Optimiser c´est trouver une méthode pour atteindre le meilleur
lorsque l´on a défini une mesure de la qualité de ce que l´on cherche
à optimiser. Il faut distinguer le processus de recherche et
l´optimum à atteindre. En particulier Une méthode atteignant
rapidement un optimum approché peut être préférée, dans certains
cas, à une méthode donnant l´optimum vrai en un temps prohibitif.
Méthodes analytiques
Elles supposent que la fonction dont on cherche un minimum est
continue et dérivable.
Les méthodes indirectes résolvent les systèmes d´équations obtenues
en annulant le gradient (extremums aux points de pente nulle).
Les méthodes directes reviennent à se déplacer dans une direction
telle que le gradient soit maximum en module.
Dans les deux cas les extremums trouvés sont locaux et
dépendent du point de départ. De plus la plupart des fonctions
"interessantes" ne sont pas dérivables et souvent même pas continues.
Ces méthodes ne sont applicables que pour des fonctions très
particulières et donc pour des problèmes très spécifiques.
Figure 1-2: Méthodes indirecte et directe
Méthodes énumératives
Un balayage systématique de l´ensemble de définition de la fonction
(supposé fini ou du moins discrétisé) permet d´atteindre les
extremums. Il est évident qu´une telle méthode est inefficace dès
que l´espace d´exploration est grand.
Méthodes aléatoires
En remplaçant le balayage systématique par un échantillonnage aléatoire
on retombe sur la même inefficacité qu´avec la méthode précédente.
Figure 1-3: Méthodes énumérative et aléatoire
Cependant on verra que les algorithmes génétiques utilisent aussi
l´aléatoire, mais de façon dirigée et "intelligente".
Ces deux dernières méthodes s´appliquent bien à tous les
problèmes, mais avec des taux de réussite tout à fait désastreux. Il
reste donc à trouver des méthodes plus générales s´appliquant
également à tous les problèmes, c´est à dire des méthodes robustes.
Caractérisation des algorithmes génétiques
Les algorithmes génétiques se caractérisent par:
1) Ils utilisent un codage des paramètres et non les
paramètres eux-mêmes. Alors que dans les méthodes traditionnelles
le codage est intimement lié à la spécificité du problème à résoudre,
dans les algorithmes génétiques le codage est arbitraire, on dit
qu´ils sont aveugles.
2) Ils travaillent sur une population d´individus et non
pas sur des points isolés. La recherche d´un extremum est
menée en parallèle par plusieurs individus, réduisant ainsi le risque
de n´atteindre qu´un extremum local.
3) Ils n´utilisent pas les propriétés de la fonction à optimiser,
en particulier celle-ci n´est supposée ni dérivable ni continue, d´où
leur généralité d´application.
4) Enfin ils sont probabilistes et non pas déterministes, se
rapprochant par là des phénomènes naturels.
5) Ils empruntent leur vocabulaire à celui de la génétique naturelle:
Les chromosomes (batonnets porteurs de l´information
génétique) sont constitués de gènes
pouvant prendre différentes valeurs appelées
allèles, un ou plusieurs chromosomes constituent le plan de
construction et de fonctionnement d´un organisme. On parlera, en génétique
artificielle, de chaînes de caractères pris dans
un certain vocabulaire, l´ensemble des chaînes est appelé une
structure.
La position d´un gène, ou son locus, est indépendante
de sa fonction. De même, le codage des paramètres d´un problème ne devra
pas utiliser leur signification.
Le génotype est l´ensemble du matériel génétique, et le
phénotype est l´organisme formé par l´interaction du génotype
avec son environnement. On parlera d´un ensemble de paramètres
formés par les structures décodées, encore appelés solutions.