Algorithmes Génétiques - castejon.iiens.netcastejon.iiens.net/gene.pdf · Les algorithmes...

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)