简介这份 PDF 是一篇航天工程优化领域的学术论文核心面向研究航天器协同任务分配、群体智能算法应用的高校师生、科研人员及算法工程师。论文针对多颗服务航天器在轨服务任务分配的难点提出离散粒子群优化DPSO算法设计了新的粒子位置与速度更新公式并综合目标卫星价值、服务航天器损耗、距离消耗等关键指标建立数学模型。内容包含任务编码、数据结构组织方式以及大规模任务分配中的寻优与收敛性能分析既可作算法研究方向的专业指导也可为运筹调度、智能优化等离散场景提供参考。资源包内为 1 个 PDF 文件共 371KB轻量便于快速查阅已有 126 人学习下载。读者可从论文中获取完整的算法设计思路、模型构建过程与仿真验证结论便于直接复现实验对比或借鉴其离散编码策略拓展到其他组合优化问题兼具理论价值和实践参考意义。1. 在轨服务任务分配难在哪离散粒子群算法能解决什么在轨服务任务分配的关键在于“任务必须在指定时间窗内被某颗服务航天器完成”这类问题既有时间窗约束又有服务机容量和燃料上限本质上是一个带约束的组合优化。直接套用标准粒子群算法会遇到很实际的问题连续实数向量无法直接解释成“由哪颗卫星、以什么顺序执行哪些任务”。离散粒子群算法把粒子位置当作任务优先级通过排序和贪心映射生成离散方案在搜索能力和实现复杂度之间取得较好平衡很适合任务规模不大但约束密集的快速规划场景。下面按照模型建立、编码设计、迭代代码、参数调优到验证细节的顺序完整展开并给出每个关键参数对应的物理含义。如果你已经熟悉标准 PSO 和遗传算法那这篇的重点可以放在时间窗约束处理与离散解码回写这两处。2. OOS 任务分配模型与任务优先级编码设计2.1 在轨服务任务分配的目标函数与约束条件先把问题抽象成一组带时间窗的任务节点。设服务机集合 S {1, 2, …, m}任务集合 T {1, 2, …, n}每台服务机从基地出发依次访问分配给自己的任务节点最后返航。目标函数是所有服务机路线消耗的 ΔV 总和最小min ∑_{s1..m} ( ∑_{i ∈ seq_s} C[prev_i][i] C[last_s][0] )其中 C[i][j] 是从节点 i 转移到节点 j 的燃料代价索引 0 表示服务基地。如果各服务机的停泊轨道不同把基地索引从 0 换成对应服务机驻泊点即可公式结构不变。这个形式意味着任务的顺序变化会直接影响燃料消耗所以“谁做、按什么顺序做”必须同时被优化仅做分配不考虑顺序是拿不到可执行方案的。约束条件有四个层面每台服务机执行的任务数不能超过容量 cap_s每个任务最多只能分配一次服务机到达任务节点的实际时刻必须落在窗口 [E_t, L_t] 内整条路线的累计 ΔV 不能超过服务机的可用燃料上限。时间窗约束是 OOS 与一般车辆路径问题差异最大的地方多数实现会把前两个约束设计成硬条件把时间窗处理成惩罚项理由是窄窗口会让可行解区域严重碎片化硬约束搜索在迭代初期几乎找不到可行粒子。2.2 标准粒子群算法的连续更新机制为何不兼容组合优化标准 PSO 的更新公式只有两行v(t1) w * v(t) c1 * r1 * (pbest - x(t)) c2 * r2 * (gbest - x(t))x(t1) x(t) v(t1)位置 x 是连续实数向量如果没有额外的离散化机制这个向量在 OOS 任务分配问题里没有语义。因为解是由“任务到服务机的映射”和“任务执行顺序”组成的连续数值无法直接表达这两个离散结构。有人会把位置值四舍五入成 0-1 分配矩阵但这种做法在规模稍大时会出现两个典型问题一个是两个任务同时被映射到同一台服务机的同一时间片另一个是某台服务机任务数突破容量时间窗约束更是难以用连续小步长调整来恢复。从搜索角度解释标准 PSO 依靠 pbest 与 gbest 的差向量来驱动粒子移动这种“差分牵引”在连续空间中能自然平滑地逼近最优区域。但组合优化的可行域不是凸的差向量往往指向一个不可行方式所以需要改变编码让位置向量的每个维度对应“任务优先级”而不是“是否选中”。2.3 基于任务优先级的 DPSO 编码与三种离散化映射常见的离散化映射有三种适用场景不同下面用表格做一个直接对比编码方式粒子向量长度可行性修复代价适用场景四舍五入映射m × n高需要反复重扫修正重复与超载无顺序要求的纯静态分配排序映射n低排序即为全局任务序列有顺序要求、有容量上限的路径分配组合块编码n中需要按块长度重新划分位置段任务存在先后依赖或执行窗口OOS 任务分配中我更推荐排序映射也就是 SPV 规则粒子的第 t 个分量代表任务 t 的优先级每个迭代周期内把所有分量按值从小到大排序得到一个任务优先级序列再把这个序列按容量约束贪心分配给各台服务机。这样每个任务在编码层天然只出现一次不需要额外处理重复映射问题。SPV 解码的最小实现很短先看这段def spv_decode(x, n_svc, capacity): # x: 每个任务对应的位置值, 长度为任务数 order np.argsort(x) # 位置越小, 任务优先级越高 load np.zeros(n_svc, dtypeint) plan [[] for _ in range(n_svc)] for task in order: for s in range(n_svc): if load[s] capacity: plan[s].append(int(task)) load[s] 1 break return plan这段代码把连续位置向量通过排序转成任务序列再按“第一台能放下的服务机”依次填充。capacity 是单台服务机的最大可执行任务数。如果所有服务机都已装满任务会落在所有 plan 之外实际应用时把它记为未分配任务并加惩罚。这个实现可以跑通但有一个明显缺陷任务总是优先填满编号靠前的服务机容易造成载荷分布偏斜。更稳妥的做法是按边际插入成本选择服务机在后面的完整代码里会体现这一点。3. 求解 OOS 任务分配的 DPSO 主循环与 Python 实现3.1 速度更新、SPV 解析与可行性修复的三段式流程DPSO 求解 OOS 任务分配的迭代过程可以拆成三段第一段执行标准 PSO 的速度与位置更新得到新一代的连续位置向量第二段把位置向量通过 SPV 规则解析成所有服务机的任务序列第三段对任务序列做容量、时间窗和燃料约束的检查与修复。这里要注意三段式不是简单地串行执行。第二段解析出来的序列如果不满足硬约束要修正后再计算适应度如果修正后的方案仍未满足时间窗就需要把不可行程度折算成惩罚项加入适应度。很多初学者把约束处理放在适应度函数里但修复与惩罚应该同时存在先修复能修复的再用惩罚兜底不能直接修复的。3.2 可运行的 DPSO 主循环代码下面给出一个完整可运行的简化实现。为了便于读者直接跑通成本矩阵 C 用随机对称矩阵代替真实轨道转移代价实际项目中替换成由轨道根数计算的 ΔV 矩阵即可。import numpy as np class DPSO: def __init__(self, n_task, n_svc, cap, C, n_pop30, n_iter300, w_max0.9, w_min0.4, c11.8, c21.8, v_max0.5): self.n_task n_task self.n_svc n_svc self.cap cap self.C C # 代价矩阵, 0 号节点是基地 self.n_pop n_pop self.n_iter n_iter self.w_max w_max self.w_min w_min self.c1 c1 self.c2 c2 self.v_max v_max self.x np.random.rand(n_pop, n_task) # 位置: 任务优先级 self.v np.random.uniform(-v_max, v_max, (n_pop, n_task)) self.pbest_x self.x.copy() self.pbest_cost np.full(n_pop, 1e12) self.gbest_x self.x[0].copy() self.gbest_cost 1e12 self.history [] def decode(self, xj): order np.argsort(xj) plan [[] for _ in range(self.n_svc)] load np.zeros(self.n_svc, dtypeint) for task in order: best_s, best_inc -1, 1e9 for s in range(self.n_svc): if load[s] self.cap: continue # 按插入到队尾的边际成本选择服务机 inc self.C[0 if len(plan[s]) 0 else plan[s][-1], task] if inc best_inc: best_s, best_inc s, inc if best_s 0: plan[best_s].append(int(task)) load[best_s] 1 return plan def route_cost(self, plan): total 0.0 for tasks in plan: if len(tasks) 0: continue prev 0 for t in tasks: total self.C[prev, t] prev t total self.C[prev, 0] # 返回基地 assigned sum(len(t) for t in plan) missing self.n_task - assigned return total missing * 100.0 # 未分配任务惩罚 def run(self): for epoch in range(self.n_iter): w self.w_max - (self.w_max - self.w_min) * epoch / self.n_iter for i in range(self.n_pop): plan self.decode(self.x[i]) cost self.route_cost(plan) if cost self.pbest_cost[i]: self.pbest_cost[i] cost self.pbest_x[i] self.x[i].copy() if cost self.gbest_cost: self.gbest_cost cost self.gbest_x self.x[i].copy() r1 np.random.rand(self.n_pop, self.n_task) r2 np.random.rand(self.n_pop, self.n_task) self.v (w * self.v self.c1 * r1 * (self.pbest_x - self.x) self.c2 * r2 * (self.gbest_x - self.x)) self.v np.clip(self.v, -self.v_max, self.v_max) self.x np.clip(self.x self.v, 0, 10) self.history.append(self.gbest_cost) return self.gbest_x, self.gbest_cost代码逻辑说明decode中不再使用“第一台能放下的服务机”而是计算每个任务插入到某台服务机任务序列末尾的边际成本选择增量最小的服务机这样能避免载荷全堆在第一台的偏斜问题。route_cost对每条路线累加基地到第一个任务、任务到任务、最后一个任务返回基地的三段 ΔV未分配部分按 100 倍代价作为惩罚。run的惯性权重 w 随迭代线性下降epoch 越靠后越偏重局部精化这一步直接影响收敛曲线的形态。参数说明v_max是速度上限位置向量被 clip 到 0 到 10 之间保证优先级数值区间稳定c1和c2分别是向个体最优和全局最优牵引的加速度系数n_pop是粒子数量任务量在 10 到 30 之间时取 30 通常够用。注意位置向量的绝对值大小并不重要重要的是迭代过程中它的相对次序保持稳定所以x的取值范围不需要严格限制在 0 到 1。3.3 时间窗与燃料约束的惩罚处理时间窗约束无法在解码阶段一次性修复因为它取决于每个任务在路线中的到达时刻。常见做法是先按顺序累加转移时间和服务时间超过窗口上界再触发惩罚。下面这段函数可以直接并入上面的route_costdef time_window_penalty(self, tw_early, tw_late, service_time): penalty 0.0 for tasks in self.decode(self.gbest_x): now 0.0 prev 0 for t in tasks: now self.C[prev, t] prev t if now tw_late[t]: penalty now - tw_late[t] now max(now, tw_early[t]) service_time[t] return penalty逻辑说明每当到达时刻晚于tw_late[t]就把超出部分累计进惩罚项如果早于tw_early[t]则等待到窗口下界再开始服务。这样时间窗被表达成连续可导的软约束粒子在迭代中可以逐步修正到达时刻。燃料约束的处理方式类似把单条路线累计 ΔV 超过服务机燃料上限的部分按比例放大为惩罚值。约束类型触发条件修复策略处理优先级容量约束服务机任务数达到上限改选边际成本最小的下一台服务机高时间窗约束到达时刻晚于窗口上界交换任务顺序后再判断高燃料上限约束单机累计 ΔV 超限裁剪序列末尾任务并标记未分配中这张表的用途是给解码与惩罚模块定边界容量约束必须在解码阶段解决时间窗可以软惩罚燃料超限如果只是罚款会造成大量不可执行解参与比较需要在迭代后期提高罚系数。4. 离散粒子群算法参数基线与防早熟调优4.1 一组适合 OOS 场景的参数基线表DPSO 参数对结果的影响比在标准 PSO 中更敏感因为离散解码放大了位置微扰带来的排序变化。下面这组参数基线适合任务数 10 到 30、服务机 2 到 4 台的常见规模参数符号推荐范围对结果的影响种群规模n_pop20 - 50小于 20 时容易丢失多样解惯性权重w0.4 - 0.9 线性递减前期探索后期开发加速度系数c1 / c21.5 - 2.5偏大易早熟偏小收敛慢速度上限v_max0.2 - 0.8影响迭代中任务顺序的跳变幅度迭代次数n_iter100 - 500窄时间窗任务需要更大迭代数在 OOS 任务分配里最需要注意的是v_max。在连续 PSO 中v_max过大只是让粒子飞行过快在 DPSO 中位置变化过大意味着下一轮排序产生的任务序列可能和上一轮完全无关粒子失去了对局部区域的精细搜索能力。实测中v_max超过 0.8 以后最优解曲线呈现类似随机采样的跳动而不是逐步收敛。4.2 惯性权重递减与速度上限的动态控制前面代码中已经用了线性递减的惯性权重这里单独拆出来说明它的作用。迭代早期 w 接近 0.9粒子速度继承度高运动范围大可以跨过局部极小点迭代后期 w 接近 0.4速度衰减快粒子主要在当前区域做精细搜索。对于时间窗密集的问题这个衰减速度往往要放慢因为窗口约束形成的可行区域很窄粒子需要更多迭代来调整到达时刻。这段代码用于单独计算当前代的 wdef adaptive_w(w_max, w_min, epoch, n_iter): return w_max - (w_max - w_min) * epoch / n_iter # 调用示例 w_now adaptive_w(0.9, 0.4, 150, 300)如果发现收敛曲线在中后期还出现明显的阶梯式下降说明粒子跳跃范围过大。可以额外加一个随迭代缩短的v_max控制比如从 0.8 线性降到 0.2让迭代后期的任务顺序只在相邻位置间微调。这个技巧对带窄时间窗的实例效果明显原因在于时间窗约束对任务前后顺序极其敏感小幅调整比大步重排更容易找到可行解。4.3 借助局部搜索抑制 DPSO 早熟并正确回写 gbest粒子群算法在离散问题上容易早熟常见补充手段是对全局最优解做局部搜索。方案是在当前 gbest 解码出的任务序列中随机选取任务尝试插入其它位置或迁移到其它服务机接受成本降低的候选解。关键在于局部搜索得到的是离散方案如果不转回连续位置向量下一轮迭代的 gbest 引导仍然使用旧的 gbest_x改进就丢失了。下面这段代码演示如何把局部搜索改良后的方案回写成新的位置向量def plan_to_position(plan, n_task): x_new np.zeros(n_task) seq [] for tasks in plan: seq.extend(tasks) for rank, t in enumerate(seq): x_new[t] rank 1.0 rank len(seq) 1 for t in range(n_task): if x_new[t] 0: x_new[t] rank rank 1 return x_new # 调用后替换全局最优 solver.gbest_x plan_to_position(better_plan, solver.n_task)逻辑说明位置向量的相对大小决定 SPV 序列所以只要把局部搜索得到的任务序列按优先顺序赋不同值再对未分配任务赋更大的末位值即可。这一招能让局部搜索的改进真正参与后续的粒子牵引过程。需要注意回写后应执行一次解码确认重置后的位置向量不会因为序号断层产生意外排序。实际工程中局部搜索每 10 代调用一次即可调用过密会让粒子群退化为爬山算法。5. 验证与工程落地中要盯住的三个细节5.1 怎么生成随机任务实例并做多次对比验证 DPSO 实现是否正确第一步是构造可控实例。可以用任务数 12、服务机 3、容量 5 这样的小规模参数随机生成对称成本矩阵运行多次观察统计量np.random.seed(7) C np.random.rand(13, 13) C (C C.T) / 2 np.fill_diagonal(C, 0) results [] for _ in range(20): solver DPSO(n_task12, n_svc3, cap5, CC, n_pop30, n_iter200) _, cost solver.run() results.append(cost) print(fbest{min(results):.4f}, mean{np.mean(results):.4f}, std{np.std(results):.4f})多次运行的标准差是判断稳定性的重要指标。标准差过大说明算法对初始粒子的分布敏感v_max或n_pop需要调大。同时可以用穷举或约束规划求解器验证小规模实例的最优值确认 DPSO 找到的解与下界之间的差距。5.2 DPSO 收敛曲线的判读与提前终止收敛曲线记录每代gbest_cost用于判断算法是否进入停滞。如果曲线在迭代后半段变成一条平坦直线而最终方案仍有未分配任务说明当前参数下粒子没有足够能力穿越不可行区域需要提高初始惯性权重或增加局部搜索频率。工程上可以按适应度变化幅度设置提前终止条件例如连续 30 代最优值变化小于 1e-4 就结束代码实现就是在run()的每轮末尾检查history[-30]与history[-1]的差值。提前终止节省的时间有限但对于需要在线重规划的动态场景省出的几十秒迭代时间可以留给约束修复和后处理。5.3 动态任务到达时的重规划技巧真实在轨服务过程中会有新任务临时插入比如某颗卫星突然失稳需要应急离轨。此时不应把种群清空重跑而是保留旧方案中未执行任务和对应服务机序列只对新任务建立新的优先级维度。具体做法是将旧 pbest 的任务序列解码出来剔除已完成任务再调用plan_to_position回写成位置向量作为新一代种群的个体之一参与迭代。这样重规划结果会尽可能继承原有任务序列减少不必要的燃料消耗和轨道相位调整。对离散粒子群算法做动态任务分配保持解的时间连续性和重新优化最优性同样重要这也是工程实现和纯算法验证最大的区别。本文还有配套的精品资源点击获取 离散粒子群算法求解在轨服务任务分配：编码设计与时间窗约束处理
简介这份 PDF 是一篇航天工程优化领域的学术论文核心面向研究航天器协同任务分配、群体智能算法应用的高校师生、科研人员及算法工程师。论文针对多颗服务航天器在轨服务任务分配的难点提出离散粒子群优化DPSO算法设计了新的粒子位置与速度更新公式并综合目标卫星价值、服务航天器损耗、距离消耗等关键指标建立数学模型。内容包含任务编码、数据结构组织方式以及大规模任务分配中的寻优与收敛性能分析既可作算法研究方向的专业指导也可为运筹调度、智能优化等离散场景提供参考。资源包内为 1 个 PDF 文件共 371KB轻量便于快速查阅已有 126 人学习下载。读者可从论文中获取完整的算法设计思路、模型构建过程与仿真验证结论便于直接复现实验对比或借鉴其离散编码策略拓展到其他组合优化问题兼具理论价值和实践参考意义。1. 在轨服务任务分配难在哪离散粒子群算法能解决什么在轨服务任务分配的关键在于“任务必须在指定时间窗内被某颗服务航天器完成”这类问题既有时间窗约束又有服务机容量和燃料上限本质上是一个带约束的组合优化。直接套用标准粒子群算法会遇到很实际的问题连续实数向量无法直接解释成“由哪颗卫星、以什么顺序执行哪些任务”。离散粒子群算法把粒子位置当作任务优先级通过排序和贪心映射生成离散方案在搜索能力和实现复杂度之间取得较好平衡很适合任务规模不大但约束密集的快速规划场景。下面按照模型建立、编码设计、迭代代码、参数调优到验证细节的顺序完整展开并给出每个关键参数对应的物理含义。如果你已经熟悉标准 PSO 和遗传算法那这篇的重点可以放在时间窗约束处理与离散解码回写这两处。2. OOS 任务分配模型与任务优先级编码设计2.1 在轨服务任务分配的目标函数与约束条件先把问题抽象成一组带时间窗的任务节点。设服务机集合 S {1, 2, …, m}任务集合 T {1, 2, …, n}每台服务机从基地出发依次访问分配给自己的任务节点最后返航。目标函数是所有服务机路线消耗的 ΔV 总和最小min ∑_{s1..m} ( ∑_{i ∈ seq_s} C[prev_i][i] C[last_s][0] )其中 C[i][j] 是从节点 i 转移到节点 j 的燃料代价索引 0 表示服务基地。如果各服务机的停泊轨道不同把基地索引从 0 换成对应服务机驻泊点即可公式结构不变。这个形式意味着任务的顺序变化会直接影响燃料消耗所以“谁做、按什么顺序做”必须同时被优化仅做分配不考虑顺序是拿不到可执行方案的。约束条件有四个层面每台服务机执行的任务数不能超过容量 cap_s每个任务最多只能分配一次服务机到达任务节点的实际时刻必须落在窗口 [E_t, L_t] 内整条路线的累计 ΔV 不能超过服务机的可用燃料上限。时间窗约束是 OOS 与一般车辆路径问题差异最大的地方多数实现会把前两个约束设计成硬条件把时间窗处理成惩罚项理由是窄窗口会让可行解区域严重碎片化硬约束搜索在迭代初期几乎找不到可行粒子。2.2 标准粒子群算法的连续更新机制为何不兼容组合优化标准 PSO 的更新公式只有两行v(t1) w * v(t) c1 * r1 * (pbest - x(t)) c2 * r2 * (gbest - x(t))x(t1) x(t) v(t1)位置 x 是连续实数向量如果没有额外的离散化机制这个向量在 OOS 任务分配问题里没有语义。因为解是由“任务到服务机的映射”和“任务执行顺序”组成的连续数值无法直接表达这两个离散结构。有人会把位置值四舍五入成 0-1 分配矩阵但这种做法在规模稍大时会出现两个典型问题一个是两个任务同时被映射到同一台服务机的同一时间片另一个是某台服务机任务数突破容量时间窗约束更是难以用连续小步长调整来恢复。从搜索角度解释标准 PSO 依靠 pbest 与 gbest 的差向量来驱动粒子移动这种“差分牵引”在连续空间中能自然平滑地逼近最优区域。但组合优化的可行域不是凸的差向量往往指向一个不可行方式所以需要改变编码让位置向量的每个维度对应“任务优先级”而不是“是否选中”。2.3 基于任务优先级的 DPSO 编码与三种离散化映射常见的离散化映射有三种适用场景不同下面用表格做一个直接对比编码方式粒子向量长度可行性修复代价适用场景四舍五入映射m × n高需要反复重扫修正重复与超载无顺序要求的纯静态分配排序映射n低排序即为全局任务序列有顺序要求、有容量上限的路径分配组合块编码n中需要按块长度重新划分位置段任务存在先后依赖或执行窗口OOS 任务分配中我更推荐排序映射也就是 SPV 规则粒子的第 t 个分量代表任务 t 的优先级每个迭代周期内把所有分量按值从小到大排序得到一个任务优先级序列再把这个序列按容量约束贪心分配给各台服务机。这样每个任务在编码层天然只出现一次不需要额外处理重复映射问题。SPV 解码的最小实现很短先看这段def spv_decode(x, n_svc, capacity): # x: 每个任务对应的位置值, 长度为任务数 order np.argsort(x) # 位置越小, 任务优先级越高 load np.zeros(n_svc, dtypeint) plan [[] for _ in range(n_svc)] for task in order: for s in range(n_svc): if load[s] capacity: plan[s].append(int(task)) load[s] 1 break return plan这段代码把连续位置向量通过排序转成任务序列再按“第一台能放下的服务机”依次填充。capacity 是单台服务机的最大可执行任务数。如果所有服务机都已装满任务会落在所有 plan 之外实际应用时把它记为未分配任务并加惩罚。这个实现可以跑通但有一个明显缺陷任务总是优先填满编号靠前的服务机容易造成载荷分布偏斜。更稳妥的做法是按边际插入成本选择服务机在后面的完整代码里会体现这一点。3. 求解 OOS 任务分配的 DPSO 主循环与 Python 实现3.1 速度更新、SPV 解析与可行性修复的三段式流程DPSO 求解 OOS 任务分配的迭代过程可以拆成三段第一段执行标准 PSO 的速度与位置更新得到新一代的连续位置向量第二段把位置向量通过 SPV 规则解析成所有服务机的任务序列第三段对任务序列做容量、时间窗和燃料约束的检查与修复。这里要注意三段式不是简单地串行执行。第二段解析出来的序列如果不满足硬约束要修正后再计算适应度如果修正后的方案仍未满足时间窗就需要把不可行程度折算成惩罚项加入适应度。很多初学者把约束处理放在适应度函数里但修复与惩罚应该同时存在先修复能修复的再用惩罚兜底不能直接修复的。3.2 可运行的 DPSO 主循环代码下面给出一个完整可运行的简化实现。为了便于读者直接跑通成本矩阵 C 用随机对称矩阵代替真实轨道转移代价实际项目中替换成由轨道根数计算的 ΔV 矩阵即可。import numpy as np class DPSO: def __init__(self, n_task, n_svc, cap, C, n_pop30, n_iter300, w_max0.9, w_min0.4, c11.8, c21.8, v_max0.5): self.n_task n_task self.n_svc n_svc self.cap cap self.C C # 代价矩阵, 0 号节点是基地 self.n_pop n_pop self.n_iter n_iter self.w_max w_max self.w_min w_min self.c1 c1 self.c2 c2 self.v_max v_max self.x np.random.rand(n_pop, n_task) # 位置: 任务优先级 self.v np.random.uniform(-v_max, v_max, (n_pop, n_task)) self.pbest_x self.x.copy() self.pbest_cost np.full(n_pop, 1e12) self.gbest_x self.x[0].copy() self.gbest_cost 1e12 self.history [] def decode(self, xj): order np.argsort(xj) plan [[] for _ in range(self.n_svc)] load np.zeros(self.n_svc, dtypeint) for task in order: best_s, best_inc -1, 1e9 for s in range(self.n_svc): if load[s] self.cap: continue # 按插入到队尾的边际成本选择服务机 inc self.C[0 if len(plan[s]) 0 else plan[s][-1], task] if inc best_inc: best_s, best_inc s, inc if best_s 0: plan[best_s].append(int(task)) load[best_s] 1 return plan def route_cost(self, plan): total 0.0 for tasks in plan: if len(tasks) 0: continue prev 0 for t in tasks: total self.C[prev, t] prev t total self.C[prev, 0] # 返回基地 assigned sum(len(t) for t in plan) missing self.n_task - assigned return total missing * 100.0 # 未分配任务惩罚 def run(self): for epoch in range(self.n_iter): w self.w_max - (self.w_max - self.w_min) * epoch / self.n_iter for i in range(self.n_pop): plan self.decode(self.x[i]) cost self.route_cost(plan) if cost self.pbest_cost[i]: self.pbest_cost[i] cost self.pbest_x[i] self.x[i].copy() if cost self.gbest_cost: self.gbest_cost cost self.gbest_x self.x[i].copy() r1 np.random.rand(self.n_pop, self.n_task) r2 np.random.rand(self.n_pop, self.n_task) self.v (w * self.v self.c1 * r1 * (self.pbest_x - self.x) self.c2 * r2 * (self.gbest_x - self.x)) self.v np.clip(self.v, -self.v_max, self.v_max) self.x np.clip(self.x self.v, 0, 10) self.history.append(self.gbest_cost) return self.gbest_x, self.gbest_cost代码逻辑说明decode中不再使用“第一台能放下的服务机”而是计算每个任务插入到某台服务机任务序列末尾的边际成本选择增量最小的服务机这样能避免载荷全堆在第一台的偏斜问题。route_cost对每条路线累加基地到第一个任务、任务到任务、最后一个任务返回基地的三段 ΔV未分配部分按 100 倍代价作为惩罚。run的惯性权重 w 随迭代线性下降epoch 越靠后越偏重局部精化这一步直接影响收敛曲线的形态。参数说明v_max是速度上限位置向量被 clip 到 0 到 10 之间保证优先级数值区间稳定c1和c2分别是向个体最优和全局最优牵引的加速度系数n_pop是粒子数量任务量在 10 到 30 之间时取 30 通常够用。注意位置向量的绝对值大小并不重要重要的是迭代过程中它的相对次序保持稳定所以x的取值范围不需要严格限制在 0 到 1。3.3 时间窗与燃料约束的惩罚处理时间窗约束无法在解码阶段一次性修复因为它取决于每个任务在路线中的到达时刻。常见做法是先按顺序累加转移时间和服务时间超过窗口上界再触发惩罚。下面这段函数可以直接并入上面的route_costdef time_window_penalty(self, tw_early, tw_late, service_time): penalty 0.0 for tasks in self.decode(self.gbest_x): now 0.0 prev 0 for t in tasks: now self.C[prev, t] prev t if now tw_late[t]: penalty now - tw_late[t] now max(now, tw_early[t]) service_time[t] return penalty逻辑说明每当到达时刻晚于tw_late[t]就把超出部分累计进惩罚项如果早于tw_early[t]则等待到窗口下界再开始服务。这样时间窗被表达成连续可导的软约束粒子在迭代中可以逐步修正到达时刻。燃料约束的处理方式类似把单条路线累计 ΔV 超过服务机燃料上限的部分按比例放大为惩罚值。约束类型触发条件修复策略处理优先级容量约束服务机任务数达到上限改选边际成本最小的下一台服务机高时间窗约束到达时刻晚于窗口上界交换任务顺序后再判断高燃料上限约束单机累计 ΔV 超限裁剪序列末尾任务并标记未分配中这张表的用途是给解码与惩罚模块定边界容量约束必须在解码阶段解决时间窗可以软惩罚燃料超限如果只是罚款会造成大量不可执行解参与比较需要在迭代后期提高罚系数。4. 离散粒子群算法参数基线与防早熟调优4.1 一组适合 OOS 场景的参数基线表DPSO 参数对结果的影响比在标准 PSO 中更敏感因为离散解码放大了位置微扰带来的排序变化。下面这组参数基线适合任务数 10 到 30、服务机 2 到 4 台的常见规模参数符号推荐范围对结果的影响种群规模n_pop20 - 50小于 20 时容易丢失多样解惯性权重w0.4 - 0.9 线性递减前期探索后期开发加速度系数c1 / c21.5 - 2.5偏大易早熟偏小收敛慢速度上限v_max0.2 - 0.8影响迭代中任务顺序的跳变幅度迭代次数n_iter100 - 500窄时间窗任务需要更大迭代数在 OOS 任务分配里最需要注意的是v_max。在连续 PSO 中v_max过大只是让粒子飞行过快在 DPSO 中位置变化过大意味着下一轮排序产生的任务序列可能和上一轮完全无关粒子失去了对局部区域的精细搜索能力。实测中v_max超过 0.8 以后最优解曲线呈现类似随机采样的跳动而不是逐步收敛。4.2 惯性权重递减与速度上限的动态控制前面代码中已经用了线性递减的惯性权重这里单独拆出来说明它的作用。迭代早期 w 接近 0.9粒子速度继承度高运动范围大可以跨过局部极小点迭代后期 w 接近 0.4速度衰减快粒子主要在当前区域做精细搜索。对于时间窗密集的问题这个衰减速度往往要放慢因为窗口约束形成的可行区域很窄粒子需要更多迭代来调整到达时刻。这段代码用于单独计算当前代的 wdef adaptive_w(w_max, w_min, epoch, n_iter): return w_max - (w_max - w_min) * epoch / n_iter # 调用示例 w_now adaptive_w(0.9, 0.4, 150, 300)如果发现收敛曲线在中后期还出现明显的阶梯式下降说明粒子跳跃范围过大。可以额外加一个随迭代缩短的v_max控制比如从 0.8 线性降到 0.2让迭代后期的任务顺序只在相邻位置间微调。这个技巧对带窄时间窗的实例效果明显原因在于时间窗约束对任务前后顺序极其敏感小幅调整比大步重排更容易找到可行解。4.3 借助局部搜索抑制 DPSO 早熟并正确回写 gbest粒子群算法在离散问题上容易早熟常见补充手段是对全局最优解做局部搜索。方案是在当前 gbest 解码出的任务序列中随机选取任务尝试插入其它位置或迁移到其它服务机接受成本降低的候选解。关键在于局部搜索得到的是离散方案如果不转回连续位置向量下一轮迭代的 gbest 引导仍然使用旧的 gbest_x改进就丢失了。下面这段代码演示如何把局部搜索改良后的方案回写成新的位置向量def plan_to_position(plan, n_task): x_new np.zeros(n_task) seq [] for tasks in plan: seq.extend(tasks) for rank, t in enumerate(seq): x_new[t] rank 1.0 rank len(seq) 1 for t in range(n_task): if x_new[t] 0: x_new[t] rank rank 1 return x_new # 调用后替换全局最优 solver.gbest_x plan_to_position(better_plan, solver.n_task)逻辑说明位置向量的相对大小决定 SPV 序列所以只要把局部搜索得到的任务序列按优先顺序赋不同值再对未分配任务赋更大的末位值即可。这一招能让局部搜索的改进真正参与后续的粒子牵引过程。需要注意回写后应执行一次解码确认重置后的位置向量不会因为序号断层产生意外排序。实际工程中局部搜索每 10 代调用一次即可调用过密会让粒子群退化为爬山算法。5. 验证与工程落地中要盯住的三个细节5.1 怎么生成随机任务实例并做多次对比验证 DPSO 实现是否正确第一步是构造可控实例。可以用任务数 12、服务机 3、容量 5 这样的小规模参数随机生成对称成本矩阵运行多次观察统计量np.random.seed(7) C np.random.rand(13, 13) C (C C.T) / 2 np.fill_diagonal(C, 0) results [] for _ in range(20): solver DPSO(n_task12, n_svc3, cap5, CC, n_pop30, n_iter200) _, cost solver.run() results.append(cost) print(fbest{min(results):.4f}, mean{np.mean(results):.4f}, std{np.std(results):.4f})多次运行的标准差是判断稳定性的重要指标。标准差过大说明算法对初始粒子的分布敏感v_max或n_pop需要调大。同时可以用穷举或约束规划求解器验证小规模实例的最优值确认 DPSO 找到的解与下界之间的差距。5.2 DPSO 收敛曲线的判读与提前终止收敛曲线记录每代gbest_cost用于判断算法是否进入停滞。如果曲线在迭代后半段变成一条平坦直线而最终方案仍有未分配任务说明当前参数下粒子没有足够能力穿越不可行区域需要提高初始惯性权重或增加局部搜索频率。工程上可以按适应度变化幅度设置提前终止条件例如连续 30 代最优值变化小于 1e-4 就结束代码实现就是在run()的每轮末尾检查history[-30]与history[-1]的差值。提前终止节省的时间有限但对于需要在线重规划的动态场景省出的几十秒迭代时间可以留给约束修复和后处理。5.3 动态任务到达时的重规划技巧真实在轨服务过程中会有新任务临时插入比如某颗卫星突然失稳需要应急离轨。此时不应把种群清空重跑而是保留旧方案中未执行任务和对应服务机序列只对新任务建立新的优先级维度。具体做法是将旧 pbest 的任务序列解码出来剔除已完成任务再调用plan_to_position回写成位置向量作为新一代种群的个体之一参与迭代。这样重规划结果会尽可能继承原有任务序列减少不必要的燃料消耗和轨道相位调整。对离散粒子群算法做动态任务分配保持解的时间连续性和重新优化最优性同样重要这也是工程实现和纯算法验证最大的区别。本文还有配套的精品资源点击获取