17

Click here to load reader

Algorithmes Génétiques - castejon.iiens.netcastejon.iiens.net/gene.pdf · Les algorithmes génétiques Basé sur les théories concernant l’intelligence humaine :

Embed Size (px)

Citation preview

Page 1: Algorithmes Génétiques - castejon.iiens.netcastejon.iiens.net/gene.pdf · Les algorithmes génétiques Basé sur les théories concernant l’intelligence humaine :

Algorithmes

Génétiques… ET COMBATS DE DAMES.

Page 2: Algorithmes Génétiques - castejon.iiens.netcastejon.iiens.net/gene.pdf · Les algorithmes génétiques Basé sur les théories concernant l’intelligence humaine :

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

Page 3: Algorithmes Génétiques - castejon.iiens.netcastejon.iiens.net/gene.pdf · Les algorithmes génétiques Basé sur les théories concernant l’intelligence humaine :

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 ?

Page 4: Algorithmes Génétiques - castejon.iiens.netcastejon.iiens.net/gene.pdf · Les algorithmes génétiques Basé sur les théories concernant l’intelligence humaine :

Le problème des 8-reines

Sur un échiquier de taille 8x8, comment placer les 8 reines ?

?

Page 5: Algorithmes Génétiques - castejon.iiens.netcastejon.iiens.net/gene.pdf · Les algorithmes génétiques Basé sur les théories concernant l’intelligence humaine :

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)

Page 6: Algorithmes Génétiques - castejon.iiens.netcastejon.iiens.net/gene.pdf · Les algorithmes génétiques Basé sur les théories concernant l’intelligence humaine :

Le problème des 8-reines

Page 7: Algorithmes Génétiques - castejon.iiens.netcastejon.iiens.net/gene.pdf · Les algorithmes génétiques Basé sur les théories concernant l’intelligence humaine :

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 !

Page 8: Algorithmes Génétiques - castejon.iiens.netcastejon.iiens.net/gene.pdf · Les algorithmes génétiques Basé sur les théories concernant l’intelligence humaine :

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)

Page 9: Algorithmes Génétiques - castejon.iiens.netcastejon.iiens.net/gene.pdf · Les algorithmes génétiques Basé sur les théories concernant l’intelligence humaine :

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

Page 10: Algorithmes Génétiques - castejon.iiens.netcastejon.iiens.net/gene.pdf · Les algorithmes génétiques Basé sur les théories concernant l’intelligence humaine :

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)

Page 11: Algorithmes Génétiques - castejon.iiens.netcastejon.iiens.net/gene.pdf · Les algorithmes génétiques Basé sur les théories concernant l’intelligence humaine :

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

Page 12: Algorithmes Génétiques - castejon.iiens.netcastejon.iiens.net/gene.pdf · Les algorithmes génétiques Basé sur les théories concernant l’intelligence humaine :

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.

Page 13: Algorithmes Génétiques - castejon.iiens.netcastejon.iiens.net/gene.pdf · Les algorithmes génétiques Basé sur les théories concernant l’intelligence humaine :

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

Page 14: Algorithmes Génétiques - castejon.iiens.netcastejon.iiens.net/gene.pdf · Les algorithmes génétiques Basé sur les théories concernant l’intelligence humaine :

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

Page 15: Algorithmes Génétiques - castejon.iiens.netcastejon.iiens.net/gene.pdf · Les algorithmes génétiques Basé sur les théories concernant l’intelligence humaine :

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

Page 16: Algorithmes Génétiques - castejon.iiens.netcastejon.iiens.net/gene.pdf · Les algorithmes génétiques Basé sur les théories concernant l’intelligence humaine :

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

Page 17: Algorithmes Génétiques - castejon.iiens.netcastejon.iiens.net/gene.pdf · Les algorithmes génétiques Basé sur les théories concernant l’intelligence humaine :

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)