research-article

Runtime Analysis of Ant Colony Optimization with Best-So-Far Reinforcement

Authors:

Walter J. Gutjahr,

Giovanni SebastianiAuthors Info & Claims

Volume 10, Issue 3

Pages 409 - 433

https://doi.org/10.1007/s11009-007-9047-1

Published: 01 September 2008 Publication History

Abstract

The paper provides some theoretical results on the analysis of the expected time needed by a class of Ant Colony Optimization algorithms to solve combinatorial optimization problems. A part of the study refers to some general results on the expected runtime of the considered class of algorithms. These results are then specialized to the case of pseudo-Boolean functions. In particular, three well known functions and a combination of two of them are considered: the OneMax, the Needle-in-a-Haystack, the LeadingOnes, and the OneMax-Needle-in-a-Haystack. The results obtained for these functions are also compared to those from the well-investigated (1+1)-Evolutionary Algorithm. The results shed light on a suitable parameter choice for the considered class of algorithms. Furthermore, it turns out that for two of the four studied problems, the expected runtime for the considered class, expressed in terms of the problem size, is of the same order as that for (1+1)-Evolutionary Algorithm. For the other two problems, the results are significantly in favour of the considered class of Ant Colony Optimization algorithms.

References

[1]

M. Birattari, P. Pellegrini, and M. Dorigo, “On the invariance of ant colony optimization,” Res. Rept, TR/IRIDIA/2006-025, 2006.

[2]

P. A. Borisovsky and A. V. Eremeev, “A study on performance of the (1+1)-evolutionary algorithm,” Proceedings on Foundations of Genetic Algorithms 7, Morgan Kaufmann: San Francisco, 2003.

[3]

M. Dorigo and C. Blum, “Ant colony optimization theory: a survey,” Theoretical Computer Science vol. 344 pp. 243–278, 2005.

Digital Library

[4]

M. Dorigo and G. Di Caro, “The ant colony optimization metaheuristic.” In D. Corne, M. Dorigo, and F. Glover (eds.), New Ideas in Optimization, pp. 11–32, McGraw-Hill: New York, 1999.

[5]

M. Dorigo, V. Maniezzo, and A. Colorni, “The ant system: an autocatalytic optimization process,” Res. Rept, pp. 91–016, Dept. of Electronics, Politecnico di Milano, Italy, 1991.

[6]

M. Dorigo, V. Maniezzo, and A. Colorni, “The ant system: optimization by a colony of cooperating agents,” IEEE Transactions On Systems, Man, and Cybernetics vol. 26 pp. 1–13, 1996.

Digital Library

[7]

M. Dorigo and T. Stützle, Ant Colony Optimization, MIT Press: Cambridge, 2004.

[8]

S. Droste, T. Jansen, and I. Wegener, “On the analysis of the (1+1) evolutionary algorithm,” Theoretical Computer Science vol. 276 pp. 51–81, 2002.

Digital Library

[9]

W. J. Gutjahr, “A graph–based ant system and its convergence,” Future Generations Computer Systems vol. 16 pp. 873–888, 2000.

Digital Library

[10]

W. J. Gutjahr, “ACO algorithms with guaranteed convergence to the optimal solution,” Information Processing Letters vol. 82 pp. 145–153, 2002.

[11]

W. J. Gutjahr, “A generalized convergence result for the graph–based ant system,” Probability in the Engineering and Informational Sciences vol. 17 pp. 545–569, 2003.

Digital Library

[12]

W. J. Gutjahr, “Theory of ant colony optimization: status and perspectives.” In MIC ’05 (6th Metaheuristics International Conference), Proceedings CD-ROM, 2005.

[13]

W. J. Gutjahr, “On the finite-time dynamics of ant colony optimization,” Methodology and Computing in Applied Probability vol. 8 pp. 105–133, 2006.

Digital Library

[14]

W. J. Gutjahr, “First steps to the runtime complexity analysis of ant colony optimization,” Computers & Operations Research 2007, click article in press at http://www.sciencedirect.com/science/journal/03050548

[15]

W. J. Gutjahr and G. Sebastiani, “Runtime analysis of ant colony optimization,” Res. Rept, 2007-03, Department of Mathematics, “Sapienza” University of Rome, 2007, available at www.mat.uniroma1.it/people/sebastiani/preprints.htm.

[16]

T. Jones and S. Forrest, “Fitness distance correlation as a measure of problem difficulty for genetic algorithms.” In Proc. 6th Int. Conf. on Genetic Algorithms, pp. 184–192, Morgan Kaufmann: San Mateo, 1995.

[17]

L. Kallel, B. Naudts, and C. R. Reeves, “Properties of fitness functions and search landscapes.” In L. Kallel, B. Naudts, and A. Rogers (eds.), Theoretical Aspects of Evolutionary Computing, pp. 174–206, Springer: Berlin, Heidelberg, New York, 1998.

[18]

V. Ladret, “Asymptotic hitting times for a simple evolutionary model of protein folding,” Journal of Applied Probability vol. 42 pp. 39–51, 2005.

[19]

D. Merkle and M. Middendorf, “Modeling the dynamics of ant colony optimization,” Evolutionary Computation vol. 10 pp. 235–262, 2002.

Digital Library

[20]

F. Neumann and C. Witt, “Runtime analysis of a simple ant colony optimization algorithm,” Res. Rept, CI-200/06, Dept. of Computer Science, University of Dortmund, Germany, 2006.

[21]

G. Sebastiani and G. L. Torrisi, “An extended ant colony algorithm and its convergence analysis,” Methodology and Computing in Applied Probability vol. 7 pp. 249–263, 2005.

Digital Library

[22]

T. Stützle and M. Dorigo, “A short convergence proof for a class of ACO algorithms,” IEEE Transactions on Evolutionary Computation vol. 6 pp. 358–365, 2002.

Digital Library

[23]

T. Stützle and H. H. Hoos, “The MAX-MIN Ant System and local search for the travelling salesman problem.” In T. Baeck, Z. Michalewicz, and X. Yao (eds.), Proc. ICEC ’97 Int. Conf. on Evolutionary Computation, pp. 309–314, 1997.

[24]

T. Stützle and H. H. Hoos, “MAX-MIN Ant System,” Future Generations Computer Systems vol. 16 pp. 889–914, 2000.

[25]

I. Wegener and C. Witt, “On the analysis of a simple evolutionary algorithm on quadratic pseudo-Boolean functions,” Journal of Discrete Algorithms vol. 3 pp. 61–78, 2005.

Cited By

Dang DOpris ASudholt D(2024)Level-Based Theorems for Runtime Analysis of Multi-objective Evolutionary AlgorithmsParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70071-2_16(246-263)Online publication date: 14-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-70071-2_16
Ivanova AAntipov DDoerr BSilva SPaquete L(2023)Larger Offspring Populations Help the (1 + (λ, λlambda)) Genetic Algorithm to Overcome the NoiseProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590514(919-928)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590514
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

Index Terms

Runtime Analysis of Ant Colony Optimization with Best-So-Far Reinforcement

Index terms have been assigned to the content through auto-classification.

Recommendations

Extended trail reinforcement strategies for ant colony optimization
SEMCCO'11: Proceedings of the Second international conference on Swarm, Evolutionary, and Memetic Computing - Volume Part I

Ant colony optimization (ACO) is a metaheuristic inspired by the foraging behavior of biological ants that was successfully applied for solving computationally hard problems. The fundamental idea that drives the ACO is the usage of pheromone trails for ...
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 ...
Ant colony optimization theory: a survey

Research on a new metaheuristic for optimization is often initially focused on proof-of-concept applications. It is only after experimental work has shown the practical interest of the method that researchers try to deepen their understanding of the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Methodology and Computing in Applied Probability

Methodology and Computing in Applied Probability Volume 10, Issue 3

Sep 2008

150 pages

ISSN:1387-5841

Issue’s Table of Contents

Copyright © 2008 Springer Science+Business Media, LLC.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 September 2008

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Dang DOpris ASudholt D(2024)Level-Based Theorems for Runtime Analysis of Multi-objective Evolutionary AlgorithmsParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70071-2_16(246-263)Online publication date: 14-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-70071-2_16
Ivanova AAntipov DDoerr BSilva SPaquete L(2023)Larger Offspring Populations Help the (1 + (λ, λlambda)) Genetic Algorithm to Overcome the NoiseProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590514(919-928)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590514
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

View Options

View options

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