A fast ant colony optimization for traveling salesman problem

Shih Pang Tseng, Chun Wei Tsai, Ming Chao Chiang, Chu-Sing Yang

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

14 Citations (Scopus)

Abstract

In this paper, we present an efficient method for speeding up Ant Colony Optimization (ACO), called Pattern Reduction Enhanced Ant Colony Optimization (PREACO). The proposed algorithm is motivated by the observation that many of the computations of ACO on its convergence process are essentially redundant and thus can be eliminated to reduce its computation time. To evaluate the performance of the proposed algorithm, we use it to solve the the traveling salesman problem (TSP). Moreover, we compare the proposed algorithm with several state-of-the-art ACO-based algorithms. Our simulation results indicate that the proposed algorithm can reduce the computation time of ACO algorithms we evaluated up to 99.21% or by a factor of 126.58 while limiting the degradation of the quality of the solution to a very small percentage compared to ACO algorithms themselves.

Original languageEnglish
Title of host publication2010 IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010
DOIs
Publication statusPublished - 2010 Dec 1
Event2010 6th IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010 - Barcelona, Spain
Duration: 2010 Jul 182010 Jul 23

Publication series

Name2010 IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010

Other

Other2010 6th IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010
CountrySpain
CityBarcelona
Period10-07-1810-07-23

    Fingerprint

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics
  • Applied Mathematics

Cite this

Tseng, S. P., Tsai, C. W., Chiang, M. C., & Yang, C-S. (2010). A fast ant colony optimization for traveling salesman problem. In 2010 IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010 [5586153] (2010 IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010). https://doi.org/10.1109/CEC.2010.5586153