A hybrid estimation of distribution algorithm for agile earth observing satellite task scheduling problem

Agile Earth Observing Satellites (AEOSs) represent a new generation of Earth observation satellites, used for various observation tasks. To efficiently utilize the visible and observing durations of the AEOS, the AEOS scheduling problem (AEOSSP) is formulated to maximize the overall observation profit satisfying the complex operational constraints. In this paper, a hybrid Estimation of Distribution Algorithm (EDA) that incorporates three knowledge-oriented local search operators is proposed to efficiently solve AEOSSP. The multiple multidimensional knapsack problem with conflicts (MMdKPC) is first modeled and to formulate AEOSSP. An EDA probability model as well as its updating and sampling mechanisms, is designed to generate solutions to explore the solution space and generate potential solutions. In addition, based characteristics of MMdKPC, three knowledge-oriented local search operators are developed to improve solution. Based on the benchmark instances and simulation data provided sampled from Satellite Tool comparison simulation experiments are carried out. The results validate the effectiveness of three knowledge oriented local search operators, respectively. Additionally, the proposed hybrid EDA performs better compared to the existing state-of-the-art algorithms in terms of overall observation profit.