Métaheuristiques Hybrides pour le problème de couverture par ensembles (set covering problem)

Lieu : Institut de recherche IRIMAS - Université de Haute Alsace - Mulhouse

Durée : 6 mois à partir de janvier ou février 2019

Rémunération : gratification légale en vigueur, soit environ 550€ mensuel

Objectif du stage :

Le problème de « couverture par ensembles », également connu sous le nom de « set covering problem », fait partie des grands classiques de l’optimisation. Au sein de l’institut de recherche IRIMAS, nous nous intéressons notamment aux approches heuristiques permettant de résoudre de tels problèmes.

Dans le cadre de ce stage, nous nous intéressons au développement de méthodes hybrides de type mémétique, mêlant recherche locale et algorithmes génétiques. Ce type d’hybridation s’est révélé particulièrement efficace pour résoudre des problèmes connus pour être très difficiles, appartenant à la famille des problèmes NP-complets. Dans le cadre de travaux menés conjointement avec l’ENAC de Toulouse, nous avons développé des algorithmes reposant sur des populations réduites à deux individus. Les résultats obtenus sur le problème bien connu de coloration de graphes [1] nous laisse supposer que cette démarche pourrait se révéler particulièrement efficace sur d’autres types de problèmes, tels que le « set cover ».

Le candidat retenu aura ainsi l’opportunité de développer, en s’appuyant sur les travaux existants, des algorithmes hybrides avec une recherche poussée de performance.

Les principales étapes du travail à réaliser sont les suivantes :

1. Identifier dans la littérature scientifique du domaine quels sont les opérateurs élémentaires efficaces pour le problème de « set cover ». Il s’agit donc d’analyser les différents opérateurs de croisement et les recherches locales connus actuellement.

2. Mettre en place des structures de données adaptées pour modéliser informatiquement le problème de « set cover ».

3. Construire les algorithmes qui vont rechercher le meilleur optimum possible.

4. Analyser les résultats et construire une étude comparative afin de positionner les résultats obtenus par rapport aux autres approches de la littérature.

Profil du candidat :

• École d'ingénieur ou Master 2 en informatique

• Bonnes connaissances en Recherche Opérationnelle

• Bonne aptitude à la programmation en C++

Candidature :

Transmettre CV, notes de M1 et M2 ainsi que votre lettre de motivation à Laurent Moalic : laurent.moalic@uha.fr

[1] L. Moalic and A. Gondran “Variations on memetic algorithms for graph coloring problems”. Journal of Heuristics (Feb 2018), Volume 24, pp 1-24, doi:10.1007/s10732-017-9354-9