Algorithmes Evolutionnaires

PROFESSEUR: MARIE-JO HUGUET

AHMED KHASSIBA & MONCEF ILIES NASRI M2R-IT RO

NOVEMBRE 2014

Problèmes d’optimisation. Définition:

𝑀𝑀𝑀 𝑓 𝑥 ; 𝑥 ∈ 𝑆

Souvent les problèmes d’optimisation sont difficiles à résoudre.

Beaucoup de problèmes d’optimisation réels sont prouvés NP-difficiles.

Inefficacité des méthodes exactes pour de grandes instances. Plusieurs siècles de temps d’exécution.

Solution ?

Sacrifier l’optimalité pour le temps d’exécution !

2

Introduction aux méta- heuristiques

Heuristiques Simples, rapides, basées sur le bon sens.

Un seul mot d’ordre « Eurisiko » : je trouve.

Est-ce vraiment tout ce qu’on peut faire ?

Les Meta-heuristiques (Meta : Au-delà, plus haut niveau) : Fred Glover 1986.

L’adaptabilité( méthodes génériques).

Alternance local/global.

Aptitude à Surpasser les minima locaux.

Deux catégories principales:

A trajectoire.

A population de solution(évolutionnaires).

3

Introduction à l’algorithme génétique

Créativité: la capacité d’harmoniser des idées de domaines différents, parfois très éloignés. (John S. Liu)

4

sources d’inspiration Phénomènes physiques ou

biologiques sources d’inspiration de nombreux algorithmes.

algorithme

Réseaux de neurones

Recuit simulé

Algorithmes évolutionnaires

origine Fonctionnement du

cerveau humain

Thermodynamique

Évolution darwinienne des populations

biologiques

5

Théorie de Darwin

Une source d’inspiration != justification

6

Apparition d’espèces adaptées au milieu

Sélection naturelle:

les plus adaptés survivent et se reproduisent

Variations non dirigées du

matériel génétique

Terminologie et notation

Modèle mathématique

Fonction objectif

Point de l’espace de recherche

P-uplet de points

Boucle de l’algorithme

Représentation

Perfomance (fitness)

Individu

P-uplet d’individus: Population de taille P

génération

7

Terminologie et notation

Espace phénotypique

Espace de recherche initial

Fonction objectif

Point de l’espace de recherche

Espace génotypique

Espace de représentation

Perfomance (fitness)

Codage des individus = chromosomes

8

Exemple 9

0

1000

2000

3000

4000

5000

1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35

f(x)

f(x)

•Max f(x) = x3 - 60 * x2 + 900 * x +100

Fonction objectif

•x entier dans [0,31]

Domaine

Exemple

Espace phénotypique

x -> x3 - 60 * x2 + 900 * x +100

x entier dans [0,31]

Espace génotypique

Performace (fitness)

Individu codé en chaîne de 5 bits

10

Exemple

Individu Chromosome x f(x) I1 11100 28 212 I2 01111 15 3475 I3 10111 23 1227 I4 00100 4 2804

Moyenne 1929,5

11

•Max f(x) = x3 - 60 * x2 + 900 * x +100

Fonction objectif

•x entier dans [0,31]

Domaine

Population de taille 4

Le squelette Début

Initialisation

Evaluation

Sélection des parents

opérateurs de variation

Evaluation des fils

remplacement

Fin

12

Début

Initialisation

Evaluation

Sélection des parents

opérateurs de variation

Evaluation des fils

remplacement

Fin

Initialisation Choisir P individus de l’espace

de recherche, soit par tirage aléatoire avec

une probabilité uniforme sur l’espace de recherche génotypique,

soit par des heuristiques de construction.

Dans le premier cas, ne dépend pas de la fonction objectif

Permet l’exploration (diversification) de l’espace de recherche.

13

Initialisation Exemple:

Générer aléatoirement 4 chaînes de 5 bits

Une population initiale de 4 individus:

Individu Chromosome x I1 11100 28 I2 01111 15 I3 10111 23 I4 00100 4

Début

Initialisation

Evaluation

Sélection des parents

opérateurs de variation

Evaluation des fils

remplacement

Fin

14

Début

Initialisation

Evaluation

Sélection des parents

opérateurs de variation

Evaluation des fils

remplacement

Fin

Evaluation Calculer la performance de tous

les individus

Étape coûteuse en CPU

Exemple:

Individu Chromosome x f(x)

I1 11100 28 212

I2 01111 15 3475

I3 10111 23 1227

I4 00100 4 2804

Moyenne 1929,5

15

Sélection des parents Choisir les individus les plus performants

(au sens de la fonction objectif) : les parents.

2 types de sélection: Déterministe: élitiste

Stochastique: Tirage de roulette

Sélection par le rang

Sélection par tournoi

Permet l’exploitation (intensification) des individus les plus performants

Début

Initialisation

Evaluation

Sélection des parents

opérateurs de variation

Evaluation des fils

remplacement

Fin

16

Sélection des parents Exemple:

sélection déterministe de 2 parents Début

Initialisation

Evaluation

Sélection des parents

opérateurs de variation

Evaluation des fils

remplacement

Fin

Individu Chromosome x f(x)

I1 11100 28 212

I2 01111 15 3475

I3 10111 23 1227

I4 00100 4 2804

Moyenne 1929,5

17

Opérateurs de variation Appliquer des opérateurs de variation sur les

parents sélectionnés pour générer de nouveaux individus: les enfants.

Avec des probabilités associées.

Étape spécifique au génotype.

2 opérateurs: Croisement: opérateur binaire (ou n-aire)

Mutation: opérateur unaire

Début

Initialisation

Evaluation

Sélection des parents

opérateurs de variation

Evaluation des fils

remplacement

Fin

18

Opérateurs de variation (croisement) opérateur binaire (ou n-aire): échange de

matériel génétique entre les parents.

Permet l’exploitation des “bonnes” parties du génotype des parents.

Types: Un ou plusieurs points de croisement.

Propriétés: hérédité, validité.

Début

Initialisation

Evaluation

Sélection des parents

opérateurs de variation

Evaluation des fils

remplacement

Fin

19

Opérateurs de variation (croisement) Croisement à un point

I2 0 1 1 1 1

I4 0 0 1 0 0

Fils 2 0 0 1 1 1

Fils 1 0 1 1 0 0

20

Début

Initialisation

Evaluation

Sélection des parents

opérateurs de variation

Evaluation des fils

remplacement

Fin

Opérateurs de variation (croisement) Croisement à 2 points

I2 0 1 1 1 1

I4 0 0 1 0 0

Fils 3 0 0 1 0 1

Fils 4 0 1 1 1 0

Début

Initialisation

Evaluation

Sélection des parents

opérateurs de variation

Evaluation des fils

remplacement

Fin

21

Opérateurs de variation (mutation) Mutation: opérateur unaire

tirer aléatoirement un gène dans le chromosome et le remplacer par une valeur aléatoire.

Permet l’exploration de l’espace de recherche.

Propriétés: Ergodicité: toute solution est atteignable.

Localité: analogue aux opérateurs de voisinage.

Début

Initialisation

Evaluation

Sélection des parents

opérateurs de variation

Evaluation des fils

remplacement

Fin

22

Opérateurs de variation (mutation) opérateur unaire:

tirer aléatoirement un gène dans le chromosome et le remplacer par une valeur aléatoire.

Fils 2 0 0 1 1 1

Fils 2 0 0 1 1 0

Début

Initialisation

Evaluation

Sélection des parents

opérateurs de variation

Evaluation des fils

remplacement

Fin

23

Fils 1 0 1 1 0 0

Fils 1 0 1 1 1 0

Evaluation des fils Début

Initialisation

Evaluation

Sélection des parents

opérateurs de variation

Evaluation des fils

remplacement

Fin

Calculer la performance des fils.

24

Individu Chromosome x f(x) Fils 1 01110 7 3803 Fils 2 00110 6 3556

Parents I2 01111 15 3475 I4 00100 4 2804

Remplacement Créer une nouvelle population à partir des

enfants et/ou des «vieux» parents sur la base de l’ancienne population.

analogue à la sélection: Déterministe: élitiste: éliminer les individus les

moins performants

Stochastique

Début

Initialisation

Evaluation

Sélection des parents

opérateurs de variation

Evaluation des fils

remplacement

Fin

25

Remplacement • Exemple: Déterministe: élitiste: éliminer les individus

les moins performants

Début

Initialisation

Evaluation

Sélection des parents

opérateurs de variation

Evaluation des fils

remplacement

Fin

Individu Chromosome x f(x)

I1 11100 28 212

I2 01111 15 3475

I3 10111 23 1227

I4 00100 4 2804

Moyenne 1929,5

Individu Chromosome x f(x)

Fils 2 00110 6 3556

I2 01111 15 3475

Fils 1 01110 7 3803

I4 00100 4 2804

Moyenne 3409,5

26

Condition d’arrêt • Statique

Limite de CPU

Nombre de génération

• Adaptative

Nombre de génération sans amélioration

Niveau de performance souhaité

Début

Initialisation

Evaluation

Sélection des parents

opérateurs de variation

Evaluation des fils

remplacement

Fin

27

Limites des AG Résumé de l’AG:

Création d’une population de départ. Faire évoluer la population

Initialisation, mutation : diversification. Sélection, croisement : intensification.

Solution finale: Meilleur individu de la population. Remarques ?

Très peu d’information sur le problème à traiter est utilisée! Optimisation : Performance = Information. Cause du début timide de cette méthode. Par quoi compenser ce manque d’information?

28

Intensification Diversification

Renaissance des AEs

Nouvel opérateur : EDUCATION.

Ces nouveaux AEs sont baptisés : Algorithmes mémétiques.

29

Evaluation des fils remplacement Fin Début Initialisation Evaluation EDUCATION opérateurs de

variation Sélection des

parents

Concept des AMs Qu‘est-ce qu’un méme ? AG + recherche locale= Algorithme mémétique.

Pourquoi changer de nom ?

Transmission du méme. L’information.

Preuve réele : Internet.

30

Individu Chromosome I1 11100 I2 01111 I3 10111 I4 00100

L’éducation Notion de voisinage.

Relation entre deux solutions. Caractéristiques en communs. Spécifique à chaque problème.

Ex : le problème de voyageur de commerce (TSP).

Important :la taille du voisinage doit être maîtriser!

31

Codage de solution du TSP Une tournée :

Chromosome:

Fitness : Distance totale parcourue.

32

1 2 3 4

1

2

3

4 5

6

5 6

Générateurs de voisinage TSP. 2-opt :

Swap :

Changement de position :

Or-exchange :

1 2 3 4 5

1 2 3 4 5

1 2 3 4 5

33

1 2 3 4 5 6 5 2 4 3

Que-est-ce qui change par rapport au AG ?

Le paramétrage de la méthode (inconvénients des Meta) :

Population plus petite.

Moins d’itération, même résultat.

Le paramétrage de la recherche locale: Le méme trop puissant ?!

Faire plus attention à conserver la diversification.

L’ordre dans le quel les voisinages sont visités(imbriqués).

34

Implémentation et résultats

0

2

4

6

8

10

12

14

16

18

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Eloi

gnem

ent d

e la

BKS

en

%

Les instances, la moyenne et écart type

Comparaison des meilleurs résultats MA/GRASP

Mémétic Algorithm GRASP (Prins et al, 2006)

L’éloignement moyen de GRASP et MA est de 3.6% En revanche L’écart type de GRASP est de 4.34% MA est de 2.57%. et pour >100 sommets, l’écart type GRASP 4.69% et MA 2.15%. La différence max en faveur de GRASP est de 3.82% et celle en faveur de MA est de 9.07%.

35

A retenir pour une bonne implémentation AM meilleur que AG ? (No Free Lunch Theorem) Bon codage solution/chromosome :

maniable.

Respect des contraintes du problème originale.

Intégrité de l’information.

génération : Remplacer l’aléatoire par des méthodes plus élaborées.

Sélection/Elimination : trouver l’équilibre stochastique/déterministe. Croisement : Réparer les fils engendrés. Education : implémenter plusieurs générateurs de voisinages. Régler : Taille population, critères d’arrêt. Pour valider : Tester sur des instances usuelles. Mot d’ordre: Essayer, essayer et encore essayer !

36

MERCI DE VOTRE ATTENTION

THANK YOU FOR YOUR ATTENTION

اإلصغاءعلى حسن المتابعة و شكراً

37

références 38

http://www.enseignement.polytechnique.fr/profs/informatique/Eric.Goubault/poly/cours009.html

http://www.lifl.fr/~derbel/ueOC/cours/

http://wikipedia/meta-heuristiques