改进蚁群算法求解圆排列问题*

作者：章义刚1，王会颖2 日期：2008-06-23/span> 浏览：4237 查看PDF文档

改进蚁群算法求解圆排列问题*

章义刚1，王会颖2
（1.合肥学院 科研处,安徽 合肥 230022； 2.安徽财贸职业学院 计算机系，安徽 合肥 230601）

摘要：圆排列问题是典型的NP完全问题，且蚁群算法已成功地解决了许多组合优化的难题。介绍了一种求解圆排列问题的蚁群算法，并通过改变概率、下一个元素的选择方式以及采用分段交换,对求解圆排列问题的蚁群算法进行了优化。提出了一种改进的蚁群算法，并将其应用于求解圆排列问题。仿真实验的结果表明，该方法有效地改善了蚁群算法的搜索时间较长，且易于过早地收敛于非最优解的缺陷。
关键词：蚁群算法；改进蚁群算法；圆排列问题；求解圆排列问题的改进蚁群算法
中图分类号：TP301文献标识码：A文章编号：1001-4551(2008)05-0092-04

An improved ant colony algorithm of solving circle permutation problem
ZHANG Yigang1, WANG Huiying2
(1.Department of Scientific Research, Hefei University, Hefei 230022, China;
2.Department of Computer, Anhui Finance & Trade Vocational College, Hefei 230601,China)
Abstract: Circle permutation problem is a difficult NP problem. Ant colony algorithm is applied successfully to many hard combinational optimization problems. So, an ant colony algorithm of solving circle permutation problem was introduced. By changing the probability and the way of selecting the next element and adopting subsection exchange, an improved ant colony algorithm of solving circle permutation problem was put forward. The simulation results show that it greatly reduces the searching time of ant colony algorithm. It also effectively ameliorates the disadvantage of easily falling in local best of ant colony algorithm.
Key words: ant colony algorithm (ACA); improved ant colony algorithm (IACA); circle permutation problem; circle permutation problem improved ant colony algorithm (CPPIACA)
参考文献(Reference):
［1］DORIGO M, GAMBARDELLA L M. Ant colony system: a cooperative learning approach to the traveling salesman problem［J］. IEEE Trans on Evolutionary Computation,1997,1(1):53-66.
［2］COLORNI A, DORIGO M. Heuristics from nature for hard combinatorial optimization problems［J］. International Trans Operational Research,1996,3(1):1-21.
［3］STUTZLE T, HOOS H H. Maxmin ant system［J］. Future Generation Computer System,2000,16(8):889-914.
［4］吴斌,史忠植.一种基于蚁群算法的TSP问题分段求解算法［J］.计算机学报,2001,24(12):1328-1333
［5］高尚,杨静宇,吴小俊,等.圆排列问题的蚁群模拟退火算法［J］.系统工程理论与实践，2004,8(8)：102-106.
［6］王晓东.计算机算法设计与分析：第2版［M］.北京:电子工业出版社，2005.
［7］徐精明，曹先彬，王煦法.蚁群算法求解问题时易产生的误区及对策［J］.计算机工程,2004,30(16):25-26.