Algorithme Génétique

Introduction
Les algorithmes génétiques ont été créés par J.H. Holland pour mimer les processus observés
dans l'évolution des espèces. Librement inspirés des théories de Darwin, les algorithmes
génétiques reproduisent les processus de sélection au sein des espèces en fonction de leur
environnement.

Les individus favorisés par leurs particularités seront également favorisés dans le processus de
reproduction et transmettront tout ou partie de leur patrimoine génétique à leurs enfants. C’est
la sélection naturelle.

Ainsi sélectionnés au fil des générations, les individus seront plus adaptés à leur
environnement car bénéficiant d’un patrimoine génétique plus approprié, hérité de seulement
quelques aïeux plusieurs générations auparavant.

Le mécanisme des algorithmes évolutionnistes consiste donc à faire évoluer une population de
solutions (les chromosomes ou les individus) toutes plus ou moins bonnes ou mauvaises et à
diriger l’évolution de la population en fonction d’un ou plusieurs objectifs à atteindre sous un
ensemble de contraintes de résolution, pour que les solutions engendrées soient plus adaptées
au problème.

La notion évolutionniste ou génétique d’un algorithme est bien évidemment métaphorique.

Imitant le processus naturel de l’évolution d’une population, un algorithme génétique (AG) en
reprend ses lignes directrices pour adapter un ensemble de solutions de manière optimale à
l’environnement.

Les particularités des algorithmes génétiques sont [GOL 89a]:

 Ils utilisent un codage des paramètres et non pas les paramètres eux-mêmes.
 Ils travaillent sur une population de points au lieu d’un point unique.
 Ils n’utilisent que la valeur de la fonction étudiée et non sa dérivée ou une autre
connaissance auxiliaire.
Principe de l’algorithme génétique

1) Initialisation
Au début, de nombreuses solutions individuelles sont générées de manière aléatoire pour
former une population initiale. La taille de la population dépend de la nature du problème,
mais contient généralement plusieurs centaines voire milliers de solutions possibles.
Traditionnellement, la population est générée de manière aléatoire, couvrant l'ensemble de la
plage de solutions possibles (l'espace de recherche). De temps en temps, les solutions peuvent
être "semées" dans des zones où les solutions optimales sont susceptibles d'être trouvées.

2) Evaluation
Chaque solution individuelle dans la population est évaluée en fonction de sa performance par
rapport au problème à résoudre. Cette évaluation est effectuée à l'aide d'une fonction de
fitness qui mesure la qualité de chaque solution. Plus la valeur de fitness est élevée, meilleure
est la solution.

3) Sélection
Pendant chaque génération successive, une proportion de la population existante est
sélectionnée pour engendrer une nouvelle génération. Les solutions individuelles sont
sélectionnées grâce à un processus basé sur la condition physique, où les solutions les plus
adaptées (telles que mesurées par une fonction de condition physique) ont généralement plus
de chances d'être sélectionnées. Certains méthodes de sélection évaluent la condition physique
de chaque solution et sélectionnent préférentiellement les meilleures solutions. D'autres
méthodes n'évaluent qu'un échantillon aléatoire de la population, car ce processus peut être
très long.

La plupart des fonctions sont stochastiques et conçues de sorte qu'une petite proportion de
solutions moins adaptées soit sélectionnée. Cela contribue à maintenir une grande diversité au
sein de la population, évitant ainsi une convergence prématurée vers des solutions médiocres.
Les méthodes de sélection populaires et bien étudiées comprennent la sélection par la roulette
et la sélection par tournoi.

4) Reproduction
La prochaine étape consiste à générer une deuxième génération de solutions à partir de celles
sélectionnées par les opérateurs génétiques : le croisement (également appelé recombinaison)
et/ou la mutation. Pour chaque nouvelle solution à produire, une paire de solutions "parentes"
est sélectionnée pour la reproduction à partir du pool sélectionné précédemment. En
produisant une solution "enfant" en utilisant les méthodes de croisement et de mutation
mentionnées ci-dessus, une nouvelle solution est créée qui partage généralement de
nombreuses caractéristiques avec ses "parents". De nouveaux parents sont sélectionnés pour
chaque nouvel enfant, et le processus se poursuit jusqu'à ce qu'une nouvelle population de
solutions de taille appropriée soit générée. Bien que les méthodes de reproduction basées sur
l'utilisation de deux parents soient plus "inspirées de la biologie", certaines recherches
suggèrent qu'il est préférable d'utiliser plus de deux "parents" pour reproduire un chromosome
de bonne qualité.

Ces processus aboutissent finalement à la génération suivante de chromosomes qui est

différente de la génération initiale. En général, la condition physique moyenne aura augmenté
grâce à cette procédure pour la population, puisque seules les meilleures solutions ou
algorithmes génétiques de la première génération sont sélectionnés pour la reproduction, ainsi
qu'une petite proportion de solutions moins adaptées, pour les raisons déjà mentionnées ci-
dessus.

5) Terminaison
Ce processus générationnel est répété jusqu'à ce qu'une condition de terminaison soit atteinte.
Les conditions de terminaison courantes sont :

Une solution est trouvée qui satisfait des critères minimaux ;

 Un nombre fixe de générations est atteint ;

 Le budget alloué (temps de calcul/argent) est atteint ;
 La condition physique de la solution la mieux classée atteint un plateau tel que les
itérations successives ne produisent plus de meilleurs résultats ;
 Inspection manuelle ;
 Combinaisons des éléments qui précède.

Pseudocodes simples de l'algorithme génétique :

1. Choisissez la population initiale d'individus.

2. Évaluez la condition physique de chaque individu dans cette population.

3. Répétez cette génération jusqu'à la terminaison : a. Sélectionnez les individus les mieux
adaptés pour la reproduction.

b. Faites se reproduire de nouveaux individus grâce à des opérations de croisement et de

mutation pour donner naissance à une progéniture.

c. Évaluez la condition physique individuelle des nouveaux individus.

d. Remplacez la population la moins adaptée par de nouveaux individus.

 Récapitulatif :

Figure1 : Algorithme génétique Standard

Les opérateurs d’évolution dans les algorithmes génétiques
Pour utiliser les AG, la première chose à se demander est "Comment décrire un individu?
C'est à dire, comment les paramètres peuvent se coder?

La réponse à cette question a une influence forte sur l'implémentation des mécanismes de
croisement et de mutation. Un gène correspond de fait à un paramètre et un seul xi, Un
chromosome est constitué par un ensemble de gènes et décrit complètement un individu.
L'ensemble des individus est appelé population. On aboutit ainsi à une structure présentant
quatre niveaux d'organisation (fig. 2) Un chromosome est une concaténation des gènes (fig. 3)

Figure2 : Les quatres niveaux Figure3 : Illustration du codage des variables

d’optimisation. d’organisations des AG.

Après avoir compris la manière dont les individus seront représentés et les paramètres codés,
nous pouvons explorer les différents opérateurs d'évolution.
 1) Sélection

La sélection consiste à choisir les individus les mieux adaptés afin d'avoir une population de
solution la plus proche de converger vers l'optimum global.
Cet opérateur est l'application du principe d'adaptation de la théorie de Darwin.

Il existe plusieurs techniques de sélection. Voici les principales utilisées :

 Sélection par rang : Cette technique de sélection choisit toujours les individus
possédant les meilleurs scores d'adaptation.

 Probabilité de sélection proportionnelle à l'adaptation : Technique de la roulette

ou roue de la fortune, pour chaque individu, la probabilité d'être sélectionné est
proportionnelle à son adaptation au problème.

 Sélection par tournoi : Cette technique utilise la sélection proportionnelle sur des
paires d'individus, puis choisit parmi ces paires l'individu qui a le meilleur score
d'adaptation.

 Sélection uniforme : La sélection se fait aléatoirement, uniformément et sans

intervention de la valeur d'adaptation.

Voici un exemple avec des individus en représentation binaire une fois la sélection effectuée :

On réalise ensuite un croisement entre deux chromosomes parmi la population restante.

2) Croisement
Le croisement, ou enjambement, crossing-over, est le résultat obtenue lorsque deux
chromosomes partage leurs particularités.
Celui-ci permet le brassage génétique de la population et l'application du principe d’hérédité
de la théorie de Darwin.

Il existe deux méthodes de croissement : simple ou double enjambement.

Le simple enjambement consiste à fusionner les particularités de deux individus à partir d'un
pivot, afin d'obtenir un ou deux enfants :

Le double enjambement repose sur le même principe, sauf qu'il y a deux pivots :

On réalise ensuite une mutation sur les enfants obtenues lors du croisement.

3) Mutation
La mutation consiste à altérer un gène dans un chromosome selon un facteur de mutation. Ce
facteur est la probabilité qu'une mutation soit effectuée sur un individu.

Cet opérateur est l'application du principe de variation de la théorie de Darwin et permet, par
la même occasion, d'éviter une convergence prématurée de l'algorithme vers un extremum
local.

Voici un exemple de mutation sur un individu ayant un seul chromosome :

Avec ces trois opérateurs d'évolution, nous pouvons appliquer les algorithmes génétiques.