. "Parallel hybrid optimization methods for permutation based problems" . "Arbres de d\u00E9cision" . "Algorithmes parall\u00E8les" . "2011" . "Parallel hybrid optimization methods for permutation based problems" . . "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." . . "M\u00E9thodes d'optimisation parall\u00E8les hybrides pour les probl\u00E8mes de permutation" . "La r\u00E9solution efficace de probl\u00E8mes d'optimisation \u00E0 permutation de grande taille n\u00E9cessite le d\u00E9veloppement de m\u00E9thodes hybrides complexes combinant diff\u00E9rentes classes d'algorithmes d'optimisation. L'hybridation des m\u00E9taheuristiques avec les m\u00E9thodes 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\u00E9thodes utilis\u00E9es s\u00E9par\u00E9ment. Le d\u00E9fi principal dans le d\u00E9veloppement de telles m\u00E9thodes consiste \u00E0 trouver des liens ou connections entre les strat\u00E9gies de recherche divergentes utilis\u00E9s dans les deux classes de m\u00E9thodes. Les Algorithmes G\u00E9n\u00E9tiques (AGs) sont des m\u00E9taheuristiques, \u00E0 base de population, tr\u00E8s populaires bas\u00E9s sur des op\u00E9rateurs stochastiques inspir\u00E9s de la th\u00E9orie de l'\u00E9volution. Contrairement aux AGs et aux m\u00E9taheuristiques g\u00E9n\u00E9ralement, les algorithmes de B&B sont bas\u00E9s sur l'\u00E9num\u00E9ration implicite de l'espace de recherche repr\u00E9sent\u00E9 par le moyen d'un arbre, dit arbre de recherche. Notre approche d'hybridation consiste \u00E0 d\u00E9finir un codage commun des solutions et de l'espace de recherche ainsi que des op\u00E9rateurs de recherche ad\u00E9quats afin de permettre un couplage efficace de bas niveau entre les deux classes de m\u00E9thodes AGs et B&B. La repr\u00E9sentation de l'espace de recherche par le moyen d'arbres est traditionnellement utilis\u00E9e dans les algorithmes de B&B. Dans cette th\u00E8se, cette repr\u00E9sentation a \u00E9t\u00E9 adapt\u00E9e aux m\u00E9taheuristiques. L'encodage des permutations au moyen de nombres naturels faisant r\u00E9f\u00E9rence \u00E0 l'ordre d'\u00E9num\u00E9ration lexicographique des permutations dans l'arbre du B&B, est propos\u00E9 comme une nouvelle mani\u00E8re de repr\u00E9senter l'espace de recherche des probl\u00E8mes \u00E0 permutations dans les m\u00E9taheuristiques. Cette m\u00E9thode de codage est bas\u00E9e sur les propri\u00E9t\u00E9s math\u00E9matiques des permutations, \u00E0 savoir les codes de Lehmer et les tables d'inversions ainsi que les syst\u00E8me d'\u00E9num\u00E9ration factoriels. Des fonctions de transformation permettant le passage entre les deux repr\u00E9sentations (permutations et nombres) ainsi que des op\u00E9rateurs de recherche adapt\u00E9s au codage, sont d\u00E9finis pour les probl\u00E8mes \u00E0 permutations g\u00E9n\u00E9ralis\u00E9s. Cette repr\u00E9sentation, d\u00E9sormais commune aux m\u00E9taheuristiques et aux algorithmes de B&B, nous a permis de concevoir des strat\u00E9gies 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\u00E9s sur cette repr\u00E9sentation commune ont \u00E9t\u00E9 propos\u00E9es dans cette th\u00E8se. Pour validation, une impl\u00E9mentation a \u00E9t\u00E9 r\u00E9alis\u00E9e pour le probl\u00E8me d'affectation quadratique \u00E0 trois dimension (Q3AP). Afin de r\u00E9soudre de larges instances de ce probl\u00E8me, nous avons aussi propos\u00E9 une parall\u00E9lisation pour les deux algorithmes hybrides, bas\u00E9e sur des techniques de d\u00E9composition d'espace (d\u00E9composition par intervalle) utilis\u00E9es auparavant pour la parall\u00E9lisation des algorithmes de B&B. Du point de vue impl\u00E9mentation, afin de faciliter de futurs conceptions et impl\u00E9mentations de m\u00E9thodes hybrides combinant m\u00E9taheuristiques et m\u00E9thodes exacte arborescentes, nous avons d\u00E9velopp\u00E9 une plateforme d'hybridation int\u00E9gr\u00E9e au logiciel pour m\u00E9taheuristiques, ParadisEO. La nouvelle plateforme a \u00E9t\u00E9 utilis\u00E9e pour r\u00E9aliser des exp\u00E9rimentations intensives sur la grille de calcul Grid'5000." . "Optimisation combinatoire" . "Algorithmes g\u00E9n\u00E9tiques" . . "Grilles informatiques" . . . . "Th\u00E8ses et \u00E9crits acad\u00E9miques" . . . . . "Algorithme de s\u00E9paration - \u00E9limination" . . . "Permutations (math\u00E9matiques)" . . . . . . "Heuristique" . . . "Text" . "Affectation quadratique" .