A novel feature-based approach to characterize algorithm performance for the traveling salesperson problem
From MaRDI portal
Publication:2248551
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 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.
Recommendations
- A feature-based comparison of local search and the Christofides algorithm for the travelling salesperson problem
- Measuring instance difficulty for combinatorial optimization problems
- scientific article; zbMATH DE number 177832
- scientific article; zbMATH DE number 795217
- scientific article; zbMATH DE number 1488085
Cites work
- A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
- A method for solving traveling-salesman problems
- An Effective Heuristic Algorithm for the Traveling-Salesman Problem
- Ant colony optimization.
- Automata, Languages and Programming
- Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
- Computer Solutions of the Traveling Salesman Problem
- Discovering the suitability of optimisation algorithms by learning from evolved instances
- Ejection chains, reference structures and alternating path methods for traveling salesman problems
- scientific article; zbMATH DE number 3860199 (Why is no real title available?)
- scientific article; zbMATH DE number 4048925 (Why is no real title available?)
- scientific article; zbMATH DE number 1082106 (Why is no real title available?)
- scientific article; zbMATH DE number 1839431 (Why is no real title available?)
- scientific article; zbMATH DE number 5582828 (Why is no real title available?)
- Introduction to evolutionary computing
- Measuring instance difficulty for combinatorial optimization problems
- Multivariate adaptive regression splines
- New Results on the Old k-opt Algorithm for the Traveling Salesman Problem
- On the analysis of the \((1+1)\) evolutionary algorithm
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- Random forests
- Runtime analysis of a simple ant colony optimization algorithm
- Solution of a min-max vehicle routing problem
- Stochastic local search. Foundations and applications.
- The landscape of the traveling salesman problem
- Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP (extended abstract)
- Wrappers for feature subset selection
Cited in
(15)- Advancing Shannon entropy for measuring diversity in systems
- Measuring instance difficulty for combinatorial optimization problems
- Decomposition-based multi-objective landscape features and automated algorithm selection
- Machine learning at the service of meta-heuristics for solving combinatorial optimization problems: a state-of-the-art
- On the use of fitness landscape features in meta-learning based algorithm selection for the quadratic assignment problem
- A study on the effects of normalized TSP features for automated algorithm selection
- On the empirical scaling of run-time for finding optimal solutions to the travelling salesman problem
- Unified encoding for hyper-heuristics with application to bioinformatics
- Union search: a new meta-heuristic algorithm to the traveling salesman problem
- scientific article; zbMATH DE number 1488085 (Why is no real title available?)
- Algorithm runtime prediction: methods \& evaluation
- On the potential of normalized TSP features for automated algorithm selection
- A feature-based comparison of local search and the Christofides algorithm for the travelling salesperson problem
- Adaptive neighborhood search based on landscape learning: a TSP study
- Machine scheduling instance generation by reverse engineering from instance space analysis
This page was built for publication: A novel feature-based approach to characterize algorithm performance for the traveling salesperson problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2248551)
