{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T15:15:06Z","timestamp":1781104506024,"version":"3.54.1"},"reference-count":38,"publisher":"IGI Global Scientific Publishing","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017,10]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.4018\/ijsir.2017100101","type":"journal-article","created":{"date-parts":[[2017,7,14]],"date-time":"2017-07-14T11:51:13Z","timestamp":1500033073000},"page":"1-17","source":"Crossref","is-referenced-by-count":0,"title":["Running-time Analysis of Ant System Algorithms with Upper-bound Comparison"],"prefix":"10.4018","volume":"8","author":[{"given":"Han","family":"Huang","sequence":"first","affiliation":[{"name":"School of Software Engineering, South China University of Technology, Guangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hongyue","family":"Wu","sequence":"additional","affiliation":[{"name":"School of Software Engineering, South China University of Technology, Guangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yushan","family":"Zhang","sequence":"additional","affiliation":[{"name":"School of Statistics and Mathematics, Guangdong University of Finance and Economics, Guangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhiyong","family":"Lin","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Guangdong Polytechnic Normal University, Guangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhifeng","family":"Hao","sequence":"additional","affiliation":[{"name":"School of Applied Mathematics, Guangdong University of Technology, Guangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"2432","reference":[{"key":"IJSIR.2017100101-0","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.08.013"},{"issue":"1","key":"IJSIR.2017100101-1","first-page":"267","article-title":"A proof of convergence for ant algorithms. Information Sciences\u2014informatics & Computer Science","volume":"160","author":"A.Badr","year":"2004","journal-title":"International Journal (Toronto, Ont.)"},{"key":"IJSIR.2017100101-2","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2009.2040019"},{"key":"IJSIR.2017100101-3","doi-asserted-by":"crossref","unstructured":"Doerr, B., & Johannsen, D. (2007). Refined runtime analysis of a basic ant colony optimization algorithm. Proceedings of the IEEE Congress on Evolutionary Computation CEC \u201807 (Vol. 96, pp. 480-485). IEEE.","DOI":"10.1109\/CEC.2007.4424512"},{"key":"IJSIR.2017100101-4","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.12.030"},{"key":"IJSIR.2017100101-5","doi-asserted-by":"crossref","unstructured":"Dorigo, M., Birattari, M., & St\u00fctzle, T. (2006). Ant colony optimization. Encyclopedia of Machine Learning (pp. 36-39). Springer US.","DOI":"10.1109\/CI-M.2006.248054"},{"key":"IJSIR.2017100101-6","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.05.020"},{"key":"IJSIR.2017100101-7","doi-asserted-by":"publisher","DOI":"10.1109\/4235.585892"},{"key":"IJSIR.2017100101-8","doi-asserted-by":"crossref","unstructured":"Dorigo, M., Maniezzo, V., & Colorni, A. (1996). Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems Man & Cybernetics Part B Cybernetics, 26(1), 29-41.","DOI":"10.1109\/3477.484436"},{"key":"IJSIR.2017100101-9","first-page":"11","article-title":"The Ant Colony Optimization Metaheuristic: Algorithms, Applications, and Advances.","volume":"28","author":"M.Dorigo","year":"1999","journal-title":"New Ideas in Optimization"},{"key":"IJSIR.2017100101-10","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-739X(00)00044-3"},{"key":"IJSIR.2017100101-11","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(01)00258-7"},{"key":"IJSIR.2017100101-12","doi-asserted-by":"publisher","DOI":"10.1017\/S0269964803174086"},{"key":"IJSIR.2017100101-13","doi-asserted-by":"publisher","DOI":"10.1007\/s11721-007-0001-1"},{"key":"IJSIR.2017100101-14","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2006.12.017"},{"key":"IJSIR.2017100101-15","doi-asserted-by":"publisher","DOI":"10.1007\/s11009-007-9047-1"},{"key":"IJSIR.2017100101-16","doi-asserted-by":"publisher","DOI":"10.1007\/11903697_65"},{"key":"IJSIR.2017100101-17","doi-asserted-by":"crossref","unstructured":"Huang, H., Wu, C. G., & Hao, Z. F. (2009). A pheromone-rate-based analysis on the convergence time of aco algorithm. IEEE Transactions on Systems Man & Cybernetics Part B Cybernetics A Publication of the IEEE Systems Man & Cybernetics Society, 39(4), 910-923.","DOI":"10.1109\/TSMCB.2009.2012867"},{"key":"IJSIR.2017100101-18","doi-asserted-by":"publisher","DOI":"10.1145\/1830483.1830741"},{"key":"IJSIR.2017100101-19","first-page":"324","article-title":"Theoretical properties of two ACO approaches for the traveling salesman problem. Swarm Intelligence -, International Conference, Ants 2010, Brussels, Belgium, September 8-10, 2010.","volume":"6","author":"T.K\u00f6tzing","year":"2010","journal-title":"Proceedings"},{"key":"IJSIR.2017100101-20","doi-asserted-by":"publisher","DOI":"10.1007\/s11721-011-0059-7"},{"key":"IJSIR.2017100101-21","first-page":"2045","article-title":"Parameterized complexity analysis and more effective construction methods for ACO algorithms and the Euclidean traveling salesperson problem.","author":"S.Nallaperuma","year":"2013","journal-title":"Evolutionary Computation"},{"issue":"3","key":"IJSIR.2017100101-22","first-page":"474","article-title":"Rigorous analyses for the combination of ant colony optimization and local search. Biochimica et Biophysica Acta (BBA) -","volume":"544","author":"F.Neumann","year":"1978","journal-title":"General Subjects"},{"key":"IJSIR.2017100101-23","author":"F.Neumann","year":"2009","journal-title":"Computational Complexity of Ant Colony Optimization and Its Hybridization with Local Search. Innovations in Swarm Intelligence"},{"key":"IJSIR.2017100101-24","doi-asserted-by":"publisher","DOI":"10.1007\/s11721-008-0023-3"},{"key":"IJSIR.2017100101-25","author":"F.Neumann","year":"2008","journal-title":"Ant Colony Optimization and the minimum spanning tree problem. Learning and Intelligent Optimization"},{"key":"IJSIR.2017100101-26","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9134-2"},{"key":"IJSIR.2017100101-27","doi-asserted-by":"publisher","DOI":"10.1007\/s11633-007-0281-3"},{"key":"IJSIR.2017100101-28","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87700-4_9"},{"key":"IJSIR.2017100101-29","doi-asserted-by":"publisher","DOI":"10.4018\/jsir.2011070101"},{"key":"IJSIR.2017100101-30","article-title":"Approximation performance of ant colony optimization for the TSP (1, 2) problem.","author":"X.Peng","year":"2015","journal-title":"International Journal of Computer Mathematics"},{"key":"IJSIR.2017100101-31","unstructured":"Samadhi, N. (2015). Parametrized Analysis of Bio-inspired Computation and the Traveling Salesperson Problem [Unpublished doctoral dissertation]. University of Adelaide, Australia."},{"key":"IJSIR.2017100101-32","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2002.802444"},{"key":"IJSIR.2017100101-33","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2011.06.002"},{"key":"IJSIR.2017100101-34","doi-asserted-by":"publisher","DOI":"10.4018\/jsir.2010070105"},{"key":"IJSIR.2017100101-35","doi-asserted-by":"publisher","DOI":"10.4018\/jsir.2012070102"},{"key":"IJSIR.2017100101-36","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548312000600"},{"key":"IJSIR.2017100101-37","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2009.2016570"}],"container-title":["International Journal of Swarm Intelligence Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.igi-global.com\/viewtitle.aspx?TitleId=186770","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,5]],"date-time":"2022-05-05T18:03:15Z","timestamp":1651773795000},"score":1,"resource":{"primary":{"URL":"http:\/\/services.igi-global.com\/resolvedoi\/resolve.aspx?doi=10.4018\/IJSIR.2017100101"}},"subtitle":[""],"short-title":[],"issued":{"date-parts":[[2017,10]]},"references-count":38,"journal-issue":{"issue":"4"},"URL":"https:\/\/doi.org\/10.4018\/ijsir.2017100101","relation":{},"ISSN":["1947-9263","1947-9271"],"issn-type":[{"value":"1947-9263","type":"print"},{"value":"1947-9271","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,10]]}}}