Logo du LIFL

Depuis le 1er janvier 2015 le LIFL et le LAGIS forment le laboratoire CRIStAL

  1. Doctoral studies

Thesis of

Malika Mehdi

Thursday 20 October 2011
Université (Luxembourg)

Parallel hybrid optimization methods for permutation-based problems

Co-directeurs : Pascal Bouvry, Professeur, Université du Luxembourg
El-Ghazali Talbi, Professeur, Université Lille 1
Nouredine Melab, Professeur, Université Lille 1
Rapporteurs : Enrique Alba, Professeur, Université de Málaga (Espagne)
Didier El Baz, Chargé de Recherche HDR, LAAS/CNRS
Membre : Raymond Bisdorff, Professeur, Université du Luxembourg

Solving efficiently large benchmarks of NP-hard permutation-based problems requires the development of hybrid methods combining different classes of optimization methods. Indeed, it is now acknowledged that such methods perform better than traditional optimization methods when used separately. The key challenge is how to find connections between the divergent search strategies used in each class of methods in order to build efficient hybridization strategies. Genetic algorithms (GAs) are very popular population-based metaheuristics based on stochastic evolutionary operators. The hybridization of GAs with tree-based exact methods such as Branch-and-Bound is a promising research trend. B\&B algorithms are based on an implicit enumeration of the solution space represented as a tree. Our hybridization approach consists in providing a common solution and search space coding and associated search operators enabling an efficient cooperation between the two methods. The tree-based representation of the solution space is traditionally used in B\&B algorithms to enumerate the solutions of the problem at hand. In this thesis, this special representation is adapted to metaheuristics. The encoding of permutations as natural numbers, which refer to their lexicographic enumeration in the tree, is proposed as a new way to represent the solution space of permutation problems in metaheuristics. This encoding approach is based on the mathematical properties of permutations (Lehmer codes, inversion tables, etc.). This common representation allows the design of efficient cooperation strategies between GAs and B\&B algorithms. In order to solve large benchmarks of permutation-based problems, a parallelization of the hybrid methods have been developed using the B&B tree. The proposed methods have been validated on standard benchmarks of one of the hardest permutation-based problems, the three dimensional quadratic assignment problem (Q3AP). To this purpose, extensive experiments have been conducted over the computational grid Grid'5000


UMR 8022 - Laboratoire d'Informatique Fondamentale de Lille - Copyright © 2012 Sophie TISON - Crédits & Mentions légales

Page respectant XHTML et CSS.

Pour tout commentaire / Comments and remarks : webmaster