一种求解旅行商问题的迭代改进蚁群优化算法

山东大学学报(工学版) ›› 2012, Vol. 42 ›› Issue (1): 6-11.

一种求解旅行商问题的迭代改进蚁群优化算法

蔡荣英,王李进,吴超,钟一文*

福建农林大学计算机与信息学院, 福建福州 350002

收稿日期:2011-04-15 出版日期:2012-02-20 发布日期:2011-04-15
通讯作者: 钟一文(1968- ),男,福建上杭人,博士,教授,主要研究方向为计算智能和生物信息学. Email: yiwenzhong@fjau.edu.cn
作者简介:蔡荣英(1969- ),女,福建南平人,高级实验师,主要研究方向为运筹与优化、计算智能.Email: rongyingcai@fjau.edu.cn
基金资助:
福建省自然科学基金项目(2008J0316)

A kind of iterative improvement based ant colony optimization algorithm for the traveling salesman problem

CAI Rong-ying, WANG Li-jin, WU Chao, ZHONG Yi-wen*

College of Computer and Information, Fujian Agriculture and Forestry University, Fuzhou 350002, China

Received:2011-04-15 Online:2012-02-20 Published:2011-04-15

摘要/Abstract

摘要：

传统的蚁群优化算法每次都从头开始构造新解,无条件地接收选择的解部件,该策略削弱了算法的局部求精能力。针对该不足,提出了一种求解旅行商问题的迭代改进蚁群优化算法。在构造解的过程中,蚂蚁始终记忆一个完整的解,并且只接受能够改进解的候选城市。使用解的部分重构策略来保持种群的多样性,以避免早熟收敛。仿真结果表明迭代改进蚁群优化算法能在更少的迭代次数内获得更好的解。

关键词: 蚁群优化算法, 迭代改进, 旅行商问题, 集中性, 多样性

Abstract:

Classical ant colony optimization algorithms build solutions by starting with an empty initial solution, and unconditionally accepting selected components. This has become a natural restriction of its intensification ability. To overcome this shortage, an iterative improvement based ant colony optimization algorithm was presented for the traveling salesman problem. In the process of constructing the solution, the ant always memorizes a complete solution; and it adopts a candidate city only when such an adoption can improve the solution. Reconstructing of a partial solution was used to keep the diversity of swarm and avoid premature convergence. Simulation results showed that the proposed algorithm can obtain better solutions within less iteration numbers.

Key words: ant colony optimization algorithm, iterative improvement, traveling salesman problem, intensification, diversification

蔡荣英,王李进,吴超,钟一文*. 一种求解旅行商问题的迭代改进蚁群优化算法[J]. 山东大学学报(工学版), 2012, 42(1): 6-11.

CAI Rong-ying, WANG Li-jin, WU Chao, ZHONG Yi-wen*. A kind of iterative improvement based ant colony optimization algorithm for the traveling salesman problem[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2012, 42(1): 6-11.

参考文献

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

本文评价

推荐阅读 10

[1]	李侃 . 嵌入式相贯线焊接控制系统开发与实现[J]. 山东大学学报(工学版), 2008, 38(4): 37 -41 .
[2]	来翔 . 用胞映射方法讨论一类MKdV方程[J]. 山东大学学报(工学版), 2006, 36(1): 87 -92 .
[3]	余嘉元1 , 田金亭1 , 朱强忠2 . 计算智能在心理学中的应用[J]. 山东大学学报(工学版), 2009, 39(1): 1 -5 .
[4]	陈瑞,李红伟,田靖. 磁极数对径向磁轴承承载力的影响[J]. 山东大学学报(工学版), 2018, 48(2): 81 -85 .
[5]	王波,王宁生 . 机电装配体拆卸序列的自动生成及组合优化[J]. 山东大学学报(工学版), 2006, 36(2): 52 -57 .
[6]	张英,郎咏梅,赵玉晓,张鉴达,乔鹏,李善评 . 由EGSB厌氧颗粒污泥培养好氧颗粒污泥的工艺探讨[J]. 山东大学学报(工学版), 2006, 36(4): 56 -59 .
[7]	Yue Khing Toh1 ， XIAO Wendong2 ， XIE Lihua1 . 基于无线传感器网络的分散目标跟踪：实际测试平台的开发应用（英文）[J]. 山东大学学报(工学版), 2009, 39(1): 50 -56 .
[8]	孙炜伟,王玉振. 考虑饱和的发电机单机无穷大系统有限增益镇定[J]. 山东大学学报(工学版), 2009, 39(1): 69 -76 .
[9]	孙玉利,李法德,左敦稳,戚美 . 直立分室式流体连续通电加热系统的升温特性[J]. 山东大学学报(工学版), 2006, 36(6): 19 -23 .
[10]	王勇, 谢玉东. 大流量管道煤气的控制技术研究 [J]. 山东大学学报(工学版), 2009, 39(2): 70 -74 .