Détail du sujet

De nombreux problèmes issus du monde réel peuvent se modéliser comme des problèmes d'optimisation combinatoire multi-objectif. Ces problèmes sont souvent caractérisés par des espaces de recherche vastes et difficiles. Les heuristiques et métaheuristiques, constituant une classe de méthodes approchées, se montrent particulièrement adaptées à leur résolution. Ainsi, l'optimisation multi-objectif vise à optimiser (minimiser ou maximiser) plusieurs fonctions objectif simultanément (typiquement coût vs. qualité). La difficulté réside dans le fait que ces critères sont souvent antagonistes : lorsque l'un d'eux est amélioré, les autres sont généralement dégradés. Il existe donc rarement une solution unique optimisant tous les critères à la fois. En conséquence, les problèmes d'optimisation multi-objectif possèdent un ensemble de solutions de bon compromis entre les différents objectifs. Il s’agit donc d’identifier cet ensemble de solutions, dites Pareto optimales, ou d’en trouver une bonne approximation.

Pour cela, deux types d’approches sont généralement utilisées. D’une part les approches scalaires consistent à réduire le problème original en plusieurs problèmes mono-objectif, et à résoudre chacun de ces problèmes indépendamment. D’autre part, les approches Pareto utilisent directement la notion de dominance pour comparer les différentes solutions, et se basent donc sur des ensembles de solutions. Au cours de ce projet, il s’agira de développer de nouveaux algorithmes, et de comparer leurs performances, en termes de temps de calcul et de qualité des solutions trouvées.

Pour cela, nous nous intéressons à des problèmes d’optimisation combinatoire multi-objectif «classiques» étudiés par les chercheurs, qui sont en quelques sortes leurs «souris de laboratoire». Nous veillerons à prendre en compte le degré de corrélation entre les différents objectifs, qui a un impact considérable sur le nombre de solutions Pareto optimales, et donc sur la performance des algorithmes.

Le travail pourra être effectué en monôme ou en binôme.
Des bases solides en algorithmique sont nécessaires. Par ailleurs, une connaissance et une bonne pratique d’un langage orienté objet sont recommandées.

• Métaheuristique : http://fr.wikipedia.org/wiki/Métaheuristique
• Optimisation multiobjectif : http://fr.wikipedia.org/wiki/Optimisation_multiobjectif
• Optimum de Pareto : http://fr.wikipedia.org/wiki/Optimum_de_Pareto