4.3.4 Les méthodes non agrégées, non
Pareto
En général, les méthodes dites non
agrégées et non Pareto possèdent un processus de recherche
qui traite séparément les objectifs.
4.3.4.1. Algorithme VEGA (Vector Evaluated Genetic
Algorithm)
Cette méthode a été introduite par
Schaffer en 1985 dans la perspective d'adapter un algorithme
génétique canonique à la résolution d'un
problème multiobjectif [Schaffer, 1985]. Appelée Vector Evaluated
Genetic Algorithm, cette technique se différencie de l'algorithme de
base uniquement par le type de sélection utilisé. L'idée
est simple, si nous avons k objectifs et une population de n
individus, une sélection de n/k individus est effectuée
pour chaque objectif. Ainsi K sous-populations vont être
crées, chacune d'entre elles contenant les n/k meilleurs
individus pour un objectif particulier. Une nouvelle population de taille n est
ensuite formée à partir des K sous populations. Le
processus se termine par l'application des opérateurs
génétiques de base (croisement et mutation).
De nombreuses variantes de cette technique ont été
proposées :
Mélange de VEGA avec dominance de Pareto [Tanaki,
1995],
Paramètre pour contrôler le taux de sélection
[Ritzel, 1994],
Application à un problème contraint [surry,
1995],
Utilisation d'un vecteur contenant les probabilités
d'utiliser un certain objectif lors de la sélection [Kurwase, 1984].
4.3.4.2. Utilisation des genres
Cette méthode introduite par Allenson [Allenson, 1992]
utilise la notion de genre et d'attracteur sexuel pour traiter un
problème à deux objectifs. Une des applications de ce
modèle consiste à minimiser la longueur d'un pipeline tout en
réduisant l'impact écologique de sa construction. En affectant un
objectif à chaque genre, l'auteur espère minimiser les deux
objectifs simultanément car un genre sera toujours jugé
d'après l'objectif qui lui a été associé.
Allenson utilise un algorithme génétique
canonique dans lequel un nombre égal d'individus des deux genres sera
maintenu. La population est initialisée avec autant de males que de
femelles, puis à chaque génération, les enfants remplacent
les plus mauvais individus du même genre. La création des enfants
s'effectue par croisement
mais leur genre est choisi aléatoirement et leur
attracteur est crée en fonction de plusieurs heuristiques
différentes (aléatoire, clonage ou croisement).
En 1996, Lis et Eiben ont également
réalisé un algorithme basé sur l'utilisation des genres,
mais dans ce cas l'algorithme n'est pas limité à deux genres [Lis
et Eiben 1996]. Il peut y avoir autant de genres que d'objectifs du
problème. Ils ont également modifié le principe de
croisement. Pour générer un enfant, un parent de chaque genre est
sélectionné. Ensuite un croisement multipoint est effectué
et le parent ayant participé le plus, en nombre de gènes,
à l'élaboration de l'enfant transmet son genre. En cas
d'égalité le choix s'effectue aléatoirement entre les
parents égaux. L'opérateur de mutation effectue un simple
changement de genre.
| 
