使用四种基本启发式算法求解广义TSP问题。
所谓广义TSP，即一些城市可能卖的是同一类商品，在买这类商品时仅走这些城市其中之一即可。
目录：
-
images - 只是一些结果图片
-
codes **
-
extendTSP.py
用于随机生成广义TSP实例，并提供一些通用函数(如生成广义TSP实例，生成距离等)
-
SA.py 模拟退火
-
tabu.py 禁忌搜索
-
Genetic.py 遗传算法
-
ACO.py 蚁群算法
-
依赖：matplotlib + numpy，python3
可以通过extendTSP.py 中的 extendTSP_generate() 函数来生成实例
def extendTSP_generate(city_num, goods_num, x_range = 20, y_range = 20)
'''
city_num - 城市数量
goods_num - 商品种类数目
x_range, y_range - 坐标界限
'''TODO list： 模块化代码; 效果优化(陷入局部最优原因分析等); 效率优化
但大抵不会做了
效果简单示例：以 39个城市，25种商品为例
除路径图外 还可以打印最优解迭代情况等
问题定义：
# city_num = 39
# goods_num = 25
# tuple: (city_position, goods_class, city_class)
# 各个城市坐标：
([(5, 13), (10, 5), (11, 9), (18, 9), (8, 3), (0, 10), (19, 17), (9, 17), (11, 12), (18, 3), (3, 4), (17, 11), (5, 2), (6, 12), (18, 7), (1, 7), (11, 4), (13, 1), (6, 15), (0, 3), (19, 2), (18, 10), (14, 1), (16, 3), (4, 3), (3, 15), (19, 11), (13, 13), (4, 4), (2, 9), (15, 7), (2, 15), (7, 18), (13, 14), (14, 0), (15, 15), (17, 3), (13, 16), (15, 9)],
# 每个城市所卖的商品类别:
[11, 7, 2, 21, 11, 16, 6, 21, 9, 8, 9, 24, 23, 0, 6, 17, 18, 18, 5, 15, 4, 10, 12, 24, 12, 7, 20, 22, 3, 11, 19, 0, 4, 14, 13, 21, 1, 12, 9],
# 按照商品类别对城市进行分类：
[[13, 31], [36], [2], [28], [20, 32], [18], [6, 14], [1, 25], [9], [8, 10, 38], [21], [0, 4, 29], [22, 24, 37], [34], [33], [19], [5], [15], [16, 17], [30], [26], [3, 7, 35], [27], [12], [11, 23]])注：根据迭代次数等耗时会发生变化，下述结果以当前代码中默认次数及参数进行统计(非完全公平比较)
公平比较还是要限定一些条件的，若单纯根据迭代次数，由于模拟退火还需要控温，遗传算法和蚁群算法都有种群数量等因素，导致单纯的迭代次数本身可能不是那么公平；若考虑上述因素平衡各方实际执行次数，那么就需要先大体分析一下再选择一套比较合适的方案。 其实也可以直接把时间当成一个刻度来看待，看看最优解的收敛情况(以时间为横轴)，同样的时间下评判哪个好还是比较直观的，或者说哪种算法通过较少时间就能达到更好的效果。
若还是考虑单次迭代效率，确实是有区别，例如仅考虑单次迭代(或某群体/某蚂蚁)，蚁群算法可能消耗会多些，因为每只蚂蚁每走一步都要对剩余城市进行一次判断，这本身是阶乘级的复杂度，而使用轮盘可以缓解此种消耗，但由于还是需要固定判断n-1次（n为商品种类数量），并且使用轮盘也依然需要判断若干城市(随机)，因此单次迭代的时间消耗理论上确实相较前几种会大些，但体现在效果上就不一定谁更出色了。
上述本质上是要比较每次迭代操作的多少，可以进行理论分析，当然跑一跑验证结论更真实。
蚁群算法若追求效率，可以考虑把 line 88 注释掉或进一步放宽条件，但一定程度会损失精度
两个版本效果不同仅在于显示方式，代码是一样的(统计中蚁群算法还算入了中间打印的开销、其他没有，可以去掉或者迭代一轮再打印[已改])
可使用 check_valid() 函数来验证解的正确性
def check_valid(goods_class, solution)
'''
goods_class - 城市所卖商品种类
solution - 解(list)的下标(不含回路)
'''| 算法 | 耗时(s) | 求解的最优距离 |
|---|---|---|
| 模拟退火 | 14.577972 | 81.80118610291628 |
| 禁忌搜索 | 1.214795 | 73.87283105707995 |
| 遗传算法 | 26.364176 | 76.73653745864254 |
| 蚁群算法 | 51.245369 | 80.70618234947098 |
结果图：
模拟退火：
解：[(19, 11), (18, 10), (18, 9), (15, 7), (17, 3), (18, 3), (19, 2), (14, 0), (11, 4), (10, 5), (5, 2), (4, 3), (4, 4), (3, 4), (0, 3), (1, 7), (0, 10), (5, 13), (6, 15), (6, 12), (11, 9), (13, 13), (13, 14), (19, 17), (17, 11), (19, 11)]
下标顺序：[26, 21, 3, 30, 36, 9, 20, 34, 16, 1, 12, 24, 28, 10, 19, 15, 5, 0, 18, 13, 2, 27, 33, 6, 11]
禁忌搜索：
解：[(6, 15), (13, 14), (13, 13), (11, 9), (15, 7), (18, 10), (19, 11), (17, 11), (18, 9), (18, 7), (19, 2), (18, 3), (17, 3), (14, 0), (13, 1), (8, 3), (5, 2), (4, 3), (4, 4), (3, 4), (0, 3), (1, 7), (0, 10), (2, 15), (3, 15), (6, 15)]
下标顺序：[18, 33, 27, 2, 30, 21, 26, 11, 3, 14, 20, 9, 36, 34, 17, 4, 12, 24, 28, 10, 19, 15, 5, 31, 25]
遗传算法：
解：[(18, 7), (17, 3), (18, 3), (19, 2), (14, 0), (14, 1), (11, 4), (10, 5), (8, 3), (5, 2), (4, 4), (3, 4), (0, 3), (1, 7), (0, 10), (6, 12), (6, 15), (13, 14), (13, 13), (11, 9), (15, 7), (17, 11), (18, 10), (19, 11), (18, 9), (18, 7)]
下标顺序：[14, 36, 9, 20, 34, 22, 16, 1, 4, 12, 28, 10, 19, 15, 5, 13, 18, 33, 27, 2, 30, 11, 21, 26, 3]
蚁群算法：
解：
[(5, 2), (4, 3), (4, 4), (3, 4), (0, 3), (1, 7), (2, 9), (0, 10), (2, 15), (3, 15), (6, 15), (11, 9), (15, 7), (18, 7), (18, 9), (18, 10), (19, 11), (17, 11), (13, 13), (13, 14), (17, 3), (18, 3), (19, 2), (14, 0), (13, 1), (5, 2)]
下标顺序：[12, 24, 28, 10, 19, 15, 29, 5, 31, 25, 18, 2, 30, 14, 3, 21, 26, 11, 27, 33, 36, 9, 20, 34, 17]
| 算法 | 耗时(s) | 求解的最优距离 |
|---|---|---|
| 模拟退火 | 14.717047 | 81.91532259779534 |
| 禁忌搜索 | 1.294436 | 75.84301327322318 |
| 遗传算法 | 26.854897 | 77.5726497320684 |
| 蚁群算法 | 50.743670 | 80.70618234947098 |
结果图：
模拟退火：
解：[(1, 7), (0, 3), (3, 4), (4, 4), (5, 2), (8, 3), (10, 5), (11, 4), (14, 0), (14, 1), (19, 2), (18, 3), (17, 3), (15, 7), (18, 9), (18, 10), (17, 11), (19, 11), (19, 17), (13, 14), (13, 13), (11, 9), (6, 12), (6, 15), (0, 10), (1, 7)]
下标顺序：[15, 19, 10, 28, 12, 4, 1, 16, 34, 22, 20, 9, 36, 30, 3, 21, 11, 26, 6, 33, 27, 2, 13, 18, 5]
禁忌搜索：
解：[(13, 13), (11, 9), (6, 12), (6, 15), (3, 15), (0, 10), (2, 9), (1, 7), (0, 3), (4, 4), (3, 4), (4, 3), (5, 2), (13, 1), (14, 0), (19, 2), (18, 3), (17, 3), (15, 7), (18, 7), (18, 9), (18, 10), (19, 11), (17, 11), (13, 14), (13, 13)]
下标顺序：[27, 2, 13, 18, 25, 5, 29, 15, 19, 28, 10, 24, 12, 17, 34, 20, 9, 36, 30, 14, 3, 21, 26, 11, 33]
遗传算法：
解：[(6, 15), (6, 12), (0, 10), (1, 7), (0, 3), (4, 4), (5, 2), (8, 3), (10, 5), (11, 4), (14, 1), (14, 0), (17, 3), (18, 3), (19, 2), (18, 7), (18, 10), (19, 11), (17, 11), (15, 7), (11, 9), (11, 12), (13, 13), (13, 14), (9, 17), (6, 15)]
下标顺序：[18, 13, 5, 15, 19, 28, 12, 4, 1, 16, 22, 34, 36, 9, 20, 14, 21, 26, 11, 30, 2, 8, 27, 33, 7]
蚁群算法：
解：[(5, 2), (4, 3), (4, 4), (3, 4), (0, 3), (1, 7), (2, 9), (0, 10), (2, 15), (3, 15), (6, 15), (11, 9), (15, 7), (18, 7), (18, 9), (18, 10), (19, 11), (17, 11), (13, 13), (13, 14), (17, 3), (18, 3), (19, 2), (14, 0), (13, 1), (5, 2)]
下标顺序：[12, 24, 28, 10, 19, 15, 29, 5, 31, 25, 18, 2, 30, 14, 3, 21, 26, 11, 27, 33, 36, 9, 20, 34, 17]
