In this thesis we focus on Stochastic combinatorial Optimization Problems (SCOPs), a wide class of combinatorial optimization problems under uncertainty, where part of the information about the problem data is unknown at the planning stage, but some knowledge about its probability distribution is assumed.<p><p>Optimization problems under uncertainty are complex and difficult, and often classical algorithmic approaches based on mathematical and dynamic programming are able to solve only very small problem instances. For this reason, in recent years metaheuristic algorithms such as Ant Colony Optimization, Evolutionary Computation, Simulated Annealing, Tabu Search and others, are emerging as successful alternatives to classical approaches.<p><p>In this thesis, metaheuristics that have been applied so far to SCOPs are introduced and the related literature is thoroughly reviewed. In particular, two properties of metaheuristics emerge from the survey: they are a valid alternative to exact classical methods for addressing real-sized SCOPs, and they are flexible, since they can be quite easily adapted to solve different SCOPs formulations, both static and dynamic. On the base of the current literature, we identify the following as the key open issues in solving SCOPs via metaheuristics: <p>(1) the design and integration of ad hoc, fast and effective objective function approximations inside the optimization algorithm;<p>(2) the estimation of the objective function by sampling when no closed-form expression for the objective function is available, and the study of methods to reduce the time complexity and noise inherent to this type of estimation;<p>(3) the characterization of the efficiency of metaheuristic variants with respect to different levels of stochasticity in the problem instances. <p><p>We investigate the above issues by focusing in particular on a SCOP belonging to the class of vehicle routing problems: the Probabilistic Traveling Salesman Problem (PTSP). For the PTSP, we consider the Ant Colony Optimization metaheuristic and we design efficient local search algorithms that can enhance its performance. We obtain state-of-the-art algorithms, but we show that they are effective only for instances above a certain level of stochasticity, otherwise it is more convenient to solve the problem as if it were deterministic.<p>The algorithmic variants based on an estimation of the objective function by sampling obtain worse results, but qualitatively have the same behavior of the algorithms based on the exact objective function, with respect to the level of stochasticity. Moreover, we show that the performance of algorithmic variants based on ad hoc approximations is strongly correlated with the absolute error of the approximation, and that the effect on local search of ad hoc approximations can be very degrading.<p><p>Finally, we briefly address another SCOP belonging to the class of vehicle routing problems: the Vehicle Routing Problem with Stochastic Demands (VRPSD). For this problem, we have implemented and tested several metaheuristics, and we have studied the impact of integrating in them different ad hoc approximations.<p> / Doctorat en sciences appliquées / info:eu-repo/semantics/nonPublished

<p>A metaheuristic is a generic algorithmic template that, once properly instantiated, can be used for finding high quality solutions of combinatorial optimization problems.<p>For obtaining a fully functioning algorithm, a metaheuristic needs to be configured: typically some modules need to be instantiated and some parameters need to be tuned. For the sake of precision, we use the expression <em>parametric tuning</em> for referring to the tuning of numerical parameters, either continuous or discrete but in any case ordinal. <p>On the other hand, we use the expression <em>structural tuning</em> for referring to the problem of defining which modules should be included and, in general, to the problem of tuning parameters that are either boolean or categorical. Finally, with <em>tuning</em> we refer to the composite <em>structural and parametric tuning</em>.</p><p><p><p>Tuning metaheuristics is a very sensitive issue both in practical applications and in academic studies. Nevertheless, a precise definition of the tuning problem is missing in the literature. In this thesis, we argue that the problem of tuning a metaheuristic can be profitably described and solved as a machine learning problem.</p><p><p><p>Indeed, looking at the problem of tuning metaheuristics from a machine learning perspective, we are in the position of giving a formal statement of the tuning problem and to propose an algorithm, called F-Race, for tackling the problem itself. Moreover, always from this standpoint, we are able to highlight and discuss some catches and faults in the current research methodology in the metaheuristics field, and to propose some guidelines.</p><p><p><p>The thesis contains experimental results on the use of F-Race and some examples of practical applications. Among others, we present a feasibility study carried out by the German-based software company <em>SAP</em>, that concerned the possible use of F-Race for tuning a commercial computer program for vehicle routing and scheduling problems. Moreover, we discuss the successful use of F-Race for tuning the best performing algorithm submitted to the <em>International Timetabling Competition</em> organized in 2003 by the <em>Metaheuristics Network</em> and sponsored by <em>PATAT</em>, the international series of conferences on the <em>Practice and Theory of Automated Timetabling</em>.</p> / Doctorat en sciences appliquées / info:eu-repo/semantics/nonPublished

La musique de Charlemagne Palestine semble transcender les approches musicales américaines comme européennes des vingtième et vingt-et-unième siècles. Si sa pratique de la musique drone prend ses racines dans ses années passées enfant à chanter des lamentations dans les synagogues en tant que choriste, puis jeune adulte dans son expérience de carillonneur à l'église Saint-Thomas de Manhattan, et plus tard dans les approches expérimentales post-cagiennes et son étude vocale de la musique hindoustanie, son oeuvre, qui à de nombreux égards évoque également certaines esthétiques musicales de l'avant-garde européenne, oscille entre musique, installation et performance. C'est au travers de l'étude de la pièce "Schlingen-Blängen" pour orgue, sous le prisme de l'heuristique musicale, que cette thèse tente d'appréhender la quête du "son d'or" du musicien contemporain new-yorkais d'origine, bruxellois d'adoption. / The music of Charlemagne Palestine seems to transcend both american and european musical mouvements of the twentieth and twentieth-first centuries. His approach of drone music finds its origins in his early years when he would participate in synanogue choirs, singing lamentations, as well as in his young adult years when he would work as a bell ringer in the church of Saint-Thomas in Manhattan. Later on, his experimental post-Cage music approach and his vocal studies of Hindustani music, all gave birth to a body of work that oscillates between music, installation and performance, not without recalling in various ways certain european avant-garde musical esthetics. The present doctoral thesis aims to study the piece "Schlingen-Blängen" for organ, via a musical heuristics approach, in order to apprehend the pursuit of the "golden sound" in the oeuvre of the New-York contemporary artist, based in Brussels.

L'optimisation difficile représente une classe de problèmes dont la résolution ne peut être obtenue par une méthode exacte en un temps polynomial.Trouver une solution en un temps raisonnable oblige à trouver un compromis quant à son exactitude.Les métaheuristiques sont une classe d'algorithmes permettant de résoudre de tels problèmes, de manière générique et efficiente (i.e. trouver une solution satisfaisante selon des critères définis: temps, erreur, etc.).Le premier chapitre de cette thèse est notamment consacré à la description de cette problématique et à l'étude détaillée de deux familles de métaheuristiques à population, les algorithmes évolutionnaires et les algorithmes d'intelligence en essaim.Afin de proposer une approche innovante dans le domaine des métaheuristiques, ce premier chapitre présente également la notion d'analyse de sensibilité.L'analyse de sensibilité permet d'évaluer l'influence des paramètres d'une fonction sur son résultat.Son étude caractérise globalement le comportement de la fonction à optimiser (linéarité, influence, corrélation, etc.) sur son espace de recherche.L'incorporation d'une méthode d'analyse de sensibilité au sein d'une métaheuristique permet d'orienter sa recherche le long des dimensions les plus prometteuses.Deux algorithmes réunissant ces notions sont proposés aux deuxième et troisième chapitres.Pour le premier algorithme, ABC-Morris, la méthode de Morris est introduite dans la métaheuristique de colonie d'abeilles artificielles (ABC).Cette inclusion est dédiée, les méthodes reposant sur deux équations similaires.Afin de généraliser l'approche, une nouvelle méthode, NN-LCC, est ensuite développée et son intégration générique est illustrée sur deux métaheuristiques, ABC avec taux de modification et évolution différentielle.L'efficacité des approches proposées est testée sur le jeu de données de la conférence CEC 2013. L'étude se réalise en deux parties: une analyse classique de la méthode vis-à-vis de plusieurs algorithmes de la littérature, puis vis-à-vis de l'algorithme d'origine en désactivant un ensemble de dimensions, provoquant une forte disparité des influences / Hard optimization stands for a class of problems which solutions cannot be found by an exact method, with a polynomial complexity.Finding the solution in an acceptable time requires compromises about its accuracy.Metaheuristics are high-level algorithms that solve these kind of problems. They are generic and efficient (i.e. they find an acceptable solution according to defined criteria such as time, error, etc.).The first chapter of this thesis is partially dedicated to the state-of-the-art of these issues, especially the study of two families of population based metaheuristics: evolutionnary algorithms and swarm intelligence based algorithms.In order to propose an innovative approach in metaheuristics research field, sensitivity analysis is presented in a second part of this chapter.Sensitivity analysis aims at evaluating arameters influence on a function response. Its study characterises globally a objective function behavior (linearity, non linearity, influence, etc.), over its search space.Including a sensitivity analysis method in a metaheuristic enhances its seach capabilities along most promising dimensions.Two algorithms, binding these two concepts, are proposed in second and third parts.In the first one, ABC-Morris, Morris method is included in artificial bee colony algorithm.This encapsulation is dedicated because of the similarity of their bare bone equations, With the aim of generalizing the approach, a new method is developped and its generic integration is illustrated on two metaheuristics.The efficiency of the two methods is tested on the CEC 2013 conference benchmark. The study contains two steps: an usual performance analysis of the method, on this benchmark, regarding several state-of-the-art algorithms and the comparison with its original version when influences are uneven deactivating a subset of dimensions

Nous nous intéressons dans cette thèse aux possibilités d’hybridation entre les méthodes exactes et les méthodes heuristiques afin de pouvoir tirer avantage de chacune des deux approches : optimalité de la résolution exacte, caractère moins déterministe et rapidité de la composante heuristique. Dans l’objectif de résoudre des problèmes NPdifficiles de taille relativement importante tels que les problèmes de transports, nous nous intéressons dans les deux dernières parties de ce mémoire à la conception de méthodes incomplètes basées sur ces hybridations. Dans la première partie, nous allons nous intéresser aux méthodes de résolution par recherche arborescente. Nous introduisons une nouvelle approche pour la gestion des décisions de branchement, que nous appelons Dynamic Learning Search (DLS). Cette méthode définit de manière dynamique des règles de priorité pour la sélection des variables à chaque noeud et l’ordre des valeurs sur lesquelles brancher. Ces règles sont conçues dans une optique de généricité, de manière à pouvoir utiliser la méthode indépendamment du problème traité. Le principe général est de tenir compte par une technique d’apprentissage de l’impact qu’ont eu les décisions de branchement dans les parties déjà explorées de l’arbre. Nous évaluons l’efficacité de la méthode proposée sur deux problèmes classiques : un problème d’optimisation combinatoire et un problème à satisfaction de contraintes. La deuxième partie de ce mémoire traite des recherches à grand voisinage. Nous présentons un nouvel opérateur de voisinage, qui détermine par un algorithme de programmation dynamique la sous-séquence optimale d’un chemin dans un graphe. Nous montrons que cet opérateur est tout particulièrement destiné à des problèmes de tournées pour lesquels tous les noeuds ne nécessitent pas d’être visités. Nous appelons cette classe de problème les Problèmes de Tournées avec Couverture Partielle et présentons quelques problèmes faisant partie de cette classe. Les chapitres 3 et 4 montrent, à travers des tests expérimentaux conséquents, l’efficacité de l’opérateur que nous proposons en appliquant cette recherche à voisinage large sur deux problèmes, respectivement le Problème de l’Acheteur Itinérant (TPP) et le Problème de Voyageur de Commerce Généralisé (GTSP). Nous montrons alors que cet opérateur peut être combiné de manière efficace avec des métaheuristiques classiques, telles que des algorithmes génétiques ou des algorithmes d’Optimisation par Colonies de Fourmis. Enfin, la troisième partie présente des méthodes heuristiques basées sur un algorithme de Génération de Colonnes. Ces méthodes sont appliquées sur un problème complexe : le problème de Tournées de Véhicules avec Contraintes de Chargement à Deux Dimensions (2L-VRP). Nous montrons une partie des possibilités qu’il existe afin de modifier une méthode a priori exacte en une méthode heuristique et nous évaluons ces possibilités à l’aide de tests expérimentaux / We are interested in this thesis in the possibilities of hybridization between the exact methods and the methods heuristics to be able to take advantage of each of both approaches: optimality of the exact resolution, the less determinist character and the speed of the constituent heuristics. In the objective to resolve problems NP-hard of relatively important size such as the transportation problems, we are interested in the last two parts of this report in the conception of incomplete methods based on these hybridizations. In the first part, we are going to be interested in the methods of resolution by tree search. We introduce a new approach for the management of the decisions of connection, which we call Dynamic Learning Search ( DLS). This method defines in a dynamic way rules of priority for the selection of variables in every knot and the order of the values on which to connect. These rules are conceived in an optics of genericity, so as to be able to use the method independently of the treated problem. The general principle is to take into account by a technique of learning of the impact which had the decisions of connection in the parts already investigated in the tree. We estimate the efficiency of the method proposed on two classic problems: a combinatorial optimization problem and a constraints satisfaction problem. The second part of this report handles large neighborhood search. We present a new operator of neighborhood, who determines by an algorithm of dynamic programming the optimal sub-sequence of a road in a graph. We show that this operator is quite particularly intended for problems of tours for which all the vertices do not require to be visited. We call this class of problem the Problems of Tours with Partial Cover and present some problems being a part of this class. Chapters 3 and 4 show, through consequent experimental tests, the efficiency of the operator which we propose by applying this search to wide neighborhood on two problems, respectively the Traveling Purchaser Problem (TPP) and Generalized Traveling Salesman Problem ( GTSP). We show while this operator can be combined in a effective way with classic metaheuristics, such as genetic algorithms or algorithms of Ant Colony Optimization

La présente thèse porte sur la question de l’intelligibilité de la traduction juridique pour un praticien du droit. Notre hypothèse de travail consiste à dire que l’échec de la traduction juridique s’explique par l’absence de pertinence de la traduction pour son utilisateur. Pour éclairer cet aspect, une approche interdisciplinaire est adoptée. Méthodologiquement, nous partons de la critique de la notion d’équivalence et de la conception de la traduction comme recherche d’équivalents. Notre état de l’art se déploie en trois volets. Le premier volet traite de la théorie de la pertinence de Sperber et Wilson. Le second volet expose le traitement de la notion de pertinence en sciences de l’information. Le troisième volet présente la théorie de la pertinence et la théorie des connaissances élaborées par le sociologue Alfred Schütz Notre corpus d’étude comporte 145 bitextes allemand-français servant de base à des analyses contrastives. Dans la dernière partie, nous proposons une définition de la notion de pertinence et de ses conditions en traduction. Enfin, une méthode pratique de traduction fondée sur les notions de pertinence et d’usage est esquissée. / This thesis deals with the question of the intelligibility of legal translation for a legal practitioner. Our working hypothesis is that the failure of the legal translation is explained by the lack of relevance of the translation for its user. To shed light on this aspect, an interdisciplinary approach is adopted. Methodologically, we start from the criticism of the notion of equivalence and the conception of translation as a search for equivalents. Our state of the art is divided into three parts. The first part deals with the relevance theory of Sperber and Wilson. The second part describes the treatment of relevance in information science. The third part presents the theory of relevance and the theory of knowledge developed by sociologist Alfred Schütz. Our corpus includes 145 French-German texts used as a basis for contrasts analyses. In the personal contribution, we propose a definition of relevance and its conditions in translation. Finally, a practical method of translation based on the notions of relevance and usage is outlined.

Le système de fabrication des plaquettes de silicium (wafer) est la partie la plus complexe et la plus coûteuse du processus de fabrication des semi-conducteurs et son ordonnancement pour la production a un impact significatif sur la rentabilité économique. Le système d’outils Multi-cluster pour la fabrication de plaquettes est un système de type multi-boucles, largement utilisé dans la fabrication de plaquettes de 300 mm et 450 mm. Le problème d’ordonnancement dans ce système de production présente des caractéristiques pour les modèles de flux de plaquettes compliqué, des contraintes résidentielles strictes et des conflits de ressources à gérer, ce qui rend le problème très complexe. Dans cette thèse, l'outil multi-cluster est étudié et les recherches se concentrent principalement sur les caractéristiques des contraintes sur le temps de séjour, les contraintes sur les ressources utilisés et les flux plaquettes de silicium. Plus particulièrement, cette thèse traite trois problèmes d'ordonnancement: le problème d'ordonnancement cyclique unitaire pour un flux unique de plaquettes, le problème d'ordonnancement cyclique multi-unitaires dans un modèle de flux unique de plaquettes et le problème d'ordonnancement non-cyclique. Pour résoudre ces problèmes, des modèles robustes sont développés ainsi que certains algorithmes heuristiques efficaces sont construits pour atteindre les objectifs. L'objectif principal étant d'améliorer la performance des outils multi-cluster et d'augmenter le rendement des flux des plaquettes de silicium. Des tests de simulation et des analyses sont effectuées afin d’évaluer la performance des algorithmes proposés. Les résultats montrent la stabilité et l'efficacité de ces algorithmes. / Multi-cluster tool is a highly automated and costly wafer fabrication system with multi-loop coupling structure, and scheduling of such equipment directly affects the overall efficiency of semiconductor manufacturing enterprises. Multi-cluster tools scheduling problem has the features of large scale, complex wafer flow patterns, strict residency time constraints and intense resource conflict, which are significantly different from any other manufacturing system. Since the existing literatures have proved that most of the wafer fabrication systems scheduling problems are NP-hard, it’s difficult to obtain the optimal solution by using exact algorithms. Thus, how to develop an efficient heuristic algorithm to solve the multi-cluster tools scheduling problem attracts considerable attention both in academia and in industry. After reviewing the literatures, it is found that the research on the cyclic scheduling problem of multi-cluster tools rarely takes into account the characteristics of residency constraints. The scale of the object is limited to three single cluster tools, and the proposed scheduling methods are mostly mathematical programming and simple scheduling rules. Therefore, in this thesis, the multi-cluster tool is studied and our research mainly focuses on the characteristics of residency constraints, resource constraints and wafer flow patterns. Based on the descriptions of research domains, some solid models are developed for different scheduling problems and some efficient heuristic algorithms are constructed to realize the objectives. To deal with the problem, different approaches are proposed: A non-linear mixed-integer programming model, a two-stage = approximate-optimal scheduling algorithm, and a chaos-based particle swarm optimization-tabu search hybrid heuristic algorithm. Simulation experiments and analysis demonstrate the effectiveness of these algorithms. Results show the stability and efficiency of proposed algorithms.

Les développements récents de la recherche en sciences cognitives ont établi que les individus détectent fréquemment qu'ils sont en train de commettre certaines erreurs de raisonnement, alors même qu'ils n'identifient pas, et peut-être ne peuvent pas identifier, la source de ces erreurs. Jusqu'à maintenant, ce programme de recherche a principalement visé à démontrer que même les individus aux raisonnements les plus biaisés faisaient preuve de tendances à la détection de conflits. Le présent travail s'appuie sur ces résultats et analyse trois domaines d'enquête connexes et encore inexplorés : (1) les sous-types de détection de conflits ; (2) les différences individuelles quant à la détection ; (3) le caractère de généralité ou de spécificité au domaine des sensibilités pour la détection de conflits. En identifiant des sous-types de détection de conflits de plus en plus spécifiques, ce projet a pour objectif d'examiner les corrélations entre, d'une part, certaines sensibilités pour la détection de conflits, et des prédicteurs cognitifs, d'autre part. Il s'agit, fondamentalement, d'un travail préparatoire en vue d'une analyse différentielle complète des sensibilités particulières de détection de conflits parmi les individus en train de raisonner. / Recent state of the art research into cognitive biases has revealed that individuals often detect that they are making certain reasoning errors even when they themselves do not, perhaps cannot, articulate the source of the error. Until now, this research has focused primarily on demonstrating the existence of conflict detection tendencies among even the most biased reasoners. This thesis builds on this research by analyzing three related and unexplored areas of inquiry: (1) subtypes of conflict detection; (2) individual-specific differences among detectors; and (3) the domain generality or specificity of conflict detection sensitivities. By identifying increasingly fine-tuned detection subtypes, the project aims to explore correlations between particular conflict detection sensitivities and other cognitive predictors. It is, essentially, preparatory work for a complete differential analysis of conflict detection sensitivities among reasoners.

La SNCF utilise plusieurs engins spécialisés pour ausculter les fissures internes du rail. La fréquence d’auscultation de chaque rail est fonction du tonnage cumulé qui passe dessus. La programmation des engins d’auscultations ultrasonores est aujourd’hui décentralisée. Dans le cadre d’une étude de réorganisation, la SNCF souhaite étudier la faisabilité de l’optimisation de certaines tournées d’inspection. Dans le cadre de cette thèse de doctorat, l’optimisation de la programmation des engins d’auscultation à ultrasons est étudiée.Une modélisation mathématique sous forme de problème de tournées sur arcs généralisant plusieurs problèmes académiques est proposées. Une méthode de résolution exacte, appliquant la décomposition de Benders, est détaillée. À partir de cette approche, une heuristique de génération de colonnes et de contraintes est présentée et analysée numériquement sur des données réelles de 2009. Enfin, un logiciel industriel développé autour de cette approche est présenté / SNCF is using specialised rolling stock units to inspect internal defects in rails. Rail’s inspection frequency is defined by the cumulative weight of the trains which are going through. In2009, the scheduling of these train units is decentralised. SNCF is studying the centralisation of this process. In this Ph.D. thesis, a new problem, the Railroad Track Inspection SchedulingProblem is studied.A mathematical formulation, based on the generalization of classical arc routing models,is proposed. An exact solving approach, based on Benders’ decomposition scheme, is detailed.From this approach, a column and cut generation heuristic is developed, implemented, andtested on real datasets for 2009. The industrial software developed around this heuristic is presented.

Un déploiement adéquat et une bonne gestion des ambulances amènent des temps de réponse plus courts lors d'un appel d'urgence et ainsi permettent de réduire la souffrance, la mortalité et les conséquences néfastes sur la santé des patients. Ce mémoire est divisé en deux parties et adresse sous forme de deux articles les problèmes de la localisation des ambulances et de leur gestion. L'objectif du premier article est de résoudre le problème de localisation d'ambulances multi-périodes en faisant l'hypothèse d'une demande déterministe, dynamique et cyclique. Un modèle mathématique ainsi que deux méthodes heuristiques sont proposés pour aider à résoudre ce problème. La première heuristique utilise de façon répétitive la version mono-période du modèle mathématique proposé alors que la deuxième est une heuristique itérative composée d'une phase de construction et une phase d'amélioration. L'efficacité de ces méthodes est démontrée par leur application pour résoudre des problèmes fictifs ainsi qu'un problème réel fourni par la corporation Urgences-santé. Les résultats obtenus avec les deux méthodes heuristiques nous indiquent que ces méthodes, en plus d'être très rapides, donnent des plans de déploiement près du plan optimal. De plus, la méthode heuristique basée sur le modèle mono-période semble dominer la méthode heuristique itérative sur tous les points en plus d'être plus simple. L'objectif du deuxième article est d'évaluer l'efficacité de plusieurs règles de répartition dans le cadre de la gestion des demandes d'intervention d'un réseau de service ambulancier. Deux types de décisions font l'objet de cette étude : le choix d'une ambulance pour répondre à une demande d'intervention et le choix du poste d'attente où ce véhicule sera redéployé après son intervention. Les règles généralement utilisées en pratique sont comparées à des règles visant non seulement la réduction des temps d'attente mais aussi le maintient d'une bonne couverture territoriale. Différentes règles sont testées sur des problèmes fictifs ainsi que sur un problème réel fourni par la corporation Urgences-santé. Les résultats obtenus démontrent que l'application d'une règle d'assignation simple comme affecter l'ambulance qui peut se rendre le plus rapidement possible sur les lieux de la demande d'intervention peut être efficace seulement si un bon plan de déploiement et de redéploiement est maintenu. On démontre que l'utilisation d'une règle de redéploiement visant la maximisation de la couverture du territoire permet d'atteindre un bon niveau d'efficacité.