TSP问题及几种常见算法的比较研究

TSP问题及几种常见算法的比较研究

第5卷第5期2010年5月

长春理工大学学报

JournalofChangchunUniversityofScienceandTechnologyVol.5No.5May.2010

TSP问题及几种常见算法的比较研究

王敏（沈阳工程学院基础部，辽宁沈阳，110136）

［摘

要］TSP问题是一个经典的NP完全问题，它在众多领域中都有着广泛而有价值的实际应用，所以一直有众多的学者对其进行研究。从介绍TSP问题入手，从动态规划法、分枝界限法、遗传算法、蚁群算法等四种常见算法开始，在概述了各种算法的基本原理、程序设计的基本步骤的基础上，对各种算法的优缺点、时间复杂度、适用范围等几个方面进行了分析和比较。

［关键词］TSP问题；动态规划法；分枝界限法；遗传算法；蚁群算法［中图分类号］O158

［文献标识码］A

［作者简介］王敏（1968-），女，硕士研究生，副教授，研究方向为离散数学和大学数学教育。

一、概述

TSP问题也称为巡回旅行商问题，是一个易于描述但难于解决的古老而著名的难题之一。TSP问题可以描述为：给定n个城市和它们两者之间的直达距离，寻求一个闭合的旅程，使得该旅行线路经过每个城市一次且仅一次，而且总的旅行距离最短。TSP问题的数学描述即为：如何在一个赋权图中，寻求权和最小的哈密尔顿回路问题。现实生活中有很多实际问题可以转化为旅行商问题，如邮路问题、电路布线问题、输油管路铺设问题、连锁店的货物配送路线问题、产品的生产安排问题等等。因此，研究TSP问题的求解方法具有重要的

(1)判断图理论意义和实际意义。求解TSP问题的难度在于：G是否是哈密尔图。目前既无有效的算法，也不知道这样的

有效算法是否存在。在不知道图G是否是哈密尔图的情况下去寻求图G的哈密尔回路自然是非常盲目的。（2）即使已知图G是一个哈密尔图，虽然从理论上讲求解TSP问题是可以通过穷举法来解决的，但问题是在TSP问题中，由于所有旅行的组合数是(n-1)!/2，当城市数n很大时，TSP问题的搜索空间会随着城市数n的增大而急剧增加，所以，使用常规的穷举法求解TSP问题的最优解就成了一个NP难问题。于是，寻求TSP问题的近似解的优化算法就成了现实而可行的解决方法了。迄今为止，所提出求解最佳TSP回路的各种算法可以分为两大类：第一类是传统的确定性算法（精确算法）。如：动态规划法、分枝界限法等；第二类是现代流行的智能算法，即近似算法。如：遗传算法、模拟退火算法、蚁群算法、人工神经网络算法、最近邻搜索算法等。

复杂度为）。随着问题规模的扩大所需的空间会急剧增

加，故一般除了很小规模的问题外，几乎不予采用。

（二）分枝界限法

分枝界限法是由三栖学者查理德 卡普（RichardM.Karp）在20世纪60年代发明的。分枝界限法是一个用途十分广泛的算法，其基本思想是对有约束条件的最优化问题的所有可行解（数目有限）空间进行搜索。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集（称为分枝），并为每个子集内的解的值计算一个下界或上界（称为定界）。在每次分枝后，对凡是界限超出已知可行解值的那些子集不再做进一步分枝。这样，解的许多子集（即搜索树上的许多结点）就可以不予考虑了，从而缩小了搜索范围。这一过程一直进行到找出可行解为止，该可行解的值不大于任何子集的界限。因此，这种算法一般可以求得最优解。分枝定界法的算法步骤为（假设问题的目标为最小化）：

（1）设定目前最优解的值Z=∞。

（2）根据分枝法则，从尚未被洞悉的结点（局部解）中选择一个结点，并在此结点的下一阶层中分为几个新的结点。

（3）计算每一个新分枝出来的结点的下限值。

（4）对每一节点进行洞悉条件测试。第一，此结点不可能包含可行解；第二，若此结点的下限值大于等于Z值或已找到在此结点中，具有最小下限值的可行解，则此结点可洞悉而不再被考虑；否则，则需比较此可行解与Z值，若前者较小，则需更新Z值，并以此为可行解的值。若结点满足以上的任意一个条件，则此结点可洞悉而不再被考虑。

（5）判断是否仍有尚未被洞悉的结点，如果有，则进行步骤二，如果已无尚未被洞悉的结点，则演算停止，并得到最优解。

分枝界限法从最小下界开始分枝，每次算完限界后，把搜索树上当前所有的结点的限界进行比较，找出限界最小的结点，此结点即为下次分枝的结点。这种决策的优点是检查子问题较少，能较快地求得最佳解。但需要大量的内存空间以及对界值的过分依赖又制约着分枝界限法的求解效率。

（三）遗传算法

遗传算法是一类借鉴生物界自然选择和自然遗传机制的随机化的搜索算法，它是由密执安大学教授Holland及其学生

），空间

于1975年创建。该算法的基本思想是：把问题的解表示为"

二、几种常见的算法

（一）动态规划法

动态规划法DM(DynamicProgramming,简称DM)是美国数学家BellmanRE等人在20世纪50年代在研究多阶段决策过程的优化问题时提出的，其基本思想是将求解问题分解成若干个子问题。动态规划方法求解TSP问题的基本步骤为：

（1）找出最优解的性质，并刻划其结构特征；（2）递归地定义最优解；（3）以自底向上的方式计算出最优解；（4）根据计算最优值时得到的信息，构造最优解。

该算法是一个递归算法，

它的时间复杂度为

—184—

TSP问题及几种常见算法的比较研究

染色体"，这些"染色体"在后续迭代中不断进化，称之为遗传。遗传算法从一组随机产生的初始"染色体"（称之为种群即假设解）开始搜索，然后把这些假设解置于问题的"环境"中，并按适者生存的原则，从中选择出较适应环境的"染色体"进行复制，再通过交叉、变异过程产生更适应环境的新一代"染色体"群。"染色体"的好坏用适应度来衡量，根据适应度的大小从上一代和后代中选择一定数量的个体，作为下一代种群，再继续进化。这样经过若干代后，算法收敛于最适应环境的一个"染色体"上，它就是问题的最优解。其基本步骤是：

（1）

初始化种群规模=0。

（2）随机产生初始种群；计算初始种群的适应度。

（3）根据一定选择策略选择父体1和父体2。（4）产生一个0~1随机数（5）判断

2

2

长度和信息激素浓度构成的函数），把选择的城市

=1,2,…

优路径。

（5）根据本次蚂蚁的访问情况更新每一条边上的信息激素浓度，清空禁忌表。

（6）判断是否满足结束条件，如果不满足，转到（2），否则

结束。

蚁群算法在最优解的求解速度和运算结果的稳定性等方面均有较大的优势，但蚁群算法的性能是由信息素决定的。而初期信息素匮乏，这就容易导致求解速度缓慢。信息素设置不当也会造成算法收敛速度过慢或容易走向局部最优解。

条路径的路径长度，选出本次的最

、交叉概率

。

三、各种算法的比较

表1

是否成立，如果成立，把父体1和父体2按

一定交叉方法生成子个体1和子个体2；否则把父体1和父体2作为新的子个体1和子个体2。

（6）判断

它们在求解特定的问题领域里发挥着各自的作用。近些年，随着对TSP问题的认识的加深，试图用一种单一算法求解TSP问题的研究正在减少，而使用多种方法相结合的研究正逐渐兴起。在今后相 …… 此处隐藏：1691字，全部文档内容请下载后查看。喜欢就下载吧 ……