sylvain@sylbarth.com		Curriculum Vitae			My Blog

Les Algorithmes Génétiques

Les algorithmes génétiques sont constitués par une catégorie de programmes dont l'objectif est de résoudre un problème en reproduisant les mécanismes de la sélection naturelle. Ces algorithmes sont particulièrement adaptés à l'optimisation de problèmes combinatoires et notamment des problèmes dits NP-complets (dont le temps de calcul croit de façon non polynomiale avec la complexité du problème). Ces algorithmes constituent parfois une alternative intéressante aux réseaux de neurones mais sont le plus souvent complémentaires. Un exemple peut être donnée dans le cas d'un système à N variables (dans le cas où N est grand) et où seulement certaines combinaisons de ces variables sont pertinentes dans quelques cas particuliers. Le problème du voyageur de commerce des bien connu des chercheurs ("Traveling Salesman Problem"). L'énoncé est le suivant: un voyageur de commerce doit effectuer un déplacement dans 20 villes des Etats-Unis, quel est l'itinéraire le plus court ? Résoudre ce problème par un algorithme génétique pour 20 villes équivaut à utiliser une centrale nucléaire pour alimenter une seule maison, mais qu'en est-il lorsque vous avez 100, 10000 ou même 1 milliard de villes ou de points ? Un algorithme traditionnel aura généralement un temps de calculs dissuasif et c'est justement là qu'interviennent les algorithmes génétiques, pour vous aider à réduire ce temps de calcul.

 Principe Général

Les algorithmes génétiques, comme les réseaux de neurones, ont calqué leur schéma d'optimisation sur l'observation de la sélection naturelle, et plus précisément sur les gènes et les chromosomes. A la différence des programmes génétiques, introduits par Holland (1975) et largement développés par Koza (1992), les algorithmes génétiques travaillent sur des chaînes de caractères de taille fixe. Ces chaines de taille fixe définissent chacune un individus et un solution potentielle à problème que vous devez résoudre. On défini au départ une population d'individus, chacun disposant d'une chaîne de caractères particulière (codant son chromosome) généralement définie de façon aléatoire au départ. Les individus vont ensuite être évalués sur la base d'une fonction objectif, être sélectionnés, se reproduire et subir des mutations. C'est un processus itératif qui prend généralement fin lorsque la population n'évolue plus entre deux périodes.

t = 0;
Initialisation de P[t];
Evaluation de P[t];
Tant Que Population Non Identique
   t = t + 1;
   Selection de P[t] dans P[t-1];
   Recombinaison de P[t];
   Evaluation de P[t];
Fin Tant Que

Nous disposons en première période d'une population P(0) d'individus ayant des caractéristiques diverses (aléatoires au départ) et dont les chaines de caractères représentes des solutions potentielles à notre problème. Les caractéristiques des individus sont ainsi codées par des chaînes de caractères de taille fixe et les individus n'ont aucune connaissance d'un modèle éventuel. A chaque période, nous sélectionnons les meilleurs individus selon une fonction objectif et certains individus mutent ou se reproduisent. Nous itérons le processus jusqu'à la condition de terminaison (stabilité des caractéristiques de la population sur deux périodes par exemple). "Evaluation" utilise la fonction d'évaluation qui dépend de notre problème et qu'il faudra minimiser ou maximiser.

 La sélection

Comme son nom l'indique, la sélection vise à sélectionner une sous population à partir d'une population parent. La méthode la plus courante est celle initiée par Holland lui même en 1975 : la "roulette wheel" selection, qui est une méthode de sélection proportionnelle au niveau de fitness des individus. Le nombre de fois qu'un individus sera sélectionné est égal à son fitness divisé par la moyenne du fitness de la population totale (plus exactement, la partie entière représente le nombre de fois qu'il sera sélectionné, et la partie flottante la probabilité qu'il aura d'être sélectionné à nouveau ). Cette fonction est déterminante dans un algorithme génétique et de nombreuses méthodes de sélection, bien plus complexes sont disponibles : le sigma scaling, la sélection à la Boltzman, la sélection par rang, la sélection par tournois...

 Le crossover

Le crossover, qui symbolise la reproduction sexuée (toujours par métaphore du mécanisme de sélection naturelle), est une des étapes importantes de l'A.G. C'est l'instrument majeur des innovations au sein de l'algorithme, c'est lui qui insufle le changement. Il peut être effectué de plusieurs manières mais la plus courante croise les chaines de caractères de deux individus parents pour former des chaines de caractère enfants. La figure ci-dessous illuste un "single-point" crossover avec deux parent (A,B) et deux enfants (C,D) qui échangent une partie de leur chaine.

Le taux de crossover est en général assez fort et se situe entre 70% et 95% de la population totale.

 La mutation

Comme pour le crossover, la mutation vise à modifier de façon aléatoire une partie de la population.C'est le second mécanisme d'innovation d'un AG. Ici, le principe est de choisir une valeur de remplacement aléatoire pour l'un des gènes des individus de la population concernés. D'autres méthodes de mutation peuvent aussi être utilisées comme la mutation par soustraction numérique fixée sur un gène, ou remplacée par une valeur aléatoire choisie dans un sous ensemble de valeur (pour un cas réel par exemple). A la différence du crossover le taux de mutation est généralement faible et se situe entre 0.5% et 1% de la population totale. Ce taux faible permet d'éviter une dispersion aléatoire de la population et n'entraine que quelques modifications sur un nombre limité d'individus. La mutation prend une place de plus en plus importante dans les algorithmes génétiques, alors qu'il y a encore quelques années son rôle était encore considéré comme accessoire.

 L'évaluation

L'évaluation est la phase au sein de laquelle l'ensemble des individus devant être évalués (notamment ceux ayant subit une mutation ou un crossover) vont pouvoir quantifier leur degré d'élitisme. Le degré de fitness d'un individus sera calculé à l'aide de cette fonction d'évaluation qu'il faudra maximiser ou minimiser. L'opération de fait à l'aide d'une fonction fournie par l'auteur et qui dépend très étroitement du problème à résoudre via l'A.G.

 Existe-il un paramétrage universel ?

Non il n'existe pas de paramètres qui soient adaptés à la résolution de tous les problèmes qui peuvent être posés à une A.G. Cependant, certaines valeurs sont souvent utilisées peuvent être de bons points de départ pour démarrer une recherche de solution(s) à l'aide d'un A.G.

• taille de la population: entre 30 et 50 individus
• taux de crossover: entre 70% et 95%
• taux de mutation: entre 0.5% et 1%

Bien sur ces valeurs sont données à titre indicatif et ne peuvent en aucun cas s'appliquer à l'ensemble des problèmes que peuvent résoudrent les algorithmes génétiques. Une approche prudente consiste à essayer différents paramètres et à choisir ceux qui vous donnent les résultats les plus satisfaisants.

 Quelques sources d'information

• PGAPack : excellent librairie C supportant les AG parallèles et gratuite. Cette librairie peut utiliser MPI pour fonctionner en parallèle mais fonctionne aussi en séquenciel. MPICH fonctionne fonctionne très bien avec PGAPack et je vous encourage fortement à l'installer. Vous pouvez consulter à ce titre le MPICH Install Guide.
• libGA : est aussi une très bonne librairie, largement utilisée dans les milieux universitaires. Elle est gratuite pour une utilisation non commerciale.
• Galopps : outils assez puissant mais encore trop peu documenté à l'heure où j'écris ces lignes.