基于混合遗传模拟退火算法求解TSP问题

doi:10.3778/j.issn.1002-8331.2010.29.011

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

基于混合遗传模拟退火算法求解TSP问题

杜宗宗，刘国栋

江南大学通信与控制工程学院，江苏无锡 214122

收稿日期:2009-03-25 修回日期:2009-05-25 出版日期:2010-10-11 发布日期:2010-10-11
通讯作者: 杜宗宗

Solution of TSP problem based on hybrid genetic simulated annealing algorithm

DU Zong-zong，LIU Guo-dong

College of Communication and Control Engineering，Jiangnan University，Wuxi，Jiangsu 214122，China

Received:2009-03-25 Revised:2009-05-25 Online:2010-10-11 Published:2010-10-11
Contact: DU Zong-zong

摘要/Abstract

摘要： TSP问题是典型的NP-hard组合优化问题，遗传算法是求解此类问题的一种方法，但它存在如何较快地找到全局最优解，并防止“早熟”收敛的问题。针对上述问题并结合TSP问题的特点，提出将遗传算法与模拟退火算法相结合形成遗传模拟退火算法。为了解决群体的多样性和收敛速度的矛盾，采用了部分近邻法来生成初始种群，生成的初始种群优于随机产生初始种群。仿真实验结果证明，该算法相对于基本遗传算法的收敛速度、搜索质量和最优解输出概率方面有了明显的提高。

Abstract: TSP is a classical NP-hard combinatorial optimization problem.Genetic algorithm is a method for solving this problem.But it is hard for genetic algorithm to find global optimization quickly and prevent premature convergence.This paper，in order to solve the problem，considers the characteristic of TSP，and puts forward a genetic simulated annealing algorithm，a hybrid of genetic and simulated annealing algorithm.In order to solve the inconsistency between diversity and convergent speed，this paper also adopts part greedy method to produce original population.The original population produced by this method is superior to the randomly produced original population.The simulation results demonstrate that，the proposed algorithm achieves considerable improvements，with respect to the basic genetic algorithm，in convergence speed，search quality and optimal solution output rate.

中图分类号:

TP301.6

杜宗宗，刘国栋. 基于混合遗传模拟退火算法求解TSP问题[J]. 计算机工程与应用, 2010, 46(29): 40-42.

DU Zong-zong，LIU Guo-dong. Solution of TSP problem based on hybrid genetic simulated annealing algorithm[J]. Computer Engineering and Applications, 2010, 46(29): 40-42.

[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.

基于混合遗传模拟退火算法求解TSP问题

Solution of TSP problem based on hybrid genetic simulated annealing algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics