TD6 2023-2024

Algorithme génétique 2 G. Indus A et B

TAO Prof. Med DHIB

• Initialisation :
— Création : création aléatoire des individus pour une population initiale.
— Codage : chaque individu est codé.
• Evaluation :
L’opération attribue une valeur à chaque individu, nommée fonction d’adaptation ou fitness.
• Exécution :
Sélection les meilleurs individus sont sélectionnés pour la reproduction et forment un groupe
de parents.
Reproduction l’opérateur de croisement ou cross-over permet de mélanger les codes génétiques des
deux parents.
Mutation L’opérateur de mutation permet de générer des modifications aléatoires dans le code
génétique des enfants.
Remplacement ▪Stationnaire : les enfants remplacent les parents.
▪Elitiste : On garde les individus possédant les meilleures performances d’une
génération à la suivante (nombre de population N ne varie pas)
• Retour à l’évaluation :
Une réévaluation des individus permet de décider de poursuivre ou d’arrêter le processus.

Exercice 1
On se propose d’appliquer l’algorithme génétique pour rechercher le maximum de la fonction f à une
variable réelle x définie par :
𝑓(𝑥) = −𝑥 + 4𝑥,
-1
dans l’intervalle [1, 3] avec une précision de 10 en utilisant les paramètres suivants :
Probabilité de croisement : Pc = 0.75
Probabilité de mutation : Pm = 0.01
1. Déterminer la longueur de chromosome (nombre de bits dans la chaîne)
2. Pour modéliser le problème, on considère une génération de 4 individus. Construire aléatoirement la
génération initiale.
a. Calculer la fitness de chaque chromosome.
b. Calculer l’évaluation totale 𝐹 = ∑ 𝑓(𝑥 ) de la population.
( )
c. Calculer la probabilité de sélection 𝑝 = .
d. Calculer la probabilité cumulative q pour chaque chromosome : 𝑞 = 𝑝 + 𝑝 + ⋯ 𝑝

Pour sélectionner à l’aide de la roulette, on fait tourner la roulette N fois (N taille de la population) de la
façon suivante. A chaque fois, on génère aléatoirement un nombre r dans l’intervalle [0, 1]. Ensuite, on
compare ces nombres aux probabilités qi.
Si r1  q1, v1 est sélectionné.
Sinon vi est sélectionné tel que qi-1  r1  qi avec (2  i  N).
3. On fait tourner 4 fois la roulette pour générer des nombres r dans [0, 1], on obtient : 0.512 0.710
0.216 0.773. Déterminer la nouvelle génération après sélection.
4. Pour chaque chromosome de la nouvelle génération, on génère au hasard, N nombres r dans [0, 1]
ème
et on les compare à la probabilité de croisement Pc. Si ri  Pc, la i chromosome est sélectionné
pour le croisement, sinon il n’est pas. On procède au croisement à partir de la deuxième position. On
fait tourner la roulette, on obtient : 0.82 0.52 0.17 0.79. Donner la nouvelle génération après
croisement.
5. La nouvelle génération est constituée de 4 individus, chaque individu codé sur 5 bits. Il ya au total
4*5=20 bits, on fait tourner 20 fois la roulette pour générer r dans [0, 1]. Si r  Pm, on mute le bit de
ce rang. Après rotation de la roulette, on obtient : [0.121, 0.92, 0.27, 0.85, 0.02, 0.033, 0.71, 0.42, 0.61,

1
 0.57, 0.107, 0.215, 0.03, 0.42, 0.87, 0.09, 0.82, 0.008, 0.87, 0.15]. Appliquer l’opérateur de mutation et
donner la première génération puis la meilleure solution.

Exercice 2
ème
On cherche à maximiser une fonction, la procédure de l’AG a donné pour la 10 génération les individus
suivants :

I1 : 4.3 3.2 3.6 102 0.32

I2 : 2 3 3.5 111 0.46

I3 : 1.5 2.5 3.75 100 0.34

I4 : 2.5 3.5 4.5 96 0.2

I5 : 3.5 4 4.75 105 0.13

I6 : 4 5.5 3.25 125 0.66

I7 : 3.5 4.5 4.25 105 0.5

I8 : 4.5 5.5 4.75 95 0.55

I9 : 5 2.75 3.25 110 0.4

I10 : 6 3.75 3.25 115 0.42

La fonction à optimiser s’exprime par : F=x1+x2+x3+x4+x5

1. Donner la dimension de la fonction à optimiser.
2. Donner le nombre d’individus fixé dans la procédure.
3. Calculer la valeur de la fonction à optimiser pour chaque individu de la génération courante.
4. Quel est le meilleur individu dans la présente génération.
ème
5. On cherche à construire la 11 génération. Calculer la probabilité de sélection pour chaque
individu.
6. Si la sélection donne pour la population intermédiaire trois fois le premier individu, deux fois le
ème ème
deuxième individu, deux fois le 5 individu, une fois le dernier individu, une fois le 4 individu et
ème
une fois le 7 individus, donner l’ensemble des individus obtenus après la sélection.
7. Le hasard fait que le meilleur individu de la population sélectionné se croise avec le moins bon des
individus sélectionnés. Si l’opérateur de croisement utilisé est le croisement en deux points
(croisement double), choisir des sites de coupe et donner le résultat pour ce croisement.
8. Choisir les 3èmes et 4èmes individus de la population sélectionnée et donner le résultat pour un
croisement à un point (croisement simple) avec un site de coupe=3.
9. Les autres individus de la population sélectionnée ne subissent pas de croisement. Avec l’opérateur
de remplacement élitiste, on garde les individus possédant les meilleures performances, donner alors
la population intermédiaire obtenue.

2
 Corrigé TD6- Algorithme génétique

Exercice 1
Maximum de la fonction f à une variable réelle x définie par :
𝑓(𝑥) = −𝑥 + 4𝑥,
-1
dans l’intervalle [1, 3] avec une précision de 10 en utilisant les paramètres suivants :
Probabilité de croisement : Pc = 0.75
Probabilité de mutation : Pm = 0.01
𝑓 (𝑥) = −2𝑥 + 4, 𝑓 (𝑥) = 0  x=2 et 𝑓 (2) = −2 ≤ 0, le maximum de f correspond à x=2 et f(x)=4.
1. Longueur de chromosome (nombre de bits dans la chaîne)
(𝑥 − 𝑥 ). 10  2 , d=1
(3 − 1). 10 = 202  n=5 bits
2. Génération de la population initiale aléatoire :
𝑥 −𝑥 2 2
𝑥=𝑥 + 𝑔 = 1+ 𝑔=1+ 𝑔
(2 − 1) (2 − 1) 31
Individu Entier gi xi Qualité (fitness) Probabilité en % Probabilité qi
01100 g1=1*22+1*23=12 1.77 3.949 26.93 0.2693
00011 g2=3 1.19 3.349 22.84 0.4977
11011 g3=27 2.74 3.449 23.52 0.733
10100 g4=20 2.29 3.915 26.70 1.000
Total 14.664 100

3. On fait tourner 4 fois la roulette pour générer des nombres r dans [0, 1], on obtient : 0.512 0.710
0.216 0.773. Déterminer la nouvelle génération après sélection.

r1 q3  x3 est sélectionné

r2 q3  x3 est sélectionné
r3 q1  x1 est sélectionné
r4 q4  x4 est sélectionné
Première génération
x’1 (=x3): 11011
x’2 (=x3): 11011
x’3 (=x1): 01100
x’4 (=x4): 10100

4. On procède au croisement à partir de la deuxième position. On fait tourner la roulette, on obtient :

0.82 0.52 0.17 0.35. Donner la nouvelle génération après croisement.
r1 Pc  x’1 n’est sélectionné pour croisement
r2 Pc  x’2 est sélectionné pour croisement
r3 Pc  x’3 est sélectionné pour croisement
r4 Pc  x’4 n’est sélectionné pour croisement
Cela donne pour le croisement :

x’2: 11011 x’’2 : 11100

Après croisement
x’3: 01100 x’’3 : 01011

1
 Après croisement, on obtient la nouvelle génération:

x’’1 : 11011
x’’2 : 11100
x’’3 : 01100
x’’4 : 01011
5. Mutation
Il y a 5*4=20 bits, on tourne la roulette 20 fois pour générer r dans [0, 1]. Si r  Pm, on mute le bit de
ce rang.
rm = [0.121, 0.92, 0.27, 0.85, 0.02, 0.033, 0.71, 0.42, 0.61, 0.57, 0.107, 0.215, 0.03, 0.42, 0.87, 0.09, 0.82,
0.008, 0.87, 0.15].
ème ème
Seulement au 18 tour on obtient Pm  rm, on mute alors, le 3 bit du quatrième individu
ère
Finalement la 1 génération devient :
x’’1 : 11011
x’’2 : 11100
x’’3 : 01100
x’4 : 01111
La meilleure solution.
Individu Entier gi xi Qualité (fitness) Probabilité en %
11011 27 2.74 3.45 23.41
11100 28 2.80 3.36 22.79
01100 12 1.77 3.94 26.72
01111 15 1.96 3.99 27.06
Total 14.74 100
La solution délivrée par cette génération est x4=1.96 qui correspond à f(x4)=3.99 et elle est très
proche du résultat théorique (x=2 et fmax=4)
Exercice 2
1. Dimension de F=5
2. Nombre d’individus = 10 individus
3. Valeur de F pour chaque individu :
Individus Valeur de Fi
I1 113.42
I2 119.96
I3 108.09
I4 106.70
I5 117.38
I6 138.41
I7 117.75
I8 110.3
I9 121.4
I10 128.42
4. Meilleur individu= I6
5. Probabilité de sélection : 𝑃 = ∑

2
 Individus Valeur de Fi Probabilité Probabilité %
I1 113.42 0.096 9.6
I2 119.96 0.101 10.1
I3 108.09 0.091 9.1
I4 106.70 0.090 9
I5 117.38 0.099 9.9
I6 138.41 0.117 11.7
I7 117.75 0.099 9.9
I8 110.3 0.093 9.3
I9 121.4 0.103 10.3
I10 128.42 0.108 10.8
Total 1181.83 1.00 100
6. Individus après sélection :
I1, I1, I1, I2, I2, I5, I5, I10, I4, I7
I’1 : 4.3 3.2 3.6 102 0.32

I’2 : 4.3 3.2 3.6 102 0.32

I’3 : 4.3 3.2 3.6 102 0.32

I’4 : 2 3 3.5 111 0.46

I’5 : 2 3 3.5 111 0.46

I’6 : 3.5 4 4.75 105 0.13

I’7 : 3.5 4 4.75 105 0.13

I’8 : 6 3.75 3.25 115 0.42

I’9 : 2.5 3.5 4.5 96 0.2

I’10 : 3.5 4.5 4.25 105 0.5

7. Croisement meilleur individu et le moins bon individu
I’8 : 6 3.75 3.25 115 0.42

I’9 : 2.5 3.5 4.5 96 0.2

Après croisement, on obtient :

I’11 : 6 3.5 4.5 115 0.42

I’12 : 2.5 3.75 3.25 96 0.2

8. Croisement I3 et I4

3
 I’3 : 4.3 3.2 3.6 102 0.32

I’4 : 2 3 3.5 111 0.46

Après croisement
I’13 : 4.3 3.2 3.6 111 0.46

I’14 : 2 3 3.5 102 0.32

9. Population intermédiaire
On a 14 individus, il faut garder dans la génération les 10 meilleurs individus.

I’1 : 6 3.5 4.5 115 0.42 F=129.42

I’2 : 4.3 3.2 3.6 102 0.32 F=113.42

I’3 : 4.3 3.2 3.6 102 0.32 F=113.42

I’4 : 2 3 3.5 111 0.46 F=119.96

I’5 : 2 3 3.5 111 0.46 F=119.96

I’6 : 3.5 4 4.75 105 0.13 F=117.38

I’7 : 3.5 4 4.75 105 0.13 F=117.38

I’8 : 6 3.75 3.25 115 0.42 F=128.42

I’9 : 4.3 3.2 3.6 111 0.46 F=122.56

I’10 : 3.5 4.5 4.25 105 0.5 F=117.75