5 分钟跑通蚁群算法：scikit-opt TSP 实战

5 分钟跑通蚁群算法scikit-opt TSP 实战【免费下载链接】scikit-optGenetic Algorithm, Particle Swarm Optimization, Simulated Annealing, Ant Colony Optimization Algorithm,Immune Algorithm, Artificial Fish Swarm Algorithm, Differential Evolution and TSP(Traveling salesman)项目地址: https://gitcode.com/GitHub_Trending/sci/scikit-opt这篇文章带你在 scikit-opt 库里用蚁群算法ACA_TSP解决旅行商问题从安装到调参跑通一个 25 城市的 TSP 求解实例再讲收敛判断和常见坑。 先跑起来安装与最小可运行示例scikit-opt 安装就一条命令pip install scikit-opt然后直接跑这段最小示例6 个城市先看结果再说import numpy as np from scipy import spatial from sko.ACA import ACA_TSP n 6 # 城市数 coords np.random.rand(n, 2) # 随机落点 dist spatial.distance.cdist(coords, coords, metriceuclidean) def total_len(route): # 绕一圈的总路程 return sum(dist[route[i], route[(i 1) % n]] for i in range(n)) ant ACA_TSP(functotal_len, n_dimn, size_pop20, max_iter50, distance_matrixdist) best_route, best_len ant.run() print(最短路径长度:, round(best_len, 4))最短路径长度: 2.3174跑通了有结果了。下面拆开讲它是怎么来的。 蚁群算法到底在干什么30 秒理解版一句话类比一群快递员同时出门跑单谁走通的路线被贴上越多便签后来者就越优先抄这条路便签会随时间褪色所以队伍不会永远困在旧路线上总有新的捷径被试出来。对应到代码里每轮迭代就做四件事信息素初始化所有路段的热度先设成相同的起始值路径选择每只蚂蚁站在当前城市按热度 × 距离倒数加权随机挑下一站信息素更新一圈跑完后总路程越短的蚂蚁在走过的路段上刷越多热度自然挥发每轮先按比例清掉一部分热度再叠加新刷上去的这套逻辑全部封装在ACA_TSP类里源码见 sko/ACA.py你实际只需要关心run()这一个入口。 ACA_TSP 参数速查表ACA_TSP的参数不多一张表讲清楚 ACA_TSP 参数怎么配参数名含义推荐起步值调大的影响调小的影响size_pop蚂蚁数量群体规模城市数的 2 倍路线多样性更高不易卡局部但每轮更慢速度快探索不足解质量下降max_iter最大迭代次数200搜索更充分总耗时线性增加可能没收敛就提前停了alpha信息素权重因子1更信热度偏利用容易反复走同一条路选择更随机探索增强beta启发式信息权重2更信距离偏探索行为趋近贪心挑近路更依赖信息素随机性变大rho信息素挥发系数0.1热度退得快不易早熟但收敛变慢热度残留久容易过早收敛新手阶段先盯size_pop和rho就够了一个决定队伍规模一个决定遗忘速度。其余参数保持默认等结果不理想再回头调。️ 完整实战25 城市 TSP 求解上正题25 个随机城市求一圈的最短访问顺序。完整代码如下import numpy as np from scipy import spatial from sko.ACA import ACA_TSP # 1. 随机生成 25 个城市坐标 n_city 25 city_coords np.random.rand(n_city, 2) # 2. 城市两两间的欧氏距离构成距离矩阵 dist_matrix spatial.distance.cdist(city_coords, city_coords, metriceuclidean) # 3. 目标函数输入访问顺序返回绕一圈的总距离 def route_length(order): return sum(dist_matrix[order[i], order[(i 1) % n_city]] for i in range(n_city)) # 4. 配置蚁群参数并运行 ant ACA_TSP(funcroute_length, n_dimn_city, size_pop50, # 城市数的 2 倍 max_iter200, distance_matrixdist_matrix) best_order, best_length ant.run() # 5. 输出结果 print(最短路径长度:, round(best_length, 4)) print(最优访问顺序:, best_order.tolist())最短路径长度: 3.2841 最优访问顺序: [3, 21, 4, 17, 9, 24, 0, 12, 19, 6, 2, 22, 15, 8, 23, 11, 5, 1, 14, 18, 10, 16, 13, 7, 20]第一段是数据准备坐标随机生成距离矩阵用scipy的cdist一次算好。注意算法本身只依赖这个矩阵坐标仅在计算距离时用了一次。第二段定义目标函数。ACA_TSP对你的问题一无所知它只是拿你给的func给每条路线打分所以距离怎么算完全由你决定。第三段是核心把目标函数、城市数、群体规模、距离矩阵交给ACA_TSPrun()返回最优顺序best_order和对应长度best_length。官方示例在 examples/demo_aca_tsp.py里面还带了画图代码。 看收敛曲线你的解够不够好跑完后ant.y_best_history里存着每一轮的最优长度画出来只要几行import pandas as pd import matplotlib.pyplot as plt pd.DataFrame(ant.y_best_history).cummin().plot() plt.xlabel(迭代次数); plt.ylabel(历史最优路径长度); plt.show()曲线前半段快速下坠、后段贴着底部走平说明基本收敛了如果到最后一轮还在明显下滑就加大max_iter再跑一轮。 调参 避坑指南常见误区正确做法只跑一次就下结论随机性强建议跑 5 次取最优或固定随机种子做对比size_pop设太小经验值是城市数的 1.5~2 倍太小路线多样性不足rho设为 0不挥发热度只增不减队伍很快锁死在一条路上建议 0.1~0.5漏传distance_matrix转移概率要用它算倒数启发值属于必传参数期望得到精确最优解蚁群找的是近似解把max_iter翻倍后长度不再变化就可以接受当前结果alpha和beta是最常被问到的信息素参数调优方向alpha调大蚂蚁更信信息素偏利用beta调大蚂蚁更信距离偏探索。如果你发现结果总停在差不多的位置先调大rho再考虑动alpha。 蚁群算法还能干嘛TSP 只是最顺手的练手题同一套排序即解的思路还能迁到这些场景VRP 车辆路径给多条路线加容量约束解决配送车队怎么派车网络路由节点当路由器、边权当延迟给数据包挑低延迟路径任务调度把任务排成一个执行顺序最小化总完成时间资源分配把分配方案映射成排列顺序按总代价打分scikit-opt 里各算法的接口风格一致目标函数 run()只要你能把问题改写成给一个排列打分换算法基本只是换 import 的事。 延伸阅读这份蚁群算法 Python 实现只是 scikit-opt 的一个模块其他算法可以对照着学粒子群优化sko/PSO.py遗传算法sko/GA.py模拟退火sko/SA.py差分进化sko/DE.py图文教程入口在 docs/中英文文档都有。写在最后参数表里的数字都只是起点曲线和结果才是答案。把上面那段完整实战代码跑起来改两个参数再看一眼收敛曲线你就已经入门蚁群算法了。【免费下载链接】scikit-optGenetic Algorithm, Particle Swarm Optimization, Simulated Annealing, Ant Colony Optimization Algorithm,Immune Algorithm, Artificial Fish Swarm Algorithm, Differential Evolution and TSP(Traveling salesman)项目地址: https://gitcode.com/GitHub_Trending/sci/scikit-opt创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考