L’apprentissage automatique est un domaine en forte croissance à la fois dans le nombre de méthodes employées mais aussi dans le nombre de base de données mises à disposition des utilisateurs. La classification, qui est une tâche qui peut être abordée par l’apprentissage artificiel, est ainsi affectée par ce changement. La présence d’un grand nombre d’algorithmes de classification incite alors à créer des systèmes globaux −basés sur des comités de classifieurs− dont le but est de donner des solutions plus efficaces pour les problèmes de classification complexes. Pour cette raison, on traite dans cette thèse la problématique des systèmes multi-classifieurs ou bien les comités de classifieurs dans un sens général. Le but de mes travaux de recherche est alors la conception de systèmes multi-classifieurs assurant une amélioration des performances de classification ainsi qu’un certain niveau de robustesse. Cependant, une conception de tels systèmes de classifieurs, qu'on peut voir comme des sources d'informations différentes et qui seront entraînés sur des exemples d’apprentissage corrélés, engendre une dépendance dans les différentes décisions individuelles produites par ces classifieurs et par conséquent on rajoute le but de construire des systèmes multi-classifieurs qui s'adaptent à la dépendance à l’intérieur du comité. Ainsi, nous proposons deux solutions qui seront les principales contributions de cette thèse. La première est une approche possibiliste basée sur une règle de combinaison bien connue en logique floue, la t-norme tandis que la deuxième est une approche probabiliste basée sur les copules qui sont des modèles de dépendance entre variables aléatoires. / Machine learning is a rapidly growing field of science concerning both the number of methods used and the amount of data available for users. Classification is thus affected by these changes. The presence of a large number of classification algorithms thus encourages the creation of global systems that are based on classifier ensembles, in the purpose of providing efficient solutions to complex classification problems. This is the main motivation behind our thesis whose subject is the study of multi-classifiers systems. A multi-classifiers system is a set of classifiers whose decisions is aggregated according to a specific architecture and using a combination rule. There are different types architectures such as parallel, sequential or hybrid architectures. In this thesis, we are only interested in classifier ensembles having a parallel architecture. Briefly, the purpose of my research is then the design of multi-classifiers systems to improve classification performance and to offer certain level of robustness. However, the design of such systems, that can be seen as a fusion of different sources of information and which will be trained on correlated learning examples, generates dependence in the individual decisions of classifiers and consequently impose the creation of classifier ensembles that are adapted to dependency between individual classifiers. Thus, we propose two approaches that are the main contributions of this thesis. The first one is a possibilistic approach based on a well-known combination rule in fuzzy logic, the t-norm, while the second is a probabilistic approach based on a copula function which are models of dependence between random variables.

Les parsers en dépendances modernes ont des résultats comparables à ceux d'experts humains. Cependant, ils sont encore gourmands en données annotées et ces données ne sont disponibles que pour quelques langues. Pour rendre l'analyse syntaxique accessible aussi aux langues peu dotées, de nombreuses méthodes sont apparues comme le transfert de modèle ou d'annotation. Dans cette thèse, nous proposons de nouvelles méthodes de partage de l'information entre plusieurs langues en utilisant leurs traits grammaticaux communs.Nous utilisons cette morphologie partagée pour apprendre des représentations de mots délexicalisés qui aideront l'apprentissage de modèles d'analyse syntaxique. Nous proposons aussi une nouvelle méthode d'apprentissage nommée apprentissage phylogénétique qui utilise l'arbre généalogique des langues pour guider l'apprentissage des modèles. Enfin, à l'aide de notre mesure de la complexité morphosyntaxique nous étudions le rôle de la morphologie pour l'analyse en dépendances. / While modern dependency parsers have become as good as human experts, they still rely heavily on hand annotated training examples which are available for a handful of languages only. Several methods such as model and annotation transfer have been proposed to make high quality syntactic analysis available to low resourced languages as well. In this thesis, we propose new approaches for sharing information across languages relying on their shared morphological features. In a fist time, we propose to use shared morphological features to induce cross-lingual delexicalised word representations that help learning syntactic analysis models. Then, we propose a new multi-task learning framework called phylogenetic learning which learns models for related tasks/languages guided by the tasks/languages evolutionary tree. Eventually, with our new measure of morphosyntactic complexity we investigate the intrinsic role of morphological information for dependency parsing.

H Εργασία αυτή διαπραγματεύεται μια προσέγγιση για το αυτόματο φιλτράρισμα της ανεπιθύμητης Ηλ. Αλληλογραφίας βασισμένη σε μεθόδους Μηχανικής Μάθησης (Μ.Μ). Πιο συγκεκριμένα δημιουργήθηκε μια εφαρμογή εξαγωγής χαρακτηριστικών από Βάσεις Δεδομένων Ηλ. Αλληλογραφίας που υπάρχουν διαθέσιμες στον παγκόσμιο Ιστό και στην συνέχεια η προκύπτουσα γνώση ενσωματώθηκε σε ένα MUA που δημιουργήθηκε για τον σκοπό αυτό. Το σύνολο των προσπαθειών επικεντρώθηκε γύρω από αλγορίθμους Μ.Μ και πιο συγκεκριμένα Naïve Bayes, AdaBoost-Naïve-Bayes, C4.5, SVMs, Decision-Stump & AdaBoost, KStar, Random Forest, Νευρωνικά Δίκτυα, και RBF. Πιο ειδικά στην εργασία αναπτύσσονται τα παρακάτω : • Παρουσίαση της πορείας της Αυτόματης Κατηγοριοποίησης Κειμένου και των Tεχνικών/Aλγορίθμων Μηχανικής Μάθησης (Μ.Μ) στο συγκεκριμένο πρόβλημα. • Εξαγωγή παραμέτρων από Βάσεις ηλ. Αλληλογραφίας και σώματα ηλ. μηνυμάτων. • Αξιολόγηση της συμπεριφοράς των προαναφερθέντων αλγορίθμων Μ.Μ. • Βελτιστοποίηση της απόδοσης των αλγορίθμων με μελέτη της επίδρασης, του τύπου και του πλήθους των παραμέτρων του χαρακτηριστικού διανύσματος. • Ανάπτυξη του πραγματικού συστήματος φιλτραρίσματος και ενσωμάτωση του σε περιβάλλον διαχείρισης ηλ. Αλληλογραφίας. / -

Ce travail de thèse a été réalisé dans le contexte de la recommandation dynamique. La recommandation est l'action de fournir du contenu personnalisé à un utilisateur utilisant une application, dans le but d'améliorer son utilisation e.g. la recommandation d'un produit sur un site marchant ou d'un article sur un blog. La recommandation est considérée comme dynamique lorsque le contenu à recommander ou encore les goûts des utilisateurs évoluent rapidement e.g. la recommandation d'actualités. Beaucoup d'applications auxquelles nous nous intéressons génèrent d'énormes quantités de données grâce à leurs millions d'utilisateurs sur Internet. Néanmoins, l'utilisation de ces données pour évaluer une nouvelle technique de recommandation ou encore comparer deux algorithmes de recommandation est loin d'être triviale. C'est cette problématique que nous considérons ici. Certaines approches ont déjà été proposées. Néanmoins elles sont très peu étudiées autant théoriquement (biais non quantifié, borne de convergence assez large...) qu'empiriquement (expériences sur données privées). Dans ce travail nous commençons par combler de nombreuses lacunes de l'analyse théorique. Ensuite nous discutons les résultats très surprenants d'une expérience à très grande échelle : une compétition ouverte au public que nous avons organisée. Cette compétition nous a permis de mettre en évidence une source de biais considérable et constamment présente en pratique : l'accélération temporelle. La suite de ce travail s'attaque à ce problème. Nous montrons qu'une approche à base de bootstrap permet de réduire mais surtout de contrôler ce biais. / The context of this thesis work is dynamic recommendation. Recommendation is the action, for an intelligent system, to supply a user of an application with personalized content so as to enhance what is refered to as "user experience" e.g. recommending a product on a merchant website or even an article on a blog. Recommendation is considered dynamic when the content to recommend or user tastes evolve rapidly e.g. news recommendation. Many applications that are of interest to us generates a tremendous amount of data through the millions of online users they have. Nevertheless, using this data to evaluate a new recommendation technique or even compare two dynamic recommendation algorithms is far from trivial. This is the problem we consider here. Some approaches have already been proposed. Nonetheless they were not studied very thoroughly both from a theoretical point of view (unquantified bias, loose convergence bounds...) and from an empirical one (experiments on private data only). In this work we start by filling many blanks within the theoretical analysis. Then we comment on the result of an experiment of unprecedented scale in this area: a public challenge we organized. This challenge along with a some complementary experiments revealed a unexpected source of a huge bias: time acceleration. The rest of this work tackles this issue. We show that a bootstrap-based approach allows to significantly reduce this bias and more importantly to control it.

Les systèmes d’intelligence artificielle les plus puissants utilisent désormais des modèles statistiques. Afin de construire des modèles efficaces, ces systèmes doivent collecter une quantité substantielle de données issues de l’environnement. Les assistants personnels, maisons connectées, serveurs vocaux et autres systèmes de dialogue ne font pas exception. Ces systèmes ont pour vocation d’interagir avec des humains, et pour cela, leurs données d’apprentissage se doivent d’être collectées avec ces mêmes humains. Parce que le nombre d’interactions avec une seule personne est assez faible, l’approche usuelle pour augmenter le jeu de données consiste à agréger les données de tous les utilisateurs.Une des limitations de cette approche vient du fait que, par construction, les modèles entraînés ainsi ne sont efficaces qu’avec un humain "moyen" et n’incluent pas de système d’adaptation ; cette faiblesse entraîne la restriction du service à certains groupes de personnes; Par conséquent, cela réduit l’ensemble des utilisateurs et provoque des problèmes d’inclusion. La présente thèse propose des solutions impliquant la construction de systèmes de dialogue combinant l’apprentissage par transfert et l’apprentissage parrenforcement. La thèse explore deux pistes de recherche : La première consiste à inclure un mécanisme d’adaptation dès les premières interactions avec un nouvel utilisateur. Pour ce faire, nous utilisons la connaissance accumulée avec des utilisateurs déjà connus du système. La question sous-jacente est la suivante : comment gérer l’évolution du système suite à une croissance interrompue d’utilisateurs et donc de connaissance? La première approche implique le clustering des systèmes de dialogue (chacun étant spécialisé pour un utilisateur) en fonction de leurs stratégies. Nous démontrons que la méthode améliore la qualité des dialogues en interagissant avec des modèles à base de règles et des modèles d’humains. La seconde approche propose d’inclure un mécanisme d’apprentissage par transfert dans l’exécution d’un algorithme d’apprentissage profond par renforcement, Deep Q-learning. La seconde piste avance l’idée selon laquelle les premières interactions avec un nouvel utilisateur devraient être gérées par un système de dialogue sécurisé et précautionneux avant d’utiliser un système de dialogue spécialisé. L’approche se divise en deux étapes. La première étape consiste à apprendre une stratégie sécurisée avec de l’apprentissage par renforcement. À cet effet, nous proposons un nouveau framework d’apprentissage par renforcement sous contrainte en états continus ainsi que des algorithmes les solutionnant. En particulier, nous validons, en termes de sécurité et d’efficacité, une extension de Fitted-Q pour les deux applications sous contraintes : les systèmes de dialogue et la conduite autonome. La deuxième étape implique l’utilisation de ces stratégies sécurisées lors des premières interactions avec un nouvel utilisateur ; cette méthode est une extension de l’algorithme classique d’exploration, ε-greedy. / The most powerful artificial intelligence systems are now based on learned statistical models. In order to build efficient models, these systems must collect a huge amount of data on their environment. Personal assistants, smart-homes, voice-servers and other dialogue applications are no exceptions to this statement. A specificity of those systems is that they are designed to interact with humans, and as a consequence, their training data has to be collected from interactions with these humans. As the number of interactions with a single person is often too scarce to train a proper model, the usual approach to maximise the amount of data consists in mixing data collected with different users into a single corpus. However, one limitation of this approach is that, by construction, the trained models are only efficient with an "average" human and do not include any sort of adaptation; this lack of adaptation makes the service unusable for some specific group of persons and leads to a restricted customers base and inclusiveness problems. This thesis proposes solutions to construct Dialogue Systems that are robust to this problem by combining Transfer Learning and Reinforcement Learning. It explores two main ideas: The first idea of this thesis consists in incorporating adaptation in the very first dialogues with a new user. To that extend, we use the knowledge gathered with previous users. But how to scale such systems with a growing database of user interactions? The first proposed approach involves clustering of Dialogue Systems (tailored for their respective user) based on their behaviours. We demonstrated through handcrafted and real user-models experiments how this method improves the dialogue quality for new and unknown users. The second approach extends the Deep Q-learning algorithm with a continuous transfer process.The second idea states that before using a dedicated Dialogue System, the first interactions with a user should be handled carefully by a safe Dialogue System common to all users. The underlying approach is divided in two steps. The first step consists in learning a safe strategy through Reinforcement Learning. To that extent, we introduced a budgeted Reinforcement Learning framework for continuous state space and the underlying extensions of classic Reinforcement Learning algorithms. In particular, the safe version of the Fitted-Q algorithm has been validated, in term of safety and efficiency, on a dialogue system tasks and an autonomous driving problem. The second step consists in using those safe strategies when facing new users; this method is an extension of the classic ε-greedy algorithm.

L’apprentissage de modèles stochastiques générant des séquences a de nombreuses applications en traitement de la parole, du langage ou bien encore en bio-informatique. Les Automates à Multiplicité (MA) sont des modèles graphiques à variables latentes qui englobent une grande variété de systèmes linéaires pouvant en particulier représenter des langues stochastiques, des processus stochastiques ainsi que des processus contrôlés. Les algorithmes traditionnels d’apprentissage comme celui de Baum-Welch sont itératifs, lent et peuvent converger vers des optima locaux. Une alternative récente consiste à utiliser la méthode des moments (MoM) pour concevoir des algorithmes rapides et consistent avec des garanties pseudo-PAC. Cependant, les algorithmes basés sur la MoM ont deux inconvénients principaux. Tout d'abord, les garanties PAC ne sont valides que si la dimension du modèle appris correspond à la dimension du modèle cible. Deuxièmement, bien que les algorithmes basés sur la MoM apprennent une fonction proche de la distribution cible, la plupart ne contraignent pas celle-ci à être une distribution. Ainsi, un modèle appris à partir d’un nombre fini d’exemples peut renvoyer des valeurs négatives et qui ne somment pas à un. Ainsi, cette thèse s’adresse à ces deux problèmes. D’abord, nous proposons un élargissement des garanties théoriques pour les modèles compressés, ainsi qu’un algorithme spectral régularisé qui adapte la taille du modèle aux données. Puis, une application en guerre électronique est aussi proposée pour le séquencement des écoutes du récepteur superhétérodyne. D’autre part, nous dérivons de nouveaux algorithmes d’apprentissage ne souffrant pas du problème des probabilités négatives et dont certains bénéficient de garanties PAC. / Learning stochastic models generating sequences has many applications in natural language processing, speech recognitions or bioinformatics. Multiplicity Automata (MA) are graphical latent variable models that encompass a wide variety of linear systems. In particular, they can model stochastic languages, stochastic processes and controlled processes. Traditional learning algorithms such as the one of Baum-Welch are iterative, slow and may converge to local optima. A recent alternative is to use the Method of Moments (MoM) to design consistent and fast algorithms with pseudo-PAC guarantees. However, MoM-based algorithms have two main disadvantages. First, the PAC guarantees hold only if the size of the learned model corresponds to the size of the target model. Second, although these algorithms learn a function close to the target distribution, most do not ensure it will be a distribution. Thus, a model learned from a finite number of examples may return negative values or values that do not sum to one. This thesis addresses both problems. First, we extend the theoretical guarantees for compressed models, and propose a regularized spectral algorithm that adjusts the size of the model to the data. Then, an application in electronic warfare is proposed to sequence of the dwells of a super-heterodyne receiver. Finally, we design new learning algorithms based on the MoM that do not suffer the problem of negative probabilities. We show for one of them pseudo-PAC guarantees.

Dans cette thèse nous étudions différentes généralisations du problème dit « du bandit manchot ». Le problème du bandit manchot est un problème de décision séquentiel au cours duquel un agent sélectionne successivement des actions et obtient une récompense pour chacune d'elles. On fait généralement l'hypothèse que seule la récompense associée à l'action choisie est observée par l'agent, ce dernier ne reçoit aucune information sur les actions non choisies. Cette hypothèse s'avère parfois très restrictive pour certains problèmes très structurés tels que les systèmes de recommandations, la publicité en ligne, le routage de paquets, etc. Il paraît assez naturel de tenir compte de la connaissance de la structure du problème pour améliorer les performances des algorithmes d'apprentissage usuels. Dans cette thèse, nous nous focalisons sur les problèmes de bandits présentant une structure pouvant être modélisée par un graphe dont les nœuds représentent les actions. Dans un premier temps, nous étudierons le cas où les arêtes du graphe modélisent les similitudes entre actions. Dans un second temps, nous analyserons le cas où l'agent observe les récompenses de toutes les actions adjacentes à l'action choisie dans le graphe. Notre contribution principale a été d'élaborer de nouveaux algorithmes permettant de traiter efficacement les problèmes évoqués précédemment, et de démontrer théoriquement et empiriquement le bon fonctionnement de ces algorithmes. Nos travaux nous ont également amenés à introduire de nouvelles grandeurs, telles que la dimension effective et le nombre d'indépendance effectif, afin de caractériser la difficulté des différents problèmes. / This thesis studies several extensions of multi-armed bandit problem, where a learner sequentially selects an action and obtain the reward of the action. Traditionally, the only information the learner acquire is about the obtained reward while information about other actions is hidden from the learner. This limited feedback can be restrictive in some applications like recommender systems, internet advertising, packet routing, etc. Usually, these problems come with structure, similarities between users or actions, additional observations, or any additional assumptions. Therefore, it is natural to incorporate these assumptions to the algorithms to improve their performance. This thesis focuses on multi-armed bandit problem with some underlying structure usually represented by a graph with actions as vertices. First, we study a problem where the graph captures similarities between actions; connected actions tend to grand similar rewards. Second, we study a problem where the learner observes rewards of all the neighbors of the selected action. We study these problems under several additional assumptions on rewards (stochastic, adversarial), side observations (adversarial, stochastic, noisy), actions (one node at the time, several nodes forming a combinatorial structure in the graph). The main contribution of this thesis is to design algorithms for previously mentioned problems together with theoretical and empirical guaranties. We also introduce several novel quantities, to capture the difficulty of some problems, like effective dimension and effective independence number.

Nous proposons des méthodes pour caractériser efficacement les arêtes au sein de réseaux complexes. Dans les graphes simples, les nœuds sont liés par une sémantique unique, tels deux utilisateurs amis dans un réseau social. De plus, ces arêtes sont guidées par la similarité entre les nœuds (homophilie). Ainsi, les membres deviennent amis à cause de caractéristiques communes. En revanche, les réseaux complexes sont des graphes où chaque arête possède une sémantique parmi k possibles. Ces arêtes sont de plus basées à la fois sur une homophilie et une hétérophilie partielle. Cette information supplémentaire permet une analyse plus fine de graphes issus d’applications réelles. Cependant, elle peut être coûteuse à acquérir, ou même être indisponible. Nous abordons donc le problème d’inférer la sémantique des arêtes. Nous considérons d'abord les graphes dont les arêtes ont deux sémantiques opposées, et où seul une fraction des étiquettes est visibles. Ces «graphes signés» sont une façon élégante de représenter des interactions polarisées. Nous proposons deux biais d’apprentissage, adaptés respectivement aux graphes signés dirigés ou non, et plusieurs algorithmes utilisant la topologie du graphe pour résoudre un problème de classification binaire. Ensuite, nous traitons les graphes avec k > 2 sémantiques possibles. Dans ce cas, nous ne recevons pas d’étiquette d’arêtes, mais plutôt un vecteur de caractéristiques pour chaque nœud. Face à ce problème non supervisé, nous concevons un critère de qualité exprimant dans quelle mesure une k-partition des arêtes et k vecteurs sémantiques expliquent les arêtes observées. Nous optimisons ce critère sous forme vectorielle et matricielle. / We develop methods to efficiently and accurately characterize edges in complex networks. In simple graphs, nodes are connected by a single semantic. For instance, two users are friends in a social networks. Moreover, those connections are typically driven by node similarity, according to homophily. In the previous example, users become friends because of common features. By contrast, complex networks are graphs where every connection has one semantic among k possible ones. Those connections are moreover based on both partial homophily and heterophily of their endpoints. This additional information enable finer analysis of real world graphs. However, it can be expensive to acquire, or is sometimes not known beforehand. We address the problems of inferring edge semantics in various settings. First, we consider graphs where edges have two opposite semantics, and where we observe the label of some edges. These so-called signed graphs are a common way to represent polarized interactions. We propose two learning biases suited for directed and undirected signed graphs respectively. This leads us to design several algorithms leveraging the graph topology to solve a binary classification problem that we call edge sign prediction. Second, we consider graphs with k > 2 available semantics for edge. In that case of multilayer graphs, we are not provided with any edge label, but instead are given one feature vector for each node. Faced with such an unsupervised problem, we devise a quality criterion expressing how well an edge k-partition and k semantical vectors explains the observed connections. We optimize this goodness of explanation criterion in vectorial and matricial forms.

Dans cette thèse, nous abordons deux problèmes principaux, à savoir l'évaluation quantitative des algorithmes de segmentation de maillages ainsi que la segmentation de maillages par apprentissage en exploitant le facteur humain.Tout d'abord, nous proposons un benchmark dédié à l'évaluation des algorithmes de segmentation de maillages 3D. Le benchmark inclut un corpus de segmentation vérités-terrains réalisées par des volontaires ainsi qu'une nouvelle métrique de similarité pertinente qui quantifie la cohérence entre ces segmentations vérités-terrains et celles produites automatiquement par un algorithme donné sur les mêmes modèles. De plus, nous menons un ensemble d'expérimentations, y compris une expérimentation subjective, pour respectivement démontrer et valider la pertinence de notre benchmark. Nous proposons ensuite un algorithme de segmentation par apprentissage. Pour cela, l'apprentissage d'une fonction d'arête frontière est effectué, en utilisant plusieurs critères géométriques, à partir d'un ensemble de segmentations vérités-terrains. Cette fonction est ensuite utilisée, à travers à une chaîne de traitement pour segmenter le maillage en entrée. Nous montrons, à travers une série d'expérimentations s'appuyant sur différents benchmarks, les excellentes performances de notre algorithme par rapport à ceux de l'état de l'art. Enfin, nous proposons une application de notre algorithme de segmentation pour l'extraction de squelettes cinématiques pour les maillages 3D dynamiques, et présentons quelques résultats prometteurs. / In this thesis, we address two main problems namely the quantitative evaluation of mesh segmentation algorithms and learning mesh segmentation by exploiting the human factor. First, we propose a benchmark dedicated to the evaluation of mesh segmentation algorithms. The benchmark includes a human-made ground-truth segmentation corpus and a relevant similarity metric that quantifies the consistency between these ground-truth segmentations and automatic ones produced by a given algorithm on the same models. Additionally, we conduct extensive experiments including subjective ones to respectively demonstrate and validate the relevance of our benchmark. Then, we propose a new learning mesh segmentation algorithm. A boundary edge function is learned, using multiple geometric criteria, from a set of human segmented training meshes and then used, through a processing pipeline, to segment any input mesh. We show, through a set of experiments using different benchmarks, the performance superiority of our algorithm over the state-of-the-art. Finally, we propose an application of our segmentation algorithm for kinematic skeleton extraction of dynamic 3D-meshes, and present some early promising results.

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.