Contacts tuteurs : Antoine Saillenfest (antoine.saillenfest AT telecom-paristech.fr)

Les algorithmes génétiques sont utilisés pour résoudre, de manière approchée, des problèmes d’optimisation, en particulier lorsqu’il n’existe pas de méthode de résolution exacte ou lorsque celle-ci s’avère trop coûteuse en temps. Les algorithmes génétiques sont construits sur le principe de la sélection naturelle que l’on applique à un ensemble initial donné de solutions potentielles au problème d’optimisation et qui, par cycles d’évolution successifs permet de faire émerger une solution satisfaisante, approchée ou réelle dudit problème.

Les organismes vivants sont constitués de cellules, dont les noyaux comportent des chromosomes qui sont des chaînes d’ADN et dont l’élément de base est un gène. Ces gènes, rassemblés en chaînes, codent les fonctionnalités de l’organisme (la couleur des yeux …). Les algorithmes génétiques font une analogie avec la théorie de l’évolution qui propose qu’au fil du temps, les gènes conservés au sein d’une population donnée sont ceux qui sont le plus adaptés aux besoins de l’espèce vis à vis de son environnement.

La sélection naturelle est modélisée par un ensemble de trois phases successives répétées lors de chaque cycle de l’algorithme (une génération):

• la phase de sélection : il s’agit de choisir quels individus vont être conservés lors du passage d’une génération à une autre (d’un cycle à l’autre de l’algorithme), c’est-à-dire ceux dont le génome est le plus adapté.
• La phase de croisement (ou reproduction) : cette phase consiste à croiser de manière simple ou multiple (en un ou plusieurs points) deux chromosomes pour en donner deux nouveaux.
• La phase de mutation : la mutation d’un gène consiste à le remplacer par un autre. L’objectif de la phase de mutation est d’éviter une convergence prématurée de l’algorithme, par exemple la convergence trop rapide vers un extremum local

Les trois phases décrites précédemment doivent être paramétrées correctement en fonction des problèmes à résoudre considérés. Par ailleurs, les algorithmes génétiques doivent être utilisés avec discernement et ne doivent pas remplacer des méthodes plus adaptées ou plus efficaces.

Dans le cadre de PACT, cette méthode peut être utilisée :

• pour trouver la solution optimale d’un problème donné
• comme source d’inspiration pour la modélisation d’un phénomène naturel

Bibliographie partielle :

R. Poli, W. B. Langdon et N. F. McPhee, A Field Guide to Genetic Programming (disponible gratuitement)

J. H. Holland, Adaptation In Natural And Artificial Systems, University of Michigan Press (1975)