Running-time Analysis of Ant System Algorithms with Upper-bound Comparison

Running-time Analysis of Ant System Algorithms with Upper-bound Comparison

Han Huang, Hongyue Wu, Yushan Zhang, Zhiyong Lin, Zhifeng Hao
Copyright: © 2017 |Pages: 17
DOI: 10.4018/IJSIR.2017100101
OnDemand:
(Individual Articles)
Available
$37.50
Current Special Offers
No Current Special Offers
TOTAL SAVINGS: $37.50

Abstract

Running-time analysis of ant colony optimization (ACO) is crucial for understanding the power of the algorithm in computation. This paper conducts a running-time analysis of ant system algorithms (AS) as a kind of ACO for traveling salesman problems (TSP). The authors model the AS algorithm as an absorbing Markov chain through jointly representing the best-so-far solutions and pheromone matrix as a discrete stochastic status per iteration. The running-time of AS can be evaluated by the expected first-hitting time (FHT), the least number of iterations needed to attain the global optimal solution on average. The authors derive upper bounds of the expected FHT of two classical AS algorithms (i.e., ant quantity system and ant-cycle system) for TSP. They further take regular-polygon TSP (RTSP) as a case study and obtain numerical results by calculating six RTSP instances. The RTSP is a special but real-world TSP where the constraint of triangle inequality is stringently imposed. The numerical results derived from the comparison of the running time of the two AS algorithms verify our theoretical findings.
Article Preview
Top

The representative studies of theoretical foundation of ACO are briefly reviewed in two branches (i.e., convergence proof and running-time analysis) as follows.

Complete Article List

Search this Journal:
Reset
Volume 15: 1 Issue (2024)
Volume 14: 3 Issues (2023)
Volume 13: 4 Issues (2022)
Volume 12: 4 Issues (2021)
Volume 11: 4 Issues (2020)
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing