ALGORITHMIQUE
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 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,[...]
La suite de cet article est accessible aux abonnés
- Des contenus variés, complets et fiables
- Accessible sur tous les écrans
- Pas de publicité
Déjà abonné ? Se connecter
Écrit par
- Philippe COLLARD : professeur des Universités
- Philippe FLAJOLET : ingénieur de recherche à l'Institut national de recherche en informatique et automatique (I.N.R.I.A.).
Classification
Médias
Algorithmes de calcul de p
Encyclopædia Universalis France
Arbre binaire
Encyclopædia Universalis France
Échelle de complexité
Encyclopædia Universalis France
Autres références
-
ALGORITHME
- Écrit par Alberto NAIBO et Thomas SEILLER
- 5 919 mots
- 4 médias
La notion d’algorithme a envahi nos discours et nos pratiques, en raison surtout de la diffusion massive d’applications informatiques dédiées à l’exécution automatisée de certaines tâches, ou à la résolution de certains problèmes. On trouve en effet les algorithmes non seulement dans de nombreux domaines...
-
PRIX ABEL 2021
- Écrit par Bernard PIRE
- 1 014 mots
- 2 médias
Le prix Abel, qui distingue chaque année un ou plusieurs mathématiciens pour leurs contributions exceptionnelles au développement des mathématiques, a été décerné en 2021 au Hongrois László Lovász et à l’Israélien Avi Wigderson. Dix-neuf ans après la création de ce « prix Nobel des...
-
CALCUL, mathématique
- Écrit par Philippe FLAJOLET
- 1 785 mots
L'algorithmique s'attache à l'élaboration d'algorithmes efficaces pour résoudre les problèmes reconnus comme calculables. Cette discipline s'organise selon quelques grands principes généraux. Par exemple, pour traiter efficacement des problèmes de recherche d'information de forme complexe, il s'avère... -
INDE (Arts et culture) - Les mathématiques
- Écrit par Agathe KELLER
- 5 429 mots
- 3 médias
À l’indépendance, la création de centres d’excellence pour les mathématiques et une école indienne très forte, notamment en algorithmique théorique, placent définitivement l’Inde nouvellement créée sur la carte mondiale des sciences mathématiques. Si un certain nombre de mathématiciens fameux... -
ITÉRATION, mathématique
- Écrit par Jean-Paul DELAHAYE et Encyclopædia Universalis
- 830 mots
Itérer signifie recommencer, faire à nouveau. Construire les nombres entiers peut être vu comme l'opération consistant à partir de zéro à itérer indéfiniment l'ajout d'une unité.
Plus généralement, en mathématiques, lorsqu'une fonction ou opération est disponible, il est fréquent...
- Afficher les 10 références
