On the finite-time dynamics of ant colony optimization

被引：34

作者：

Gutjahr, Walter J. ^{[1
]}

机构：

[1] Univ Vienna, Dept Stat & Decis Support Syst, Vienna, Austria

来源：

METHODOLOGY AND COMPUTING IN APPLIED PROBABILITY | 2006年 / 8卷 / 01期

关键词：

ant colony optimization; convergence speed; probabilistic algorithms; stochastic approximation; stochastic optimization;

D O I：

10.1007/s11009-006-7291-4

中图分类号：

O21 [概率论与数理统计]; C8 [统计学];

学科分类号：

020208 ; 070103 ; 0714 ;

摘要：

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.

引用

页码：105 / 133

页数：29

共 36 条

[21] ACO algorithms with guaranteed convergence to the optimal solution [J].

Gutjahr, WJ .

INFORMATION PROCESSING LETTERS, 2002, 82 (03) :145-153

[22]

GUTJAHR WJ, 2006, 200601 U VIENN DEP S

[23]

GUTJAHR WJ, IN PRESS COMPUTER OP

[24]

Hadji R., 2000, Ant colonies for the set covering problem, P63

[25]

Kushner H, 2003, STOCHASTIC APPROXIMA

[26] Modeling the dynamics of ant colony optimization [J].

Merkle, D ;

Middendorf, M .

EVOLUTIONARY COMPUTATION, 2002, 10 (03) :235-262

[27]

Merkle D, 2004, LECT NOTES COMPUT SC, V3172, P95

[28]

MONTGOMERY J, 2002, TR0207 BOND U

[29]

Mühlenbein H, 2001, NAT COMP SER, P135

[30]

Prügel-Bennett A, 2001, NAT COMPUT SER, P59

← 1 2 3 4 →