research-article

Runtime analysis of an ant colony optimization algorithm for TSP instances

Author:

Yuren ZhouAuthors Info & Claims

IEEE Transactions on Evolutionary Computation, Volume 13, Issue 5

Pages 1083 - 1092

https://doi.org/10.1109/TEVC.2009.2016570

Published: 01 October 2009 Publication History

Abstract

Ant colony optimization (ACO) is a relatively new random heuristic approach for solving optimization problems. The main application of the ACO algorithm lies in the field of combinatorial optimization, and the traveling salesman problem (TSP) is the first benchmark problem to which the ACO algorithm has been applied. However, relatively few results on the runtime analysis of the ACO on the TSP are available. This paper presents the first rigorous analysis of a simple ACO algorithm called (1 + 1) MMAA (Max-Min ant algorithm) on the TSP. The expected runtime bounds for (1 + 1) MMAA on two TSP instances of complete and non-complete graphs are obtained. The influence of the parameters controlling the relative importance of pheromone trail versus visibility is also analyzed, and their choice is shown to have an impact on the expected runtime.

References

[1]

M. Dorigo, V. Maniezzo, and A. Colorni, "The ant system: An autocatalytic optimizing process," Dipartimento di Elettronica, Politecnico di Milano, Milan, Italy, Tech. Rep. 91-016, 1991.

[2]

M. Dorigo, V. Maniezzo, and A. Colorni, "Ant system: Optimization by a colony of cooperating agents," IEEE Trans. Syst., Man, Cybern.-Part B, vol. 26, no. 1, pp. 29-41, Feb. 1996.

Digital Library

[3]

M. Dorigo and T. Stützle, Ant Colony Optimization, 1st ed. Cambridge, MA: MIT Press, 2004, ch. 4, pp. 153-222.

Digital Library

[4]

M. Dorigo, M. Birattari, and T. Stützle, "Ant colony optimization," IEEE Comput. Intell. Mag., vol. 1, no. 4, pp. 28-39, Nov. 2006.

Digital Library

[5]

M. Dorigo and C. Blum, "Ant colony optimization theory: A survey," Theor. Comput. Sci., vol. 344, no. 2-3, pp. 243-278, 2005.

Digital Library

[6]

W. J. Gutjahr, "A graph-based ant system and its convergence," Future Gener. Comput. Syst., vol. 16, no. 9, pp. 873-888, 2000.

Digital Library

[7]

T. Stützle and M. Dorigo, "A short convergence proof for a class of ACO algorithms," IEEE Trans. Evol. Comput., vol. 6, no. 4, pp. 358-365, 2002.

Digital Library

[8]

W. J. Gutjahr, "On the finite-time dynamics of ant colony optimization," Methodology Comput. Appl. Probab., vol. 8, no. 1, pp. 105-133, 2006.

[9]

M. Zlochin, M. Birattari, N. Meuleau, and M. Dorigo, "Model-based search for combinatorial optimization: A critical survey," Ann. Oper. Res., vol. 131, no. 1-4, pp. 373-395, 2004.

[10]

S. Droste, T. Jansen, and I. Wegener, "On the analysis of the (1+1)-evolutionary algorithm," Theor. Comput. Sci., vol. 276, no. 1-2, pp. 51-81, 2002.

Digital Library

[11]

I. Wegener and C. Witt, "On the analysis of a simple evolutionary algorithm on quadratic pseudo-boolean function," J. Discrete Algorithms, vol. 3, no. 1, pp. 61-78, 2005.

[12]

H. G. Beyer, H. P. Schwefel, and I. Wegener, "How to analyze evolutionary algorithms," Theor. Comput. Sci., vol. 287, no. 1, pp. 101-130, 2002.

Digital Library

[13]

C. Witt, "Worst-case and average-case approximations by simple randomized search heuristic," in Proc. 22nd Annu. Symp. Theor. Aspects Comput. Sci. (STACS), LNCS vol. 3404. Stuttgart, Germany, Feb. 2005, pp. 44-56.

Digital Library

[14]

D. Sudholt, "Crossover is provably essential for the Ising model on trees," in Proc. Genetic Evol. Comput. Conf. (GECCO '05), Washington D.C., Jun. 2005, pp. 1161-1167.

Digital Library

[15]

J. He, X. Yao, and J. Li, "A comparative study of three evolutionary algorithms incorporating different amount of domain knowledge for node covering problems," IEEE Trans. Syst., Man Cybern., Part C, vol. 35, no. 2, pp. 266-271, 2005.

Digital Library

[16]

T. Friedrich, J. He, N. Hebbinghaus, F. Neumann, and C. Witt, "On improving approximate solutions by evolutionary algorithms," in Proc. Congr. Evol. Comput., Piscataway, NJ: IEEE Press, 2007, pp. 2614-2621.

[17]

T. Friedrich, J. He, N. Hebbinghaus, F. Neumann, and C. Witt, "Approximating covering problems by randomized search heuristics using multiobjective models," in Proc. Genetic Evol. Comput. Conf. (GECCO), London, U.K., Jul. 2007, pp. 797-804.

Digital Library

[18]

F. Neumann and C. Witt, "Runtime analysis of a simple ant colony optimization algorithm," in Proc. 17th Int. Symp. Algorithms Comput. (ISAAC), LNCS vol. 4288. Kolkata, India, Berlin, Germany: Springer-Verlag, Dec. 2006, pp. 618-627.

Digital Library

[19]

W. J. Gutjahr, "First steps to the runtime complexity analysis of ant colony optimization," Comput. Oper. Res., vol. 35, no. 9, pp. 2711-2727, 2008.

Digital Library

[20]

B. Doerr and D. Johannsen, "Refined runtime analysis of a basic ant colony optimization algorithm," in Proc. IEEE Congr. Evol. Comput., Piscataway, NJ: IEEE Press, 2007, pp. 501-507.

[21]

B. Doerr, F. Neumann, D. Sudholt, and C. Witt, "On the runtime analysis of the 1-ANT ACO algorithm," in Proc. Genetic Evol. Comput. Conf. (GECCO), London, U.K.: ACM, 2007, pp. 33-40.

Digital Library

[22]

W. J. Gutjahr and G. Sebastiani, "Runtime analysis of ant colony optimization with best-so-far reinforcement," Methodology Comput. Appl. Probab., vol. 10, no. 3, pp. 409-433, 2008.

[23]

F. Neumann, D. Sudholt, and C. Witt, "Analysis of different MMAS ACO algorithms on unimodal functions and plateaus," Swarm Intell., vol. 3, no. 1, pp. 35-68, 2009.

[24]

F. Neumann and C. Witt, "Ant colony optimization and the minimum spanning tree problem," in Proc. Learn. Intell. Optimization-LION 2, LNCS vol. 5313, Berlin, Germany: Springer-Verlag, pp. 153-166. Preliminary version: Electron. Colloq. Comput. Complexity (ECCC), Rep. no. 143.

Digital Library

[25]

N. Attiratanasunthron and J. Fakcharoenphol, "A running time analysis of an ant colony optimization algorithm for shortest paths in directed acyclic graphs," Inform. Process. Lett., vol. 105, no. 3, pp. 88-92, 2008.

Digital Library

[26]

E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys, The Traveling Salesman Problem, A Guided Tour of Combinatorial Optimization. 1st ed. New York: Wiley, 1985, ch. 1, pp. 1-16.

[27]

F. Neumann, D. Sudholt, and C. Witt, "Comparing variants of MMAS ACO algorithms on pseudo-Boolean functions," in Proc. Stoch. Local Search Algorithms, LNCS 4638. Brussels, Belgium: Springer-Verlag, Sep. 2007, pp. 61-75.

Digital Library

[28]

T. Stützle and H. H. Hoos, "MAX-MIN ant system," Future Gener. Comput. Syst., vol. 16, no. 8, pp. 889-914, 2000.

[29]

W. J. Gutjahr, "Mathematical runtime analysis of ACO algorithms: Survey on an emerging issue," Swarm Intell., vol. 1, no. 1, pp. 59-79, 2007.

[30]

S. Lin and B. Kernighan, "Efficient heuristic algorithm for the traveling salesman problem," Oper. Res., vol. 21, no. 2, pp. 498-516, 1973.

Digital Library

[31]

K. Helsgaun, "An effective implementation of Lin-Kernighan traveling salesman heuristic," Eur. J. Oper. Res., vol. 126, no. 1, pp. 106-130, Oct. 2000.

[32]

I. Wegener, "Simulated annealing beats metropolis in combinatorial optimization," in Proc. ICALP, LNCS vol. 3580. 2005, pp. 589-601.

Digital Library

[33]

K. Meer, "Simulated annealing versus metropolis for a TSP instance," Inform. Process. Lett., vol. 104, no. 6, pp. 216-219, 2007.

Digital Library

Cited By

Yu JYou XLiu S(2022)A heterogeneous guided ant colony algorithm based on space explosion and long–short memoryApplied Soft Computing10.1016/j.asoc.2021.107991113:PBOnline publication date: 3-Jan-2022
https://dl.acm.org/doi/10.1016/j.asoc.2021.107991
Lu MXu BNener BCong JShi J(2022)An accurate cell tracking approach with self-regulated foraging behavior of ant colonies in dynamic microscopy imagesApplied Intelligence10.1007/s10489-021-02424-052:2(1448-1460)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1007/s10489-021-02424-0
Doerr BNeumann F(2021)A Survey on Recent Progress in the Theory of Evolutionary Algorithms for Discrete OptimizationACM Transactions on Evolutionary Learning and Optimization10.1145/34723041:4(1-43)Online publication date: 13-Oct-2021
https://dl.acm.org/doi/10.1145/3472304
Show More Cited By

Runtime analysis of an ant colony optimization algorithm for TSP instances

Recommendations

An Effective Hybrid Ant Colony Algorithm for Solving the Traveling Salesman Problem
ICICTA '10: Proceedings of the 2010 International Conference on Intelligent Computation Technology and Automation - Volume 01

Ant colony optimization (ACO) is a relatively new random heuristic algorithm inspired by the behavior of real ant colony. It has been applied in many combinatorial optimization problems and the traveling salesman problem (TSP) is the basic problem to ...
A modified ant colony optimization algorithm for dynamic topology optimization

A modified ant colony optimization (MACO) algorithm implementing a new definition of pheromone and a new cooperation mechanism between ants is presented in this paper. The sensitivity of structural response to the presence of each element included in ...
On the Invariance of Ant Colony Optimization

Ant colony optimization (ACO) is a promising metaheuristic and a great amount of research has been devoted to its empirical and theoretical analysis. Recently, with the introduction of the hypercube framework, Blum and Dorigo have explicitly raised the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Evolutionary Computation

IEEE Transactions on Evolutionary Computation Volume 13, Issue 5

October 2009

249 pages

ISSN:1089-778X

Issue’s Table of Contents

Copyright © 2009.

Publisher

IEEE Press

Publication History

Published: 01 October 2009

Accepted: 19 February 2009

Revised: 10 December 2008

Received: 14 June 2008

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 29 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yu JYou XLiu S(2022)A heterogeneous guided ant colony algorithm based on space explosion and long–short memoryApplied Soft Computing10.1016/j.asoc.2021.107991113:PBOnline publication date: 3-Jan-2022
https://dl.acm.org/doi/10.1016/j.asoc.2021.107991
Lu MXu BNener BCong JShi J(2022)An accurate cell tracking approach with self-regulated foraging behavior of ant colonies in dynamic microscopy imagesApplied Intelligence10.1007/s10489-021-02424-052:2(1448-1460)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1007/s10489-021-02424-0
Doerr BNeumann F(2021)A Survey on Recent Progress in the Theory of Evolutionary Algorithms for Discrete OptimizationACM Transactions on Evolutionary Learning and Optimization10.1145/34723041:4(1-43)Online publication date: 13-Oct-2021
https://dl.acm.org/doi/10.1145/3472304
Benbaki RBenomar ZDoerr BKrawiec K(2021)A rigorous runtime analysis of the 2-MMASib on jump functionsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3449639.3459350(4-13)Online publication date: 26-Jun-2021
https://dl.acm.org/doi/10.1145/3449639.3459350
Lu MXu BQin WShi J(2020)Hybrid Ant Colony Optimization-Based Method for Focal of a Disease Segmentation in Lung CT ImagesAdvances in Swarm Intelligence10.1007/978-3-030-53956-6_19(215-222)Online publication date: 14-Jul-2020
https://dl.acm.org/doi/10.1007/978-3-030-53956-6_19
Lu MXu BNener B(2018)Tracking of multiple cells with ant pheromone field evolutionEngineering Applications of Artificial Intelligence10.1016/j.engappai.2018.03.01572:C(150-161)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.1016/j.engappai.2018.03.015
Peng XXia XLiao WGuo Z(2018)Running time analysis of the Pareto archived evolution strategy on pseudo-Boolean functionsMultimedia Tools and Applications10.1007/s11042-017-5466-377:9(11203-11217)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1007/s11042-017-5466-3
Huang HWu HZhang YLin ZHao Z(2017)Running-time Analysis of Ant System Algorithms with Upper-bound ComparisonInternational Journal of Swarm Intelligence Research10.4018/IJSIR.20171001018:4(1-17)Online publication date: 1-Oct-2017
https://dl.acm.org/doi/10.4018/IJSIR.2017100101
Wang YXu N(2017)A Hybrid Particle Swarm Optimization Method for Traveling Salesman ProblemInternational Journal of Applied Metaheuristic Computing10.4018/IJAMC.20170701048:3(53-65)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.4018/IJAMC.2017070104
Wu ZKolonko MMöhring R(2017)Stochastic Runtime Analysis of the Cross-Entropy AlgorithmIEEE Transactions on Evolutionary Computation10.1109/TEVC.2017.266771321:4(616-628)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1109/TEVC.2017.2667713
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents