Learning Memetic Algorithm for Multi-Complex Targets Scheduling of Large-Scale Heterogeneous Satellites

The advancements in satellite imaging systems have transformed the way we observe and interpret events on Earth, from environmental monitoring and disaster assessment to military reconnaissance and urban planning. However, the rapid growth in capability has also brought new operational challenges to the forefront: how to coordinate and schedule imaging tasks across a constellation of heterogeneous satellites when the targets themselves are numerous, diverse, and operationally complex.  At the core of the difficulty lies the diversity of “complex targets.” Some are tightly clustered in space, forcing satellites to adjust imaging strategies to capture multiple objectives within a single visible time window. Others are “multi-imaging” targets that must be revisited multiple times at specific intervals, often within the constraints of narrow observation windows. Still others are vast regional targets, where success depends not on a single snapshot but on high coverage ratios achieved through coordinated imaging by multiple platforms. Each category alone poses scheduling challenges, but when combined in the same operational window, they generate a solution space riddled with interdependencies and trade-offs that are computationally exhausting to resolve. The operational reality compounds the complexity. Modern satellite constellations typically blend assets with very different capabilities — optical and radar systems, high- and medium-resolution imagers, varying agility, and distinct onboard resource limits. Each imaging opportunity, represented as a visible time window (VTW), competes for power, data storage, and downlink capacity. The sheer number of possible task–satellite–time combinations creates a combinatorial explosion, rendering exhaustive optimization impractical. Traditional exact algorithms cannot keep pace without severely simplifying the problem, while many heuristic or metaheuristic approaches either lose solution quality at scale or struggle to balance global exploration with the nuanced local refinements needed for such heterogeneous tasks. Past research often sidestepped these full complexities by focusing on a single type of target, or by preprocessing the data to reduce problem size — for instance, clustering nearby targets or segmenting large regions into fixed strips. While these shortcuts improve computational tractability, they do so at the cost of flexibility, frequently discarding feasible high-value imaging opportunities. The result is a persistent gap between theoretical scheduling approaches and the messy realities of operational satellite planning.

To this account, new research paper published in Swarm and Evolutionary Computation and conducted by Dr. Lei Li, Professor Yonghao Du, Professor Feng Yao, Dr. Shilong Xu from the National University of Defense Technology alongside Professor Yucheng She from the China Academy of Space Technology, the researchers developed a Learning Memetic Algorithm with Variable Population and Neighborhood (LMA-VP/N) to address the multi-complex target scheduling problem for large-scale heterogeneous imaging satellites. Their approach integrates dual-population co-evolution, a learning hybrid-rule heuristic, and a deep Q-network–guided variable neighborhood search to adaptively balance exploration and exploitation. This framework unifies the scheduling of closely distributed, multi-imaging, and regional targets under a single integrated model, preserving operational realism while achieving high scalability and solution quality. The researchers tested their newly proposed LMA-VP/N against both established metaheuristics and classical local search methods, using twelve scenarios that varied in scale from modest constellations to immense operational settings involving thousands of tasks. Each scenario was drawn from open satellite scheduling datasets, with targets distributed to reflect realistic spatial arrangements and operational constraints. This diversity allowed them to see not only how the algorithm handled small, cleanly defined problems, but also how it coped when the task list grew overwhelming and the interactions between targets became intricate. In the smaller instances, where computational demands were modest, LMA-VP/N performed on par with other advanced algorithms like adaptive large neighborhood search or reinforcement-learning-guided genetic algorithms. This parity was telling: it showed that the new design did not lose efficiency in situations where more straightforward methods already work well. However, as the scale expanded, the differences became pronounced. The authors found that in the largest cases—those with several thousand tasks and heterogeneous satellite capabilities—LMA-VP/N consistently delivered the highest total profit values, often surpassing the next-best method by a comfortable margin. The dual-population structure proved especially important here, maintaining diversity in the search space so that the algorithm did not settle prematurely into suboptimal schedules. The authors also showed how individual design choices shaped performance and that removing the deep Q-network from the variable neighborhood search caused a noticeable decline in solution quality for large-scale scenarios which confirmed that adaptive operator selection was critical for navigating complex solution landscapes. Similarly, disabling the learning component of the hybrid-rule heuristic led to weaker results in high-density instances, where target conflicts and resource bottlenecks were more severe. These ablation tests made clear that each layer of adaptivity—whether in population collaboration, neighborhood selection, or heuristic rule weighting—contributed to the algorithm’s resilience as complexity mounted.

One important authors’ finding to mention came from examining the extension of visible time windows. When this feature was disabled, profits dropped sharply, with losses growing larger in denser, more competitive target fields. Visual comparisons of schedules made the reason intuitive: extended windows allowed satellites to capture additional targets without the costly attitude changes or resource reallocations that would otherwise be required. This not only increased overall coverage, especially for regional targets, but also freed capacity for multi-imaging and closely distributed tasks that might have been neglected.

In conclusion, the new study by Professor Yonghao Du and colleagues successfully unified the treatment of closely distributed, multi-imaging, and regional targets within a single integrated model, and showed that it is possible to preserve the full richness of real-world constraints without collapsing under computational strain. We believe the implications extend well beyond the immediate domain of earth observation satellites. The core architecture—a dual-population memetic algorithm augmented with deep reinforcement learning for adaptive local search—offers a general template for other complex scheduling environments where diverse resources, heterogeneous tasks, and interlinked constraints collide. Applications in unmanned aerial vehicle coordination, maritime surveillance, or even large-scale manufacturing planning could benefit from the same adaptive mechanisms that here proved so effective. The ability of the system to dynamically adjust search strategies and allocate computational effort where it yields the most return hints at a broader class of algorithms that can self-tune to the character of the problem as it unfolds. From a practical standpoint, the demonstrated scalability is especially important. As satellite networks grow in size and capability, operational planners face decision spaces that can no longer be navigated by human intuition supplemented with basic heuristics. This work provides a path toward tools that can handle thousands of interdependent tasks in minutes, producing schedules that are not only high in measured profit but also balanced, feasible, and aligned with operational priorities. The empirical evidence that visible time window extensions yield substantial gains also offers a concrete operational recommendation: rethinking imaging constraints in terms of flexible time spans rather than rigid slots can unlock performance gains without requiring new hardware.