TY - GEN
T1 - A theoretical framework for runtime analysis of ant colony optimization
AU - Yang, Zhong-Ming
AU - Huang, Han
AU - Cai, Zhaoquan
AU - Qin, Yong
PY - 2010
Y1 - 2010
N2 - Ant colony optimization (ACO) is one of the most famous bio-inspired algorithms. Its theoretical research contains convergence proof and runtime analysis. The convergence of ACO has been proved since several years ago, but there are less results of runtime analysis of ACO algorithm except for some special and simple cases. The present paper proposes a theoretical framework of a class of ACO algorithms. The ACO algorithm is modeled as an absorbing Markov chain. Afterward its convergence can be analyzed based on the model, and the runtime of ACO algorithm is evaluated with the convergence time which reflects how many iteration times ACO algorithms spend in converging to the optimal solution. Moreover, the runtime analysis result is advanced as an estimation method, which is used to study a binary ACO algorithm as a case study. © 2010 IEEE.
AB - Ant colony optimization (ACO) is one of the most famous bio-inspired algorithms. Its theoretical research contains convergence proof and runtime analysis. The convergence of ACO has been proved since several years ago, but there are less results of runtime analysis of ACO algorithm except for some special and simple cases. The present paper proposes a theoretical framework of a class of ACO algorithms. The ACO algorithm is modeled as an absorbing Markov chain. Afterward its convergence can be analyzed based on the model, and the runtime of ACO algorithm is evaluated with the convergence time which reflects how many iteration times ACO algorithms spend in converging to the optimal solution. Moreover, the runtime analysis result is advanced as an estimation method, which is used to study a binary ACO algorithm as a case study. © 2010 IEEE.
KW - Ant colony optimization
KW - Bio-inspired algorithm
KW - Convergence
KW - Convergence time
KW - Runtime analysis
UR - http://www.scopus.com/inward/record.url?scp=78149309746&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-78149309746&origin=recordpage
U2 - 10.1109/ICMLC.2010.5580959
DO - 10.1109/ICMLC.2010.5580959
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 9781424465262
VL - 4
SP - 1817
EP - 1822
BT - 2010 International Conference on Machine Learning and Cybernetics, ICMLC 2010
T2 - 2010 International Conference on Machine Learning and Cybernetics, ICMLC 2010
Y2 - 11 July 2010 through 14 July 2010
ER -