Efficient Policy Learning with Hybrid Evaluation-Based Genetic Programming for Uncertain Agile Earth Observation Satellite Scheduling

📄 arXiv: 2603.08447v1 📥 PDF

作者: Junhua Xue, Yuning Chen

分类: cs.AI

发布日期: 2026-03-09

备注: 18 pages, 10 figures, 8 tables

💡 一句话要点

提出混合评估遗传编程(HE-GP)算法，高效解决不确定敏捷地球观测卫星调度问题。

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 地球观测卫星调度 不确定性优化 遗传编程 混合评估 超启发式算法

📋 核心要点

  1. 现有方法难以应对地球观测卫星调度中利润、资源消耗和可见性等方面的不确定性，导致调度方案的鲁棒性不足。
  2. 提出混合评估遗传编程(HE-GP)算法，通过动态切换精确和近似评估模式，在保证评估精度的同时降低计算成本。
  3. 实验结果表明，HE-GP在计算效率和调度性能上均优于手工启发式算法和基于单一评估的GPHH算法。

📝 摘要（中文）

不确定敏捷地球观测卫星调度问题(UAEOSSP)是一个新型组合优化问题，也是符合当前航天技术发展需求的实际工程挑战。它融合了利润、资源消耗和可见性等方面的不确定性，这可能导致预先计划的调度方案变得次优甚至不可行。遗传编程超启发式算法(GPHH)在演化可解释的调度策略方面显示出潜力；然而，其基于仿真的评估会产生高昂的计算成本。此外，在线调度算法(OSA)这种构造方法的设计直接影响适应度评估，导致策略空间中出现依赖于评估的局部最优。为了解决这些问题，本文提出了一种混合评估遗传编程(HE-GP)算法，以有效解决UAEOSSP。一种混合评估(HE)机制被集成到策略驱动的OSA中，结合了精确和近似过滤模式：精确模式通过精心设计的约束验证模块确保评估精度，而近似模式通过简化的逻辑降低计算开销。HE-GP基于实时进化状态信息动态切换评估模型。在16个模拟实例集上的实验表明，HE-GP显著优于手工启发式算法和基于单一评估的GPHH，在降低计算成本的同时，在各种场景中保持了出色的调度性能。具体而言，与仅采用精确评估的GP相比，HE-GP的平均训练时间减少了17.77％，并且HE-GP生成的最优策略在所有场景中实现了最高的平均排名。

🔬 方法详解

问题定义：论文旨在解决不确定敏捷地球观测卫星调度问题(UAEOSSP)。该问题考虑了利润、资源消耗和可见性等方面的不确定性，使得传统的确定性调度方法难以适用。现有基于仿真的遗传编程超启发式算法(GPHH)虽然可以演化调度策略，但计算成本高昂，且容易陷入依赖于评估的局部最优。

核心思路：论文的核心思路是利用混合评估(HE)机制，在遗传编程(GP)的进化过程中动态切换精确和近似评估模式。精确评估模式保证评估精度，近似评估模式降低计算开销。通过这种方式，HE-GP能够在保证调度性能的同时，显著降低计算成本，避免陷入局部最优。

技术框架：HE-GP的整体框架如下：首先，使用遗传编程(GP)生成调度策略；然后，使用在线调度算法(OSA)执行这些策略，并使用混合评估(HE)机制评估其性能。HE机制包含精确和近似两种过滤模式，根据进化状态动态切换。最后，根据评估结果更新GP的种群，进行迭代优化。

关键创新：该论文的关键创新在于提出了混合评估(HE)机制。与传统的单一评估方法相比，HE机制能够根据进化状态自适应地选择评估模式，从而在精度和效率之间取得平衡。这种动态切换的策略使得HE-GP能够更有效地搜索策略空间，找到更优的调度方案。

关键设计：HE机制的关键设计在于精确和近似过滤模式的实现以及切换策略。精确模式通过精心设计的约束验证模块确保评估精度，近似模式通过简化的逻辑降低计算开销。切换策略则基于实时进化状态信息，例如种群的多样性或适应度变化率，动态调整两种模式的使用频率。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，HE-GP算法在16个模拟实例集上显著优于手工启发式算法和基于单一评估的GPHH算法。与仅采用精确评估的GP相比，HE-GP的平均训练时间减少了17.77％，并且HE-GP生成的最优策略在所有场景中实现了最高的平均排名。这些结果表明HE-GP在计算效率和调度性能上都具有显著优势。

🎯 应用场景

该研究成果可应用于实际的地球观测卫星调度任务中，提高卫星资源的利用效率，降低运营成本。此外，该方法也可推广到其他具有不确定性和计算复杂性的组合优化问题，例如资源调度、生产计划等。

📄 摘要（原文）

The Uncertain Agile Earth Observation Satellite Scheduling Problem (UAEOSSP) is a novel combinatorial optimization problem and a practical engineering challenge that aligns with the current demands of space technology development. It incorporates uncertainties in profit, resource consumption, and visibility, which may render pre-planned schedules suboptimal or even infeasible. Genetic Programming Hyper-Heuristic (GPHH) shows promise for evolving interpretable scheduling policies; however, their simulation-based evaluation incurs high computational costs. Moreover, the design of the constructive method, denoted as Online Scheduling Algorithm (OSA), directly affects fitness assessment, resulting in evaluation-dependent local optima within the policy space. To address these issues, this paper proposes a Hybrid Evaluation-based Genetic Programming (HE-GP) for effectively solving UAEOSSP. A Hybrid Evaluation (HE) mechanism is integrated into the policy-driven OSA, combining exact and approximate filtering modes: exact mode ensures evaluation accuracy through elaborately designed constraint verification modules, while approximate mode reduces computational overhead via simplified logic. HE-GP dynamically switches between evaluation models based on real-time evolutionary state information. Experiments on 16 simulated instance sets demonstrate that HE-GP significantly outperforms handcrafted heuristics and single-evaluation based GPHH, achieving substantial reductions in computational cost while maintaining excellent scheduling performance across diverse scenarios. Specifically, the average training time of HE-GP was reduced by 17.77\% compared to GP employing exclusively exact evaluation, while the optimal policy generated by HE-GP achieved the highest average ranks across all scenarios.