2.5 Utilisation de NSGA-II
L'algorithme NSGA-II est déjà
implémenté sous R (l'outil utilisé pour
la programmation) et appeler de la façon suivante :
nsga2(fn, idim, odim,
generations, popsize,lower.bounds, upper.bounds, cprob , cdist,mprob , mdist )
avec,
fn : la fonction à minimiser
(l'algorithme1 (section2.2.1) pour nous).
idim : la taille des entrées de la
fonction fn (le nombre de nos paramètres à ajuster)
odim : la taille des sorties de la fonction fn (la
taille de vecteur des sorties de l'algorithme1, qui est 2 pour
nous et quelque soit la procédure d'ajustement).
26
generations : le nombre de
générations souhaitées et aussi le critère
d'arrêt à respecter.
popsize : la taille de la population, il
présente aussi le nombre des compromis qu'on
pourra avoir.
lower.bounds : les bornes inférieures des
entrées de la fonction fm (les bornes inférieures
de nos paramètres )
upper.bounds : les bornes supérieures des
entrées de la fonction fm (les bornes supé-
rieures de nos paramètres )
cprob : Crossover probability
cdist : Crossover distribution index
mprob : Mutation probability
mdist : Mutation distribution index
Lorsqu'on fait un appel de l'algorithme NSGA-II sur un
génotype pour un ajustement (indépendant ou parallèle),
les sorties sont stockées dans un fichier contenant des colonnes pour
les valeurs obtenues des nos paramètres à ajuster et deux
colonnes particulières représentant les valeurs des fonctions
objectifs à minimiser f1 et f2 (les sorties de
l'algorithme1 (section2.2.1)). Cet algorithme va donc donner
en sortie les "popsize : nombre de compromis" meilleurs compromis obtenus. Et
la question posée est comment choisir le compromis ayant des valeurs
minimales à la fois de f1 et puis f2 ?, cette question
sera traitée dans la sous section suivante.
2.5.1 La recherche du meilleur compromis sur le front de
Pareto
Comme toute méthode d'optimisation multi-objectif,
l'algorithme NSGA-II vise à déterminer le front de Pareto ayant
contenu l'ensemble des meilleurs compromis optimaux. NSGA-II nous propose donc
les valeurs de fonctions objectifs (f1, f2), pour les
meilleurs compromis trouvés. Pour lesquels, il faut tracer le front de
Pareto.
2.5.1.1 Tracer le front de Pareto pour les meilleurs
compromis
Pour qu'un compromis (une solution) A, ayant les
coordonnées (xA, yA)
soit sur le front de Pareto, il ne faut pas qu'il existe un autre compromis
B ayant les coordonnées (xB,
yB), qui vérifie la contrainte suivante :
xB < xA et yB
< yA (2.5)
L'algorithme5 résume les étapes
nécessaires pour sélectionner les compromis formant le front de
Pareto, tel qu'à l'étape2 (while), on fait les tests sur les
compromis, s'il existe un compromis B qui vérifie la
contrainte2.5 contre un compromis A, cela veut dire que A est
rejeté sinon retenu et stocké dans le tableau Pareto[k,2]. Nous
obtenons donc un tableau qui récapitule l'ensemble des solutions
minimisant les fonctions objectifs (f1, f2). La
Figure2.6 donne un exemple sur l'application du
critère.
Maintenant la question devient comment sélectionner le
meilleur compromis se trouvant sur le front de Pareto?. Trois critères
de sélection ont été développés pour
répondre à cette question.
27
Algorithm 5 Tracer le front de Pareto à
partir des nuages des points des compromis
1: Initialiser :
k = 0;
Pareto[k, 2]
: Il prendra les compromis ayant construit le front de Pareto. i =
1;
2: while(i<= f1 )) // Notons que, f1 =
f2
{
for(j = 1; j <= f1 ; j++)
{
if((f1[j]<f1[i]) and
(f2[j]<f2[i]))
{
boule=False;
break;
}
else{boule=True ;}
}
if(boule==True)
{
k=k+1;
Pareto[k,] =(f1[i],f2[i])
}
i=i+1;
}
3: Tracer les éléments de Pareto.
Remarque 2.3. La cntrainte2.5 traduit juste
le principe de dominance entre deux individus (solutions) dans l'espace de
recherche (vu en sectin2.3.1 et algrithme3).
| 
