Dans la présente thèse de doctorat je présente des résultats concernant des modèles désordonnés et frustrés venant de la physique statistique et de l'optimisation combinatoire. Comme application de la théorie des verres de spins, j'étudie le modèle de Blume, Emery et Griffiths désordonné et frustré. Ce modèle est traité dans l'approximation de champ moyen dans le cadre de la méthode des répliques A l'aide de l'Ansatz symétrique dans les répliques je présente une solution numérique complète puis je discute des effets de brisure de cette symétrie La stabilité de la solution symétrique a été Rudik et les régions instables identifiées Le diagramme de phase exhibe des transitions de premier et de second ordre. Le point tricritique persiste dans le modèle frustré, Ce qui est en accord avec des travaux antérieurs une version du modèle BEG avec un potentiel chimique désordonné a également été étudiée. les calculs confirment que le point tricritique apparaît à plus basse température quand il y a du désordre. Ensuite je considère le problème de la bipartition d'un graphe. Ce problème correspond du point de vue de la physique statistique h un verre de spins soumis h une contrainte d'aimantation totale nulle. je considère les propriétés statistiques des solutions de faible énergie engendrées par des algorithmes heuristiques. de tels algorithme sont en général conçus pour résoudre des problèmes d'optimisation combinatoire qui sont NP- difficiles. Plusieurs heuristiques ont 60 implémentées pour le problème de la bipartition de graphe. des lois d'échelle ont été obtenues : en particulier la moyenne et la variance du coût obéissent A une loi linéaire en N. Par conséquent le coût obtenu par des heuristiques est une quantité auto-moyennante. je suggère que cette propriété est générale valable aussi pour les solutions aléatoires pour les solutions quasi-optimales et pour les solutions optimales. En outre je propose une procédure pour comparer des algorithmes heuristiques. Cette procédure tient compte de la qualité de la solution aussi bien que du temps de calcul utilisé. Dans la troisième partie de ma thèse j'ai étudié en détail les propriétés h température nulle des verres de spins sur des graphes aléatoires lacunaires avec une coordination fixe. les verres de spins sur de tels graphes peuvent être considérés comme une approximation aux vrais verres de spins qui est plus réaliste que le modèle de Sherrington et Kirkpatrick. J'ai conçu un nouvel algorithme pour trouver les états fondamentaux. Aussi je teste numériquement une conjecture de Banavar, Sherrington et Sourlas qui donne la densité d'énergie du fondamental dans la limite de grande taille en fonction de la coordination. La distribution du paramètre d'ordre se révèle être non triviale et les données présentent une forte indication de la présence d'ultramétricité pour toutes les valeur de la coordination. Ces résultats confirment que les propriétés particulières des verres de spin, déduites an niveau de l'approximation de champ moyen dans le cadre du modèle de Sherrington et Kirkpatrick, sont aussi présentes pour des modèles plus réalistes comme les verres de spins sur des graphes aléatoires lacunaires avec une coordination fixe.

Généralement, les problèmes de conception de réseaux consistent à sélectionner les arcs et les sommets d’un graphe G de sorte que la fonction coût est optimisée et l’ensemble de contraintes impliquant les liens et les sommets dans G sont respectées. Une modification dans le critère d’optimisation et/ou dans l’ensemble de contraintes mène à une nouvelle représentation d’un problème différent. Dans cette thèse, nous nous intéressons au problème de conception d’infrastructure de réseaux maillés sans fil (WMN- Wireless Mesh Network en Anglais) où nous montrons que la conception de tels réseaux se transforme d’un problème d’optimisation standard (la fonction coût est optimisée) à un problème d’optimisation à plusieurs objectifs, pour tenir en compte de nombreux aspects, souvent contradictoires, mais néanmoins incontournables dans la réalité. Cette thèse, composée de trois volets, propose de nouveaux modèles et algorithmes pour la conception de WMNs où rien n’est connu à l’ avance. Le premiervolet est consacré à l’optimisation simultanée de deux objectifs équitablement importants : le coût et la performance du réseau en termes de débit. Trois modèles bi-objectifs qui se différent principalement par l’approche utilisée pour maximiser la performance du réseau sont proposés, résolus et comparés. Le deuxième volet traite le problème de placement de passerelles vu son impact sur la performance et l’extensibilité du réseau. La notion de contraintes de sauts (hop constraints) est introduite dans la conception du réseau pour limiter le délai de transmission. Un nouvel algorithme basé sur une approche de groupage est proposé afin de trouver les positions stratégiques des passerelles qui favorisent l’extensibilité du réseau et augmentent sa performance sans augmenter considérablement le coût total de son installation. Le dernier volet adresse le problème de fiabilité du réseau dans la présence de pannes simples. Prévoir l’installation des composants redondants lors de la phase de conception peut garantir des communications fiables, mais au détriment du coût et de la performance du réseau. Un nouvel algorithme, basé sur l’approche théorique de décomposition en oreilles afin d’installer le minimum nombre de routeurs additionnels pour tolérer les pannes simples, est développé. Afin de résoudre les modèles proposés pour des réseaux de taille réelle, un algorithme évolutionnaire (méta-heuristique), inspiré de la nature, est développé. Finalement, les méthodes et modèles proposés on été évalués par des simulations empiriques et d’événements discrets. / Generally, network design problems consist of selecting links and vertices of a graph G so that a cost function is optimized and all constraints involving links and the vertices in G are met. A change in the criterion of optimization and/or the set of constraints leads to a new representation of a different problem. In this thesis, we consider the problem of designing infrastructure Wireless Mesh Networks (WMNs) where we show that the design of such networks becomes an optimization problem with multiple objectives instead of a standard optimization problem (a cost function is optimized) to take into account many aspects, often contradictory, but nevertheless essential in the reality. This thesis, composed of three parts, introduces new models and algorithms for designing WMNs from scratch. The first part is devoted to the simultaneous optimization of two equally important objectives: cost and network performance in terms of throughput. Three bi-objective models which differ mainly by the approach used to maximize network performance are proposed, solved and compared. The second part deals with the problem of gateways placement, given its impact on network performance and scalability. The concept of hop constraints is introduced into the network design to reduce the transmission delay. A novel algorithm based on a clustering approach is also proposed to find the strategic positions of gateways that support network scalability and increase its performance without significantly increasing the cost of installation. The final section addresses the problem of reliability in the presence of single failures. Allowing the installation of redundant components in the design phase can ensure reliable communications, but at the expense of cost and network performance. A new algorithm is developed based on the theoretical approach of "ear decomposition" to install the minimum number of additional routers to tolerate single failures. In order to solve the proposed models for real-size networks, an evolutionary algorithm (meta-heuristics), inspired from nature, is developed. Finally, the proposed models and methods have been evaluated through empirical and discrete events based simulations.

La transformation de modèles consiste à transformer un modèle source en un modèle cible conformément à des méta-modèles source et cible. Nous distinguons deux types de transformations. La première est exogène où les méta-modèles source et cible représentent des formalismes différents et où tous les éléments du modèle source sont transformés. Quand elle concerne un même formalisme, la transformation est endogène. Ce type de transformation nécessite généralement deux étapes : l’identification des éléments du modèle source à transformer, puis la transformation de ces éléments. Dans le cadre de cette thèse, nous proposons trois principales contributions liées à ces problèmes de transformation. La première contribution est l’automatisation des transformations des modèles. Nous proposons de considérer le problème de transformation comme un problème d'optimisation combinatoire où un modèle cible peut être automatiquement généré à partir d'un nombre réduit d'exemples de transformations. Cette première contribution peut être appliquée aux transformations exogènes ou endogènes (après la détection des éléments à transformer). La deuxième contribution est liée à la transformation endogène où les éléments à transformer du modèle source doivent être détectés. Nous proposons une approche pour la détection des défauts de conception comme étape préalable au refactoring. Cette approche est inspirée du principe de la détection des virus par le système immunitaire humain, appelée sélection négative. L’idée consiste à utiliser de bonnes pratiques d’implémentation pour détecter les parties du code à risque. La troisième contribution vise à tester un mécanisme de transformation en utilisant une fonction oracle pour détecter les erreurs. Nous avons adapté le mécanisme de sélection négative qui consiste à considérer comme une erreur toute déviation entre les traces de transformation à évaluer et une base d’exemples contenant des traces de transformation de bonne qualité. La fonction oracle calcule cette dissimilarité et les erreurs sont ordonnées selon ce score. Les différentes contributions ont été évaluées sur d’importants projets et les résultats obtenus montrent leurs efficacités. / Model transformations take as input a source model and generate as output a target model. The source and target models conform to given meta-models. We distinguish between two transformation categories. Exogenous transformations are transformations between models expressed using different languages, and the whole source model is transformed. Endogenous transformations are transformations between models expressed in the same language. For endogenous transformations, two steps are needed: identifying the source model elements to transform and then applying the transformation on them. In this thesis, we propose three principal contributions. The first contribution aims to automate model transformations. The process is seen as an optimization problem where different transformation possibilities are evaluated and, for each possibility, a quality is associated depending on its conformity with a reference set of examples. This first contribution can be applied to exogenous as well as endogenous transformation (after determining the source model elements to transform). The second contribution is related precisely to the detection of elements concerned with endogenous transformations. In this context, we present a new technique for design defect detection. The detection is based on the notion that the more a code deviates from good practice, the more likely it is bad. Taking inspiration from artificial immune systems, we generate a set of detectors that characterize the ways in which a code can diverge from good practices. We then use these detectors to determine how far the code in the assessed systems deviates from normality. The third contribution concerns transformation mechanism testing. The proposed oracle function compares target test cases with a base of examples containing good quality transformation traces, and assigns a risk level based on the dissimilarity between the two. The traces help the tester understand the origin of an error. The three contributions are evaluated with real software projects and the obtained results confirm their efficiencies.

Nous étudions la gestion de centres d'appels multi-compétences, ayant plusieurs types d'appels et groupes d'agents. Un centre d'appels est un système de files d'attente très complexe, où il faut généralement utiliser un simulateur pour évaluer ses performances. Tout d'abord, nous développons un simulateur de centres d'appels basé sur la simulation d'une chaîne de Markov en temps continu (CMTC), qui est plus rapide que la simulation conventionnelle par événements discrets. À l'aide d'une méthode d'uniformisation de la CMTC, le simulateur simule la chaîne de Markov en temps discret imbriquée de la CMTC. Nous proposons des stratégies pour utiliser efficacement ce simulateur dans l'optimisation de l'affectation des agents. En particulier, nous étudions l'utilisation des variables aléatoires communes. Deuxièmement, nous optimisons les horaires des agents sur plusieurs périodes en proposant un algorithme basé sur des coupes de sous-gradients et la simulation. Ce problème est généralement trop grand pour être optimisé par la programmation en nombres entiers. Alors, nous relaxons l'intégralité des variables et nous proposons des méthodes pour arrondir les solutions. Nous présentons une recherche locale pour améliorer la solution finale. Ensuite, nous étudions l'optimisation du routage des appels aux agents. Nous proposons une nouvelle politique de routage basé sur des poids, les temps d'attente des appels, et les temps d'inoccupation des agents ou le nombre d'agents libres. Nous développons un algorithme génétique modifié pour optimiser les paramètres de routage. Au lieu d'effectuer des mutations ou des croisements, cet algorithme optimise les paramètres des lois de probabilité qui génèrent la population de solutions. Par la suite, nous développons un algorithme d'affectation des agents basé sur l'agrégation, la théorie des files d'attente et la probabilité de délai. Cet algorithme heuristique est rapide, car il n'emploie pas la simulation. La contrainte sur le niveau de service est convertie en une contrainte sur la probabilité de délai. Par après, nous proposons une variante d'un modèle de CMTC basé sur le temps d'attente du client à la tête de la file. Et finalement, nous présentons une extension d'un algorithme de coupe pour l'optimisation stochastique avec recours de l'affectation des agents dans un centre d'appels multi-compétences. / We study the management of multi-skill call centers, with multiple call types and agent groups. A call center is a very complex queueing system, and we generally need to use simulation in order to evaluate its performances. First, we develop a call center simulator based on the simulation of a continuous-time Markov chain (CTMC) that is faster than traditional discrete-event simulation. Using an uniformization method, this simulator simulates the embedded discrete-time Markov chain of the CTMC. We propose strategies to use this simulator efficiently within a staffing optimization algorithm. In particular, we study the use of common random numbers. Secondly, we propose an algorithm, based on subgradient cuts and simulation, to optimize the shift scheduling problem. Since this problem is usually too big to be solved as an integer programming problem, we relax the integer variables and we propose methods to round the solutions. We also present a local search to improve the final solution. Next, we study the call routing optimization problem. We propose a new routing policy based on weights, call waiting times, and agent idle times or the number of idle agents. We develop a modified genetic algorithm to optimize all the routing parameters. Instead of doing mutations and crossovers, this algorithm refines the parametric distributions used to generate the population of solutions. We also develop a staffing algorithm based on aggregation, queueing theory and delay probability. This heuristic algorithm is fast, because it does not use simulation. The service level constraint is converted into a delay probability constraint. Moreover, we propose a variant of a CTMC model based on the waiting time of the customer at the head of the queue. Finally, we design an extension of a cutting-plane algorithm to optimize the stochastic version with recourse of the staffing problem for multi-skill call centers.

Le Problème de Tournées de Véhicules (PTV) est une clé importante pour gérér efficacement des systèmes logistiques, ce qui peut entraîner une amélioration du niveau de satisfaction de la clientèle. Ceci est fait en servant plus de clients dans un temps plus court. En terme général, il implique la planification des tournées d'une flotte de véhicules de capacité donnée basée à un ou plusieurs dépôts. Le but est de livrer ou collecter une certain quantité de marchandises à un ensemble des clients géographiquement dispersés, tout en respectant les contraintes de capacité des véhicules. Le PTV, comme classe de problèmes d'optimisation discrète et de grande complexité, a été étudié par de nombreux au cours des dernières décennies. Étant donné son importance pratique, des chercheurs dans les domaines de l'informatique, de la recherche opérationnelle et du génie industrielle ont mis au point des algorithmes très efficaces, de nature exacte ou heuristique, pour faire face aux différents types du PTV. Toutefois, les approches proposées pour le PTV ont souvent été accusées d'être trop concentrées sur des versions simplistes des problèmes de tournées de véhicules rencontrés dans des applications réelles. Par conséquent, les chercheurs sont récemment tournés vers des variantes du PTV qui auparavant étaient considérées trop difficiles à résoudre. Ces variantes incluent les attributs et les contraintes complexes observés dans les cas réels et fournissent des solutions qui sont exécutables dans la pratique. Ces extensions du PTV s'appellent Problème de Tournées de Véhicules Multi-Attributs (PTVMA). Le but principal de cette thèse est d'étudier les différents aspects pratiques de trois types de problèmes de tournées de véhicules multi-attributs qui seront modélisés dans celle-ci. En plus, puisque pour le PTV, comme pour la plupart des problèmes NP-complets, il est difficile de résoudre des instances de grande taille de façon optimale et dans un temps d'exécution raisonnable, nous nous tournons vers des méthodes approcheés à base d’heuristiques. / The Vehicle Routing Problem (VRP) is an important key to efficient logistics system management, which can result in higher level of customer satisfaction because more customers can be served in a shorter time. In broad terms, it deals with designing optimal delivery or collection routes from one or several depot(s) to a number of geographically scattered customers subject to side constraints. The VRP is a discrete optimization and computationally hard problem and has been extensively studied by researchers and practitioners during the past decades. Being complex problems with numerous and relevant potential applications, researchers from the fields of computer science, operations research and industrial engineering have developed very efficient algorithms, both of exact and heuristic nature, to deal with different types of VRPs. However, VRP research has often been criticized for being too focused on oversimplified versions of the routing problems encountered in real-life applications. Consequently, researchers have recently turned to variants of the VRP which before were considered too difficult to solve. These variants include those attributes and constraints observed in real-life planning and lead to solutions that are executable in practice. These extended problems are called Multi-Attribute Vehicle Routing Problems (MAVRPs). The main purpose of this thesis is to study different practical aspects of three multi-attribute vehicle routing problems which will be modeled in it. Besides that, since the VRP has been proved to be NP-hard in the strong sense such that it is impossible to optimally solve the large-sized problems in a reasonable computational time by means of traditional optimization approaches, novel heuristics will be designed to efficiently tackle the created models.

Le problème de tournées de véhicules (VRP) implique de planifier les itinéraires d'une flotte de véhicules afin de desservir un ensemble de clients à moindre coût. Ce problème d'optimisation combinatoire NP-difficile apparait dans de nombreux domaines d'application, notamment en logistique, télécommunications, robotique ou gestion de crise dans des contextes militaires et humanitaires. Ces applications amènent différents contraintes, objectifs et décisions supplémentaires ; des "attributs" qui viennent compléter les formulations classiques du problème. Les nombreux VRP Multi-Attributs (MAVRP) qui s'ensuivent sont le support d'une littérature considérable, mais qui manque de méthodes généralistes capables de traiter efficacement un éventail significatif de variantes. Par ailleurs, la résolution de problèmes "riches", combinant de nombreux attributs, pose d'importantes difficultés méthodologiques. Cette thèse contribue à relever ces défis par le biais d'analyses structurelles des problèmes, de développements de stratégies métaheuristiques, et de méthodes unifiées. Nous présentons tout d'abord une étude transversale des concepts à succès de 64 méta-heuristiques pour 15 MAVRP afin d'en cerner les "stratégies gagnantes". Puis, nous analysons les problèmes et algorithmes d'ajustement d'horaires en présence d'une séquence de tâches fixée, appelés problèmes de "timing". Ces méthodes, développées indépendamment dans différents domaines de recherche liés au transport, ordonnancement, allocation de ressource et même régression isotonique, sont unifiés dans une revue multidisciplinaire. Un algorithme génétique hybride efficace est ensuite proposé, combinant l'exploration large des méthodes évolutionnaires, les capacités d'amélioration agressive des métaheuristiques à voisinage, et une évaluation bi-critère des solutions considérant coût et contribution à la diversité de la population. Les meilleures solutions connues de la littérature sont retrouvées ou améliorées pour le VRP classique ainsi que des variantes avec multiples dépôts et périodes. La méthode est étendue aux VRP avec contraintes de fenêtres de temps, durée de route, et horaires de conducteurs. Ces applications mettent en jeu de nouvelles méthodes d'évaluation efficaces de contraintes temporelles relaxées, des phases de décomposition, et des recherches arborescentes pour l'insertion des pauses des conducteurs. Un algorithme de gestion implicite du placement des dépôts au cours de recherches locales, par programmation dynamique, est aussi proposé. Des études expérimentales approfondies démontrent la contribution notable des nouvelles stratégies au sein de plusieurs cadres méta-heuristiques. Afin de traiter la variété des attributs, un cadre de résolution heuristique modulaire est présenté ainsi qu'un algorithme génétique hybride unifié (UHGS). Les attributs sont gérés par des composants élémentaires adaptatifs. Des expérimentations sur 26 variantes du VRP et 39 groupes d'instances démontrent la performance remarquable de UHGS qui, avec une unique implémentation et paramétrage, égalise ou surpasse les nombreux algorithmes dédiés, issus de plus de 180 articles, révélant ainsi que la généralité ne s'obtient pas forcément aux dépends de l'efficacité pour cette classe de problèmes. Enfin, pour traiter les problèmes riches, UHGS est étendu au sein d'un cadre de résolution parallèle coopératif à base de décomposition, d'intégration de solutions partielles, et de recherche guidée. L'ensemble de ces travaux permet de jeter un nouveau regard sur les MAVRP et les problèmes de timing, leur résolution par des méthodes méta-heuristiques, ainsi que les méthodes généralistes pour l'optimisation combinatoire. / The Vehicle Routing Problem (VRP) involves designing least cost delivery routes to service a geographically-dispersed set of customers while taking into account vehicle-capacity constraints. This NP-hard combinatorial optimization problem is linked with multiple applications in logistics, telecommunications, robotics, crisis management in military and humanitarian frameworks, among others. Practical routing applications are usually quite distinct from the academic cases, encompassing additional sets of specific constraints, objectives and decisions which breed further new problem variants. The resulting "Multi-Attribute" Vehicle Routing Problems (MAVRP) are the support of a vast literature which, however, lacks unified methods capable of addressing multiple MAVRP. In addition, some "rich" VRPs, i.e. those that involve several attributes, may be difficult to address because of the wide array of combined and possibly antagonistic decisions they require. This thesis contributes to address these challenges by means of problem structure analysis, new metaheuristics and unified method developments. The "winning strategies" of 64 state-of-the-art algorithms for 15 different MAVRP are scrutinized in a unifying review. Another analysis is targeted on "timing" problems and algorithms for adjusting the execution dates of a given sequence of tasks. Such methods, independently studied in different research domains related to routing, scheduling, resource allocation, and even isotonic regression are here surveyed in a multidisciplinary review. A Hybrid Genetic Search with Advanced Diversity Control (HGSADC) is then introduced, which combines the exploration breadth of population-based evolutionary search, the aggressive-improvement capabilities of neighborhood-based metaheuristics, and a bi-criteria evaluation of solutions based on cost and diversity measures. Results of remarkable quality are achieved on classic benchmark instances of the capacitated VRP, the multi-depot VRP, and the periodic VRP. Further extensions of the method to VRP variants with constraints on time windows, limited route duration, and truck drivers' statutory pauses are also proposed. New route and neighborhood evaluation procedures are introduced to manage penalized infeasible solutions w.r.t. to time-window and duration constraints. Tree-search procedures are used for drivers' rest scheduling, as well as advanced search limitation strategies, memories and decomposition phases. A dynamic programming-based neighborhood search is introduced to optimally select the depot, vehicle type, and first customer visited in the route during local searches. The notable contribution of these new methodological elements is assessed within two different metaheuristic frameworks. To further advance general-purpose MAVRP methods, we introduce a new component-based heuristic resolution framework and a Unified Hybrid Genetic Search (UHGS), which relies on modular self-adaptive components for addressing problem specifics. Computational experiments demonstrate the groundbreaking performance of UHGS. With a single implementation, unique parameter setting and termination criterion, this algorithm matches or outperforms all current problem-tailored methods from more than 180 articles, on 26 vehicle routing variants and 39 benchmark sets. To address rich problems, UHGS was included in a new parallel cooperative solution framework called "Integrative Cooperative Search (ICS)", based on problem decompositions, partial solutions integration, and global search guidance. This compendium of results provides a novel view on a wide range of MAVRP and timing problems, on efficient heuristic searches, and on general-purpose solution methods for combinatorial optimization problems. / Thèse réalisée en cotutelle entre l'Université de Montréal et l'Université de Technologie de Troyes

La reconnaissance faciale (RF) est un domaine de recherche très actif en raison de ses nombreuses applications dans le domaine de la vision par ordinateur en général et en biométrie en particulier. Cet intérêt est motivé par plusieurs raisons. D’abord, le visage est universel. Ensuite, il est le moyen le plus naturel par les êtres humains de s’identifier les uns des autres. Enfin, le visage en tant que modalité biométrique est présente un caractère non intrusif, ce qui le distingue d’autres modalités biométriques comme l’iris ou l’emprunte digitale. La RF représente aussi des défis scientifiques importants. D’abord parce que tous les visages humains ont des configurations similaires. Ensuite, avec les images faciales 2D que l’on peut acquérir facilement, la variation intra-classe, due à des facteurs comme le changement de poses et de conditions d’éclairage, les variations d’expressions faciales, le vieillissement, est bien plus importante que la variation inter-classe.Avec l’arrivée des systèmes d’acquisition 3D capables de capturer la profondeur d’objets, la reconnaissance faciale 3D (RF 3D) a émergé comme une voie prometteuse pour traiter les deux problèmes non résolus en 2D, à savoir les variations de pose et d’éclairage. En effet, les caméras 3D délivrent généralement les scans 3D de visages avec leurs images de texture alignées. Une solution en RF 3D peut donc tirer parti d’une fusion avisée d’informations de forme en 3D et celles de texture en 2D. En effet, étant donné que les scans 3D de visage offrent à la fois les surfaces faciales pour la modalité 3D pure et les images de texture 2D alignées, le nombre de possibilités de fusion pour optimiser le taux de reconnaissance est donc considérable. L’optimisation de stratégies de fusion pour une meilleure RF 3D est l’objectif principal de nos travaux de recherche menés dans cette thèse.Dans l’état d’art, diverses stratégies de fusion ont été proposées pour la reconnaissance de visages 3D, allant de la fusion précoce "early fusion" opérant au niveau de caractéristiques à la fusion tardive "late fusion" sur les sorties de classifieurs, en passant par de nombreuses stratégies intermédiaires. Pour les stratégies de fusion tardive, nous distinguons encore des combinaisons en parallèle, en cascade ou multi-niveaux. Une exploration exhaustive d’un tel espace étant impossible, il faut donc recourir à des solutions heuristiques qui constituent nos démarches de base dans le cadre des travaux de cette thèse.En plus, en s’inscrivant dans un cadre de systèmes biométriques, les critères d’optimalité des stratégies de fusion restent des questions primordiales. En effet, une stratégie de fusion est dite optimisée si elle est capable d’intégrer et de tirer parti des différentes modalités et, plus largement, des différentes informations extraites lors du processus de reconnaissance quelque soit leur niveau d’abstraction et, par conséquent, de difficulté.Pour surmonter toutes ces difficultés et proposer une solution optimisée, notre démarche s’appuie d’une part sur l’apprentissage qui permet de qualifier sur des données d’entrainement les experts 2D ou 3D, selon des critères de performance comme ERR, et d’autre part l’utilisation de stratégie d’optimisation heuristique comme le recuit simulé qui permet d’optimiser les mélanges des experts à fusionner. [...] / Face recognition (FR) was one of the motivations of computer vision for a long time, but only in recent years reliable automatic face recognition has become a realistic target of biometrics research. This interest is motivated by several reasons. First, the face is one of the most preferable biometrics for person identification and verification related applications, because it is natural, non-intrusive, and socially well accepted. The second reason relates to the challenges encountered in the FR domain, in which all human faces are similar to each other and hence offer low distinctiveness as compared with other biometrics, e.g., fingerprints and irises. Furthermore, when employing facial texture images, intra-class variations due to various factors as illumination and pose changes are usually greater than inter-class ones, preventing 2D face recognition systems from being completely reliable in real conditions.Recent, 3D acquisition systems are capable to capture the shape information of objects. Thus, 3D face recognition (3D FR) has been extensively investigated by the research community to deal with the unsolved issues in 2D face recognition, i.e., illumination and pose changes. Indeed, 3D cameras generally deliver the 3D scans of faces with their aligned texture images. 3D FR can benefit from the fusion of 2D texture and 3D shape information.This Ph.D thesis is dedicated to the optimization of fusion strategies based on three dimensional data. However, there are some problems. Indeed, since the 3D face scans provide both the facial surfaces for the 3D model and 2D texture images, the number of fusion method is high.In the literature, many fusion strategies exist that have been proposed for 3D face recognition. We can roughly classify the fusion strategies into two categories: early fusion and late fusion. Some intermediate strategies such as serial fusion and multi-level fusion have been proposed as well. Meanwhile, the search for an optimal fusion scheme remains extraordinarily complex because the cardinality of the space of possible fusion strategies. It is exponentially proportional to the number of competing features and classifiers. Thus, we require fusion technique to efficiently manage all these features and classifiers that constitute our contribution in this work. In addition, the optimality criteria of fusion strategies remain critical issues. By definition, an optimal fusion strategy is able to integrate and take advantage from different data.To overcome all these difficulties and propose an optimized solution, we adopted the following reflection. [...]

Combinatorial optimization problems are of high academical as well as practical importance. Many instances of relevant combinatorial optimization problems are, due to their dimensions, intractable for complete methods such as branch and bound. Therefore, approximate algorithms such as metaheuristics received much attention in the past 20 years. Examples of metaheuristics are simulated annealing, tabu search, and evolutionary computation. One of the most recent metaheuristics is ant colony optimization (ACO), which was developed by Prof. M. Dorigo (who is the supervisor of this thesis) and colleagues. This thesis deals with theoretical as well as practical aspects of ant colony optimization.<p><p>* A survey of metaheuristics. Chapter 1 gives an extensive overview on the nowadays most important metaheuristics. This overview points out the importance of two important concepts in metaheuristics: intensification and diversification. <p><p>* The hyper-cube framework. Chapter 2 introduces a new framework for implementing ACO algorithms. This framework brings two main benefits to ACO researchers. First, from the point of view of the theoretician: we prove that Ant System (the first ACO algorithm to be proposed in the literature) in the hyper-cube framework generates solutions whose expected quality monotonically increases with the number of algorithm iterations when applied to unconstrained problems. Second, from the point of view of the experimental researcher, we show through examples that the implementation of ACO algorithms in the hyper-cube framework increases their robustness and makes the handling of the pheromone values easier.<p><p>* Deception. In the first part of Chapter 3 we formally define the notions of first and second order deception in ant colony optimization. Hereby, first order deception corresponds to deception as defined in the field of evolutionary computation and is therefore a bias introduced by the problem (instance) to be solved. Second order deception is an ACO-specific phenomenon. It describes the observation that the quality of the solutions generated by ACO algorithms may decrease over time in certain settings. In the second part of Chapter 3 we propose different ways of avoiding second order deception.<p><p>* ACO for the KCT problem. In Chapter 4 we outline an ACO algorithm for the edge-weighted k-cardinality tree (KCT) problem. This algorithm is implemented in the hyper-cube framework and uses a pheromone model that was determined to be well-working in Chapter 3. Together with the evolutionary computation and the tabu search approaches that we develop in Chapter 4, this ACO algorithm belongs to the current state-of-the-art algorithms for the KCT problem.<p><p>* ACO for the GSS problem. Chapter 5 describes a new ACO algorithm for the group shop scheduling (GSS) problem, which is a general shop scheduling problem that includes among others the well-known job shop scheduling (JSS) and the open shop scheduling (OSS) problems. This ACO algorithm, which is implemented in the hyper-cube framework and which uses a new pheromone model that was experimentally tested in Chapter 3, is currently the best ACO algorithm for the JSS as well as the OSS problem. In particular when applied to OSS problem instances, this algorithm obtains excellent results, improving the best known solution for several OSS benchmark instances. A final contribution of this thesis is the development of a general method for the solution of combinatorial optimization problems which we refer to as Beam-ACO. This method is a hybrid between ACO and a tree search technique known as beam search. We show that Beam-ACO is currently a state-of-the-art method for the application to the existing open shop scheduling (OSS) problem instances.<p><p> / Doctorat en sciences appliquées / info:eu-repo/semantics/nonPublished

Le système de santé français est confronté au défi d’augmentation permanente de la demande en soins, sous une forte pression financière. Dans la stratégie nationale de santé, une des grandes orientations est de développer une base de coopération impliquant l’ensemble des acteurs et de leur engagement. Ces enjeux demandent au génie hospitalier de rechercher une efficience dans une échelle encore plus globale, ce qui demande d’intégrer les problèmes locaux et leurs outils d’optimisation qui présentent en général un haut degré de fragmentation, afin de contribuer à l’amélioration globale du système. Dans ce contexte-là, initialisé par un projet de conception du système de soins en réseau avec ressource de production mutualisée, nous proposons à travers ce mémoire de thèse une méthode générique pour résoudre le problème d’optimisation multi-niveaux dans lequel les décisions interdépendantes doivent être prises à différents niveaux dans une structure hiérarchique, ou aux étapes successives. Les décisions faites sont souvent corrélées, surtout pour une topologie de décisions enchaînées en hiérarchique que nous définissons sous le terme de « sous-structure optimale feedback ». La résolution de ce type de problème doit s’adapter pour prendre en compte autant que possible les implications liées aux décisions corrélées. La méthode proposée est basée sur la méta-heuristique PSO, elle utilise une procédure récursive pour définir le transfert des paramètres des sous-problèmes descendant et des évaluations ascendant à travers de multiples espaces de recherche, en assurant la cohérence de la convergence du problème global. Les applications et les analyses ont montrées que la méthode est assez générique et capable de produire la performance et la qualité de résolution proche de celles de la littérature / French healthcare system confronts the challenges of permanent increase in demand for healthcare, under heavy financial pressure. In the national healthcare strategy, a key focus is to develop a cooperation framework involving all organizations and units. These challenges require healthcare engineering to find efficiency in a more global scale, which means to integrate local optimization problems and decision tools that have generally a high degree of fragmentation in order to contribute to the overall improvement of the system. In this thesis, initiated by a shared unit-dose drug distribution system design project, a generic method was developed to solve the multi-level optimization problem in which interdependent decisions are made at different levels in a hierarchical structure, or at successive stages. The decisions made are often correlated, particularly for decisions in hierarchical topologies that we define by the term "optimal substructure with feedback". The resolution of this problem must be adapted to take into account all implications for correlated decisions. The proposed method is based on the meta-heuristic PSO, it uses a recursive procedure to define the top-down transfer of parameters and the bottom-up feedback of fitness through multiple search spaces, and ensures the consistency of global problem convergence. Our applications and analyzes have shown that this method is generic and is able to provide similar resolution performance and quality compared to the literature references

Mémoire en recherche-création / Un endroit familier est composé de trois portraits littéraires. L’auteur y met en relief des moments marquants de la vie de trois membres de sa famille : son grand-père maternel, qui a participé activement à un réseau de radio clandestine dans la France occupée, dans les années 1940; sa grand-mère paternelle, qui a élevé quatorze enfants à Saint-Joachim-de-Montmorency, et dont la longue vie embrasse à elle seule tout un pan de la ruralité québécoise du siècle dernier; puis son arrière-grand-mère maternelle, dont le mari est mort dans les tranchées de Champagne, durant la Première Guerre mondiale. Avec en arrière-plan le vingtième siècle, ses enthousiasmes et ses dérives, cette galerie de portraits en comprend un autre, plus discret, fragmenté, celui de l’auteur qui cherche à mieux comprendre d’où il vient. À la recherche de l’autre, ne sommes-nous pas toujours un peu à la recherche de nous-mêmes ? L’essai qui suit, intitulé Le problème de la mémoire dans le portrait littéraire, aborde le recours aux sources documentaires qu’exige le genre, de même que l’incidence des intentions de l’auteur sur la façon dont les sources seront exploitées. Il est ensuite question du degré d’exclusivité de la mémoire individuelle et de ce qu’implique l’idée, nourrie par la théorie de la postmémoire, notamment, d’une mémoire des traumas où le souvenir de l’un devient le souvenir de l’autre. L’essai se referme sur une réflexion portant sur le pouvoir qu’a la littérature de faire sortir de l’ombre, avec leurs énigmes non résolues, celles et ceux qui nous ont précédés. Et s’il y avait d’abord, au coeur d’une telle démarche d’écriture, le besoin de mieux vivre avec ses morts ? / Un endroit familier is made up of three literary portraits. The author highlights significant moments in the life of three members of his family : his maternal grandfather, who actively participated in an underground radio network in occupied France, in the 1940s; his paternal grandmother, who raised fourteen children in Saint-Joachim-de-Montmorency, and whose long life alone encompasses a vast segment of Quebec rurality of the last century; finally, there will be his maternal great-grandmother, whose husband died in the trenches of Champagne, during the First World War. Against the backdrop of the twentieth century’s enthusiasms and excesses, this gallery of portraits includes as well the more discreet, fragmented image of the author who seeks to better understand where he comes from. Looking for the other, aren't we always looking a little for ourselves ? The following essay, Le problème de la mémoire dans le portrait littéraire, discusses the use of documentary sources required by the genre, as well as the impact of the author's intentions on how those sources will be exploited. Then we will explore the degree of exclusivity of individual memory and the idea, drawn from the theory of postmemory, in particular, of a memory of traumas in which one’s memory becomes that of another. The essay ends with a reflection on the power of literature to bring out of the shadows, with their unsolved puzzles, those who came before us. What if there was first, at the heart of such a writing process, the need to live better with our dead ?