Parameterized complexity analysis and more effective construction methods for ACO algorithms and the euclidean traveling salesperson problem

Samadhi Nallaperuma, Andrew M. Sutton, Frank Neumann

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

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 Max-Min 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.

Original languageEnglish (US)
Title of host publication2013 IEEE Congress on Evolutionary Computation, CEC 2013
Pages2045-2052
Number of pages8
DOIs
StatePublished - Aug 21 2013
Event2013 IEEE Congress on Evolutionary Computation, CEC 2013 - Cancun, Mexico
Duration: Jun 20 2013Jun 23 2013

Publication series

Name2013 IEEE Congress on Evolutionary Computation, CEC 2013

Other

Other2013 IEEE Congress on Evolutionary Computation, CEC 2013
CountryMexico
CityCancun
Period6/20/136/23/13

Fingerprint Dive into the research topics of 'Parameterized complexity analysis and more effective construction methods for ACO algorithms and the euclidean traveling salesperson problem'. Together they form a unique fingerprint.

  • Cite this

    Nallaperuma, S., Sutton, A. M., & Neumann, F. (2013). Parameterized complexity analysis and more effective construction methods for ACO algorithms and the euclidean traveling salesperson problem. In 2013 IEEE Congress on Evolutionary Computation, CEC 2013 (pp. 2045-2052). [6557810] (2013 IEEE Congress on Evolutionary Computation, CEC 2013). https://doi.org/10.1109/CEC.2013.6557810