使用启发式算法模拟退火禁忌搜索遗传算法与蚁群算法求解广义旅行商(广义TSPGTSP)问题python源码+项目说明.zip

# 简单说明 使用四种基本启发式算法求解广义TSP问题。 所谓广义TSP，即一些城市可能卖的是同一类商品，在买这类商品时仅走这些城市其中之一即可。 目录： - images - 只是一些结果图片 - codes ** - extendTSP.py 用于随机生成广义TSP实例，并提供一些通用函数(如生成广义TSP实例，生成距离等) - SA.py 模拟退火 - tabu.py 禁忌搜索 - Genetic.py 遗传算法 - ACO.py 蚁群算法 依赖：matplotlib + numpy，python3 可以通过extendTSP.py 中的 extendTSP_generate() 函数来生成实例 ```python 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种商品为例 除路径图外 还可以打印最优解迭代情况等 问题定义： ```python # 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() 函数来验证解的正确性 ```python 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