research-article

Optimizing expected path lengths with ant colony optimization using fitness proportional update

Authors:

Matthias Feldmann,

Timo KötzingAuthors Info & Claims

FOGA XII '13: Proceedings of the twelfth workshop on Foundations of genetic algorithms XII

Pages 65 - 74

https://doi.org/10.1145/2460239.2460246

Published: 16 January 2013 Publication History

Abstract

We study the behavior of a Max-Min Ant System (MMAS) on the stochastic single-destination shortest path (SDSP) problem. Two previous papers already analyzed this setting for two slightly different MMAS algorithms, where the pheromone update fitness-independently rewards edges of the best-so-far solution.

The first paper showed that, when the best-so-far solution is not reevaluated and the stochastic nature of the edge weights is due to noise, the MMAS will find a tree of edges successfully and efficiently identify a shortest path tree with minimal noise-free weights. The second paper used reevaluation of the best-so-far solution and showed that the MMAS finds paths which beat any other path in direct comparisons, if existent. For both results, for some random variables, this corresponds to a tree with minimal expected weights.

In this work we analyze a variant of MMAS that works with fitness-proportional update on stochastic-weight graphs with arbitrary random edge weights from [0,1]. For δ such that any suboptimal path is worse by at least δ than an optimal path, then, with suitable parameters, the graph will be optimized after O(n³ ln n/δ over δ³ iterations (in expectation).

In order to prove the above result, the multiplicative and the variable drift theorem are adapted to continuous search spaces.

References

[1]

N. Attiratanasunthron and J. Fakcharoenphol. A running time analysis of an ant colony optimization algorithm for shortest paths in directed acyclic graphs. Information Processing Letters, 105:88--92, 2008.

Digital Library

[2]

L. Bianchi, M. Dorigo, L. M. Gambardella, and W. J. Gutjahr. A survey on metaheuristics for stochastic combinatorial optimization. Natural Computing, 8:239--287, 2009.

Digital Library

[3]

B. Doerr and L. Goldberg. Adaptive drift analysis. Algorithmica, 2011.

[4]

B. Doerr, A. Hota, and T. Kötzing. Ants easily solve stochastic shortest path problems. In Proceedings of the Conference on Genetic and Evolutionary Computation (GECCO'12), pages 17--24. ACM, 2012.

Digital Library

[5]

B. Doerr, D. Johannsen, and C. Winzen. Multiplicative drift analysis. In Proceedings of the Conference on Genetic and Evolutionary Computation (GECCO'10), pages 1449--1456. ACM, 2010.

Digital Library

[6]

M. Dorigo. Optimization, Learning and Natural Algorithms (in Italian). PhD thesis, Dipartimento di Elettronica, Politecnico di Milano, Milan, Italy, 1992.

[7]

M. Dorigo, V. Maniezzo, and A. Colorni. Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B, 26:29--41, 1996.

Digital Library

[8]

M. Dorigo and T. Stützle. Ant colony optimization. MIT Press, 2004.

Digital Library

[9]

W. J. Gutjahr. A graph-based ant system and its convergence. Future Generation Comper Systems, 16:873--888, 2000.

Digital Library

[10]

W. J. Gutjahr. ACO algorithms with guaranteed convergence to the optimal solution. Information Processessing Letters, 82:145--153, 2002.

[11]

W. J. Gutjahr. A converging ACO algorithm for stochastic combinatorial optimization. In Proceedings of the Symposium on Stochastic Algorithms: Foundations and Applications (SAGA'03), pages 10--25, 2003.

[12]

W. J. Gutjahr. S-ACO: An ant-based approach to combinatorial optimization under uncertainty. In Proceedings of the ANTS Conference (ANTS'04), pages 238--249. Springer, 2004.

[13]

B. Hajek. Hitting-time and occupation-time bounds implied by drift analysis with applications. Advances in Applied Probability, 14:502--525, 1982.

[14]

C. Horoba and D. Sudholt. Ant colony optimization for stochastic shortest path problems. In Proceedings of the Conference on Genetic and Evolutionary Computation (GECCO'10), pages 1465--1472. ACM, 2010.

Digital Library

[15]

D. Johannsen. Random Combinatorial Structures and Randomized Search Heuristics. PhD thesis, Universität des Saarlandes, 2010. Available online at http://scidok.sulb.uni-saarland.de/volltexte/2011/3529/pdf/Dissertation_3166_Joha_Dani_2010.pdf.

[16]

T. Kötzing, F. Neumann, H. Röglin, and C. Witt. Theoretical analysis of two ACO approaches for the traveling salesman problem. Swarm Intelligence, 6:1--21, 2012.

[17]

T. Kötzing, F. Neumann, D. Sudholt, and M. Wagner. Simple max-min ant systems and the optimization of linear pseudo-boolean functions. In Proceedings of Foundations of Genetic Algorithms (FOGA'11), pages 209--218. ACM, 2011.

Digital Library

[18]

B. Mitavskiy, J. E. Rowe, and C. Cannings. Preliminary theoretical analysis of a local search algorithm to optimize network communication subject to preserving the total number of links. In IEEE Congress on Evolutionary Computation, pages 1484--1491, 2008.

[19]

F. Neumann and C. Witt. Ant colony optimization and the minimum spanning tree problem. Theoretical Computer Science, 411:2406--2413, 2010.

Digital Library

[20]

P. S. Oliveto and C. Witt. Simplified drift analysis for proving lower bounds in evolutionary computation. Algorithmica, 59:369--386, 2011.

Digital Library

[21]

J. E. Rowe and D. Sudholt. The choice of the offspring population size in the (1, łambda ) EA. In Proceedings of the Conference on Genetic and Evolutionary Computation (GECCO'12), pages 1349--1356, 2012.

Digital Library

[22]

T. Stützle and H. H. Hoos. MAX-MIN ant system. Future Generation Computer Systems, 16:889--914, 2000.

Digital Library

Cited By

Doerr BKötzing T(2022)Lower Bounds from Fitness Levels Made EasyAlgorithmica10.1007/s00453-022-00952-w86:2(367-395)Online publication date: 28-Apr-2022
https://doi.org/10.1007/s00453-022-00952-w
Doerr BKötzing TKrawiec K(2021)Lower bounds from fitness levels made easyProceedings of the Genetic and Evolutionary Computation Conference10.1145/3449639.3459352(1142-1150)Online publication date: 26-Jun-2021
https://dl.acm.org/doi/10.1145/3449639.3459352
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
Show More Cited By

Index Terms

Optimizing expected path lengths with ant colony optimization using fitness proportional update
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Ant colony optimization for stochastic shortest path problems
GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation

We consider Ant Colony Optimization (ACO) for stochastic shortest path problems where edge weights are subject to noise that reflects delays and uncertainty. The question is whether the ants can find or approximate shortest paths in the presence of ...
Particle swarm optimizer, ant colony strategy and harmony search scheme hybridized for optimization of truss structures

A heuristic particle swarm ant colony optimization (HPSACO) is presented for optimum design of trusses. The algorithm is based on the particle swarm optimizer with passive congregation (PSOPC), ant colony optimization and harmony search scheme. HPSACO ...
A Simple Ant Colony Optimizer for Stochastic Shortest Path Problems

Ant Colony Optimization (ACO) is a popular optimization paradigm inspired by the capabilities of natural ant colonies of finding shortest paths between their nest and a food source. This has led to many successful applications for various combinatorial ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

FOGA XII '13: Proceedings of the twelfth workshop on Foundations of genetic algorithms XII

January 2013

198 pages

ISBN:9781450319904

DOI:10.1145/2460239

General Chairs:
Frank Neumann
The University of Adelaide, Australia
,
Kenneth De Jong
George Mason University, USA

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 January 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

FOGA '13

Sponsor:

SIGEVO

FOGA '13: Foundations of Genetic Algorithms XII

January 16 - 20, 2013

Adelaide, Australia

Acceptance Rates

Overall Acceptance Rate 72 of 131 submissions, 55%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
170
Total Downloads

Downloads (Last 12 months)25
Downloads (Last 6 weeks)3

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Doerr BKötzing T(2022)Lower Bounds from Fitness Levels Made EasyAlgorithmica10.1007/s00453-022-00952-w86:2(367-395)Online publication date: 28-Apr-2022
https://doi.org/10.1007/s00453-022-00952-w
Doerr BKötzing TKrawiec K(2021)Lower bounds from fitness levels made easyProceedings of the Genetic and Evolutionary Computation Conference10.1145/3449639.3459352(1142-1150)Online publication date: 26-Jun-2021
https://dl.acm.org/doi/10.1145/3449639.3459352
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
Bian CQian CYu YTang K(2021)On the robustness of median sampling in noisy evolutionary optimizationScience China Information Sciences10.1007/s11432-020-3114-y64:5Online publication date: 8-Apr-2021
https://doi.org/10.1007/s11432-020-3114-y
Witt CCoello Coello C(2020)Theory of estimation-of-distribution algorithmsProceedings of the 2020 Genetic and Evolutionary Computation Conference Companion10.1145/3377929.3389888(1254-1282)Online publication date: 8-Jul-2020
https://dl.acm.org/doi/10.1145/3377929.3389888
Bian CQian CTang KYu Y(2020)Running time analysis of the (1+1)-EA for robust linear optimizationTheoretical Computer Science10.1016/j.tcs.2020.07.001Online publication date: Jul-2020
https://doi.org/10.1016/j.tcs.2020.07.001
Sudholt D(2020)Analysing the Robustness of Evolutionary Algorithms to Noise: Refined Runtime Bounds and an Example Where Noise is BeneficialAlgorithmica10.1007/s00453-020-00671-0Online publication date: 25-Jan-2020
https://doi.org/10.1007/s00453-020-00671-0
Qian CBian CYu YTang KYao X(2020)Analysis of Noisy Evolutionary Optimization When Sampling FailsAlgorithmica10.1007/s00453-019-00666-6Online publication date: 20-Jan-2020
https://doi.org/10.1007/s00453-019-00666-6
Doerr BSutton AAuger AStützle T(2019)When resampling to cope with noise, use median, not meanProceedings of the Genetic and Evolutionary Computation Conference10.1145/3321707.3321837(242-248)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3321707.3321837
Witt CAuger AStützle T(2019)Theory of estimation-of-distribution algorithmsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3319619.3323367(1197-1225)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3319619.3323367
Show More Cited By

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten