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

A Heuristic Algorithm by Inserting Genetic Operators to Solve the Traveling Salesman Problem

作　　者：陈继业[1] 谢文平[2] 成礼智[1] 张君[3] 

机构地区：[1]国防科技大学理学院,长沙410073 [2]中南大学信息科学与工程学院,长沙410083 [3]邵阳学院数学系,湖南邵阳422000

出　　处：《计算机工程与应用》2006年第18期43-46,共4页Computer Engineering and Applications

摘　　要：算法复杂性理论中的NP完全问题是悬解的著名难题之一。旅行商问题作为经典的组合优化问题,实际中的应用非常广泛,但它却是一个NP完全问题。历年来,对它的一项主要研究工作,就是寻找一种既有高质量的解,又能快速收敛的近似算法。围绕这项研究,本文的主要创新是:首先,设计了求解该问题的一种嵌入遗传算子的启发式算法,它在本质上是经典插入算法的改良,但同时渗透了遗传算法思想;其次,对于这种近似算法,文章阐明算法具有多项式时间界O(n3),并且给出了评价其性能的不超过2的界估计及其严格的理论证明,因而它的算法理论基础是坚实的;最后,通过两个典型的算例计算结果的对比分析表明:该近似算法较之几种常用的启发式算法,其解的质量更高,又由于插入算法的程序设计方便快捷,因而它对于实际问题的计算需求无疑是极有意义的。NP complete problem in the complexity theory of algorithm is to hang as one of the famous hard problems to be solved.The TSP problem is considered as classical optimization grouping problem,which is widely used in practice,but it is real a difficult NP problem.Over the past years,the chief research on it is to find a proximate algorithms with the solution of high quality as well as quick convergent.The chief innovation of this article surround this research are as follows.Firstly,it has designed a heuristic algorithm by inserting genetic operations to solve this problem.Naturally,it is an improvement of inserting algorithm.At the same time,h reflects the genetic algorithm thought. Secondly,The algorithm is interpreted by the polynomial time bound O（n3） ,and has given detailed proof on bounded estimation which is less than two when evaluating its properties.So the basis of the algorithm is solid.Finally,by comparing the result of two typical calculate example ,it indicates that the solution of this proximate algorithm is higher in quality than other usual heuristic algnrithms.Because the programming of inserting algorithm is quick and convenient, the necessity of it toward practical calculation is meaningful.

关 键 词：旅行商问题 环游 插入算法 遗传算子 近似算法性能 

分 类 号：TP312[自动化与计算机技术—计算机软件与理论]