旅行商问题(TSP): 动态规划算法、蚁群算法、遗传算法
人工智能课结束，大作业选择了题目名为：基于概率搜索的旅行商问题求解策略分析。因此大作业内将包含了求解TSP问题的精确算法——动态规划算法（DP），以及启发式算法——蚁群算法（ACO）和遗传算法（GA）。 因为TSP问题是一个备受数学家和计算机科学家关注的一个问题，主要是因为它很容易描述，但是很难解决，是一个经典的NP(non-deterministic polynomial)困难问题，在日常生活中比较常见，例如交通运输、电路设计、物流分发、抄表等等。该问题可以简单地表述为:一个商品推销员要去n个城市推销商品，该推销员随机从一个城市出发，需要经过所有城市后，最后回到出发地应如何选择行进路线以使总的行程最短。
-orange){kind=icon}
-red){kind=icon}
-red){kind=icon}
-red){kind=icon}
为了方便测试，已经把它们各自都封装成了函数，并且写了参数注释。相当于一个小的测试系统吧，功能包括：动态规划算法、蚁群算法、遗传算法、蚁群算法优化测试、数据集测试、自动化算法测试。
程序中需手动下载安装的Python库有：numpy、matplotlib、networkx、prettytable。
程序运行后首先会显示如下界面，然后只要输入想使用的功能的序号就可以了：
| 算法序号 | 算法名称 |
|---|---|
| 1 | 动态规划算法 |
| 2 | 蚁群算法 |
| 3 | 遗传算法 |
| 4 | 蚁群算法优化测试 |
| 5 | 数据集测试 |
| 6 | 自动化算法测试 |
首先因为动态规划算法的空间复杂度为$O(2^nn^2)$，因此不建议使用超过城市数量为20的TSP问题求解，同时时间复杂度也是指数型增长。
通过对一系列的城市规模的TSP问题求解，自己比较得出在各范围内的最优算法：在城市规模数量小于16座的时候选取DP算法较为合适；在城市规模数量大于16座同时小于220座的时候选取ACO算法较为合适；在城市规模数量大于220座同时小于300座的时候选取GA算法较为合适。
使用流程：
- 用户输入城市数量后按回车
- 算法运行好后会展示运行结果，下表展示用动态规划算法计算城市规模为5的TSP问题并得到如下的结果（其他算法的结果也都如此）：
| TSP参数 | 运行结果 |
|---|---|
| 城市数量 | 5 |
| 最短路程 | 26.86 |
| 运行时间 | 692.875微秒 |
| 最小路径 | 0 --> 1 --> 3 --> 2 --> 4 --> 0 |
- 会提示用户是否显示城市网络图，其中输入Y/y表示显示，N/n表示不显示。该图包括了最初的旅行商城市分布图（随机生成的城市坐标）以及最优路径解的网络图，示例如下：
- 询问用户是否退出系统，操作符同上。
- 即序号1、2、3的功能使用；
- 其中蚁群算法使用的是经过简单优化后的算法，计算速度对更快一些。
这是最基本的蚁群算法和简单优化后的蚁群算法的比较测试，这是论文中的一部分，因为要测试，所以单独开了这么一个功能。
使用流程：
- 输入城市规模，城市规模之间用逗号隔开，示例如下：
20,50,100,200,300 - 输入跳过次数（这是优化代码的参数，即达到阈值后迭代次数会减少相应次数)，示例如下：
0,10,20,30 - 输入线条样式，其他样式如下图所示，只需在字母前加上"-"即可，如“-D”表示菱形样式，示例如下：
-D,-s,-o,-^
- 输入每轮测试次数，这是每种代码每轮的测试次数，示例如下：
10
最后的输出结果分为四张图：最优路径解、标准差（平均值为所有测试结果取平均）、迭代次数、运行时间，结果如下所示：
需要注意的是跳过次数的输入个数应与线条样式个数相等，否则会报错
这是测试数据集的功能，只要把数据集导入即可，但是会依次执行ACO和GA，最后得出最终结果，不能单独执行，不过可以把源码简单稍作修改应该就能实现。
使用流程：
- 输入导入的txt文件的地址，示例：
../TSP-DataSet/set1.txt
具体格式如下：
1 170.0 85.0
2 166.0 88.0
3 133.0 73.0
4 140.0 70.0
5 142.0 55.0
6 126.0 53.0
7 125.0 60.0
8 119.0 68.0
9 117.0 74.0
10 99.0 83.0
......
第一列为城市编号，最后输出时城市1作为下标0输出
第二列为城市横坐标x
第三列为城市纵坐标y
-
输入每种算法运行次数，将运行结果取平均值作为最后输出的结果，示例：
10 -
输出结果，结果展示如下：
已完成已完成第1次蚁群算法, 用时4.135秒
...
已完成第1次遗传算法, 用时03分35秒
...
| 算法名称 | 运行结果 |
|---|---|
| 10次蚁群算法最优解平均值 | 782.06 |
| 10次遗传算法最优解平均值 | 819.78 |
这是将所有算法都进行一轮执行，共执行n轮。
使用流程：
- 输入想要测试的城市规模，示例：
6,8,10,12,14,16,18,20,25,30,35,40,45 - 输入每轮测试的次数，示例：
10 - 结果输出，示例如下，会展示每种算法的最优路径解以及运行时间
因为DP算法的局限性，当城市数大于20后就不再使用，所有数据均为0展示
- TSP文件为源代码文件夹，其中main.py为入口文件
- main.py为入口文件
- ACO.py为蚁群算法文件
- GA.py为遗传算法文件
- DP.py为动态规划算法文件
- utils.py为算法文件中所使用的功能的封装，如：画图、打印表格等
- TSP-DataSet为TSP数据集文件夹
- 最优结果.txt为数据集的结果
- 剩余文件为测试的数据集
- images为README.md的引用图片文件夹
MIT license