基于python旅行商问题(TSP) 动态规划算法、蚁群算法、遗传算法实现源代码(带数据和代码注释).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, 8, 27, 33, 7]  蚁群算法： 解：[(5,