文档介绍：杂交遗传算法求解旅行商问题的动态规划的研究PHAMDinhThanhFacultyofMathematics-Physics–InformaticTayBacUniversitySonLa,******@municationTechnologyHaNoiUniversityofScienceandTechnologyHaNoi,******@,@摘要—旅行商问题(TSP)是一个众所周知的NP-hard问题。许多算法被开发出来解决这个问题,并在合理的时间内给出几乎最优的解。本文提出了一个关于用动态规划(DP)方法来求解TSP的组合遗传算法(GA)问题的调查方案。我们还为这个问题设置了GA和DP之间的组合,并在来自TSP-lib的7个欧几里德实例上进行了实验。实验结果重点介绍了实验算法与遗传算法的效率比较。关键词:旅行商问题;遗传算法;动态规划;分支定界算法。,在调度、车辆路径、VLSI布局等领域有着广泛的应用。该问题是在1930年被首次制定,并成为最深入研究的优化问题之一。到目前为止,研究人员在这个问题上已经获得了许多重大的研究结果。本文介绍了杂交遗传算法求解TSP问题的动态规划概述,然后提出一个组合GA与DP(称为CGADP)解决这个问题。在CGADP中,通过遗传算法找到的解决方案将被选择用于应用基于DP的局部搜索。我们在来自TSP-lib的7个欧几里德实例上实验了CGADP[22],并将结果与GA[5]进行比较。实验结果表明,CGADP的解决方案优于GA[5]的最小和平均成本值。CGADP求解的收敛速度比GA快。本文的其余部分组织如下。在第二部分,我们概述了TSP。第三节调查组合GA与DP的方差,用于求解TSP。我们的实验细节以及计算和比较结果在第四节中给出。在第四和第五节中我们对这项工作的未来延伸会做出一些讨论。:令1,2,...,n为n个城市的标签,c=ci,j为n×n成本矩阵,其中ci,j表示从城市i到城市j的旅行成本。TSP是找到具有最小成本的n城市封闭游览的问题,使得每个城市被访问恰好一次。旅行的总成本A是:An=i=1n-1ci,i+,1(1)TSP被定义为找到n个城市的排列,其具有最小成本。这个问题被称为NP-hard[2,4,5]。人们已经提出了许多算法来解决这个问题[2,3,4,5,7,10,11,12,14,15,17]。其中有两种解决TSP的主要方法:精确和近似。精确的方法几乎总是基于动态规划,分支和绑定,整数线性规划。这些方法给出了TSP的最佳解决方案。然而,基于这些方法的算法具有指数运行时间,[1]指出动态规划需要运行时间。因此,他们只能解决具有少量顶点的TSP算法,使用分支和绑定方法仅能够给出40-60个城市集的解决方案,而使用线性规划解决方案可以解决200个城市集的问题。在试图解决更大问题的情况下,特别是在这样的NP-hard问题中,近年来的研究者已经注意到近似方法,提出了许多近似方法来解决TSP,如2-opt,3-opt[2],模拟退火[3],禁忌搜索[4],基于自然的优化算法和基于群体的优化算法:遗传算法[16,19,20],进化计算[5],神经网络[6],DNA计算[9],群优化算法:蚁群优化[7],蜂群优化[8],基于这些方法的算法可以解决大型实例,并在合理的时间内提供接近最优解的近似解。除了上述原始近似方法之外,存在组合基本启发式方法缩放元启发式的不同方法。在[18],作者应用本地搜索启发法到GA解决TSP。他们使用的本地搜索方法是2-opt。他们提出了三个交叉操作员(PMX,OX,POS)和两个变异算子(IVM,EM),然后将2-opt与一对交叉和变异操作器轮流组合。在kroA100,kroB100和kroC100实例上实验他们的算法后,他们发现两个遗传算子(IVM和POS)与2-选择的组合给出了比其他解决TSP问题更好的解决方案。他们还实现了这种组合,但使用的是3-opt而不是2-opt,并得出结论,与3-opt的组合给予了更好的解决方案,但在更多的时间收敛到全局最优。BerndFreisleben等人利用本地搜索提出了遗传局部搜索(GLS)的TSP[20]。他们的算法中使用登山者的想法在GA中开发本地搜索。他们的实验表明,GLS不仅运行时间更短,而且成本比[21]多。除了精确和近似方法,有一种不同的办法是这两种方法的组合,其中GA与DP的组合是