Etude de l'influence de la neutralité sur la dynamique des Algorithmes Génétiques Francis BONNIN Soutenance du stage de DEA. Encadreurs : Philippe Collard

Etude de l'influence de la neutralité sur la dynamique des Algorithmes Génétiques

Francis BONNIN

Soutenance du stage de DEA.

Encadreurs : Philippe Collard & Manuel Clergue

1Université de Nice - Sophia Antipolis

03 Juillet 2000


03 Juillet 2000

1. Introduction

• Algos génétiques : inspirés de la nature

• Algos génétiques : technique d’optimisation

• Théorie biologique : la neutralité (dérive aléatoire > pression sélective)

Objectif : étudier l’influence de la neutralité intrinsèque sur la dynamique d’un AG.

1. Introduction

• Phénotype Génotype

• Fitness valeur d’adaptation : sélection des individus

• Action d’opérateurs génétiques

2. Etat de l’art2.1 Algorithmes génétiques


03 Juillet 2000

1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 11 0 0 1 10 0

0

1

01 1 1 10 0 1 0 0 10 0 10

Croisement Mutation

2. Etat de l’art


03 Juillet 2000

• Population : ensemble d’individus

• générations :

• Critère d’arrêt : qualité des solutions, nombre de générations, individus identiques, ...

Evaluation des solutions

Décodage des solutions

Sélection des individus

Croisement et mutation

2.1. Algorithmes génétiques

• Points d’iso-fitness réseaux de neutralité

• création de diversité

• un nouvel opérateur : l’opérateur neutre

• avantage de la mutation sans les inconvénients

• difficulté : trouver l’opérateur pour une neutralité intrinsèque

2.2 Concept de neutralité


03 Juillet 2000

L’opérateur neutre est un moyen d’utiliser de la connaissance.

2.2. Concept de neutralité


03 Juillet 2000

3. Présentation du travail3.1 Méthodologie de travail

Documentation sur l’état de l’art

valider des hypothèses (ou observer un comportement à l’aide de simulations

programmation en C. Utilisation de la librairie SUGAL

étude de la neutralité de divers problèmes

tests volumineux car les AG sont non déterministes

3. Présentation du travail


03 Juillet 2000

3.2 La neutralité sur un exemple

Etude du problème du TSP concentrique :

3.2 La neutralité sur un exemple

• trouver un problème contenant une neutralité intrinsèque• adapter le problème à l’AG• trouver un opérateur neutre efficace• trouver un opérateur de croisement adapté

But :


03 Juillet 20003.2 La neutralité sur un exemple

Mauvais résultats :pb : croisement mal adaptéchangement d’op de croisement. PMX croisement glouton

L’opérateur de symétrie dégrade les performances :pb : mauvaise implémentation.Ajout d’une inversion.(adéquation entre le croisement et l’op neutre)

Bons résultats. Amélioration grâce à l’op neutre

tests

tests

tests


03 Juillet 2000

4. Travaux réalisés

Etude de fonctions simples :• Unitation• Alternation

Etude du rôle du croisement dans la neutralité

Etude de classes de fonctions paramétrées par le degré de neutralité• Fonctions d’Unitation Neutres• Fonctions d’Alternation Neutres

Etude de fonctions plus complexes :• problème du TSP concentrique• problème des rectangles chromatiques

4. Travaux réalisés


03 Juillet 20004.1 Fonction d’Unitation

4.1 Fonction d’Unitation

Les chromosomes 0100110 et 1110000 ont même fitness• croisement classique à un site• opérateurs neutres : permutation et inversion

1 10 01 0 1 0 1 10 00 1 0 1 1 10 01 1 0 0

Après Inversion Chromosome d’origine Après Permutation

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0 50 100 150 200

Fit

nes

s

Generation

Fonction d'unitation (Inversion+Mutation): Fitness Max

Taux = 0.00Taux = 0.02Taux = 0.08Taux = 0.50Taux = 1.00

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0 50 100 150 200

En

tro

pie

Generation

Fonction d'unitation (Inversion+Mutation) : Diversite Genotypique



03 Juillet 2000

4.2 Fonction d’Alternation

Les chromosomes 0100110 et 0010100 ont même fitnessPlus difficile :

Croisement identique.Opérateur neutre identique : utilisation d’un mapping pour passer de l’Alternation vers l’Unitation

• épistasie• solutions de fitness voisines très différentes (000010101 et 000001010)

1 1 1 10 0

0 1 0 0 1 1 0

1 0 0 1 1 00

On restaure le premier gene

1 1 1 10 0Alternation

Unitation

On sauvegarde le premier gene

Unitation

Alternation

inv inv invinv

4.1 Fonction d’Alternation


03 Juillet 20004.1 Fonction d’Alternation

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0 50 100 150 200

Fitn

ess

Generation

Fonction d'alternation (Inversion+Mutation): Fitness Max


0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0 50 100 150 200

Ent

ropi

e

Generation

Fonction d'alternation (Inversion+Mutation) : Diversite Genotypique


Plus le taux d’inversion est élevé, plus la diversité est élevée

Sans l’opérateur neutre, l’AG converge vers un minimum local


03 Juillet 20004.3 Rôle du croisement dans la neutralité

4.3 Rôle du croisement dans la neutralité

La neutralité n’apporte aucune nouvelle solutionLe croisement en crée grâce à des recombinaisonsTests sur l’unitation en faisant varier le taux de croisement :

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0 50 100 150 200

Fitn

ess

Generation

Fonction d'unitation avec variation du croisement (Inversion=0.0 + Mutation) : Fitness Maximale

croisement = 0.00croisement = 0.02croisement = 0.10croisement = 0.20croisement = 0.40croisement = 0.70croisement = 1.00

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0 50 100 150 200

Fitn

ess

Generation

Fonction d'unitation avec variation du croisement (Inversion=0.5 + Mutation) : Fitness Maximale

croisement = 0.00croisement = 0.02croisement = 0.10croisement = 0.20croisement = 0.40croisement = 0.70croisement = 1.00


03 Juillet 20004.4 Fonctions d’Unitation neutres

4.4 Fonctions d’Unitation neutres

Up x x x x xni

i i2 2 3

1

11...

Les deltai sont calculés en fonction d’une probabilité psi p=0 : unitation (distribution binomiale)si p=1 : tous les chromosomes ont une fitness différente

0

50

100

150

200

250

300

0 0.2 0.4 0.6 0.8 1

Nom

bre

de p

heno

type

s id

entiq

ues

Fitness

Evolution de la distribution des valeurs de fitness normalisees en fonction de p (10 Bits, Seed = 5)

p = 0.000000p = 0.500000p = 1.000000

Distribution des réseaux de neutralité


03 Juillet 20004.4 Fonctions d’Unitation neutres

Opérateur neutre de l’unitation modifié.

Tests pour différentes valeurs de p :

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0 50 100 150 200

Fitn

ess

norm

alis

ee

Generation

Fonction d'unitation neutre (1 tentative, taux de neutralite = 0.5, mutation) : Fitness Maximale

P = 0.00P = 0.02P = 0.10P = 0.20P = 0.40P = 0.80P = 1.00

Plus p est petit plus l’AG converge rapidementIl vaut mieux avoir de gros réseaux que de petits réseaux.


03 Juillet 20004.5 Fonctions d’Alternation neutres

4.5 Fonctions d’Alternation neutres

Ap x x x x x xni

i i i2 2 3 1

1

11...

Opérateur neutre du même type que l’Unitation neutre.

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0 50 100 150 200

Fitn

ess

Generation

Fonction d'alternation neutre (10 tentatives, taux de neutralite = 0.5) : Fitness Maximale

P = 0.00P = 0.02P = 0.10P = 0.20P = 0.40P = 0.80P = 1.00


03 Juillet 20004.6 problème du TSP concentrique

4.6 problème du TSP concentrique

NP-completproblème de minimisationcodage sur les entiersopérateur neutre de symétriecroisement glouton

30

31

32

33

34

35

36

0 50 100 150 200 250 300 350 400

Fitn

ess

Generation

TSP3Cercles(24 villes , symetrieInv2+mutation, pop=200, seed=200, TSP)(8, 1, 2, 3): Fitness Minimale

Taux = 0.000Taux = 0.500Taux = 1.000

Croisement des courbes


03 Juillet 20004.7 problème des rectangles chromatiques

4.7 problème des rectangles chromatiques

1 1 1 2 20 2 2 0 10 0 1 1 22 2 2 1 12 0 1 0 2

grille avec 0 conflit

0 2 2 2 11 2 2 1 20 0 1 2 21 1 0 2 02 1 2 1 0

grille avec 1 conflit

But : minimiser le nombre de rectangles ayant les 4 coins de la même couleur

Problème étudié : un tableau de taille 10*10 avec 3 couleurscodage sur les symboles, ligne après ligne.Opérateur neutre : permutations de lignesCroisement : coupure horisontale du tableau

Echec des tests ...

Opérateur neutre augmenté par la connaissanceCroisement : coupure d ’un coin du tableau

Inachevé ...

2 2 1 1 2 0 1 1 0 01 1 0 0 2 2 2 1 0 20 0 1 2 0 1 2 2 1 10 2 0 2 1 2 0 1 1 02 1 2 2 1 1 1 0 0 21 0 2 0 2 2 1 2 1 00 2 2 0 1 0 2 1 2 11 2 0 1 0 1 0 2 2 21 0 0 2 2 0 1 0 2 12 1 1 0 0 2 0 0 2 1

7 conflits


03 Juillet 2000

5. Conclusion5. Conclusion

• Bonne combinaison d’op neutre et de croisement

• Gains en vitesse de convergence ou en qualité des solutions trouvées

• Difficulté de trouver ces opérateurs

• opérateur neutre = utilisation de la connaissance sur le problème

• nécessaire pour être compétitif

• utilité pratique de l’opérateur neutre.

Perspectives : Tests sur des applications plus réalistesEtude plus approfondie sur le concept même de neutralité

Documents

Etude de l'influence de la neutralité sur la dynamique des Algorithmes Génétiques Francis BONNIN Soutenance du stage de DEA. Encadreurs : Philippe Collard