L’algorithme du recuit simulé

Table des matières

ABSTRACT
REMERCIEMENTS
LISTE DES TABLEAUX
LISTE DES FIGURES
LISTE DES ABRÉVIATIONS ET DES SIGLES
CHAPITRE 1 HORAIRES D’EXAMENS ET OPTIMISATION COMBINATOIRE 
1.1 Introduction 
1.2 Problématique des horaires d’examens 
1.3 Caractéristiques des problèmes d’optimisation combinatoire 
1.4 Structure des problèmes d’optimisation combinatoire 
1.5 Optimisation multi-critères 
1.6 Méthodes pour la résolution des problèmes d’optimisation  
1.6.1 Fouille par escalade non déterministe
1.6.2 Fouille Tabou
1.6.3 Recuit simulé
1.6.4 Types de voisinage utilisés
1.6.5 Les algorithmes génétiques
1.7 Méthodes d’initialisation utilisées  
1.8 Conclusion 
CHAPITRE 2 MODÈLES DU PROBLÈME ET REVUE DE LA LITTÉRATURE  
2.1 Introduction 
2.2 Problème de coloration des graphes  
2.3 Objectifs et contraintes 
2.3.1 Conflits d’horaire (j1 ,c1)
2.3.2 Étalement temporel des examens (!2 à h)
2.3.3 Capacité des locaux (f8 , c2)
2.3.4 Préassignations des examens (c3)
2.3.5 Nombre de périodes à l’horaire (f9)
2.4 Critères de performance et problèmes standards
2.5 L’état de l’art
2.5.1 Méthodes constructives
2.5.2 Fouille Tabou
2.5.3 Le recuit simulé
2.5.4 Méthodes évolutives
2.6 Conclusion 
CHAPITRE 3 ALGORITHMES ÉVOLUTIFS MULTI-CRITÈRES EXISTANTS
3.1 Introduction
3.2 Justification du choix d’une méthode évolutive multi-critères
3.3 Algorithmes évolutifs multi-critères
3.3.1 NSGA
3.3.2 NSGA-II
3.3.3 SPEA
3.3.4 SPEA-II
3.3.5 Algorithmes évolutifs multi-critères sous contraintes
3.4 Application à la création des horaires d’examens
3.4.1 Modèle utilisé
3.4.2 Représentation des solutions
3.4.3 Application de NSGA-II et SPEA-II
3.4.4 Amélioration de la diversité
3.4.5 Minimisation des conflits
3.4.6 Discussion
3.5 Conclusion 
CHAPITRE 4 CONCEPTION D’UN ALGORITHME ÉVOLUTIF HYBRIDE 
4.1 Introduction  
4.2 Présentation de l’algorithme
4.2.1 Structure générale
4.2.2 Justification de la structure
4.2.3 Méthode d’initialisation des solutions
4.2.4 Fouilles locales
4.2.5 Valeur d’adaptation et sélection des solutions
4.2.6 Mise à jour de l’archive et traitement de la diversité
4.2.7 Opérateur de mutation
4.2.8 Gestion de la capacité des locaux
4.3 Protocole d’expérimentation 
4.4 Résultats pour le problème P1-P2 
4.4.1 Analyse des résultats
4.4.2 Progression de l’archive
4.5 Résultats pour le problème P1-P3
4.5.1 Analyse des résultats
4.5.2 Progression de l’ archive
4.6 Conclusion
CHAPITRE 5 CONCLUSION  
5.1 Points forts du AEMH 
5.2 Points faibles du AEMH 
5.3 Améliorations possibles du AEMH  
ANNEXE 1 RÉSULTATS DE SIMULATION POUR LE PROBLÈME P1- P2
BIBLIOGRAPHIE