Fondements de l’intelligence artificielle
Unité 6: Recherches Locales
partie 2: Algorithme Génétique
Redoaune Ezzahir
[Link]@[Link]
Rappel sur la résolution de problème
Tout au long de ce cours, nous nous intéressons à la résolution de problèmes combinatoires qui
se posent dans de nombreux domaines de l'intelligence artificielle et des applications
informatiques dans notre vie quotidienne, tels que :
La planification/ordonnancement des tâches
Le planing des emplois du temps (écoles, université, usine, hôpital, ou clinique)
La recherche du chemin optimal dans un plan
Le positionnement des stations des eaux usés
Le positionnement des stations des énergies renouvelables
Les jeux
…
Rappel sur la résolution de problème
Première étape: Modélisation
Modélisation
La modélisation consiste à mettre au point un ensemble de
variables, d’équations ou de règles pour décrire d’une
manière simple abstraite ou formelle le problème à résoudre
(la représentation doit être simple, compréhensive,
from CS 188 Artificial Intelligence, UC Berkeley, Spring 2014
prédictive) Lecture 2 Uninformed Search, Instructor: Prof. Pieter Abbeel
Etat du monde réel
Tous les détailles (fines) Modèle (abstraction):
définissent le problème Ensemble suffisante de variables, d'équations
ou de règles nécessaires à la résolution du
problème.
La taille de l’espace de recherche
est liée au modèle En général, ces ensemble peuvent être
déterminer par la connaissance des états initial
Bon modèle <==> Bon programme et objectif
Rappel sur la résolution de problème
Deuxième étape: Application d’une stratégie de résolution
Deux grandes catégories de stratégies de recherche
état
state space based search but
- DFS, BFS, UCS, GBFS, A*
- Backtracking search
état
initial
Exemple
Backtracking search
problème 4-queens
X1 X2 X3 X4
1
4
Rappel sur la résolution de problème
Deuxième étape: Application d’une stratégie de résolution
Stratégies état
state space based search but
- DFS, BFS, UCS, GBFS, A*
- Backtracking search
état
initial
Modele CSP du
problème 4-queens
X1 X2 X3 X4
1
4
Rappel sur la résolution de problème
Deuxième étape: Application d’une stratégie de résolution
Stratégies état
state space based search but
- DFS, BFS, UCS, GBFS, A*
- Backtracking search
état
initial
state space
Local search landscape
- Hill climbing
- simulated annealing
Objectif/cost
- min-conflict
paysage de l'espace d'état
state
Rappel sur la résolution de problème
Deuxième étape: Application d’une stratégie de résolution
state space
Local search landscape
- Hill climbing
- simulated annealing
Objectif/cost
- min-conflict
paysage de l'espace d'état
state
Exemple : min-conflict
sur problème 4-queens
X1 X2 X3 X4 X1 X2 X3 X4 X1 X2 X3 X4
X1 X2 X3 X4
1 1 1 1
2 2 2 2
3 3 3 3
4 4 4 4
f=5 f=2 f=0
Idée de base
Population-based
Algorithms
solution
acceptable
Genetic
Algorithm
Contexte biologique des algorithmes génétiques
La génétique détermine les facteurs
d'hérédité, les similitudes et les différences
entre une génération et sa progéniture.
Les gènes sont des fragments d'ADN qui
contiennent un code pour une protéine spécifique
qui fonctionne dans un ou plusieurs types de
cellules du corps. Les gènes sont l'unité de base
de l’hérédité
Les chromosomes sont des structures à Analogie
l'intérieur des cellules qui contiennent les Gènes <——> variables/valeurs
gènes d’un individu.
chromosomes <——> solutions
L'ensemble des gènes d'une espèce s'appelle
un Génome. Génome <-—> domaines des
variables
Contexte biologique des algorithmes génétiques
Croisement et Mutation
La recombinaison génétique « croisement »
Elle est connue sous le nom de « crossover ».
Elle se déroule toujours entre deux chromosomes
homologues et fait intervenir une cassure-réunion
de l’ADN entre des points strictement homologues
Mutation
Une mutation est une modification rare, accidentelle ou
provoquée, de l'information génétique dans le génome.
Selon la partie du génome touchée, les conséquences
d'une mutation peuvent varier.
Contexte biologique des algorithmes génétiques
Sélection
Application de la génétique dans le domaine Agricole
L'amélioration des animaux d’élevage
L'amélioration génétique des plantes
La sélection est basé sur la « fitness » des
individus
Algorithme Génétique
Codage des gènes
Un individu est un chromosome formé d’une chaîne de gènes
Codage binaire
1 0 1 0 0 0 1 0 1 0 0 1 1 0 0 1
binaire
3 4 1 7 5 8 2 6 6 4 1 5 7 2 3 8
permutation de chaine
A C C T G A T A 1,3 0,4 0,4 1,5 1,9 0,1 0 1,3
Exemples
Vert Rouge Bleu Vert Vert Bleu Rouge Rouge
4-queens
X1 X2 X3 X4 X1 X2 X3 X4
1 1
2 2
S E N D M O R Y - -
3 3 SEND
4 4
+ MORE N D - M - Y R O E S
3 2 3 2 3 1 4 2 ————-
fitness = 1 / (difference + 1)
fitness = sum(conflicts) = MONEY difference = MONEY - (SEND + MORE)
Algorithme Génétique
Un algorithme génétique comprend une population
(groupe) d'individus appelés chromosomes.
Les chromosomes, chacun composé de gènes qui
spécifient leurs traits, rivalisent pour résoudre un
problème.
La capacité d'un chromosome à résoudre un
problème est définie par une fonction de fitness.
Algorithme Génétique
L'algorithme génétique traverse les générations.
À chaque génération, les chromosomes les mieux adaptés sont
plus susceptibles d'être sélectionnés pour se reproduire.
Il existe également une probabilité à chaque génération que
deux chromosomes aient leurs gènes fusionnés. C'est ce qu'on
appelle le croisement.
Et enfin, il y a la possibilité à chaque génération qu'un gène
dans un chromosome puisse muter (changer de manière
aléatoire).
Algorithme Génétique : organigramme
Début
Creation de la population initial
Calculer les fitness appropriées f1= 5 f2= 2 f3=1 f4=3 f5=4
Appliquer les opérateurs génétiques:
Sélection
Croisement
Mutation
Population=Nouvelle génération
Croisement
y a-t-il une
Exemple
non oui
meilleur valeur de la retourner la meilleur de Mutation
fitness ou la limite individu
atteinte?
Algorithme génétique
Les algorithmes génétiques sont généralement réservés
aux problèmes complexes sans solutions faciles.
satisfaction (CSPs clairsemés où les plusieurs
solutions sont possibles)
Optimisation
Implementation en Python
Télécharger le fichier template sur la page du cours
