# tsp_heuristic

**Repository Path**: mathu-dxy/tsp_heuristic

## Basic Information

- **Project Name**: tsp_heuristic
- **Description**: 使用2opt局域搜索、模拟退火、遗传算法求解Tsp问题
- **Primary Language**: Python
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 3
- **Forks**: 0
- **Created**: 2020-12-01
- **Last Updated**: 2024-08-01

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# Tsp问题的启发式方法

## Tsp问题

Tsp问题是经典的组合优化问题。虽然问题形式简单，但已经被证明属于NP-Hard问题。精确求解算法很难在合理时间内求解完成，启发式方法有着易扩展、速度快、效果好的优势。本代码利用爬山法、模拟退火、遗传算法三种启发式方法对Tsp问题进行求解。

## 爬山法

爬山法是局域搜索方法的最简单形式。在每一个步，算法贪婪选择当前邻域中最优状态，作为下一状态。如果邻域中所有状态都比当前状态差，则达到局部最优点，终止算法。

本代码利用数组表示一个解，数组的第 $i$ 位，表示第 $i$ 个访问的城市。采用2OPT作为邻域算子，即把部分解序列前后翻转。如果邻域中有多个状态对应相同的最优长度，则随机选择一个作为下一状态。

邻域搜索算法，通常步数很多，需要尽量减小每一步的计算花销。本代码主要采用两个方式加速计算。首先利用Python列表的seq[::-1]实现翻转，利用列表加法，实现部分解序列的组合。相比于利用循环，每个位置单独赋值计算更快。其次，下一状态的长度通过相邻两状态长度的改变量计算。

通过在berlin52和kroE100两个问题上测试，说明爬山法的特性。下文通过十次计算得到平均长度和平均求解时间。其他两个启发式方法也采用同样方式进行测试。berlin52最优解通过代入最优序列计算长度得到（TspLib给出最优值7542，代入最优解得到7544，很困惑）。kroE100，TspLib没有给最优解，通过[Best known solutions for symmetric TSPs](http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/STSP.html)处得到最优解值。

|            | berlin52 | kroE100 |
| ---------- | -------- | ------- |
| 平均长度   | 8099     | 23523   |
| 平均时间/s | 0.14     | 1.4     |
| 最优解     | 7544     | 22068   |
| gap        | 7.4%     | 6.6%    |

测试表明爬山法计算速度快，能够在2s内得到计算结果。由于KroE问题规模更大，需要更多步数达到局部最优，因此求解时间更长。结果长度与最优值有较大gap，约7%。以上结果是因为爬山法每一步都贪婪地选择步骤，导致很快陷入局部最优。

结果展示如下图

<center> <figure> 
<img src="results/HillClimb_berlin.png" style="zoom: 40%;"/> 
<img src="results/HillClimb_kroe.png" style="zoom: 40%;"/> </figure> </center>





## 模拟退火算法

模拟退火算法是仿照打铁退火过程而设计的智能算法，能够克服爬山法易陷入局部最优的不足。模拟退化算法算法在每一步根据温度决定是否接受某一步骤。当温度高时，可以接受长度增大较大的值。温度逐渐降低，算法不再接受长度增大较多的步骤，更类似于爬山法的效果。

模拟退火算法的局域算子直接调用前述爬山法的邻域算子2OPT。

模拟退火算法有更多的参数设置，会显著影响求解时间，与求解质量。例如较高的初始温度，导致前期无意义的探索。较大的温度衰减系数会导致降温过慢，能够更充分地探索解空间，但是会显著增加计算时间。单个温度迭代次数增大同样会提升解的质量，但增加计算时间。实验中设定初始温度为100，温度衰减系数为0.995，末温为20，单个温度迭代2000步。为增强算法的探索能力，如果连续5个温度，最优值都未改变，则返回之前最优解重新搜索。

测试结果如下

|            | berlin52 | kroE100 |
| ---------- | -------- | ------- |
| 平均长度   | 7585     | 22428   |
| 平均时间/s | 16       | 16      |
| 最优解     | 7544     | 22068   |
| gap        | 0.5%     | 1.6%    |

测试表明，模拟退火算法有更好的求解质量。本代码的2OPT局域算子增量地计算下一状态，计算时间与规模无关，所以两个问题测试的总时间一样。

结果展示如下图

<center> <figure> 
<img src="results/sa_berlin.png" style="zoom: 40%;"/> 
<img src="results/sa_kroe.png" style="zoom: 40%;"/> </figure> </center>



## 遗传算法

遗传算法是模仿生物遗传变异设计的智能算法。该算法为群体算法，通过选择机制筛选出具有优良性质的个体。群体中的个体通过交叉，得到结合父本母本的优良性质的个体。通过变异对个体解进行扰动，增加探索。

本代码基于github开源代码TSP_GA_PY修改实现。算法中选择机制通过轮盘赌法实现，每个个体选择的概率正比与长度的倒数。交叉采用贪婪选取父本母本下一顶点较近者实现。假如当前部分解序列最后顶点为3，父本顶点3下一顶点点为7，母本顶点3下一顶点为9，则下一顶点选取7与9离3较近者。变异采用3OPT，2OPT。

具体实现上，设定种群数为50，演化代数为1000，变异概率为0.2（3OPT，2OPT各0.1概率）。以上参数对时间影响极大，运行时间与种群数，演化代数线性成正比。

测试结果如下

|            | berlin52 | kroE100 |
| ---------- | -------- | ------- |
| 平均长度   | 7546     | 22300   |
| 平均时间/s | 6        | 14      |
| 最优解     | 7544     | 22068   |
| gap        | 0.05%    | 1%      |

测试表明，相比于模拟退火，遗传算法运行时间更快，且求解质量更高。

结果展示如下图

<center> <figure> 
<img src="results/ga_berlin.png" style="zoom: 40%;"/> 
<img src="results/ga_kroe.png" style="zoom: 40%;"/> </figure> </center>



## 总结

本代码测试了三个启发式算法在Tsp问题上的表现。总的来说模拟退火、遗传算法，相较于爬山法效果更好。在目前的测试参数下，遗传算法效果要好于模拟退火算法。

在实际测试中，也发现当增大模拟退火算法温度衰减系数时，算法能探索到更好的解，虽然求解时间更长。而遗传算法在求解时间更长时，解的质量提升不明显。