CHAPITRE II. METHODES D'OPTIMISATION
II.5.5 micro-GA
L'algorithme micro-GA utilise deux mémoires : Une
mémoire interne M, et une mémoire externe E. La
population initiale est générer de façon aléatoire
et met dans M. M et divisé en deux parties :
remplaçable et non-remplaçable. La partie non-remplaçable
de M ne changera jamais, elle sert pour fournir la diversité
requise pour l'algorithme. Pendant un cycle, le micro- GA effectue les
opérateurs génétiques conventionnels : sélection
par tournoi, croisement de 2, mutation uniforme et en fin la sélection
élitisme. Après chaque cycle et quand la convergence est
réalisée, on choisi deux individus non dominés de Pi
+ 1 et on les compare au contenu de E. Si l'un ou l'autre reste
comme non dominée alors ils sont jeté dans E en
éliminant tous les individus dominés. Les deux individus sont
aussi comparés avec les individus de la partie remplaçable de
M. Si l'un ou l'autre domine un individu il le remplace. L'idée
est que, avec le temps, la partie remplaçable de la mémoire de la
population tendra à avoir des individus non dominés. Certains
d'entre eux seront utilisés dans la population initiale du micro-GA pour
recommencer à nouveaux le cycle évolutionnaire.
Algorithm: Micro-GA
|
1 : P0 = random (); N = n; E
= 0;
2 : M +- P0
3 : i = 0
4 : while i < Max do
5 : Pi +- select(M)
6 : repeat
7 : opérateurs(Pi);
8 : until (convergence)
14 : copier(2,Pi,E); actualiser (E)
15 : copier(2,Pi,M); actualiser (M)
16 : i = i + 1 19 : end while
|
II.5.6 GA PM
Le fonctionnement général du GA PM (Genetic
Algorithm Population Managment )est basé sur un algorithme
génétique. Cependant, l'amélioration des solutions est
effectuée par une recherche locale.
Le PM (Population Management) signifie qu'une nouvelle
solution T ne peut intégrer la population courante que si sa
distance à la population courante P est supérieur
à un seuil donné: dp > S.
Au départ, on génère une population
initiale de petite taille et on choisit un paramètre fixant le niveau de
dissemblance des solutions entre elles. Ensuite, on procède comme dans
un algorithme génétique, on choisit deux individus que l'on
croise pour obtenir deux enfants. Pour chacun on applique une recherche locale
de façon à obtenir des optima locaux. S'ils ne répondent
pas au critère de diversité, on applique un opérateur de
mutation sur ces individus jusqu'à satisfaction de ce critère.
Ensuite sous condition, on les insère dans la population a la place d'un
autre individu. A chaque itération le paramètre gérant la
diversité est mise à jour.
26
| 
