A Multi-Population Genetic Algorithm for Multi-Objective Multi-Agile Satellite Task Scheduling

The multi-agile satellite task scheduling problem (MSTSP) is a challenging scheduling optimization problem in the aerospace field, which directly influences the total task execution profit and load balance among satellites. The MSTSP has two issues to be handled sequentially, the initial task allocation and then the observation window allocation. Therefore, the quality of task allocation will heavily influence not only the results of observation window allocation but also the final profit and load balance of the multi-agile satellites system. However, existing researches mainly study the observation window allocation subproblem but fail to obtain satisfactory results in the initial task allocation, leading to poor performance when solving the entire MSTSP. To this end, this paper proposes a multi-population multi-objective genetic algorithm with an allocation knowledge-based crossover strategy (MPMOGA-AKCS). In order to optimize the two objectives of total profit and load balance more effectively, two strategies are proposed and integrated in MPMOGA-AKCS. First, a heuristic crossover strategy based on the multiple populations for multiple objectives (MPMO) framework is proposed to quickly generate high-quality offspring through incorporating the allocation knowledge from successful solutions for different obj ectives. Second, an adaptive archive update strategy is proposed to realize the dynamic balance between the diversity and convergence of the solution set through phased adjustments. Extensive experimental results show that the performance of the MPMOGA-AKCS is superior to some state-of-the-art algorithms.