改进遗传算法求解多卫星时间窗任务规划问题（附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_{i=1}^{T} \sum_{s=1}^{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_c=0.8 ), ( p_m=0.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 ) 是每个任务分配的卫星编号。比如 ( T=6 ), 染色体前半段是[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 = i+1:n newSeq = [seq(1:i-1), seq(j:-1:i), seq(j+1: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, T+1: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(eliteCount+1: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 倍，但要注意全局变量的传递。

下面这个表格是我自己在实际调试中积累的典型问题速查，分享出来供参考。

另外想强调一点：遗传算法这类启发式，参数敏感度极高，不要指望一组参数通吃所有任务规模。我的实践是先用小规模算例做参数扫描（比如任务数 10 的小型实例），锁定较优参数区间，再迁移到大实例上微调。很多人一上来就跑大规模，出了问题也不知道是算法设计不对还是参数不对，浪费时间还打击信心。

关于实验验证，我还建议做一个算法对比雷达图：从解质量、运行时间、鲁棒性（多次运行的方差）、收敛速度四个维度对比改进GA、标准GA、模拟退火和CPLEX求解器（小规模时）。这种图在论文答辩和项目验收中说服力很强，因为你看的不是单一数据点，而是多维度表现。

在算例设计上也要留个心眼。如果你构造的任务时间窗全都宽裕得离谱，任何算法表现都差不多，改进的差距体现不出来。真正能体现算法功力的是紧约束场景——任务数多于可排空间、时间窗相互重叠严重、卫星资源只能覆盖 70% 左右的任务，这样的算例才逼得算法去精细化排布时间窗和权衡任务取舍。

6. 关于后续扩展的一些方向

这个项目做完后，如果你想继续延伸，有几个方向非常顺手。

第一是加入卫星侧摆调度。现实中卫星不是只在天顶看看目标，需要通过侧摆角调整成像范围，侧摆会带来转换时间，导致相邻任务之间有拆装时间约束。改进模型只需要在任务属性里加入侧摆角，在变化约束里加一个"转换时间"项，遗传算法的编码和解码框架整体不须大改。

第二是多目标化。实际任务规划往往不止"收益最大化"一个目标，还要均衡各颗卫星的负载、最小化总执行时间。这时候拿改进遗传算法做基础框架，接NSGA-II式的非支配排序，添加拥挤度距离，就能平滑过渡到多目标进化优化。

第三是动态扰动重规划。卫星运行中会发生突发情况，比如云层遮挡导致某个任务失败、卫星临时故障，这需要快速重新生成调度方案。可以在模型里加入"动态事件"接口，把改进GA做成增量式重规划——用旧解一部分作为初始种群的一部分，快速修复方案，而不是每次都从头算。这个方向工程价值很大。

我个人实际使用的体会是，这套改进遗传算法框架的迁移能力比想象中强。后来我把同一套代码更换了适应度函数和编码长度，就改成了"无人机侦察任务分配"和"地面传感器巡检路径规划"，效果都相当不错。核心在于编码结构（排列+分配双层设计）、自适应参数策略和局部搜索模块三者是一套通用骨架，换问题等于换皮肤，骨骼不用动。

最后再分享一个很实用的小技巧：在Matlab里，把rng的种子在每次实验前都记录下来。记录种子的价值在于，别人复现不了实验时，你可以快速定位到底是代码问题还是随机性问题；自己调参数时，固定种子能让每次改动效果看得非常清楚，而不是被随机噪声干扰判断。这个习惯帮我省了非常多的调试时间。

如果你正在做类似的调度优化课题，希望这套"问题建模→算法设计→代码实现→实验调试"的完整链路能给你一个可复现的起点。多卫星任务规划虽然复杂，但把它拆成编码、解码、算子、评估这几个模块后，会发现每一步都是可以独立验证和改进的。改完一个模块，跑一组对比，看曲线变化，这种正反馈会让你越调越有信心。