Runtime Analysis of Ant Colony Optimization with Best-So-Far Reinforcement |
| |
Authors: | Walter J Gutjahr Giovanni Sebastiani |
| |
Institution: | (1) Department of Statistics and Decision Support Systems, University of Vienna, Universitaetsstrasse 5/9, 1010 Vienna, Austria;(2) Istituto per le Applicazioni del Calcolo “Mauro Picone”, CNR, Viale del Policlinico 137, 00161 Rome, Italy;(3) Mathematics Department, “Sapienza” University of Rome, Piazzale Aldo Moro 5, 00185 Rome, Italy |
| |
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.
|
| |
Keywords: | Analysis of algorithms Combinatorial optimization Stochastic algorithms Hitting times Markov processes |
本文献已被 SpringerLink 等数据库收录! |
|