Click here to load reader
Upload
phamdien
View
212
Download
0
Embed Size (px)
Citation preview
Algorithmes
Génétiques… ET COMBATS DE DAMES.
Objectifs du cours
Présentation du problème des n-dames
Présentation des algorithmes génétiques
Résolution du problème des n-dames (ou n-reines)
Présentation de quelques autres applications
Introduction à ParadisEO
Le problème des n-reines
Question : sur un échiquier de taille n*n, combien peut-on placer de
reines sans qu’elles ne s’attaquent entre elles ?
Le problème des 8-reines
Sur un échiquier de taille 8x8, comment placer les 8 reines ?
?
Le problème des 8-reines
Sur un échiquier de taille 8x8, comment placer les 8 reines ?
Réponse : il existe 92 solutions, dont 12 uniques (sans rotation/symétrie)
Le problème des 8-reines
Le problème des 8-reines
Galère à faire à la main
Programmation :
Arbre de solutions : long à parcourir
Algorithme de résolution : dur à mettre en place
Idée : algorithme génétique !
Les algorithmes génétiques
Basé sur les théories concernant l’intelligence humaine :
Théorie de l’évolution (Darwin)
Théorie de la sélection naturelle (Weismann)
Concepts de génétique (Mendel)
Concept général :
Partir d’une population d’individus (solutions), et les faire évoluer afin
d’obtenir l’individu optimal (la solution optimale)
Les algorithmes génétiques
On commence avec un ensemble de k solutions
Population de k chromosomes
On évalue les chromosomes avec une fonction de fitness
Fonction d’adaptation
Les successeurs sont chacun générés avec trois étapes
Sélection des deux parents
Croisement des deux parents
Mutation du chromosome
Algorithme génétique
population = ensemble{n1,n2,…nk} généré aléatoirement de chromosomes
Pour t=1…Nb_itérations :
nouvelle_population = {}
Pour i=1…k:
n = chromosome pris dans population avec probabilité selon F(n)
n’ = chromosome pris dans population-{n} avec probabilité selon F(n’)
n* = croisement(n,n’)
mutation(n*)
nouvelle_population = nouvelle_population + n*
population = nouvelle_population
Retourner n qui maximise F(n)
Application au problème des 8
reines : modélisation
X
X
X
X
X X
X X
67247588
Comment modéliser une solution?
Comment évaluer une solution (fonction de fitness) ?
F(A) = nombre de paires de reines qui ne s’attaquent pas.
min( F(A) ) = 0
max( F(A) ) = 8*7/2 = 28
Application au problème des 8
reines : sélection
Valeurs (exemple) :
F(n1) = 12
F(n2) = 16
F(n4) = 5
Probabilités de sélection, proportionnelles à F(n) :
P(n1) = 12 / (12+16+5) = 0.37
P(n2) = 16 / (12+16+5) = 0.48
P(n3) = 5 / (12+16+5) = 0.15
Note: il existe de nombreuses méthodes pour sélectionner, on aurait par
exemple pu exclure tout chromosome avec F(n) < 10, aussi.
Application au problème des 8
reines : croisement
X
X
X
X
X X
X X
X
X
X X
X X
X X
N = 67247588 N’ = 75251447
X
X
X X
X
X
X X
N* = 67251447
Application au problème des 8
reines : mutation
X
X
X X
X
X
X X
67251447
X
X
X X
X
X
X X
67351447
Reprenons le tout …
24748552
32752411
24415124
32543213
Population
initialeFitness
24
23
20
11
32752411
24748552
32752411
24415124
Sélection
32748552
24752411
24415124
32543213
Croisement
32748152
24752411
24215124
32544213
Mutation Fin
MEILLEUR
k itérations
Autres applications
Téléchargement de films : sélection du meilleur groupe de serveurs
Chromosomes : Identifiants des serveurs sélectionnés
F(n) : vitesse de téléchargement
Applications industrielles
Motorola, pour tester une application après modifications de code
NASA, pour la mission d’exploration de Mars de Pathfinder
Sony, pour AIBO, robot qui apprend à marcher
Exemple concret : Super Mario Bros
Objectif : faire avancer Mario le plus loin
possible dans le niveau
Etat n : liste des actions de Mario
action des boutons de la manette
F(n) : distance parcourue (par exemple)