[Paper] 用图神经网络增强遗传算法：排课案例研究

Source: arXiv - 2602.08619v1

概述

本文提出了一种新颖的混合方法，将多模态遗传算法（GA）与图神经网络（GNN）相结合，以解决经典的员工排班时间表问题。通过让 GNN 向 GA 的进化搜索注入领域层面的知识，作者实现了更快的收敛速度和更高质量的排班——这一进展有望简化众多实际的调度系统。

关键贡献

• 首个用于排班的 GA‑GNN 混合模型 – 引入一种无缝集成方式，在 GA 循环中将 GNN 作为“增强算子”。
• 面向领域的 GNN 设计 – 构建员工、班次和约束的图结构表示，使网络能够学习通用的排班启发式规则。
• 广泛的实证验证 – 在标准员工排班数据集上，将该混合模型与经过优化的独立 GA 和 GNN 基线进行基准测试，显示出统计显著的提升。
• 开源实现 – 提供代码和训练好的模型，便于实践者复现和采用。

方法论

1. 问题建模 – 将排班任务编码为图：节点代表员工和班次时段，边捕获资格、可用性以及硬约束（例如法定工作时长限制）。
2. 遗传算法核心 – 多模态 GA 维护候选排班的种群，使用交叉、变异和选择算子来探索解空间。
3. 图神经网络 – 离线在历史排班上训练 GNN（如图卷积网络），预测节点‑边对的“良好”分配分数，有效学习软约束和偏好。
4. 混合交互 – 在每一代 GA 过程中，查询 GNN 以 增强 子代：它重新打分或局部修复排班，建议更高效的分配，引导进化过程向有前景的区域发展。
5. 优化循环 – 首先分别调优两个组件（超参数搜索、架构选择）。随后对混合系统进行联合微调，确保 GNN 的建议是对 GA 探索的补充而非主导。

结果与发现

• 与单独使用 GA 相比，混合方法将目标值降低了 ≈15 %，并将约束违规次数削减了 ≈50 %。
• 由于 GNN 提供的指导，收敛速度约 快30 %，相较于 GA 更为迅速。
• 统计检验（Wilcoxon 符号秩检验）表明改进具有显著性（p < 0.01）。

实际意义

• 企业排班系统 – 生成每周员工排班表的公司（零售、医疗、物流）可以将 GNN 增强的 GA 接入现有流水线，从而生成更合规、对员工更友好的排班，并减少人工微调。
• 快速原型化新约束 – 由于 GNN 从图结构数据中学习，添加新规则（例如临时假期政策）只需更新图特征并进行微调，无需重新设计整个 GA。
• 边缘设备部署 – GNN 推理步骤轻量，混合模型可在普通服务器甚至本地硬件上运行，适用于数据不能上传云端的隐私敏感环境。
• 跨领域迁移 – 同一混合框架可适配其他自然映射为图的组合优化问题（车辆路径、考试排课、资源分配），加速各行业的解决方案开发。

限制与未来工作

• 对超大实例的可扩展性 – 实验仅限于几百名员工的基准数据集；扩展到数千人可能需要层次化图表示或分布式 GA 种群。
• 训练数据依赖性 – GNN 的有效性取决于高质量历史排班表的可用性；冷启动情形可能导致性能下降。
• 混合开销 – 虽然整体运行时间有所提升，但额外的 GNN 推理会增加计算开销，对于超快速、低复杂度的排班任务可能得不偿失。
• 未来方向 – 作者建议探索基于强化学习的 GNN 进行在线适应，将约束编程求解器作为额外的混合伙伴，并将该方法扩展到多目标时间表（例如在成本与员工满意度之间平衡）。

作者

• Laura-Maria Cornei
• Mihaela-Elena Breabăn

论文信息

• arXiv ID: 2602.08619v1
• 分类: cs.NE, cs.AI, cs.LG
• 出版日期: 2026年2月9日
• PDF: 下载 PDF