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

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

Han Huang (School of Software Engineering, South China University of Technology, Guangzhou, China), Hongyue Wu (School of Software Engineering, South China University of Technology, Guangzhou, China), Yushan Zhang (School of Statistics and Mathematics, Guangdong University of Finance and Economics, Guangzhou, China), Zhiyong Lin (Department of Computer Science, Guangdong Polytechnic Normal University, Guangzhou, China) and Zhifeng Hao (School of Applied Mathematics, Guangdong University of Technology, Guangzhou, China)
Copyright: © 2017 |Pages: 17
DOI: 10.4018/IJSIR.2017100101
OnDemand PDF Download:
$30.00
List Price: $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

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
Open Access Articles: Forthcoming
Volume 9: 4 Issues (2018): 1 Released, 3 Forthcoming
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