用图神经网络增强遗传算法，提升排班优化效率与质量
Enhancing Genetic Algorithms with Graph Neural Networks: A Timetabling Case Study
- 将图神经网络作为知识引导模块嵌入遗传算法
- 在排班问题上实现更快收敛和更高解质
- 适合需要智能调度的场景，如医院排班
本文研究了将多模态遗传算法与图神经网络结合用于排班优化的影响。图神经网络用于封装领域知识以提升排班质量，而遗传算法则在搜索空间中探索不同区域，并将深度学习模型作为增强算子引导解的搜索趋向最优。该混合方法的两个组件最初独立设计、开发并优化以解决目标任务。在经典的员工排班问题上进行了多次实验，对比所提出的混合方法与独立优化的遗传算法和图神经网络。实验结果表明，相较于独立方法，该混合方法在时间效率和解质量指标上均带来统计显著的提升。据我们所知，这是首个将遗传算法与图神经网络结合求解排班问题的工作。
原文摘要 · Abstract (English)
This paper investigates the impact of hybridizing a multi-modal Genetic Algorithm with a Graph Neural Network for timetabling optimization. The Graph Neural Network is designed to encapsulate general domain knowledge to improve schedule quality, while the Genetic Algorithm explores different regions of the search space and integrates the deep learning model as an enhancement operator to guide the solution search towards optimality. Initially, both components of the hybrid technique were designed, developed, and optimized independently to solve the tackled task. Multiple experiments were conducted on Staff Rostering, a well-known timetabling problem, to compare the proposed hybridization with the standalone optimized versions of the Genetic Algorithm and Graph Neural Network. The experimental results demonstrate that the proposed hybridization brings statistically significant improvements in both the time efficiency and solution quality metrics, compared to the standalone methods. To the best of our knowledge, this work proposes the first hybridization of a Genetic Algorithm with a Graph Neural Network for solving timetabling problems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。