Algorithmes Génétiques - Uqtr

Algorithmes Génétiques
Marc-Olivier LaBarre Mai-Août 2002 Les algorithmes génétiques sont une méthode d'optimisation utile dans les
cas non linéaires (évidemment, cette méthode fonctionne également pour les
cas linéaires, mais dans ce cas, est inutilement lourde en temps et en
calcul). Cette technique part du principe évolutif de la sélection
naturelle de Darwin. Celle-ci énonçait que les individus les plus aptes à
survivre (les « meilleurs ») se reproduiront plus souvent et auront plus de
descendants. Ainsi, la qualité du pool génétique de la population sera
augmentée, les gènes plus efficaces deviendront plus fréquent; la
population s'améliore. Selon le même principe, un algorithme génétique
part d'une population de solutions initiales, les fait se reproduire (les
meilleures solutions ont plus de chances de se reproduire), créant ainsi la
nouvelle génération de solutions. En répétant ce cycle plusieurs fois, on
obtient une population composée de solutions meilleures. On utilise
généralement les algorithmes génétiques pour trouver une solution, la
meilleure solution après un certain nombre de générations. Voici le corps principal d'une itération d'un algorithme génétique :
1- Évaluer la qualité (fitness) des individus et leurs chances de survie
2- Sélectionner les individus pour la reproduction
3- Effectuer la reproduction
4- Remplacer l'ancienne population par la nouvelle Cette itération est répétée autant de fois que demandé. L'évaluation de la
qualité (fitness) d'un individu permet d'illustrer avec une valeur
numérique (et donc plus facile à manipuler) la qualité des gènes qui
forment l'individu. Plus la qualité d'un individu est grande, plus ses
chances d'être sélectionné pour la reproduction sont grandes. En général,
on calcule les chances de reproduction d'un individu en regard de sa
qualité en relation avec la qualité totale des individus de la population.
La reproduction se fait en croisant deux individus. On applique sur les
deux individus choisis des opérateurs génériques, habituellement
l'enjambement (cross-over) et la mutation. La reproduction donne deux
enfants (offspring), qui sont placés dans la nouvelle population. On
répète la reproduction jusqu'à ce qu'on ait rempli la nouvelle population
(la taille de la population devrait rester constante). On remplace alors
l'ancienne population par la nouvelle, et on recommence le processus le
nombre de générations voulu. Voici un algorithme plus détaillé d'un algorithme génétique :
Algorithme génétique générique
1- Générer une population de individus de taille N : x1, x2, x3,..., xN.
2- Calculer les chances de survie (qualité ou encore fitness) de chaque
individu. f(x1), f(x2), f(x3), ..., f(xN).
3- Vérifier si le critère de terminaison est atteint. Si oui, terminer.
4- Choisir une paire d'individus pour la reproduction (selon les chances
de survie de chaque individu).
5- Selon les probabilités associées à chaque opérateur génétique,
appliquer ces opérateurs.
6- Placer les individus produits dans la nouvelle population.
7- Vérifier si la taille de la nouvelle population est correcte. Si
non, retourner à l'étape 4.
8- Remplacer l'ancienne population d'individus par la nouvelle.
9- Retourner à l'étape 2. Notez que cet algorithme génétique générique est plutôt « vide ». Il
s'agit d'un modèle très général. Nous verrons un exemple plus concret plus
tard. EXPLICATIONS DES ÉLÉMENTS D'UN ALGORITHME GÉNÉTIQUE Individu :
Les individus correspondent aux « solutions » du problème à optimiser. Ces
solutions doivent être « codées » pour que le traitement puisse être
effectué par l'algorithme génétique. Cette représentation codée d'une
solution est appelée chromosome, et est composée de gènes. Chaque gène
peut représenter une variable, un élément de la solution, ou encore une
partie plus abstraite. La manière la plus utilisée de codage par
algorithme génétique est le codage en vecteurs. Chaque solution est
représentée par un vecteur. Ce vecteur peut être binaire ou encore de
n'importe quel type discret dénombrable (entier, caractères, etc.). On
pourrait également utiliser un type continu (ex : nombres réels), mais dans
ce cas, il faut également revoir les opérations qui modifient le contenu
des chromosomes (la fonction qui crée aléatoirement les chromosomes et les
opérateurs génétiques). La simplicité veut que les chromosomes soient
uniformes, c'est-à-dire que tous les gènes sont du même type. Cependant,
si on tient compte encore une fois des opérations qui modifient le contenu
des chromosomes, on peut assez aisément construire des vecteurs d'éléments
de type différents. On demande habituellement que les chromosomes soient
tous de même longueur, basés sur la même architecture, les gènes homologues
étant au même endroit sur leur chromosome respectif. De fait, le codage
par vecteur est si utilisé (très grande simplicité comparée aux autres
méthodes de codage de chromosome) que les algorithmes sont souvent
identifiés comme étant des méthodes de traitement vectoriel. Cette
affirmation n'est pas tout a fait vraie car d'autres types de codage
existent, bien que n'étant pas très fréquents. Par exemple, l'utilisation
des algorithmes génétiques pour faire de la programmation génétique utilise
un codage en arbre (ce qui permet entre autres d'avoir des chromosomes de
longueurs différentes). Population :
C'est l'ensemble des individus, ou encore l'ensemble des chromosomes d'une
même génération. Habituellement, la taille de la population reste
constante tout au long de l'algorithme génétique. Générer :
Habituellement, au départ d'un algorithme génétique, il faut créer une
population d'individus. Ces individus sont générés par une fonction
simple. Cette fonction affecte à chaque individu qu'elle crée une valeur
aléatoire pour chacun de ses gènes. L'algorithme génétique peut également
utiliser comme population de départ une population déjà créée a priori. Qualité, fitness, d'un individu :
Le calcul de la qualité d'un individu est essentiel aux algorithmes
génétiques. Cette fonction donne, en valeur numérique (habituellement
réelle), la qualité d'un individu. C'est selon cette valeur numérique
qu'est calculée les chances de sélection de cet individu. La fonction de
fitness doit avoir 0 comme plancher, pour ne pas fausser le calcul des
pourcentages. Les algorithmes génétiques étant une technique
d'optimisation, ils cherchent la qualité maximale, donc l'optimisation de
la fonction de qualité. Si on cherche plutôt à minimiser une fonction, il
faudra la modifier de sorte que la fonction de qualité se maximise. Il
serait bien entendu possible de conserver un fonction de qualité qui
fonctionne à l'envers et de modifie à la place le calcul des probabilités,
mais ceci rendrait l'algorithme beaucoup plus difficile à décoder pour les
utilisateurs externes. Sélection :
Selon la qualité des individus, chacun se voit attribuer un pourcentage de
chances d'être choisi pour la reproduction, qui correspond à l'importance
relative de la qualité de l'individu par rapport à la qualité totale de la
population. Reproduction :
La reproduction s'effectue généralement en croisant deux individus, ce qui
produit deux nouveaux individus à placer dans la nouvelle population. De
la manière classique, la reproduction consiste à appliquer les opérateurs
génétiques sur les deux chromosomes sélectionnés et mettre les deux
chromosomes résultant dans la nouvelle population. Les deux opérateurs
génétiques courants sont l'enjambement (cross-over) et la mutation. Le
premier est la véritable reproduction. Chaque chromosome enfant reçoit
environ la moitié des gènes de chacun de ses parents. La probabilité
d'enjambement est presque toujours de 50% (effectue de cette manière un
mélange plus efficace). Selon cette probabilité, on échange les gènes
homologues des deux chromosomes. De cette façon, après l'enjambement, on
obtient deux enfants qui sont complémentaires par rapport à leurs parents
(si un enfant a un gène d'un tel parent, l'autre enfant tiendra ce même
gène de l'autre parent). L'opérateur de mutation, bien qu'ayant une
probabilité bien moindre (habituellement entre 0,5% et 5%) joue un rôle
très important. Une reproduction utilisant uniquement l'enjambement est
une méthode de hill-climbing, méthode qui est limitée par l'atteinte de
maxima locaux. En effet, les gènes des enfants sont limités par les gènes
des parents, et si un gène n'est pas présent dans la population initiale
(ou s'il disparaît à cause des reproductions), il ne pourra jamais se
développer chez les descendants. L'opérateur de mutation est là pour
contourner ce problème. Chaque gène possède une faible probabilité de
muter, c'est-à-dire d'être aléatoirement remplacé par une autre incarnation
de ce gène. Cette précaution permet de conserver ce qu'on appelle la
diversité génétique. Habituellement, la mutation crée des individus
faibles, peu aptes à survivre. Cependant, un certaine mutation pourrait se
révéler « géniale » et permet d'augmenter grandement l'évolution de la
population. Ces opérateurs génétiques peuvent habituellement s'accommoder
de la plupart des situations sans trop de modifications. Toutefois, afin
de conserver la cohérence des individus, on doit parfois modifier
grandement, voire changer totalement les opérateurs génétiques. Il n'y a
pas de limite quant au nombre d'opérateurs