求解旅行商问题的嵌入遗传算子启发式算法

• 作者: 张君 成礼智 谢文平 陈继业
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 旅行商问题 环游 插入算法 遗传算子 近似算法性能
• 年，卷（期）: 2006,（18）
• 所属期刊栏目: 学术探讨
• 页码范围: 43-46
• 页数: 4页
• 分类号: TP312
• 字数: 4899字
• 语种: 中文
• DOI: 10.3321/j.issn:1002-8331.2006.18.014

摘要

算法复杂性理论中的NP完全问题是悬解的著名难题之一.旅行商问题作为经典的组合优化问题,实际中的应用非常广泛,但它却是一个NP完全问题.历年来,对它的一项主要研究工作,就是寻找一种既有高质量的解,又能快速收敛的近似算法.围绕这项研究,本文的主要创新是:首先,设计了求解该问题的一种嵌入遗传算子的启发式算法,它在本质上是经典插入算法的改良,但同时渗透了遗传算法思想;其次,对于这种近似算法,文章阐明算法具有多项式时间界O(n3),并且给出了评价其性能的不超过2的界估计及其严格的理论证明,因而它的算法理论基础是坚实的;最后,通过两个典型的算例计算结果的对比分析表明:该近似算法较之几种常用的启发式算法,其解的质量更高,又由于插入算法的程序设计方便快捷,因而它对于实际问题的计算需求无疑是极有意义的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	成礼智	国防科技大学理学院	54	731	14.0	26.0
2	张君	邵阳学院数学系	5	11	3.0	3.0
3	陈继业	国防科技大学理学院	3	14	2.0	3.0
4	谢文平	中南大学信息科学与工程学院	2	7	2.0	2.0