@inproceedings{48861, abstract = {{Generating instances of different properties is key to algorithm selection methods that differentiate between the performance of different solvers for a given combinatorial optimization problem. A wide range of methods using evolutionary computation techniques has been introduced in recent years. With this paper, we contribute to this area of research by providing a new approach based on quality diversity (QD) that is able to explore the whole feature space. QD algorithms allow to create solutions of high quality within a given feature space by splitting it up into boxes and improving solution quality within each box. We use our QD approach for the generation of TSP instances to visualize and analyze the variety of instances differentiating various TSP solvers and compare it to instances generated by established approaches from the literature.}}, author = {{Bossek, Jakob and Neumann, Frank}}, booktitle = {{Proceedings of the Genetic and Evolutionary Computation Conference}}, isbn = {{978-1-4503-9237-2}}, keywords = {{instance features, instance generation, quality diversity, TSP}}, pages = {{186–194}}, publisher = {{Association for Computing Machinery}}, title = {{{Exploring the Feature Space of TSP Instances Using Quality Diversity}}}, doi = {{10.1145/3512290.3528851}}, year = {{2022}}, } @inbook{48881, abstract = {{Classic automated algorithm selection (AS) for (combinatorial) optimization problems heavily relies on so-called instance features, i.e., numerical characteristics of the problem at hand ideally extracted with computationally low-demanding routines. For the traveling salesperson problem (TSP) a plethora of features have been suggested. Most of these features are, if at all, only normalized imprecisely raising the issue of feature values being strongly affected by the instance size. Such artifacts may have detrimental effects on algorithm selection models. We propose a normalization for two feature groups which stood out in multiple AS studies on the TSP: (a) features based on a minimum spanning tree (MST) and (b) a k-nearest neighbor graph (NNG) transformation of the input instance. To this end we theoretically derive minimum and maximum values for properties of MSTs and k-NNGs of Euclidean graphs. We analyze the differences in feature space between normalized versions of these features and their unnormalized counterparts. Our empirical investigations on various TSP benchmark sets point out that the feature scaling succeeds in eliminating the effect of the instance size. Eventually, a proof-of-concept AS-study shows promising results: models trained with normalized features tend to outperform those trained with the respective vanilla features.}}, author = {{Heins, Jonathan and Bossek, Jakob and Pohl, Janina and Seiler, Moritz and Trautmann, Heike and Kerschke, Pascal}}, booktitle = {{Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms}}, isbn = {{978-1-4503-8352-3}}, keywords = {{automated algorithm selection, graph theory, instance features, normalization, traveling salesperson problem (TSP)}}, pages = {{1–15}}, publisher = {{Association for Computing Machinery}}, title = {{{On the Potential of Normalized TSP Features for Automated Algorithm Selection}}}, year = {{2021}}, } @inbook{48892, abstract = {{Evolutionary algorithms based on edge assembly crossover (EAX) constitute some of the best performing incomplete solvers for the well-known traveling salesperson problem (TSP). Often, it is desirable to compute not just a single solution for a given problem, but a diverse set of high quality solutions from which a decision maker can choose one for implementation. Currently, there are only a few approaches for computing a diverse solution set for the TSP. Furthermore, almost all of them assume that the optimal solution is known. In this paper, we introduce evolutionary diversity optimisation (EDO) approaches for the TSP that find a diverse set of tours when the optimal tour is known or unknown. We show how to adopt EAX to not only find a high-quality solution but also to maximise the diversity of the population. The resulting EAX-based EDO approach, termed EAX-EDO is capable of obtaining diverse high-quality tours when the optimal solution for the TSP is known or unknown. A comparison to existing approaches shows that they are clearly outperformed by EAX-EDO.}}, author = {{Nikfarjam, Adel and Bossek, Jakob and Neumann, Aneta and Neumann, Frank}}, booktitle = {{Proceedings of the 16th ACM}/SIGEVO Conference on Foundations of Genetic Algorithms}}, isbn = {{978-1-4503-8352-3}}, keywords = {{edge assembly crossover (EAX), evolutionary algorithms, evolutionary diversity optimisation (EDO), traveling salesperson problem (TSP)}}, pages = {{1–11}}, publisher = {{Association for Computing Machinery}}, title = {{{Computing Diverse Sets of High Quality TSP Tours by EAX-based Evolutionary Diversity Optimisation}}}, year = {{2021}}, } @inproceedings{48852, abstract = {{The Traveling Salesperson Problem (TSP) is one of the best-known combinatorial optimisation problems. However, many real-world problems are composed of several interacting components. The Traveling Thief Problem (TTP) addresses such interactions by combining two combinatorial optimisation problems, namely the TSP and the Knapsack Problem (KP). Recently, a new problem called the node weight dependent Traveling Salesperson Problem (W-TSP) has been introduced where nodes have weights that influence the cost of the tour. In this paper, we compare W-TSP and TTP. We investigate the structure of the optimised tours for W-TSP and TTP and the impact of using each others fitness function. Our experimental results suggest (1) that the W-TSP often can be solved better using the TTP fitness function and (2) final W-TSP and TTP solutions show different distributions when compared with optimal TSP or weighted greedy solutions.}}, author = {{Bossek, Jakob and Neumann, Aneta and Neumann, Frank}}, booktitle = {{Parallel Problem Solving from Nature (PPSN XVI)}}, isbn = {{978-3-030-58111-4}}, keywords = {{Evolutionary algorithms, Node weight dependent TSP, Traveling Thief Problem}}, pages = {{346–359}}, publisher = {{Springer-Verlag}}, title = {{{Optimising Tours for the Weighted Traveling Salesperson Problem and the Traveling Thief Problem: A Structural Comparison of Solutions}}}, doi = {{10.1007/978-3-030-58112-1_24}}, year = {{2020}}, } @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}}, } @article{48889, abstract = {{Meta-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.}}, author = {{Mersmann, Olaf and Bischl, Bernd and Trautmann, Heike and Wagner, Markus and Bossek, Jakob and Neumann, Frank}}, issn = {{1012-2443}}, journal = {{Annals of Mathematics and Artificial Intelligence}}, keywords = {{2-opt, 90B06, Classification, Feature selection, MARS, TSP}}, number = {{2}}, pages = {{151–182}}, title = {{{A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesperson Problem}}}, doi = {{10.1007/s10472-013-9341-2}}, volume = {{69}}, year = {{2013}}, } @inproceedings{48890, abstract = {{With 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.}}, author = {{Mersmann, Olaf and Bischl, Bernd and Bossek, Jakob and Trautmann, Heike and Wagner, Markus and Neumann, Frank}}, booktitle = {{Revised Selected Papers of the 6th International Conference on Learning and Intelligent Optimization - Volume 7219}}, isbn = {{978-3-642-34412-1}}, keywords = {{2-opt, Classification, Feature Selection, MARS, TSP}}, pages = {{115–129}}, publisher = {{Springer-Verlag}}, title = {{{Local Search and the Traveling Salesman Problem: A Feature-Based Characterization of Problem Hardness}}}, year = {{2012}}, }