VI.4. Algorithmes Génétiques (1/16)

Principes

Les algorithmes génétiques, créés par John Holland, [Holland, 75], puis développés par David Goldberg, sont des algorithmes d’exploration définie par les deux principes du néo-darwinisme :

• Survie des individus les mieux adaptés, C. Darwin.
• Recombinaison génétique, J. Mendel.

Le principe de base est de simuler l’évolution d’une population de solutions avec les règles citées ci-dessus en vue d’obtenir une solution, ou un ensemble de solutions les plus adaptées au problème. " A chaque génération, un nouvel ensemble de créatures artificielles est créé en utilisant des parties des meilleurs éléments de la génération précédente ; ainsi que des parties innovatrices à l’occasion. ", [Goldberg, 89]. La figure de la page suivante montre le déroulement d’un algorithme génétique standard.

Les phases sont les suivantes :

• Etape 1 : Créer la population initiale et évaluer chacun de ses individus.
• Etape 2 : Sélectionner les individus à utiliser pour construire la population fille.
• Etape 3 : Effectuer une recombinaison des individus sélectionnés à l’aide des opérateurs de croisement et de mutation.
• Etape 4 : Evaluer les nouveaux individus et établir la population fille.
• Etape 5 : Recommencer à l’étape 2 tant que la condition d’arrêt n’est pas remplie.