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

• URL: http://arxiv.org/abs/2603.08447v2
• Date: Wed, 18 Mar 2026 00:12:48 GMT
• Title: Efficient Policy Learning with Hybrid Evaluation-Based Genetic Programming for Uncertain Agile Earth Observation Satellite Scheduling
• Abstract summary: The Agile Earth Observation Satellite Scheduling Problem (UAEOSSP) is a novel optimization problem.<n>It incorporates uncertainties in profit, resource consumption, and visibility, which may render pre-planned schedules suboptimal or even infeasible.<n>This paper proposes a Hybrid Evaluation-based Genetic Programming (HE-GP) for effectively solving UAEOSSP.
• Score: 12.409081996599665
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• A Smart-Scheduled Hybrid (SSH) EKF-FGO State Estimation [1.3750624267664155]
  This paper presents an experimental study that explicitly isolates optimisation scheduling using a Smart Scheduled Hybrid (SSH) EKF-FGO framework as a testbed.<n>By combining EKF-based state propagation with periodically invoked batch optimisation and holding solver structure and effort fixed, the main contribution is the experimental characterisation of optimisation scheduling as an independent design variable.<n>Results identify operating regimes in which most of the benefit of global optimisation can be retained at a fraction of the computational cost.
  arXiv  Detail & Related papers  (2026-06-14T23:13:56Z)
• Surrogate-Assisted Genetic Programming with Rank-Based Phenotypic Characterisation for Dynamic Multi-Mode Project Scheduling [6.835074198877901]
  Genetic Programming (GP) has been shown to evolve rules for decision-making tasks.<n>GP requires problem-specific phenotypic characterisation (PC) schemes of rules.<n>This paper proposes a rank-driven PC scheme derived from ordering of eligible activity-mode pairs and activity groups in decision situations.<n>The resulting PC vectors enable a surrogate model to estimate the fitness of unevaluated GP individuals.
  arXiv  Detail & Related papers  (2026-03-17T09:19:20Z)
• Unbiased Dynamic Pruning for Efficient Group-Based Policy Optimization [60.87651283510059]
  Group Relative Policy Optimization (GRPO) effectively scales LLM reasoning but incurs prohibitive computational costs.<n>We propose Dynamic Pruning Policy Optimization (DPPO), a framework that enables dynamic pruning while preserving unbiased gradient estimation.<n>To mitigate the data sparsity induced by pruning, we introduce Dense Prompt Packing, a window-based greedy strategy.
  arXiv  Detail & Related papers  (2026-03-04T14:48:53Z)
• An effective Genetic Programming Hyper-Heuristic for Uncertain Agile Satellite Scheduling [7.511388506308957]
  An effective Genetic Programming Hyper-Heuristic is designed to automate the generation of scheduling policies.<n>The evolved scheduling policies can be utilized to adjust plans in real time and perform exceptionally well.
  arXiv  Detail & Related papers  (2026-02-15T02:09:57Z)
• PGU-SGP: A Pheno-Geno Unified Surrogate Genetic Programming For Real-life Container Terminal Truck Scheduling [7.678307721780809]
  This paper proposes a pheno-geno unified surrogate GP algorithm, PGU-SGP, to enhance surrogate sample selection and fitness prediction.<n>With the same training time, PGU-SGP significantly outperforms traditional GP and the state-of-the-art algorithm on most datasets.
  arXiv  Detail & Related papers  (2025-04-15T15:19:42Z)
• CSF: Fixed-outline Floorplanning Based on the Conjugate Subgradient Algorithm Assisted by Q-Learning [9.16178663078742]
  We propose a nonsmooth analytic floorplanning model addressed by the conjugate subgradient algorithm (CSA)<n> Experimental results on the MCNC and GSRC benchmarks demonstrate that the proposed fixed-outline floorplanning algorithm based on CSAQ (CSF)<n>It is also demonstrated that the CSF is competitive to the state-of-the-art algorithms on floorplanning scenarios only containing hard modules.
  arXiv  Detail & Related papers  (2025-04-04T04:01:26Z)
• Towards safe and tractable Gaussian process-based MPC: Efficient sampling within a sequential quadratic programming framework [35.79393879150088]
  We propose a robust GP-MPC formulation that guarantees constraint satisfaction with high probability. We highlight the improved reachable set approximation compared to existing methods, as well as real-time feasible times.
  arXiv  Detail & Related papers  (2024-09-13T08:15:20Z)
• When Demonstrations Meet Generative World Models: A Maximum Likelihood Framework for Offline Inverse Reinforcement Learning [62.00672284480755]
  This paper aims to recover the structure of rewards and environment dynamics that underlie observed actions in a fixed, finite set of demonstrations from an expert agent. Accurate models of expertise in executing a task has applications in safety-sensitive applications such as clinical decision making and autonomous driving.
  arXiv  Detail & Related papers  (2023-02-15T04:14:20Z)
• Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time Guarantees [56.848265937921354]
  Inverse reinforcement learning (IRL) aims to recover the reward function and the associated optimal policy. Many algorithms for IRL have an inherently nested structure. We develop a novel single-loop algorithm for IRL that does not compromise reward estimation accuracy.
  arXiv  Detail & Related papers  (2022-10-04T17:13:45Z)
• Robust and Adaptive Temporal-Difference Learning Using An Ensemble of Gaussian Processes [70.80716221080118]
  The paper takes a generative perspective on policy evaluation via temporal-difference (TD) learning. The OS-GPTD approach is developed to estimate the value function for a given policy by observing a sequence of state-reward pairs. To alleviate the limited expressiveness associated with a single fixed kernel, a weighted ensemble (E) of GP priors is employed to yield an alternative scheme.
  arXiv  Detail & Related papers  (2021-12-01T23:15:09Z)
• Incremental Ensemble Gaussian Processes [53.3291389385672]
  We propose an incremental ensemble (IE-) GP framework, where an EGP meta-learner employs an it ensemble of GP learners, each having a unique kernel belonging to a prescribed kernel dictionary. With each GP expert leveraging the random feature-based approximation to perform online prediction and model update with it scalability, the EGP meta-learner capitalizes on data-adaptive weights to synthesize the per-expert predictions. The novel IE-GP is generalized to accommodate time-varying functions by modeling structured dynamics at the EGP meta-learner and within each GP learner.
  arXiv  Detail & Related papers  (2021-10-13T15:11:25Z)
• Mixed Strategies for Robust Optimization of Unknown Objectives [93.8672371143881]
  We consider robust optimization problems, where the goal is to optimize an unknown objective function against the worst-case realization of an uncertain parameter. We design a novel sample-efficient algorithm GP-MRO, which sequentially learns about the unknown objective from noisy point evaluations. GP-MRO seeks to discover a robust and randomized mixed strategy, that maximizes the worst-case expected objective value.
  arXiv  Detail & Related papers  (2020-02-28T09:28:17Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.