求解旅行商问题的二阶段演化算法

doi:10.3778/j.issn.1002-8331.2010.29.012

计算机工程与应用 ›› 2010, Vol. 46 ›› Issue (29): 43-46.DOI: 10.3778/j.issn.1002-8331.2010.29.012

求解旅行商问题的二阶段演化算法

王玉亭，孙剑，李俊青，潘全科

聊城大学计算机学院，山东聊城 252059

收稿日期:2009-03-25 修回日期:2009-06-01 出版日期:2010-10-11 发布日期:2010-10-11
通讯作者: 王玉亭

Two-stage evolutionary algorithm for traveling salesman problem

WANG Yu-ting，SUN Jian，LI Jun-qing，PAN Quan-ke

School of Computer Science，Liaocheng University，Liaocheng，Shandong 252059，China

Received:2009-03-25 Revised:2009-06-01 Online:2010-10-11 Published:2010-10-11
Contact: WANG Yu-ting

摘要/Abstract

摘要： 对Inver-over算子进行了改进，提出了1st-Inver-over算子和2nd-Inver-over算子，实现了求解TSP问题的基于改进Inver-over算子的二阶段演化算法（Two-stage Inver-over EA）。在算法前期，只采用1st-Inver-over算子来保证算法的收敛速度；在算法后期，根据种群的多样性自适应地选取1st-Inver-over算子和2nd-Inver-over算子来协调算法的收敛速度和种群的多样性。在TSPLIB（Traveling Salesman Problem Library）中的典型实例上的实验结果表明，Two-stage Inver-over EA比经典的GT算法具有更好的收敛性和搜索效率。

Abstract: Based on the analysis of Inver-over operator，two improved Inver-over operators—1st-Inver-over operator and 2nd-Inver-over operator are proposed.Two-stage Evolutionary Algorithm based on improved Inver-over operator（Two-stage Inver-over EA） for TSP is implemented.In the prior period of the Two-stage Inver-over EA，in order to guarantee the convergence rate of the population，the algorithm only uses 1st-Inver-over operator.In the later period of the Two-stage Inver-over EA，in order to coordinate the convergence rate and the diversity of the population，the algorithm self-adaptively uses 1st-Inver-over operator and 2nd-Inver-over operator on the basis of the diversity of the population.The experiments results on TSPLIB（Traveling Salesman Problem Library） show that the Two-stage Inver-over EA is improved a lot on the convergence rate and efficiency compared with the classic GT algorithm.

中图分类号:

TP301.6

王玉亭，孙剑，李俊青，潘全科. 求解旅行商问题的二阶段演化算法[J]. 计算机工程与应用, 2010, 46(29): 43-46.

WANG Yu-ting，SUN Jian，LI Jun-qing，PAN Quan-ke. Two-stage evolutionary algorithm for traveling salesman problem[J]. Computer Engineering and Applications, 2010, 46(29): 43-46.

[1]	高芳^1，2，韩璞¹，翟永杰¹. 基于变异操作的蚁群算法用于连续函数优化[J]. 计算机工程与应用, 2011, 47(4): 5-8.
[2]	赵东旭，乐晓波. 采用改进的进化策略优化模糊Petri网参数[J]. 计算机工程与应用, 2011, 47(4): 29-32.
[3]	党正军，杜中军. 基于图裁减和图搜索的工作流图验证算法[J]. 计算机工程与应用, 2011, 47(4): 226-228.
[4]	戴海鹏，唐厚君. 求凸多边形直径的改进算法[J]. 计算机工程与应用, 2011, 47(3): 44-46.
[5]	崔明义. 小波分解的浮点数编码遗传算法消噪变异研究[J]. 计算机工程与应用, 2011, 47(2): 35-37.
[6]	于勇¹，张亚²，郭希娟²，封雪². 基于成功回路的凹多面体的剖分算法[J]. 计算机工程与应用, 2011, 47(2): 41-42.
[7]	李强，刘国栋. 多移动机器人的组队规划研究[J]. 计算机工程与应用, 2011, 47(2): 242-245.
[8]	林时来，刘光远，张慧玲. 蚁群算法在呼吸信号情感识别中的应用研究[J]. 计算机工程与应用, 2011, 47(2): 169-172.
[9]	鲁婷，王浩，姚宏亮. 一种基于中心文档的KNN中文文本分类算法[J]. 计算机工程与应用, 2011, 47(2): 127-130.
[10]	赵军¹，高满屯²，王三民². 求平面多边形集凸壳的方法[J]. 计算机工程与应用, 2011, 47(1): 205-207.
[11]	金婷婷，王波，宁爱兵. 最小顶点覆盖问题的竞争决策算法[J]. 计算机工程与应用, 2011, 47(1): 32-34.
[12]	赵成贵. 若干多级互连网络的扩展Cayley图模型[J]. 计算机工程与应用, 2010, 46(36): 118-121.
[13]	孙小军¹，刘三阳²，王志强³. 求解度约束最小生成树问题的新算法[J]. 计算机工程与应用, 2010, 46(36): 40-42.
[14]	陈庆燕. Bordat概念格构造算法的改进[J]. 计算机工程与应用, 2010, 46(35): 33-35.
[15]	李岩，王显山. 实时操作系统任务调度算法的硬件实现[J]. 计算机工程与应用, 2010, 46(35): 52-54.

求解旅行商问题的二阶段演化算法

Two-stage evolutionary algorithm for traveling salesman problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics