@inproceedings{48873, abstract = {{Despite the intrinsic hardness of the Traveling Salesperson Problem (TSP) heuristic solvers, e.g., LKH+restart and EAX+restart, are remarkably successful in generating satisfactory or even optimal solutions. However, the reasons for their success are not yet fully understood. Recent approaches take an analytical viewpoint and try to identify instance features, which make an instance hard or easy to solve. We contribute to this area by generating instance sets for couples of TSP algorithms A and B by maximizing/minimizing their performance difference in order to generate instances which are easier to solve for one solver and much harder to solve for the other. This instance set offers the potential to identify key features which allow to distinguish between the problem hardness classes of both algorithms.}}, author = {{Bossek, Jakob and Trautmann, Heike}}, booktitle = {{Learning and Intelligent Optimization}}, editor = {{Festa, Paola and Sellmann, Meinolf and Vanschoren, Joaquin}}, isbn = {{978-3-319-50349-3}}, keywords = {{Algorithm selection, Feature selection, Instance hardness, TSP}}, pages = {{48–59}}, publisher = {{Springer International Publishing}}, title = {{{Evolving Instances for Maximizing Performance Differences of State-of-the-Art Inexact TSP Solvers}}}, doi = {{10.1007/978-3-319-50349-3_4}}, year = {{2016}}, } @inproceedings{48874, abstract = {{State of the Art inexact solvers of the NP-hard Traveling Salesperson Problem TSP are known to mostly yield high-quality solutions in reasonable computation times. With the purpose of understanding different levels of instance difficulties, instances for the current State of the Art heuristic TSP solvers LKH+restart and EAX+restart are presented which are evolved using a sophisticated evolutionary algorithm. More specifically, the performance differences of the respective solvers are maximized resulting in instances which are easier to solve for one solver and much more difficult for the other. Focusing on both optimization directions, instance features are identified which characterize both types of instances and increase the understanding of solver performance differences.}}, author = {{Bossek, Jakob and Trautmann, Heike}}, booktitle = {{Proceedings of the XV International Conference of the Italian Association for Artificial Intelligence on Advances in Artificial Intelligence - Volume 10037}}, isbn = {{978-3-319-49129-5}}, keywords = {{Combinatorial optimization, Instance hardness, Metaheuristics, Transportation, TSP}}, pages = {{3–12}}, publisher = {{Springer-Verlag}}, title = {{{Understanding Characteristics of Evolved Instances for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference}}}, doi = {{10.1007/978-3-319-49130-1_1}}, year = {{2016}}, } @inproceedings{46365, abstract = {{Despite the intrinsic hardness of the Traveling Salesperson Problem (TSP) heuristic solvers, e.g., LKH+restart and EAX+restart, are remarkably successful in generating satisfactory or even optimal solutions. However, the reasons for their success are not yet fully understood. Recent approaches take an analytical viewpoint and try to identify instance features, which make an instance hard or easy to solve. We contribute to this area by generating instance sets for couples of TSP algorithms A and B by maximizing/minimizing their performance difference in order to generate instances which are easier to solve for one solver and much harder to solve for the other. This instance set offers the potential to identify key features which allow to distinguish between the problem hardness classes of both algorithms.}}, author = {{Bossek, Jakob and Trautmann, Heike}}, booktitle = {{Learning and Intelligent Optimization}}, editor = {{Festa, P and Sellmann, M and Vanschoren, J}}, isbn = {{978-3-319-50348-6}}, pages = {{48–59}}, publisher = {{Springer International Publishing}}, title = {{{Evolving Instances for Maximizing Performance Differences of State-of-The-Art Inexact TSP Solvers}}}, doi = {{10.1007/978-3-319-50349-3_4}}, volume = {{10079}}, year = {{2016}}, } @inproceedings{46366, abstract = {{State of the Art inexact solvers of the NP-hard Traveling Salesperson Problem (TSP) are known to mostly yield high-quality solutions in reasonable computation times. With the purpose of understanding different levels of instance difficulties, instances for the current State of the Art heuristic TSP solvers LKH+restart and EAX+restart are presented which are evolved using a sophisticated evolutionary algorithm. More specifically, the performance differences of the respective solvers are maximized resulting in instances which are easier to solve for one solver and much more difficult for the other. Focusing on both optimization directions, instance features are identified which characterize both types of instances and increase the understanding of solver performance differences.}}, author = {{Bossek, Jakob and Trautmann, Heike}}, booktitle = {{AI*IA 2016 Advances in Artificial Intelligence}}, editor = {{Adorni, G and Cagnoni, S and Gori, M and Maratea, M}}, isbn = {{978-3-319-49129-5}}, pages = {{3–12}}, publisher = {{Springer}}, title = {{{Understanding Characteristics of Evolved Instances for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference}}}, doi = {{10.1007/978-3-319-49130-1_1}}, volume = {{10037}}, year = {{2016}}, } @inproceedings{46373, abstract = {{The need for automatic methods of topic discovery in the Internet grows exponentially with the amount of available textual information. Nowadays it becomes impossible to manually read even a small part of the information in order to reveal the underlying topics. Social media provide us with a great pool of user generated content, where topic discovery may be extremely useful for businesses, politicians, researchers, and other stakeholders. However, conventional topic discovery methods, which are widely used in large text corpora, face several challenges when they are applied in social media and particularly in Twitter – the most popular microblogging platform. To the best of our knowledge no comprehensive overview of these challenges and of the methods dedicated to address these challenges does exist in IS literature until now. Therefore, this paper provides an overview of these challenges, matching methods and their expected usefulness for social media analytics.}}, author = {{Chinnov, Andrey and Kerschke, Pascal and Meske, Christian and Stieglitz, Stefan and Trautmann, Heike}}, booktitle = {{Proceedings of the 20$^th$ Americas Conference on Information Systems (AMCIS ’15)}}, isbn = {{978-0-9966831-0-4}}, pages = {{1–10}}, title = {{{An Overview of Topic Discovery in Twitter Communication through Social Media Analytics}}}, year = {{2015}}, } @inproceedings{46375, abstract = {{In single-objective optimization different optimization strategies exist depending on the structure and characteristics of the underlying problem. In particular, the presence of so-called funnels in multimodal problems offers the possibility of applying techniques exploiting the global structure of the function. The recently proposed Exploratory Landscape Analysis approach automatically identifies problem characteristics based on a moderately small initial sample of the objective function and proved to be effective for algorithm selection problems in continuous black-box optimization. In this paper, specific features for detecting funnel structures are introduced and combined with the existing ones in order to classify optimization problems regarding the funnel property. The effectiveness of the approach is shown by experiments on specifically generated test instances and validation experiments on standard benchmark problems.}}, author = {{Kerschke, Pascal and Preuss, Mike and Wessing, Simon and Trautmann, Heike}}, booktitle = {{Proceedings of the Genetic and Evolutionary Computation Conference (GECCO ’15)}}, editor = {{Silva, Sara}}, isbn = {{978-1-4503-3472-3}}, pages = {{265–272}}, publisher = {{ACM}}, title = {{{Detecting Funnel Structures by Means of Exploratory Landscape Analysis}}}, doi = {{10.1145/2739480.2754642}}, year = {{2015}}, } @inproceedings{46376, abstract = {{We investigate per-instance algorithm selection techniques for solving the Travelling Salesman Problem (TSP), based on the two state-of-the-art inexact TSP solvers, LKH and EAX. Our comprehensive experiments demonstrate that the solvers exhibit complementary performance across a diverse set of instances, and the potential for improving the state of the art by selecting between them is significant. Using TSP features from the literature as well as a set of novel features, we show that we can capitalise on this potential by building an efficient selector that achieves significant performance improvements in practice. Our selectors represent a significant improvement in the state-of-the-art in inexact TSP solving, and hence in the ability to find optimal solutions (without proof of optimality) for challenging TSP instances in practice.}}, author = {{Kotthoff, Lars and Kerschke, Pascal and Hoos, Holger and Trautmann, Heike}}, booktitle = {{Learning and Intelligent Optimization}}, editor = {{Dhaenens, Clarisse and Jourdan, Laetitia and Marmion, Marie-Eléonore}}, isbn = {{978-3-319-19084-6}}, pages = {{202–217}}, publisher = {{Springer International Publishing}}, title = {{{Improving the State of the Art in Inexact TSP Solving Using Per-Instance Algorithm Selection}}}, year = {{2015}}, } @article{46379, abstract = {{In multiobjective optimization, set-based performance indicators are commonly used to assess the quality of a Pareto front approximation. Based on the scalarization obtained by these indicators, a performance comparison of multiobjective optimization algorithms becomes possible. The R2 and the Hypervolume (HV) indicator represent two recommended approaches which have shown a correlated behavior in recent empirical studies. Whereas the HV indicator has been comprehensively analyzed in the last years, almost no studies on the R2 indicator exist. In this extended version of our previous conference paper, we thus perform a comprehensive investigation of the properties of the R2 indicator in a theoretical and empirical way. The influence of the number and distribution of the weight vectors on the optimal distribution of µ solutions is analyzed. Based on a comparative analysis, specific characteristics and differences of the R2 and HV indicator are presented. Furthermore, the R2 indicator is integrated into an indicator-based steady-state evolutionary multiobjective optimization algorithm (EMOA). It is shown that the so-called R2-EMOA can accurately approximate the optimal distribution of µ solutions regarding R2.}}, author = {{Brockhoff, D and Wagner, T and Trautmann, Heike}}, journal = {{Evolutionary Computation Journal}}, number = {{3}}, pages = {{369–395}}, title = {{{R2 Indicator Based Multiobjective Search}}}, doi = {{10.1162/EVCO_a_00135}}, volume = {{23}}, year = {{2015}}, } @inproceedings{46374, abstract = {{We consider a routing problem for a single vehicle serving customer Locations in the course of time. A subset of these customers must necessarily be served, while the complement of this subset contains dynamic customers which request for service over time, and which do not necessarily need to be served. The decision maker’s conflicting goals are serving as many customers as possible as well as minimizing total travel distance. We solve this bi-objective Problem with an evolutionary multi-objective algorithm in order to provide an a-posteriori evaluation tool for enabling decision makers to assess the single objective solution strategies that they actually use in real-time. We present the modifications to be applied to the evolutionary multi-objective algorithm NSGA2 in order to solve the routing problem, we describe a number of real-time single-objective solution strategies, and we finally use the gained efficient trade-off solutions of NSGA2 to exemplarily evaluate the real-time strategies. Our results show that the evolutionary multi-objective approach is well-suited to generate benchmarks for assessing dynamic heuristic strategies. Our findings point into future directions for designing dynamic multi-objective approaches for the vehicle routing problem with time windows. }}, author = {{Grimme, C and Meisel, S and Trautmann, Heike and Rudolph, G and Wölck, M}}, booktitle = {{Proceedings of the European Conference On Information Systems}}, title = {{{Multi-Objective Analysis of Approaches to Dynamic Routing Of a Vehicle}}}, year = {{2015}}, } @article{46380, abstract = {{We present methods to answer two basic questions that arise when benchmarking optimization algorithms. The first one is: which algorithm is the "best" one? and the second one is: which algorithm should I use for my real-world problem? Both are connected and neither is easy to answer. We present a theoretical framework for designing and analyzing the raw data of such benchmark experiments. This represents a first step in answering the aforementioned questions. The 2009 and 2010 BBOB benchmark results are analyzed by means of this framework and we derive insight regarding the answers to the two questions. Furthermore, we discuss how to properly aggregate rankings from algorithm evaluations on individual problems into a consensus, its theoretical background and which common pitfalls should be avoided. Finally, we address the grouping of test problems into sets with similar optimizer rankings and investigate whether these are reflected by already proposed test problem characteristics, finding that this is not always the case.}}, author = {{Mersmann, O and Preuss, M and Trautmann, Heike and Bischl, B and Weihs, C}}, journal = {{Evolutionary Computation Journal}}, number = {{1}}, pages = {{161–185}}, title = {{{Analyzing the BBOB Results by Means of Benchmarking Concepts}}}, volume = {{23}}, year = {{2015}}, } @inproceedings{48838, abstract = {{The majority of algorithms can be controlled or adjusted by parameters. Their values can substantially affect the algorithms’ performance. Since the manual exploration of the parameter space is tedious – even for few parameters – several automatic procedures for parameter tuning have been proposed. Recent approaches also take into account some characteristic properties of the problem instances, frequently termed instance features. Our contribution is the proposal of a novel concept for feature-based algorithm parameter tuning, which applies an approximating surrogate model for learning the continuous feature-parameter mapping. To accomplish this, we learn a joint model of the algorithm performance based on both the algorithm parameters and the instance features. The required data is gathered using a recently proposed acquisition function for model refinement in surrogate-based optimization: the profile expected improvement. This function provides an avenue for maximizing the information required for the feature-parameter mapping, i.e., the mapping from instance features to the corresponding optimal algorithm parameters. The approach is validated by applying the tuner to exemplary evolutionary algorithms and problems, for which theoretically grounded or heuristically determined feature-parameter mappings are available.}}, author = {{Bossek, Jakob and Bischl, Bernd and Wagner, Tobias and Rudolph, Günter}}, booktitle = {{Proceedings of the Genetic and Evolutionary Computation Conference}}, isbn = {{978-1-4503-3472-3}}, keywords = {{evolutionary algorithms, model-based optimization, parameter tuning}}, pages = {{1319–1326}}, publisher = {{Association for Computing Machinery}}, title = {{{Learning Feature-Parameter Mappings for Parameter Tuning via the Profile Expected Improvement}}}, doi = {{10.1145/2739480.2754673}}, year = {{2015}}, } @inproceedings{48887, abstract = {{We evaluate the performance of a multi-objective evolutionary algorithm on a class of dynamic routing problems with a single vehicle. In particular we focus on relating algorithmic performance to the most prominent characteristics of problem instances. The routing problem considers two types of customers: mandatory customers must be visited whereas optional customers do not necessarily have to be visited. Moreover, mandatory customers are known prior to the start of the tour whereas optional customers request for service at later points in time with the vehicle already being on its way. The multi-objective optimization problem then results as maximizing the number of visited customers while simultaneously minimizing total travel time. As an a-posteriori evaluation tool, the evolutionary algorithm aims at approximating the related Pareto set for specifically designed benchmarking instances differing in terms of number of customers, geographical layout, fraction of mandatory customers, and request times of optional customers. Conceptional and experimental comparisons to online heuristic procedures are provided.}}, author = {{Meisel, Stephan and Grimme, Christian and Bossek, Jakob and Wölck, Martin and Rudolph, Günter and Trautmann, Heike}}, booktitle = {{Proceedings of the Genetic and Evolutionary Computation Conference }}, isbn = {{978-1-4503-3472-3}}, keywords = {{combinatorial optimization, metaheuristics, multi-objective optimization, online algorithms, transportation}}, pages = {{425–432}}, publisher = {{Association for Computing Machinery}}, title = {{{Evaluation of a Multi-Objective EA on Benchmark Instances for Dynamic Routing of a Vehicle}}}, doi = {{10.1145/2739480.2754705}}, year = {{2015}}, } @inproceedings{46377, abstract = {{We evaluate the performance of a multi-objective evolutionary algorithm on a class of dynamic routing problems with a single vehicle. In particular we focus on relating algorithmic performance to the most prominent characteristics of problem instances. The routing problem considers two types of customers: mandatory customers must be visited whereas optional customers do not necessarily have to be visited. Moreover, mandatory customers are known prior to the start of the tour whereas optional customers request for service at later points in time with the vehicle already being on its way. The multi-objective optimization problem then results as maximizing the number of visited customers while simultaneously minimizing total travel time. As an a-posteriori evaluation tool, the evolutionary algorithm aims at approximating the related Pareto set for specifically designed benchmarking instances differing in terms of number of customers, geographical layout, fraction of mandatory customers, and request times of optional customers. Conceptional and experimental comparisons to online heuristic procedures are provided.}}, author = {{Meisel, Stephan and Grimme, Christian and Bossek, Jakob and Wölck, Martin and Rudolph, Guenter and Trautmann, Heike}}, booktitle = {{Proceedings of the Genetic and Evolutionary Computation Conference (GECCO ’15)}}, isbn = {{978-1-4503-3472-3}}, pages = {{425–432}}, title = {{{Evaluation of a Multi-Objective EA on Benchmark Instances for Dynamic Routing of a Vehicle}}}, doi = {{10.1145/2739480.2754705}}, year = {{2015}}, } @inbook{46381, abstract = {{Exploratory Landscape Analysis is an effective and sophisticated approach to characterize the properties of continuous optimization problems. The overall aim is to exploit this knowledge to give recommendations of the individually best suited algorithm for unseen optimization problems. Recent research revealed a high potential of this methodology in this respect based on a set of well-defined, computable features which only requires a quite small sample of function evaluations. In this paper, new features based on the cell mapping concept are introduced and shown to improve the existing feature set in terms of predicting expert-designed high-level properties, such as the degree of multimodality or the global structure, for 2-dimensional single objective optimization problems.}}, author = {{Kerschke, Pascal and Preuss, Mike and Hernández, Carlos and Schütze, Oliver and Sun, Jian-Qiao and Grimme, Christian and Rudolph, Günter and Bischl, Bernd and Trautmann, Heike}}, booktitle = {{EVOLVE — A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation V}}, editor = {{Tantar, Alexandru-Adrian and Tantar, Emilia and Sun, Jian-Qiao and Zhang, Wei and Ding, Qian and Schütze, Oliver and Emmerich, Michael T M and Legrand, Pierrick and Del, Moral Pierre and Coello, Coello Carlos A}}, isbn = {{978-3-319-07493-1}}, pages = {{115–131}}, publisher = {{Springer International Publishing}}, title = {{{Cell Mapping Techniques for Exploratory Landscape Analysis}}}, doi = {{10.1007/978-3-319-07494-8_9}}, volume = {{288}}, year = {{2014}}, } @inbook{46382, abstract = {{The incorporation of expert knowledge into multiobjective optimization is an important issue which in this paper is reflected in terms of an aspiration set consisting of multiple reference points. The behaviour of the recently introduced evolutionary multiobjective algorithm AS-EMOA is analysed in detail and comparatively studied for bi-objective optimization problems w.r.t. R-NSGA2 and a respective variant. It will be shown that the averaged Hausdorff distance, integrated into AS-EMOA, is an efficient means to accurately approximate the desired aspiration set.}}, author = {{Rudolph, G and Schütze, O and Grimme, C and Trautmann, Heike}}, booktitle = {{EVOLVE — A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation V}}, editor = {{Tantar, A and Tantar, E and Sun, J and Zhang, W and Ding, Q and Schütze, O and Emmerich, M and Legrand, P and Del, Moral P and Coello, Coello CA}}, isbn = {{978-3-319-07493-1}}, pages = {{261–273}}, publisher = {{Springer International Publishing}}, title = {{{A Multiobjective Evolutionary Algorithm Guided by Averaged Hausdorff Distance to Aspiration Sets}}}, doi = {{10.1007/978-3-319-07494-8_18}}, volume = {{288}}, year = {{2014}}, } @inproceedings{46383, abstract = {{We propose an evolutionary multiobjective algorithm that approximates multiple reference points (the aspiration set) in a single run using the concept of the averaged Hausdorff distance.}}, author = {{Rudolph, Günter and Grimme, Christian and Schütze, Oliver and Trautmann, Heike}}, booktitle = {{Proceedings of the Learning and Intelligent OptimizatioN Conference (LION 8)}}, pages = {{153–156}}, publisher = {{Springer}}, title = {{{An Aspiration Set EMOA Based on Averaged Hausdorff Distances}}}, volume = {{8426}}, year = {{2014}}, } @inproceedings{46384, abstract = {{Multimodal optimization requires maintenance of a good search space coverage and approximation of several optima at the same time. We analyze two constitutive optimization algorithms and show that in many cases, a phase transition occurs at some point, so that either diversity collapses or optimization stagnates. But how to derive suitable stopping criteria for multimodal optimization? Experimental results indicate that an algorithm’s population contains sufficient information to estimate the point in time when several performance indicators reach their optimum. Thus, stopping criteria are formulated based on summary characteristics employing objective values and mutation strength.}}, author = {{Wessing, S and Preuss, M and Trautmann, Heike}}, booktitle = {{Proceedings of the Parallel Problem Solving from Nature — PPSN XIII}}, editor = {{Bartz-Beielstein, T and Branke, J and Filipic, B and Smith, J}}, pages = {{141–150}}, publisher = {{Springer}}, title = {{{Stopping Criteria for Multimodal Optimization}}}, doi = {{10.1007/978-3-319-10762-2_14}}, volume = {{8672}}, year = {{2014}}, } @inbook{46385, abstract = {{In many applications one is faced with the problem that multiple objectives have to be optimized at the same time. Since typically the solution set of such multi-objective optimization problems forms a manifold which cannot be computed analytically, one is in many cases interested in a suitable finite size approximation of this set. One widely used approach is to find a representative set that maximizes the dominated hypervolume that is defined by the images in objective space of these solutions and a given reference point. In this paper, we propose a new point-wise iterative search procedure, Hypervolume Directed Search (HVDS), that aims to increase the hypervolume of a given point in an archive for bi-objective unconstrained optimization problems. We present the HVDS both as a standalone algorithm and as a local searcher within a specialized evolutionary algorithm. Numerical results confirm the strength of the novel approach.}}, author = {{Sosa, Hernández V and Schütze, O and Rudolph, G and Trautmann, Heike}}, booktitle = {{EVOLVE — A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation IV}}, editor = {{Emmerich, M and Deutz, A and Schuetze, O and Bäck, T and Tantar, A and Moral, PD and Legrand, P and Bouvry, P and Coello, CA}}, isbn = {{978-3-319-01127-1}}, pages = {{189–205}}, publisher = {{Springer International Publishing}}, title = {{{The Directed Search Method for Pareto Front Approximations with Maximum Dominated Hypervolume}}}, doi = {{10.1007/978-3-319-01128-8_13}}, volume = {{227}}, year = {{2013}}, } @inbook{46386, abstract = {{The averaged Hausdorff distance Δ p is a performance indicator in multi-objective evolutionary optimization which simultaneously takes into account proximity to the true Pareto front and uniform spread of solutions. Recently, the multi-objective evolutionary algorithm Δ p -EMOA was introduced which successfully generates evenly spaced Pareto front approximations for bi-objective problems by integrating an external archiving strategy into the SMS-EMOA based on Δ p . In this work a conceptual generalization of the Δ p -EMOA for higher objective space dimensions is presented and experimentally compared to state-of-the art EMOA as well as specialized EMOA variants on three-dimensional optimization problems.}}, author = {{Trautmann, Heike and Rudolph, G and Dominguez-Medina, C and Schütze, O}}, booktitle = {{EVOLVE — A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation II}}, editor = {{Schütze, O and Coello, Coello CA and Tantar, A and Tantar, E and Bouvry, P and Del, Moral P and Legrand, P}}, isbn = {{978-3-642-31518-3}}, pages = {{89–105}}, publisher = {{Springer Berlin Heidelberg}}, title = {{{Finding Evenly Spaced Pareto Fronts for Three-Objective Optimization Problems}}}, doi = {{10.1007/978-3-642-31519-0_6}}, volume = {{175}}, year = {{2013}}, } @inproceedings{46388, abstract = {{Understanding the behaviour of well-known algorithms for classical NP-hard optimisation problems is still a difficult task. With this paper, we contribute to this research direction and carry out a feature based comparison of local search and the well-known Christofides approximation algorithm for the Traveling Salesperson Problem. We use an evolutionary algorithm approach to construct easy and hard instances for the Christofides algorithm, where we measure hardness in terms of approximation ratio. Our results point out important features and lead to hard and easy instances for this famous algorithm. Furthermore, our cross-comparison gives new insights on the complementary benefits of the different approaches.}}, author = {{Nallaperuma, Samadhi and Wagner, Markus and Neumann, Frank and Bischl, Bernd and Mersmann, Olaf and Trautmann, Heike}}, booktitle = {{Proceedings of the Twelfth Workshop on Foundations of Genetic Algorithms XII}}, isbn = {{9781450319904}}, keywords = {{approximation algorithms, local search, traveling salesperson problem, feature selection, prediction, classification}}, pages = {{147–160}}, publisher = {{Association for Computing Machinery}}, title = {{{A Feature-Based Comparison of Local Search and the Christofides Algorithm for the Travelling Salesperson Problem}}}, doi = {{10.1145/2460239.2460253}}, year = {{2013}}, }