Liste des abréviations
TTP : Time Tabiling Problem
UMBB : Université M'HAMED BOUGUERRA - Boumerdes
TD :Travaux Dirigés
TP :Travaux Pratiques
TS : Tabou Search
GRASP : Greedy Randomized Adaptative Search Procedure
GA :Genetic Algorithms
EA : Evolutionary Algorithm
MOEA : MultiObjectif Evolutionary Algorithm
SPEA : Strenght Pareto Evolutionary Algorithm
IBEA : Indicator Based Evolutionary Algorithm
NSGA : Non-dominated Sorting Genetic Algorithm
PM : Population Management
PEA : Parallele Evolutionary Algorithm
cPEA : cellular Parallele Evolutionary Algorithm
dPEA : distributed Parallele Evolutionary Algorithm
SISD :Single Instruction Single Data
SIMD : Single Instruction Multiple Data
MISD : Multiple Instruction Single Data
MIMD : Multiple Instruction Multiple Data
iii
Table des matières
Résumé i
Liste des abréviations ii
liste de figures v
INTRODUCTION GÉNÉRALE 1
I LE PROBLÈME D'EMPLOI DE TEMPS 2
I.1 La complexité Temporelle 2
I.2 Types des problèmes 3
I.3 Le problème d'emploi de temps (TTP) 4
I.4 Classification des problèmes d'emplois de temps 5
I.5 Une instance de problème TTP 5
I.6 L'aspect combinatoire du problème TTP 7
I.7 Conclusion 7
II METHODES D'OPTIMISATION 8
II.1 Classification des méta-heuristiques 9
II.2 Exposition de quelques méta-heuristiques 9
II.2.1 La méthode de descente 9
II.2.2 Le recuit simulé 10
II.2.3 La méthode tabou 10
II.2.4 Les algorithmes génétiques 11
II.2.5 Les algorithmes de colonies de fourmis 11
II.2.6 La méthode GRASP 13
II.2.7 La méthode d'évolution différentielle
13
II.2.8 Discussion 14
II.3 Les algorithmes évolutionnaires 15
II.3.1 Terminologie spécifique aux EAs 15
II.3.2 Analyse de processus de recherche des AEs 16
II.3.3 Procédures de sélection 16
II.3.4 Les schémas d'évolution 17
II.4 Notion préliminaires 17
II.4.1 Le principe de dominance 18
II.4.2 Les indicateurs de Performance 18
iv
TABLE DES MATIÈRES
II.4.3 Procédures de comparaison et de classement 19
II.5 ETAT DE L'ART: (MOEAs) 20
II.5.1 SPEA-II 21
II.5.2 €-MOEA 22
II.5.3 IBEA 23
II.5.4 NSGA-II 24
II.5.5 micro-GA 25
II.5.6 GA PM 25
II.5.7 Discussion 26
II.6 CONCLUSION 26
IIIALGORITHMES EVOLUTIONNAIRES PARALLÈLES
27
III.1 Les architectures parallèles selon Flynn 28
III.2 Etat de l'art : les modèles parallèles pour
les EAs 29
III.2.1 Parallélisation du calcul de performance 29
III.2.2 Distribution du calcul de performance 30
III.2.3 Modèle en îlots 31
III.2.4 Population distribuée 31
III.2.5 Discussion 32
III.3 Les outils de parallélisme 32
III.3.1 Les outils implémentant le modèle de
passage de messages 32
III.3.2 Discussion 33
III.4 Conclusion 33
CONCLUSION GÉNÉRALE ET PERSPECTIVES
34
Bibliographie 36
v
| 
