Convergence of Ant Colony Optimization on First-Order Deceptive Systems

被引：14

作者：

Chen, Yixin ^{[1
]}

Sun, Haiying ^{[2
]}

机构：

[1] Washington Univ, Dept Comp Sci & Engn, St Louis, MO 63130 USA

[2] Yangzhou Univ, Dept Comp Sci, Yangzhou 225009, Jiangsu, Peoples R China

来源：

2008 IEEE INTERNATIONAL CONFERENCE ON GRANULAR COMPUTING, VOLS 1 AND 2 | 2008年

关键词：

D O I：

10.1109/GRC.2008.4664719

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

Deceptive problems have been considered difficult for ant colony optimization (ACO) and it was believed that ACO will fail to converge to global optima of deceptive problems. This paper presents a convergence analysis of ACO on deceptive systems. This paper proves, for the first time, that ACO can achieve reachability convergence but not asymptotic convergence for a class of first order deceptive systems (FODS) without assuming a minimum pheromone at each iteration. Experimental results confirm the analysis.

引用

页码：158 / +

页数：2

共 10 条

[1]

[Anonymous], 2004, Ant colony optimization

[2] Search bias in ant colony optimization: On the role of competition-balanced systems [J].

Blum, C ;

Dorigo, M .

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2005, 9 (02) :159-174

[3]

Blum C, 2004, LECT NOTES COMPUT SC, V3172, P118

[4]

Blum C., 2004, THESIS

[5] Ant colony optimization: Introduction and recent trends [J].

Blum, Christian .

PHYSICS OF LIFE REVIEWS, 2005, 2 (04) :353-373

[6] Ant colony optimization theory: A survey [J].

Dorigo, M ;

Blum, C .

THEORETICAL COMPUTER SCIENCE, 2005, 344 (2-3) :243-278

[7] Graph-based Ant System and its convergence [J].

Gutjahr, WJ .

FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE, 2000, 16 (08) :873-888

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

Gutjahr, WJ .

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

[9] Ant algorithms: Theory and applications [J].

Shtovba, SD .

PROGRAMMING AND COMPUTER SOFTWARE, 2005, 31 (04) :167-178

[10] A short convergence proof for a class of ant colony optimization algorithms [J].

Stützle, T ;

Dorigo, M .

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2002, 6 (04) :358-365

← 1 →