Search papers, labs, and topics across Lattice.
This paper introduces a Hybrid Evaluation-based Genetic Programming (HE-GP) approach to solve the Uncertain Agile Earth Observation Satellite Scheduling Problem (UAEOSSP), which involves uncertainties in profit, resource consumption, and visibility. HE-GP integrates a hybrid evaluation mechanism into the Online Scheduling Algorithm (OSA), switching between exact and approximate filtering modes based on the evolutionary state to balance accuracy and computational cost. Experiments on simulated instance sets demonstrate that HE-GP outperforms handcrafted heuristics and single-evaluation based GPHH, achieving a 17.77% reduction in training time while maintaining superior scheduling performance.
By intelligently switching between exact and approximate evaluations during genetic programming, HE-GP slashes training time by 17.77% while simultaneously improving the quality of scheduling policies for Earth observation satellites.
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.
