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

山东大学学报(工学版) ›› 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

[1]	易云飞,苗剑,林郭隆,殷智. 基于牛顿力学和博弈论模型的粒子网络优化算法[J]. 山东大学学报(工学版), 2017, 47(1): 28-36.
[2]	王立宏,李强. 旅行商问题的一种选择性集成求解方法[J]. 山东大学学报(工学版), 2016, 46(1): 42-48.
[3]	戴红伟, 杨玉, 仲兆满, 李存华. 改进量子交叉免疫克隆算法及其应用[J]. 山东大学学报(工学版), 2015, 45(2): 17-21.
[4]	张飞,耿红琴. 基于混沌粒子群算法的车间作业调度优化[J]. 山东大学学报(工学版), 2013, 43(3): 19-22.
[5]	曾华1,崔文2,付连宁1,吴耀华1*. Lin-Kernighan算法初始解的启发式构造策略[J]. 山东大学学报(工学版), 2012, 42(2): 30-35.