562 research outputs found
Parallel Universes: Multi-Criteria Optimization
No full textIn this paper parallel universes are defined by their relation to multi-criteria optimization combined with an explicit
or implicit link for the unambiguous identification of an optimum. As an explicit link function the desirability index
is introduced. Desirabilities are also used for restricting the Pareto set to desired parts
Automated Algorithm Selection and Configuration (Dagstuhl Seminar 16412)
No full textThis report documents the programme and the outcomes of Dagstuhl Seminar 16412 "Automated Algorithm Selection and Configuration", which was held October 9--14, 2016 and attended by 34 experts from 10 countries. Research on automated algorithm selection and configuration has lead to some of the most impressive successes within the broader area of empirical algorithmics, and has proven to be highly relevant to industrial applications. Specifically, high-performance algorithms for cnp-hard problems, such as propositional satisfiability (SAT) and mixed integer programming (MIP), are known to have a huge impact on sectors such as manufacturing, logistics, healthcare, finance, agriculture and energy systems, and algorithm selection and configuration techniques have been demonstrated to achieve substantial improvements in the performance of solvers for these problems. Apart from creating synergy through close interaction between the world's leading groups in the area, the seminar pursued two major goals: to promote and develop deeper understanding of the behaviour of algorithm selection and configuration techniques and to lay the groundwork for further improving their efficacy. Towards these ends, the organisation team brought together a group of carefully chosen researchers with strong expertise in computer science, statistics, mathematics, economics and engineering; a particular emphasis was placed on bringing together theorists, empiricists and experts from various application areas, with the goal of closing the gap between theory and practice
Local search and the traveling salesman problem: A feature-based characterization of problem hardness
No full textWith this paper we contribute to the understanding of the success of 2-opt based local search algorithms for solving the traveling salesman problem (TSP). Although 2-opt is widely used in practice, it is hard to understand its success from a theoretical perspective. We take a statistical approach and examine the features of TSP instances that make the problem either hard or easy to solve. As a measure of problem difficulty for 2-opt we use the approximation ratio that it achieves on a given instance. Our investigations point out important features that make TSP instances hard or easy to be approximated by 2-opt. © 2012 Springer-Verlag.Olaf Mersmann, Bernd Bischl, Jakob Bossek, Heike Trautmann, Markus Wagner and Frank Neuman
Towards Decision Support in Dynamic Bi-Objective Vehicle Routing
No full textPart of: IEEE WCCI 2020 is the world’s largest technical event on computational intelligence, featuring the three flagship conferences of the IEEE Computational Intelligence Society (CIS) under one roof: The 2020 International Joint Conference on Neural Networks (IJCNN 2020); the 2020 IEEE International Conference on Fuzzy Systems (FUZZ-IEEE 2020); and the 2020 IEEE Congress on Evolutionary Computation (IEEE CEC 2020).We consider a dynamic bi-objective vehicle routing problem, where a subset of customers ask for service over time. Therein, the distance traveled by a single vehicle and the number of unserved dynamic requests is minimized by a dynamic evolutionary multi-objective algorithm (DEMOA), which operates on discrete time windows (eras). A decision is made at each era by a decision-maker, thus any decision depends on irreversible decisions made in foregoing eras. To understand effects of sequences of decision-making and interactions/ dependencies between decisions made, we conduct a series of experiments. More precisely, we fix a set of decision-maker preferences D and the number of eras nt and analyze all jDjnt combinations of decision-maker options. We find that for random uniform instances (a) the final selected solutions mainly depend on the final decision and not on the decision history, (b) solutions are quite robust with respect to the number of unvisited dynamic customers, and (c) solutions of the dynamic approach can even dominate solutions obtained by a clairvoyant EMOA. In contrast, for instances with clustered customers, we observe a strong dependency on decision-making history as well as more variance in solution diversity.Jakob Bossek, Christian Grimmey, Günter Rudolph and Heike Trautmann
Deep Learning as a Competitive Feature-Free Approach for Automated Algorithm Selection on the Traveling Salesperson Problem
No full textIn this work we focus on the well-known Euclidean Traveling Salesperson Problem (TSP) and two highly competitive inexact heuristic TSP solvers, EAX and LKH, in the context of per-instance algorithm selection (AS). We evolve instances with 1 000 nodes where the solvers show strongly different performance profiles. These instances serve as a basis for an exploratory study on the identification of well-discriminating problem characteristics (features). Our results in a nutshell: we show that even though (1) promising features exist, (2) these are in line with previous results from the literature, and (3) models trained with these features are more accurate than models adopting sophisticated feature selection methods, the advantage is not close to the virtual best solver in terms of penalized average runtime and so is the performance gain over the single best solver. However, we show that a feature-free deep neural network based approach solely based on visual representation of the instances already matches classical AS model results and thus shows huge potential for future studies.Moritz Seiler, Janina Pohl, Jakob Bossek, Pascal Kerschke, and Heike Trautman
Multi-objective Optimization for Liner Shipping Fleet Repositioning
No full textTierney K, Handali J, Grimme C, Trautmann H. Multi-objective Optimization for Liner Shipping Fleet Repositioning. In: Trautmann H, Rudolph G, Klamroth K, et al., eds. Evolutionary Multi-Criterion Optimization : 9th International Conference, EMO 2017, Münster, Germany, March 19-22, 2017, Proceedings. Lecture Notes in Computer Science. Vol 10173. Cham: Springer International Publishing; 2017: 622-638
Learned Features vs. Classical ELA on Affine BBOB Functions
No full textInternational audienceAutomated algorithm selection has proven to be effective to improve optimization performance by using machine learning to select the best-performing algorithm for the particular problem being solved. However, doing so requires the ability to describe the landscape of optimization problems using numerical features, which is a difficult task.In this work, we analyze the synergies and complementarity of recently proposed feature sets TransOpt and Deep ELA, which are based on deeplearning, and compare them to the commonly used classical ELA features. We analyze the correlation between the feature sets as well as how well one set can predict the other. We show that while the feature sets contain some shared information, each also contains important unique information. Further, we compare and benchmark the different feature sets for the task of automated algorithm selection on the recently proposed affine black-box optimization problems. We find that while classical ELA is the best-performing feature set by itself, using selected features from a combination of all three feature sets provides superior performance, and all three sets individually substantially outperform the single best solver
Fitness landscape analysis of dimensionally-aware genetic programming featuring feynman equations
No full textGenetic programming is an often-used technique for symbolic regression: finding symbolic expressions that match data from an unknown function. To make the symbolic regression more efficient, one can also use dimensionally-aware genetic programming that constrains the physical units of the equation. Nevertheless, there is no formal analysis of how much dimensionality awareness helps in the regression process. In this paper, we conduct a fitness landscape analysis of dimensionally-aware genetic programming search spaces on a subset of equations from Richard Feynman’s well-known lectures. We define an initialisation procedure and an accompanying set of neighbourhood operators for conducting the local search within the physical unit constraints. Our experiments show that the added information about the variable dimensionality can efficiently guide the search algorithm. Still, further analysis of the differences between the dimensionally-aware and standard genetic programming landscapes is needed to help in the design of efficient evolutionary operators to be used in a dimensionally-aware regression.Accepted author manuscriptCyber Securit
Interaction between characters in Heike monogatari dialogues: language forms and functions
No full textThis thesis examines language aspects of interaction in dialogue passages of Heike monogatari (The Tale of the Heike, 1371) focusing on the role of language forms in characterization. The main goal of the present study is to assess the role of language variation and analyze how it participates in construction of asymmetries in social status and power between characters. Selected dialogue data is divided into two groups according to the participants and the dominant context: political interaction at court and interaction involving religious matters. Analysis of language forms in each dialogue draws on research by Japanese scholars and covers a wide range of linguistic phenomena such as sound changes, lexical choices, and markers of politeness. Linguistic findings are intended to supplement recent studies of the literary, socio-political, and religious contexts for early medieval narratives. By selecting a specific language style for each interacting character, the author(s) constructed particular images that have shaped audience’s perceptions of the characters. This study brings attention to language variation and clarifies how the socio-political status of characters, their interpersonal relations, and attitudes toward each other are encoded in the language of Heike monogatari dialogues. As such, this study is perhaps the first attempt in English to adopt a sociolinguistic approach to a Japanese pre-modern text, focusing on language properties and shifts in style in Heike monogatari.Arts, Faculty ofAsian Studies, Department ofGraduat
A novel feature-based approach to characterize algorithm performance for the traveling salesperson problem
No full textMeta-heuristics are frequently used to tackle NP-hard combinatorial optimization problems. With this paper we contribute to the understanding of the success of 2-opt based local search algorithms for solving the traveling salesperson problem (TSP). Although 2-opt is widely used in practice, it is hard to understand its success from a theoretical perspective. We take a statistical approach and examine the features of TSP instances that make the problem either hard or easy to solve. As a measure of problem difficulty for 2-opt we use the approximation ratio that it achieves on a given instance. Our investigations point out important features that make TSP instances hard or easy to be approximated by 2-opt.Olaf Mersmann, Bernd Bischl, Heike Trautmann, Markus Wagner, Jakob Bossek, Frank Neuman
- …
