mémoire licence aribi 2014.pdf


Aperçu du fichier PDF memoire-licence-aribi-2014.pdf - page 3/48

Page 1 2 34548



Aperçu texte


`
TABLE DES MATIERES

2
2 Approche mim´
etique

17

2.1

Introduction a` l’algorithme M´em´etique (MA) : . . . . . . . . . . . . . . . . . . . 17

2.2

Explication : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.3

Croisement [th997] : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.4

2.5

2.3.1

Le croisement a` un point : . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.3.2

Le croisement a` deux points . . . . . . . . . . . . . . . . . . . . . . . . . 19

Mutation : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4.1

Mutation binaire : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.4.2

Mutation r´eelle : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.4.3

Mutation non uniforme :

Recherche locale : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.5.1

2.6

. . . . . . . . . . . . . . . . . . . . . . . . . . 21

Basic de la recherche locale : . . . . . . . . . . . . . . . . . . . . . . . . . 21

Algorithme de la recherche locale : . . . . . . . . . . . . . . . . . . . . . . . . . 22

3 Description du probl`
eme :

24

3.1

Aspect G´en´erale :

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

3.2

Les contraintes dures : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.3

Les Contraintes de Pr´ef´erence (souples) : . . . . . . . . . . . . . . . . . . . . . . 26

4 R´
esolution et Structures

27

4.1

Les structures de donn´ees utilis´ees : . . . . . . . . . . . . . . . . . . . . . . . . . 27

4.2

Les contraintes : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

4.3

4.2.1

Contrainte souple de la solution : . . . . . . . . . . . . . . . . . . . . . . 29

4.2.2

Contraintes dures de la solution : . . . . . . . . . . . . . . . . . . . . . . 31

L’algorithme memetique : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.3.1

Cr´eation de la population initiale : . . . . . . . . . . . . . . . . . . . . . 32

4.4

Croisement : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4.5

Mutation : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

4.6

La recherche locale : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

5 Impl´
ementation

39

5.1

Les outils utilis´es dans la r´ealisation de cette application :

5.2

Pr´esentation de l’application : . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

Pr´esent´e par : A.M et B.W

. . . . . . . . . . . . 39

UMBB