6. Algorithmes génétiques
Les algorithmes génétiques (A.G.) constituent un exemple représentatif d'un ensemble de méthodes connues sous le nom d'algorithmes évolutionnaires (A.E.). Ces méthodes servent à implanter sur des systèmes artificiels les mécanismes néo-darwiniens de l'évolution naturelle. Cette approche initiée dans les années 1970 par John Holland connaît depuis le début des années 1990 une forte croissance. Les A.E. sont des algorithmes itératifs fondés sur la notion de génération ; mais ils sont, également, par nature, hautement parallèles dans la mesure où ils simulent l'évolution de tout un ensemble de solutions.
• 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 fit […]
… pour nos abonnés, l'article se prolonge sur 10 pages…
