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. / 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.

La lithographie et la loi de Moore ont permis des avancées extraordinaires dans la fabrication des circuits intégrés. De nos jours, plusieurs systèmes très complexes peuvent être embarqués sur la même puce électronique. Les contraintes de développement de ces systèmes sont tellement grandes qu’une bonne planification dès le début de leur cycle de développement est incontournable. Ainsi, la planification de la gestion énergétique au début du cycle de développement est devenue une phase importante dans la conception de ces systèmes. Pendant plusieurs années, l’idée était de réduire la consommation énergétique en ajoutant un mécanisme physique une fois le circuit créé, comme par exemple un dissipateur de chaleur. La stratégie actuelle est d’intégrer les contraintes énergétiques dès les premières phases de la conception des circuits. Il est donc essentiel de bien connaître la dissipation d’énergie avant l’intégration des composantes dans une architecture d’un système multiprocesseurs de façon à ce que chaque composante puisse fonctionner efficacement dans les limites de ses contraintes thermiques. Lorsqu’une composante fonctionne, elle consomme de l’énergie électrique qui est transformée en dégagement de chaleur. Le but de ce mémoire est de trouver une affectation efficace des composantes dans une architecture de multiprocesseurs en trois dimensions en tenant compte des limites des facteurs thermiques de ce système. / Lithography and Moore’s law have led to extraordinary advances in integrated circuits manufacturing. Nowadays, many complex systems can be embedded on the same chip. Development constraints of these systems are so significant that a good planning from the beginning of the development stage is essential. Thus, the planning of energy management at the beginning of the development cycle has become important in the design of these systems. For several years, the idea was to reduce energy consumption by adding a cooling system once the circuit is created, a heat sink for example. The current strategy is to integrate energy constraints in the early stages of circuits design. It is therefore important to know the energy dissipation before the integration of the components in the architecture of a multiprocessor system so that each component can work within the limits of its thermal stresses. When a component is running, it consumes electric energy which is converted into heat. The aim of this thesis is to find an efficient assignment of components in a multiprocessor system architecture in three dimensions, taking into account the limits of its thermal factors.