Analyzing the Effects of Instance Features and Algorithm Parameters for Max–Min Ant System and the Traveling Salesperson Problem
Authors:
Open Access
- 20 July 2015
- journal article
- research article
- Published by Frontiers Media SA in Frontiers in Robotics and AI
- Vol. 2
Abstract
Ant colony optimization (ACO) performs very well on many hard optimization problems, even though no good worst-case guarantee can be given. Understanding the effects of different ACO parameters and the structural features of the considered problem on algorithm performance has become an interesting problem. In this paper, we study structural features of easy and hard instances of the traveling salesperson problem for a well-known ACO variant called Max–Min Ant System (MMAS) for several parameter settings. The four considered parameters are the importance of pheromone values, the heuristic information, the pheromone update strength, and the number of ants. We further use this knowledge to predict the best parameter setting for a wide range of instances taken from TSPLIB.Keywords
This publication has 28 references indexed in Scilit:
- Identifying Key Algorithm Parameters and Instance Features Using Forward Selection2013
- The Traveling Salesman Problem2011
- The WEKA data mining softwareACM SIGKDD Explorations Newsletter, 2009
- Reducibility Among Combinatorial Problems2009
- Ant Colony Optimization and Swarm Intelligence2004
- Solution of a Min-Max Vehicle Routing ProblemINFORMS Journal on Computing, 2002
- Fuel saving strategies for separated spacecraft interferometry2000
- A Fast and Scalable Radiation Hybrid Map Construction and Integration StrategyGenome Research, 2000
- Instance-based learning algorithmsMachine Learning, 1991
- Large travelling salesman problems arising from experiments in X-ray crystallography: A preliminary report on computationOperations Research Letters, 1989