《机电工程》杂志,月刊( 详细... )

中国标准连续出版物号 ISSN 1001-4551 CN 33-1088/TH
主办单位浙江省机电集团有限公司
浙江大学
主编赵 群
副 主 编唐任仲、罗向阳(执行主编)
总 经 理罗向阳
出 版浙江《机电工程》杂志社有限公司
地 址杭州市上城区延安路95号浙江省机电集团大楼二楼211、212室
电话Tel+86-571-87041360、87239525
E-mailmeem_contribute@163.com
国外发行中国国际图书贸易总公司
订阅全国各地邮局   国外代号M3135
国内发行浙江省报刊发行局
邮发代号32-68
广告发布登记证:杭上市管广发G-001号

在线杂志

当前位置: 机电工程 >>在线杂志

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

作者:章义刚1,王会颖2 日期:2008-06-23/span> 浏览:3521 查看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.



友情链接

浙江机械信息网