@inproceedings{46339, abstract = {{Evolutionary algorithms have successfully been applied to evolve problem instances that exhibit a significant difference in performance for a given algorithm or a pair of algorithms inter alia for the Traveling Salesperson Problem (TSP). Creating a large variety of instances is crucial for successful applications in the blooming field of algorithm selection. In this paper, we introduce new and creative mutation operators for evolving instances of the TSP. We show that adopting those operators in an evolutionary algorithm allows for the generation of benchmark sets with highly desirable properties: (1) novelty by clear visual distinction to established benchmark sets in the field, (2) visual and quantitative diversity in the space of TSP problem characteristics, and (3) significant performance differences with respect to the restart versions of heuristic state-of-the-art TSP solvers EAX and LKH. The important aspect of diversity is addressed and achieved solely by the proposed mutation operators and not enforced by explicit diversity preservation.}}, author = {{Bossek, Jakob and Kerschke, Pascal and Neumann, Aneta and Wagner, Markus and Neumann, Frank and Trautmann, Heike}}, booktitle = {{Proceedings of the 15$^th$ ACM/SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA XV)}}, editor = {{Friedrich, Tobias and Doerr, Carola and Arnold, Dirk}}, pages = {{58–71}}, title = {{{Evolving Diverse TSP Instances by Means of Novel and Creative Mutation Operators}}}, doi = {{10.1145/3299904.3340307}}, year = {{2019}}, } @inproceedings{46338, abstract = {{We tackle a bi-objective dynamic orienteering problem where customer requests arise as time passes by. The goal is to minimize the tour length traveled by a single delivery vehicle while simultaneously keeping the number of dismissed dynamic customers to a minimum. We propose a dynamic Evolutionary Multi-Objective Algorithm which is grounded on insights gained from a previous series of work on an a-posteriori version of the problem, where all request times are known in advance. In our experiments, we simulate different decision maker strategies and evaluate the development of the Pareto-front approximations on exemplary problem instances. It turns out, that despite severely reduced computational budget and no oracle-knowledge of request times the dynamic EMOA is capable of producing approximations which partially dominate the results of the a-posteriori EMOA and dynamic integer linear programming strategies.}}, author = {{Bossek, Jakob and Grimme, Christian and Meisel, Stephan and Rudolph, Günter and Trautmann, Heike}}, booktitle = {{Evolutionary Multi-Criterion Optimization (EMO)}}, editor = {{Deb, Kalyanmoy and Goodman, Erik and Coello, Coello Carlos A. and Klamroth, Kathrin and Miettinen, Kaisa and Mostaghim, Sanaz and Reed, Patrick}}, isbn = {{978-3-030-12597-4}}, pages = {{516–528}}, publisher = {{Springer International Publishing}}, title = {{{Bi-Objective Orienteering: Towards a Dynamic Multi-Objective Evolutionary Algorithm}}}, doi = {{10.1007/978-3-030-12598-1_41}}, volume = {{11411}}, year = {{2019}}, } @inproceedings{46337, abstract = {{A multiobjective perspective onto common performance measures such as the PAR10 score or the expected runtime of single-objective stochastic solvers is presented by directly investigating the tradeoff between the fraction of failed runs and the average runtime. Multi-objective indicators operating in the bi-objective space allow for an overall performance comparison on a set of instances paving the way for instance-based automated algorithm selection techniques.}}, author = {{Bossek, Jakob and Trautmann, Heike}}, booktitle = {{Learning and Intelligent Optimization}}, editor = {{Battiti, R and Brunato, M and Kotsireas, I and Pardalos, P}}, isbn = {{978-3-030-05347-5}}, pages = {{215–219}}, publisher = {{Springer}}, title = {{{Multi-Objective Performance Measurement: Alternatives to PAR10 and Expected Running Time}}}, volume = {{11353}}, year = {{2019}}, } @inproceedings{48839, abstract = {{We analyze the effects of including local search techniques into a multi-objective evolutionary algorithm for solving a bi-objective orienteering problem with a single vehicle while the two conflicting objectives are minimization of travel time and maximization of the number of visited customer locations. Experiments are based on a large set of specifically designed problem instances with different characteristics and it is shown that local search techniques focusing on one of the objectives only improve the performance of the evolutionary algorithm in terms of both objectives. The analysis also shows that local search techniques are capable of sending locally optimal solutions to foremost fronts of the multi-objective optimization process, and that these solutions then become the leading factors of the evolutionary process.}}, author = {{Bossek, Jakob and Grimme, Christian and Meisel, Stephan and Rudolph, Günter and Trautmann, Heike}}, booktitle = {{Proceedings of the Genetic and Evolutionary Computation Conference}}, isbn = {{978-1-4503-5618-3}}, keywords = {{combinatorial optimization, metaheuristics, multi-objective optimization, orienteering, transportation}}, pages = {{585–592}}, publisher = {{Association for Computing Machinery}}, title = {{{Local Search Effects in Bi-Objective Orienteering}}}, doi = {{10.1145/3205455.3205548}}, year = {{2018}}, } @inproceedings{48867, abstract = {{Assessing the performance of stochastic optimization algorithms in the field of multi-objective optimization is of utmost importance. Besides the visual comparison of the obtained approximation sets, more sophisticated methods have been proposed in the last decade, e. g., a variety of quantitative performance indicators or statistical tests. In this paper, we present tools implemented in the R package ecr, which assist in performing comprehensive and sound comparison and evaluation of multi-objective evolutionary algorithms following recommendations from the literature.}}, author = {{Bossek, Jakob}}, booktitle = {{Proceedings of the Genetic and Evolutionary Computation Conference Companion}}, isbn = {{978-1-4503-5764-7}}, keywords = {{evolutionary optimization, performance assessment, software-tools}}, pages = {{1350–1356}}, publisher = {{Association for Computing Machinery}}, title = {{{Performance Assessment of Multi-Objective Evolutionary Algorithms with the R Package ecr}}}, doi = {{10.1145/3205651.3208312}}, year = {{2018}}, } @inproceedings{48885, abstract = {{Performance comparisons of optimization algorithms are heavily influenced by the underlying indicator(s). In this paper we investigate commonly used performance indicators for single-objective stochastic solvers, such as the Penalized Average Runtime (e.g., PAR10) or the Expected Running Time (ERT), based on exemplary benchmark performances of state-of-the-art inexact TSP solvers. Thereby, we introduce a methodology for analyzing the effects of (usually heuristically set) indicator parametrizations - such as the penalty factor and the method used for aggregating across multiple runs - w.r.t. the robustness of the considered optimization algorithms.}}, author = {{Kerschke, Pascal and Bossek, Jakob and Trautmann, Heike}}, booktitle = {{Proceedings of the Genetic and Evolutionary Computation Conference Companion}}, isbn = {{978-1-4503-5764-7}}, keywords = {{algorithm selection, optimization, performance measures, transportation, travelling salesperson problem}}, pages = {{1737–1744}}, publisher = {{Association for Computing Machinery}}, title = {{{Parameterization of State-of-the-Art Performance Indicators: A Robustness Study Based on Inexact TSP Solvers}}}, doi = {{10.1145/3205651.3208233}}, year = {{2018}}, } @book{48880, author = {{Grimme, Christian and Bossek, Jakob}}, isbn = {{978-3-658-21150-9}}, publisher = {{Springer Vieweg}}, title = {{{Einführung in die Optimierung - Konzepte, Methoden und Anwendungen}}}, doi = {{10.1007/978-3-658-21151-6}}, year = {{2018}}, } @article{48884, abstract = {{The Travelling Salesperson Problem (TSP) is one of the best-studied NP-hard problems. Over the years, many different solution approaches and solvers have been developed. For the first time, we directly compare five state-of-the-art inexact solvers\textemdash namely, LKH, EAX, restart variants of those, and MAOS\textemdash on a large set of well-known benchmark instances and demonstrate complementary performance, in that different instances may be solved most effectively by different algorithms. We leverage this complementarity to build an algorithm selector, which selects the best TSP solver on a per-instance basis and thus achieves significantly improved performance compared to the single best solver, representing an advance in the state of the art in solving the Euclidean TSP. Our in-depth analysis of the selectors provides insight into what drives this performance improvement.}}, author = {{Kerschke, Pascal and Kotthoff, Lars and Bossek, Jakob and Hoos, Holger H. and Trautmann, Heike}}, issn = {{1063-6560}}, journal = {{Evolutionary Computation}}, keywords = {{automated algorithm selection, machine learning., performance modeling, Travelling Salesperson Problem}}, number = {{4}}, pages = {{597–620}}, title = {{{Leveraging TSP Solver Complementarity through Machine Learning}}}, doi = {{10.1162/evco_a_00215}}, volume = {{26}}, year = {{2018}}, } @article{48866, abstract = {{Bossek, (2018). grapherator: A Modular Multi-Step Graph Generator. Journal of Open Source Software, 3(22), 528, https://doi.org/10.21105/joss.00528}}, author = {{Bossek, Jakob}}, issn = {{2475-9066}}, journal = {{Journal of Open Source Software}}, number = {{22}}, pages = {{528}}, title = {{{Grapherator: A Modular Multi-Step Graph Generator}}}, doi = {{10.21105/joss.00528}}, volume = {{3}}, year = {{2018}}, } @inproceedings{46348, abstract = {{We analyze the effects of including local search techniques into a multi-objective evolutionary algorithm for solving a bi-objective orienteering problem with a single vehicle while the two conflicting objectives are minimization of travel time and maximization of the number of visited customer locations. Experiments are based on a large set of specifically designed problem instances with different characteristics and it is shown that local search techniques focusing on one of the objectives only improve the performance of the evolutionary algorithm in terms of both objectives. The analysis also shows that local search techniques are capable of sending locally optimal solutions to foremost fronts of the multi-objective optimization process, and that these solutions then become the leading factors of the evolutionary process.}}, author = {{Bossek, Jakob and Grimme, Christian and Meisel, Stephan and Rudolph, Guenter and Trautmann, Heike}}, booktitle = {{Proceedings of the Genetic and Evolutionary Computation Conference}}, isbn = {{978-1-4503-5618-3}}, pages = {{585–592}}, publisher = {{ACM}}, title = {{{Local Search Effects in Bi-Objective Orienteering}}}, doi = {{10.1145/3205455.3205548}}, year = {{2018}}, } @article{46352, abstract = {{The Travelling Salesperson Problem (TSP) is one of the best-studied NP-hard problems. Over the years, many different solution approaches and solvers have been developed. For the first time, we directly compare five state-of-the-art inexact solvers—namely, LKH, EAX, restart variants of those, and MAOS—on a large set of well-known benchmark instances and demonstrate complementary performance, in that different instances may be solved most effectively by different algorithms. We leverage this complementarity to build an algorithm selector, which selects the best TSP solver on a per-instance basis and thus achieves significantly improved performance compared to the single best solver, representing an advance in the state of the art in solving the Euclidean TSP. Our in-depth analysis of the selectors provides insight into what drives this performance improvement.}}, author = {{Kerschke, Pascal and Kotthoff, Lars and Bossek, Jakob and Hoos, Holger H. and Trautmann, Heike}}, journal = {{Evolutionary Computation (ECJ)}}, number = {{4}}, pages = {{597–620}}, title = {{{Leveraging TSP Solver Complementarity through Machine Learning}}}, doi = {{10.1162/evco_a_00215}}, volume = {{26}}, year = {{2018}}, } @inproceedings{46349, abstract = {{Performance comparisons of optimization algorithms are heavily influenced by the underlying indicator(s). In this paper we investigate commonly used performance indicators for single-objective stochastic solvers, such as the Penalized Average Runtime (e.g., PAR10) or the Expected Running Time (ERT), based on exemplary benchmark performances of state-of-the-art inexact TSP solvers. Thereby, we introduce a methodology for analyzing the effects of (usually heuristically set) indicator parametrizations - such as the penalty factor and the method used for aggregating across multiple runs - w.r.t. the robustness of the considered optimization algorithms.}}, author = {{Kerschke, Pascal and Bossek, Jakob and Trautmann, Heike}}, booktitle = {{Proceedings of the Genetic and Evolutionary Computation Conference (GECCO ’18) Companion}}, isbn = {{978-1-4503-5764-7/18/07}}, pages = {{1737–1744}}, title = {{{Parameterization of State-of-the-Art Performance Indicators: A Robustness Study Based on Inexact TSP Solvers}}}, doi = {{10.1145/3205651.3208233}}, year = {{2018}}, } @inproceedings{48863, abstract = {{The novel R package ecr (version 2), short for Evolutionary Computation in R, provides a comprehensive collection of building blocks for constructing powerful evolutionary algorithms for single- and multi-objective continuous and combinatorial optimization problems. It allows to solve standard optimization tasks with few lines of code using a black-box approach. Moreover, rapid prototyping of non-standard ideas is possible via an explicit, white-box approach. This paper describes the design principles of the package and gives some introductory examples on how to use the package in practise.}}, author = {{Bossek, Jakob}}, booktitle = {{Proceedings of the Genetic and Evolutionary Computation Conference Companion}}, isbn = {{978-1-4503-4939-0}}, keywords = {{evolutionary optimization, software-tools}}, pages = {{1187–1193}}, publisher = {{Association for Computing Machinery}}, title = {{{Ecr 2.0: A Modular Framework for Evolutionary Computation in R}}}, doi = {{10.1145/3067695.3082470}}, year = {{2017}}, } @inproceedings{48857, abstract = {{While finding minimum-cost spanning trees (MST) in undirected graphs is solvable in polynomial time, the multi-criteria minimum spanning tree problem (mcMST) is NP-hard. Interestingly, the mcMST problem has not been in focus of evolutionary computation research for a long period of time, although, its relevance for real world problems is easy to see. The available and most notable approaches by Zhou and Gen as well as by Knowles and Corne concentrate on solution encoding and on fairly dated selection mechanisms. In this work, we revisit the mcMST and focus on the mutation operators as exploratory components of evolutionary algorithms neglected so far. We investigate optimal solution characteristics to discuss current mutation strategies, identify shortcomings of these operators, and propose a sub-tree based operator which offers what we term Pareto-beneficial behavior: ensuring convergence and diversity at the same time. The operator is empirically evaluated inside modern standard evolutionary meta-heuristics for multi-criteria optimization and compared to hitherto applied mutation operators in the context of mcMST.}}, author = {{Bossek, Jakob and Grimme, Christian}}, booktitle = {{2017 IEEE Symposium Series on Computational Intelligence (SSCI)}}, keywords = {{Convergence, Encoding, Euclidean distance, Evolutionary computation, Heating systems, Optimization, Standards}}, pages = {{1–8}}, title = {{{A Pareto-Beneficial Sub-Tree Mutation for the Multi-Criteria Minimum Spanning Tree Problem}}}, doi = {{10.1109/SSCI.2017.8285183}}, year = {{2017}}, } @inproceedings{48856, abstract = {{There exist many optimal or heuristic priority rules for machine scheduling problems, which can easily be integrated into single-objective evolutionary algorithms via mutation operators. However, in the multi-objective case, simultaneously applying different priorities for different objectives may cause severe disruptions in the genome and may lead to inferior solutions. In this paper, we combine an existing mutation operator concept with new insights from detailed observation of the structure of solutions for multi-objective machine scheduling problems. This allows the comprehensive integration of priority rules to produce better Pareto-front approximations. We evaluate the extended operator concept compared to standard swap mutation and the stand-alone components of our hybrid scheme, which performs best in all evaluated cases.}}, author = {{Bossek, Jakob and Grimme, Christian}}, booktitle = {{2017 IEEE Symposium Series on Computational Intelligence (SSCI)}}, keywords = {{Evolutionary computation, Processor scheduling, Schedules, Scheduling, Sociology, Standards, Statistics}}, pages = {{1–8}}, title = {{{An Extended Mutation-Based Priority-Rule Integration Concept for Multi-Objective Machine Scheduling}}}, doi = {{10.1109/SSCI.2017.8285224}}, year = {{2017}}, } @article{48864, abstract = {{Bossek, (2017), mcMST: A Toolbox for the Multi-Criteria Minimum Spanning Tree Problem, Journal of Open Source Software, 2(17), 374, doi:10.21105/joss.00374}}, author = {{Bossek, Jakob}}, issn = {{2475-9066}}, journal = {{Journal of Open Source Software}}, number = {{17}}, pages = {{374}}, title = {{{mcMST: A Toolbox for the Multi-Criteria Minimum Spanning Tree Problem}}}, doi = {{10.21105/joss.00374}}, volume = {{2}}, year = {{2017}}, } @article{48865, author = {{Bossek, Jakob}}, issn = {{2073-4859}}, journal = {{The R Journal}}, number = {{1}}, pages = {{103–113}}, title = {{{Smoof: Single- and Multi-Objective Optimization Test Functions}}}, volume = {{9}}, year = {{2017}}, } @article{48837, author = {{Bischl, Bernd and Richter, Jakob and Bossek, Jakob and Horn, Daniel and Thomas, Janek and Lang, Michel}}, journal = {{CoRR}}, title = {{{mlrMBO: A Modular Framework for Model-Based Optimization of Expensive Black-Box Functions}}}, year = {{2017}}, } @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}}, }