计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (11): 53-55.DOI: 10.3778/j.issn.1002-8331.2009.11.016

• 研究、探讨 • 上一篇    下一篇

基于模拟退火算法的多道逆向蚁群算法

岳 凤1,刘希玉2,张 萍1   

  1. 1.山东师范大学 信息科学与工程学院,济南 250014
    2.山东师范大学 管理学院,济南 250014
  • 收稿日期:2008-03-03 修回日期:2008-05-15 出版日期:2009-04-11 发布日期:2009-04-11
  • 通讯作者: 岳 凤

Multiple converse ant colony algorithm based on simulated annealing

YUE Feng1,LIU Xi-yu2,ZHANG Ping1   

  1. 1.School of Information Science and Engineering,Shandong Normal University,Jinan 250014,China
    2.School of Management,Shandong Normal University,Jinan 250014,China
  • Received:2008-03-03 Revised:2008-05-15 Online:2009-04-11 Published:2009-04-11
  • Contact: YUE Feng

摘要: 为克服现有蚁群算法运算过程中易出现停滞现象、收敛速度慢等缺点,提出了一种基于模拟退火策略的多道逆向蚁群算法。通过向原始蚁群中引入逆向蚂蚁,并结合模拟退火思想确定蚁群中逆向蚂蚁的数目,来提高算法全局寻优能力。在算法执行过程中一组蚂蚁分成几群并行运算,通过交换策略,有效地利用了当前最优解,提高了算法收敛速度。将该算法应用于旅行商问题的求解,仿真实验结果表明该算法的全局寻优能力和收敛速度都得到了很大改善。

关键词: 蚁群算法, 模拟退火, 旅行商问题, 多道蚁群算法

Abstract: In order to get over the disadvantages of stagnation behavior and the slow convergence speed,a multiple converse ant colony algorithm based on simulated annealing is proposed.Inducting converse ants into the ant colony and the number of converse ants is adjusted by simulated annealing,the ability of searching for global optimal solution can be improved.Parallel running of a group of colonies are used in such a way that they can share their information efficiently,this information can be utilized by colonies via an exchange colonies,the ability of stagnation behavior can be improved.Using this algorithm to solve the traveling salesman problem shows that the ability of optimization and the convergence speed have improved a lot.

Key words: ant colony algorithm, simulated annealing, traveling salesman problem, multiple ant colony algorithms