Thèse de Marie-Eléonore Marmion-Kessaci

Recherche locale et optimisation combinatoire : de l'analyse structurelle d'un problème à la conception d'algorithmes efficaces

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.


Directrices : Clarisse Dhaenens, Professeur, Université Lille 1 Laetitia Jourdan, Professeur, Université Lille 1 Rapporteurs : Alexandre Caminada, Professeur, UTBM Frédéric Saubion, Professeur, Université Angers Membres : Laurence Duchien, Professeur, Université Lille 1 Thomas Stützle, Professeur, Université libre de Bruxelles (Belgique) Sébastien Verel, Maître de Conférence, Université Nice-Sophia Antipolis

Thèse de l'équipe soutenue le 9 décembre 2011

Retour vers les autres thèses