CHAPITRE II. METHODES D'OPTIMISATION
tions. Il est basé sur les trois
caractéristiques suivantes : il utilise le principe de
l'élitisme, il favorise les solutions non dominées, et il utilise
une variété explicite des solutions, grâce au«
distance crowding », l'algorithme micro-GA se rapporte
à une petit-population génétique
lors de l'initialisation. Selon Goldberg une population de 3
individus peut être convergée
indépendamment de la
longueur de chromosome. Le processus suggéré par Goldberg
était de commencer par une petite population produite
aléatoirement et qui subi des opérateurs génétiques
jusqu'à la convergence, puis générer une nouvelle
population en transférant les meilleurs individus de la population
convergée d'une façon aléatoire . Plusieurs chercheurs ont
adopté cet algorithme dans plusieurs travaux. Citons par exemple Charles
et Karr (1991), Joshua, Knowles et David (2000).
En 2001 Carlos Coello et Gregorio ont publié un article
décrivant cet algorithme avec deux mémoires [1]. Contrairement
aux algorithmes citer avant qui introduisent des compléments
(opérateurs génétiques, mémoire externe...) pour
rendre l'algorithme plus performant, d'autre algorithmes hybrides comme
GA|PM par lequel en finira notre état de l'art ,
introduisent une recherche locale (Moscato, 1989; Moscato et Cotta, 2003), dont
la forme la plus évoluée utilisant une mesure de distance afin
d'apporter une certaine diversité dans les chromosomes avec la gestion
de la population (Sorensen et Sevaux, 2003)[21].
II.5.1 SPEA-II
SPEA-II (Strenght Pareto Evolutionary Algorithm)
utilise une archive At de taille Narchive fixe qui est
destinée à contenir un nombre limité de solutions
non-dominées trouvées par l'algorithme au cours de
l'optimisation.
A chaque itération, les nouveaux individus
non-dominés de la population Ptsont comparés aux membres
de l'archive At en utilisant le critère de dominance. Si le
nombre d'individus non-dominés n'est pas suffisant, l'archive est
complétée par les meilleurs individus dominés. Le
critère de classement est donnée par : F(i) = R(i) +
D(i)
R(i) est calculé comme suit :
R(i) = X S(j)
i?Pt?At,j<i
.
S(j) représente le Strength : S(j)
=| {i : i E Pt U At et j < i} |
Si R(i) = 0 alors l'individu i est non
dominé, par contre si elle est élevée l'individu i
est dominé par plusieurs individus. Ce critère a un
inconvénient lorsque plusieurs individus ne dominent pas les uns les
autres. Dans ce cas, le critère du kime voisin sera
utilisé comme critère de diversité et la densité de
chaque solution i est définie par : D(i) = 1
ók i +2
ók i : est la distance recherchée et
k est définie comme étant la racine carrée de la
taille de l'ensemble Pt U At i.e. k = vN +
Narchive .
22
| 
