[Paper] 代理辅助遗传编程与基于排序的表型特征化用于动态多模式项目调度

Source: arXiv - 2603.16286v1

（请提供您希望翻译的具体文本，我将为您翻译成简体中文。）

概述

本文研究 动态多模式资源受限项目调度问题（DMRCPSP）——这是一项现实中的挑战，项目经理必须随着资源和项目状态的变化不断重新安排任务。通过将 遗传编程（GP） 与 代理模型 相结合，作者显著缩短了演化有效调度启发式所需的时间，使得在大型复杂项目中实现即时决策支持成为可能。

关键贡献

• 基于排名的表型特征化（PC）： 一种新颖的方法，通过在每个决策上下文中对符合条件的活动模式对和活动组进行排名，将 GP 生成的启发式规则转化为固定长度向量。
• 代理辅助的 GP 框架： 将 PC 向量与回归型代理模型集成，该模型在不运行昂贵仿真的情况下预测启发式规则的适应度。
• 效率提升： 证明了在代理引导下的 GP 能够 更早 找到高质量的调度规则，并且相较于最先进的 GP 基线仅有 适度的开销。
• 后代选择洞察： 表明代理的适应度估计可以使进化搜索倾向于有前景的后代，从而提升整体进化效率。

方法论

1. 问题编码：

   • 每个 GP 个体编码一个 启发式规则，决定下一个要调度的活动‑模式对。
   • 在给定的项目状态下，规则产生一个可行动作的有序列表。

2. 表型特征化：

   • 对于每个决策情境，将有序列表转换为 秩向量（例如，“活动 A‑模式 2 排第 1，活动 B‑模式 1 排第 2，…”。）
   • 将这些向量在大量抽样状态上聚合，得到固定大小的 PC 向量，捕捉规则行为而不依赖其语法 GP 表示。

3. 代理模型构建：

   • 使用少量 已评估 的 GP 个体，利用它们的 PC 向量作为输入、真实基于仿真的适应度作为目标，训练轻量回归模型（如随机森林或梯度提升）。

4. 代理辅助进化：

   • 在每一代 GP 中，代理预测新产生子代的适应度。
   • 仅将最有前景的候选（依据代理）送入昂贵的仿真进行真实评估；其余的被丢弃或保留以待后续重新评估。

5. 迭代精炼：

   • 随着获得新的真实适应度值，定期重新训练代理，使其预测与不断演化的种群保持一致。

结果与发现

• 代理辅助的方法始终能够更早地发现 更高质量的启发式。
• 由代理选出的后代表现出 更好的平均真实适应度，证明代理提供了有用的指导，而非仅仅噪声。
• 基于排名的 PC 在不同项目实例中表现稳健，能够处理活动数量、模式和资源约束的变化。

实际意义

• 更快的启发式生成： 项目管理软件现在可以即时演化自定义调度规则，能够在资源可用性变化时立即适应，而无需等待数小时进行完整的基于仿真的搜索。
• 可扩展的决策支持： 该方法能够扩展到更大型的项目（数百个活动），而传统的遗传编程（GP）在此类规模下会变得极其缓慢。
• 即插即用的代理模型： 由于性能指标（PC）是从规则的行为而非其语法中导出的，代理模型可以随时更换（例如使用神经网络），而无需重新设计 GP 流程。
• 实时再规划： 在建筑、航空航天或软件发布计划等行业中，该方法能够在出现意外事件（资源中断、范围变更）时实现近实时的重新调度。

限制与未来工作

• 代理模型的保真度： 代理模型的准确性取决于训练样本的多样性；在高度非线性或噪声较大的调度空间中，预测误差可能会误导搜索。
• 特定领域的 PC 设计： 基于排序的 PC 在 DMRCPSP 上表现良好，但在其他组合优化问题（如车辆路径规划）中可能需要进行适配。
• 计算预算权衡： 虽然整体运行时间下降，但仍存在一定的训练和更新代理模型的开销；在更紧的预算下可能需要更激进的剪枝策略。
• 作者提出的未来方向：
  • 探索 基于深度学习的代理模型，以捕获更丰富的行为模式。
  • 将框架扩展到 多目标 项目调度（例如平衡成本、风险和完工时间）。
  • 研究 迁移学习：在相似项目之间复用代理模型的知识，以进一步降低评估成本。

作者

• Yuan Tian
• Yi Mei
• Mengjie Zhang

论文信息

• arXiv ID: 2603.16286v1
• 分类: cs.NE, cs.AI
• 发表时间: 2026年3月17日
• PDF: 下载 PDF