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

陈继业; 谢文平; 成礼智; 张君

首页> 中文期刊> 《计算机工程与应用》 >求解旅行商问题的嵌入遗传算子启发式算法

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

开具论文收录证明 >>

期刊封面封底目录下载 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

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

著录项

来源
《计算机工程与应用》 |2006年第18期|43-46|共4页
作者
陈继业; 谢文平; 成礼智; 张君;
展开▼
作者单位

国防科技大学理学院;

长沙;

410073;

中南大学信息科学与工程学院;

长沙;

410083;

国防科技大学理学院;

长沙;

410073;

邵阳学院数学系;

湖南;

邵阳;

422000;

展开▼
原文格式 PDF
正文语种 chi
中图分类程序语言、算法语言;
关键词
旅行商问题; 环游; 插入算法; 遗传算子; 近似算法性能;

相似文献

中文文献
外文文献
专利

1. 用遗传算法求解旅行商问题时遗传算子的设计 [J] . 黄艳峰 ,范云芝 . 西南民族大学学报（自然科学版） . 2006,第001期
2. 求解配送收集旅行商问题的启发式算法 [J] . 霍佳震 ,张磊 . 同济大学学报（自然科学版） . 2006,第001期
3. 求解旅行商问题的两个启发式算法的改进 [J] . 苏丽杰 ,聂义勇 ,李长军 . 计算机应用 . 2004,第0z1期
4. 旅行商问题的一种启发式算法 [J] . 洪玉振 ,张际东 ,李明 . 河海大学学报（自然科学版） . 2007,第002期
5. 关于旅行商问题的若干启发式算法的性能比分析 [J] . 刘剑平 . 华东理工大学学报（自然科学版） . 2005,第006期
6. 旅行商问题的近优解评价方法——浅析启发式算法的有效性 [C] . 苏丽杰 ,聂义勇 . 第四届中国Rough集与软计算学术研讨会 . 2004
7. 新型启发式算法求解旅行商问题及其衍生问题 [A] . 郑硕 . 2016

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

摘要

著录项

相似文献

相关主题

期刊订阅