Université de la Méditerranée
	Faculté des Sciences de Luminy
	Département d'Informatique
	Laboratoire d'Informatique Fondamentale
	Département de Biologie

---

Ce document a été traduit de L^AT_EX par H^EV^EA.

M09b : Métaheuristiques et recherche locale

Table des matières

• 1  Introduction
• 2  Le cours
• 3  Matériel pédagogique
• 4  La compétition
  • 4.1  Description du problème
  • 4.2  Une analyse des solutions proposées
  • 4.3  Un peu de matériel
  • 4.4  Une analyse du premier jeu de données
    • 4.4.1  Les salles
    • 4.4.2  Les cours
    • 4.4.3  Les étudiants

1  Introduction

L'objectif de cette partie du cours est de vous présenter des techniques pour résoudre des problèmes d'optimisation combinatoire difficiles. Ces méthodes : recuit simulé, méthode tabou, algorithmes génétiques, colonies de fourmis sont très souvent utilisés. La principale difficulté pour enseigner ces méthodes c'est qu'il s'agit souvent de "bricolages" très astucieux. Aussi l'expérimentation pratique est nécessaire pour ce cours.

Comme, je m'intéresse en ce moment au problème d'emploi du temps de l'Université (le LMD a rendu ce problème très complexe!!!), j'ai décidé de vous faire travailler sur des problèmes d'emploi du temps d'une semaine type à la Fac des Sciences. Cela fera l'objet d'un projet (M11). Mais pour ce cours nous allons travailler sur un problème plus abstrait. En 2002 une compétition a été organisé sur ce sujet : La compétition . Regardez le lien intitulé "Original competion...". En gros il s'agissait de résoudre le mieux possible un problème d'emploi du temps sur des jeux de données fournis. Ce qui est intéressant, c'est que chaque concurent a écrit un petit papier qui décrit la méthode utilisée (dans la partie résultat). Il s'agit pour vous de faire mieux!!! Je vais mieux décrire ce problème dans une section suivante.

Le matériel pédagogique est abondant sur Internet, mais il ne faut pas trop se perdre. On peut aussi noter l'année dernière la sortie d'un livre sur le sujet : Métaheuristiques pour l'optimisation difficile (Editeur Eyrolles : Prix public : 45,00 EUR). (Ce livre est intéressant, mais son achat n'est pas obligatoire : le cours n'abordera que quelques chapitres de ce livre).

Les ingénieurs, les économistes, les décideurs se heurtent quotidiennement, quel que soit leur secteur d'activité, à des problèmes d'optimisation. Il peut s'agir de minimiser un coût de production, d'optimiser le parcours d'un véhicule ou le rendement d'un portefeuille boursier, de rationaliser l'utilisation de ressources, d'améliorer les performances d'un circuit électronique, de fournir une aide à la décision à des managers, etc. Cet ouvrage présente une famille de techniques d'optimisation, appelées "métaheuristiques", adaptées à la résolution de problèmes pour lesquels il est difficile de trouver un optimum global ou de bons optimums locaux par des méthodes plus classiques.

La première partie de l'ouvrage présente les principales métaheuristiques : recuit simulé, recherche avec tabous, algorithmes évolutionnaires et algorithmes génétiques, colonies de fourmis. La deuxième partie décrit différentes variantes et extensions de ces méthodes, ainsi que de nouvelles voies de recherche. Y sont également proposés des conseils méthodologiques : techniques de modélisation, comparaisons de méthodes et choix de la méthode la mieux adaptée à un problème donné.

La troisième partie présente trois études de cas réels : optimisation de réseaux de mobiles UMTS (France Télécom RD), gestion de trafic aérien (ENAC), optimisation de tournées de véhicules (ILOG).

Certains chapitres de ce livre sont disponibles sur internet chez sur le site de l'éditeur : Eyrolles . En particulier l'avant propos que je vous invite à lire, ainsi que le chapitre concernant les colonies de fourmis

2  Le cours

Ce cours sera composé de 6 séances. Chaque cours sera composé de deux parties : l'une de cours et l'autre de présentations et discussions

Date	Cours	Présentation étudiant	Travail de la semaine
Mardi 28 Septembre 14h-17h	Dans ce premier cours je vous présenterai en détail le problème que l'on souhaite résoudre : création d'un emploi du temps pour une semaine d'une Université. Ainsi que la méthode de travail que je propose pour résoudre ce problème. Ensuite je ferai un survol des différentes méthodes de recherche locales. Avant propos du livre Métaheuristiques....	rien	Vous travaillerez par groupes de 2 ou 3 et vous aurez comme travail de présenter pour la semaine suivante une méthode pour trouver une solution initiale.
Mardi 5 Octobre 14h-17h	Je vous présenterai la méthode tabou, en commentant trois exemples l'un sur l'affectation quadratique, un autre sur la localisation d'entrepôt et le dernier sur le voyageur de commerce. Je vous décrirai la notion de voisinnage	Vous exposerez les méthodes pour trouver une solution initiale	Programmer la méthode que vous avez exposé.
Mardi 12 Octobre 14h-17h	Je vous présenterai les méthodes autour du recuit simulé.	Vous présenterez les résultats de vos programmes pour trouver une solution initiale.	On affectera a chaque groupe une méthode de résolution et vous devrez préparer pour la semaine suivante une présentation sur la méthode qui vous a été affectée.
Mercredi 20 Octobre 9h-12h	ATTENTION CE COURS EST LE MERCREDI Je vous présenterai les algorithmes évolutionnaires et les colonies de fourmis.	Vous présenterez les méthodes que vous avez étudiées	Programmation des méthodes choisies
Mardi 26 Octobre 14h-17h	Je vous présenterai différentes méthodes pour améliorer les solutions de la recherche locale.	Vous présenterez vos résultats.	Programmation de différentes méthodes d'améliorations
Mardi 2 Novembre 14h-17h	Je vais vous présenter différents outils de programmation linéaires en insistant sur les outils gratuits.	Vous commenterez vos résultats	Finalisation de vos programmes, qu'il faudra me rendre le 8 Novembre.

3  Matériel pédagogique

Voici quelques liens :

• Metaheuristics Network web site : Ce site contient beaucoup de choses, regardez les onglets algorithms et problems
  
  
• The Working Group on Automated Timetabling
  
  
• à suivre...

4  La compétition

Tout est décrit sur le site de la compétition , mais je ,vais vous résumer ici le problème.

4.1  Description du problème

It is a reduction of a typical university course timetabling problem. It consists of a set of events to be scheduled in 45 timeslots (5 days of 9 hours each), a set of rooms in which events can take place, a set of students who attend the events, and a set of features satisfied by rooms and required by events. Each student attends a number of events and each room has a size. A feasible timetable is one in which all events have been assigned a timeslot and a room so that the following hard constraints are satisfied:

• no student attends more than one event at the same time;
• the room is big enough for all the attending students and satisfies all the features required by the event;
• only one event is in each room at any timeslot.

In addition, a candidate timetable is penalised equally for each occurrence of the following soft constraint violations:

• a student has a class in the last slot of the day;
• a student has more than two classes consecutively;
• a student has a single class on a day.

4.2  Une analyse des solutions proposées

Sur la page des résultats du site de la compétition, on trouve de petits articles décrivant les méthodes utilisées par les concurrents. Tout ces articles contiennent des informations intéressantes. J'ai retenu 4 articles, pour 3 groupes d'étudiants (mais vous avez le droit de mélanger les méthodes). Voici les méthodes que j'ai retenu :

• Philipp Kostuc : il a terminé le premier. Son article est très intéressant, car il a fait une analyse très détaillé du problème. Sa méthode est cependant un peu complexe. Il utilise le recuit simulé.
• Brigitte Jaumard, Jean-François Cordeau and Rodrigo Morales : c'est surement l'article le plus clair : la construction de la solution initiale est assez claire et ce groupe utilise la méthode tabou.
• Yuri Bykov : l'article est un peu sommaire, mais il fait référence a un autre article sur la planification des examens beaucoup plus complet. Il utilise la méthode du grand déluge (comparable au recuit simulé).
• Krzysztof Socha : C'est le dernier dans la page, pas en performance. Utilise les colonies de fourmis.

D'autres articles sont intéressant :

• Halvard Arntzen and Arne Løkketangen : intéressant
• Alexandre Dubourg, Benoît Laurent, Emmanuel Long and Benoît Salotti des élèves comme vous du DESS d'Angers, cependant leur article n'est pas très informatif!
• Gustavo Toro, Victor Parada : bonne description du tabou et il donne une fonction de coût
• Tomás Müller : contient quelqyes informations intéressantes
• Marco Chiarandini, Mauro Birattari, Olivia Rossi-Doria and Krzysztof Socha : très intéressant, mais plutôt complexe. Il semble utiliser plusieurs méthodes ensemble

4.3  Un peu de matériel

Au cas ou vous auriez des problèmes voici les benchmarks : le premier jeu de donnée : competition et le second : competition2 .

4.4  Une analyse du premier jeu de données

Nous allons examiner le jeu de données intitulé "competition01.tim". Il y a :

• Number of events : 400
• Number of rooms : 10
• Number of features : 10
• Number of students : 200

Comme il y a 45 créneaux horaires et 10 Salles, il y a la place pour 450 cours. Ceci dit si on tient compte de la première contrainte molle cela nous laisse la place pour 40 créneaux par salles soit 400 cours. Il semble d'après l'énoncé qu'une telle solution existe. Cependant on voit tout de suite que la solution sera très tendue.

4.4.1  Les salles

4.4.2  Les cours

l y a 4 cours qui ont un public de 11 étudiants (c'est mieux que moi !!) et un cours qui a 0 étudiant. La contrainte de capacité des salles ne va donc pas servir à grand chose. Le nombre moyen d'étudiant par cours est de : 8,88 etu/cours

De manière plus intéressante analysons pour chaque cours le nombre de salles disponibles compte tenu des caractéristiques demandées pour chaque cours. On trouve le tableau suivant :

nbSallesDisponibles = 1, nbCours = 133
nbSallesDisponibles = 2, nbCours = 185
nbSallesDisponibles = 3, nbCours = 56
nbSallesDisponibles = 4, nbCours = 22
nbSallesDisponibles = 5, nbCours = 2
nbSallesDisponibles = 6, nbCours = 1
nbSallesDisponibles = 7, nbCours = 0
nbSallesDisponibles = 8, nbCours = 0
nbSallesDisponibles = 9, nbCours = 0
nbSallesDisponibles = 10, nbCours = 1

Cela veut dire par exemple que pour 133 cours il n'y a qu'une salle disponibles (les cours qui utilisent la même salle doivent se trouver dans des créneaux horaires différents). Pour la majorité des cours il n'y a qu'une salle ou deux de disponible. On peut donc déduire de cela que l'allocation des salles ne va pas être facile.

4.4.3  Les étudiants

Il y a 200 étudiants qui suivent des cours. Chaque étudiant suit en moyenne 17,75 cours par semaine. Celui qui travaille le plus suit 20 cours par semaine (20h) et celui qui travaille le moins 16 cours par semaine.

Il est intéressant de construire le graphe d'incompatibilité concernant les cours. Les sommets sont les cours. Il y a une arête entre 2 cours si il y a au moins un étudiant qui suit ces deux cours. Chaque étudiant est a l'origine d'une clique dans ce graphe. Il faut donc affecter a chaque cours un créneau horaire différent. Cela revient a voir si on peut colorier ce graphe avec 45 couleurs au plus (ou 40 couleurs). Il est donc intéressant de calculer le degré max et le degré moyen de ce graphe. On trouve respectivement 113 et 36,14.(Ce graphe d'icompatibilité devrait être étendu avec les contraintes de salles)

REMARQUE : Une fois que l'on a affecter des créneaux horaires aux cours, ce qui ne devrait pas être trop dur, il faut affecter des salles au cours, pour cela il faudra vérifier dans le coloriage qu'il n'y a pas plus de 10 cours de la même couleur. A suivre.....