Analyzing the effects of instance features and algorithm parameters for max-min ant system and the traveling salesperson problem
Files
(Published version)
Date
2015
Authors
Nallaperuma, S.
Wagner, M.
Neumann, F.
Editors
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Journal article
Citation
Frontiers in Robotics and AI, 2015; 2(JUL):18-1-18-16
Statement of Responsibility
Samadhi Nallaperuma, Markus Wagner and Frank Neumann
Conference Name
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.
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
Copyright: © 2015 Nallaperuma, Wagner and Neumann. This is an open-access article distributed under the terms of the Creative Commons Attribution License (CC BY). The use, distribution or reproduction in other forums is permitted, provided the original author(s) or licensor are credited and that the original publication in this journal is cited, in accordance with accepted academic practice. No use, distribution or reproduction is permitted which does not comply with these terms.