Algorithmes
évolutionnaires
multi-objectifs
Elitist Nondominated Sorting
Genetic Algorithm (NSGA-II)
Dans cet algorithme, le double objectif convergence-diversité est atteint, d’une
part, par l’utilisation d’un schéma du calcul de la performance qui préfère les
solutions non-dominées et, d’autre part, par l’application d’une technique de
mesu,re de densité des solutions du même front non-dominée,
Génération de la population enfant Q(t): la population des enfants Q(t) est d’abord créée à
partir de la population des parents P(t).
Fusion: P(t) et Q(t) sont réunies en ensemble R(t) = P(t)∪Q(t),
Trie : R est trié selon le principe de dominance : l’ensemble R est divisé en un nombre de
classes distinctes Rj suivant la façon suivante : tous les individus non-dominés de R
appartiennent à l’ensemble R1 ; ensuite, tous les éléments non-dominés de R\R1 sont
placés dans l’ensemble R2 et ainsi de suite jusqu’à trier toute la population.
Elitist Nondominated Sorting
Genetic Algorithm (NSGA-II)
Remplissage: Quand toute la population est triée, La population suivante P(t+1) est
remplie par les solutions des sous-ensembles non-dominé de R(t) l’un après l’autre
en commençant, évidement, par le premier front.
Pour choisir les solutions qui vont survivre du front dont seulement une partie peut être
placée dans la population suivante, une mesure de la densité des solutions dans l’espace
de critères, dite distance de surpeuplement ou crowding distance
Elitist Nondominated Sorting
Genetic Algorithm (NSGA-II)
Elitist Nondominated Sorting
Genetic Algorithm (NSGA-II)
Elitist Nondominated Sorting
Genetic Algorithm (NSGA-II)
Calcul des distances de surpeuplement: Pour estimer la densité des solutions
voisines d’une solution i dans un ensemble non-dominé F, la quantité di, appelée
distance de surpeuplement, est calculée de la façon suivante.
Elitist Nondominated Sorting
Genetic Algorithm (NSGA-II)
Clustered Elitist Non-dominated Sorting
Genetic Algorithm (c-NSGA-II)
c-NSGA-II hérite le même principe de base de NSGA-II. Il consiste à remplacer la
méthode de crowding par celle de clustring.
Procédure de clustering: Afin de réduire la taille de la population F de N1 à N2 (N1 >
N2), la procédure suivante est utilisée.
Clustered Elitist Non-dominated
Sorting Genetic Algorithm (c-NSGA-
II)
D’abord, tout élément de F est considéré être situé dans son propre cluster.
Initialement, nous avons donc N1 clusters. Ensuite, les distances entre chaque paire
de clusters sont calculées comme suit :
Les distances d(i, j) entre les solutions i et j peuvent être calculées dans l’espace
de décision ou dans l’espace des critères. Les deux clusters les plus proches sont
fusionnés pour former un cluster plus grand. Le processus est répété jusqu’à ce que
le nombre de clusters atteint N2.
Enfin, on ne retient qu’une seule solution dans chaque cluster. C’est la solution dont
la distance moyenne des autres solutions du même cluster est minimale
Clustered Elitist Non-dominated
Sorting Genetic Algorithm (c-NSGA-
II)
Epsilon-Domination based Multi-
Objective Evolutionnary Algorithm
(epsilon-MOEA)
L’ algorithme epsilon-MOEA maintient une archive de taille finie de solutions non-
dominées.
Après avoir initialiser la population P(0) et l’archive A(0), on sélectionne un individu
de la population et un autre de l’archive. Les nouvelles solutions engendrées de ces
deux individus vont servir à la mise à jour de la population, en se basant sur le
concept de dominance, et de l’archive, en se basant sur le concept de epsilon-
dominance
Epsilon-Domination based Multi-
Objective Evolutionnary Algorithm
(epsilon-MOEA)
Epsilon-Domination based Multi-
Objective Evolutionnary Algorithm
(epsilon-MOEA)
Epsilon-Domination based Multi-
Objective Evolutionnary Algorithm
(epsilon-MOEA)
Pop_selection: Pour choisir une solution de P(t), deux individus de P(t) sont choisis
aléatoirement puis comparés au sens de dominance. Si une d’eux domine l’autre, ce
dernier est choisi. Sinon, une solution est choisi aléatoirement parmi eux.
Epsilon-Domination based Multi-
Objective Evolutionnary Algorithm
(epsilon-MOEA)
Archive_selection: Pour choisir une solution de A(t), plusieurs stratégies peuvent
être suivies. Dans ce qui suit, nous choisissons cette solution aléatoirement.
Pop_acceptance: Pour intégrer la solution c dans la population P(t), cette solution
est comparée avec tous les individus de P(t). Si un ou plusieurs individus de P(t)
domine c, c n’est pas accepté. D’autre coté, s’il existe un individu de P(t) dominé
par c , c remplace un d’eux (choisi aléatoirement). Si les deux tests précédents
échouent, c remplace un individu de P(t) choisi aléatoirement.
Epsilon-Domination based Multi-
Objective Evolutionnary Algorithm
(epsilon-MOEA)
Epsilon-Domination based Multi-
Objective Evolutionnary Algorithm
(epsilon-MOEA)
Archive_acceptance: Pour toute solution de l’archive A(t), on associe un vecteur
d’identification B = (B1,B2, · · · ,BM)T , ou M est le nombre des objectifs, comme
suit :
où ⌊·⌋ désigne la valeur entière, fmin,j le minimum possible du jème objectif et ǫj
la l’erreur tolérée pour le jème objectif.
Epsilon-Domination based Multi-
Objective Evolutionnary Algorithm
(epsilon-MOEA)
Pour intégrer la solution c dans l’archive A(t), cette solution est comparée avec tous
les individus de A(t) au sens de epsilon-dominance.
