Note publique d'information : La résolution efficace de problèmes d'optimisation à permutation de grande taille
nécessite le développement de méthodes hybrides complexes combinant différentes classes
d'algorithmes d'optimisation. L'hybridation des métaheuristiques avec les méthodes
exactes arborescentes, tel que l'algorithme du branch-and-bound (B&B), engendre une
nouvelle classe d'algorithmes plus efficace que ces deux classes de méthodes utilisées
séparément. Le défi principal dans le développement de telles méthodes consiste à
trouver des liens ou connections entre les stratégies de recherche divergentes utilisés
dans les deux classes de méthodes. Les Algorithmes Génétiques (AGs) sont des métaheuristiques,
à base de population, très populaires basés sur des opérateurs stochastiques inspirés
de la théorie de l'évolution. Contrairement aux AGs et aux métaheuristiques généralement,
les algorithmes de B&B sont basés sur l'énumération implicite de l'espace de recherche
représenté par le moyen d'un arbre, dit arbre de recherche. Notre approche d'hybridation
consiste à définir un codage commun des solutions et de l'espace de recherche ainsi
que des opérateurs de recherche adéquats afin de permettre un couplage efficace de
bas niveau entre les deux classes de méthodes AGs et B&B. La représentation de l'espace
de recherche par le moyen d'arbres est traditionnellement utilisée dans les algorithmes
de B&B. Dans cette thèse, cette représentation a été adaptée aux métaheuristiques.
L'encodage des permutations au moyen de nombres naturels faisant référence à l'ordre
d'énumération lexicographique des permutations dans l'arbre du B&B, est proposé comme
une nouvelle manière de représenter l'espace de recherche des problèmes à permutations
dans les métaheuristiques. Cette méthode de codage est basée sur les propriétés mathématiques
des permutations, à savoir les codes de Lehmer et les tables d'inversions ainsi que
les système d'énumération factoriels. Des fonctions de transformation permettant le
passage entre les deux représentations (permutations et nombres) ainsi que des opérateurs
de recherche adaptés au codage, sont définis pour les problèmes à permutations généralisés.
Cette représentation, désormais commune aux métaheuristiques et aux algorithmes de
B&B, nous a permis de concevoir des stratégies d'hybridation et de collaboration efficaces
entre les AGs et le B&B. En effet, deux approches d'hybridation entre les AGs et les
algorithmes de B&B (HGABB et COBBIGA) basés sur cette représentation commune ont été
proposées dans cette thèse. Pour validation, une implémentation a été réalisée pour
le problème d'affectation quadratique à trois dimension (Q3AP). Afin de résoudre de
larges instances de ce problème, nous avons aussi proposé une parallélisation pour
les deux algorithmes hybrides, basée sur des techniques de décomposition d'espace
(décomposition par intervalle) utilisées auparavant pour la parallélisation des algorithmes
de B&B. Du point de vue implémentation, afin de faciliter de futurs conceptions et
implémentations de méthodes hybrides combinant métaheuristiques et méthodes exacte
arborescentes, nous avons développé une plateforme d'hybridation intégrée au logiciel
pour métaheuristiques, ParadisEO. La nouvelle plateforme a été utilisée pour réaliser
des expérimentations intensives sur la grille de calcul Grid'5000.
Note publique d'information : 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.). Mapping functions between
the two representations (permutations and numbers) and special search operators adapted
to the encoding are defined for general permutation problems, with respect to the
theory of representation. This common representation allows the design of efficient
cooperation strategies between GAs and B\&B algorithms. In this thesis, two hybridization
schemes combining GAs with B\&B based on this common representation are proposed.
The two hybridization approaches HGABB/HAGABB (Hybrid Adaptive GA-B\&B) and COBBIGA
(cooperative B&B interval-based GA), have been validated on standard benchmarks of
one of the hardest permutation-based problems, the three dimensional quadratic assignment
problem (Q3AP). In order to solve large benchmarks of permutation-based problems,
a parallelization for computational grids is also proposed for the two hybrid schemes.
This parallelization is based on space decomposition techniques (the decomposition
by intervals) used in parallel B\&B algorithms. From the implementation point of view,
in order to facilitate further design and implementation of hybrid methods combining
metaheuristics with tree-based exact methods, a hybridization C++ framework integrated
to the framework for metaheuristics ParadisEO is developed. The new framework is used
to conduct extensive experiments over the computational grid Grid'5000.