Angers - stage M2 - Ordonnancement et paysages de fitness

Les problèmes d’ordonnancement ont suscité l’intérêt de nombreux chercheurs du domaine de la Recherche Opérationnelle (RO) depuis plusieurs dizaines d’années. La majorité des méthodes approchées qui ont été développées se basent sur des stratégies de recherche locale (descente itérée, recuit simulé, recherche tabou, …) utilisant des opérateurs de voisinages classiques (insertion, swap, …). Ces stratégies et ces voisinages peuvent être plus ou moins adaptés selon les problèmes et les instances de problèmes à résoudre. Dans le domaine du calcul évolutionnaire, un axe de recherche est dédié au concept de paysages de fitness, s’intéressant entre autre à la prédiction des performances d’un algorithme d’optimisation en fonction de ses composants et des caractéristiques des problèmes. Le paysage d’un problème d’optimisation combinatoire relativement à un voisinage donné est défini par un triplet (S, V, f) où S est l’espace de recherche, V est une relation de voisinage qui à toute solution de l’espace de recherche associe un ensemble de solutions réalisables appelés ses voisins, et f est une fonction objectif qui mesure la qualité des solutions. Une métaheuristique de type recherche locale, qui se déplace de solution en solution voisine selon une stratégie basée sur la qualité des solutions évaluées, détermine ainsi des trajectoires dans un paysage de fitness. Les principales caractéristiques d’un paysage (nombre et distribution des optimums locaux, présence de plateaux, rugosité, …) peuvent permettre d’évaluer la capacité d’un couple (stratégie, voisinage) à atteindre de bonnes solutions. Cependant, pour le moment, peu d’études de ce type portent sur les problèmes d’ordonnancement. 

L’objectif de ce stage est d’établir et de comprendre la relation entre l’efficacité de divers algorithmes d’optimisation et les propriétés d’instances d’un problème d’ordonnancement particulier appelé Open-Shop, ceci en se basant sur l’étude des paysages associés. Les résultats obtenus auront pour but d’expliquer et de prédire les performances des algorithmes, et éventuellement de faciliter la conception d’un algorithme combinant les approches de résolution exacte et approchée. Le travail consistera dans un premier temps à implémenter plusieurs stratégies de recherche locale associées à différents voisinages pour l’Open-Shop. Chaque couple (stratégie, voisinage) sera ensuite testé sur des instances de la littérature de différentes tailles afin de déduire des propriétés issues de l’étude des paysages associés. Ces propriétés permettront de répondre à des questions telles que :

• Quelle est la meilleure modélisation (représentation, voisinage) du problème ?
• Quelle métaheuristique est la mieux adaptée au problème (ou à une instance du problème) ?
• Comment paramétrer au mieux la métaheuristique choisie ?

Profil :

Le stage s’adresse à des étudiants de niveau Master 2 ou en dernière année d’Ecole d’Ingénieur. Les candidats devront avoir de bonnes connaissances en recherche opérationnelle / optimisation ainsi qu’en développement (C++). 

Lieu du stage : Université d’Angers

Durée : 6 mois

Gratification : environ 550 euros par mois

Pour candidater, envoyer un CV et une lettre de motivation à : 

Adrien Goëffon : Adrien.Goeffon@univ-angers.fr

Christelle Guéret : Christelle.Gueret@univ-angers.fr