基于深度强化学习的自适应大邻域搜索算法在成像卫星调度问题中的应用

来源：电子与信息学报杂志2025年第12期北京时间：

作者：魏普远, 何磊

单位：国防科技大学系统工程学院 长沙 410072

摘要：卫星调度问题(Satellite Scheduling Problem, SSP)是典型的NP-hard组合优化问题，其目标是在满足一系列复杂物理和运行约束的条件下，最大化观测收益或完成任务数量。自适应大邻域搜索(Adaptive Large Neighborhood Search, ALNS)是求解此类问题的有效元启发式算法，其性能高度依赖于破坏与修复算子的选择策略。传统ALNS算法通常采用基于历史表现的启发式计分机制来调整算子选择概率，这种机制受参数影响较大且无法动态适应搜索过程中的复杂状态变化。为解决此问题，该文提出了一种基于深度强化学习(Deep Reinforcement Learning, DRL)的自适应大邻域搜索算法(DR-ALNS)。该算法将算子选择过程建模为一个马尔可夫决策过程，智能体利用深度强化学习在每次迭代中根据当前解的状态动态选择最合适的破坏与修复算子。通过端到端的学习，DRL智能体能够学习到一种隐式的、高效的算子选择策略，从而更好地引导搜索方向，提升算法的全局探索与局部开发能力。通过在标准的卫星调度问题测试集上进行实验，可以看出DR-ALNS算法产生的解的质量优于传统ALNS及其他算法。

关键词：SSP, DR-ALNS, 组合优化问题, 深度强化学习

基金资助：国家自然科学基金(72571283)，中国科协青年人才托举工程(2022QNRC001)