Journal Home Online First Current Issue Archive For Authors Journal Information 中文版

Strategic Study of CAE >> 2007, Volume 9, Issue 2

Ant Colony Algorithm:Survey and Prospect

1. School of Automation Science and Electrical Engineering, Beijing University of Aeronautics and Astronautics, Beijing   100083, China ;

2. College of Automation Engineering, Nanjing University of Aeronautics and Astronautics, Nanjing   210016, China ;

3. Center for Space Science and Applied Research, Chinese Academy of Sciences, Beijing   100080, China

Funding project:国家自然科学基金资助项目(60604009;60474499);航空科学基金资助项目(2006ZC51039);“三三三”工程基金重点资助项目(JS200204) Received: 2006-03-05 Revised: 2006-03-15

Next Previous

Abstract

 Ant colony algorithm is a novel category of bionic meta唱heuristic system, and parallel computation and positive feedback mechanism are adopted in this algorithm. Ant colony algorithm, which has strong robustness and is easy to combine with other methods in optimization, has wide application in various combined optimization fields. Based on the introduction of the mathematical model of basic ant colony algorithm, typical improved models and applications of the ant colony algorithm in the21st century are listed. Finally, based on the systematic address of model improvement, theoretical analysis, parallel realization, application field,  hardware realization and intelligent combination, the key issues and prospects of the ant colony algorithm are proposed in detail.

References

[ 1 ] Colorni A , Dorigo M , Maniezzo V , et al . Distributed optimization by ant colonies[A] . Proceedings of the 1st European Conference on Artificial Life[C] . 1991 .134 ~ 142 link1

[ 2 ] Dorigo M . Optimization , learning and natural algorithms [D] . Department of Electronics , Politecnico diMilano , Italy ,1992

[ 3 ] Bonabeau E , Dorigo M , Theraulaz G . Inspiration for optimization from social insect behavior [ J] . Nature , 2000 ,406(6) :39 ~ 42 link1

[ 4 ] Dorigo M , Maniezzo V , Colorni A . Ant system : optimization by a colony of cooperating agents[J] . IEEE Transaction on Systems , Man , and Cybernetics-Part B , 1996 ,26(1) :29 ~ 41 link1

[ 5 ] Dorigo M , Gambardella L M . Ant colony system : a cooperative learning approach to the traveling salesman problem [ J ] . IEEE Transactions on Evolutionary Computation ,1997 ,1(1) :53 ~ 66 link1

[ 6 ] 段海滨 ,王道波 .一种快速全局优化的改进蚁群算 法及仿真[J] .信息与控制 ,2004 ,33(2) :241 ~ 244 link1

[ 7 ] 段海滨 ,王道波 ,朱家强 ,等 .蚁群算法理论及应 用研究的进展[J] .控制与决策 ,2004 ,19(12) :1321 ~ 1326 ,1340 link1

[ 8 ] 段海滨 .蚁群算法原理及其应用[M] .北京 :科学出 版社 ,2005

[ 9 ] Holland J . Adaptation in Natural and Artificial Systems [M] . Ann Arbor : University of Michigan Press , 1975 ; MIT Press ,1992

[10] Dorigo M ,Bonabeau E ,Theraulaz G .Ant algorithms and stigmergy [ J] . Future Generation Computer Systems , 2000 ,16(8) :851 ~ 871 link1

[11] Gutjahr W J . A graph-based ant system and its convergence[J] . Future Generation Computer Systems , 2000 ,16(8) :873 ~ 888 link1

[12] Gutjahr W J .ACO algorithms with guaranteed convergence to the optimal solution [ J ] . Information Processing Letters ,2002 ,82(3) :145 ~ 153 link1

[13] Stüezle T ,Dorigo M .A short convergence proof for a class of ant colony optimization algorithms [ J ] . IEEE Transactions on Evolutionary Computation , 2002 , 6(4) : 358 ~ 365 link1

[14] Yoo J H ,La R J ,Makowski A M .Convergence results for ant routing [R] . Technical Report CSHCN 2003 - 46 , Institute for Systems Research , University of Maryland , College Park (MD) ,2003

[15] Yoo J H , La R J , Makowski A M . Convergence of ant routing algorithms-results for simple parallel network and perspectives[R] . Technical Report CSHCN 2003 - 44 , Institute for Systems Research , University of Maryland , College Park (MD) ,2003

[16] 孙 焘 ,王秀坤 ,刘业欣 ,等 .一种简单蚂蚁算法 及其收敛性分析[J] .小型微型计算机系统 , 2003 , 21(8) :1524 ~ 1526 link1

[17] 丁建立 ,陈增强 ,袁著祉 .遗传算法与蚂蚁算法融 合的马尔可夫收敛性分析[J] .自动化学报 , 2004 , 30(4) :659 ~ 634 link1

[18] Hou Y H , Wu Y W , Lu L J , et al . Generalized ant colony optimization for economic dispatch of power systems [A] .Proceedings of the 2002 International Conference on Power System Technology ,Vol 1 [C] .2002 .225 ~ 229

[19] Dorigo M , Stützle T . Ant Colony Optimization [ M] . Cambridge ,MA :MIT Press ,2003

[20] 段海滨 .蚁群算法及其在高性能电动仿真转台参数 优化中的应用研究[D] .南京 :南京航空航天大学 , 2005

[21] 秦 玲 .蚁群算法的改进与应用[D] .江苏扬州 :扬 州大学 ,2004 link1

[22] Chu S C ,Roddick J F ,Pan J S ,et al .Parallel ant colony systems [ J] . Lecture Notes in Artificial Intelligence , 2003 ,2871 :279 ~ 284 link1

[23] Guntsch M , Middendorf M , Scheuermann B , et al . Population based ant colony optimization on FPGA[A] . Proceedings of the 2002 IEEE International Conference on Field- Programmable Technology[C] .2002 .125 ~ 132 link1

[24] Scheuermann B , So K , Guntsch M , et al . FPGA implementation of population-based ant colony optimization [J] .Applied Soft Computing ,2004 ,4(4) :303 ~ 322 link1

[25] 段海滨 ,王道波 ,于秀芬 .蚁群算法硬件实现的研 究进展[J] .控制与决策 ,2006 ,21(12) :1380 ~ 1386 link1

[26] 李晓磊 ,邵之江 ,钱积新 .一种基于动物自治体的 寻优模式 : 鱼群算法[J] . 系统工程理论与实践 , 2002 ,22(11) :32 ~ 38 link1

[27] Eusuff M M , Lansey K E . Optimization of water distribution network design using the shuffled frog leaping algorithm[J] . Journal of Water Resources Planning and Management ,2003 ,129(3) :210 ~ 225 link1

[28] Sato T , Hagiwara M . Bee system : finding solution by a concentrated search [ A] . Proceedings of the IEEE International Conference on Systems , Man , and Cybernetics ,Vol 4 [C] .1997 .3954 ~ 3959 link1

[29] Canamero D .Modeling motivations and emotions as a basis for intelligent behavior [ A] . Proceedings of the 1st International Conference on Automation Agents [ C] , 1997 .145 ~ 155 link1

Related Research