On the Finite-Time Dynamics of Ant Colony Optimization |
| |
Authors: | Walter J Gutjahr |
| |
Institution: | (1) Department of Statistics and Decision Support Systems, University of Vienna, Vienna, Austria |
| |
Abstract: | An analytical framework for investigating the finite-time dynamics of ant colony optimization (ACO) under a fitness-proportional
pheromone update rule on arbitrary construction graphs is developed. A limit theorem on the approximation of the stochastic
ACO process by a deterministic process is demonstrated, and a system of ordinary differential equations governing the process
dynamics is identified. As an example for the application of the presented theory, the behavior of ACO on three different
construction graphs for subset selection problems is analyzed and compared for some basic test functions. The theory enables
first rough theoretical predictions of the convergence speed of ACO.
AMS 2000 Subject classification 68W20, 68W40 |
| |
Keywords: | Ant colony optimization Convergence speed Probabilistic algorithms Stochastic approximation Stochastic optimization |
本文献已被 SpringerLink 等数据库收录! |
|