Source-linked AI summary
RL-GA: A Reinforcement Learning-Based Genetic Algorithm for Electromagnetic Detection Satellite Scheduling Problem
Yanjie Song, Luona Wei, Qing Yang, Jian Wu, Lining Xing, Yingwu Chen
TL;DR
EDSSP requires high-quality satellite schedules despite numerous detection, timing, storage, and operational constraints. The paper builds a practical mixed-integer model and an RL-GA that uses Q-learning within genetic search, then reports effective scheduling across multiple instances. It concludes that the approach handles increasing satellite and task counts, while future work targets lower Q-value evaluation cost and online scheduling.
Problem
EDSSP must schedule electromagnetic satellite tasks under detection, timing, storage, and operational constraints, while existing studies simplify satellite-specific modes.
Method
The paper combines a mixed-integer EDSSP model with an RL-GA that uses Q-learning to select evolutionary operators and TTWSA to generate schedules and fitness values.
Results
RL-GA effectively solves EDSSP and handles increases in the numbers of satellites and tasks while producing high-quality plans in a short time.
Takeaways & Limitations
The proposed combination provides an approach for EDSSP and is also applicable to other order-dependent combinatorial optimization problems.
Takeaways & Limitations
Future work will reduce Q-value evaluation cost and extend learning-based approaches to online scheduling, which has higher algorithmic requirements.
Abstract
from arXiv · showhide
The study of electromagnetic detection satellite scheduling problem (EDSSP) has attracted attention due to the detection requirements for a large number of targets. This paper proposes a mixed-integer programming model for the EDSSP problem and a genetic algorithm based on reinforcement learning (RL-GA). Numerous factors that affect electromagnetic detection are considered in the model, such as detection mode, bandwidth, and other factors. The RL-GA embeds a Q-learning method into an improved genetic algorithm, and the evolution of each individual depends on the decision of the agent. Q-learning is used to guide the population search process by choosing evolution operators. In this way, the search information can be effectively used by the reinforcement learning method. In the algorithm, we design a reward function to update the Q value. According to the problem characteristics, a new combination of <state, action> is proposed. The RL-GA also uses an elite individual retention strategy to improve search performance. After that, a task time window selection algorithm (TTWSA) is proposed to evaluate the performance of population evolution. Several experiments are used to examine the scheduling effect of the proposed algorithm. Through the experimental verification of multiple instances, it can be seen that the RL-GA can solve the EDSSP problem effectively. Compared with the state-of-the-art algorithms, the RL-GA performs better in several aspects.
1. Introduction
The paper frames EDSSP as a constrained satellite-planning problem requiring practical electromagnetic detection modeling and efficient large-scale optimization. It proposes combining reinforcement learning with a genetic algorithm to improve adaptive search and reports effective performance across extensive experiments.
- Problem motivation: EDSSP plans satellite resources and task execution times, but orbit, coverage, and operational constraints limit the number of executable tasks.
- Problem motivation: Higher detection accuracy can increase generated data, creating a trade-off with limited onboard storage capacity.
- Research gap: Prior electromagnetic-satellite studies simplify satellite-specific modes, leaving EDSSP modeling relatively immature and insufficiently detailed.
- Research gap: The paper combines reinforcement learning with genetic search because evolutionary parameters are problem-sensitive while reinforcement learning lacks domain-specific knowledge.
- Contributions: The proposed model incorporates detection mode, detection angle, and data volume to produce more practical scheduling schemes.
- Contributions: The RL-GA uses Q-learning to guide population evolution, with a new state-action design, reward function, strategy selection, and task-window selection algorithm.
- Results: Extensive experiments verify that RL-GA performs well and solves large-scale EDSSP effectively.
2. Model
The EDSSP model maximizes detection profit while scheduling tasks within visibility, timing, angle, storage, and equipment-transition constraints. It accounts for detection quality, bandwidth-dependent data generation, and practical satellite operating assumptions.
- Problem formulation: EDSSP assigns an ordered task sequence to electromagnetic satellites and maximizes detection profit under satellite constraints.
- Detection quality: Detection quality depends on antenna angle, signal gain, detection accuracy, bandwidth, generated data, and limited satellite storage.
- Model components: The model represents task attributes, satellite resources, orbits, time windows, visible-time bounds, detection angles, and execution variables.
- Assumptions: The formulation assumes identical receivers and storage devices, no external detection interference, fixed tasks, sufficient orbital energy, and one detection per task.
- Bandwidth and data: Bandwidth is matched to task importance, and generated data equals the per-second rate β · ϕ(degree_j) multiplied by task duration.
- Operational transitions: Equipment transitions account for polarization, detection mode, frequency, bandwidth, and load on/off changes between tasks.
3. The Proposed Method
Because EDSSP is computationally difficult, the paper proposes an RL-based genetic algorithm and a task time-window selection algorithm to generate scheduling schemes.
- Method motivation: The paper identifies EDSSP as a complex problem without a polynomial-time algorithm and proposes RL-GA with TTWSA to solve it.
3.1. Reinforcement Learning based Genetic Algorithm (RL-GA)
RL-GA combines genetic population search with Q-learning to adaptively select evolutionary operators, decode task schedules, and retain elite solutions. TTWSA evaluates executable plans and supplies rewards for Q-value updates.
- Algorithm rationale: Evolutionary algorithms provide population-based global search for large-scale complex problems but are sensitive to parameter configuration.
- Procedure: The algorithm initializes a population and Q-table before iterating under an evaluation budget.
- Procedure: Elite individuals can be retained by replacing selected population members with the global-best individual.
- RL-GA pipeline: RL-GA uses Q-learning to select crossover and mutation operations, while TTWSA decodes populations into task execution plans.
- RL-GA pipeline: TTWSA determines executable tasks and their start and end times, and its resulting profit supports reward calculation and Q-value updating.
- RL-GA pipeline: The GA supplies search data to the agent, and the agent’s selected actions directly control population evolution.
3.1.1. Individual Representation and Initialization
The RL-GA represents individuals with real-number sequences and decodes them into detection schemes using the task time window selection algorithm.
- Individuals are encoded as real-number sequences, giving each position a unique element correspondence.
- The task time window selection algorithm decodes task order to determine execution or discard decisions and specific execution times.
- Real-number coding simplifies decoding and guarantees legitimate solution structures without repair methods.
3.1.2. Fitness Evaluation
Fitness evaluation assigns each individual an objective-function value based on its corresponding detection plan, supporting both selection and reinforcement-learning updates.
- Fitness evaluation calculates each individual's objective-function value from its corresponding detection plan.
- The fitness value is used to select population individuals and to evaluate rewards and update states in reinforcement learning.
3.1.3. Individual Selection
Individual selection combines fitness-based preference with population diversity, then applies evolutionary operators to generate new individuals.
- Roulette selection makes better-performing individuals more likely to be selected while preserving selection opportunities for others.
- The RL-GA uses crossover and mutation operators to search for improved detection plans.
- Seven crossover operators vary segment length or apply heuristic sequence rearrangements, including C1–C7.
- Short segment crossover exchanges two task-sequence segments of length L within an individual.
- Medium and long segment crossover exchange segments of lengths 2L and 3L, respectively.
- Fragment flipping reverses a selected task-sequence fragment of length L.
3.1.5. Mutation
The RL-GA combines mutation and crossover with Q-learning, using fitness changes to select operators and update the search state while balancing exploration and exploitation.
- Mutation exchanges two positions in the sequence and is combined with crossover to evolve individuals.
- Q-learning selects population update strategies by choosing combinations of crossover and mutation operators according to Q-values.
- The agent state records whether fitness improves, while rewards are tied to fitness values and their changes.
- The Q-value table contains 15 actions and 30 state-action combinations for seven crossover operators, one mutation operator, and two fitness-improvement states.
- Softmax uses Q-values and a control parameter for action probabilities, while ε enables random evolution strategies to maintain exploration.
3.1.7. Elite Individual Retention Strategies
RL-GA retains elite individuals across generations to improve convergence, while limiting prolonged elite retention to preserve global search ability and stopping after a preset evaluation budget.
- Elite retention: The elite retention strategy carries the best individual found by the search into the next generation.This strategy is introduced because EDSSP has a large solution space.
- Elite retention: A count parameter and threshold Thre regulate elite retention because excessive retention can affect global search ability.
- Termination: The algorithm outputs the optimal result as the final execution plan after the iterative search ends.
- Termination: Evolution times num eval record iterative search and provide the evaluation index for the reinforcement-learning-based crossover and mutation process.
3.2. Task Time Window Selection Algorithm (TTWSA)
TTWSA first filters infeasible task time windows, then selects start and end times near the window midpoint to increase detection profit while satisfying constraints.
- TTWSA overview: TTWSA uses two-stage task time window selection: preliminary filtering followed by execution-time determination.
- Preliminary filtering: Preliminary filtering clips or discards windows that violate constraints such as angle and transition time.It obtains the actual earliest available start time and latest available end time after filtering.
- Execution-time determination: The midpoint of a feasible time window is used as an intermediate moment because it usually has the smallest antenna-to-signal-source angle.Detection profit is described as first increasing and then decreasing with execution timing.
- Execution-time determination: The best start time is calculated from the intermediate moment, with task execution shifted forward or backward until all constraints are satisfied.The resulting start and end times define the task execution interval.
- Notation: The best start time bstijo denotes the execution start time for task j of satellite i on orbit o.
4. Performance Evaluation of Proposed Algorithm
The evaluation tests RL-GA across increasingly large scheduling instances against state-of-the-art algorithms, examining profit, stability, convergence, CPU time, and practical system operation. RL-GA generally delivers stronger scheduling performance, with advantages becoming clearer on large and ultra-large instances.
- Experimental settings: The experiments use four instance scales from 100–300 to 1000–1400 tasks, with 30 runs per instance and detection profit as the evaluation basis.Instances are randomly distributed globally, and the study reports maximum, mean, and standard-deviation results.
- Scheduling performance: RL-GA’s profit advantage becomes significant as small-scale instances grow from 200 to 300 tasks, whereas results are nearly identical at 100 tasks.The reported gap between algorithms increases with problem scale as constraints prevent some tasks from being executed.
- Scheduling performance: On medium- and large-scale instances, RL-GA achieves the largest detection profit in most cases and shows good average performance and stability across repeated runs.The comparison includes IGA, ALNS/TPF, ABC, and CHA.
- Scheduling performance: On ultra-large instances, Q-learning changes strategy selection to explore new search spaces, while elite retention improves local search ability.The other comparison algorithms are relatively close overall, with ABC often outperforming the remaining state-of-the-art algorithms.
- Scheduling performance: RL-GA has better planning performance than traditional GA and GA ELUMS because Q-learning dynamically selects operations throughout population evolution.This learning mechanism uses search information to improve exploration of the solution space.
- Overall evaluation: RL-GA achieves better results in profit, stability, convergence speed, and CPU time, although its time advantage is not obvious on small instances.The study reports significant differences from comparison algorithms at p = 0.05 in most instances.
- Case study: The case study obtains steady daily profit with fewer than 10% of tasks incomplete and maintains planning performance during multi-day system operation.Generated plans are checked, converted into satellite commands, executed, and followed by data downlink and distribution.
5. Conclusion
The paper proposes RL-GA for EDSSP, combining Q-learning with genetic search and elite retention to adapt operator selection. Experiments report advantages over comparison algorithms, while future work targets the computational cost of Q-value evaluation and online scheduling.
- Method: RL-GA combines Q-learning with a genetic algorithm so individuals select evolution strategies through rewards and Q values.The method constructs state-action combinations from search performance and updates values after each evolution.
- Method: An elite individual retention strategy is included to improve search performance.
- Results: The approach is reported to handle increases in the numbers of satellites and tasks and to produce high-quality mission plans in a short time.The paper also states that the problem-solving idea applies to other order-dependent combinatorial optimization problems.
- Future work: Future work will reduce the computational cost of Q-value evaluation without affecting algorithm performance.The paper also proposes considering transfer learning, deep learning, and online scheduling in future research.