Refined runtime analysis of a basic ant colony optimization algorithm
作者： Benjamin Doerr , Daniel Johannsen
关键词:
摘要: Neumann and Witt (2006) analyzed the runtime of basic ant colony optimization (ACO) algorithm 1-Ant on pseudo-Boolean problems. For problem OneMax they showed how depends evaporation factor. In particular, proved a phase transition from exponential to polynomial runtime. this work, we simplify view by an appropriate translation pheromone model. This results in profound simplification update rule and, that, refinement Witt. show bound gradually changes inside transition.
mpg.de
sci-hub.se 参考文章(21)
Dirk Sudholt, Benjamin Doerr, Carsten Witt, Frank Neumann, On the influence of pheromone updates in ACO algorithms Deutsche Nationalbibliothek. ,(2007) , 10.17877/DE290R-8719
Nils Hebbinghaus, L. Darrell Whitley, Benjamin Doerr, Juan J. Merelo-Guervós, Xin Yao, Edmund Burke, Frank Neumann, Thomas Ph. Runarsson, Hans G. Beyer, Speeding Up Evolutionary Algorithms Through Restricted Mutation Operators Untitled Event. pp. 978- 987 ,(2006)
Carsten Witt, Worst-case and average-case approximations by simple randomized search heuristics symposium on theoretical aspects of computer science. pp. 44- 56 ,(2005) , 10.1007/978-3-540-31856-9_4
Oliver Giel, Ingo Wegener, Evolutionary Algorithms and the Maximum Matching Problem symposium on theoretical aspects of computer science. pp. 415- 426 ,(2003) , 10.1007/3-540-36494-3_37
Carsten Witt, Frank Neumann, Ant Colony Optimization and the Minimum Spanning Tree Problem Electronic Colloquium on Computational Complexity. ,vol. 143, pp. 1- 12 ,(2006)
Benjamin Doerr, Nils Hebbinghaus, Frank Neumann, Speeding Up Evolutionary Algorithms Through Restricted Mutation Operators Parallel Problem Solving from Nature - PPSN IX. pp. 978- 987 ,(2006) , 10.1007/11844297_99
M. Birattari, T. Stutzle, M. Dorigo, Ant Colony Optimization ,(2004)
Frank Neumann, Ingo Wegener, Randomized Local Search, Evolutionary Algorithms, and the Minimum Spanning Tree Problem genetic and evolutionary computation conference. pp. 713- 724 ,(2004) , 10.1007/978-3-540-24854-5_73
Frank Neumann, Expected runtimes of evolutionary algorithms for the Eulerian cycle problem congress on evolutionary computation. ,vol. 35, pp. 2750- 2759 ,(2004) , 10.1016/J.COR.2006.12.009
Walter J. Gutjahr, On the Finite-Time Dynamics of Ant Colony Optimization Methodology and Computing in Applied Probability. ,vol. 8, pp. 105- 133 ,(2006) , 10.1007/S11009-006-7291-4