Problématique des horaires d’examens

Problématique des horaires d’examens

Pour un élève, un horaire d’examens représente la distribution des périodes où ce dernier doit se présenter afin de subir une évaluation dans un ou plusieurs cours dans lequel il est inscrit. Pour un gestionnaire responsable de l’ordonnancement, un horaire d’examens représente l’assignation des examens dans les différentes périodes prévues à cette fin. Cette représentation sera utlisée dans le cadre de ce travail de recherche. Un horaire d’examens peut être considéré comme réalisable ou non réalisable. Un horaire dit réalisable doit obligatoirement respecter l’ensemble des contraintes fortes. ll existe un certain nombre de contraintes fortes.

La première, essentielle à tout PCHE, est le respect des conflits d’horaire. Un conflit d’horaire est présent lorsqu’un élève se voit assigner deux examens à la même période. Il est aussi possible de considérer d’autres contraintes fortes comme le repect de la capacité des locaux et la préassignation des examens. Les préassignations stipulent que certains examens doivent avoir lieu durant certaines périodes spécifiques. Ainsi, dès que l’une ou l’autre de ces contraintes est enfreinte, l’horaire est considéré comme non réalisable. Ce n’est pas toutes les institutions d’enseignement qui ont recours à la création d’un horaire d’examens finaux. Certaines utilisent la dernière semaine de cours pour la tenue des examens. Cette décision évite d’avoir à procéder à la recherche d’un horaire. Par contre, pour les élèves, cette décision implique qu’ils n’auront qu’une seule semaine attribuée pour la tenue de leurs examens. La création d’un horaire d’examen différent de celui des cours permet donc d’ajouter des périodes suplémentaires et ainsi de donner plus de temps d’étude aux élèves. Évidemment, cette tâche doit se faire de façon tout aussi rigoureuse que la création des horaires de cours. Un horaire d’examens qui est bien conçu permettra aux élèves de mieux se préparer et permettra aux administrateurs de créer un horaire qui respecte la capacité d’accueil des locaux ainsi que les différentes contraintes reliées au personel enseignant.

Lorsque la résolution d’un PCHE ne nécessite que des contraintes fortes, le problème posé est un problème de satisfaction de contraintes. Par contre, un PCHE peut aussi être considéré comme un problème d’optimisation combinatoire. Cette situation se présente lorsque le PCHE est soumis à certaines contraintes dites faibles. Ces contraintes peuvent, entre autres, être reliées aux proximités. Les proximités dans un horaire d’examens correspondent à l’étalement temporel des examens d’un élève. Dans la plupart des applications, les proximités représentent le critère d’optimisation. Nous pouvons donc considérer le PCHE comme un problème d’optimisation combinatoire. En effet, un horaire est créé en choisissant une assignation des périodes disponibles à l’ensemble des examens. Cette assignation doit permettre la minimisation d’un ou plusieurs critères tout en satisfaisant les contraintes imposées. Le choix d’une telle assignation n’est pas trivial puisque la taille de l’ensemble des assignations est très grande. Même si cet ensemble est réduit par l’application des contraintes, le choix d’une assignation demeure très difficile. Pour cette raison, il est nécessaire d’apporter une méthode de solution qui est systématique et rigoureuse.

Caractéristiques des problèmes d’optimisation combinatoire

Les définitions qui suivent serviront à exposer de façon concise les caractéristiques élémentaires des problèmes d’optimisation combinatoire. Ces définitions sont tirées, en partie, des travaux de Gottlieb [15] effectués sur les algorithmes évolutifs servant à la résolution de problèmes d’optimisation combinatoire. Pour faciliter la lecture, les symboles suivants seront utilisés :
a. He : Espace de décision réalisable
b. Di :Domaine associé à la variable Xi
c. f : Fonction d’objectif
d. ci : Fonction de contrainte
e. N+ :Ensemble des nombres entiers positifs
f. n+ :Ensemble des nombres réels positifs
g. S : Espace de décision
h. Uc : Espace de décision non réalisable
1. \:Opérateur de soustraction d’ensembles

Définition 1.1 Un domaine est un ensemble fini ou infiniment dénombrable d’éléments D = { d1, d2 , ..• , dm}· Pour les besoins de ce projet de recherche, di EN+.
Définition 1.2  Soit un ensemble fini de variables de décision X = { x1 , x2 , … , Xm} ainsi que les domaines Di associés à chaque variable de X, un espace de décision est noté par le produit cartésien de tous les domaines S = D1 x D2 x · · · x Dm. Un élément a E S est appelé une solution.
Définition 1.3 Soit Sun espace de décision et une fonction d’objectif f : S-+ n+. Une solution a E S est optimale par rapport à f si j(a) > f(b), V b E S dans le cas d’une maximisation et J(a) < J(b), V bE S dans le cas d’une minimisation.
Définition 1.4 Soit S un espace de décision et un ensemble fonction de contrainte Ci : S -+ n+, i = 1, 2, … , K. Un espace de décision réalisable est noté par He =a E S tel que ci(a) op 0, V i (op ~:::. >pour le cas d’une contrainte d’inégalité, op A =pour le cas d’une contrainte d’égalité). Chaque élément de He est appelé solution réalisable. Un espace de solutions non réalisables est donné parUe= S\He et chaque élément de Ue est une solution non réalisable. Dans ce travail nous considérons deux types de contraintes. Les contraintes d’égalités c(x) = 0 et les contraintes d’inégalités c(x) >O. Ces contraintes peuvent être fortes, dans le cas où toutes les solutions réalisables doivent respecter les contraintes. Les contraintes peuvent être faibles si elles peuvent être relâchées pour accepter une solution comme « réalisable ». Notons que les contraintes d’égalité fortes sont les plus restrictives puisqu’elles découpent l’espace de décision de façon très draconienne. Par exemple, dans un problème.

Recuit simulé

L’algorithme du recuit simulé, comme son nom l’indique, est une analogie aux méthodes de recuit effectuées sur les aciers. Pour développer l’algorithme du recuit simulé (algorithme 3, page 18), Kirkpatrik et son équipe se sont inspirés de l’algorithme Métropolis. Cet algorithme utilise des modèles statistiques qui régissent l’agencement des molécules lors du refroidissement d’un acier chauffé à haute température. Le but des recuits est de trouver la température initiale ainsi que la fonction de refroidissement qui optimiseront l’ agencement des molécules de façon à augmenter les propriétés mécaniques des aciers . Appliqué dans le domaine de la résolution de problèmes d’optimisation combinatoire, le recuit simulé est semblable à la méthode de fouille par escalade, à la différence que le choix d’une solution peut être valide malgré une baisse de qualité.  Un désavantage important quant à l’utilisation de cette technique est l’ajustement des paramètres. En plus d’avoir à détemimer quel cycle de froidissement s’applique le mieux, ces cycles requièrent l’utilisation de plusieurs paramètres. Comme le cycle de refroidissment est un élément très important dans cette fouille, l’ajustement des paramètres doit donc être fait avec attention.

Les algorithmes génétiques

Depuis les dix dernières années, les algorithmes génétiques (AG) n’ont cessé d’augmenter en popularité. Cette méthode (algorithme 4, page 23), basée sur les principes empiriques de l’évolution, est très utile pour la résolution de problèmes d’optimisation. Les AG peuvent être vus comme une série de transformations appliquées à un sous-ensemble de solutions. Les solutions sont aussi appellées chromosomes. Le croisement représente l’échange des éléments, que l’on appelle gènes, constituants l’ensemble des n > 1 solutions, tandis que la mutation représente l’altération des éléments constituant une seule solution. Ainsi, l’exploitation de l’espace de décision est réalisée par le croisement des solutions sélectionnées, alors que la mutation des solutions individuelles permet l’exploration de l’espace de décision. Un nouvel ensemble de solutions candidates est produit par l’application successive de la mutation et du croisement. Comme l’algorithme s’opère sur un ensemble de solutions, il est en mesure d’obtenir plus d’une solutions réalisables en un seul lancement de l’algorithme.

Évaluation des chromosomes :L’évaluation des chromosomes consiste à attribuer une valeur d’adaptation à chaque individu. Cette valeur permettra d’établir une comparaison lors de la sélection des individus. Un exemple d’implantation de l’opérateur d’assignation de la valeur d’adaptation est de bomer la valeur entre [0,1]. Dans le cas d’une minimisation, si 0 :S f(a) :S oo, l’application peut être réalisée par la relation : F(a) = 1 + f(a) (1.6) .

Sélection :Les deux principales implantations A de l’opérateur de sélection S sont le tournoi et la roulette. Dans le cas du tournoi binaire, les solutions sont choisies de façon aléatoire parmi une sous-population qui est construite en effectuant des compétitions entre les solutions de la population. Goldberg et Deb ont montré que cet opérateur converge plus rapidement que tout autre opérateur utilisé pour la sélection [9]. Pour l’utilisation de la sélection par roulette, la solution est choisie, par exemple, en fonction d’une probabilité p8 qui varie entre 0 et I:_%:0 F(aj) où N est la taille de la population et F(aj) est la valeur d’adaptation de la solution aj calculée selon la relation (1.6).

Croisement :Outre les croisements réels, les deux principales implantations r de l’opérateur de croisement X sont le croisement uniforme et par points de coupure. Dans le cas des croisements uniformes, chaque valeur associée aux gènes de l’enfant est constituée par la valeur d’un des deux gènes des parents. Le choix de la valeur de chaque gène est fait selon une probabilité Pc comprise entre [0,1] (figure 4). Pour les croisements par points de coupure (figure 5), les chromosomes sont découpés de façon aléatoire en un ou plusieurs points afin de reconstituer le nouveau chromosome. Il existe un bon nombre de méthodes de croisement pour les modèles en nombre réels [16] [23]. Par contre, comme ce travail porte essentiellement sur des modèles discrets, seuls les techniques de croisement et de mutation applicables à ces modèles seront résumées.

Mutation :L’implantation TI de l’opérateur de mutation M consiste à modifier un gène du chromosome de façon aléatoire selon une probabilité PM comprise entre [0,1]. La mutation favorisera une plus grande diversité à l’intérieur de la population.

Insertion et élitisme :Il existe, en général, deux façons de procéder à l’insertion des individus produits lors de l’application des opérateurs génétiques de croisement et de mutation. Tout d’abord, l’implantation de l’opérateur d’insertion pourra être totale lorsque la population est remplacée par de nouveaux chromosomes. Une deuxième méthode, en régime permanent (« steady-state »), consiste à insérer immédiatement dans la population les chromosomes qui viennent d’être croisés et mutés. Pour l’élitisme, la principale implantation est celle où les meilleurs individus sont conservés à chaque itération. Le nombre d’élites est défini par c% du nombre total d’individus dans la population. Une autre forme d’élitisme est celle où, lors de la création de deux enfants par deux parents, une comparaison est faite entre ces quatre individus et les deux meilleurs sont conservés.

Choix des paramètres :Beaucoup d’efforts ont été déployés dans le domaine des AG afin de démontrer de façon analytique ou empirique les paramètres optimaux. Les travaux de Eiben et al. [21] font état d’une multitude de techniques pour l’obtention de ces paramètres. Entre autres, le taux de mutation Pm proposé est défini par 1/L où Lest la longueur du chromosome, c’est-à-dire le nombre d’éléments constituants un chromosome. Une version dynamique équivalente peut aussi être implantée. Dans l’équation (1.7), le taux de mutation décroît en fonction des générations ce qui permet une recherche plus vaste au départ et plus raffinée à la fin. Pour le taux de croisement, les valeurs les plus souvent préconisées sont Pc E [0.6, 0.95]. Eiben et al. [21] précisent que le taux de croisement ne doit pas être inférieur à 0.6. Pm – (L- 2 ) -l 2+–t .

Fouille Tabou

Dans le domaine de la génération automatique des horaires d’examens, la fouille Tabou (Ff) est l’une des méthodes les plus citées. De nombreux travaux ont été réalisés à l’aide de cette fouille locale. White et al. [18] ont travaillé à la résolution du problème P2 à l’aide de deux Ff. La première fouille sert à assigner les examens qui n’ont pu être traités suite à l’initialisation de la solution par la technique Largest Degree. Une fois la solution initiale obtenue, une deuxième Ff est appliquée pour l’optimisation de proximités. Une des caractéristiques importantes de leur travail est le calcul de la tenure Tabou. La tenure Tabou désigne la durée à laquelle une solution est présente dans la liste Tabou. Les auteurs proposent deux méthodes basées sur les caractéristiques des bases de données afin de calculer la tenure Tabou.

Le nombre de liens (examens ayant des élèves en commun), le nombre d’inscriptions-cours ainsi que la pondération des liens entre les examens sont les caractéristiques utilisées. Cet ajustement de paramètres est un avantage très intéressant, car dans les publications concernant les bases de données standard, on note que les meilleurs résultats ne sont pas obtenus systématiquement par le même chercheur. Ceci implique que les bases de données ont possiblement des caractéristiques bien différentes qui ont une influence sur les performances des algorithmes. Malheureusement White et al. n’ont donné des résultats que sur deux bases de données publiques.

ALGORITHMES ÉVOLUTIFS MULTI-CRITÈRES EXISTANTS

Introduction :Bien peu de travaux ont été réalisés sur l’optimisation multi-critères dans le domaine des horaires d’examens. Aucun travail n’a encore été réalisé jusqu’à maintenant sur l’optimisation multi-critères des horaires d’examens en utilisant les bases de données publiques. C’est pour cette raison, entre autre, que cette étude portera sur l’utilisation d’algorithmes évolutifs multi-critères (AEMC) déjà existants. Une revue des principales techniques d’optimisation multi-critères sera effectuée dans ce chapitre. Par la suite, une première série de tests seront effectués sur les bases de données publiques. Afin de comparer les résultats avec ceux déjà publiés, un modèle multi-critères appelé Pl-P2 sera proposé. Les résultats obtenus montront que les AEMC les plus populaires tels que le NSGA-II et le SPEAII sont inéfficaces pour la résolution d’un PCHE de forme mutli-critères. Les causes de cet échec seront mises en évidence afin de guider la conception d’un éventuel algorithme multi-critères. Dans ce contexte, ce chapitre permettra donc de justifier la conception d’un nouvel algorithme évolutif multi-critères.

Justification du choix d’une méthode évolutive multi-critères Les problèmes d’optimisation multi-critères (POMC) sont une généralisation des problèmes d’optimisation. Le but est de trouver l’ensemble de Pareto optimal comprenant des solutions non dominées (définition 1.6). Les PCHE sont fondamentalement des problèmes d’optimisation multi-critères. Tout comme la plupart des problèmes d’optimisation, ils doivent traiter avec plusieurs objectifs. Les techniques d’optimisation mono-critère quant à elles, assemblent tous les objectifs dans une même fonction. Si l’on suppose un problème d’optimisation sans contrainte défini par min {fi, f2, … , fm} m > 1 la fonction d’objectif utilisée par un algorithme mono-critère sera L: fiwi, i = 1 … m. Le vecteur W= { Wt. w2, … , Wm} est le poids qui est accordé à chaque objectif. Ce vecteur de poids ne représente qu’une mesure de préférence. Si l’on prend par exemple les poids w1 = 16 et w2 = 8 du problème P2 (section 2.4), ceci implique que la fonction fi est deux fois plus importante que h et que la valeur finale de / 1 risque d’être deux fois plus faible que celle de h. Par contre, si les critères de préférence changent, un nouveau vecteur W doit être identifié et une nouvelle recherche doit être faite.

Une autre différence est que dans un problème d’optimisation multi-critères l’objectif est double. Contrairement aux techniques d’optimisation mono critère où le seul objectif à atteindre est la maximisation ou la minimisation de la fonction d’objectif, pour un problème multi-critères l’obtention de l’ensemble de Pareto optimal du problème et la diversité des solutions qui en font partie sont deux objectifs indissociables. Cette diversité est un objectif important, car elle permet d’effectuer une meilleure décision à posteriori. En considérant qu’un PCHE est un problème multi-critères, l’application d’une méthode de résolution multi-critères semble logique. Les méthodes évolutives offrent aussi l’avantage d’utiliser une population d’individus. Dans une application multi-critères il sera donc possible de faire converger l’ensemble de la population vers un ensemble de Pareto en effectuant un seul lancement de l’algorithme. Ceci éliminera du même coup toute pondération des fonctions d’objectifs appliquée à priori. De plus, les résultats obtenus par Burke [28] montrent que les algorithmes génétiques peuvent être aussi performants que tout autre algorithme tels que le recuit simulé ou la fouille Tabou.

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

Télécharger le rapport complet