4.3.6 Les techniques non élitistes
4.3.6.1. Algorithme MOGA (Multiple Objective Genetic
Algorithm)
En 1993 Fonseca et Fleming ont proposé une
méthode, dans laquelle chaque individu de la population est rangé
en fonction du nombre d'individus qui le dominent [Fonseca et Fleming, 1993].
Ensuite; ils utilisent une fonction de notation permettant de prendre en compte
le rang de l'individu et le nombre d'individus ayant le même rang.
Soit un individu x à la génération
t, dominé par p (t) individus. Le rang de cet individu
est :
rang(x ,t) = 1 + p (t)
(4.11)
Tous les individus non dominés sont de rang 1. Les auteurs
calculent la fitness de chaque individu de la façon suivante :
Calcul du rang de chaque individu.
Affectation de la fitness de chaque individu par application
d'une fonction de changement d'échelle sur la valeur de son rang. Cette
fonction est en général linéaire. Suivant le
problème, d'autres types de fonction pourront être
envisagés afin d'augmenter ou de diminuer l'importance des meilleurs
rangs ou d'atténuer la largueur de l'espace entre les individus de plus
fort rang et de plus bas rang.
L'utilisation de la sélection par rang a tendance
à répartir la population autour d'un même optimum. Or cela
n'est pas satisfaisant pour un décideur car cette méthode ne lui
proposera qu'une seule solution. Pour éviter cette dérive, les
auteurs utilisent une fonction de partage. L'objectif est de répartir la
population sur l'ensemble de la frontière de Pareto.
La technique de partage agit sur l'espace des objectifs. Cela
suppose que deux actions qui ont le même résultat dans l'espace
des objectifs ne pourront pas être présentes dans la
population.
Cette méthode obtient des solutions de bonne
qualité et son implémentation est facile. Mais les performances
dépendent de la valeur du paramètre
óshare utilisé dans la technique de partage.
Dans leur article Fonseca et Flaming proposent une méthode de
sélection de la meilleure valeur de óshare.
4.3.6.2. Algorithme NSGA (Non dominated Sorting
Genetic Algorithm)
Dans la méthode proposée par [Srivinas et Deb
1993], le calcul de fitness s'effectue en séparant la population en
plusieurs groupes en fonction du degré de domination au sens de Pareto
de chaque individu.
1. Dans la population entière, on recherche les individus
non dominés. Ces derniers constituent la première
frontière de Pareto.
2. On leur attribue une valeur de fitness factice, cette
valeur est supposée donner une chance égale de reproduction
à tous ces individus. Cependant pour maintenir la diversité dans
la population, il est nécessaire d'appliquer une fonction de partage sur
cette valeur.
3. Ce premier groupe d'individu est ensuite supprimé
de la population.
4. On recommence cette procédure pour
déterminer la seconde frontière de Pareto. La valeur factice de
fitness attribuée à ce second groupe est inférieure
à la plus petite fitness après application de la fonction de
partage sur le premier groupe. Ce mécanisme est
répété jusqu'à ce que l'on ait traité tous
les individus de la population.
L'algorithme se déroule ensuite comme un algorithme
génétique classique. Srivinas et Deb utilisent une
sélection basée sur le reste stochastique. Mais leur
méthode peut être utilisée avec d'autres heuristiques de
sélections (tournoi, roulette pipée, etc.).
| 
