ALGORITHMIQUE

Concepts de base

Un A.G. manipule des chaînes de symboles. Chaque chaîne représente une solution potentielle complète à un problème donné. De façon métaphorique, une chaîne est assimilée à un chromosome, la valeur d'un symbole à un allèle et l'ensemble des chaînes manipulées à une population. Le plus souvent, la population est de taille constante, les chromosomes sont de longueur fixe et l'alphabet des symboles est binaire. D'autres représentations sont également utilisées : structure arborescente, taille de chromosome variable, ou encore codage fondé sur les nombres réels. Un des problèmes cruciaux pour appliquer un A.G. réside dans le codage des solutions sous la forme d'une chaîne de symboles. On peut établir un parallèle entre cette correspondance et le processus de morphogenèse qui produit un phénotype à partir du génotype. Les chromosomes sont soumis à un processus directement inspiré par l'évolution. L'algorithme de base est à la fois simple et général : il implante une boucle évolutionniste dans laquelle chaque itération correspond à une génération.

Le plus souvent, la population initiale est engendrée de façon aléatoire mais il peut être judicieux de biaiser cet échantillonnage dès lors que l'on dispose d'informations a priori sur la qualité de certaines solutions. Afin d'améliorer, de génération en génération, les performances de la population, une pression sélective est exercée sur les solutions. La sélection est fondée sur une valeur d'adaptation, dite valeur de fitness, associée à chaque chromosome via son expression phénotypique. Exploiter les connaissances disponibles en sélectionnant les « meilleurs » chromosomes de la population n'est pas suffisant, car la sélection seule conduirait à terme à ne conserver que les meilleures solutions déjà disponibles dans la population initiale. Il faut donc disposer de mécanismes – mutation ou croisement – qui, en introduisant de la diversité, permettent d'explorer l'espace de recherche. L'opérateur de croisement est essentiel dans la dynamique d'un A.G. ; il consiste à recombiner deux chromosomes (par exemple les chaînes binaires 00111 et 11000) pour donner deux « descendants » (00000 et 11111). Le croisement permet l'échange d'information entre solutions tout en laissant globalement invariant le « matériel génétique » disponible dans la population. L'opérateur de mutation modifie la valeur allélique sur un locus particulier d'un chromosome ; il joue un rôle de moindre importance.

Contrairement aux autres heuristiques de recherche non déterministes, un A.G. explore en parallèle plusieurs chemins vers des solutions optimales. Bien que l'on ne puisse pas garantir l'obtention d'une solution optimale, cela permet d'éviter une convergence vers une solution sous optimale. Il existe de nombreuses variantes de ce schéma général ; elles concernent la méthode de sélection, le choix des opérateurs, ou encore les techniques de remplacement.

Application

Un des intérêts de l'approche évolutionnaire est que l'on dispose d'un algorithme générique facile à implanter. Pour l'instancier sur un nouveau problème,[...]