@article{54548, author = {{Prager, Raphael Patrick and Trautmann, Heike}}, journal = {{IEEE Transactions on Evolutionary Computation}}, keywords = {{Optimization, Evolutionary computation, Benchmark testing, Hyperparameter optimization, Portfolios, Extraterrestrial measurements, Dispersion, Exploratory landscape analysis, mixed-variable problem, mixed search spaces, automated algorithm selection}}, pages = {{1--1}}, title = {{{Exploratory Landscape Analysis for Mixed-Variable Problems}}}, doi = {{10.1109/TEVC.2024.3399560}}, year = {{2024}}, } @article{46310, 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) nearest neighbor relationships of the input instance. To this end we theoretically derive minimum and maximum values for properties of MSTs and k-nearest neighbor graphs (NNG) 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. 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}}, issn = {{0304-3975}}, journal = {{Theoretical Computer Science}}, keywords = {{Feature normalization, Algorithm selection, Traveling salesperson problem}}, pages = {{123--145}}, title = {{{A study on the effects of normalized TSP features for automated algorithm selection}}}, doi = {{https://doi.org/10.1016/j.tcs.2022.10.019}}, volume = {{940}}, year = {{2023}}, } @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}}, } @inproceedings{48897, abstract = {{In 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 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.}}, author = {{Seiler, Moritz and Pohl, Janina and Bossek, Jakob and Kerschke, Pascal and Trautmann, Heike}}, booktitle = {{Parallel Problem Solving from {Nature} (PPSN XVI)}}, isbn = {{978-3-030-58111-4}}, keywords = {{Automated algorithm selection, Deep learning, Feature-based approaches, Traveling Salesperson Problem}}, pages = {{48–64}}, publisher = {{Springer-Verlag}}, title = {{{Deep Learning as a Competitive Feature-Free Approach for Automated Algorithm Selection on the Traveling Salesperson Problem}}}, doi = {{10.1007/978-3-030-58112-1_4}}, year = {{2020}}, } @article{48848, abstract = {{We build upon a recently proposed multi-objective view onto performance measurement of single-objective stochastic solvers. The trade-off between the fraction of failed runs and the mean runtime of successful runs \textendash both to be minimized \textendash is directly analyzed based on a study on algorithm selection of inexact state-of-the-art solvers for the famous Traveling Salesperson Problem (TSP). Moreover, we adopt the hypervolume indicator (HV) commonly used in multi-objective optimization for simultaneously assessing both conflicting objectives and investigate relations to commonly used performance indicators, both theoretically and empirically. Next to Penalized Average Runtime (PAR) and Penalized Quantile Runtime (PQR), the HV measure is used as a core concept within the construction of per-instance algorithm selection models offering interesting insights into complementary behavior of inexact TSP solvers. \textbullet The multi-objective perspective is naturally generalizable to multiple objectives. \textbullet Proof of relationship between HV and the PAR in the considered bi-objective space. \textbullet New insights into complementary behavior of stochastic optimization algorithms.}}, author = {{Bossek, Jakob and Kerschke, Pascal and Trautmann, Heike}}, issn = {{1568-4946}}, journal = {{Applied Soft Computing}}, keywords = {{Algorithm selection, Combinatorial optimization, Multi-objective optimization, Performance measurement, Traveling Salesperson Problem}}, number = {{C}}, title = {{{A Multi-Objective Perspective on Performance Assessment and Automated Selection of Single-Objective Optimization Algorithms}}}, doi = {{10.1016/j.asoc.2019.105901}}, volume = {{88}}, year = {{2020}}, } @article{46334, abstract = {{We build upon a recently proposed multi-objective view onto performance measurement of single-objective stochastic solvers. The trade-off between the fraction of failed runs and the mean runtime of successful runs – both to be minimized – is directly analyzed based on a study on algorithm selection of inexact state-of-the-art solvers for the famous Traveling Salesperson Problem (TSP). Moreover, we adopt the hypervolume indicator (HV) commonly used in multi-objective optimization for simultaneously assessing both conflicting objectives and investigate relations to commonly used performance indicators, both theoretically and empirically. Next to Penalized Average Runtime (PAR) and Penalized Quantile Runtime (PQR), the HV measure is used as a core concept within the construction of per-instance algorithm selection models offering interesting insights into complementary behavior of inexact TSP solvers.}}, author = {{Bossek, Jakob and Kerschke, Pascal and Trautmann, Heike}}, issn = {{1568-4946}}, journal = {{Applied Soft Computing}}, keywords = {{Algorithm selection, Multi-objective optimization, Performance measurement, Combinatorial optimization, Traveling Salesperson Problem}}, pages = {{105901}}, title = {{{A multi-objective perspective on performance assessment and automated selection of single-objective optimization algorithms}}}, doi = {{https://doi.org/10.1016/j.asoc.2019.105901}}, volume = {{88}}, year = {{2020}}, } @inproceedings{48875, 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, Roberto and Brunato, Mauro and Kotsireas, Ilias and Pardalos, Panos M.}}, isbn = {{978-3-030-05348-2}}, keywords = {{Algorithm selection, Performance measurement}}, pages = {{215–219}}, publisher = {{Springer International Publishing}}, title = {{{Multi-Objective Performance Measurement: Alternatives to PAR10 and Expected Running Time}}}, doi = {{10.1007/978-3-030-05348-2_19}}, year = {{2019}}, } @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}}, } @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}}, } @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{46396, abstract = {{The steady supply of new optimization methods makes the algorithm selection problem (ASP) an increasingly pressing and challenging task, specially for real-world black-box optimization problems. The introduced approach considers the ASP as a cost-sensitive classification task which is based on Exploratory Landscape Analysis. Low-level features gathered by systematic sampling of the function on the feasible set are used to predict a well-performing algorithm out of a given portfolio. Example-specific label costs are defined by the expected runtime of each candidate algorithm. We use one-sided support vector regression to solve this learning problem. The approach is illustrated by means of the optimization problems and algorithms of the BBOB’09/10 workshop.}}, author = {{Bischl, Bernd and Mersmann, Olaf and Trautmann, Heike and Preuß, Mike}}, booktitle = {{Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation}}, isbn = {{9781450311779}}, keywords = {{machine learning, exploratory landscape analysis, fitness landscape, benchmarking, evolutionary optimization, bbob test set, algorithm selection}}, pages = {{313–320}}, publisher = {{Association for Computing Machinery}}, title = {{{Algorithm Selection Based on Exploratory Landscape Analysis and Cost-Sensitive Learning}}}, doi = {{10.1145/2330163.2330209}}, year = {{2012}}, }