CHAPITRE II. METHODES D'OPTIMISATION
Figure II.4 - Crowding distance.
- Le critère du kime
voisin.Le critère de densité est
défini comme étant l'inverse de la distance au kime
point voisin. Plus précisément, pour chaque individu
i, les distances le séparant de tous les autres individus j
de la population sont calculés et ordonnés dans une liste.
Le kime élément correspond à la
distance recherchée dénotée ók i . La
valeur de k est définie comme étant la racine
carrée de la taille de l'ensemble des individus.
- Le critère de contribution à
l'hyper-volume.Le critère de contribution à
l'hyper-volume repose sur l'utilisation de l'indicateur de l'hyper-volume. Ce
critère mesure la qualité d'un point en calculant sa contribution
à l'hyper-volume de l'ensemble de la population A. La mesure de
la contribution d'un individu a à l'hyper-volume d'une
population A est donnée par : ÄI-
H(a, A) = I-
H(A) - I-
H(A \ a)
Il est possible d'utiliser les indicateurs de performance
cités précédemment comme mesure de comparaison entre
individus. L'utilisation d'un indicateur évaluant la convergence et la
diversité des individus en même temps (Indicateur de
l'hyper-volume, indicateur epsilon) permet de considérer une mesure
unique pour établir un ordre total dans l'ensemble des individus de la
population.
II.5 ETAT DE L'ART: (MOEAs)
Nous présenterons dans cette section l'état de
l'art des algorithmes évolutionnaire multi- objectif en se focalisant
seulement sur les algorithmes de deuxième
génération, qui utilisent des approches élitistes
et manipulant une population secondaire externe.
Les trois premiers algorithmes utilisent des schémas
d'évolution stationnaire dont : l'algo-rithme SPEA2
proposé par Zitzler en 2001[8] représente une version
corrigée de l'algorithme SPEA proposé auparavant par le
même auteur. L'algorithme c-MOEA proposé par Deb en
2003[17] utilise le concept de l'c-dominance. L'algorithme IBEA
proposer par le même auteur en 2004[9] a pour objectif d'apporter
une solution au problème du « exploration / exploitation
»auquel sont confrontés les MOEAs en proposant une
généralisation du concept de dominance.
Les trois derniers algorithmes sont des algorithmes
génétiques dont l'algorithme NSGA-II proposé par
Deb en 1995 [7] et ses étudiants [16] apparaît comme l'un des
algorithmes de référence pour trouver l'ensemble optimal de
Pareto avec une excellente variété de solu-
21
| 
