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

Han Huang, Hongyue Wu, Yushan Zhang, Zhiyong Lin and Zhifeng Hao
Additional contact information
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
Zhifeng Hao: School of Applied Mathematics, Guangdong University of Technology, Guangzhou, China

International Journal of Swarm Intelligence Research (IJSIR), 2017, vol. 8, issue 4, 1-17

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.

Date: 2017
References: Add references at CitEc
Citations:

Downloads: (external link)
http://services.igi-global.com/resolvedoi/resolve. ... 018/IJSIR.2017100101 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:igg:jsir00:v:8:y:2017:i:4:p:1-17

Access Statistics for this article

International Journal of Swarm Intelligence Research (IJSIR) is currently edited by Yuhui Shi

More articles in International Journal of Swarm Intelligence Research (IJSIR) from IGI Global
Bibliographic data for series maintained by Journal Editor ().