Algorithme évolutionniste
Les algorithmes évolutionnistes ou algorithmes évolutionnaires (evolutionary algorithms en
anglais), sont une famille d'algorithmes dont le principe s'inspire de la théorie de l'évolution pour
résoudre des problèmes divers. Ce sont donc des méthodes de calcul bioinspirées. L'idée est de
faire évoluer un ensemble de solutions à un problème donné, dans l'optique de trouver les meilleurs
résultats. Ce sont des algorithmes dits stochastiques, car ils utilisent itérativement des processus
aléatoires.
La grande majorité de ces méthodes sont utilisées pour résoudre des problèmes d'optimisation,
elles sont en cela des métaheuristiques, bien que le cadre général ne soit pas nécessairement dédié
aux algorithmes d'optimisation au sens strict1. On les classe également parmi les méthodes
d'intelligence computationnelle.
Un algorithme évolutionnaire utilise itérativement des opérateurs de sélections (en bleu) et de variation (en
jaune). i : initialisation, f(X) : évaluation, ? : critère d'arrêt, Se : sélection, Cr : croisement, Mu : mutation, Re :
remplacement, X* : optimum.
Sommaire
• 1Origines
• 2Principes de bases
o 2.1Terminologie
o 2.2Algorithme
o 2.3Généralités
• 3Principales familles
o 3.1Stratégies d'évolution
o 3.2Programmation évolutionnaire
o 3.3Algorithmes génétiques
o 3.4Programmation génétique
o 3.5Algorithmes à estimation de distribution
• 4Historique
• 5Références
o 5.1Sources
o 5.2Voir aussi
Origines[modifier | modifier le code]
Ces algorithmes manipulent des populations de solutions.
L'« arbre de la vie », tel que le représente Charles Darwin dans son ouvrage L'Origine des espèces, où il
présente ses théories sur l'évolution des êtres vivants.
Les algorithmes évolutionnaires s'inspirent de l'évolution des êtres vivants, en considérant que celle-
ci tend à produire des organismes plus adaptés à leur environnement.
Selon la théorie de l'évolution, plusieurs mécanismes sont à l'œuvre pour ce faire.
Schématiquement :
• Les caractéristiques d'un organisme sont en grande partie codées dans ses gènes,
• chaque population d'organismes est composée d'individus tous différents,
• les individus sont plus ou moins adaptés à leur environnement,
• les organismes transmettent une partie de leurs caractéristiques à leurs descendants,
• les individus les plus adaptés se reproduisent plus « efficacement », leurs caractéristiques ont
donc tendance à davantage se répandre dans la population.
Principes de bases[modifier | modifier le code]
Terminologie[modifier | modifier le code]
Tous les algorithmes évolutionnaires font évoluer un ensemble (une « population ») de solutions (les
« individus »). Les individus sont représentés par leur génotype, qui s'exprime sous la forme d'un
phénotype, auxquels on associe une qualité, la « fitness ». Les algorithmes sont conçus de façon
que plus la fitness d'un individu est élevée, plus il a de chances de transmettre son génotype au sein
de la population.
À chaque étape de l'algorithme est associé un « opérateur », qui décrit la façon de manipuler les
individus. On regroupe parfois les différents opérateurs sous des termes génériques :
• opérateurs de sélection pour la sélection et le remplacement,
• opérateurs de variation pour la mutation et le croisement.
Algorithme[modifier | modifier le code]
