CHAPITRE 2
Algorithmes évolutionnaires
Les algorithmes évolutionnaires ont vu le jour au
milieu des années 70 avec les travaux de John Holland [75] puis ceux de
David Goldberg [41] sur les algorithmes génétiques (GA :
Genetic Algorithms),
Ces algorithmes, inspirés des principes de
l'évolution biologique des êtres vivants, se basent sur le
processus d'autoadaptation des espèces dont l'idée
générale est que les individus d'une population qui s'adaptent le
mieux aux conditions de leur environnement survivent le plus longtemps, ce qui
résulte en une évolution progressive de cette population au cours
du temps vers des générations meilleures.
D'autres algorithmes évolutionnaires ont vu le jour
depuis la fin des années 80, tous utilisent des populations d'individus
représentant un ensemble de solutions potentielles. Ces individus sont
mélangés et modifiés en utilisant certains
opérateurs spécifiquement créés pour ce type
d'algorithmes inspirés des principes de reproduction et de mutation
biologique. Seuls les meilleurs individus seront gardés pour la
prochaine itération en analogie au processus de la sélection
naturelle.
54
FIGURE 2.4 - Processus de base d'un algorithme
génétique
Après les succès des algorithmes
génétiques, d'autres algorithmes bio-inspirés ont
été proposés. Les systèmes immunitaires artificiels
(AIS : Artificial Immune Systems) [36] comptent parmi les premiers et
utilisent le principe de fonctionnement des systèmes immunitaires des
vertébrés basés sur l'adaptation et la
mémorisation.
D'autres types d'algorithmes sont aussi apparus tels que la
programmation génétique (Genetic Programming) [25]
où le but est de faire évoluer un programme sous forme d'arbre en
adaptant les opérateurs des algorithmes génétiques
à ce type de modèles, ou l'évolution différentielle
(Differential Evolution) [80] qui se basent sur l'évolution
d'individus codés sous forme de vecteurs de nombres réels, et
dont l'opérateur de croisement se base sur un calcul de distances.
Algorithmes d'intelligence en essaim (Swarm
Intelligence)
Le terme d'intelligence en essaim, ou intelligence collective,
désigne un phénomène où une population d'agents
simples et réactifs interagissent les uns avec les autres de
manière à ce qu'un comportement intelligent émerge
à la suite de ces interactions.
Ce phénomène est souvent observé dans les
essaims de créatures sociales comme les fourmis, les abeilles et les
oiseaux.
L'analogie la plus facile pour expliquer ce
phénomène est la manière dont les fourmis travaillent.
À l'échelle individuelle, une fourmi n'est pas intelligente et
son comportement obéit à un ensemble de règles simples,
toutefois, en combinant le comportement de toutes les fourmis d'une colonie,
nous remarquons l'émergence d'un comportement complexe et
auto-organisé. Nous disons donc que le groupe est intelligent, mais que
l'individu ne l'est pas.
55
FIGURE 2.5 - Optimisation de chemins par un
ensemble de fourmis [56]
Des métaheuristiques à base de population sont
apparues au début des années 90 s'ins-pirant de ce
phénomène. Elles se basent généralement sur le
principe de modéliser les solutions sous forme de vecteurs de nombres
réels. Ces vecteurs évolueront à travers les
itérations en se rapprochant ou s'éloignant des autres individus
selon certaines probabilités et en obéissant à certaines
contraintes. L'une des méthodes les plus populaires dans ce contexte est
l'algorithme d'Optimisation par Colonie de Fourmis (ACO : Ant Colony
Optimization) [24] qui fut créée pour la recherche de
chemins optimaux dans les graphes en modélisant le comportement des
fourmis lorsqu'elles se dirigent vers la nourriture.
| 
