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

arXiv: https://arxiv.org/abs/2603.08447 · HTML: https://mlsanity.com/paper/2603.08447/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 64 references that are in the map.
- First posted on arXiv 9 Mar 2026.

## Builds on (most cited first, 6 of 6)

- [Deep Reinforcement Learning for Multi-objective Optimization](https://mlsanity.com/paper/1906.02386/) (2019)
- [Agile Earth observation satellite scheduling over 20 years: formulations, methods and future directions](https://mlsanity.com/paper/2003.06169/) (2020)
- [Simulated annealing based heuristic for multiple agile satellites scheduling under cloud coverage uncertainty](https://mlsanity.com/paper/2003.08363/) (2020)
- [Deep Symbolic Optimization for Combinatorial Optimization: Accelerating Node Selection by Discovering Potential Heuristics](https://mlsanity.com/paper/2406.09740/) (2024)
- [Markov Decision Processes For Multi-Objective Satellite Task Planning](https://mlsanity.com/paper/1910.08419/) (2019)
- [An effective Genetic Programming Hyper-Heuristic for Uncertain Agile Satellite Scheduling](https://mlsanity.com/paper/2602.15070/) (2026)

## Abstract (arXiv)

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.