Show simple item record

Recherche Locale, structures de données et Recherche Monte-Carlo pour les problèmes d'optimisation combinatoire Multi-Objectif

dc.contributor.advisorCazenave, Tristan
dc.contributor.advisorVanderpooten, Daniel
hal.structure.identifier
dc.contributor.authorCornu, Marek*
dc.date.accessioned2018-06-05T08:34:35Z
dc.date.available2018-06-05T08:34:35Z
dc.date.issued2017-12-18
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/17810
dc.description.abstractfrDe nombreux problèmes d'optimisation combinatoire considèrent plusieurs objectifs, souvent conflictuels. Cette thèse s'intéresse à l'utilisation de méthodes de recherche locale, de structures de données et de recherche Monte-Carlo pour la recherche de l'ensemble des solutions efficaces de tels problèmes, représentant l'ensemble des meilleurs compromis pouvant être réalisés en considération de tous les objectifs.Nous proposons une nouvelle méthode d'approximation appelée 2-Phase Iterated Pareto Local Search based on Decomposition (2PIPLS/D) combinant les concepts de recherche locale Pareto (PLS) et de décomposition. La PLS est une descente de recherche locale adaptée au multi-objectif, et la décomposition consiste en la subdivision du problème multi-objectif en plusieurs problèmes mono-objectif. Deux méthodes d'optimisation mono-objectif sont considérées: la recherche locale itérée et la recherche Monte-Carlo imbriquée. Deux modules principaux sont intégrés à 2PIPLS/D. Le premier généralise et améliore une méthode existante et génère un ensemble initial de solutions. Le second réduit efficacement l'espace de recherche et permet d'accélérer la PLS sans négliger la qualité de l'approximation générée. Nous introduisons aussi deux nouvelles structures de données gérant dynamiquement un ensemble de solutions incomparables, la première est spécialisée pour le cas bi-objectif et la seconde pour le cas général.2PIPLS/D est appliquée au Problème du Voyageur de Commerce bi-objectif et tri-objectif et surpasse ses concurrents sur les instances testées. Ensuite, 2PIPLS/D est appliquée à un nouveau problème avec cinq objectifs en lien avec la récente réforme territoriale d'agrandissement des régions françaises.fr
dc.language.isoen
dc.subjectOptimisation combinatoire multi-Objectiffr
dc.subjectMéta-Heuristiquefr
dc.subjectRecherche localefr
dc.subjectStructures de donnéesfr
dc.subjectDécompositionfr
dc.subjectRecherche Monte-Carlofr
dc.subjectProblème du Voyageur de Commercefr
dc.subjectMulti-Objective combinatorial optimizationen
dc.subjectMeta-Heuristicen
dc.subjectLocal searchen
dc.subjectData structuresen
dc.subjectDecompositionen
dc.subjectMonte Carlo searchen
dc.subjectTraveling Salesman Problemen
dc.subject.ddc005.1
dc.subject.classificationjelC15
dc.titleLocal Search, data structures and Monte Carlo Search for Multi-Objective Combinatorial Optimization Problemsen
dc.titleRecherche Locale, structures de données et Recherche Monte-Carlo pour les problèmes d'optimisation combinatoire Multi-Objectiffr
dc.typeThèse
dc.contributor.editoruniversityUniversité Paris Dauphine
dc.description.abstractenMany Combinatorial Optimization problems consider several, often conflicting, objectives. This thesis deals with Local Search, data structures and Monte Carlo Search methods for finding the set of efficient solutions of such problems, which is the set of all best possible trade-offs given all the objectives.We propose a new approximation method called 2-Phase Iterated Pareto Local Search based on Decomposition (2PIPLS/D) combining the notions of Pareto Local Search (PLS) and Decomposition. PLS is a local search descent adapted to Multi-Objective spaces, and Decomposition consists in the subdivision of the Multi-Objective problem into a number of Single-Objective problems. Two Single-Objective methods are considered: Iterated Local Search and Nested Monte Carlo Search. Two main components are embedded within the 2PIPLS/D framework. The first one generalizes and improves an existing method generating an initial set of solutions. The second one reduces efficiently the search space and accelerates PLS without notable impact on the quality of the generated approximation. We also introduce two new data structures for dynamically managing a set of incomparable solutions. The first one is specialized for the bi-objective case, while the second one is general.2PIPLS/D is applied to the bi-objective and tri-objective Traveling Salesman Problem and outperforms its competitors on tested instances. Then, 2PIPLS/D is instantiated on a new five-objective problem related to the recent territorial reform of French regions which resulted in the reassignment of departments to new larger regions.en
dc.identifier.theseid2017PSLED043
dc.subject.ddclabelProgrammation, logiciels, organisation des données
hal.author.functionaut


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record