III- 2.7.2 Tirage et évaluation de la population
initiale
La première étape de tout algorithme
génétique est de produire la population initiale. Une
chaîne de caractères binaire de longueur l est associée
à chaque membre (individu) de la population. D'habitude, la chaîne
de caractères est connue comme un chromosome et représente une
solution du problème. Un échantillonnage de cette population
initiale crée une population intermédiaire. Nous fixons la taille
de la population à N = 4. Nous tirons donc de façon
aléatoire 4 chromosomes sachant qu'un chromosome est
composé de 12 bits, et chaque bit dispose d'une
probabilité '/2 d'avoir une valeur 0
ou 1. Le minimum, 1226.5 ($/hr), est atteint par la deuxième
séquence et le maximum, 1756.1 ($/hr), est atteint par la
troisième séquence TableauIII-4.
Voyons comment l'algorithme va tenter
d'améliorer ce résultat.
|
N°
|
Population initiale
|
P1 ( pu)
|
P2 (pu)
|
P3 (pu)
|
F (x )( $ / h)
|
F max - F(x)
|
|
1
|
000111111100
|
0.4
|
0.90
|
1.60
|
1579.0
|
177.10
|
|
2
|
000100101011
|
0.4
|
0.30
|
1.50
|
1226.5
|
529.60
|
|
3
|
101010011011
|
1.3
|
0.65
|
1.50
|
1756.1
|
0.000
|
|
4
|
111001010111
|
1.7
|
0.45
|
1.10
|
1622.3
|
133.80
|
Tableau III-4 : Processus de la
première génération de l'AG pour le
réseau 9 noeuds
Donc quelques opérateurs (reproduction, croisement et
mutation) sont appliqués à cette population pour obtenir une
nouvelle population. Le processus qui commence de l'actuelle population et
aboutit à la nouvelle population, est nommé une
génération [22].
III-2.7.3 Sélection
La sélection est appliquée afin de favoriser au
cours du temps les individus les mieux adaptés, à les mieux
adapté, Une nouvelle population va être créée
à partir de l'ancienne par le processus de
sélection de la roue de loterie biaisée. Nous tournons cette roue
4 fois et nous obtenons à la fin la nouvelle population décrite
dans le tableau III-5 [23] [22].
|
N°
|
Les séquences de la population initiale
|
Les séquences de la Nouvelle population
|
|
1
|
000111111100
|
000100101011
|
|
2
|
000100101011
|
000111111100
|
|
3
|
101010011011
|
111001010111
|
|
4
|
111001010111
|
000100101011
|
Tableau III-5 : Nouvelle
Population
III-2.7.4 Croisement
Le croisement est un opérateur très important des
algorithmes génétiques. Nous tirons aléatoirement un lieu
de croisement dans la séquence. Le croisement
s'opère alors à ce lieu avec une
probabilité Pc par exemple égale 1. Le tableau III-6 donne les
conséquences de cet opérateur [23] [22]
|
Locus l=3
|
|
Locus l=7
|
|
Parent 1
|
000100101011
|
Parent 2
|
000111111100
|
|
Parent 3
|
111001010111
|
Parent 4
|
000100101011
|
|
Enfant 1
|
000001010111
|
Enfant 1
|
000111101011
|
|
Enfant 2
|
111100101011
|
Enfant 2
|
000100111100
|
Tableau III-6 : Résultats
de croisement pour deux locus différents
| 
