Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Dans ce mémoire, nous nous intéressons à des algorithmes de sélection de modèles dans un contexte de régression linéaire et logistique. Nous expliquons premièrement les notions de régression linéaire et logistique et deux critères de sélection, AIC et BIC. Ensuite, nous faisons une revue des aspects théoriques des algorithmes les plus connus en détaillant deux d'entre eux, Leaps and Bounds et Occam’s Window. Pour ces deux derniers, nous présentons aussi les détails pratiques des logiciels qui font leur implantation. La partie finale est consacrée à l'étude des trois méthodes de sélection des modèles basées sur les algorithmes Leaps and Bounds, Occam’s Window et sur une combinaison entre les deux, en utilisant la technique du moyennage de modèles. Nous présentons les performances de prédiction calculées à l'aide de la technique de validation croisée et les temps d'exécution de ces trois méthodes pour plusieurs jeux de données. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : sélection de modèles, moyennage de modèles, régression linéaire, régression logistique, AIC, BIC, algorithme Leaps and Bounds, algorithme Occam’s Window, validation croisée.

Les métaheuristiques de colonies de fourmis s'inspirent des comportements collectifs observés chez les fourmis pour résoudre des problèmes d'optimisation difficile.<br /><br />La première approche pour concevoir des métaheuristiques d'optimisation continue en suivant cette métaphore consiste à créer un système multi-agent. Nous proposons ainsi un algorithme de "colonies de fourmis interagissantes" (CIAC). La deuxième approche décrit ces métaheuristiques comme des méthodes manipulant un échantillonnage d'une distribution de probabilité. Nous proposons ainsi un algorithme "à estimation de distribution" (CHEDA).<br /><br />En accord avec le concept de programmation à mémoire adaptative, nos algorithmes font l'objet d'une hybridation avec une recherche locale de Nelder-Mead (HCIAC). Nous avons ensuite adapté cette méthode à des problèmes continus dynamiques (DHCIAC), pour lesquels nous proposons également un nouveau jeu de test cohérent.<br /><br />Nos algorithmes sont enfin appliqués dans le cadre de l'automatisation du suivi des lésions de l'oeil.

Les courbes algébriques affines sont un outil qui est appliqué dans plusieurs domains, par example le CAGD. Elles sont définies par des polynômes, mais souvent elles ont plusieurs composantes irréductibles distinctes. Dans cette thèse on développe des algorithmes efficaces pour la décomposition d'une courbe definie par des polynômes rationelles. Dans la première partie on présente un algorithme de factorisation absolue pour polynômes en deux variables (problème equivalent à la décomposition de courbes dans le plan). On part de l'algorithme existant TKTD et on améliore la définition de l'extension de corps nécessaire à la factorisation, utilisant des techniques modulaires et l'algorithme LLL pour identifier un nombre algébrique de son approximation p-adique. Dans la deuxième partie on passe au problème de décomposer une courbe dans l'espace tridimensionel: l'équivalent de la factorisation pour le cas du plan est la décomposition primaire d'un idéal pour le cas des 3 dimensions. D'abord on montre des bornes sur les degrées des surfaces qui séparent les différentes composantes, utilisant des résultats classiques de géometrie algébrique, comme le "Lifting problem" ou la regularité de Castelnuovo-Mumford. Après, on considère un algorithme de décomposition classique, mais pas efficace du point de vue computationel, auquel on applique les techniques modulaires. On obtient un algorithme modulaire qui donne la fonction d'Hilbert des composantes réduites de la courbe. Les deux algorithmes principales ont été testés sur plusieurs examples et comparés avec le temps d'exécution d'autres logiciels.

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.

Dans ce travail, nous nous intéressons à la résolution exacte de problèmes de localisation de service en variables mixtes. Les problèmes de programmation linéaire bi-objectif en variables mixtes ont été très étudiés dans les dernières années, mais uniquement dans un contexte générique. De même, les problèmes de localisation de services bi-objectif n’ont été étudiés que dans un cas purement discret. Nous considérons dans un premier temps le problème de localisation de services bi-objectif sans capacité. Afin de le résoudre, nous adaptons la méthode de pavage par boîtes proposée pour le cas discret. Les boîtes rectangulaires deviennent triangulaires dans le cas mixte. De plus, leur exploration est grandement facilitée, ce qui déplace la difficulté du problème dans l’énumération et le filtrage de ces boîtes. Différentes stratégies d’énumération sont proposées. Le problème de localisation de services bi-objectif avec capacité est ensuite considéré. Tout d’abord, une adaptation de la méthode de pavage par boîtes triangulaires est réalisée pour le cas avec capacité. Cependant, la nature du problème rend cette méthode beaucoup plus limitée. Nous considérons ensuite une méthode en deux phases dont la principale routine d’exploration repose sur une adaptation d’un algorithme de branch and bound initialement proposé par Beasley, dans le contexte bi-objectif. Les résultats expérimentaux sur des instances aux caractéristiques variées attestent de la pertinence des méthodes que nous proposons. / The purpose of this work is the exact solution of biobjective mixed-integer facility location problems. Biobjective mixed integer linear programming problem have been largely studied in recent years but only in the generic context. The same way, the study of biobjective facility location problems has been restricted to the discrete case. We consider first the bi-objective uncapacitated facility location problem. To solve it, we adapt the box paving method proposed for the discrete case. Rectangular boxes become triangular. Moreover, their exploration becomes considerably easier. The difficulty of the problem is therefore translated to the enumeration and the filtering of these boxes. Different enumeration strategies are proposed. Next, we consider the bi-objective capacitated facility location problem. We first propose an adaptation of the triangular box paving method to the capacitated case. However, the structure of the problem highly limits the method. Thus, we consider a two phase method. The main exploration routine is based on the adaptation of a branch and bound algorithm proposed by Beasley that we adapt to the bi-objective context. Experimental results on various instances show the efficiency of the proposed methods.

Le problème de localisation de hubs et tournées combinées (Hub Location-Routing Problem, HLRP), concerne la conception d’un réseau de transport performant entre de nombreuses origines (fournisseurs) et destinations (clients). Ce système est basé sur la localisation de plates formes (hubs) permettant de concentrer les flux et l’organisation de tournées pour la collecte des marchandises des fournisseurs et la distribution vers les clients. Nous étudions le cas spécifique du HLRP à capacités et allocations uniques (CSAHLRP) et de processus de tournées de collecte et distribution séparés. Nous proposons un modèle de programmation linéaire mixte (MILP) et un Algorithme Mémétique (MA) pour ce problème en vue de la minimisation du coût total du réseau de transport. De plus, nous étendons le modèle MILP pour le cas bi-objectif afin de minimiser à la fois le coût total et les émissions de CO2 du transport. Notre algorithme Mémétique (MA) et adapté et combiné à un algorithme génétique de tri non-dominé élitiste rapide (NSGAII) afin de déterminer des approximations du front de Pareto. Enfin, nous proposons une procédure en deux phases pour résoudre le HLRP mono objectif, comportant la résolution du problème de localisation des hubs (HLP) suivi pour chaque hub de la résolution de deux problèmes de tournées relatifs à la collecte et la livraison. Notre modèle MILP mono objectif est décomposé et notre MA est adapté pour résoudre le problème suivant ces deux étapes. Un ensemble d’instances de différents tailles et caractéristiques a été développée afin de conduire des expérimentations et de valider nos approches de résolution de ces différents problèmes. / We study the Hub Location-Routing Problem (HLRP) aiming at the design of an efficient freight transportation network for LTL (less-than-truck) transport between many origins (suppliers) and destinations (clients). Such a network relies on the location of consolidation hubs, the organization of routings for the collection/distribution of freight from suppliers to hubs and from hubs to clients, as well as direct shipment of consolidated freight between hubs. We focus on the Capacitated Single Allocation Hub Location-Routing Problem (CSAHLRP) in the case of distinct collection and delivery processes. We propose mixed integer linear programming (MILP) model and a Memetic Algorithm (MA) to solve the problem for minimizing the total cost of the network. Then we extend the model into a bi-objective model for minimizing both the total cost and CO2 emissions of transport. A modified memetic algorithm (MA) combined with a fast elitist non-dominated sorting genetic algorithm (NSGAII) is developed to capture the trade-off between minimizing total cost and CO2 emissions and exhibit approximations of the Pareto front. At last, a two step procedure is proposed to solve the single-objective HLRP based on a hub location problem (HLP) and two distinct vehicle routing problems for suppliers and clients allocated to each hub by the first step. Our single objective MILP model is decomposed accordingly and our MA is adapted to solve the HLRP following these two steps. A data base of instances of different sizes and characteristics has been developed in order to conduct extensive experiments for solving all these problems using the different solution techniques and validate our approaches.

L'histoire du silicium cristallin cSi et de sa forme oxydée (silice aSiO2) est intimement liée au développement des transistors depuis les années 1960. La miniaturisation de ces composants au fil du temps, permettant d'améliorer la puissance des ordinateurs avec une régularité proche de celle prédite par la loi de Moore, nécessite aujourd'hui une compréhension de la physique de ces systèmes à l'échelle nanométrique. Face aux coûts nécessaires pour réaliser des expériences à de si petites échelles, la simulation numérique – et plus particulièrement la dynamique moléculaire (MD) est un outil de premier choix. Nous appliquons ainsi, dans ce mémoire de thèse, la MD classique au cas des transistors silicium-sur-isolant (SOI), afin de déterminer la résistance thermique de l'interface cSi-aSiO2, qui peut se révéler être un facteur limitatif de la dissipation thermique dans les transistors ultrafins. Après avoir exposé le principe de la MD classique (chapitre 1) et présenté des pistes pour optimiser la recherche des voisins (chapitre 2), nous proposons dans le chapitre 3 les étapes que nous avons suivies pour former nos systèmes silicium-silice, ainsi qu'une manière de caractériser l'interface pour de tels systèmes. Enfin, dans le chapitre 4, nous développons une méthode – l'approach-to-equilibrium molecular dynamics (AEMD) –, qui nous permet d'obtenir une valeur de la résistance pour l'interface cSi-aSiO2 estimée à 3,6.10-10 m2.K.W-1. / Since the 60s, the history of crystalline silicon cSi and its oxyde (silica, aSiO2) is driven by the emergence of the new transistors. The miniaturization of these technologies, which enabled an increase in computers performances closely related to the Moore law, implies nowadays a nanometric scale comprehension of the physics in these systems. Because of the important costs of nanoscale experiments, numerical simulations and especially molecular dynamics (MD) are often used as a first-choice tool to investigate this kind of problems. In this thesis, we also apply classical MD to the case of silicon-on-insulator (SOI) transistors in order to determine the Kapitza resistance of a cSi-aSiO2 interface, which could be a source of slowdown for the thermal dissipation in ultra thin body and box (UTB²) transistors. We first expose the principle of classical MD (chapter 1) and show some ideas to optimize the neighbour search algorithms (chapter 2). In chapter 3 we explain the steps to form our silicon-silica systems and propose a way to characterize the interface. Finally, in chapter 4 we develop a method – called approach-to-equilibrium molecular dynamics (AEMD) – which allows us to estimate the value of the interfacial resistance interface to be 3.6*10-10 m2.K.W-1.

No description available.

Nous présentons dans ce mémoire des outils permettant de généraliser une méthode de cartographie génétique fine. Nous y résumons les concepts de base de la statistique génétique et y décrivons aussi la méthode de cartographie génétique fine que nous cherchons à généraliser en permettant l'utilisation de génotypes plutôt que d'haplotypes. Pour ce faire, nous comparons diverses méthodes reconnues d'estimation d'haplotypes. Le développement nouveau de ce travail consiste en un algorithme EM conditionnel aux phénotypes permettant d'estimer les haplotypes associés à un échantillon de génotype, ainsi que le statut au gène causal du caractère étudié. Nous généralisons la méthode de cartographie par l'ajout d'étapes au modèle d'échantillonnage pondéré. Nous effectuons finalement quelques tests par simulation. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Algorithme EM, Cartographie génétique, Coalescence, Diplotype, Échantillonnage pondéré, Estimation, Génotype, Gène causal, Haplotype, Modèle de pénétrance, Phénotype, Vraisemblance composite.