Les algorithmes évolutionnistes

Les algorithmes évolutionnistes

Stéphane Legrand

ENG221

Mai 2014

Stéphane Legrand (ENG221) Les algorithmes évolutionnistes Mai 2014 1 / 14

1. Les mécanismes naturels

2. Structure d’un algorithme évolutionniste

3. Un exemple sur un problème de classement

4. Avantages et inconvénients

5. Pour quelles utilisations

6. Conclusion


Les mécanismes naturels

La génétiquePatrimoine génétique hérité

Diversité

La théorie de l’évolutionLes mieux adaptés survivent, se reproduisent et transmettent leursgènes

Sélection naturelle fait le tri entre variations favorables ou non

Concept d’algorithme évolutionnisteS’inspire de ces mécanismes


Structure d’un algorithme évolutionniste

Sélection

Reproduction

Mutation

Evaluation

Nouvellepopulation

Population initiale+ Evaluation

Solution(s)(Hall of fame)


Exemple : classement d’animaux

Jeu de donnéesListe d’animaux sous la forme d’un fichier CSV

Nom de l’animal, 16 attributs (à plumes, vertébré, prédateur, nbpattes...) et sa classe (mammifère, poisson, batracien...)

ObjectifDécouvrir des règles de classementSI attribut=valeur ET SI...ET SI...ALORS classe


Modèle informatique

Un individu = Une règle

. . . 0.8 1 [0,1] . . . 0.5 0 [1,0,0,0,0,0]

P Op V P Op V

Gène 12 Gène 16

SI nageoires = FAUX ET SI pattes <> 0



L’évaluation mesure la performance d’un individuPour chaque animal, on évalue la justesse du classement donné parl’individu

Plus la règle s’avère pertinente, plus l’individu sera jugé performant



ReproductionParents

G1 G2 G3 G4 G5

Ga Gb Gc Gd Ge

Enfants

G1 G2 Gc Gd Ge

Ga Gb G3 G4 G5

MutationAvant

G1 G2 G3 G4 G5

Après

G1 G2 G3’ G4 G5


Exécution

0 10 20 30 40 50

Generation

0.0

0.2

0.4

0.6

0.8

1.0E

valu

atio

n(fi

tnes

s)

MoyenneMaximum


RésultatsIndividu numéro 1 (fitness = 1.0)

plumes = faux ET ovipare = vraiET lait = faux ET aquatique = vraiET vertébré = vrai ET poumons = vraiET nageoires = faux

Individu numéro 2 (fitness = 1.0)ovipare = vrai ET aquatique = vrai

ET dents = vrai ET vertébré = vraiET nageoires = faux ET taille chat = fauxET pattes <> 0

Individu numéro 3 (fitness = 1.0)ovipare = vrai ET aquatique = vrai

ET dents = vrai ET vertébré = vraiET nageoires = faux ET taille chat = fauxET pattes <> 8


Avantages et inconvénients

Les +Résolution problèmescomplexes

Générique et adaptable

Parallélisation

Pas d’a priori

Les -Paramétrage délicat

Part d’aléatoire

Pas optimal

Peut être assez lent

Quand s’arrêter ?


Pour quelles utilisations

Conception acoustique, aéronautique, électronique, mécanique

Jeu d’échecs

Tactiques militaires

Reconnaissance de formes

Robotique

Recherche de routes optimales

Nouvelles molécules chimiques

Marchés financiers

Marketing

Planning et allocation de ressources


Conclusion

Efficace dans la pratique

Complémentaire aux algorithmes "classiques"

Peut conduire à des solutions surprenantes/novatrices


Merci de votre attention

Questions ?


Software

Les algorithmes évolutionnistes