Auswahl der wissenschaftlichen Literatur zum Thema „Optimisation combinatoire multi-objectifs“

L’objectif de ce projet de trois ans est de proposer des avancées conceptuelles et technologiques dans la résolution de problèmes d’ordonnancement du personnel. L’atteinte de cet objectif passe par la proposition de nouveaux algorithmes basés sur les métaheuristiques et leur implémentation sur les architectures de calcul haute performance. Ce projet s’inscrit en complémentarité du projet HORUS qui bénéficie d’une subvention ANR et qui réunit les expertises scientifiques de deux laboratoires universitaires spécialisés en optimisation et en calcul parallèle : l’équipe SysCom du laboratoire CReSTIC de l’URCA et l’équipe CaRO du laboratoire PRiSM de l’UVSQ. Les avancées technologiques proposées s’appuient également sur les moyens de calcul haute performance offerts par le Centre de Calcul Régional Champagne-Ardenne
.Many academic and industrial optimization problems are multi-objective and have been of particular interest to researchers in recent years. These problems usually do not have a single optimal solution but a set of best trade-off solutions which form the so-called Pareto front in the objective space. In order to approximate the Pareto front, multi-objective evolutionary algorithms (MOEAs) have been largely investigated in the fields of continuous and combinatorial optimization. Contrary to some classical algorithms, MOEAs have the ability to provide a number of solutions in one single run and are less sensitive to the shape of the Pareto front.As they often require a high amount of computing resources to explore large portions of the search space and handle complex real-life constraints, MOEAs could greatly benefit from today's high-performance computing architectures. Although significant progress has been made in recent years in the design and improvement of parallel models for evolutionary algorithms, most of these models have limited scalability and ability to solve various problems. In fact, solving multi-objective combinatorial optimization problems efficiently on a large number of processors remains a challenge today.This thesis aims to propose an island model which is based on objective space division. The main features of the proposed model are the following (i) An organizer has a global view of the current search via a global archive (ii) Asynchronous cooperation between islands, especially for the exchange of local archives with the organizer to limit model overheads (iii)Control islands to guide the exploration of the search space and improve diversity (iv) A periodic use of a specific local search procedure to improve convergence. Extensive experiments have been conducted to evaluate the performance of the approach and more particularly of each component in the resolution of two classical combinatorial problems, the travelling salesman problem and quadratic assignment problem. Extensibility and quality of the solutions are analyzed compared to state-of-the-art parallel models

Cette thèse s'intéresse à la résolution de problèmes de décision sur domaine combinatoire par des méthodes d'élicitation incrémentale des préférences basée le regret pour l'optimisation interactive. On se situe à l'intersection de la théorie de la décision, de la recherche opérationnelle et de l'intelligence artificielle, en théorie de la décision algorithmique. On suppose que les préférences du décideur peuvent être représentées par une fonction de scalarisation paramétrée (somme pondérée, OWA et intégrale de Choquet), mais que les paramètres (par exemple, le jeu de poids) ne sont pas connus au départ. L'apprentissage actif des paramètres est entremêlé à la résolution du problème dans le but d'apprendre seulement la part d'information sur ce paramètre qui est utile pour résoudre le problème donnée. L'originalité de ces travaux réside dans la conception de méthodes fondées sur la recherche heuristique couplée à l'élicitation incrémentale pour déterminer la meilleure solution du décideur. Nous proposons d'abord deux méthodes pour résoudre des problèmes d'optimisation combinatoire multi-objectifs avec des préférences imprécises, la première basée sur la recherche locale et la seconde sur un algorithme génétique. Nous proposons ensuite deux approches permettant l'élicitation d'une fonction d'ensemble linéaire, sous-modulaire et super-modulaire avec la construction d'un sous-ensemble indépendant optimal soumis à une contrainte de matroïde. La première approche est basée sur un algorithme glouton et l'autre sur la recherche locale. Afin de démontrer l'efficacité pratique de nos approches, nos algorithmes sont testés numériquement sur différents problèmes et évalués en termes de temps de calcul, de nombre de requêtes et d'erreur empirique
This thesis is concerned with solving combinatorial domain decision problems using incremental regret-based preference elicitation methods for interactive optimization. It is situated at the intersection of decision theory, operations research and artificial intelligence, in algorithmic decision theory. It is assumed that the decision maker's preferences can be represented by a parameterised scalarization function (weighted sum, OWA and Choquet integral), but the parameters (e.g. set of weights) are not known at the beginning. The active learning of the parameters is intertwined with the solution of the problem in order to learn only that part of the information about the parameter that is useful to solve the given problem. The originality of this work lies in the use of methods based on heuristic search coupled with incremental elicitation to determine the best solution for the decision maker. In first we propose two methods for solving multi-objective combinatorial optimisation problems with imprecise preferences, the first based on local search and the second on a genetic algorithm. We then propose two approaches for the elicitation of a linear, submodular and super-modular set function with the construction of an optimal independent subset subject to a matroid constraint. The first approach is based on a greedy algorithm and the other on local search. In order to demonstrate the practical effectiveness of our approaches, our algorithms are numerically tested on different problems and evaluated in terms of computation time, number of queries and empirical error

Dans cette thèse nous nous intéressons à la prise en compte des préférences du décideur pour le calcul des plus courts chemins multi-objectif. Les préférences du décideur sont modélisées a priori par une fonction d’utilité basée sur une intégrale de Choquet. Plutôt que de calculer l’ensemble des solutions efficaces puis de sélectionner une solution optimale selon cette fonction d’utilité, nous cherchons à directement construire une solution efficace optimale au regard des préférences. Le travail réalisé développe une règle de coupe, propose une relation de dominance et valide ces propositions sur un problème de routage multi-objectif rencontré dans les réseaux informatiques. La règle de coupe permet de réduire l’espace de recherche en calculant une somme pondérée bornant la fonction d’utilité. Plusieurs méthodes pour le calcul d’une telle somme pondérée sont proposées, analysées et comparées. Nous définissons une nouvelle relation de dominance capable de prendre en compte la fonction d’utilité et raffinant la relation de dominance de Pareto. Des conditions suffisantes de cette dominance sont proposées, elles permettent de réduire le nombre de solutions calculées et les temps de calcul par rapport aux méthodes existantes. Nous montrons que les préférences d’un administrateur réseau, dans le cadre du routage multi-objectif au niveau IP, peuvent être modélisées à l’aide d’une fonction d’utilité basée sur l’intégrale de Choquet. Les résultats précédents sont appliqués pour la résolution de ce problème
The purpose of this thesis is to handle decision maker preferences for computing multi-objective shortest paths. Decision maker preferences are modeled a priori with a utility function based on a Choquet integral. Instead of computing the set of efficient solutions and choosing afterward an optimal solution according to the utility function, we aim to directly compute an efficient optimal solution satisfying decision maker preferences. In this thesis we develop a pruning rule, propose a dominance relation and valid these propositions in a multi-objective routing problem for computer networks. The pruning rule allows to reduce the search space by computing a weighted sum that bounds the utility function. Several methods for computing such weighted sum are proposed, analyzed and compared. We define a new dominance relation that considers the utility function and refines Pareto dominance. Sufficient conditions for this dominance are proposed, they allow to reduce the number of solutions computed and computing time compared to existing methods. We highlight that network administrator preferences, for multi-objectif routing in IP network, can be modeled with a utility function based on the Choquet integral. Previous results are applied for solving this problem

Notre objectif dans cette thèse est de proposer des algorithmes efficaces pour résoudre des problèmes d’optimisation combinatoire difficiles. Dans un premier temps, nous établissons le principe de l’énumération ordonnée qui consiste à générer dans un ordre adéquat les solutions d’un problème relâché associé au problème principal jusqu’à l’obtention de la preuve d’optimalité d’une solution. Nous construisons une procédure générique dans le cadre général des problème d’optimisation combinatoire. Dans un second temps nous abordons les applications de notre algorithme sur des problèmes qui admettent le problème d’affectation comme relaxation. Le premier cas particulier que nous étudions est la recherche d’une solution de bon compromis pour le problème d’affectation multiobjectif. La seconde application se rapporte au problème du voyageur de commerce asymétrique qui présente la difficulté de comporter des contraintes qui interdisent les sous-tournées, en plus des contraintes du problème d’affectation
Our aim in this thesis is to propose efficient algorithms for solving difficult combinatorial optimization problems. Our algorithms are based on a generic method of ordered enumeration. Initially, we describe the principle of ordered enumeration which consists in generating in a specific order solutions of a relaxed problem associated to the difficult main problem, until meeting a proof of the optimality of a feasible solution. We construct a generic procedure in the general context of combinatorial optimization problems. In a second step we discuss applications of our algorithm on some difficult problems which admit the assignment problem as relaxation. The first special case we study is the search for a compromise solution to the multiobjective assignment problem. The second application is the asymmetric travelling salesman problem, which contains sub-tour constraints in addition to the constraints of the assignment problem

Les problèmes d’optimisation multi-objectifs mènent souvent à considérer des ensembles de points non-dominés très grands à mesure que la taille et le nombre d’objectifs du problème augmentent. Générer l’ensemble de ces points demande des temps de calculs prohibitifs. De plus, la plupart des solutions correspondantes ne sont pas pertinentes pour un décideur. Une autre approche consiste à utiliser des informations de préférence, ce qui produit un nombre très limité de solutions avec des temps de calcul réduits. Cela nécessite la plupart du temps une élicitation précise de paramètres. Cette étape est souvent difficile pour un décideur et peut amener à délaisser certaines solutions intéressantes. Une approche intermédiaire consiste à raisonner avec des relations de préférences construites à partir d’informations partielles. Nous présentons dans cette thèse plusieurs modèles de relations partielles de préférences. En particulier, nous nous sommes intéressés à la génération de l’ensemble des points non-dominés selon ces relations. Les expérimentations démontrent la pertinence de notre approche en termes de temps de calcul et qualité des points générés
Multi-objective optimization problems often lead to large nondominated sets, as the size of the problem or the number of objectives increases. Generating the whole nondominated set requires significant computation time, while most of the corresponding solutions are irrelevant to the decision maker. Another approach consists in obtaining preference information, which reduces the computation time and produces one or a very limited number of solutions. This requires the elicitation of precise preference parameters most of the time, which is often difficult and partly arbitrary, and might discard solutions of interest. An intermediate approach consists in using partial preference models.In this thesis, we present several partial preference models. We especially focused on the generation of the nondominated set according to these preference relations. This approach shows competitive performances both on computation time and quality of the generated preferred sets

La recherche de solutions équilibrées dans des problèmes multi-objectifs est un des enjeux majeurs de problématiques comme la décision multi-critères, multi-agents ou la décision dans l'incertain. La structure des problèmes sur lesquels portent cette recherche peut être combinatoire ou continue, et rendre impossible la comparaison paire à paire des différentes solutions pour évaluer la meilleure d'entre elles. Les travaux de cette thèse tente d'apporter une réponse algorithmique à cette question, en proposant des approches par programmation mathématique et par programmation dynamique pour la recherche de solutions optimales dans des problèmes multi-objectifs combinatoires et continus. Des modèles de décision sous la forme de fonctions d'agrégation dépendant du rang sont considérés dans cette thèse pour comparer les solutions entre elles. Nous étudions en particulier la résolution de programmes linéaires et mixtes, où la fonction objectif est définie comme une intégrale de Choquet sur un ensemble d'objectifs. Nous traitons ensuite de la recherche de solutions robustes dans des problèmes de décision dans l'incertain où la vraisemblance des évènements est définie sous la forme de polyèdre de probabilités possibles (modèle multi-prior). Nous consacrons aussi un chapitre à la recherche de chemins Choquet-optimaux, et nous proposons des règles de dominance pour des algorithmes de programmation dynamique, qui vont permettre d'accélérer la résolution en supprimant de la recherche des sous-chemins qui ne peuvent pas mener à des solutions optimales. Enfin, nous aborderons le thème des mécanismes incitatifs pour des procédures de décision multi-agents, lorsque des modèles de décision complexes comme l'intégrale de Choquet sont utilisés
The search for well-balanced solutions in multiobjective problems is a major issue in decision-making under uncertainty, multicriteria or multiagent decision-making. The problem's structure where this search takes place can be combinatorial or continuous and in both cases, the enumeration of solutions is impossible. This thesis work intends to give an algorithmic answer to this question by providing mathematical programming and dynamic programming approaches to find optimal solutions when the aggregating function is the Choquet integral, one of the most expressive aggregator. This thesis provides also a mechanism design analysis of multiagent problems where the aggregating function is non-affine as it is the case for the Choquet integral

La technologie haut débit des puces à ADN permet de visualiser simultanément le niveau d'expression de plusieurs milliers de gènes ou groupe de gènes dans des conditions différentes Cette technologie haut débit génère une grande diversité de données qui implique un important travail d'analyse. Une de ces problématiques, concerne la recherche de règles d'associations qui consiste à extraire un ensemble de formules logiques conditionnelles permettant de déduire la valeur d'un attribut but à partir des valeurs d'autres attributs. La recherche de règles d'association peut être vue comme un problème d'optimisation puisque l'on recherche les règles optimisant un certain critère. La combinatoire associée au problème est très importante. Ceci ne permet pas d'utiliser pour des problèmes de grandes tailles (comme c'est le cas ici) des algorithmes exactes d'énumération. Il est donc nécessaire d'avoir recours à des heuristiques telles que par exemple les métaheuristiques. Le contexte de la thèse étant la résolution d'un problème d'optimisation combinatoire multi-objectif pour l'analyse de données obtenues à l'aide de la technologie des puces à ADN, nous nous focalisons sur la modélisation et la résolution multi-objectif du problème de recherche de règles d'association. Puis nous nous intéressons à l'apport des méthodes d'optimisation approchées, à savoir les algorithmes génétiques (AG) Nous avons proposé un algorithme génétique permettant de traiter des bases de données relatives à des expérimentations sur puces à ADN. Cet algorithme possède un codage et des opérateurs adaptés à la recherche de règles d'association et des mécanismes multi-objectif ont été implémentés. Nous avons mis en place un mécanisme adaptatif pour pouvoir appliquer plusieurs mutations selon l'évolution de l'algorithme et adapter leur taux d'application en fonction de l'amélioration apportée par chacun d'eux. Nous avons proposé une approche parallèle développée pour le problème de recherche de règles, dans laquelle différents algorithmes génétiques coopèrent. Plusieurs approches coopératives ont été proposées. Nous avons montré à la fois l'apport du parallélisme et l'apport de la coopération entre méthodes de différents types.

Les travaux effectués durant cette thèse s'inscrivent dans le cadre de la théorie de la décision algorithmique, domaine au carrefour de la théorie de la décision, de la recherche opérationnelle et de l'intelligence artificielle. Cette thèse vise à concevoir des méthodes d'optimisation interactive fondées sur l'élicitation incrémentale des préférences pour la prise de décision multicritère, multi-agents ou dans le risque. Nous nous intéressons plus précisément à l'élicitation incrémentale des paramètres de fonctions d'agrégation qui consiste à alterner questions préférentielles permettant de réduire l'incertitude concernant la valeur des paramètres modélisant les préférences particulières du décideur, et exploration de l'espace des solutions, jusqu'à pouvoir déterminer une recommandation de bonne qualité. L'intérêt d'alterner phases de questions et phases d'exploration est double: d'une part, les informations préférentielles récoltées durant une phase d'élicitation permettent de mieux focaliser la phase d'exploration suivante sur les solutions les plus intéressantes pour le décideur; d'autre part, l'exploration de l'espace des solutions permet de guider le choix des questions de manière à ce qu'elles soient les plus informatives possible. Nous introduisons dans cette thèse des méthodes d'élicitation dans différents contextes. Dans un premier temps, nous nous intéressons à des fonctions d'agrégation non-linéaires pour modéliser les préférences du décideur sur un ensemble combinatoire d'alternatives. Nous nous intéressons ensuite à la conception de méthodes d'élicitation prenant en compte la possibilité de la présence d'incohérences dans les réponses du décideur, d'abord sur domaine explicite, puis sur domaine combinatoire. Les algorithmes introduits sont génériques et peuvent s'appliquer à différents problèmes de choix multi-objectifs
This thesis work falls within the area of algorithmic decision theory, a research domain at the crossroad of decision theory, operations research and artificial intelligence. The aim is to produce interactive optimization methods based on incremental preference elicitation in decision problems involving several criteria, opinions of agents or scenarios. Preferences are represented by general decision models whose parameters must be adapted to each decision problem and each decision maker. Our methods interleave the elicitation of parameters and the exploration of the solution space in order to determine the optimal choice for the decision maker. The idea behind this is to use information provided by the elicitation to guide the exploration of the solution space and vice versa. In this thesis, we introduce new incremental elicitation methods for decision making in different contexts : first for decision making in combinatorial domains when the decision models are non-linear, and then in a setting where one takes into account the possibility of inconsistencies in the answers of te decision maker. All the algorithms that we introduce are general and can be applied to a wide range of multiobjective decision problems

On s'attache dans cette thèse à plusieurs aspects liés à la résolution de problèmes multi-objectifs, sans se limiter au cas biobjectif. Nous considérons la résolution exacte, dans le sens de la détermination de l'ensemble des points non dominés, ainsi que la résolution approchée dans laquelle on cherche une approximation de cet ensemble dont la qualité est garantie a priori.Nous nous intéressons d'abord au problème de la détermination d'une représentation explicite de la région de recherche. La région de recherche, étant donné un ensemble de points réalisables connus, exclut la partie de l'espace des objectifs que dominent ces points et constitue donc la partie de l'espace des objectifs où les efforts futurs doivent être concentrés dans la perspective de déterminer tous les points non dominés.Puis nous considérons le recours aux algorithmes de séparation et évaluation ainsi qu'aux algorithmes de ranking afin de proposer une nouvelle méthode hybride de détermination de l'ensemble des points non dominés. Nous montrons que celle-ci peut également servir à obtenir une approximation de l'ensemble des points non dominés. Cette méthode est implantée pour le problème de l'arbre couvrant de poids minimal. Les quelques propriétés de ce problème que nous passons en revue nous permettent de spécialiser certaines procédures et d'intégrer des prétraitements spécifiques. L'intérêt de cette approche est alors soutenu à l'aide de résultats expérimentaux
This thesis deals with several aspects related to solving multi-objective problems, without restriction to the bi-objective case. We consider exact solving, which generates the nondominated set, and approximate solving, which computes an approximation of the nondominated set with a priori guarantee on the quality.We first consider the determination of an explicit representation of the search region. The search region, defined with respect to a set of known feasible points, excludes from the objective space the part which is dominated by these points. Future efforts to find all nondominated points should therefore be concentrated on the search region.Then we review branch and bound and ranking algorithms and we propose a new hybrid approach for the determination of the nondominated set. We show how the proposed method can be adapted to generate an approximation of the nondominated set. This approach is instantiated on the minimum spanning tree problem. We review several properties of this problem which enable us to specialize some procedures of the proposed approach and integrate specific preprocessing rules. This approach is finally supported through experimental results