Stochastic combinatorial optimization problems are combinatorial optimization problems where part of the problem data are probabilistic. The focus of this thesis is on stochastic routing problems, a class of stochastic combinatorial optimization problems that arise in distribution management. Stochastic routing problems involve finding the best solution to distribute goods across a logistic network. In the problems we tackle, we consider a setting in which the cost of a solution is described by a random variable; the goal is to find the solution that minimizes the expected cost. Solving such stochastic routing problems is a challenging task because of two main factors. First, the number of possible solutions grows exponentially with the instance size. Second, computing the expected cost of a solution is computationally very expensive. <p><br><p>To tackle stochastic routing problems, stochastic local search algorithms such as iterative improvement algorithms and metaheuristics are quite promising because they offer effective strategies to tackle the combinatorial nature of these problems. However, a crucial factor that determines the success of these algorithms in stochastic settings is the trade-off between the computation time needed to search for high quality solutions in a large search space and the computation time spent in computing the expected cost of solutions obtained during the search. <p><br><p>To compute the expected cost of solutions in stochastic routing problems, two classes of approaches have been proposed in the literature: analytical computation and empirical estimation. The former exactly computes the expected cost using closed-form expressions; the latter estimates the expected cost through Monte Carlo simulation.<p><br><p>Many previously proposed metaheuristics for stochastic routing problems use the analytical computation approach. However, in a large number of practical stochastic routing problems, due to the presence of complex constraints, the use of the analytical computation approach is difficult, time consuming or even impossible. Even for the prototypical stochastic routing problems that we consider in this thesis, the adoption of the analytical computation approach is computationally expensive. Notwithstanding the fact that the empirical estimation approach can address the issues posed by the analytical computation approach, its adoption in metaheuristics to tackle stochastic routing problems has never been thoroughly investigated. <p><br><p>In this thesis, we study two classical stochastic routing problems: the probabilistic traveling salesman problem (PTSP) and the vehicle routing problem with stochastic demands and customers (VRPSDC). The goal of the thesis is to design, implement, and analyze effective metaheuristics that use the empirical estimation approach to tackle these two problems. The main results of this thesis are: <p>1) The empirical estimation approach is a viable alternative to the widely-adopted analytical computation approach for the PTSP and the VRPSDC; <p>2) A principled adoption of the empirical estimation approach in metaheuristics results in high performing algorithms for tackling the PTSP and the VRPSDC. The estimation-based metaheuristics developed in this thesis for these two problems define the new state-of-the-art. / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

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

Plusieurs problèmes d'optimisation combinatoire sont dits NP-difficiles et ne peuvent être résolus de façon optimale par des algorithmes exacts. Les métaheuristiques ont prouvé qu'elles pouvaient être efficaces pour résoudre un grand nombre de ces problèmes en leur trouvant des solutions approchées en un temps raisonnable. Cependant, face à des instances de grande taille, elles ont besoin d'un temps de calcul et d'une quantité d'espace mémoire considérables pour être performantes dans l'exploration de l'espace de recherche. Par conséquent, l'intérêt voué à leur déploiement sur des architectures de calcul haute performance a augmenté durant ces dernières années. Les approches de parallélisation existantes suivent généralement les paradigmes de passage de messages ou de mémoire partagée qui conviennent aux architectures traditionnelles à base de microprocesseurs, aussi appelés CPU (Central Processing Unit).Cependant, la recherche évolue très rapidement dans le domaine du parallélisme et de nouvelles architectures émergent, notamment les accélérateurs matériels qui permettent de décharger le CPU de certaines de ses tâches. Parmi ceux-ci, les processeurs graphiques ou GPU (Graphics Processing Units) présentent une architecture massivement parallèle possédant un grand potentiel mais aussi de nouvelles difficultés d'algorithmique et de programmation. En effet, les modèles de parallélisation de métaheuristiques existants sont généralement inadaptés aux environnements de calcul de type GPU. Certains travaux ont d'ailleurs abordé ce sujet sans toutefois y apporter une vision globale et fondamentale.L'objectif général de cette thèse est de proposer un cadre de référence permettant l'implémentation efficace des métaheuristiques sur des architectures parallèles basées sur les GPU. Elle débute par un état de l'art décrivant les travaux existants sur la parallélisation GPU des métaheuristiques et les classifications générales des métaheuristiques parallèles. Une taxonomie originale est ensuite proposée afin de classifier les implémentations recensées et de formaliser les stratégies de parallélisation sur GPU dans un cadre méthodologique cohérent. Cette thèse vise également à valider cette taxonomie en exploitant ses principales composantes pour proposer des stratégies de parallélisation originales spécifiquement adaptées aux architectures GPU. Plusieurs implémentations performantes basées sur les métaheuristiques d'Optimisation par Colonie de Fourmis et de Recherche Locale Itérée sont ainsi proposées pour la résolution du problème du Voyageur de Commerce. Une étude expérimentale structurée et minutieuse est réalisée afin d'évaluer et de comparer la performance des approches autant au niveau de la qualité des solutions trouvées que de la réduction du temps de calcul. / Several combinatorial optimization problems are NP-hard and can only be solved optimally by exact algorithms for small instances. Metaheuristics have proved to be effective in solving many of these problems by finding approximate solutions in a reasonable time. However, dealing with large instances, they may require considerable computation time and amount of memory space to be efficient in the exploration of the search space. Therefore, the interest devoted to their deployment on high performance computing architectures has increased over the past years. Existing parallelization approaches generally follow the message-passing and shared-memory computing paradigms which are suitable for traditional architectures based on microprocessors, also called CPU (Central Processing Unit). However, research in the field of parallel computing is rapidly evolving and new architectures emerge, including hardware accelerators which offloads the CPU of some of its tasks. Among them, graphics processors or GPUs (Graphics Processing Units) have a massively parallel architecture with great potential but also imply new algorithmic and programming challenges. In fact, existing parallelization models of metaheuristics are generally unsuited to computing environments like GPUs. Few works have tackled this subject without providing a comprehensive and fundamental view of it.The general purpose of this thesis is to propose a framework for the effective implementation of metaheuristics on parallel architectures based on GPUs. It begins with a state of the art describing existing works on GPU parallelization of metaheuristics and general classifications of parallel metaheuristics. An original taxonomy is then designed to classify identified implementations and to formalize GPU parallelization strategies in a coherent methodological framework. This thesis also aims to validate this taxonomy by exploiting its main components to propose original parallelization strategies specifically tailored to GPU architectures. Several effective implementations based on Ant Colony Optimization and Iterated Local Search metaheuristics are thus proposed for solving the Travelling Salesman Problem. A structured and thorough experimental study is conducted to evaluate and compare the performance of approaches on criteria related to solution quality and computing time reduction.

Comme beaucoup de systèmes, un réseau électrique doit faire face à des pannes qui, compte tenu de sa grande connectivité, peuvent s'étendre à des régions entières : on parle alors de blackout (phénomène d'avalanche), c'est-à-dire ayant des conséquences à grande échelle. La taille des réseaux électriques et leur complexité rendent difficile la compréhension de ces phénomènes qui émergent localement. Un certain nombre de travaux existe et se fond sur un usage intensif des outils de physique statistique. L'adaptation de méthodes de percolation et les systèmes critiques auto-organisés sont autant d'outils de choix pour décrire les propriétés statistiques et topologiques d'un réseau. Les outils d'optimisation par métaheuristiques, plus particulièrement l'optimisation par essaim de particules (OEP, ou PSO en anglais) et les algorithmes génétiques (AGs), se sont révélés être la pierre angulaire de ce travail et ont permis de définir des structures opérationnelles. Les travaux développés dans ce domaine sont encore émergents et cette thèse y amène une contribution à plusieurs titres. Nous avons mis tout d'abord à profit des techniques d'optimisation afin de mieux “ rigidifier ” un réseau électrique en couplant la topologie de ce dernier au maintien des tensions aux noeuds du réseau par implémentation de FACTS (Flexible Alternative Current Transmission System). Pour le placement optimal de FACTS, l'objectif est de déterminer la répartition optimale de la puissance réactive, en relation avec la localisation et le dimensionnement optimal de FACTS, afin d'améliorer les performances d'un réseau électrique. Quatre principales questions sont alors abordées: 1) Où placer des FACTS dans le réseau ? Combien de FACTS ? Quelle puissance attribuer à ces FACTS ? Quel(s) type(s) de FACTS ? A quel prix ? Dans cette thèse, toutes ces questions seront modélisées et abordées d'un point de vue électrique et optimal en appliquant, dans un premier temps, l'optimisation par essaim de particules OEP basique puis, dans un deuxième temps, en proposant un nouvel algorithme OEP (alpha-SLPSO) et une recherche locale (alpha-LLS) s'inspirant ainsi du concept de l'OEP basique et des lois de probabilité stables dites «alpha-stables de Lévy». Par ailleurs, l'ampleur du projet défini par l'équipe @RiskTeam d'Alstom Grid oblige l'utilisation de plusieurs techniques (tirées de la physique, des statistiques, etc.) destinées à des fins particulières dont l'estimation des paramètres des lois alpha-stable de Lévy. Face à l'échec des techniques déjà existantes pour l'estimation des lois alpha −stable de paramètre alpha < 0.6 , nous proposons un nouvel estimateur semi-paramétrique de cette famille de probabilité utilisant les métaheuristiques pour résoudre le problème d'optimisation sous-jacent. Enfin, en annexe de cette thèse, un outil d'aide à la décision destiné à une équipe interne d'Alstom Grid qui consiste en l'optimisation de la topologie interne d'un parc éolien est détaillé dans le dernier chapitre / Like many systems, an electrical power grid must contend with faillures which, given its higth connectivity, could spread to entire regions: this is referred to blackout (avalanche phenomena), ie. with large-scale consequences. The size of power grids and their complexity make difficult to grasp these locally emergent phenomena. There is a number of existing works that were based on extensive use of statistical physics tools. The adaptation of percolation's methods and the Self-Organized-Criticality systems provide practical tools to describe the statistical and topological properties of a network. Optimization tools by metaheuristics particularly, particle swarm optimization (PSO) and genetic algorithms (GA) have proved to be the cornerstone of this work and helped to define operational structures. Works developed in this area are still emerging. This thesis brings a contribution in several ways. First of all, we have taken advantage in optimization technics to better "stiffen" a power grid by coupling its topology with maintaining voltages at the nodes of the network using FACTS (Flexible Alternative Current Transmission System). In the optimal location FACTS problem, the objective is to determine the optimal allocation of reactive power, in relation to the location and optimal sizing of FACTS, in order to improve the performance of the power grid. Four main issues are then discussed: 1) Where to place FACTS in the network? How many FACTS? What power attributed to these FACTS? What type(s) attributed to these FACTS? At what prices ? In this thesis, all these questions will be modeled and discussed from the point of view of optimal power by applying, firstly, the strandard particle swarm optimization and by proposing a novel particle swarm optimization (alpha-SLPOS) and a local search (alpha-LLS). These two algorithms are inspired by the basic concept of PSO and the stable distributions (alpha-stable laws). Moreover, the scope of the project defined by the team @RiskTeam Alstom Grid requires the use of several techniques (from physics, statistics, etc) for particular purposes including the alpha-stable parametere estimation problem. Facing the failure of the existing methods for estimating the parameters of alpha-stable laws for alpha<0.6, we propose a novel semi-parametric estimator for such of probability distribution familly using metaheuristic to solve the underlying problem of optimization. Finally, in the end of the thesis, a decision support tool is designed for an internal team of Alstom Grid to optimize the internal topology of a wind farm

Afin d’améliorer la qualité de prédiction des techniques de classification automatique et de fouilles de données, plusieurs modèles ont été proposés dans la littérature en vue d’extraire des connaissances à partir des données. Toutefois, avec l’expansion des systèmes d’information et des technologies associées, ces techniques d’apprentissage s’avèrent de moins en moins adaptées aux nouvelles tailles et dimensions des données. On s’intéresse dans cette étude aux problèmes de grande dimensionnalité et à l’amélioration du processus d’apprentissage des méthodes de classification à travers les techniques de filtrage et de sélection d’attributs. Le problème « d’identification d’attributs pertinents » (Feature Selection Problem), tel qu’il est défini dans la littérature, relève d’une nature combinatoire. Dans le cadre de cette thèse, on s’est intéressé au développement de nouvelles techniques d’optimisation approchées et spécifiques au problème traité ainsi qu’à l’amélioration d’algorithmes existants. La conception, l’implémentation et l’étude empirique ont montré l’efficacité et la pertinence des métaheuristiques proposées. / Although the expansion of storage technologies, networking systems, and information system methodologies, the capabilities of conventional data processing techniques remain limited. The need to knowledge extraction, compact representation and data analysis are highly motivated by data expansion. Nevertheless, learning from data might be a complex task, particularly when it includes noisy, redundant and information-less attributes. Feature Selection (FS) tries to select the most relevant attributes from raw data, and hence guides the construction of final classification models or decision support systems. Selected features should be representative of the underlying data and provide effective usefulness to the targeted learning paradigm (i.e. classification). In this thesis, we investigate different optimization paradigms as well as its adaptation to the requirements of the feature selection challenges, namely the problem combinatorial nature. Both theoritical and empirical aspects were studied, and confirm the effectiveness of the adopted methodology as well as the proposed metaheuristic based approaches.

High school timetabling problems consist in assigning meetings between classes and teachers, with the goal of minimizing the violation of specific soft requisites. This category of problems has been extensively studied since the 1950s, mostly via mixed-integer programming and metaheuristic techniques. However, the computation of optimal or near-optimal solutions using mixed-integer programs or metaheuristics is still a challenge for most practical problems. In this thesis, we investigate new mixed-integer programming formulations, column generation approaches and parallel metaheuristic based algorithms to compute lower bounds and solutions for high school timetabling problems. Extensive computational experiments conducted with real-world instances demonstrate that our best formulations are competitive with best-known formulations, while our parallel algorithms present superior performance than the state-of-the-art methods. / Problemas de horários escolares consistem em alocar encontros entre turmas e professores, com objetivo de minimizar violações a requisitos qualitativos específicos. Esta categoria de problemas tem sido largamente estudada desde 1950, particularmente via técnicas de programação linear inteira mista e metaheurísticas. Entretanto, a computação de soluções ótimas ou quase ótimas usando programas inteiro-mistos ou metaheurísticas ainda é um desafio na maioria dos problemas práticos. Nesta tese, nós investigamos novas formulações inteiro-mistas, decomposições por geração de colunas e algoritmos baseados em metaheurísticas paralelas para computar limitantes inferiores e soluções para problemas de horários escolares. Extensivos experimentos computacionais conduzidos com instâncias reais demonstram que nossas melhores formulações são competitivas com as melhores formulações existentes, enquanto nossos algoritmos paralelos são superiores em performance computacional quando comparados com métodos que são estado-da-arte.

O principal objetivo deste estudo é propor uma nova metodologia para lidar com o problema de Planejamento da Expansão de Redes de Transmissão de Energia Elétrica com Múltiplos Cenários de Geração (PERTEEG). Com a metodologia proposta neste trabalho almeja-se construir planos de expansão de redes de transmissão de energia elétrica que sejam capazes de, no menor custo de investimento possível, satisfazer às novas exigências dos sistemas elétricos modernos, tais como construção de redes de transmissão livres de congestionamento e robustas à incerteza em relação aos cenários de geração futuros. Através de estudos realizados na literatura do problema, verificou-se que novos modelos e metodologias de abordagem do PERTEEG se fazem necessários. Ao se modelar o PERTEEG visando construir redes de transmissão que contornem as incertezas em relação aos cenários de geração futuros e concomitantemente minimizar o custo de investimento para a expansão do sistema, o planejador se depara com um problema de otimização multiobjetivo. Existem na literatura da pesquisa operacional diversos algoritmos que visam lidar com problemas multiobjetivos. Nesta tese, foram aplicados dois desses algoritmos: Nondominated Sorting Genetic Algorithms-II (NSGA-II) e SPEA2: Strength Pareto Evolutionary Algorithm (SPEA2). Em primeira análise, se destacou uma das maiores dificuldade de lidar com o PERTEEG, a saber, o esforço computacional elevado. Por isso, vislumbrou-se que uma possível solução para contornar esta dificuldade esteja na computação paralela. Para se confirmar esta suspeita, nesta tese foram implementadas versões paralelas dos algoritmos sequenciais testados. A qualidade das soluções encontradas pelos algoritmos foram bastante superiores às soluções encontradas pelos algoritmos sequenciais. Neste trabalho também será mostrado que as soluções ótimas clássicas considerando somente o objetivo de m´mínimo custo são incapazes de atender às novas necessidades dos sistemas elétricos de potência. Testes computacionais foram realizados e analisados neste trabalho. Considerando as metodologias conhecidas na literatura para medição da qualidade das soluções encontradas por algoritmos multiobjetivo, se pode afirmar de que a proposta de abordagem do problema de PERTEEG pode ser viável tanto do ponto de vista de engenharia como do ponto de vista da computação matemática. / The main objective of this study is to propose a new methodology to deal with the long-term transmission system expansion planning with multiple generation dispatch scenarios problem (TEP-MDG). With the methodology proposed in this thesis we aim to build expansion plans with minimum investment cost and also capable of meeting the new demands of modern electrical systems, such as uncertainty about the future generation scenarios and congestion in the transmission systems. By modeling the TEP-MDG aiming to build transmission networks that circumvent the uncertainties regarding the future generation scenarios and simultaneously minimize the cost of investment for transmission networks expansion, the planner faces a multiobjective optimization problem. One can find various algorithms that aim to deal with multiobjective problems in the literature of operations research. In this thesis, we apply two of these algorithms: Nondominated Sorting Genetic Algorithms-II (NSGA-II) and SPEA2: Strength Pareto Evolutionary Algorithm (SPEA2). In a first analysis, we have found that the most critical issue with the TEP-MOG is the high computational demand. Therefore, in order to circumvent this difficulty we have implemented parallel versions of the sequential algorithms tested. In performed tests, the parallel algorithms have found solutions of superior quality than the solutions found by the sequential algorithms. In this thesis we also show that optimal solutions considering only the classical least cost objective are unable to meet the electric power systems new demands. Tests have been performed and analyzed in this work. By considering the methods known in the literature convinced to measure the quality of solutions found by multiobjective algorithms, we concluded that the proposed approach to TEP-MDG may be feasible from the point of view of both engineering and computational mathematics.

Only if humanity acts quickly and resolutely can we limit global warming' conclude more than 25,000 academics with the statement of SCIENTISTS FOR FUTURE. The concern about global warming and the extinction of species has steadily increased in recent years.

{This thesis deals with optimization by means of metaheuristics, which are used for complicated engineering problems that cannot be solved by classical methods of mathematical programming. At the beginning, choosed metaheuristics are described: simulated annealing, particle swarm optimization and genetic algorithm; and then they are compared with use of test functions. These algorithms are implemented in Python programming language with use of package called DEAP, which is also described in this thesis. Algorithms are then applied for optimization of design parameters of the heat storage unit.