Algorithmes génétiques

Algorithmes génétiques : Cette famille de techniques s’inspire de la théorie Darwinienne de l’évolution pour résoudre des problèmes d’optimisation.

La théorie de l’évolution présentée par Charles Darwin en 1859 dans son livre “l’Origine des espèces”, repose sur trois principes clés : l’hérédité, la variation et la sélection.

Ainsi, lorsqu’un organisme vivant se reproduit, il transmet ses caractéristiques à ses descendants, à travers ses gènes. Cependant l’hérédité des caractères n’est pas parfaite, les gènes peuvent subir des mutations et les descendants peuvent donc présenter des variations de caractères. Par conséquent, les différents individus appartenant à une population d’organismes vivants ne sont pas tous identiques, et certains d’entre eux peuvent avoir des variations qui leur permettent de mieux survivre et de se reproduire davantage dans un certain environment. Ces individus ont donc un avantage sélectif, plus de chances de transmettre leurs gènes à la génération future. À travers ce processus, les organismes s’adaptent à leur environnement, au cours des générations.

Les algorithmes génétiques, et les algorithmes évolutionnaires en général, reposent sur ces principes. Comment fonctionnent-ils ? Tout d’abord, on cherche à représenter les solutions possibles du problème d’optimisation sous la forme d’un génome, puis on génère une population de solutions potentielles au problème donné, on sélectionne ensuite les solutions les plus performantes vis à vis de la tâche à optimiser, on crée alors une nouvelle population en copiant à l’identique les solutions sélectionnées, enfin on applique des opérateurs de variation aux génomes des individus de la nouvelle population, afin de créer des solutions différentes. La population d’enfants devient à son tour la population parentale, et on itère la même procédure jusqu’à ce qu’une solution satisfaisante soit trouvée.

En pratique il existe un grand nombre de façons de représenter les solutions potentielles à un problème, les codages les plus courants sont par exemple les vecteurs de nombres (binaires, entiers ou réels) et les graphes (par exemple des structures analogues aux arbres de décision). De même, il existe différentes méthodes de sélection (tournoi, par rang, uniforme…) et de variation (mutations ponctuelles, cross-over), et le bon choix de ces différents aspects est crucial pour obtenir des résultats pertinents.

Ces algorithmes permettent d’explorer l’espace de solutions possibles de manière non exhaustive, afin d’obtenir une solution satisfaisante. Par conséquent, ils sont particulièrement utiles dans le cas d’espaces de très grande taille, présentant des optima locaux, difficiles à explorer avec des algorithmes déterministes d’optimisation. De plus, ces algorithmes s’adaptent facilement à des espaces de données qui changent dans le temps. A contrario, leur principal inconvénient est que leurs résultats dépendent fortement du  choix des différents éléments qui les constituent ainsi que des paramètres associés.

 Cette vidéo schématise comment des organismes artificiels apprennent à marcher grâce à des algorithmes génétiques.

La figure suivante illustre le fonctionnement de ces algorithmes. Les individus sont ici figurés par des ellipses de couleur, et la fonction à optimiser (axe “fitness”) dépend de la couleur et de la forme des individus. Les qualités de certains individus sont illustrées sur la courbe selon ce maillage en trois dimensions (qualité, couleur, forme) : on voit ainsi que l’ellipse rouge a un très fort avantage sélectif, contrairement à l’ellipse vert pâle, l’ellipse bleu présentant une qualité moyenne. Les trois images suivantes correspondent respectivement à la population initiale, à celle à mis parcours et à la population finale. On constate qu’au fur et à mesure, les caractéristiques des ellipses évoluent vers celles du meilleur individu possible.