Etude de paysages

Etude des paysages

Un premier aspect concernant les perspectives de travail dans
ce domaine concerne l’analyse du comportement des algorithmes de type
métaheuristiques pour l’optimisation combinatoire et plus
particulièrement des algorithmes de recherche basés sur des
structures de voisinages. La motivation principale est de comprendre
les difficultés rencontrées par les méthodes de voisinages lors de
l’exploration de l’espace de recherche en vue d’en extraire des
solutions optimales ou, au moins, de bonne qualité. Cette analyse
doit permettre par la suite de mieux justifier le choix des
composants algorithmiques, en vue d’améliorer les performances des
méthodes d’optimisation ainsi conçues. Le modèle abstrait des
paysages de fitness est un outil efficace et générique qui nous aide
à déterminer les stratégies de recherche les plus à même de converger
vers de meilleurs optimums locaux en fonction de divers indicateurs.
Nos résultats actuels nous ouvrent de nouvelles pistes de recherche
pour la conception d’algorithmes efficaces pour la résolution de
problèmes NP-difficiles. L’analyse approfondie de ces paysages au
moyen d’indicateurs pertinents sur lesquels s’appuyer devrait
permettre de définir de nouvelles stratégies de recherche dans le but
d’améliorer les algorithmes de résolution approchée de problèmes
combinatoires. En particulier, les aspects apprentissage (utiliser
l’information de la recherche) et prédiction (utiliser la
connaissance a priori) peuvent être développés afin d’aider à la
conception de stratégies de résolution efficaces et auto-adaptatives.
Ces études, qui impliquent une grande partie expérimentale, pourront
être conduites à la fois sur des paysages abstraits qui vérifieront
des propriétés spécifiques, et sur des paysages de recherche
d’instances de problèmes d’optimisation combinatoires académiques
(problèmes de coloration, de sac à dos, d’affectation quadratique,
d’ordonnancement, de satisfiabilité, etc.). Des études dédiées
pourraient être effectuées sur les problématiques relatives à
l’optimisation multi-objectif, à la modélisation des problèmes ou à
la définition de fonctions d’évaluations statiques ou dynamiques.