发布时间 : 星期一 文章TSP的几种求解方法及其优缺点更新完毕开始阅读6413c041bf64783e0912a21614791711cd797948
v1.0 可编辑可修改 TSP的几种求解方法及其优缺点
一、什么是TSP问题
旅行商问题，简称TSP，即给定n个城市和两两城市之间的距离，要求确定一条经过各城市当且仅当一次的最短路线。其图论描述为：给定图G=（V，A），其中V为顶点集，A为各顶点相互连接组成的边集，设D=（dij）是由顶点i和顶点j之间的距离所组成的距离矩阵，要求确定一条长度最短的Hamilton回路，即遍历所有顶点当且仅当一次的最短距离。
旅行商问题可分为如下两类：
1）对称旅行商问题（dij=dji，Πi，j=1，2，3，?，n）； 2）非对称旅行商问题（dij≠dji，?i，j=1，2，3，?，n）。 非对称旅行商问题较难求解，我们一般是探讨对称旅行商问题的求解。
若对于城市V={v1，v2，v3，?，vn}的一个访问顺序为T={t1，t2，t3，?，ti，?，tn}，其中ti∈V（i=1，2，3，?，n），且记tn+1=t1，则旅行商问题的数学模型为：minL=。
TSP是一个典型的组合优化问题，并且是一个NP完全难题，是诸多领域内出现的多种复杂问题的集中概括和简化形式，并且已成为各种启发式的搜索、优化算法的间接比较标准。因此，快速、有效地解决TSP有着重要的理论价值和极高的实际应用价值。
二、主要求解方法
基于TSP的问题特性，构造型算法成为最先开发的求解算法，如最近邻点、最近合并、最近插入、最远插入、最近添加、贪婪插入等。但是，由于构造型算法优化质量较差，迄今为止已开发了许多性能较好的改进型搜索算法，主要有：
1）模拟退火算法 2）禁忌搜索算法
3）Hopfield神经网络优化算法 4）蚁群算法 5）遗传算法 6）混合优化策略
1
v1.0 可编辑可修改 模拟退火算法方法
1）编码选择：采用描述TSP解的最常用的一种策略——路径编码。
2）SA状态产生函数的设计：对于基于路径编码的SA状态产生函数操作，可将其设计为：①互换操作（SWAP）；②逆序操作（INV）；③插入操作（INS）。
3）SA状态接受函数的设计：min{1，exp（-△/t）}>random[0，1]准则是作为接受新状态的条件最常用的方案，其中△为新旧状态的目标值差，t为”温度”。
4）初温和初始状态：最常用且可理解的初温确定方案是，首先随机产生一组状态，确定两两状态间的最大目标值差：|Δmax|，然后由式t0=-Δmax/lnpr，其中pr为初始接受概率（理论上应接近1，实际设计时也可以取）。初始状态可采用启发式算法（如2opt方法）快速得到一个解，并以此为SA的初始状态。
5）退温函数的设计：指数退温函数是最常用的退温策略（tk=λtk-1，λ为退温速率）。 6）温度修改准则和算法终止准则的设计：可采用阈值法设计的”温度修改”和”算法终止”两准则。
禁忌搜索算法
基于禁忌搜索算法的一般设计原则，对典型的组合优化问题TSP，其算法可以按如下方案实现：
1）初始解：可随机产生也可基于问题信息借助一些启发 式方法产生以保证一定的初始性能。 2）邻域结构：常用方法是互换（SWAP）、插入 （INSERT）、逆序（INVERSE）等操作。
3）候选解的选择：通常取当前解的邻域解集的一个子集作为候选解集，而取其中的满足藐视准则或非禁忌的最优状态为最佳候选解。
4）禁忌表及其长度：建议尝试自适应长度法，譬如根据目标值更新的情况或禁忌频率信息来适当增加或缩短禁忌表长度。
5）藐视准则：采用若某个状态的性能优于”bestsofar”状态，则忽视其禁忌属性，直接选取它为当前状态。
6）集中搜索和分散搜索策略：分别采用在一定步数的迭代后基于最佳状态进行重新初2
v1.0 可编辑可修改 始化并对其邻域进行多步趋化性搜索和对算法的重新随机初始化或是根据频率信息对一些已知对象进行惩罚。
7）终止条件：给定最优状态连续保持不变的最大持续迭代步数。大量研究表明禁忌搜索算法具有模拟退火、遗传算法等智能优化算法相当的性能，甚至更优越。
Hopfield神经网络优化算法
在用Hopfield网络求解优化问题之前，必须将问题映射为相应的神经网络。对TSP的求解，首先将问题的合法解映射为一个置换矩阵，并给出相应的能量函数，然后将满足置换矩阵要求的能量函数的最小值与问题的最优解相对应。若以X，Y表示城市，i表示第几次访问，dXY表示城市间的距离，VXi表示矩阵中的第X行第i列的元素，则可构造出能量函
数为：
这是n×n个神经元状态方程的通用表达式。为求得TSP的优化结果，需要求解n×n个非线性一阶联立微分方程式，以得到置换矩阵中n×n个元素的全部状态。例如可采用如下参数并给定个城市的位置和相互距离求解n个城市的TSP：t=1，A=B=500，C=200，D=500，u0=起始条件为随机噪声，令起始uXi如下式
而u00满足在t=0时∑X∑iVXi=n以利于收敛[7]。利用数值计算方法对此微分方程组求解，经若干次迭代即可求得网络各神经元的最终状态。
蚁群算法方法
3
v1.0 可编辑可修改 蚁群算法与其他模拟进化算法一样，通过候选解组成的群体进化过程来寻找最优解。求解TSP的工作过程为：首先将m只蚂蚁按照一定的规则（例如随机）分布在n个城市，然后每一只蚂蚁寻找出一条可行路径并进行局部信息更新，最后寻出所有蚂蚁找到的最好路径进行全局信息更新。
遗传算法方法
近年来，遗传算法已被成功的应用于工业、经济管理、交通运输、工业设计等不同领域，解决了许多问题。基于遗传算法求解TSP的算法实现，以下几个方面需要说明：
1) 遗传基因编码方法：目前主要有以下三种比较有效的方法： ①顺序表示 ②路径表示 ③布尔矩阵表示 2）遗传操作算子：
①选择算子：对于求解TSP，常用的选择机制有轮盘赌选择机制、最佳个体保存选择机制、期望值模型选择机制、排序选择机制、联赛选择模型机制等。
②交叉算子：采用顺序表示技术可以采用基本遗传算法的交叉操作例如单点交叉、两点交叉、多点交叉和均匀交叉；采用路径表示的可用部分匹配交叉、顺序交叉、循环交叉、边重组交叉；采用布尔矩阵表示的有它独特的交和并算子。
③变异算子：采用顺序表示的可采用基本位变异、均匀变异、边界变异、非均匀变异和高斯变异；采用路径表示的可用位点变异、逆转变异、对换变异和插入变异。另外适应度函数可取为哈密尔顿圈的长度的倒数（无惩罚函数），初始种群可用随机方法产生，再确定相应的控制参数及可求解。
混合优化策略方法
譬如大规模TSP的求解，鉴于问题整体求解的复杂性，在设计算法时可以先考虑空间的分解，利用聚类的方法将问题分解为若干子问题，然后先用启发式方法快速得到子问题的近似解，而后以其为初始状态利用GA，SA，TS等方法和规则性搜索在一定的混合方式下进行指导性优化，待各子问题求解完毕用临近原则确定问题的整体解，再利用局部改进算法对其作进一步加工以得到问题的最终解。 4