Les Algorithmes Génétiques

~ 1 ~

I. Introduction :

Les algorithmes génétiques appartiennent à la famille des algorithmes

évolutionnistes. Leur but est d'obtenir une solution approchée à un problème d'optimisation,

lorsqu'il n'existe pas de méthode exacte (ou que la solution est inconnue) pour le résoudre en

un temps raisonnable. Les algorithmes génétiques utilisent la notion de sélection naturelle et

l'appliquent à une population de solutions potentielles au problème donné. La solution est

approchée par « bonds » successifs, comme dans une procédure de séparation et évaluation, à

ceci près que ce sont des formules qui sont recherchées et non plus directement des valeurs.

II. Définition :

Inventés par John Holland, puis développés par David Goldberg, les algorithmes

génétiques ont gagné une renommée certaine. Ils utilisent une représentation génotypique

binaire en chaînes de bit de longueur fixe qui représentent les solutions du problème. Au

cours des générations, les individus sont sélectionnés par tirage à la roulette, donnant une plus

grande probabilité aux individus les plus adaptés à être sélectionnés ; ceux-là sont ensuite

croisés entre eux, par un croisement en un point, puis les nouveaux individus sont mutés avec

une petite probabilité par une mutation d’un bit [Holland, 75]. Il est intéressant de noter que

les algorithmes génétiques originaux n’intégraient pas la notion d’élitisme; toute la population

était remplacée par les enfants [Goldberg, 94].

Figure : Schéma résumant le fonctionnement des AG

Les Algorithmes Génétiques

~ 2 ~

III. Codage ou représentation :

Chaque paramètre d'une solution est assimilé à un gène, toutes les valeurs qu'il peut

prendre sont les allèles de ce gène, on doit trouver une manière de coder chaque allèle

différent de façon unique (établir une bijection entre l'allèle "réel" et sa représentation codée).

Un chromosome est une suite de gêne, on peut par exemple choisir de regrouper les

paramètres similaires dans un même chromosome (chromosome à un seul brin) et chaque

gène sera repérable par sa position : son locus sur le chromosome en question.

Chaque individu est représenté par un ensemble de chromosomes, et une population est un

ensemble d'individus.

Figure : Les cinq niveaux d’organisation de notre algorithme génétique.

• Codage binaire :

Ce type de codage est certainement le plus utilisé car il présente plusieurs avantages. Son

principe est de coder la solution selon une chaîne de bits (qui peuvent prendre les valeurs 0 ou

1).

• Codage à caractères multiples :

Une autre manière de coder les chromosomes d'un algorithme génétique est donc le codage à

l'aide de caractères multiples (par opposition aux bits). Souvent, ce type de codage est plus

naturel que celui énoncé ci-avant. C'est d'ailleurs celui-ci qui est utilisé dans de nombreux cas

poussés d'algorithmes génétiques que nous présenterons par la suite.

Les Algorithmes Génétiques

~ 3 ~

• Codage sous forme d'arbre :

Ce codage utilise une structure arborescente avec une racine de laquelle peuvent être issus un

ou plusieurs fils. Un de leurs avantages est qu'ils peuvent être utilisés dans le cas de

problèmes où les solutions n'ont pas une taille finie [Ritche,03].

IV. Les opérateurs de variation :

• Les sélections :

Pour déterminer quels individus sont plus enclins à obtenir les meilleurs résultats, une sélection

est opérée. Ce processus est analogue à un processus de sélection naturelle, les individus les

plus adaptés gagnent la compétition de la reproduction tandis que les moins adaptés meurent

avant la reproduction, ce qui améliore globalement l'adaptation.

• Le croisement :

Une fois certains individus sélectionnés, on les fait se reproduire entre eux, pour cela on

utilise l'opérateur croisement. C'est l'opérateur essentiel de recherche d'un algorithme

génétique. Il combine les génotypes de deux individus pour en obtenir deux nouveaux. Avec

cet opérateur, les génotypes sont vus comme une chaîne de nombres binaires. Plusieurs

méthodes de croisement sont utilisées:[Dejong et al, 92]

• Croisement en un point:

On choisit au hasard un point de coupure identique sur les deux génotypes et on

échange les fragments situés après le point de coupure pour donner les deux nouveaux

génotypes.

• Croisement en deux points:

On choisit au hasard deux points de croisement et on échange les fragments situés

entre ces deux points.

• Croisement en k points:

Généralisation à k points de coupure des méthodes précédentes.

• Croisement uniforme:

Il peut être vu comme un croisement multipoints dont le nombre de points de coupure

n'est pas connu a priori. En pratique on utilise un masque binaire de la même longueur

que les génotypes. Si à la nième position, il y a un 0, on conserve les symboles sinon

on les échanges. Le masque est généré aléatoirement pour chaque couple.

Les Algorithmes Génétiques

~ 4 ~

• La mutation :

De façon aléatoire, un gène peut, au sein d'un chromosome être substitué à un

autre. De la même manière que pour les enjambements, on définit ici un taux de

mutation lors des changements de population qui est généralement compris entre

0,001 et 0,01. Il est nécessaire de choisir pour ce taux une valeur relativement faible

de manière à ne pas tomber dans une recherche aléatoire et conserver le principe de

sélection et d'évolution. La mutation sert à éviter une convergence prématurée de

l'algorithme. Par exemple lors d'une recherche d'extremum la mutation sert à éviter la

convergence vers un extremum local .

V. Sélection et remplacement :

Cet opérateur est chargé de définir quels seront les individus de P qui vont être

dupliqués dans la nouvelle population P' et vont servir de parents (application de l'opérateur

de croisement).

Soit n le nombre d'individus de P, on doit en sélectionner n/2 (l'opérateur de

croisement nous permet de repasser à n individus).

Cet opérateur est peut-être le plus important puisqu’il permet aux individus d’une

population de survivre, de se reproduire ou de mourir. En règle générale, la probabilité de

survie d’un individu sera directement reliée à son efficacité relative au sein de la population

[Spalanzani, 99].

On trouve essentiellement quatre types de méthodes de sélection différentes :

• La méthode de la "loterie biaisée" (roulette wheel) de GoldBerg,

• La méthode "élitiste",

• La sélection par tournois,

• La sélection universelle stochastique.

• La loterie biaisée ou roulette wheel :

Cette méthode est la plus connue et la plus utilisée.

Avec cette méthode chaque individu a une chance d'être sélectionné proportionnelle à sa

performance, donc plus les individus sont adaptés au problème, plus ils ont de chances d'être

sélectionnés.

Les Algorithmes Génétiques

~ 5 ~

Pour utiliser l'image de la "roue du forain", chaque individu se voit attribué un secteur dont

l'angle est proportionnel à son adaptation, sa "fitness".

On fait tourner la roue et quand elle cesse de tourner on sélectionne l'individu correspondant

au secteur désigné par une sorte de "curseur", curseur qui pointe sur un secteur particulier de

celle-ci après qu'elle se soit arrêté de tourner.

Figure : la méthode de sélection de la loterie biaisée

• La méthode élitiste :

Cette méthode consiste à sélectionner les n individus dont on a besoin pour la nouvelle

génération P' en prenant les n meilleurs individus de la population P après l'avoir triée de

manière décroissante selon la fitness de ses individus.

Il est inutile de préciser que cette méthode est encore pire que celle de la loterie biaisée dans

le sens où elle amènera à une convergence prématurée encore plus rapidement et surtout de

manière encore plus sûre que la méthode de sélection de la loterie biaisée ; en effet, la

pression de la sélection est trop forte, la variance nulle et la diversité inexistante, du moins le

peu de diversité qu'il pourrait y avoir ne résultera pas de la sélection mais plutôt du

croisement et des mutations.

Là aussi il faut opter pour une autre méthode de sélection.

Les Algorithmes Génétiques

~ 6 ~

• La sélection par tournois :

Cette méthode est celle avec laquelle on obtient les résultats les plus satisfaisants.

Le principe de cette méthode est le suivant : on effectue un tirage avec remise de deux

individus de P, et on les fait "combattre". Celui qui a la fitness la plus élevée l'emporte avec

une probabilité p comprise entre 0.5 et 1. On répète ce processus n fois de manière à obtenir

les n individus de P' qui serviront de parents.

La variance de cette méthode est élevée et le fait d'augmenter ou de diminuer la valeur de p

permet respectivement de diminuer ou d'augmenter la pression de la sélection.

• La sélection universelle stochastique :

Cette méthode semble être très peu utilisée et qui plus est possède une variance faible, donc

introduit peu de diversité, nous n'entrerons donc pas dans les détails, on se contentera

d'exposer sa mise en œuvre :

On prend l'image d'un segment découpé en autant de sous-segments qu'il y a d'individus. Les

individus sélectionnés sont désignés par un ensemble de points équidistants.

VI. Algorithme : algorithmes génétiques

Début

1. Générer une population aléatoire de n chromosomes.

2. Evaluer la fitness des chromosomes avec la fonction f(x)

3. Répéter

4. appliquer l'opération de sélection

5. Appliquer l'opération de croisement avec une probabilité pc

6. Appliquer l'opération de mutation avec une probabilité pm

7. Ajouter les nouveaux chromosomes à la nouvelle population

8. Calculer la fonction fitness f(x), pour tout chromosome x

9. appliquer l'opération de remplacement

10. Jusqu’à la satisfaction des conditions de terminaison

FIN

• Définition :

On appelle adaptation d'une séquence A une valeur positive que nous noterons f(A).

f est la fonction objectif ou fitness du problème à résoudre.

Les Algorithmes Génétiques

~ 7 ~

Un critère permettant de déterminer l'adaptation d'un individu par rapport à

l'environnement afin de classer les individus entre eux. Dans le vocabulaire des

algorithmes génétiques, on dénomme par "fitness" (traduction anglaise du mot

adaptation) le critère à optimiser.

Figure : représentation de la fitness des individus.

La surface représente la fitness des individus dans un endroit de l’espace, les pics

figurent les individus les mieux adaptés à leur environnement. L’objectif est de

rapprocher les individus des pics.

VII. Avantages et Inconvénients :

Avantages :

• élimination de solutions non valides.

• Permet de traiter des espaces de recherche important (beaucoup de solutions, pas de

parcourt exhaustif envisagé).

• Nombre de solutions important.

• Relativité de la qualité de la solution selon le degré de précision demandé.

Inconvénients :

• Nécessitent plus de calculs que les autres algorithmes méta heuristiques (notamment la

fonction évaluation).

• Paramètres difficiles à fixer (taille population, % mutation).

• Choix de la fonction d’évaluation délicat.

Les Algorithmes Génétiques

~ 8 ~

• Pas assuré que la solution trouvée est la meilleure, mais juste une approximation de

la solution optimale.

• Problèmes des optimums locaux si paramètres mal évalués.

VIII. Domaine d’application :

Les applications des algorithmes génétiques sont multiples : optimisation de fonctions

numériques difficiles, traitement d’image, optimisation d’emplois du temps, contrôle de

systèmes industriels [Beasley, 1993a], cryptographie, apprentissage des réseaux de neurones

[Renders, 1995], etc.

IX. Exemple :

Cet exemple est dû à Goldberg (1989). Il consiste à trouver le maximum de la fonction

f(x) = x sur l'intervalle [0, 31] où x est un entier naturel.

On a 32 valeurs possibles pour x on choisit donc un codage discret sur 5 bits : on

obtient donc la séquence 0,1,1,0,1 pour 13, la séquence 1,1,0,0,1 pour 25, etc...

On initialise la population initiale de manière aléatoire et on fixe sa taille à 4

individus. On définit simplement la fitness comme étant la valeur de x, vu qu'on en

cherche la valeur maximum sur l'intervalle [0, 31] plus la valeur de x sera élevée plus

on se rapprochera du maximum de la fonction identité et donc plus la fitness sera

grande. Soit la population initiale suivante :

Figure : la population initiale

Les Algorithmes Génétiques

~ 9 ~

On opte pour une sélection par la méthode la loterie biaisée :

Figure: application de la méthode de sélection de la loterie biaisée sur la population

On fait tourner la roue 4 fois de suite, en général on fait tourner n / 2 fois, soit 2 fois dans ce

cas, mais le nombre 2 étant trop petit on décide de la faire tourner 4 fois. On obtient la

nouvelle population :

Figure: individus sélectionnés par la méthode de la loterie biaisée

On applique l'opérateur de croisement en utilisant un seul point de crossover. Normalement

chaque couple donne 2 enfants qu'on ajoute à notre nouvelle population P' la faisant passer de

n / 2 individus à n individu, mais vu que dans le cas de notre exemple nous avons déjà atteint

nos n individus, les 2 enfants du couple remplaceront leurs parents.

Deux couples sont formés de manière aléatoire :

• couple 1 : l'individu 2 avec l'individu 3

• couple 2 : l'individu 1 avec l'individu 4.

Les point de crossover sont eux aussi tirer au hasard.

On obtient le résultat suivant :

Les Algorithmes Génétiques

~ 10 ~

Figure : résultat de l'application de l'opérateur de croisement avec un point de crossover sur les individus sélectionnés par la loterie biaisée

On applique l'opérateur de mutation qui choisit de manière aléatoire si on doit faire une

mutation et sur quel locus la faire :

Figure : la nouvelle population après application des différents opérateurs

En une seule génération le maximum est passé de 24 à 27, et la fitness globale de la

population a relativement augmentée pour passer de 59 à 71. On s'arrête ici pour cet exemple

mais dans la réalité on continuera à engendrer des générations successives jusqu'à obtenir le

maximum global : 31.

X. Conclusion :

Les algorithmes génétiques fournissent des solutions proches de la solution optimale à

l'aide des mécanismes de sélection, d'hybridation et de mutation. Ils sont applicables à de

nombreux problèmes, dont le problème du voyageur de commerce.

Les Algorithmes Génétiques

~ 11 ~

Bibliographie :

[Holland,75] :J.H.Holland, »Adaptation In Natural And Artificial Systems »,Uiversity of

Michigan Press,1975.

[Spalanzani,99]: A.Spalanzani ,”Algorithmes évolutionnaires pour l’étude de la robustesse

des Systèmes de reconnaissance automatique de la parole», thèse de doctorat, Université

Joseph Fourier- Grenoble ,France28Octobre 1999.

[Dejong et al,92]: Dejong K.A. and W.M.Spears,”Aformel analysis of the role of multi-point

crossover in genetic algorithms”. Annals of Mathematics and Artificial Intelligence

Journal,pp:1-26,1992.

L'ordinateur génétique. Paris. Hermès, 1996. (Dessales.J-L).

Algorithmes génétiques, exploration, optimisation et apprentissage automatique. Paris 1994.

(Goldberg D.E).

conception et réalisation d'un système de clustering basé sure les algorithmes génétiques

USTHB.

D. Goldberg, Algorithmes génétiques, Addison–Wesley France (1994).