MATLAB实现的基于对称TSP问题研究.zip

# 基于对称TSP问题的研究 **摘要** 旅行商问题（简称TSP）是一个著名的NP-Hard问题，也是离散优化的一个经典的重要问题，对其相关求解算法的研究非常重要。本文在介绍了TSP问题本身相关的问题后，又详细讨论了求解TSP问题的动态规划方法、改良圈算法、二交换算法、模拟退火算法、蚁群算法、遗传算法，并通过整合各种优化方式，对遗传算法进行了少量优化。针对测试库中的的改良圈算法、模拟退火算法、蚁群算法、遗传算法。本文使用MATLAB软件实现这些算法，并对这些算法的运行时间和解进行比较分析等研究。结果表明在任何清空下改良圈算法的性能都最差，其余算法在小型TSP问题下差别不大，在较大型TSP问题下，模拟退火所用时间最短，蚁群算法所用时间最长，遗传算法的解最好。实验结果证明，改进后的遗传算法效果不明显，在解的大小上改善1%-3%，但时间提高了10%。 **关键词** 对称TSP问题; 算法研究; 近似算法;模拟退火;遗传算法;蚁群算法 # 一、引言 ## 1.1 TSP问题 TSP问题，即一个商人想要去n个城市推销商品，每两个城市i和j之间的的距离为$d_{ij}$,如何选择一条道路使得商人能够每个城市仅走一遍后回到起点且保证所求的路径最短。其中，当对所有的城市i和j都有 $d_{ij}$, = $d_{ji}$ 则称为对称TSP问题，否则称为非对称TSP问题，本文主要讨论对称TSP的问题。 对NP问题，如果采用标准的穷举算法，复杂度会达到O(n!)的复杂度。所以目前学术界对这类问题经常使用近似算法来求解。但这种算法，大量的启发式的搜索算法不一定能求出最优解，往往会陷入局部收敛，如何跳出局部收敛得到最优解也是现在相关算法改进的方向。 为方便后序的讨论，我们可以将TSP问题转化为数学模型:  ## 1.2 研究意义 作为NP问题的代表性问题，TSP问题具有典型的易于描述却难以大规模处理的特性[4]，是在较多领域内出点的多种复杂问题的集中概括和简化形式。对它进行相关算法的设计、优化、讨论无论是对类似的图问题的拓展，还是对相关的NP-Hard问题算法的设计与实现，都具有比较广泛的现实意义。 ## 1.3 本文的主要工作 本文针对TSP问题，首先介绍了目前学术界大多数的TSP相关算法，包括GA算法，模拟退火算法，动态规划算法，改良圈算法，二交换法，三交换法等，并通过已有的文献对这些算法进行了比较分析，并对遗传算法实现一些少量的改进等，最后通过本文相关算法进行了比较分析。 具体的研究内容如下： 1. 分析了各算法的基本原理以及解决TSP问题的方法、流程。 2. 对大多数算法进行了分析，指出各个算法的优缺点。 3. 针对遗传算法通过整合大量的优化方式，进行少量的改进。 4. 利用matlab等软件，使用TSPLIP测试集，进行算法结构改进方面的实验进行实验结果的比较分析。 # 二、相关概念与工作 ## 2.1 TSP相关算法概述 目前对TSP的大部分研究都是在非确定性的相关算法下进行的，但我们也应该注意到传统的确定性算法，因为对传统的算法的改进也能或多或少的运用。因此我们根据大部分TSP相关的论文，进行了整体的优劣性的相关比较，如下图所示。 其中传统的确定性算法在总体分析上具有时间复杂性大、空间复杂性大的特点，这主要是由于问题本身就是一个NP完全问题，而现代流行的近似算法则具有算法复杂性小的特点，很快就能得到较优的解，下面本文分别对上述的算法进行介绍，并进行比较分析。 总体来说，传统的算法在总体分析上具有时间复杂性大、空间复杂性大的特点，这主要是由于问题本身就是一个NP完全问题，而现代流行的只能算法则具有算法复杂性小的特点，很快就能得到较优的解。 ## 2.2 动态规划算法 动态规划DM( Dynamic Prog ramming , 简称 DM)是运筹学的一个分支，是针对多阶段决策过程的优化问题[7]而被提出的，他能把多阶段过程转化为一系列的单阶段的子问题，逐个进行求解，即将待求解问题分解成若干子问题，然后从这些子问题中的解得到原问题的解。   ## 2.3 改良圈算法 哈密顿图（哈密尔顿图）（英语：Hamiltonian path，或Traceable path）是一个无向图，由天文学家哈密顿提出，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。在图论中是指含有哈密顿回路的图，闭合的哈密顿路径称作哈密顿回路（Hamiltonian cycle），含有图中所有顶点的路径称作哈密顿路径。 从图中的任意一点出发，路途中经过图中每一个结点当且仅当一次，则成为哈密顿回路。（我的理解就是从一点出发经过所有点在回到原始位置画一个圈） Hamilton圈满足两个条件：①封闭的环②是一个连通图，且图中任意两点可达 由于TSP问题的母图是竞赛图，所以TSP问题可以转化为求总路径长度最短的那个Hamilton圈 算法首先求得一个Hamilton圈，然后修改圈得到具有较小权的另一个Hamilton圈，直至无法改进则停止。[9] ## 2.4 交换算法 交换算法输入的范畴，公开密钥交换算法在网络通信中扮演着重要的作用。例如，密钥交换算法是一些最常用的密码学协议中的重要组成部件(SSL, IPsec, SSH等等)，这些协议保证了网络通信以及电子商务的安全快速发展。因此，密钥交换算法自从诞生以来，一直是现代密码学家的关注重点。  ## 2.5 模拟退火算法 与传统的确定性算法想办法消除搜索消耗的影响不同，大部分的人工智能算法是在搜索的框架下进行的，他们不是完美的求解算法，都只能能在一定精确范围内求解，但时间复杂度很低，效率很高，因此得到了广泛的应用。 模拟退火算法（Simulate Annealing Arithmetic，SAA）是一种通用概率演算法，用来在一个大的搜寻空间内找寻命题的最优解。它是基于Monte-Carlo迭代求解策略的一种随机寻优算法。 SA算法是在爬山法[见附录]的基础上进行的，爬山法是一种完完全全的贪心算法，难以避免总会收敛到局部最优解，SA算法则在搜索到局部最优解后，会以一定的概率接受继续移动，这就能跳出局部最优继续搜索。SA算法的名称得益于上述概率的计算公式，即使用了  此外，为了能够产生新解，模拟退火算法需要用到新解产生的算法，比较常见的两种算法是二变换法和三变换法。 得益于爬山法的贪心性质，模拟退火算法具有较强的局部寻优能力且不容易在搜索的过程中陷入局部最优解。但是算法仍然不便于把握全局最优解，且参数温度T的初始值，退火的速度，温度管理方面都难以进行控制。[10] ## 2.6 蚁群算法 蚁群算法( Ant Colony 0 ptimization,简称ACO)由意大利学者Dorigo M等在1996 年首先提出15,16]。该算法通过模拟蚂蚁的觅食行为，蚂蚁觅食的时候会在所走过的路径.上留下信息激素,同时信息激素会随时间而挥发