4.4.2 Conservation et propagation des solutions
non-dominées
Comme déjà mentionné, il est important de
maintenir les solutions non-dominées trouvées le long de tout le
processus de recherche et ainsi pouvoir retourner à la fin ces solutions
non-dominées en tenant compte de toutes les populations
précédentes. Ceci est important non seulement pour des raisons
pragmatiques, mais également pour les raisons théoriques
[Rudolph, 1998].
La manière la plus directe de maintenir des solutions
non-dominées, en prenant en considérations toutes les populations
précédentes (ou essaims), est d'employer des archives externes.
De telles archives permettra l'ajout d'une solution seulement si elle est
non-dominée par une solution enregistrée dans l'archive ou si
elle domine une des solutions de l'archive (dans ce cas, les solutions
dominées doivent être supprimés de l'archive).
L'inconvénient de cette approche est l'augmentation
très rapide de la taille des archives. C'est un point important parce
que les archives doivent être mises à jour à chaque
génération. Ainsi, cette mise à jour peut devenir
très coûteuse en temps de calcul si la taille des archives est
importante. Dans le pire des cas, tous les membres de l'essaim peuvent entrer
dans l'archive, à chaque génération. Ainsi, le processus
de la mise à jour correspondant, à chaque
génération, aura une complexité de
o(kN2), oil N est la taille de l'essaim et k le
nombre des objectifs. De cette façon, la complexité du processus
de mise à jour pour l'exécution complète de l'algorithme
est de o(kMN2), oil M est le nombre total
d'itérations.
Cependant, il est nécessaire d'ajouter un
critère pour décider quelles solutions non-dominées
doivent être maintenues dans le cas oil l'archive est pleine. Dans
l'optimisation multiobjectif évolutionnaire, les chercheurs ont
adopté différentes techniques pour réduire la taille des
archives. D'autres concepts ont été introduits pour l'utilisation
des archives, par exemple, pour ajouter les éléments dans
l'archive, la distribution des solutions a été utilisée
comme critère additionnel au lieu d'utiliser uniquement le concept de
non dominance.
Il faut noter qu'on doit utiliser trois archives pour adapter
PSO à l'optimisation multiobjectif : une pour stocker les meilleures
solutions globales, une pour les meilleures valeurs pbest et une
troisième pour stocker la meilleure solution locale. Cependant, dans la
pratique, quelques auteurs rapportent l'utilisation de plus d'une archive dans
leur MOPSOs. Plus récemment, d'autres chercheurs ont proposé
l'utilisation de formes relaxées de dominance. La plus principale a
été la méthode c-dominance [Laumanns et al,
2002]. Le but était de sauvegarder les solutions non dominées
dans des archives externes. En utilisant le paramètre c, on
définit un ensemble de cases de taille epsilon, une seule solution
non-dominée est maintenue pour chaque case (située à la
limite gauche et inférieure de chaque case). Comme illustré dans
la figure (4.7).
FIG. 4.7 - Exemple d'utilisation de € dominance
dans un archive externe
Comme le montre la figure (4.7), la solution 1 domine la
solution 2; donc la solution 1 est maintenue. Les solutions 3 et 4 sont non
dominées l'une de l'autre, mais solution 3 est mieux que 4, puisque
solution 3 est le plus proche au coin à gauche inférieur
représenté par le point (2€, 2€).
Solution 5 domine solution 6, donc solution 5 est maintenue. Solution 7 est non
accepté puisque sa case représentée par le point
(2€, 3€) est dominée par la case
représentée par le point (2€, 2€).
Pour un cas Bi-objectif, l'utilisation du
c--dominance, comme proposé dans [Laumanns et al, 2002],
garantit que les solutions maintenues sont non-dominées en tenant compte
de toutes les solutions produites pendant l'exécution.
En utilisant c-dominance, la taille de l'archive externe
final dépend de la valeur c, qui est normalement un
paramètre défini par l'utilisateur [Laumanns et al, 2002].
| 
