A proof of convergence for Ant algorithms

被引：50

作者：

Badr, A ^{[1
]}

Fahmy, A ^{[1
]}

机构：

[1] Cairo Univ, Fac Comp & Informat, Dept Comp Sci, Cairo, Egypt

来源：

INFORMATION SCIENCES | 2004年 / 160卷 / 1-4期

关键词：

Ant algorithms; branching random walk; branching Wiener process; birth-death process; convergence;

D O I：

10.1016/j.ins.2003.08.018

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

A proof of convergence for Ant algorithms is developed. Ant algorithms were modeled as branching random processes: the branching random walk and branching Wiener process to derive rates of birth and death of ant paths. Substitution is then carried out in birth-death processes which proves that a stable distribution is surely reached. This indicates that Ant algorithms converge with probability one. This analogy models Ant algorithms complexity parameters such as the number of cycles, the degrees of freedom of problem and the number of ants. (C) 2003 Elsevier Inc. All rights reserved.

引用

页码：267 / 279

页数：13

共 14 条

[1]

[Anonymous], 1992, OPTIMIZATION LEARNIN

[2]

ASMUSSEN A, 1983, BRANCHING PROCESSES

[3] Ant colonies for the travelling salesman problem [J].

Dorigo, M ;

Gambardella, LM .

BIOSYSTEMS, 1997, 43 (02) :73-81

[4] Ant system: Optimization by a colony of cooperating agents [J].

Dorigo, M ;

Maniezzo, V ;

Colorni, A .

IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART B-CYBERNETICS, 1996, 26 (01) :29-41

[5]

Dorigo M, 1999, NEW IDEAS OPTIMIZATI, P11

[6]

DORIGO M, 1991, ANT SYSTEM AUTOCATAL

[7]

HOEL SP, 1986, INTRO STOCHASTIC PRO

[8]

Kleinrock L., 1975, Queuing Systems, VI

[9]

LIGGETT T.M., 1985, Interacting particle systems, V276

[10]

NEY P, 1991, PROGR PROBABILITY SP, P3

← 1 2 →