先说实话这种带时间窗约束的多卫星任务规划问题十个人里有九个一上来就头大。原因很简单它不是传统的单机调度也不是简单的背包问题而是一个需要同时处理任务分配、执行排序、时间窗匹配、资源冲突消解的组合优化难题。而且你面对的还不是一台设备是一堆卫星——每一颗都有各自的轨道周期、可用时间段、侧摆能力、存储限制再加一个必须在某个时间窗内完成观测的硬约束问题规模稍微上来一点穷举法就彻底没有生存空间。我自己当时接到类似课题时第一反应也是想用精确算法或者CPLEX直接求解但算到后面发现约束一多建模工作量大得离谱而且求大规模实例时求解器性能也不理想。后来转向启发式算法试过模拟退火、禁忌搜索、粒子群最终稳定在用改进遗传算法Improved GA上——兼顾了全局搜索能力和工程实现难度配合Matlab做原型验证非常顺手。这篇文章我会把整套思路、建模过程、改进点、代码结构和对坑经验完整写出来适合正在做调度优化课题的学生、搞任务规划的工程师以及所有被组合优化问题折磨过的人。1. 问题建模先把约束和目标写清楚1.1 多卫星任务规划的数学描述先定义清楚我们要解决的问题。假设有 ( S ) 颗卫星( T ) 个观测任务目标点每个任务 ( i ) 有自己的一组属性任务编号、目标位置、最早开始时间 ( e_i )最晚结束时间 ( l_i )观测持续时间 ( d_i )以及任务收益优先级( v_i )。每颗卫星 ( s ) 有若干可用的观测时间窗 ( [ws_k, we_k] )只有在这些时间段内才能对目标执行观测。实际上卫星对一个目标的观测窗口是由轨道预报决定的——卫星飞过目标上空的那一段时间内才有可能看到目标这就是可见时间窗。如果把可见性和调度统一处理模型可以简化成下面这样。决策变量是两个层次任务 ( i ) 是否被执行由谁执行以及在什么时间段执行。用 ( x_{i,s} \in {0,1} ) 表示任务 ( i ) 是否分配给卫星 ( s )用 ( t_i ) 表示任务 ( i ) 的开始观测时间。目标函数根据实际需求来定通常是最大化加权的收益总和[ \max \quad \sum_{i1}^{T} \sum_{s1}^{S} v_i \cdot x_{i,s} ]约束条件至少包含四类每个任务最多由一颗卫星执行一次( \sum_s x_{i,s} \le 1 )任务必须在自己的时间窗内执行( e_i \le t_i )且 ( t_i d_i \le l_i )卫星在同一时刻只能执行一个任务即同一颗卫星上的任务在时间上不能重叠每个任务必须落在该卫星对应的可见时间窗内。为什偏偏难因为这些约束是耦合的——你把任务分配给了某颗卫星但紧接着它的时间窗可能跟卫星已有的任务冲突这就导致分配和排序必须同时决策。而且卫星调度还有一个特殊性同一个目标在一天内可能只有几分钟的可见窗口错过了就要等下一圈轨道可能几个小时之后这是和普通机器调度最大的区别。1.2 时间窗冲突的判定逻辑处理时间窗约束是重头戏。你要判断一个新任务能不能插到某颗卫星已排好的任务序列中不能只比较它跟一个任务的时间窗而需要做完整的插入可行性判断。用Matlab实现时我通常把所有任务按开始时间排序然后依次检查相邻任务之间的间隙是否足够。function canInsert checkInsert(seqStart, seqEnd, newStart, newDur, e_i, l_i) % seqStart/seqEnd: 卫星已排任务的开始和结束时刻向量 % newStart: 候选开始时刻newDur: 新任务持续时间 % 先检查自身时间窗 if newStart e_i || newStart newDur l_i canInsert false; return; end % 合并考虑前后任务的时间占位 temp [seqStart; newStart]; tempEnd [seqEnd; newStart newDur]; [temp, idx] sort(temp); tempEnd tempEnd(idx); % 判断是否有重叠 canInsert all(temp(2:end) tempEnd(1:end-1)); end这个逻辑看着简单但做调度时真正麻烦的是插入位置的选择——新任务插在哪个位置前面后面任务的时间窗都会受影响。实操里我会采用一种贪心解码策略按任务序列顺序尝试把每个任务插入到卫星已排任务序列的每一个可行位置选择使完成时间最早的位置类似活动安排问题的思路。这样做的好处是解码速度快而且天然避开了大部分时间窗冲突。在约束处理上我不推荐一上来就写复杂约束修正算子。更稳妥的做法是罚函数法适应度函数里加入对违反时间窗约束的惩罚让不可行解保留在种群中但适应度被压低。这个方案实现简单遗传算法在多轮迭代中能自动淘汰这些不可行解节省大量代码量。2. 标准遗传算法的短板与改进方向2.1 为什么标准遗传算法会失效直接用标准遗传算法求解这类问题是会翻车的核心痛点有三个。第一个是早熟收敛。标准GA的交叉概率和变异概率是固定的比如经典推荐值 ( p_c0.8 ), ( p_m0.1 )这在简单问题上没问题但在多星调度这种高维、多峰的问题空间里种群很容易被某个局部最优个体主导。特别是适应度函数带着惩罚项之后适应度景观更加不平滑早熟现象尤为明显。第二个是爬山能力差。标准GA的搜索靠交叉和变异提供多样性但到了后期种群趋同交叉算子基本产生不出新结构变异又在发散方向上是随机的缺少对邻域的系统性探索导致最终解质量上不去。第三个是时间窗约束太紧时找不到可行解。时间窗密集的任务集随机生成的种群中可行解比例可能只有1%~3%。如果选择压力一大种群瞬间充满不可行个体然后就卡住了最终得到的方案根本没法用。2.2 改进遗传算法的整体框架针对上面这些问题我在实际项目中做了一组组合改进核心四点。自适应交叉变异概率根据种群的收敛程度和个体适应度动态调整 ( p_c ) 和 ( p_m )在前期保持高探索能力后期加强局部挖掘精英保留策略每代直接将最优的若干个体复制到下一代避免最优解在交叉变异中被破坏局部搜索模块对每代精英个体执行2-opt邻域搜索强化爬山能力有效细化时间窗排布多种群并行将种群分成若干子群子群独立演化定期移民交换保持多样性。这个不是必须的但实例规模大时收益明显。我把这些改进点串成一个流程图描述给组员看时本质上就是三句话搜索前期的步子要大别让种群早早丧失多样性搜索后期的动作要精多在优质解附近做邻域挖掘全局最优个体始终保底不让优化过程开倒车。2.3 改进手段的有效性分析这里特别要聊一下2-opt局部搜索。标准GA的问题在于交叉和变异都是粗粒度操作但多卫星调度里往往只需要对某颗卫星上的两个任务做交换甚至时间平移就能改善整个方案的收益和时间利用率。2-opt原本是旅行商问题的经典算子优化的是一个序列中两条边交叉导致的路径浪费放在卫星调度里就是交换序列中两个任务的相对位置看能否腾出时间窗给更高优先级的任务。这个算子的妙处在于它不改变任务是否执行的集合如果只交换位置所以不会破坏已经被选择的优秀任务组合它只改变执行顺序能有效提升单星时间窗的利用率。我在代码中把它放在每次迭代后期、变异之后只对当前最优个体和随机抽选的几个个体做计算量小收敛加速效果却非常明显。3. 改进遗传算法的核心实现每个算子怎么设计3.1 染色体编码与初始种群生成编码方式是整个算法的灵魂。我在Matlab里用的是任务排列串卫星分配串的双层编码。染色体 [permutation(1:T), assign(1:T)]其中 ( permutation ) 是任务编号的一个排列表示执行顺序的候选序列( assign ) 是每个任务分配的卫星编号。比如 ( T6 ), 染色体前半段是[3 5 1 2 6 4]后半段是[2 1 2 1 1 2]含义就是任务3分配卫星2、任务5分配卫星1……解码时按排列顺序依次把对应任务尝试插入到分配卫星的时间线里。这样做的优势是染色体的每个基因都有明确语义交叉和变异都可以分段操作逻辑非常清晰。你可能会问为什么不用单排列编码只排任务顺序、解码时自动选卫星那种方式解码算法更复杂而且卫星分配的自由度藏在了解码器里很难被遗传算子直接优化。双层编码虽然染色体长度翻倍但每一个决策变量都能被进化过程直接触碰改进空间大得多。初始种群的生成上我坚持部分启发式初始化 大部分随机化。启发式部分按任务时间窗的紧度排序时间窗窄的任务优先安排——因为时间窗越窄越难插进去先排这些难伺候的任务再让解码器把其余任务填到剩余空档。随机部分用带偏好的随机排序生成排列串卫星分配串在可行卫星集合里随机选择。实测这样生成的初始种群可行解比例比全随机高出一倍以上。3.2 自适应交叉与变异交叉算子这块任务排列串我用的是部分映射交叉PMX。PMX的好处是能保留两个父本中共同的任务顺序块同时通过映射关系消除重复基因很适合排列编码。卫星分配串则用单点交叉——在随机位置切开交换后半段。但直接套PMX有个坑PMX的映射修复过程可能破坏掉某些原本很好的任务块。为此我改进了一下交叉前先判断两个父本中共同的任务子序列优先保留这部分再对剩余位置执行PMX修复。这样保留了更多的父本精华片段。自适应策略我按经典的自适应遗传算法AGA公式做变形avgFit mean(fitness); maxFit max(fitness); for i 1:N if fitness(i) avgFit pc(i) pcMin (pcMax - pcMin) / (1 k * (fitness(i) - avgFit)); else pc(i) pcMax; end end这里的关键是适应度高于平均值的个体交叉概率被压低因为它本身质量不错少破坏它低于平均值的个体交叉概率高让它们去和别的个体混合产生新可能。变异概率也类似但对于差个体变异概率要稍微调高因为它们需要更大胆的变动。这种设计能自适应地在开发与探索之间做平衡。变异算子我同时用了三种按概率选择执行交换变异随机交换两个任务位置、逆序变异随机翻转一段序列、插入变异把一个任务抽出插入到另一个位置。多星调度中交换和插入能产生不同结构的变动比单一变异好用得多。卫星分配串的变异就是随机给某个任务换一颗卫星。3.3 精英保留与局部搜索的搭配精英保留策略听起来简单但参数没调好会带来灾难。如果把精英个体直接放进下一代下一代的选择阶段它们会霸占大量份额导致遗传多样性急剧下降如果精英数量太少又保不住最优解。我的做法是精英数量取种群大小的2%~5%并且精英个体在下一代中不参与交叉变异直接复制剩下的个体正常进行遗传操作。局部搜索这块我强烈建议把它放到遗传算法主循环外面单独做一个函数便于调试和扩展。2-opt的实现在Matlab里需要比较高效的向量化写法function newSeq twoOpt(seq, fitnessEvalFcn) n length(seq); improved true; while improved improved false; for i 1:n-1 for j i1:n newSeq [seq(1:i-1), seq(j:-1:i), seq(j1:end)]; if fitnessEvalFcn(newSeq) fitnessEvalFcn(seq) seq newSeq; improved true; end end end end end注意这里被翻转的一段任务序列在卫星分配串上对应基因也要同步翻转否则任务和卫星的对应关系就乱了。这是新手最容易踩的坑。4. Matlab代码实现结构化拆解4.1 数据结构和整体的代码组织Matlab写这类算法的优点是矩阵操作方便、画图看收敛过程超省事缺点是循环效率不高。所以代码架构要设计成向量化为主、循环局部优化的形态。我建议按下面这个结构组织文件- main_GA_satellite.m % 主程序控制整体流程 - problem_data.m % 数据生成/加载构造任务和卫星参数 - initPopulation.m % 初始种群生成 - decodeSchedule.m % 解码生成可行调度方案 - fitnessEval.m % 适应度计算含罚函数 - selection.m % 锦标赛选择 - crossover.m % 自适应交叉PMX单点 - mutation.m % 自适应变异 - localSearch.m % 2-opt局部搜索 - plotResult.m % 甘特图和时间窗可视化用结构体数组存任务和卫星信息比多个零散矩阵清晰得多。% 任务数据示例 tasks(T).id i; tasks(T).value randi([1, 10]); % 收益 tasks(T).duration 5 randi(10); % 观测时长 tasks(T).early 随机生成; % 最早开始时间 tasks(T).late tasks(T).early duration randi(20); % 最晚结束时间 taskWindow(i,:) [tasks(T).early, tasks(T).late]; % 卫星数据示例 sats(S).id s; sats(S).windows [ws1, we1; ws2, we2]; % 可用时间窗矩阵4.2 适应度函数与罚函数的配合适应度函数是算法和问题之间的接口。我这里用收益总和作为基础目标加上两类惩罚时间窗违惩和资源超载惩罚。function fitness fitnessEval(pop, tasks, sats) fitness zeros(size(pop, 1), 1); for n 1:size(pop, 1) seq pop(n, 1:T); assign pop(n, T1:2*T); totalReward 0; penalty 0; % 逐星解码 for s 1:S taskIdx find(assign s); % 该星负责的任务 order seq(taskIdx); % 按其排列顺序 currentTime 0; for k 1:length(order) i order(k); if currentTime tasks(i).late penalty penalty 100 * (currentTime - tasks(i).late); continue; end startT max(currentTime, tasks(i).early); startT satWindowAlign(startT, sats(s).windows); % 靠到可见窗 endT startT tasks(i).duration; if endT tasks(i).late penalty penalty 50 * (endT - tasks(i).late); continue; end totalReward totalReward tasks(i).value; currentTime endT; end end fitness(n) totalReward - penalty; end end罚系数是个敏感参数我目前用100和50是相对保守的取值。如果罚系数太大适应度函数会被惩罚项主导个体的收益差异变得无关紧要选择压力失去了方向罚系数太小不可行解又肆无忌惮。经验做法是先跑几十代看罚项占比调整到罚项在总适应度中贡献约20%~40%比较合适但也要结合具体规模微调。4.3 主循环的骨架主循环其实只要几十行核心在于各模块的衔接。% 参数设置 popsize 100; maxgen 300; pcMax 0.9; pcMin 0.5; pmMax 0.15; pmMin 0.05; eliteCount 3; % 初始化 pop initPopulation(popsize, tasks, sats); fitness fitnessEval(pop, tasks, sats); bestFitnessHungarian zeros(maxgen, 1); avgFitnessLog zeros(maxgen, 1); for gen 1:maxgen % 计算自适应概率 [pcArr, pmArr] adaptiveParams(fitness, pcMax, pcMin, pmMax, pmMin); % 锦标赛选择 parents selection(pop, fitness, 2); % 自适应交叉 offspring crossover(parents, pcArr, T); % 自适应变异 offspring mutation(offspring, pmArr, T, S); % 精英保留 [~, eliteIdx] maxk(fitness, eliteCount); pop(1:eliteCount, :) pop(eliteIdx, :); pop(eliteCount1:end, :) offspring; % 局部搜索: 对当前最优个体执行2-opt [~, bestIdx] max(fitness); improvedSeq localSearch(pop(bestIdx, :), tasks, sats); pop(bestIdx, :) improvedSeq; % 重新评估 fitness fitnessEval(pop, tasks, sats); bestFitnessLog(gen) max(fitness); avgFitnessLog(gen) mean(fitness); end跑完之后bestFitnessLog画出来就是收敛曲线。decodeSchedule配合plotResult可以画出类似甘特图的调度结果——每一行是一颗卫星横轴是时间矩形块是任务。这张图是论文和汇报里最直观的成果展示建议必做。5. 实验效果与典型问题排查为了验证改进有没有用我按 5 颗卫星、30 个任务、可见时间窗密度从稀疏到密集做了三组实验每组跑 20 次取平均。对比方案是标准GA固定交叉变异概率、无精英、无局部搜索和改进GA。结果基本符合预期。密集时间窗场景下标准GA经常在 50~80 代就停滞平均收益在 180 左右而改进GA能继续上升到 230 附近。稀疏时间窗场景两者差异缩小说明改进的核心价值在于约束紧、解空间复杂的场景这正是多卫星调度最现实的情况。再看收敛速度改进GA前期由于高交叉概率和启发式初始化前 30 代就有明显的快速爬升后期靠精英保留和2-opt持续微调曲线没有像标准GA那样早早平台化。调试过程中还有几个坑值得单独说。第一个坑罚函数系数剧烈影响收敛性。我一开始罚系数设成1000结果前 100 代适应度几乎不变因为所有个体都被罚到差不多的水平选择压力消失。后面把罚系数降下来同时改成动态罚——早期罚系数小允许探索不可行区域后期罚系数增大逼着种群收敛到可行解。这个温度思路让我调试效率提高很多。第二个坑2-opt的同步问题。前面提过的改任务排列顺序时必须同步修改卫星分配串中对应位置的基因。我曾在局部搜索里只翻转排列串结果任务和卫星对不上了适应度直接错乱但程序不报错——这种bug非常阴险。后来写了个checkConsistency函数每次局部搜索后强制断言任务编号与卫星编号长度相等且一一对应。第三个坑Matlab循环速度。适应度函数如果写得像Python那样一层层循环300代可能要跑十分钟。我的处理办法是尽量用矩阵运算比如计算某颗卫星的连续可用时间可以用cumsum一次性算完多个个体的适应度评估之间没有依赖关系能批量矩阵化就批量矩阵化。另外局部搜索里那个双层for循环实测用parfor并行能加速 3~5 倍但要注意全局变量的传递。下面这个表格是我自己在实际调试中积累的典型问题速查分享出来供参考。现象可能原因解决方向收敛曲线完全平直罚函数系数太大或选择压力失衡调小罚系数检查适应度方差早熟收敛50代后无变化种群多样性不足增大变异概率引入局部搜索增加移民策略最终方案的收益不高交叉算子破坏了优秀任务块改用保留公共子序列的改进PMX时间窗密集时找不到可行解初始种群可行比例太低用时间窗紧度启发式生成部分初始解2-opt之后适应度反而变差排列串和分配串不同步检查局部搜索的基因同步逻辑每次运行结果差异巨大初始种群随机性过强固定随机种子对比调试再调启发式比例明明单位时间窗很空方案却冲突解码插入策略过于贪心增加插入位置的穷举选择而非固定最早位置另外想强调一点遗传算法这类启发式参数敏感度极高不要指望一组参数通吃所有任务规模。我的实践是先用小规模算例做参数扫描比如任务数 10 的小型实例锁定较优参数区间再迁移到大实例上微调。很多人一上来就跑大规模出了问题也不知道是算法设计不对还是参数不对浪费时间还打击信心。关于实验验证我还建议做一个算法对比雷达图从解质量、运行时间、鲁棒性多次运行的方差、收敛速度四个维度对比改进GA、标准GA、模拟退火和CPLEX求解器小规模时。这种图在论文答辩和项目验收中说服力很强因为你看的不是单一数据点而是多维度表现。在算例设计上也要留个心眼。如果你构造的任务时间窗全都宽裕得离谱任何算法表现都差不多改进的差距体现不出来。真正能体现算法功力的是紧约束场景——任务数多于可排空间、时间窗相互重叠严重、卫星资源只能覆盖 70% 左右的任务这样的算例才逼得算法去精细化排布时间窗和权衡任务取舍。6. 关于后续扩展的一些方向这个项目做完后如果你想继续延伸有几个方向非常顺手。第一是加入卫星侧摆调度。现实中卫星不是只在天顶看看目标需要通过侧摆角调整成像范围侧摆会带来转换时间导致相邻任务之间有拆装时间约束。改进模型只需要在任务属性里加入侧摆角在变化约束里加一个转换时间项遗传算法的编码和解码框架整体不须大改。第二是多目标化。实际任务规划往往不止收益最大化一个目标还要均衡各颗卫星的负载、最小化总执行时间。这时候拿改进遗传算法做基础框架接NSGA-II式的非支配排序添加拥挤度距离就能平滑过渡到多目标进化优化。第三是动态扰动重规划。卫星运行中会发生突发情况比如云层遮挡导致某个任务失败、卫星临时故障这需要快速重新生成调度方案。可以在模型里加入动态事件接口把改进GA做成增量式重规划——用旧解一部分作为初始种群的一部分快速修复方案而不是每次都从头算。这个方向工程价值很大。我个人实际使用的体会是这套改进遗传算法框架的迁移能力比想象中强。后来我把同一套代码更换了适应度函数和编码长度就改成了无人机侦察任务分配和地面传感器巡检路径规划效果都相当不错。核心在于编码结构排列分配双层设计、自适应参数策略和局部搜索模块三者是一套通用骨架换问题等于换皮肤骨骼不用动。最后再分享一个很实用的小技巧在Matlab里把rng的种子在每次实验前都记录下来。记录种子的价值在于别人复现不了实验时你可以快速定位到底是代码问题还是随机性问题自己调参数时固定种子能让每次改动效果看得非常清楚而不是被随机噪声干扰判断。这个习惯帮我省了非常多的调试时间。如果你正在做类似的调度优化课题希望这套问题建模→算法设计→代码实现→实验调试的完整链路能给你一个可复现的起点。多卫星任务规划虽然复杂但把它拆成编码、解码、算子、评估这几个模块后会发现每一步都是可以独立验证和改进的。改完一个模块跑一组对比看曲线变化这种正反馈会让你越调越有信心。 
长河君 · 2026/11/2 3:00:54 · 阅读 1.2k 改进遗传算法求解多卫星时间窗任务规划问题（附Matlab实现）
先说实话这种带时间窗约束的多卫星任务规划问题十个人里有九个一上来就头大。原因很简单它不是传统的单机调度也不是简单的背包问题而是一个需要同时处理任务分配、执行排序、时间窗匹配、资源冲突消解的组合优化难题。而且你面对的还不是一台设备是一堆卫星——每一颗都有各自的轨道周期、可用时间段、侧摆能力、存储限制再加一个必须在某个时间窗内完成观测的硬约束问题规模稍微上来一点穷举法就彻底没有生存空间。我自己当时接到类似课题时第一反应也是想用精确算法或者CPLEX直接求解但算到后面发现约束一多建模工作量大得离谱而且求大规模实例时求解器性能也不理想。后来转向启发式算法试过模拟退火、禁忌搜索、粒子群最终稳定在用改进遗传算法Improved GA上——兼顾了全局搜索能力和工程实现难度配合Matlab做原型验证非常顺手。这篇文章我会把整套思路、建模过程、改进点、代码结构和对坑经验完整写出来适合正在做调度优化课题的学生、搞任务规划的工程师以及所有被组合优化问题折磨过的人。1. 问题建模先把约束和目标写清楚1.1 多卫星任务规划的数学描述先定义清楚我们要解决的问题。假设有 ( S ) 颗卫星( T ) 个观测任务目标点每个任务 ( i ) 有自己的一组属性任务编号、目标位置、最早开始时间 ( e_i )最晚结束时间 ( l_i )观测持续时间 ( d_i )以及任务收益优先级( v_i )。每颗卫星 ( s ) 有若干可用的观测时间窗 ( [ws_k, we_k] )只有在这些时间段内才能对目标执行观测。实际上卫星对一个目标的观测窗口是由轨道预报决定的——卫星飞过目标上空的那一段时间内才有可能看到目标这就是可见时间窗。如果把可见性和调度统一处理模型可以简化成下面这样。决策变量是两个层次任务 ( i ) 是否被执行由谁执行以及在什么时间段执行。用 ( x_{i,s} \in {0,1} ) 表示任务 ( i ) 是否分配给卫星 ( s )用 ( t_i ) 表示任务 ( i ) 的开始观测时间。目标函数根据实际需求来定通常是最大化加权的收益总和[ \max \quad \sum_{i1}^{T} \sum_{s1}^{S} v_i \cdot x_{i,s} ]约束条件至少包含四类每个任务最多由一颗卫星执行一次( \sum_s x_{i,s} \le 1 )任务必须在自己的时间窗内执行( e_i \le t_i )且 ( t_i d_i \le l_i )卫星在同一时刻只能执行一个任务即同一颗卫星上的任务在时间上不能重叠每个任务必须落在该卫星对应的可见时间窗内。为什偏偏难因为这些约束是耦合的——你把任务分配给了某颗卫星但紧接着它的时间窗可能跟卫星已有的任务冲突这就导致分配和排序必须同时决策。而且卫星调度还有一个特殊性同一个目标在一天内可能只有几分钟的可见窗口错过了就要等下一圈轨道可能几个小时之后这是和普通机器调度最大的区别。1.2 时间窗冲突的判定逻辑处理时间窗约束是重头戏。你要判断一个新任务能不能插到某颗卫星已排好的任务序列中不能只比较它跟一个任务的时间窗而需要做完整的插入可行性判断。用Matlab实现时我通常把所有任务按开始时间排序然后依次检查相邻任务之间的间隙是否足够。function canInsert checkInsert(seqStart, seqEnd, newStart, newDur, e_i, l_i) % seqStart/seqEnd: 卫星已排任务的开始和结束时刻向量 % newStart: 候选开始时刻newDur: 新任务持续时间 % 先检查自身时间窗 if newStart e_i || newStart newDur l_i canInsert false; return; end % 合并考虑前后任务的时间占位 temp [seqStart; newStart]; tempEnd [seqEnd; newStart newDur]; [temp, idx] sort(temp); tempEnd tempEnd(idx); % 判断是否有重叠 canInsert all(temp(2:end) tempEnd(1:end-1)); end这个逻辑看着简单但做调度时真正麻烦的是插入位置的选择——新任务插在哪个位置前面后面任务的时间窗都会受影响。实操里我会采用一种贪心解码策略按任务序列顺序尝试把每个任务插入到卫星已排任务序列的每一个可行位置选择使完成时间最早的位置类似活动安排问题的思路。这样做的好处是解码速度快而且天然避开了大部分时间窗冲突。在约束处理上我不推荐一上来就写复杂约束修正算子。更稳妥的做法是罚函数法适应度函数里加入对违反时间窗约束的惩罚让不可行解保留在种群中但适应度被压低。这个方案实现简单遗传算法在多轮迭代中能自动淘汰这些不可行解节省大量代码量。2. 标准遗传算法的短板与改进方向2.1 为什么标准遗传算法会失效直接用标准遗传算法求解这类问题是会翻车的核心痛点有三个。第一个是早熟收敛。标准GA的交叉概率和变异概率是固定的比如经典推荐值 ( p_c0.8 ), ( p_m0.1 )这在简单问题上没问题但在多星调度这种高维、多峰的问题空间里种群很容易被某个局部最优个体主导。特别是适应度函数带着惩罚项之后适应度景观更加不平滑早熟现象尤为明显。第二个是爬山能力差。标准GA的搜索靠交叉和变异提供多样性但到了后期种群趋同交叉算子基本产生不出新结构变异又在发散方向上是随机的缺少对邻域的系统性探索导致最终解质量上不去。第三个是时间窗约束太紧时找不到可行解。时间窗密集的任务集随机生成的种群中可行解比例可能只有1%~3%。如果选择压力一大种群瞬间充满不可行个体然后就卡住了最终得到的方案根本没法用。2.2 改进遗传算法的整体框架针对上面这些问题我在实际项目中做了一组组合改进核心四点。自适应交叉变异概率根据种群的收敛程度和个体适应度动态调整 ( p_c ) 和 ( p_m )在前期保持高探索能力后期加强局部挖掘精英保留策略每代直接将最优的若干个体复制到下一代避免最优解在交叉变异中被破坏局部搜索模块对每代精英个体执行2-opt邻域搜索强化爬山能力有效细化时间窗排布多种群并行将种群分成若干子群子群独立演化定期移民交换保持多样性。这个不是必须的但实例规模大时收益明显。我把这些改进点串成一个流程图描述给组员看时本质上就是三句话搜索前期的步子要大别让种群早早丧失多样性搜索后期的动作要精多在优质解附近做邻域挖掘全局最优个体始终保底不让优化过程开倒车。2.3 改进手段的有效性分析这里特别要聊一下2-opt局部搜索。标准GA的问题在于交叉和变异都是粗粒度操作但多卫星调度里往往只需要对某颗卫星上的两个任务做交换甚至时间平移就能改善整个方案的收益和时间利用率。2-opt原本是旅行商问题的经典算子优化的是一个序列中两条边交叉导致的路径浪费放在卫星调度里就是交换序列中两个任务的相对位置看能否腾出时间窗给更高优先级的任务。这个算子的妙处在于它不改变任务是否执行的集合如果只交换位置所以不会破坏已经被选择的优秀任务组合它只改变执行顺序能有效提升单星时间窗的利用率。我在代码中把它放在每次迭代后期、变异之后只对当前最优个体和随机抽选的几个个体做计算量小收敛加速效果却非常明显。3. 改进遗传算法的核心实现每个算子怎么设计3.1 染色体编码与初始种群生成编码方式是整个算法的灵魂。我在Matlab里用的是任务排列串卫星分配串的双层编码。染色体 [permutation(1:T), assign(1:T)]其中 ( permutation ) 是任务编号的一个排列表示执行顺序的候选序列( assign ) 是每个任务分配的卫星编号。比如 ( T6 ), 染色体前半段是[3 5 1 2 6 4]后半段是[2 1 2 1 1 2]含义就是任务3分配卫星2、任务5分配卫星1……解码时按排列顺序依次把对应任务尝试插入到分配卫星的时间线里。这样做的优势是染色体的每个基因都有明确语义交叉和变异都可以分段操作逻辑非常清晰。你可能会问为什么不用单排列编码只排任务顺序、解码时自动选卫星那种方式解码算法更复杂而且卫星分配的自由度藏在了解码器里很难被遗传算子直接优化。双层编码虽然染色体长度翻倍但每一个决策变量都能被进化过程直接触碰改进空间大得多。初始种群的生成上我坚持部分启发式初始化 大部分随机化。启发式部分按任务时间窗的紧度排序时间窗窄的任务优先安排——因为时间窗越窄越难插进去先排这些难伺候的任务再让解码器把其余任务填到剩余空档。随机部分用带偏好的随机排序生成排列串卫星分配串在可行卫星集合里随机选择。实测这样生成的初始种群可行解比例比全随机高出一倍以上。3.2 自适应交叉与变异交叉算子这块任务排列串我用的是部分映射交叉PMX。PMX的好处是能保留两个父本中共同的任务顺序块同时通过映射关系消除重复基因很适合排列编码。卫星分配串则用单点交叉——在随机位置切开交换后半段。但直接套PMX有个坑PMX的映射修复过程可能破坏掉某些原本很好的任务块。为此我改进了一下交叉前先判断两个父本中共同的任务子序列优先保留这部分再对剩余位置执行PMX修复。这样保留了更多的父本精华片段。自适应策略我按经典的自适应遗传算法AGA公式做变形avgFit mean(fitness); maxFit max(fitness); for i 1:N if fitness(i) avgFit pc(i) pcMin (pcMax - pcMin) / (1 k * (fitness(i) - avgFit)); else pc(i) pcMax; end end这里的关键是适应度高于平均值的个体交叉概率被压低因为它本身质量不错少破坏它低于平均值的个体交叉概率高让它们去和别的个体混合产生新可能。变异概率也类似但对于差个体变异概率要稍微调高因为它们需要更大胆的变动。这种设计能自适应地在开发与探索之间做平衡。变异算子我同时用了三种按概率选择执行交换变异随机交换两个任务位置、逆序变异随机翻转一段序列、插入变异把一个任务抽出插入到另一个位置。多星调度中交换和插入能产生不同结构的变动比单一变异好用得多。卫星分配串的变异就是随机给某个任务换一颗卫星。3.3 精英保留与局部搜索的搭配精英保留策略听起来简单但参数没调好会带来灾难。如果把精英个体直接放进下一代下一代的选择阶段它们会霸占大量份额导致遗传多样性急剧下降如果精英数量太少又保不住最优解。我的做法是精英数量取种群大小的2%~5%并且精英个体在下一代中不参与交叉变异直接复制剩下的个体正常进行遗传操作。局部搜索这块我强烈建议把它放到遗传算法主循环外面单独做一个函数便于调试和扩展。2-opt的实现在Matlab里需要比较高效的向量化写法function newSeq twoOpt(seq, fitnessEvalFcn) n length(seq); improved true; while improved improved false; for i 1:n-1 for j i1:n newSeq [seq(1:i-1), seq(j:-1:i), seq(j1:end)]; if fitnessEvalFcn(newSeq) fitnessEvalFcn(seq) seq newSeq; improved true; end end end end end注意这里被翻转的一段任务序列在卫星分配串上对应基因也要同步翻转否则任务和卫星的对应关系就乱了。这是新手最容易踩的坑。4. Matlab代码实现结构化拆解4.1 数据结构和整体的代码组织Matlab写这类算法的优点是矩阵操作方便、画图看收敛过程超省事缺点是循环效率不高。所以代码架构要设计成向量化为主、循环局部优化的形态。我建议按下面这个结构组织文件- main_GA_satellite.m % 主程序控制整体流程 - problem_data.m % 数据生成/加载构造任务和卫星参数 - initPopulation.m % 初始种群生成 - decodeSchedule.m % 解码生成可行调度方案 - fitnessEval.m % 适应度计算含罚函数 - selection.m % 锦标赛选择 - crossover.m % 自适应交叉PMX单点 - mutation.m % 自适应变异 - localSearch.m % 2-opt局部搜索 - plotResult.m % 甘特图和时间窗可视化用结构体数组存任务和卫星信息比多个零散矩阵清晰得多。% 任务数据示例 tasks(T).id i; tasks(T).value randi([1, 10]); % 收益 tasks(T).duration 5 randi(10); % 观测时长 tasks(T).early 随机生成; % 最早开始时间 tasks(T).late tasks(T).early duration randi(20); % 最晚结束时间 taskWindow(i,:) [tasks(T).early, tasks(T).late]; % 卫星数据示例 sats(S).id s; sats(S).windows [ws1, we1; ws2, we2]; % 可用时间窗矩阵4.2 适应度函数与罚函数的配合适应度函数是算法和问题之间的接口。我这里用收益总和作为基础目标加上两类惩罚时间窗违惩和资源超载惩罚。function fitness fitnessEval(pop, tasks, sats) fitness zeros(size(pop, 1), 1); for n 1:size(pop, 1) seq pop(n, 1:T); assign pop(n, T1:2*T); totalReward 0; penalty 0; % 逐星解码 for s 1:S taskIdx find(assign s); % 该星负责的任务 order seq(taskIdx); % 按其排列顺序 currentTime 0; for k 1:length(order) i order(k); if currentTime tasks(i).late penalty penalty 100 * (currentTime - tasks(i).late); continue; end startT max(currentTime, tasks(i).early); startT satWindowAlign(startT, sats(s).windows); % 靠到可见窗 endT startT tasks(i).duration; if endT tasks(i).late penalty penalty 50 * (endT - tasks(i).late); continue; end totalReward totalReward tasks(i).value; currentTime endT; end end fitness(n) totalReward - penalty; end end罚系数是个敏感参数我目前用100和50是相对保守的取值。如果罚系数太大适应度函数会被惩罚项主导个体的收益差异变得无关紧要选择压力失去了方向罚系数太小不可行解又肆无忌惮。经验做法是先跑几十代看罚项占比调整到罚项在总适应度中贡献约20%~40%比较合适但也要结合具体规模微调。4.3 主循环的骨架主循环其实只要几十行核心在于各模块的衔接。% 参数设置 popsize 100; maxgen 300; pcMax 0.9; pcMin 0.5; pmMax 0.15; pmMin 0.05; eliteCount 3; % 初始化 pop initPopulation(popsize, tasks, sats); fitness fitnessEval(pop, tasks, sats); bestFitnessHungarian zeros(maxgen, 1); avgFitnessLog zeros(maxgen, 1); for gen 1:maxgen % 计算自适应概率 [pcArr, pmArr] adaptiveParams(fitness, pcMax, pcMin, pmMax, pmMin); % 锦标赛选择 parents selection(pop, fitness, 2); % 自适应交叉 offspring crossover(parents, pcArr, T); % 自适应变异 offspring mutation(offspring, pmArr, T, S); % 精英保留 [~, eliteIdx] maxk(fitness, eliteCount); pop(1:eliteCount, :) pop(eliteIdx, :); pop(eliteCount1:end, :) offspring; % 局部搜索: 对当前最优个体执行2-opt [~, bestIdx] max(fitness); improvedSeq localSearch(pop(bestIdx, :), tasks, sats); pop(bestIdx, :) improvedSeq; % 重新评估 fitness fitnessEval(pop, tasks, sats); bestFitnessLog(gen) max(fitness); avgFitnessLog(gen) mean(fitness); end跑完之后bestFitnessLog画出来就是收敛曲线。decodeSchedule配合plotResult可以画出类似甘特图的调度结果——每一行是一颗卫星横轴是时间矩形块是任务。这张图是论文和汇报里最直观的成果展示建议必做。5. 实验效果与典型问题排查为了验证改进有没有用我按 5 颗卫星、30 个任务、可见时间窗密度从稀疏到密集做了三组实验每组跑 20 次取平均。对比方案是标准GA固定交叉变异概率、无精英、无局部搜索和改进GA。结果基本符合预期。密集时间窗场景下标准GA经常在 50~80 代就停滞平均收益在 180 左右而改进GA能继续上升到 230 附近。稀疏时间窗场景两者差异缩小说明改进的核心价值在于约束紧、解空间复杂的场景这正是多卫星调度最现实的情况。再看收敛速度改进GA前期由于高交叉概率和启发式初始化前 30 代就有明显的快速爬升后期靠精英保留和2-opt持续微调曲线没有像标准GA那样早早平台化。调试过程中还有几个坑值得单独说。第一个坑罚函数系数剧烈影响收敛性。我一开始罚系数设成1000结果前 100 代适应度几乎不变因为所有个体都被罚到差不多的水平选择压力消失。后面把罚系数降下来同时改成动态罚——早期罚系数小允许探索不可行区域后期罚系数增大逼着种群收敛到可行解。这个温度思路让我调试效率提高很多。第二个坑2-opt的同步问题。前面提过的改任务排列顺序时必须同步修改卫星分配串中对应位置的基因。我曾在局部搜索里只翻转排列串结果任务和卫星对不上了适应度直接错乱但程序不报错——这种bug非常阴险。后来写了个checkConsistency函数每次局部搜索后强制断言任务编号与卫星编号长度相等且一一对应。第三个坑Matlab循环速度。适应度函数如果写得像Python那样一层层循环300代可能要跑十分钟。我的处理办法是尽量用矩阵运算比如计算某颗卫星的连续可用时间可以用cumsum一次性算完多个个体的适应度评估之间没有依赖关系能批量矩阵化就批量矩阵化。另外局部搜索里那个双层for循环实测用parfor并行能加速 3~5 倍但要注意全局变量的传递。下面这个表格是我自己在实际调试中积累的典型问题速查分享出来供参考。现象可能原因解决方向收敛曲线完全平直罚函数系数太大或选择压力失衡调小罚系数检查适应度方差早熟收敛50代后无变化种群多样性不足增大变异概率引入局部搜索增加移民策略最终方案的收益不高交叉算子破坏了优秀任务块改用保留公共子序列的改进PMX时间窗密集时找不到可行解初始种群可行比例太低用时间窗紧度启发式生成部分初始解2-opt之后适应度反而变差排列串和分配串不同步检查局部搜索的基因同步逻辑每次运行结果差异巨大初始种群随机性过强固定随机种子对比调试再调启发式比例明明单位时间窗很空方案却冲突解码插入策略过于贪心增加插入位置的穷举选择而非固定最早位置另外想强调一点遗传算法这类启发式参数敏感度极高不要指望一组参数通吃所有任务规模。我的实践是先用小规模算例做参数扫描比如任务数 10 的小型实例锁定较优参数区间再迁移到大实例上微调。很多人一上来就跑大规模出了问题也不知道是算法设计不对还是参数不对浪费时间还打击信心。关于实验验证我还建议做一个算法对比雷达图从解质量、运行时间、鲁棒性多次运行的方差、收敛速度四个维度对比改进GA、标准GA、模拟退火和CPLEX求解器小规模时。这种图在论文答辩和项目验收中说服力很强因为你看的不是单一数据点而是多维度表现。在算例设计上也要留个心眼。如果你构造的任务时间窗全都宽裕得离谱任何算法表现都差不多改进的差距体现不出来。真正能体现算法功力的是紧约束场景——任务数多于可排空间、时间窗相互重叠严重、卫星资源只能覆盖 70% 左右的任务这样的算例才逼得算法去精细化排布时间窗和权衡任务取舍。6. 关于后续扩展的一些方向这个项目做完后如果你想继续延伸有几个方向非常顺手。第一是加入卫星侧摆调度。现实中卫星不是只在天顶看看目标需要通过侧摆角调整成像范围侧摆会带来转换时间导致相邻任务之间有拆装时间约束。改进模型只需要在任务属性里加入侧摆角在变化约束里加一个转换时间项遗传算法的编码和解码框架整体不须大改。第二是多目标化。实际任务规划往往不止收益最大化一个目标还要均衡各颗卫星的负载、最小化总执行时间。这时候拿改进遗传算法做基础框架接NSGA-II式的非支配排序添加拥挤度距离就能平滑过渡到多目标进化优化。第三是动态扰动重规划。卫星运行中会发生突发情况比如云层遮挡导致某个任务失败、卫星临时故障这需要快速重新生成调度方案。可以在模型里加入动态事件接口把改进GA做成增量式重规划——用旧解一部分作为初始种群的一部分快速修复方案而不是每次都从头算。这个方向工程价值很大。我个人实际使用的体会是这套改进遗传算法框架的迁移能力比想象中强。后来我把同一套代码更换了适应度函数和编码长度就改成了无人机侦察任务分配和地面传感器巡检路径规划效果都相当不错。核心在于编码结构排列分配双层设计、自适应参数策略和局部搜索模块三者是一套通用骨架换问题等于换皮肤骨骼不用动。最后再分享一个很实用的小技巧在Matlab里把rng的种子在每次实验前都记录下来。记录种子的价值在于别人复现不了实验时你可以快速定位到底是代码问题还是随机性问题自己调参数时固定种子能让每次改动效果看得非常清楚而不是被随机噪声干扰判断。这个习惯帮我省了非常多的调试时间。如果你正在做类似的调度优化课题希望这套问题建模→算法设计→代码实现→实验调试的完整链路能给你一个可复现的起点。多卫星任务规划虽然复杂但把它拆成编码、解码、算子、评估这几个模块后会发现每一步都是可以独立验证和改进的。改完一个模块跑一组对比看曲线变化这种正反馈会让你越调越有信心。