简介本资源面向计算机、人工智能、自动化等专业的在校学生与算法学习者提供一套基于仿生群智算法求解无人机任务分配多旅行商问题的Python课程设计源码。项目以群体智能大作业为背景实现了ACO蚁群算法、GA遗传算法与PSO粒子群算法三种基线方案并设置200个epochs迭代与Early Stop早停策略便于对比不同算法的收敛表现。压缩包共7个文件包含4个py源码、1个md说明文档、1个license及1个gitignore整体约19KB代码结构清晰、注释详尽可直接运行验证。目前已有246人学习关注。读者可借此掌握多旅行商问题的建模思路、群智算法的实现细节与调参方法也可在此基础上修改扩展用于课程设计、毕业设计或项目初期立项演示具备较高的学习与参考价值。1. 从一份课设说起仿生群智算法怎么把无人机任务分配讲明白很多人第一次接触“无人机任务分配”是在课程设计里题目往往长这样给定若干目标和若干架无人机每架无人机从基地出发飞完分配给自己的目标后返回要求总航程最短、负载均衡、不超时。把它抽象成数学模型本质就是多旅行商问题MTSP多个销售员从同一城市出发各自走一条闭合回路覆盖所有城市且不重复使总代价最小。区别在于无人机还有航程约束、转弯半径、任务类型差异所以不能直接套经典 TSP 求解器。仿生群智算法就是在这个背景下被引入的蚁群、粒子群、人工蜂群、灰狼、麻雀搜索这类算法不依赖梯度能处理离散组合优化还能通过信息素或位置更新自然实现并行搜索。对课设来说它的价值在于代码量可控、参数可解释、结果可视化直观答辩时能讲清楚“为什么这样迭代”。这篇笔记面向正在做这个题目的同学也面向想把 MTSP 求解器落到实际调度场景的工程师从建模、编码、参数到踩坑一步步把可复现的 Python 源码结构讲透。2. 把无人机任务分配写成 MTSP建模与数据准备2.1 为什么选 MTSP 而不是 VRP 或 TSP单旅行商问题TSP只有一个闭环多旅行商问题MTSP允许 m 条闭环两者在解空间维度上差一个数量级。车辆路径问题VRP虽然也是多车但通常带容量约束和取送货顺序对课设来说约束太多反而掩盖了群智算法的搜索机制。无人机任务分配更接近 MTSP 的变体m 架无人机从同一基地出发各自访问若干目标点后返回基地目标点只访问一次代价函数是总航程或最大单机航程。常见做法是把 MTSP 转成 TSP 再求解增加 m-1 个虚拟基地节点让一条长路径在虚拟节点处断开成 m 段。这种编码简单但虚拟节点的位置会影响解质量。我一般直接用“分段整数编码”染色体长度等于目标点数每个基因是目标编号再用 m-1 个切点把序列切成 m 段每段对应一架无人机的访问顺序。这样交叉变异都在目标序列上做切点单独进化逻辑清晰。数据准备阶段需要三类输入目标点坐标或距离矩阵、无人机数量 m、每架无人机的最大航程。坐标用二维数组存距离矩阵用欧氏距离预计算避免迭代中反复开方。下面这段代码就是标准的数据初始化注意距离矩阵用np.linalg.norm向量化计算比双重循环快一个量级。import numpy as np def build_distance_matrix(coords): coords: shape (n, 2)第一行是基地其余是目标点 返回: shape (n, n) 的对称距离矩阵 diff coords[:, np.newaxis, :] - coords[np.newaxis, :, :] dist np.linalg.norm(diff, axis-1) np.fill_diagonal(dist, 0.0) return dist # 示例1 个基地 20 个目标点 np.random.seed(42) coords np.random.rand(21, 2) * 100 dist_matrix build_distance_matrix(coords) print(dist_matrix.shape) # (21, 21)逻辑说明coords[:, np.newaxis, :] - coords[np.newaxis, :, :]利用广播生成 (n, n, 2) 的差值张量再沿最后一维求范数得到 (n, n) 距离矩阵。参数上coords第一行必须是基地后续所有索引 0 都代表基地这样计算航程时直接取dist[0, first] ... dist[last, 0]。如果目标点超过 200 个建议改用 KDTree 或直接读入外部距离矩阵避免内存膨胀。2.2 适应度函数总航程、最大航程与负载均衡怎么加权适应度函数决定了算法往哪个方向收敛。课设里最常见的翻车是只写总航程结果一架无人机飞完全部点其余无人机空载答辩时被问“这算多旅行商吗”。正确的做法是把最大单机航程和航程标准差也纳入惩罚项。我一般用加权和fitness w1 * total_distance w2 * max_distance w3 * std_distance penaltyw1通常取 1.0w2取 0.5 到 1.0w3取 0.2 到 0.5。如果某架无人机超过最大航程直接加一个很大的惩罚值比如 1e6让该个体在选择阶段被淘汰。下面是对应的 Python 实现注意切点解码后要检查每段是否为空空段意味着有无人机没任务也要惩罚。def decode_routes(sequence, cut_points, m): sequence: 目标点排列长度 n-1不含基地 cut_points: 长度为 m-1 的递增切点范围 [1, len(sequence)-1] 返回: m 条路线每条以 0基地开头和结尾 cuts [0] sorted(cut_points) [len(sequence)] routes [] for i in range(m): seg sequence[cuts[i]:cuts[i1]] routes.append([0] list(seg) [0]) return routes def fitness(sequence, cut_points, dist_matrix, m, max_range, weights(1.0, 0.8, 0.3)): routes decode_routes(sequence, cut_points, m) total, max_d, penalty 0.0, 0.0, 0.0 lengths [] for r in routes: if len(r) 2: # 空路线只有基地往返 penalty 1e5 lengths.append(0.0) continue d sum(dist_matrix[r[i], r[i1]] for i in range(len(r)-1)) lengths.append(d) total d max_d max(max_d, d) if d max_range: penalty 1e6 * (d - max_range) std_d np.std(lengths) w1, w2, w3 weights return w1 * total w2 * max_d w3 * std_d penalty逻辑说明decode_routes把排列和切点还原成 m 条闭合路线每条路线首尾都是 0。fitness里对空路线和超航程分别加惩罚std_d用 NumPy 计算标准差。参数上max_range根据无人机实际续航折算课设里可以设为总平均航程的 1.5 倍weights建议先用默认值跑通再根据结果调整如果发现某架无人机总是超载就调大w2。2.3 数据校验三个容易忽略的边界第一目标点数量必须大于无人机数量否则必然出现空路线这时候要么减少 m要么允许一架无人机访问多个点但切点重复。第二距离矩阵必须对称且对角线为 0如果从外部文件读入先做np.allclose(dist, dist.T)检查。第三坐标量纲要统一如果经纬度直接当平面坐标用距离会严重失真建议先做墨卡托投影或直接用局部平面坐标。这三条在课设报告里写清楚能省掉答辩时一半的追问。3. 仿生群智算法选型蚁群、粒子群还是人工蜂群3.1 三种算法的搜索机制与 MTSP 适配度蚁群算法ACO靠信息素和启发式因子构建路径天然适合离散排列问题但标准 ACO 是为 TSP 设计的用到 MTSP 需要改状态转移规则每只蚂蚁可以多次从基地出发或者用 m 只蚂蚁同时构建 m 条路径。粒子群PSO原本是连续优化用在 MTSP 上必须做离散化常见做法是用随机键random key编码粒子位置是连续向量排序后得到目标访问顺序再取前 m-1 个切点。人工蜂群ABC的雇佣蜂、观察蜂、侦察蜂三段式搜索对排列问题可以用交换、逆序、插入三种邻域操作实现简单但收敛速度偏慢。从课设角度我一般推荐“离散粒子群 随机键”作为主线因为代码最短、参数最少、可视化最直观如果指导老师明确要求群智算法对比就再加一个蚁群版本用同一套适应度函数最后画收敛曲线对比。下面给出离散粒子群的核心迭代代码粒子位置是长度 n-1 (m-1) 的连续向量前段排序得到目标序列后段排序得到切点。class DiscretePSO: def __init__(self, n_targets, m, pop_size50, max_iter200): self.n n_targets self.m m self.dim n_targets (m - 1) self.pop_size pop_size self.max_iter max_iter self.w, self.c1, self.c2 0.7, 1.5, 1.5 def _decode(self, pos): seq np.argsort(pos[:self.n]) 1 # 目标编号从 1 开始 cuts np.sort(pos[self.n:]) # 切点用连续值排序 cut_idx np.argsort(cuts)[:self.m-1] 1 cut_idx np.clip(np.sort(cut_idx), 1, self.n - 1) return seq, cut_idx def run(self, dist_matrix, max_range): pos np.random.rand(self.pop_size, self.dim) vel np.random.randn(self.pop_size, self.dim) * 0.1 pbest pos.copy() pbest_fit np.array([fitness(*self._decode(p), dist_matrix, self.m, max_range) for p in pos]) gbest pbest[np.argmin(pbest_fit)].copy() gbest_fit np.min(pbest_fit) history [] for it in range(self.max_iter): r1, r2 np.random.rand(), np.random.rand() vel (self.w * vel self.c1 * r1 * (pbest - pos) self.c2 * r2 * (gbest - pos)) pos np.clip(pos vel, 0, 1) for i in range(self.pop_size): seq, cuts self._decode(pos[i]) f fitness(seq, cuts, dist_matrix, self.m, max_range) if f pbest_fit[i]: pbest[i], pbest_fit[i] pos[i].copy(), f if f gbest_fit: gbest, gbest_fit pos[i].copy(), f history.append(gbest_fit) return self._decode(gbest), gbest_fit, history逻辑说明_decode把连续位置前 n 维排序得到目标序列后 m-1 维排序后取索引作为切点np.clip保证切点不越界。迭代中标准 PSO 的速度更新公式保留位置限制在 [0,1] 区间避免排序失效。参数上pop_size取 30 到 80max_iter取 200 到 500惯性权重w可以从 0.9 线性降到 0.4前期探索后期收敛。如果结果波动大把c1调小、c2调大让粒子更快向全局最优靠拢。3.2 参数怎么设种群、迭代、交叉变异概率种群规模不是越大越好。20 个目标点、3 架无人机的课设规模种群 50 足够超过 100 只会让单次迭代变慢收敛曲线反而更抖。迭代次数看收敛曲线如果 150 代后适应度变化小于 1e-3就可以停。交叉概率在离散 PSO 里对应的是“位置更新幅度”如果发现早熟把c1和c2都降到 1.0 以下增加随机扰动。对于蚁群版本关键参数是信息素挥发率rho和启发式因子权重beta。rho取 0.1 到 0.3太大导致信息素积累不足太小导致搜索停滞。beta取 2 到 5越大越贪心容易陷入局部最优。人工蜂群的重点是观察蜂数量一般设为雇佣蜂的一半侦察蜂阈值limit取 20 到 50 代。提示参数没有万能值建议先用小规模数据10 个目标点、2 架无人机跑通记录每组参数的最优适应度再放大到课设规模。不要一上来就调 500 代浪费时间。3.3 收敛曲线与路线图怎么判断结果可信收敛曲线要画两条全局最优和种群平均。如果平均线一直贴着最优线说明种群多样性不足早熟了如果平均线剧烈震荡说明参数太激进。路线图用matplotlib画基地用星号不同无人机用不同颜色箭头表示访问顺序。检查路线图时重点看三件事有没有交叉路线说明还有优化空间、有没有某架无人机绕远路负载不均、有没有路线穿过禁飞区如果题目有约束。import matplotlib.pyplot as plt def plot_routes(coords, routes, titleUAV Routes): plt.figure(figsize(8, 6)) colors plt.cm.tab10(np.linspace(0, 1, len(routes))) for idx, r in enumerate(routes): pts coords[r] plt.plot(pts[:, 0], pts[:, 1], -o, colorcolors[idx], labelfUAV {idx1}, markersize4) plt.scatter(coords[0, 0], coords[0, 1], cred, marker*, s200, labelBase) plt.legend() plt.title(title) plt.grid(True, alpha0.3) plt.show()逻辑说明coords[r]按路线顺序取出坐标plot连线并标点基地单独用红色星号。参数上figsize根据目标点密度调整点太密时把markersize降到 2。如果路线交叉严重回到适应度函数检查是否漏了最大航程惩罚。4. 避坑与排查课设里最容易翻车的五个地方4.1 现象算法跑完所有无人机都挤在一条路线上原因适应度函数只算总航程没有对单机航程做惩罚算法发现把所有点塞给一架无人机总距离最短。解决在适应度里加入最大航程项和标准差项权重从 0.5 起步观察路线是否分散。如果仍然集中检查切点解码是否把切点都映射到了序列末尾导致前 m-1 段为空。4.2 现象收敛曲线前期下降很快后期完全不动原因种群多样性丢失所有粒子位置趋同。解决在 PSO 里加入变异操作每代以 0.05 到 0.1 的概率随机重置某个粒子的位置或者把惯性权重设为线性递减前期 0.9 后期 0.4。蚁群版本则提高挥发率rho到 0.3让信息素更快更新。4.3 现象距离矩阵计算报错或结果异常大原因坐标数组形状不对或者经纬度直接当平面坐标。解决打印coords.shape确认是 (n, 2)用np.allclose(dist, dist.T)检查对称性。如果是经纬度先用x lon * 111 * cos(lat)做粗略投影或者直接改用局部坐标系。4.4 现象切点解码后路线数量不对原因切点排序后没有去重或者np.clip把多个切点压到同一个值。解决在decode_routes里对切点做sorted(set(cut_points))如果去重后数量不足 m-1用随机值补齐。更稳妥的做法是在解码前检查切点唯一性不满足就重新生成。4.5 现象换了随机种子结果差异巨大原因群智算法本身是随机搜索单次运行不能代表算法性能。解决固定随机种子做调试但最终报告里要跑 10 次取平均值和标准差画箱线图。如果标准差超过均值的 20%说明参数不稳定需要增大种群或迭代次数。5. 进阶技巧用局部搜索和并行化把解质量再提一档群智算法跑完之后最优解往往还留有明显的交叉路线。这时候加一段 2-opt 局部搜索对每条路线内部做边交换能在几十毫秒内把总航程再降 3% 到 8%。具体做法是对每条路线尝试交换任意两条边的端点如果总距离减小就接受重复直到没有改进。下面是一个针对单条路线的 2-opt 实现注意基地节点 0 不参与交换。def two_opt(route, dist_matrix): route: 以 0 开头和结尾的列表返回优化后的路线 improved True best route[:] while improved: improved False for i in range(1, len(best) - 2): for j in range(i 1, len(best) - 1): if j - i 1: continue new_route best[:i] best[i:j][::-1] best[j:] old_d sum(dist_matrix[best[k], best[k1]] for k in range(len(best)-1)) new_d sum(dist_matrix[new_route[k], new_route[k1]] for k in range(len(new_route)-1)) if new_d old_d - 1e-9: best new_route improved True # 一轮结束后重新开始直到没有改进 return best逻辑说明外层while保证反复扫描直到收敛内层双重循环枚举所有边对best[i:j][::-1]实现片段反转。参数上1e-9是浮点比较容差避免死循环。如果目标点超过 50 个2-opt 的 O(n²) 单轮会变慢可以限制每轮只扫描前 30 个最近邻。另一个提效手段是并行化把种群分成 4 组每组独立进化 50 代再合并最优个体。Python 里用multiprocessing.Pool就能做注意把距离矩阵和参数通过initializer传给子进程避免反复序列化。实测在 8 核机器上100 个目标点、5 架无人机的场景并行版比串行版快 3 倍左右解质量基本一致。最后说一个我自己的习惯每次调完参数先把最优路线和收敛曲线存成图片文件名带上参数组合比如pso_pop50_iter300_w0.7.png。课设报告写到后期你会感谢自己留了这些“后悔药”。仿生群智算法在无人机任务分配上不是银弹但它能把一个 NP-hard 问题拆成可解释、可调参、可可视化的迭代过程这对课设和实际调度都够用了。希望帮到你。本文还有配套的精品资源点击获取