4.3.7 Les techniques élitistes
Les approches que nous venons de voir sont dites non
élitistes car:
1. Elles ne conservent pas les individus Pareto-optimaux
trouvés au cours de l'évolution.
2. Elles maintiennent difficilement la diversité sur la
frontière de Pareto.
3. La convergence des solutions vers la frontière de
Pareto est lente. Pour résoudre ces difficultés, de nouvelles
techniques ont été appliquées.
1. Introduction d'une population externe ou archive permettant
de stocker les individus Pareto-optimaux.
2. Utilisation de techniques de nichage, classification et
"grid-based" pour répartir efficacement les solutions sur la
frontière de Pareto.
3. Préférence pour les solutions non
dominées.
Les paragraphes suivants présentent différents
modèles intégrants des méthodes élitistes.
4.3.7.1. Algorithme SPEA (Strength Pareto Evolutionary
Algorithm)
En 1998 Zitzler et Thiele ont proposé une nouvelle
méthode d'optimisation multiobjectif qui possède les
caractéristiques suivantes [Zitzler et Thiele, 1998] :
Utilisation du concept de Pareto pour comparer les solutions.
Un ensemble de solutions Pareto-optimales est maintenu dans une
mémoire externe appelée archive.
La fitness de chaque individu est calculée par rapport aux
solutions stockées dans l'archive.
Toutes les solutions de l'archive participent à la
sélection.
Une méthode de classification est utilisée pour
réduire l'ensemble de Pareto sans supprimer ses
caractéristiques.
Une nouvelle méthode de niche, basée sur Pareto,
est utilisée afin de préserver la diversité. L'avantage
essentiel est qu'elle n'exige pas de réglage de paramètres de la
méthode de partage.
4.3.7.2. Algorithme PAES (Pareto Archived Evolution
Strategy)
Cette méthode a été développée
initialement comme méthode de recherche locale dans un problème
de routage d'information off-line. Les premiers travaux de
Knowles et Corne ont montré que cette méthode
simple objectif fournissait des résultats supérieurs aux
méthodes de recherche basées sur une population [Knowles et
Corne, 1999]. Par conséquent, les auteurs ont adapté cette
méthode aux problèmes multiobjectifs. Les particularités
de cette méthode sont les suivantes :
Elle n'est pas basée sur une population. Elle n'utilise
qu'un seul individu à la fois pour la recherche des solutions.
Elle utilise une population annexe de taille
déterminée permettant de stocker les solutions temporairement
Pareto-optimales.
L'algorithme utilisé est plus simple et inspiré
d'une stratégie d'évolution [Rechenberg, 1973].
Elle utilise une technique de remplissage basée sur un
découpage en hypercubes de l'espace des objectifs.
| 
