4.3.7.3. Algorithme PESA (Pareto Envelope based
Selection Algorithm)
La méthode PESA a été également
proposée par Knowles et corne [Knowles et al., 2000]. Elle reprend
approximativement le principe de crowding développé dans PAES et
définit un paramètre appelé "squeeze_factor" qui
représente la mesure d'encombrement d'une zone de l'espace. Alors que
PAES est basé sur une stratégie d'évolution, PESA est une
méthode basée sur les algorithmes génétiques. Elle
définit deux paramètres concernant la taille des populations
d'individus : PI (taille de la population interne) et PE
(taille de la population externe ou archive).
4.3.7.4. Modèle NSGA II
Dans cette deuxième version de NSGA [Deb, 2000];
l'auteur tente de résoudre les problèmes liés à
l'approche NSGA : complexité, non élitisme et utilisation du
partage.
La complexité de l'algorithme NSGA est notamment due
à la procédure de création des différentes
frontières. Pour diminuer la complexité de calcul de NSGA, Deb
propose une modification de la procédure de tri de la population en
plusieurs frontières.
La deuxième difficulté liée à
l'approche NSGA est l'utilisation de la méthode de partage qui exige le
réglage d'un ou plusieurs paramètre(s) et qui nécessite un
temps de calcul important. Dans NSGA II, Deb remplace la fonction de partage
par une fonction de remplissage.
Enfin, le modèle proposé utilise une
sélection par tournoi pour permettre la conservation des meilleurs
individus d'une génération à l'autre.
4.3.7.5. Modèle PESA II (Region-based
Selection)
PESA II est une technique de sélection basée sur
l'utilisation d'hypercubes dans l'espace des objectifs [Corne, 2001]. Au lieu
d'effectuer une sélection en fonction de la fitness des individus comme
dans PESA, cette méthode effectue une sélection par rapport aux
hypercubes occupés par au moins un individu. Après avoir
sélectionné l'hypercube, on choisit aléatoirement
l'individu dans l'hypercube. Cette méthode se montre plus efficace
à repartir les solutions sur la frontière de Pareto. Cela est
dû à sa capacité de choisir avec une plus grande
probabilité que le tournoi classique, des individus situés dans
des zones désertiques.
4.3.7.6. Algorithme Micro-GA (Micro-Genetic
Algorithm)
Coello trouve que les recherches actuelles n'accordent pas
assez d'importance à l'efficience des méthodes d'optimisation
multiobjectifs. Dans [Coello et al., 2001], il propose une méthode
basée sur une population avec un nombre très faible d'individus.
Cette technique se base sur les résultats théoriques obtenus par
Goldberg [Goldberg, 1989b].
Coello applique le mécanisme suggéré par
Goldberg aux problèmes d'optimisation multiobjectifs en utilisant un
algorithme génétique avec une petite taille de population
associée à une archive et une heuristique de distribution
géographique. Il définit une population extérieure
divisée en deux parties : une partie remplaçable et une partie
non remplaçable. La portion non remplaçable ne change pas durant
le processus de modification et sert à maintenir la diversité.
Elle ne sera mise à jour que lorsque le micro algorithme
génétique aura convergé. La portion remplaçable est
totalement modifiée à intervalle régulier. Ce dernier est
défini en nombre de cycles du micro GA.
Au début de l'algorithme du micro GA, la population est
constituée à l'aide d'individus sélectionnés
aléatoirement dans la population externe. Ensuite l'algorithme se
déroule de manière classique. En fin de cycle, lorsque la
population du micro GA a perdu sa diversité, deux individus non
dominés sont sélectionnés pour mettre à jour
l'archive. L'approche utilisée est similaire à celle de PAES.
Ensuite ces deux mêmes individus sont comparés à deux
individus de la partie non remplaçable. Si l'un des deux premiers domine
l'un des deux autres alors il le remplace dans la partie non
remplaçable.
Les tests effectués par l'auteur montrent que cette
approche est capable de converger plus rapidement vers la surface de Pareto (en
terme de temps CPU). Mais pour le cas de fonctions avec contraintes, la
méthode a été moins bonne que NSGA II. Dans quelque cas,
cette méthode produit une meilleure distribution des points sur la
surface de Pareto.
| 
