Note publique d'information : Les problèmes d'optimisation combinatoire sont généralement NP-difficiles et les méthodes
exactes demeurent inefficaces pour les résoudre rapidement. Les métaheuristiques sont
des méthodes génériques de résolution connues et utilisées pour leur efficacité. Elles
possèdent souvent plusieurs paramètres qui s'avèrent fastidieux à régler pour obtenir
de bonnes performances. Il est alors intéressant de chercher à rendre plus évident,
voire à automatiser, ce réglage des paramètres. Le paysage d'un problème d'optimisation
combinatoire est une structure, basée sur la notion de voisinage, permettant de caractériser
le problème puis de suivre la dynamique d'une méthode d'optimisation pour comprendre
son efficacité. Les travaux de cette thèse portent sur l'analyse de paysage de problèmes
d'optimisation combinatoire et le lien étroit avec certaines classes de métaheuristiques,
basées sur une exploration du voisinage des solutions. Ainsi, nous montrons l'influence
de la structure de paysage sur la dynamique d'une métaheuristique, pour deux problèmes
issus de la logistique. Ensuite, nous analysons les caractéristiques du paysage qui
permettent de concevoir et/ou paramétrer des métaheuristiques, principalement des
recherches locales, efficaces. La neutralité est, en particulier, une caractéristique
structurelle importante des paysages. De tels paysages présentent de nombreux plateaux
bloquant la progression d'une recherche locale. Après une analyse fine des plateaux,
nous prouvons que cette structure neutre ne doit pas être ignorée. Puis, nous utilisons
plusieurs informations liées à la neutralité, et plus particulièrement aux plateaux
bloquants, pour concevoir une première recherche locale simple à mettre en œuvre et
efficace. Enfin, pour approfondir nos travaux sur les structures neutres, nous avons
choisi d'exploiter la neutralité à tous les niveaux du paysage pour concevoir une
nouvelle recherche locale basée sur la capacité des solutions d'un même plateau à
produire une amélioration. Une stratégie de guidage vers cette solution est alors
proposée. La thèse se termine par l'analyse comparative des deux méthodes d'optimisation
proposées pour les problèmes neutres afin d'en exploiter de nouvelles caractéristiques,
et ainsi, renforcer le lien entre l'analyse de paysage et la conception de méthodes
efficaces.
Note publique d'information : Many problems from combinatorial optimization are NP-hard, so that exact methods remain
inefficient to solve them efficiently. However, metaheuristics are approximation methods
known and used for their efficiency. But they often require a lot of parameters, which
are very difficult to set in order to provide good performance. As a consequence,
a challenging question is to perform such parameter tuning easier, or adaptive.The
fitness landscape of given combinatorial optimization problem, based on a search space,
a fitness function and a neighborhood relation, allow to characterize the problem
structure and make the understanding of the dynamics of search approches possible.This
thesis deals with fitness landscape analysis, together with the link with some neighborhood-based
metaheuristic classes. We show the influence of the landscape structure on the dynamics
of metaheuristics, for two challenging problems from the field of logistics. We analyze
the landscape characteristics which help to design efficient local search metaheuristics
and/or to set their parameters.Neutrality is one of the main structural characteristic
of a landscape. Such landscapes have numerous plateaus, which often inhibits the progress
of local search algorithms. After a deep analysis of these plateaus, we prove that
this neutral structure cannot be ignored. Then, we use several information linked
with neutrality, and particularly with blocking plateaus, in order to design a first
local search approach, which appear to efficient and easy to implement. At last, in
order to extend our work on the neutral structure, we chose to exploit the neutrality
involved in the whole landscape. We propose a new local search algorithm, based on
the ability of solutions of a plateau to produce improvement by means of a guiding
strategy.The thesis ends with an experimental analysis of the two local search methods
presented for neutral problems in order to exploit new characteristics, and then to
strengthen the link between fitness landscape analysis and efficient algorithm design.
paprika.idref.fr
data.idref.fr
Documentation
