简介这套Python实现基于仿生群智算法的无人机任务分配方案聚焦多旅行商问题求解适合期末大作业、课程设计与项目开发使用。项目包含遗传算法、粒子群优化、蚁群优化等仿生群智算法实现配合绘图工具与配置说明可直接运行并观察任务分配效果。资源压缩包共8个文件以4个Python脚本为核心另有说明文档、许可证、版本忽略文件等整体仅19KB轻量易于上手。代码已经严格测试可在其基础上扩展新的约束条件或对比不同算法的求解效能。项目自带基础测试与绘图支持便于直观比较算法收敛趋势和分配路径。至今已有85位学习者下载适合熟悉Python基础、希望深入理解群智算法在组合优化中应用的开发者参考。目录模块划分清晰算法实现与辅助脚本分层明确方便快速定位核心逻辑。1. 从无人机任务分配到MTSP仿生群智算法先解决编码问题期末大作业里常见的一道题若干架无人机从基地起飞需要覆盖一批目标点每架访问完自己负责的点后返回基地每个目标点只被访问一次目标是让所有无人机的总飞行距离最短。把无人机换成销售人员这就是多旅行商问题Multiple Traveling Salesman Problem, MTSP。标题里的仿生群智算法指遗传算法GA、蚁群算法ACO、粒子群算法PSO这类从生物群体行为抽象出的元启发式算法。第一次做这个题的人容易直接调现成库换一组数据就失效。真正决定作业质量的是编码设计把“哪架无人机去哪些点、按什么顺序飞”翻译成一条染色体。编码定下来之后遗传算法主循环就是选择、交叉、变异三件事。2. 多旅行商问题建模与仿生群智算法选型为什么先写数学模型2.1 单基地与多基地两种建模口径作业题没有特殊说明时默认所有无人机从同一个基地出发这就是单基地 MTSP。数学上可以写成给定目标点集合 V{1,2,...,n}基地编号为 0K 架无人机需要把 V 划分成 K 个非空子集每架无人机从基地出发走一条覆盖自己子集内所有点的回路最后回到基地。优化目标是 K 条回路的总长度最小。形式化一点引入决策变量 x(i,j,k) 表示第 k 架无人机是否直接从点 i 飞往点 j目标函数是 d(i,j) 乘以 x(i,j,k) 对所有 k、i、j 求和。约束有三条每个目标点恰好被访问一次每架无人机的航线构成一条从基地出发并回到基地的回路每架无人机至少分到一个目标点。多基地模型的区别只是把单一基地换成多个起点每架无人机从各自的起点出发。建模这一步决定了后面所有代码的形态。单基地时距离矩阵直接以 0 行为基地行多基地时要把每个起点单独处理成一行解码回路的起终点也要跟着改。很多实现写到一半改需求就是因为建模时没确认清楚几个基地、无人机是否必须全部出动。2.2 GA、ACO、PSO 在 MTSP 上的取舍算法编码难度收敛速度MTSP 适配度典型场景遗传算法低排列加分割点即可中高20~100 个点课程设计与工程基线首选蚁群算法中要维护信息素矩阵和路径构建规则慢迭代次数要求高中高点规模大、允许离线计算的场景粒子群算法偏高连续位置要映射回排列空间快但容易早熟中需要快速给出可行解的原型验证遗传算法最适合作为期末大作业和课程设计的基线方案原因有三个编码直观调试时能把任意染色体解码回真实航线不依赖梯度天然契合离散组合优化Python 生态里不需要额外装求解器numpy 就能跑通。ACO 在 50 个点以内反而可能比 GA 慢因为每代要做 n 次路径构建计算量是 GA 的几倍。PSO 需要把连续的位置向量通过排序规则映射成排列多一步映射就多一个出错点作业周期短时不太划算。2.3 染色体编码排列加分割点一条染色体描述 K 条航线MTSP 遗传算法最常见的编码分两部分第一部分是目标点的一个排列表示访问顺序第二部分是 K-1 个分割点把排列切成 K 段每段对应一架无人机的航线。以下面这段 Python 为例route [3, 1, 4, 2, 5] # 目标点访问顺序0 是基地 cut_points [2] # 1 个分割点2 架无人机 segments, start [], 0 for bp in cut_points [len(route)]: segments.append(route[start:bp]) start bp # 结果: [[3, 1], [4, 2, 5]]分割点取 2排列被切成 [3,1] 和 [4,2,5] 两段解码时每段前后补上基地 0得到 0-3-1-0 和 0-4-2-5-0 两条回路总距离是两段长度之和。为什么不把每个无人机单独编码成一条染色体因为多染色体交叉时很难控制“每个点只被访问一次”这个硬约束修复成本很高。排列加分割点的好处是交叉变异无论怎么操作第一部分始终是一个排列约束从“需要修复”降级成“自动满足”。3. Python实现遗传算法求解无人机MTSP从初始化到收敛3.1 数据准备生成目标点与距离矩阵作业里一般给的是坐标文件这里用固定随机种子生成测试数据保证实验结果可复现。import numpy as np import random def gen_cities(n, seed42): 生成 n 个目标点坐标点 0 当作基地 rng np.random.default_rng(seed) return rng.uniform(0, 100, size(n, 2)) def build_dist_matrix(cities): 用广播一次性算出全连接距离矩阵 diff cities[:, None, :] - cities[None, :, :] return np.sqrt((diff ** 2).sum(axis-1))gen_cities 里点 0 固定为基地生成坐标范围 0~100单位无所谓距离只参与相对比较。build_dist_matrix 用 numpy 广播避免了双层循环距离矩阵在遗传算法里每代要被读取几千次提前算好能省掉大量重复计算。规模 200 个点以内时 n 阶方阵的内存没有问题如果以后扩展到几千个点再考虑用 scipy.spatial.cKDTree 做近邻查询而不是维护全矩阵。3.2 种群初始化排列加分割点的完整个体每个个体是一个元组 (route, cut_points)route 是目标点编号的随机排列cut_points 是升序的 K-1 个分割点。def init_individual(num_cities, num_uavs): route list(range(1, num_cities)) # 只包含目标点0 是基地 random.shuffle(route) # 随机打乱访问顺序 cut_points sorted( random.sample(range(1, num_cities), num_uavs - 1) ) return route, cut_points def init_population(pop_size, num_cities, num_uavs): return [init_individual(num_cities, num_uavs) for _ in range(pop_size)]init_individual 里 route 不包含基地 0因为基地是所有回路的公共起终点放进排列会导致解码逻辑混乱。cut_points 从 1 到 num_cities-1 之间不重复抽样保证每段至少有一个目标点避免出现某架无人机空载。如果题目允许无人机不执行任务可以在解码阶段过滤空段但大多数作业隐含“每架无人机都要出动”所以初始化时直接保证非空。3.3 适应度函数与锦标赛选择def decode(route, cut_points, dist_mat): 把染色体解码成各无人机航线返回总距离 segments, start [], 0 for bp in cut_points [len(route)]: segments.append(route[start:bp]) start bp total 0.0 for seg in segments: prev 0 # 从基地出发 for city in seg: total dist_mat[prev, city] prev city total dist_mat[prev, 0] # 回到基地 return total def fitness(individual, dist_mat): route, cut_points individual return 1.0 / (decode(route, cut_points, dist_mat) 1e-6)decode 是整段代码里最需要写对的地方每段回路的起点和终点都必须是基地 0中间按排列顺序访问目标点。fitness 取总距离的倒数距离越小适应度越大加 1e-6 防止总距离为零时除零。选择算子用锦标赛选择def tournament_select(population, fit_values, k3): 从 k 个随机个体中选出总距离最短的一个 idx random.sample(range(len(population)), k) best min(idx, keylambda i: fit_values[i]) return population[best]参数 k 控制选择压力k 越大强个体越容易胜出收敛变快但种群多样性下降k 取 3 在多数算例上比较均衡个体数少于 30 时建议降到 2。3.4 顺序交叉与变异算子排列编码不能用普通单点交叉否则子代会重复或缺失编号。这里用顺序交叉OXdef ox_crossover(p1, p2): 顺序交叉子代继承 p1 的一段其余按 p2 顺序填充 size len(p1) a, b sorted(random.sample(range(size), 2)) child [-1] * size child[a:b1] p1[a:b1] # 继承父代1的连续片段 pos (b 1) % size for gene in p2: if gene not in child: # 只填缺失的基因 child[pos] gene pos (pos 1) % size return child def mutate(route, cut_points, num_cities, rate0.1): 交换变异 分割点重采样两个独立判断 if random.random() rate: i, j random.sample(range(len(route)), 2) route[i], route[j] route[j], route[i] if random.random() rate: cut_points sorted( random.sample(range(1, num_cities), len(cut_points)) ) return route, cut_pointsox_crossover 先随机取两个交叉点 a、b孩子继承父代 1 的这一段剩下的空位按父代 2 的基因顺序从左到右填补in 判断保证不重复。变异做了两件独立的事排列部分的交换变异负责微调访问顺序分割点重采样负责改变任务划分。注意交叉时分割点不参与运算直接随机继承两个父代中某一个的分割点否则子代段数可能和无人机数量对不上。3.5 主循环把选择、交叉、变异串起来def run_ga(dist_mat, num_cities, num_uavs, pop_size80, generations200, cx_rate0.8, mut_rate0.1, seed1): random.seed(seed) pop init_population(pop_size, num_cities, num_uavs) best_history [] for gen in range(generations): fit [fitness(ind, dist_mat) for ind in pop] best min(pop, keylambda ind: decode(ind[0], ind[1], dist_mat)) best_history.append(decode(best[0], best[1], dist_mat)) new_pop [best] # 精英保留 while len(new_pop) pop_size: p1 tournament_select(pop, fit) p2 tournament_select(pop, fit) if random.random() cx_rate: r1 ox_crossover(p1[0], p2[0]) r2 ox_crossover(p2[0], p1[0]) c1, c2 (r1, p1[1]), (r2, p2[1]) else: c1, c2 list(p1), list(p2) new_pop.append(mutate(c1[0], c1[1], num_cities, mut_rate)) new_pop.append(mutate(c2[0], c2[1], num_cities, mut_rate)) pop new_pop[:pop_size] return best_history, best主循环里最有价值的一行是new_pop [best]精英策略保证当前最优解不被交叉变异破坏。交叉生成的子代数量超过种群规模时直接截断到 pop_size。best_history 记录每一代的最优总距离供第 4 章画收敛曲线用。入口脚本只要读坐标、建距离矩阵、调 run_ga、打印 best 的解码结果5 架无人机 50 个目标点跑 200 代单线程大约几秒钟。4. 无人机任务分配的参数怎么调种群规模、交叉率、变异率对照实验与三个坑4.1 四个必调参数速查表参数含义推荐范围调参方向pop_size种群规模50~200点数越多取值越大超过 200 后收益递减generations迭代代数100~500看收敛曲线是否走平走平即可停止cx_rate交叉概率0.7~0.9偏大搜索范围广过大会拖慢收敛mut_rate变异概率0.05~0.2防止早熟过大会退化成随机搜索50 个目标点、5 架无人机的小规模算例pop_size80、generations200 通常几十代就能收敛到稳定区间。判断依据不是代数越大越好而是看 best_history 后半段斜率是否接近零。mut_rate 是最敏感的项0.1 附近效果稳定调到 0.3 以上解的质量会明显下降因为变异破坏了已积累的优良基因。4.2 固定随机种子的对照实验模板import matplotlib.pyplot as plt def compare_params(dist_mat, n, k, experiments): for params in experiments: hist, _ run_ga(dist_mat, n, k, seed7, **params) label fpop{params[pop_size]}, mut{params[mut_rate]} plt.plot(hist, labellabel) plt.xlabel(generation) plt.ylabel(best total distance) plt.legend() plt.show()注意对照组必须共享同一个随机种子。种子不同初始种群就不同画出来的收敛曲线差异可能完全来自随机性而不是参数差异。实验设计上至少跑三组一组按推荐值、一组调大变异率到 0.2、一组调小种群到 40分别对应“基线”“防早熟”“快速验证”三个目的。这样实验报告里既有横向对比图又能解释每组参数背后的权衡。4.3 三个容易踩的坑第一个坑是分割点越界。分割点如果从 0 到 num_cities-1 之间随机取可能抽出 0导致第一段为空初始化用range(1, num_cities)能避免变异重采样时也必须沿用同样边界不能只在初始化时保证一次。第二个坑是交叉后基因重复。自己实现单点交叉而不做合法性修复排列里会出现重复编号和缺失编号解码时距离矩阵索引可能报错更隐蔽的情况是得到“能跑通但明显不合法”的解。排查方法解码后把所有段拼回去排序后与原始排列比较不一致就说明交叉算子有问题。第三个坑是罚函数的量级。题目加了“无人机最大航程”约束时常见做法是超限段加大罚值。罚值太小约束形同虚设罚值太大则适应度被罚项主导真实距离信息丢失算法退化成只找可行解不找最优解。建议罚值取当前代种群平均航程的 2~3 倍并随代数增加自适应放大前期允许超限试探后期强制收敛到可行域内。5. 期末大作业与课程设计交付目录结构、文档重点与结果可视化5.1 项目目录怎么组织drone_mtsp/ ├── README.md ├── requirements.txt ├── config.py ├── data/ │ └── cities.csv ├── src/ │ ├── model.py # 距离矩阵与解码逻辑 │ ├── ga.py # 遗传算法主逻辑 │ ├── visualize.py # 结果绘图 │ └── main.py # 命令行入口 └── docs/ ├── 需求分析.md ├── 算法设计.md └── 实验报告.md这个结构的功能分离点很明确main.py 只读 config.py 里的参数并调用 ga.py后续换 ACO 或 PSO 时新增一个 swarm.py 即可model.py 和 visualize.py 完全不用动。整个项目源码控制在 400 行以内函数职责单一答辩时被问到任何函数都能在两句话内说清输入输出。5.2 文档里的三块得分点算法设计文档重点写约束的数学化表达和编码设计意图不要贴大段代码要解释为什么用排列加分割点而不是多染色体编码。实验报告要有对照参数表、收敛曲线图和三组实验结果分析缺一不可。README 写清楚运行方式和环境依赖Python 3.8 以上、numpy、matplotlib给出pip install -r requirements.txt和python src/main.py两行命令即可。5.3 用可视化验证解是否合法def plot_solution(cities, route, cut_points, save_pathNone): 按无人机分组绘制航线基地用红点标出 segments, start [], 0 for bp in cut_points [len(route)]: segments.append([0] route[start:bp] [0]) start bp colors plt.cm.tab10(np.linspace(0, 1, len(segments))) for seg, c in zip(segments, colors): xs, ys cities[seg, 0], cities[seg, 1] plt.plot(xs, ys, markero, colorc) plt.scatter(cities[0, 0], cities[0, 1], cred, s80) if save_path: plt.savefig(save_path, dpi150, bbox_inchestight) plt.show()验证时看三点每条航线首尾是否都是基地红点、不同颜色的线段之间有没有重复目标点、有没有异常的长环或交叉。出现两段共用目标点说明交叉算子的 in 判断有 bug某段特别长而其他段极短优先检查分割点变异是否越界。这张图直接存成 PNG 放进实验报告比任何文字描述都直观也是答辩时最容易被追问的素材。本文还有配套的精品资源点击获取