TSP的几种求解方法及其优缺点

《TSP的几种求解方法及其优缺点》由会员分享，可在线阅读，更多相关《TSP的几种求解方法及其优缺点（15页珍藏版）》请在金锄头文库上搜索。

1、、什么是 TSP 问题旅行商问题，简称TSP,即给定n个城 市和两两城市之间的距离，要求确定一条 经过各城市当且仅当一次的最短路线。其 图论描述为：给定图G= （V, A）,其中VIJJJJ为顶点集， A 为各顶点相互连接组成的边 集，设D= （dij）是由顶点i和顶点j之间 的距离所组成的距离矩阵，要求确定一条 长度最短的Hamilton回路，即遍历所有顶 点当且仅当一次的最短距离。旅行商问题可分为如下两类： 1）对称旅行商问题（dij=dji，ni，j=1,2， 3， n）；2）非对称旅行商问题（dijHdji，i， j=1， 2， 3， n）。非对称旅行商问题较难求解，我们一 般是探讨对

2、称旅行商问题的求解。若对于城市V=v1,个访问顺序为T=t1，t2,V2, V3, Vn的一 t3, ti，tn，其中 tiV （i=l，2，3，n），且记 tn+1=ti,则旅行商问题的数学模型为：minL=。TSP 是一个典型的组合优化问题，并 且是一个 NP 完全难题，是诸多领域内出 现的多种复杂问题的集中概括和简化形 式，并且已成为各种启发式的搜索、优化 算法的间接比较标准。因此，快速、有效 地解决TSP有着重要的理论价值和极高的 实际应用价值。二、主要求解方法基于 TSP 的问题特性，构造型算法成 为最先开发的求解算法，如最近邻点、最 近合并、最近插入、最远插入、最近添加、 贪婪插入

3、等。但是，由于构造型算法优化 质量较差，迄今为止已开发了许多性能较好的改进型搜索算法，主要有：1）模拟退火算法3）Hopfield 神经网络优化算法4）蚁群算法5）遗传算法6）混合优化策略模拟退火算法方法1）编码选择：采用描述 TSP 解的最 常用的一种策略路径编码。2）SA 状态产生函数的设计：对于基 于路径编码的 SA 状态产生函数操作，可 将其设计为：互换操作（SWAP）；逆 序操作（INV）；插入操作（INS）。Ill3）SA 状态接受函数的设计： min1， exp （ /t） random0, 1准则是作为接 受新状态的条件最常用的方案，其中为 新旧状态的目标值差， t 为”温度”

4、。IIIIII4）初温和初始状态：最常用且可理 解的初温确定方案是，首先随机产生一组 状态，确定两两状态间的最大目标值差：| Amax|,然后由式 t0= A max/lnpr,其中 pr 为初始接受概率（理论上应接近 1，实 际设计时也可以取）。初始状态可采用启 发式算法（如2opt方法）快速得到一个解, 并以此为 SA 的初始状态。IIIIIIIIIIII5）退温函数的设计：指数退温函数 是最常用的退温策略（tk=入tk1 ,入为退 温速率）。6）温度修改准则和算法终止准则的设计：可采用阈值法设计的”温度修改” 和”算法终止”两准则。禁忌搜索算法 基于禁忌搜索算法的一般设计原则， 对典型的

5、组合优化问题TSP,其算法可以 按如下方案实现：1) 初始解：可随机产生也可基于问 题信息借助一些启发式方法产生以保证一定的初始性能。2) 邻域结构：常用方法是互换(SWAP)、插入(INSERT)、逆序(INVERSE)等操作。3) 候选解的选择：通常取当前解的 邻域解集的一个子集作为候选解集,而取 其中的满足藐视准则或非禁忌的最优状 态为最佳候选解。4) 禁忌表及其长度：建议尝试自适 应长度法,譬如根据目标值更新的情况或 禁忌频率信息来适当增加或缩短禁忌表 长度。5) 藐视准则：采用若某个状态的性能优于” bestsofar”状态，则忽视其禁忌属性，直接选取它为当前状态。6）集中搜索和分散

6、搜索策略：分别 采用在一定步数的迭代后基于最佳状态 进行重新初始化并对其邻域进行多步趋 化性搜索和对算法的重新随机初始化或 是根据频率信息对一些已知对象进行惩 罚。7）终止条件：给定最优状态连续保持不变的最大持续迭代步数。大量研究表 明禁忌搜索算法具有模拟退火、遗传算法 等智能优化算法相当的性能，甚至更优 越。Hopfield 神经网络优化算法在用 Hopfield 网络求解优化问题之 前，必须将问题映射为相应的神经网络。 对 TSP 的求解，首先将问题的合法解映射为一个置换矩阵，并给出相应的能量函数，然后将满足置换矩阵要求的能量函数l=Jl=l的最小值与问题的最优解相对应。若以 X，I三l=

7、lY表示城市，i表示第几次访问，dXY表示 城市间的距离， VXi 表示矩阵中的第 X 行 第 i 列的元素，则可构造出能量函数为： = E E +卡 E E E 叫几 +X /2 J X YHX刀刀卩阳亠厂+* g若工可匕冲+忖+ 1丿 网络的动态方程可表示为； 少七-簣計一i 十 tailD，缶丫f+i十#耳1丿vxt 仏 芯 J这是nXn个神经元状态方程的通用 表达式。为求得 TSP 的优化结果，需要求 解 nX n 个非线性一阶联立微分方程式， 以得到置换矩阵中 nX n 个元素的全部状 态。例如可采用如下参数并给定个城市的 位置和相互距离求解 n 个城市的 TSP：t=1， A=B=

8、500, C=200, D=500, 口0=起始条件为 随机噪声，令起始 uXi 如下式于收敛7。利用数值计算方法对此微分方 程组求解，经若干次迭代即可求得网络各 神经元的最终状态。蚁群算法方法蚁群算法与其他模拟进化算法一样，最优解。求解 TSP 的工作过程为：首先将 m 只蚂蚁按照一定的规则（例如随机）分 布在 n 个城市，然后每一只蚂蚁寻找出一 条可行路径并进行局部信息更新，最后寻 出所有蚂蚁找到的最好路径进行全局信白TFf * 匚 息更新。遗传算法方法近年来，遗传算法已被成功的应用于工业、经济管理、交通运输、工业设计等 不同领域，解决了许多问题。基于遗传算 法求解 TSP 的算法实现，以

9、下几个方面需 要说明：1）遗传基因编码方法：目前主要有以下三种比较有效的方法： 顺序表示 路径表示 布尔矩阵表示2）遗传操作算子： 选择算子：对于求解TSP,常用的选择机制有轮盘赌选择机制、最佳个体保 存选择机制、期望值模型选择机制、排序选择机制、联赛选择模型机制等。 交叉算子：采用顺序表示技术可以 采用基本遗传算法的交叉操作例如单点 交叉、两点交叉、多点交叉和均匀交叉； 采用路径表示的可用部分匹配交叉、顺序 交叉、循环交叉、边重组交叉；采用布尔 矩阵表示的有它独特的交和并算子。 变异算子：采用顺序表示的可采用 基本位变异、均匀变异、边界变异、非均 匀变异和高斯变异；采用路径表示的可用位点变异

10、、逆转变异、对换变异和插入变 异。另外适应度函数可取为哈密尔顿圈的 长度的倒数（无惩罚函数），初始种群可 用随机方法产生，再确定相应的控制参数 及可求解。混合优化策略方法譬如大规模 TSP 的求解，鉴于问题整体求解的复杂性，在设计算法时可以先考 虑空间的分解，利用聚类的方法将问题分 解为若干子问题，然后先用启发式方法快 速得到子问题的近似解，而后以其为初始 状态利用 GA，SA，TS 等方法和规则性搜索在一定的混合方式下进行指导性优化， 待各子问题求解完毕用临近原则确定问 题的整体解，再利用局部改进算法对其作 进一步加工以得到问题的最终解。三、各种方法的优缺点及比较由于 TSP 的典型性，在过

11、去的几十年 里人们研究了许许多多的求解方法。除了 以上介绍的求解方法以及它们的各种改 进型方法外，还有一些其他的方法也可求 解TSP,比如：nopt法，贪心算法，爬山 法，回溯法，分支限界法，EP,混沌搜索、 模糊优化等。SA， GA 和 TS 作为具有全局优化性能 的典型 Metaheuristic 算法代表，与人工 神经网络统称为四大现代启发式算法。蚁 群算法是 90 年代初才被提出的全新的算 法，而混合优化策略由于缺乏严格且丰富 的理论研究和效率分析也是近年来也才得到发展和应用。概括地讲， SA 算法的实 易实现的优点，最大缺点是往往优化过程验性能具有质量高、初值鲁棒性强、通用l=J|=

12、|较长；GA的两个最显着的优点是隐含并行性和全局解空间搜索，但实际应用时易出现早熟收敛和收敛性能差等缺点；TS算 法是一种局部搜索能力很强的全局迭代 寻优算法，不足之处在于对初始解较强的依赖性和串行的迭代搜索过程；Hopfield神经网络优化算法具有简单、规范、快速 等优点，但是其优化性和鲁棒性比较差； 蚁群算法是一种本质并行的算法，但其搜 索时间比较长，也容易陷于局部最优解，使搜索停滞；混合优化策略若能得到有效 的设计，真正做到不同方法的取长补短将 会产生更好的优化效率。由于很少有论文提供求解TSP的一些特定实例的计算时间，而只报道函数评估 的次数，这使得不同方法之间的比较略显 困难，因为不

13、同的算子具有不同的时间复 杂性。目前的大多数文献都是将所提方法 与其他方法作比较，比较中使用的两类主 要的测试实例为：l=J|=|l=J|=|1）随机分布的 TSP 城市。典型情况 是与一个均匀随机变量相对应并假定采 用欧式距离度量。这里，关于最短的 TSP 路径的期望长度 L3 的一个经典公式为 L3=knR,其中n为城市数目，R是一个 正方形的面积，随机放置的各城市均位于 该正方形之内， k 为一个经验常数，称为 HeldKarp 下界。对于 n 城市的随机欧氏 TS (nlOO), k与n的期望比例关系为 k=+。 Bonomi 和 Lutton 建议采用 k=。2) TSP公共测试实例

14、库(TSPLIB18)。 它还提供了有文献报道的最优解或目前 已知的最好解。四、结论对于TSP，目前还不存在能找到完美 解的方法，这个问题是 NP 难的：目前还 没有任何算法能在与城市总数呈多项式 关系的时间复杂性下找到完美解。我们只 能产生一些近似完美解，在合理的运行时 间里使其与完美解尽可能的接近。结论来看，少于 1OO 个城市的 TSP 例子很 适合于用全局优化技术求解，但是要考虑 城市规模比这大得多的 TSP 实例则需要采 用启发式方法。为了进一步提高算法的全局优化能力，避免搜索过程陷入局部极小，现已提 出的改进策略主要有：并行多邻域搜索， 平滑优化曲面形状，引进重升温、熵抽样 等高级技术等。对于复杂优化问题，单一 机制的优化算法很难实现全局优化，且效 率较低。多种优化机制和邻域搜索结构相混合，是能较大程度提高全局优化度和鲁 棒性的有力途径，并可一定程度上放松对单一算法参数选择的苛刻性。所以混合优 化策略会是一种趋势。对于 TSP 的求解，我认为以后在以下几个方面可能会有很好的进展：1）新的方法的提出；2）基于目前各种方法的改进 3）混合优化策略的发展等。我们希望最终人们能找到一种求解TSP的完美方 法。