Joint Probability Density Immune Algorithm for Multi-satellite Earth Observation Scheduling

As a multi-objective combinatorial optimization problem, multi-agile satellite scheduling of earth observation, which with long observation time and multiple observation windows under complex constraints, has been a hotspot research problem in recent years. As a scarce resource, improving the in-orbit utilization of satellites and optimizing the imaging observation plan have been the goals of many researchers. For small scale task scheduling, the optimal solution is obtained by precise algorithm. However, for the large-scale task scheduling, it is difficult to find the exact solution, and the precise algorithm no longer has the advantage. Intelligent algorithms have been widely studied to obtain approximate optimal solutions. Genetic algorithm and immune algorithm are the most widely used intelligent algorithm. But the immune algorithm follows the evolutionary mode of the genetic algorithm, when confronted with large-scale task scheduling, the evolution operations such as crossover and mutation tend to make the solution fall into local optimization easily, and the randomness of these two operations make the scheduling time increases. Therefore, the traditional evolutionary approaches not only resulted in a waste of resources but also extended the evolutionary generations. In this paper we developed an improved immune algorithm, which the evolutionary idea of probability distribution instead. The specific evolution process are as follows. First, discretized the observation time of the all tasks, then coded all observation periods of tasks as antibody genes. Secondly, assigned an average probability value to the different observation periods of tasks, so the initial joint probability density matrix was constructed. Finally, updates the joint probability density matrix until convergence according to the fitness value of antibodies, then the optimal scheduling solution was obtained. The simulation results show that compared with the genetic algorithm, both scheduling time and scheduling efficiency have a significant improvement.