Parameterized complexity analysis and more effective construction methods for ACO algorithms and the Euclidean traveling salesperson problem
Date
2013
Authors
Nallaperuma, S.
Sutton, A.
Neumann, F.
Editors
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Conference paper
Citation
2013 IEEE Congress on Evolutionary Computation (CEC): pp.2045-2052
Statement of Responsibility
Samadhi Nallaperuma, Andrew M. Sutton, Frank Neumann
Conference Name
IEEE Congress on Evolutionary Computation (2013 : Cancun, Mexico)
Abstract
We propose a new construction procedure for ant colony optimization (ACO) algorithms working on the Euclidean traveling salesperson problem (TSP) that preserves the ordering on the convex hull of the points in the instance. The procedure is inspired by theoretical analyses for simple evolutionary algorithms that are provably more efficient on instances where the number of inner points of the instance is not too large. We integrate the construction procedure into the well-known MaxMin Ant System (MMAS) and empirically show that it leads to more efficient optimization on instances where the number of inner points is not too high.
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
©2013 IEEE