Optimisation multi-objective des problèmes combinatoires : application à la génération des horaires d'examens finaux

Côté, Pascal (2004). Optimisation multi-objective des problèmes combinatoires : application à la génération des horaires d'examens finaux. Mémoire de maîtrise électronique, Montréal, École de technologie supérieure.

Prévisualisation

PDF Télécharger (4MB) | Prévisualisation

Résumé

Les problèmes d'optimisation combinatoire discrète (POCD) sont des problèmes très difficiles à résoudre. La nature discrète des variables forme un espace non dérivable qui rendent inutiles les techniques basées sur le gradient. Le problème de la production des horaires est représentatif d'une famille de POCD. Il renferme un ensemble d'objectifs conflictuels, un ensemble de contraintes non linéaires et un nombre de combinaisons potentielles très élevé. De plus, un certain nombre d'institutions académiques produisent encore des horaires d'une manière manuelle ou semi-automatique. L'automatisation peut donc éliminer les aspects déplaisants de cette tâche. Ce travail porte sur l'optimisation combinatoire par algorithmes évolutifs et, plus précisément, sur les problèmes de création d'horaires des examens finaux (PCHE). Dans un premier temps, les POCD mono-critère et multi-critères sont décrits d'une manière formelle afin d'en établir les principales caractéristiques. Les méthodes qui ont été proposées pour la résolution d'un PCHE, tels que le recuit simulé, la fouille Tabou et les algorithmes génétiques ont fait l'objet d'une revue de la littérature. Afin de faire un lien avec les méthodes de résolutions multi-critères, il sera prouvé qu'un PCHE est lui aussi un POCD multi-critères. Jusqu'à maintenant, ce sont principalement les modèles mono-critères qui sont utilisés lors de la résolution de ce type de problème. Ainsi, l'étude qui a été entreprise dans ce travail s'est concentrée sur les différentes techniques d'optimisation multi-critères envisagables pour la résolution d'un PCHE. Parmi les algorithmes évolutifs multi-critères les plus populaires, ceux de la famille NSGA de Deb et du SPEA de Zitzler ont été susceptibles d'obtenir de bons résultats. Ces techniques, vues en détail dans ce travail, ont été implantées sur un problème de création des horaires d'examens finaux. Suite à une première série d'expérimentations, les algorithmes NSGA-II et SPEA-II se sont montrés inappropriés pour la résolution d'un PCHE à cause de la gestion des contraintes et à la diversité des solutions. L'ensemble des problèmes rencontrés lors de l'utilisation de ces algorithmes a permis la conception d'une nouvelle approche hybride. Cet algorithme évolutif hybride possède une structure semblable à celle de l'algorithme SPEA-II de Zitzler. La différence majeure est le remplacement de l'opérateur de croisement par deux fouilles Tabou. La première fouille est appliquée afin de réduire les violations de contraintes alors que la deuxième fouille Tabou permet l'optimisation de l'étalement temporel des examens des élèves. Les résultats obtenus avec l'ensemble des bases de données publiques ont démontré qu'en moyenne l'algorithme développé fonctionne très bien et présente un bon potentiel pour la réalisation de travaux futurs.

Titre traduit

Application of a hybrid multi-objective evolutionary algorithm to the final exam proximity problem

Résumé traduit

Final exam proximity problem is a hard combinatorial optimization problem. The decision variables formed a discretized search space that does not possess gradient or Hessian operators. The general exam proximity problem contains conflicting objectives, nonlinear side constraints and a very complex solution-space landscape. For the academic institutions that produce timetables in a semi-manually or manually way, the complete automation of the procedure is, obviously, a great improvement. This work presents a hybrid multi-objective evolutionary algorithm to solve the exam proximity problem. The problem has been investigated by many researchers. However, most of the techniques are based on a single-objective approach. Since the final exam proximity problem contains conflicting objectives, a multi-objective approach is more ppropriated. The first part of this work presents the mathematical definitions and a formal description of single and multi-objective combinatorial optimization problems. We reviewed the previous works done on the exam proximity problem by presenting the standard solution techniques such as Tabu Search, Simulated Annealing and Genetic Algorithms. The content of the second part concerns the application of a multi-objective evolutionary algorithm (MOEA). After analyzing some of the most popular MOEAs, we applied two of them, the Elitist Non-Dominated Sorting Genetic Algorithm (NSGA-II) and the Strength Pareto Evolutionary Algorithm (SPEA-ll) to the uncapacitated exam proximity problem. These two algorithms failed on our multi-objective model due to the constraint handling and the diversity of the solutions on the Pareto front. The weakness of these algorithms gave us the opportunity to develop a new algorithm. Thus, a Hybrid Multi-Objective Evolutionary Algorithm is used to tackle the uncapacitated and the capacitated exam proximity problem. In this hybridization, local search operators are used instead of the traditional genetic recombination operators. One of the local search operators is designed to repair unfeasible timetables produced by the initialization procedure and the mutation operator. The other search operator implements a simplified Variable Neighborhood Descent meta-heuristic and its role is to improve the proximity cost. The resulting non dominated timetables are compared to other optimization methods using several public domain datasets. Without special fine-tuning, the hybrid algorithm was able to produce timetables ranking first and second in most of the datasets.

Type de document:	Mémoire ou thèse (Mémoire de maîtrise électronique)
Renseignements supplémentaires:	"Mémoire présenté à l'École de technologie supérieure comme exigence partielle à l'obtention de la maîtrise en génie". Bibliogr.: f. [128].
Mots-clés libres:	Algorithme, Combinatoire, Discret, Evolutif, Examen, Final, Horaire, Hybride, Modele, Multi-Critere, Multi-Objectif, Optimisation, Probleme
Directeur de mémoire/thèse:	Directeur de mémoire/thèse Wong, Tony
Codirecteur:	Codirecteur Sabourin, Robert
Programme:	Maîtrise en ingénierie > Génie
Date de dépôt:	20 avr. 2011 16:23
Dernière modification:	21 oct. 2016 00:36
URI:	https://espace.etsmtl.ca/id/eprint/709

Gestion Actions (Identification requise)

Dernière vérification avant le dépôt