简单说明

使用四种基本启发式算法求解广义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)的下标(不含回路)
'''

效果 - new

算法	耗时(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]

效果 - old

算法	耗时(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]