Algorithmes génétiques

Introduction aux algorithmes génétiques

Les algorithmes génétiques sont des algorithmes d'optimisation s'appuyant sur des techniques dérivées de la génétique et des mécanismes d'évolution de la nature : croisements, mutations, sélections, etc... Ils appartiennent á la classe des algorithmes évolutionnaires.

Historique

1860

Charles Darwin publie son livre intitulé L'origine des espèces au moyen de la sélection naturelle ou la lutte pour l'existence dans la nature. Dans ce livre, Darwin rejete l'existence «de systèmes naturels figés», déjà adaptés pour toujours à toutes les conditions extérieures, et expose sa théorie de l'évolution des espèces : sous l'influence des contraintes extérieurs, les êtres vivants se sont graduellement adaptés à leur milieu naturel au travers de processus de reproductions.

20ième siècle

Mise en évidence de l'existence de mutations génétiques. Les problèmes de traitement de l'information sont résolus de manières figés : lors de sa phase de conception, le système reçoit toutes les caractéristiques nécessaires pour les conditions d'exploitations connues au moment de sa conception ce qui empêche une adaptation à des conditions d'environnement inconnues, variables ou évolutives. Les chercheurs en informatique étudient donc des méthodes pour permettrent aux systèmes d'évoluer spontanément en fonction de nouvelles conditions.

1966

Programmation évolutionnaire L. J. Fogel.

1973

Stratégie d'évolution I. Rechenberg.

1975

Dans les années 1960, John Holland étudient les systémes évolutifs et, en 1975, il introduit le premier modèle formel des algorithmes génétiques (the canonical genetic algorithm AGC) dans son livre Adaptation in Natural and Artificial Systems. Ce modèle servira de base aux recherches ultèrieures.

1989

David Goldberg publie un ouvrage de vulgarisation des algorithmes génétiques.

années 1990

Programmation d'une panoplie d'algorithmes génétiques trancris en C++, appelée GAlib. Cette librairie contient des outils pour des problèmes d'optimisation en utilisant les AG. Elle est conçue pour servir de support de programmation.

Principes

But

Le but des AG est de déterminer les extrêmes d'une fonction $f~:~X\mapsto~\mathbb{R}$, où $X$ est un ensemble quelconque appelé espace de recherche et $f$ est appelée fonction d'adaptation ou fonction d'évaluation ou encore fonction fitness. La fonction agit comme une «boite noire»pour l'AG. Aussi des problèmes très complexes peuvent être approchés par programmation génétique sans avoir de compréhension particulière du problème.

Codage d'une population

Le premier pas dans l'implantation des algorithmes génétiques est de créer une population d'individus initiaux. En effet, les algorithmes génétiques agissent sur une population d'individus, et non pas sur un individu isolé. Par analogie avec la biologie, chaque individu de la population est codé par un chromosome ou génotype (Holland, 1975). Une population est donc un ensemble de chromosomes. Chaque chromosome code un point de l'espace de recherche. L'efficacité de l'algorithme génétique va donc dépendre du choix du codage d'un chromosome.

Dans l'algorithme canonique de Holland (AGC), un chromosome était représenté sous forme de chaînes de bits contenant toute l'information nécessaire à la description d'un point dans l'espace ce qui permettait des opérateurs de mutations et de croisements simples (voir 2.3.5). L'inconvénient, c'est que deux individus voisins en terme de distance de Hamming ne codent pas nécessairement des éléments proches dans l'espace de recherche. La solution est d'utiliser un code de Gray.

Pour le PVC, un chromosome représente un élément de l'espace de recherche, c'est-à-dire un chemin possible pour le commis voyageur. Une population est donc un ensemble de chemin. Chaque ville est représentée par un point de l'espace physique et porte un numéro d'identité différent. Un chemin étant une suite de villes, un chromosome est une suite de nombres.

Fonction d'évaluation et fonction fitness

Pour calculer le coût d'un point de l'espace de recherche, on utilise une fonction d'évaluation. L'évaluation d'un individu ne dépendant pas de celle des autres individus, le résultat fournit par la fonction d'évaluation va permettre de sélectionner ou de refuser un individu pour ne garder que les individus ayant le meilleur coût en fonction de la population courante : c'est le rôle de la fonction fitness. Cette méthode permet de s'assurer que les individus performants seront conservés, alors que les individus peu adaptés seront progressivement éliminés de la population.

Par exemple, pour le PVC, la fonction d'évaluation utilisée calcule la distance parcourue par le commis voyageur pour un chemin donné.

Dans l'AGC de Holland, la fonction fitness est définit par : $f_i/\overline{f}$ où $f_i$ est la fonction d'évaluation de l'individu $i$ et $\overline{f}$ est la fonction moyenne des évaluations de toutes les chaînes de bits de la population. Cependant, en général, on ne fait pas la différence entre fonction fitness et fonction d'évaluation.

L'hybridation ( ou crossover )

A partir de deux individus, on obtient deux nouveaux individus (enfants) qui héritent de certaines caractéristiques de leurs parents. L'hybridation sélectionnne des gènes parmis deux individus appelés parents. A partir de ces gènes sont générés les enfants. La probabilité d'hybridation représente la fréquence à laquelle les hybridations sont appliquées.

• S'il n'y a pas d'hybridation, les fils sont l'exacte copie des parents.
• S'il y a hybridation, les fils sont composés d'une partie de chacun de leur parents.
• Si la probalitité est de 0%, la nouvelle génération est la copie de la précédente.
• Si la probabilité est fixée à 100%, tous les descendants sont générés par hybridation.

L'hybridation est mis en place pour que les nouveaux chromosomes gardent la meilleur partie des chromosomes anciens. Ceci dans le but d'obtenir, peut-être, de meilleurs chromosomes. Néanmoins, il est quand même important qu'une partie de la population survive à la nouvelle génération ( voir sélection par steady-state section 2.4.3)

La mutation

La mutation génère des «erreurs»de recopie, afin de créer un nouvel individu qui n'existait pas auparavant. Le but est d'éviter à l'AG de converger vers des extrema locaux de la fonction et de permettre de créer des éléments originaux. Si elle génère un individu plus faible l'individu est éliminé. La probabilité de mutation représente la fréquence à laquelle les gènes d'un chromosome sont mutés.

• S'il n'y a pas de mutation, le fils est inséré dans la nouvelle population sans changement.
• Si la mutation est appliquée, une partie du chromosome est changée.

La mutation est prévue pour éviter au AG de s'enliser dans des optima locaux. Mais si elle est trop fréquente, le AG est orienté vers une recherche aléatoire de la bonne solution.

Itération

A partir d'une population initiale de $m$ individus, l'AG sélectionne une population intermédiaire de $m$ individus en faisant une sélection sur la population initiale ( un même individu peut être sélectionné plusieurs fois ou peut ne pas être sélectionné du tout, en fonction de la valeur de sa fonction d'évaluation). Les $m$ individus de la population se croisent deux à deux (les couples se forment aléatoirement) pour construire $m$ nouveaux individus. Ces individus passent par un opérateur de mutation (qui agit aléatoirement avec une possibilité faible 2-3% de bits) pour former une nouvelle population. On réitère ensuite le procédé à partir de cette population jusqu'à obtenir une solution que l'on juge satisfaisante.

Les différentes méthodes de sélection

Sélection par roulette (wheel)

Les parents sont sélectionnés en fonction de leur performance. Meilleur est le résultat codé par un chromosome, plus grandes sont ses chances d'être sélectionné. Il faut imaginer une sorte de roulette de casino sur laquelle sont placés tous les chromosomes de la population, la place accordée à chacun des chromosomes étant en relation avec sa valeur d'adaptation. Cette roulette est représentée par la figure 1.

Figure 1: Exemple de sélection par roulette

Ensuite, la bille est lancée et s'arrête sur un chromosome. Les meilleurs chromosomes peuvent ainsi être tirés plusieurs fois et les plus mauvais ne jamais être sélectionnés. Cela peut être simulé par l'algorithme suivant :

1. On calcule la somme $S1$ de toutes les fonctions d'évaluation d'une population.
2. On génère un nombre $r$ entre $0$ et $S1$.
3. On calcule ensuite une somme $S2$ des évaluations en s'arrêtant dès que $r$ est dépassé.
4. Le dernier chromosome dont la fonction d'évaluation vient d'être ajoutée est sélectionné.

Sélection par rang

La sélection précédente rencontre des problèmes lorsque la valeur d'adaptation des chromosomes varient énormément. Si la meilleure fonction d'évaluation d'un chromosome représente $90\%$ de la roulette alors les autres chromosomes auront très peu de chance d'être sélectionnés et on arriverait à une stagnation de l'évolution.

La sélection par rang trie d'abord la population par fitness. Ensuite, chaque chromosome se voit associé un rang en fonction de sa position. Ainsi le plus mauvais chromosome aura le rang $1$, le suivant $2$, et ainsi de suite jusqu'au meilleur chromosome qui aura le rang $N$ (pour une population de $N$ chromosomes). La sélection par rang d'un chromosome est la même que par roulette, mais les proportions sont en relation avec le rang plutôt qu'avec la valeur de l'évaluation. Le tableau 2 fournit un exemple de sélection par rang. Avec cette méthode de sélection, tous les chromosomes ont une chance d'être sélectionnés. Cependant, elle conduit à une convergence plus lente vers la bonne solution. Ceci est dû au fait que les meilleurs chromosomes ne diffèrent pas énormément des plus mauvais.

Tableau 2: Exemples de sélection par rang pour 6 chromosomes.

Chromosomes	1	2	3	4	5	6	Total
Probabilités initiales	89 %	5 %	1 %	4 %	3 %	2 %	100 %
Rang	6	5	1	4	3	2	21
Probabilités finales	29 %	24 %	5 %	19 %	14 %	9 %	9 %

Sélection steady-state

Ce n'est pas une méthode particulière de sélection des chromosomes parents. L'idée principale est qu'une grande partie de la population puisse survivre à la prochaine génération. L'algorithme génétique marche alors de la manière suivante. A chaque génération sont sélectionnés quelques chromosomes (parmi ceux qui ont le meilleur coût) pour créer des chromosomes fils. Ensuite les chromosomes les plus mauvais sont retirés et remplacés par les nouveaux. Le reste de la population survie à la nouvelle génération.

Sélection par tournoi

Sur une population de $m$ chromosomes, on forme $m$ paires de chromosomes. Dans les paramètres de l'AG, on détermine une probabilité de victoire du plus fort. Cette probabilité représente la chance qu'a le meilleur chromosome de chaque paire d'être sélectionné. Cette probabilité doit être grande (entre 70% et 100%). A partir des $m$ paires, on détermine ainsi $m$ individus pour la reproduction.

Elitisme

A la création d'une nouvelle population, il y a de grandes chances que les meilleurs chromosomes soient perdus après les opérations d'hybridation et de mutation. Pour éviter cela, on utilise la méthode d'élitisme. Elle consiste à copier un ou plusieurs des meilleurs chromosomes dans la nouvelle génération. Ensuite, on génère le reste de la population selon l'algorithme de reproduction usuel. Cette méthode améliore considérablement les algorithmes génétiques, car elle permet de ne pas perdre les meilleurs solutions.

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 comme le montre la figure 2. Ils sont applicables à de nombreux problèmes, dont le problème du voyageur de commerce.

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