Chapitre 2
Algorithmes évolutionnaires
Les algorithmes évolutionnaires regroupent un ensemble
d'algorithmes inspirés du processus d'évolution naturelle. Ces
algorithmes sont utiles pour la résolution de problèmes où
les algorithmes classiques d'optimisation, d'apprentissage ou de conception
automatique sont incapables de produire des résultats satisfaisants. Ils
appartiennent à la classe des méthaheuristiques qui, à
leur tour, font partie des méthodes heuristiques. Ce sont des
méthodes d'approximation qui fournissent des résultats de bonne
qualité, en sacrifiant éventuellement l'exactitude ou
l'optimalité de la solution, à des problèmes souvent
réputés difficiles pour lesquels on ne connait pas de
méthodes exactes plus efficace.
2.1 Principes d'inspiration
- Les individus d'une espèce à grande
fertilité ont plus de chance de survivre pour longtemps.
- Sous l'absence d'influence externe, la dimension d'une
espèce reste, en gros, constante. - Encore, sans influences externes, la
ressource de nourriture est limitée mais reste équilibrée
avec le temps.
- Les individus luttent pour la survie à cause de la
concurrence sur les ressources limitées.
- Il n'existe pas d'individus équivalents, notamment pour
les espèces à reproduction sexuelle.
- Les différences entre individus peuvent affecter leurs
aptitudes, et par conséquent, leur capacité de survie.
- Une bonne partie de ces variations est inhéritable.
- Les bons individus ont plus de chances de survivre et de
produire d'autes bons individus.
- Les individus qui survivent transmettront, probablement, leurs
caractéristiques
à leurs enfants.
- Les espèces évoluent lentement, et s'adaptent de
plus en plus à leur environnement.
2.2 Cycle de base d'un algorithme
évolutionnaire
Tous les algorithmes évolutionnaires font
évoluer un ensemble (population) de solutions (individus). La population
initiale est générée aléatoirement. En suite, Pour
chaque individus, on calcul le résultat d'une fonction
d'évaluation (fitness) mesurant le degré de leur adaptation.
L'utilité de chaque individu étant maintenant connue,
l'algorithme filtre la population courante en éliminant les individus
ayant obtenus un mauvais résultat lors du processus d'évaluation,
tout en préservant les autres. Après avoir
sélectionné les bons individus, ces derniers seront
combinés ou variés afin d'en produire de nouveaux. Les nouveaux
individus sont sensés être d'une qualité aussi bonne que
ceux de la génération précédente. Ils seront
passés à leur tour à la phase de sélection, et
ainsi de suite jusqu'à atteindre un des critères
d'arrêt.L'algorithme devrait tendre, de plus en plus, vers la solution
optimale. Le critère d'arrêt est le plus souvent relatif au nombre
de générations. Mais il peut cependant dépendre du
degré d'évolution (amélioration) de l'algorithme, de la
distance entre individus ou du facteur de temps.
| 
