Introduction aux algorithmes génétiques

Cours introduction aux algorithmes génétiques, tutoriel & guide de travaux pratiques en pdf.

Étude du croisement en population finie

Malheureusement, l’étude en population finie n’est pas si simple. Cette fois-ci, on n’a plus une suite déterministe de lois de probabilité pt sur {0,1}ℓ, mais une suite de k-uplets aléatoires πt d’éléments de {0,1}ℓ. On voudrait dire que la population finie constitue une approximation de la population infinie. Mais si l’on n’y prend pas garde, on risque des corrélation inattendues : pour connaître un individu à la génération t, il faut connaître ses deux parents, ses quatre grands-parents, etc. , ses 2t aïeux dans la population initiale. Si la taille de la population est inférieure à 2t, des aïeux apparaîtront donc forcément plusieurs fois, ce qui biaisera le processus (penser à k = 1). Cette difficulté est générale dans un système quadratique. Elle a été formalisée (cf. [ARV]) : s’il était possible de simuler rapidement tout système quadratique, on pourrait résoudre en temps polynomial tout problème de classe PSpace (classe de problèmes solubles avec une mémoire polynomiale; contient NP).
Néanmoins, le cas de l’algorithme génétique est particulier et plus simple.
L’idée est que lors du croisement de deux individus, on délaisse la moitié de l’information; si un individu a ℓ gènes, parmi ses 2t ancêtres, seuls ℓ d’entre eux au plus ont transmis de l’information génétique. On va donc comparer le processus à population infinie pt et le processus à population finie πt (où on initialise π0 en tirant k fois de suite un individu suivant la loi p0). Un dernier écueil est à éviter : on pourrait croire que le k-uplet πt, vu comme une mesure sur {0,1}ℓ, constitue une approximation de la mesure pt, mais il n’en est rien. Ceci est dû au phénomène bien connu de coalescence : à chaque génération, une petite part de l’information génétique est définitivement perdue (certains n’ont pas de descendants). Aussi, au bout d’un certain temps, toute la population est-elle constituée d’individus tous identiques. La répartition de πt ne donne donc certainement pas une bonne image de pt. Cependant, l’individu qui compose cette population-clone est aléatoire (c’est un mélange aléatoire de traits de la population de départ). On peut donc espérer que sur plusieurs simulations de l’évolution à population finie, la loi de l’individu-clone obtenu donnera une bonne image de pt. Cet essai-ci est le bon. Soit qt la loi d’un individu tiré dans le k-uplet πt