1.2.3.2. Les algorithmes évolutifs (AE)
Les algorithmes évolutifs (Evolutionary Algorithms)
sont des techniques de recherche inspirées de l'évolution
biologique des espèces, apparues à la fin des années 1950.
Parmi plusieurs approches [Holland, 1962], [Fogel et al, 1966], [Rechenberg,
1965], les algorithmes génétiques (AG) constituent certainement
les algorithmes les plus connus [Goldberg, 1989a].
Le principe d'un algorithme évolutionnaire est
très simple. Un ensemble de N points dans un espace de recherche, choisi
a priori au hasard, constituent la population initiale; chaque individu x de la
population possède une certaine performance, qui mesure son degré
d'adaptation à l'objectif visé : dans le cas de la minimisation
d'une fonction objectif f, x est d'autant plus performant que f(x) est plus
petit. Un AE consiste à faire évoluer progressivement, par
générations successives, la composition de la population, en
maintenant sa taille constante. Au cours des générations,
l'objectif est d'améliorer globalement la performance des individus; le
but étant d'obtenir un tel résultat en imitant les deux
principaux mécanismes qui régissent l'évolution des
êtres vivants, selon la théorie de Darwin :
la sélection, qui favorise la reproduction et la survie
des individus les plus performants,
la reproduction, qui permet le brassage, la recombinaison et
les variations des caractères héréditaires des parents,
pour former des descendants aux potentialités nouvelles.
En fonction des types d'opérateurs, i.e.,
sélection et reproduction génétique, employés dans
un algorithme évolutif, quatre approches différentes ont
été proposées [Bäck et al, 1997] : les algorithmes
génétiques (AG), la programmation génétique (PG),
les stratégies d'évolution (SE) et la programmation
évolutive (PE) que nous
allons décrire par la suite. La structure
générale d'un AE est donnée par le pseudo code (7).
algorithme 1 Structure de base d'un algorithme évolutif
Algorithme évolutif
t 4-- 0
Initialiser la population P(t)
Evaluer P(t)
Répéter
t 4-- t + 1
Sélectionner les parents
Appliquer les opérateurs génétiques
Evaluer la population des enfants crées
Créer par une stratégie de sélection la
nouvelle population P(t) Tant que (condition d'arrêt n'est pas
satisfaite)
a. Les algorithmes génétiques (Genetic
Algorithms)
Les algorithmes génétiques sont des techniques
de recherche stochastiques dont les fondements théoriques ont
été établis par Holland [Holland, 1975]. Ils sont
inspirés de la théorie Darwinienne : l'évolution naturelle
des espèces vivantes. Celles-ci évoluent grâce à
deux mécanismes : la sélection naturelle et la reproduction. La
sélection naturelle, l'élément propulseur de
l'évolution, favorise les individus, d'une population, les plus
adaptés à leur environnement. La sélection est suivie de
la reproduction, réalisée à l'aide de croisements et de
mutations au niveau du patrimoine génétique des individus. Ainsi,
deux individus parents, qui se croisent, transmettent une partie de leur
patrimoine génétique à leurs progénitures. En plus,
quelques gènes des individus, peuvent être mutés pendant la
phase de reproduction. La combinaison de ces deux mécanismes, conduit,
génération après génération, à des
populations d'individus de plus en plus adaptés à leur
environnement. Le principe des AG est décrit par le pseudo code (8).
algorithme 2 Structure de base d'un algorithme
génétique
Algorithme Génétique
t 4-- 0
Initialiser la population P(t)
Evaluer P(t)
Répéter
t 4-- t + 1
P(t) = Sélectionner (P(t -
1)) Croiser (P(t))
Muter (P(t))
Evaluer P(t)
Jusqu'à (condition d'arrêt validée)
Dans leur version canonique, les AG présentent des
limites qui conduisent le plus souvent à des problèmes de
convergences lente ou prématurée. Pour pallier à ces
inconvénients, des améliorations ont été
apportées : e.g, codage, opérateurs biologiques, stratégie
élitiste, etc. les détails de fonctionnement de ces algorithmes
peuvent être trouvés dans plusieurs références
principalement : [El Imrani, 2000], [Michalewicz, 1996].
b. Programmation génétique (Genetic
Programming)
La programmation génétique est une variante,
des algorithmes génétiques, destinée à manipuler
des programmes [Koza, 1992] pour implémenter un modèle
d'apprentissage automatique. Les programmes sont généralement
codés par des arbres qui peuvent être vus comme des chaînes
de bits de longueur variable. Une grande partie des techniques et des
résultats concernant les algorithmes génétiques peuvent
donc également s'appliquer à la programmation
génétique.
c. Stratégies d'évolution (Evolutionary
Strategy)
Les stratégies d'évolution forment une famille
de métaheuristiques d'optimisation. Elles sont inspirées de la
théorie de l'évolution. Ce modèle fut initialement
proposé par Rencherberg [Rechenberg, 1965]. il constitue, à ce
titre, la première véritable métaheuristique et le premier
algorithme évolutif.
Dans sa version de base, l'algorithme manipule
itérativement un ensemble de vecteurs de variables réelles,
à l'aide d'opérateurs de mutation et de sélection.
L'étape de mutation est classiquement effectuée par l'ajout d'une
valeur aléatoire, tirée au sein d'une distribution normale. La
sélection s'effectue par un choix déterministe des meilleurs
individus, selon la valeur de la fonction d'adaptation.
Les strategies d'évolution utilisent un ensemble de
u "parents" pour produire A "enfants". Pour produire chaque
enfant, p parents se "recombinent". Une fois produits, les enfants
sont mutés. L'étape de sélection peut s'appliquer, soit
uniquement aux enfants, soit à l'ensemble (enfants + parents).
Dans le premier cas, l'algorithme est noté (u, A)--ES,
dans le second (u + A)--ES [Schoenauer et
Michalewicz, 1997].
À l'origine, l'étape de recombinaison
était inexistante, les algorithmes étant alors notés
((u, A)--ES ou (u + A)--ES. Les
méthodes actuelles utilisent l'opérateur de recombinaison, comme
les autres algorithmes évolutifs, afin d'éviter d'être
piégées dans des optima locaux.
Une itération de l'algorithme général
procède comme suit :
1. À partir d'un ensemble de u parents,
2. produire une population de A enfants:
a. choisir p parents,
b. recombiner les parents pour former un unique individu,
c. muter l'individu ainsi crée,
3. sélectionner les i meilleurs individus.
d. Programmation évolutive (Evolutionary Programming)
La programmation évolutive a été
introduite par Laurence Fogel en 1966 [Fogel et al, 1966] dans la perspective
de créer des machines à état fini (Finite State Machine)
dans le but de prédire des événements futurs sur la base
d'observations antérieures.
La programmation évolutive suit le schéma classique
des algorithmes évolutifs de la façon suivante :
1. on génère aléatoirement une population
de n individus qui sont ensuite évalués;
2. chaque individu produit un fils par l'application d'un
opérateur de mutation suivant une distribution normale;
3. les nouveaux individus sont évalués et on
sélectionne de manière stochastique une nouvelle population de
taille n (les mieux adaptés) parmi les 2m individus de la
population courante (parents + enfants);
4. on réitère, à partir de la
deuxième étape, jusqu'à ce que le critère
d'arrêt choisi soit valide.
La programmation évolutive partage de nombreuses
similitudes avec les stratégies d'évolution : les individus sont,
a priori, des variables multidimensionnelles réelles et il n'y a pas
d'opérateur de recombinaison. La sélection suit une
stratégie de type
(i + A).
| 
