Université d’Alger 1 Benyoucef Benkhedda 2ème année master ISII
Département de Mathématiques et Informatique Module : Bio-inspired computing
Série n°2: Algorithmes Génétiques
Exercice n° 1 :
Dans un algorithme génétique simple constitué d’une population d’individus où chaque
individu est représenté par un chromosome de longueur L :
1. Quel est le nombre de chromosomes résultant de l’application de la mutation bit-flip
sur un seul gène d’un chromosome binaire ?
2. Quel est le nombre de chromosomes résultant de l’application de la mutation bit-flip
sur k gènes d’un chromosome binaire (k ≤ L) ?
3. Quel est le nombre de chromosomes résultant de l’application de la mutation bit-flip
sur un seul gène d’un chromosome ?
4. Quel est le nombre de chromosomes résultant de l’application de la mutation bit-flip
sur k gènes d’un chromosome (k ≤ L) ?
5. Calculez la probabilité qu'un chromosome binaire ne soit pas modifié en appliquant la
mutation bit-flip habituelle avec une probabilité pm = 1 / L
Exercice n° 2 :
Considérons l'algorithme génétique simple appliqué à une population de 8 nombres entiers.
Supposons qu'au temps t de l'évolution la population ait la composition suivante:
• x=1: 2 exemplaires
• x=2: 3 exemplaires
• x=3: 3 exemplaires
En supposant que la fonction de fitness est f (x) = x2, calculez la probabilité de sélectionner les
individus x = 1, x = 2 et x = 3 en utilisant la sélection de la roulette.
Exercice n° 3 :
Considérons une population d’individus simples, avec un seul chromosome de longueur n =
1000. Chaque entrée dans le chromosome peut prendre quatre valeurs (A, C, G, T). Supposons
que la taille de la population est égale à M.
1. Combien de chromosomes possibles existe-t-il?
2. En supposant que la longueur des chromosomes et la taille de la population restent
constantes, quelle est la borne supérieure du nombre de chromosomes différents évalués
au cours de G générations ?
Page 1 sur 2
3. Si la taille de la population est constante et est égale à 1012, quel sera le nombre total de
chromosomes qui sera évalué au cours de 109 générations, en supposant que tous les
chromosomes évalués sont différents ?
Exercice n° 4 :
Soit la fonction g(x) = x3 - 60 * x2 + 900 * x +100 avec: 0 ≤ x ≤ 31
Utiliser les algorithmes génétiques pour résoudre le problème de maximisation lié à la fonction
g(x) en considérant les paramètres suivants:
Probabilité de croisement, Pc = 1.0
Probabilité de mutation, Pm = 0.0
1. Donner la représentation d’une solution.
2. Définir la fonction objectif (fitness) qui permet d’évaluer les solutions.
3. Dérouler l’algorithme génétique en commençant par une population initiale constituée
de 4 individus en détaillant :
a. L’étape de la sélection en utilisant la sélection de la roulette.
b. L’étape du croisement en utilisant le croisement à point unique.
c. L’étape de la mutation.
Exercice n° 5 :
Pour la population initiale décrite sur le tableau ci-dessous, déterminez la population suivante
qui résulte après une itération de la version simple de l’algorithme génétique basé sur les
critères suivants :
• Maximisation de la fonction objective,
• Sélection de la roulette,
• Croisement à point unique au niveau du 4ème gène,
• Taux de mutation de 0,1.
Si vous avez besoin de nombres aléatoires, choisissez dans l'ordre parmi les suivants:
0.86, 0.59, 0.67, 0.14, 0.34, 0.08, 0.11, 0.29, 0.85, 0.76, 0.43, 0.47, 0.89, 0.80, 0.98, 0.58, 0.03,
0.57, 0.49, 0.92
Répétez depuis le début si vous en avez besoin de plus.
Population initiale Fitness Nouvelle population
100010111 4
100000001 -10
010101010 -6
010100110 1
001100111 -5
110110110 21
Page 2 sur 2
