Surrogate-Assisted Genetic Programming with Rank-Based Phenotypic Characterisation for Dynamic Multi-Mode Project Scheduling

本文针对动态多模式资源约束项目调度问题，提出了一种基于排序的表型表征方案，并据此构建了代理辅助遗传编程算法，该算法能以极低的计算开销更早地进化出高质量启发式规则，从而显著提升了进化效率。

要点

这篇论文讲述了一个关于如何更聪明、更省钱地给复杂项目排期的故事。我们可以把它想象成是在管理一个超级繁忙的大型建筑工地。

1. 核心难题：工地上的“混乱”与“盲猜”

想象一下，你是一个工地的总指挥（项目经理）。你的任务是安排几百个工人（活动）在有限的时间、有限的工具（资源）下，把大楼盖好。

• 动态变化：最头疼的是，你没法提前知道每个工人具体要花多久。也许今天下雨，也许机器坏了，工期随时在变。你必须在现场根据当时的情况，实时决定：“接下来先让谁干活？用哪种方法干？”
• 传统方法（遗传编程 GP）：以前，科学家让计算机像“进化生物”一样，自动发明各种排班规则（比如“优先干最急的活”或“优先干用资源最少的活”）。计算机通过成千上万次的“模拟演练”来测试这些规则好不好用。
• 痛点：这个“模拟演练”非常烧钱、烧时间。就像你要为了测试一个排班规则，真的把整个工地模拟运行一遍，这需要巨大的计算量。计算机累得够呛，还没找到最好的规则。

2. 新方案：给规则画“肖像画”（表型特征化）

为了解决“太慢太贵”的问题，作者提出了一种**“替身代理”（Surrogate Model）**的方法。

• 什么是“替身代理”？
  想象一下，你要面试几千个排班员（计算机生成的规则）。

  • 旧方法：让每个人真的去工地干一天活，看看谁干得好。这太慢了。
  • 新方法：先给每个人画一张**“行为肖像画”（论文里叫表型特征向量**）。
    • 这张画不是画长相，而是画**“他在面对各种突发状况时，会怎么选择”**。
    • 比如：当有 10 个活要干时，他是把第 3 个排第一，还是把第 8 个排第一？
    • 这张“肖像画”非常小，画出来很快，不需要真的去工地干活。

• 创新点：以前的“肖像画”只画了“谁排第一”，但这不够。这篇论文发明了一种**“排名肖像画”，不仅看谁排第一，还看所有候选人的排名顺序**。这就好比不仅看谁拿了冠军，还看谁拿了亚军、季军，这样能更精准地识别出这个人的真实水平。

3. 工作流程：先“画像”，再“面试”

有了这张“肖像画”，整个选拔过程变得超级高效：

1. 生成候选人：计算机一次生成很多个新的排班规则（比如 4000 个）。
2. 快速画像：给这 4000 个规则都画一张“行为肖像画”。这步很快，就像照镜子一样。
3. 替身预测：利用一个**“老练的面试官”（代理模型）**，看着这些“肖像画”，预测谁干得好。
   • 面试官不需要真的让他们去工地，只要看“肖像画”长得像不像以前那些干得好的人，就能猜出谁行。
4. 优中选优：只挑出预测中最好的 1000 个，让他们去进行真正的“工地模拟”（昂贵的全量评估）。
5. 淘汰与进化：剩下的 3000 个直接淘汰，不用浪费时间去模拟了。

4. 结果：既快又好

实验结果显示，这种方法非常成功：

• 省钱：它能在少花 20% 到 40% 的计算成本的情况下，找到和以前一样好（甚至更好）的排班规则。
• 提速：它能更早地发现优秀的规则。就像在赛跑中，它不需要跑完全程就知道谁有冠军相，提前锁定胜局。
• 代价极小：画“肖像画”和用“替身”预测的时间，只占真正模拟时间的几十分之一。就像为了省下一顿大餐的钱，只花了几块钱买了张优惠券。

总结

这篇论文的核心思想就是：不要盲目地让所有候选人都去“真刀真枪”地干，先给他们画一张“行为画像”，用聪明的算法快速筛选出最有潜力的，只让精英去接受真正的考验。

这就好比在选秀节目中，评委不再让所有选手都唱完一整首歌，而是先听一段“清唱小样”（画像），觉得有潜力的再进棚录正片。这样既节省了录音棚的费用，又加快了选拔速度，最终选出的明星质量还更高。

技术摘要

这是一份关于论文《Surrogate-Assisted Genetic Programming with Rank-Based Phenotypic Characterisation for Dynamic Multi-Mode Project Scheduling》（基于排序表型特征表征的代理辅助遗传编程用于动态多模式项目调度）的详细技术总结。

1. 研究背景与问题定义 (Problem)

核心问题： 动态多模式资源约束项目调度问题 (DMRCPSP)。

• 定义： 这是一个在动态环境下进行的项目调度问题。活动具有多种执行模式（每种模式对应不同的持续时间和资源需求），且活动的实际持续时间在执行前是不确定的，仅在运行时揭示。
• 挑战： 需要在满足优先关系和资源约束的前提下，实时决定哪些活动执行以及以何种模式执行，以最小化项目总工期（Makespan）。
• 现有方法的局限：
  • 遗传编程 (GP)： 作为一种超启发式方法，GP 能自动进化出调度规则，但在动态环境中，评估每个 GP 个体（启发式规则）都需要进行大量的基于模拟的适应度评估，计算成本极高，限制了可扩展性。
  • 代理模型 (Surrogate Models) 的瓶颈： 虽然代理模型可以降低评估成本，但其成功应用依赖于能够准确捕捉启发式规则行为差异的表型特征表征 (Phenotypic Characterisation, PC) 方案。
  • 现有 PC 方案的不足： 现有的 PC 方案（如针对作业车间调度的方案）主要适用于单选择决策场景。而 DMRCPSP 中的启发式规则涉及基于排序的活动选择和活动组（子集）选择。现有的基于索引的 PC 方案无法有效处理活动排序的排列组合爆炸问题，也无法区分那些选择相同首选活动但后续排序不同的规则，导致个体间的行为距离测量不准确。

2. 方法论 (Methodology)

本文提出了一种基于排序的表型特征表征方案，并将其集成到代理辅助遗传编程 (Surrogate-Assisted GP) 框架中。

A. 新的表型特征表征方案 (Rank-based PC Scheme)

为了解决 DMRCPSP 中决策行为的复杂性问题，作者设计了一种基于决策情境的 PC 方案：

1. 决策情境分类： 将调度过程中的决策分为两类：
   • 活动排序情境 (Activity Ordering Situations)： 对符合条件的“活动 - 模式”对进行优先级排序。
   • 活动组选择情境 (Activity Group Selection Situations)： 从候选子集中选择要执行的活动组。
2. 特征提取：
   • 在模拟过程中采样特定的决策情境。
   • 对于每个 GP 个体，应用其对应的启发式规则（活动排序规则和活动组选择规则）。
   • 记录所有候选项（活动 - 模式对或活动组）的排名 (Rank)。
   • 向量构建： 将所有决策情境中候选项的排名序列拼接，形成完整的 PC 向量。
3. 优势： 该方案不仅捕捉了首选项的选择，还保留了候选项之间的相对排序关系，能够更准确地反映启发式规则的行为特征。

B. 代理辅助 GP 算法框架 (Surrogate-Assisted GP Framework)

基于上述 PC 方案，构建了如下工作流程：

1. 初始化： 随机生成初始种群，计算每个个体的 PC 向量，去除重复个体（基于 PC 向量），对剩余个体进行全量适应度评估。
2. 进化循环：
   • 构建代理模型： 利用当前种群的 PC 向量和真实适应度值构建代理数据库。
   • 生成中间后代： 生成 $k \times |P|$ 个中间后代（$k$ 为后代倍数，如 1.5, 2, 4）。
   • 去重与估算： 计算中间后代的 PC 向量，去重后，使用代理模型（基于最近邻回归，计算曼哈顿距离）估算其适应度。
   • 选择： 根据估算适应度选择前 $|P|$ 个个体进行全量真实评估。
3. 终止： 满足停止条件后返回最优个体。

C. 代理模型设计

• 采用最近邻 (Nearest-Neighbour) 回归模型。
• 训练策略： 代理数据库仅包含当前代的个体。这是因为不同代的模拟使用不同的随机种子，适应度值不可直接跨代比较，因此不累积历史数据。

3. 实验设置 (Experimental Setup)

• 基准算法： 对比了文献 [13] 中的 KGGP 算法（无代理辅助的 GP）。
• 测试场景： 包含 200 个活动，3 种执行模式，12 种可再生资源的动态项目。设置了三种优先关系复杂度（Order Strength: 0.75, 0.5, 0.25）。
• 变体算法： 提出了 SKGGP 系列，通过改变后代倍数 $k$ (1, 1.5, 2, 4) 来研究不同策略的影响。
• 评估指标： 相对于理论下界的平均工期（Makespan），以及收敛速度、计算开销。

4. 主要结果 (Results)

1. 性能提升：

   • 引入代理辅助的 SKGGP 算法（特别是 $k=2$ 和 $k=4$ 的变体）在大多数场景下显著优于基准 KGGP。
   • 收敛速度： SKGGP-2 和 SKGGP-4 的收敛速度明显快于 KGGP，能够更早地发现高质量的启发式规则。
   • 评估预算节省： 在达到与 KGGP 相同性能水平时，SKGGP 节省了约 20% - 40% 的全量适应度评估次数。

2. 代理模型的有效性分析：

   • 精度： 当 $k=1.5$ 时，代理模型区分高质量个体的精度最高（80-90%）。随着 $k$ 增大（如 $k=4$），精度下降至 50-60%，因为候选空间变大，而代理数据库（仅当前代）相对较小，难以覆盖所有分布。
   • 额外后代的贡献： 即使 $k=4$ 时精度下降，生成的额外后代中仍有约 35% 的个体被证明是高质量的（正确添加），说明增加中间后代数量有助于探索更优解，尽管也引入了更多噪声。

3. 计算开销：

   • 代理估算（包括 PC 向量计算和距离计算）的时间仅占全量评估时间的 1/20 到 1/40。
   • 这表明引入代理模型带来的额外计算开销极小，性价比极高。

5. 核心贡献与意义 (Key Contributions & Significance)

1. 填补了 PC 方案的空白： 首次为 DMRCPSP 领域的遗传编程设计了适用的表型特征表征方案。该方案通过基于排名的向量解决了传统方案无法处理“活动排序”和“子集选择”混合决策场景的难题，能够准确捕捉启发式规则的行为差异。
2. 提升了动态调度效率： 证明了代理辅助 GP 可以在不显著增加计算成本的前提下，大幅减少昂贵的模拟评估次数，从而更快地找到高质量调度策略。这对于需要实时响应的动态项目调度环境具有极高的实用价值。
3. 方法论的普适性启示： 研究揭示了在动态决策问题中，如何设计能够反映决策逻辑（而不仅仅是最终选择）的特征表示，对于将代理模型应用于其他复杂的组合优化问题具有参考意义。
4. 参数敏感性分析： 深入分析了后代倍数 $k$ 对进化效率和代理精度的影响，为实际应用中平衡探索（Exploration）与利用（Exploitation）提供了理论依据。

总结

该论文通过创新性地设计基于排序的表型特征表征方案，成功将代理模型引入到动态多模式项目调度的遗传编程中。实验结果表明，该方法在保持低计算开销的同时，显著提高了进化算法的搜索效率和最终解的质量，为解决复杂的动态资源调度问题提供了一种高效、可扩展的新途径。