Solving The Muti-earth Observation Satellites Scheduling Problem With A Quantum Genetic Algorithm

In recent years,with the continuous development of China's space undertaking,satellites have played an increasingly important role in military,agricultural and commercial applications.The imaging satellites scheduling is based on the comprehensive consideration of resources such as satellites,ground stations and the needs of different users,and maximizes the benefits of limited resources by formulating conflict-free scheduling solutions.The imaging satellite mission planning belongs to the complex combinatorial optimization problem,and as the scale of the problem increases,the solution space also exponentially increases.Most of the present researches use heuristic algorithms to solve the problem.As a genetic algorithm,quantum genetic algorithm is used in combination optimization,function optimization,communication,image,automatic control,path planning and other fields,and shows good results.In this thesis,the application needs of imaging satellite in modern society are closely integrated,and the concrete realization of quantum genetic algorithm in multi-satellite mission planning is specially designed.Firstly,the principle and method of multi-satellite mission planning are analyzed,and a reasonable scheduling model is established.Considering the satellite's storage,energy and attitude adjustment,the input and output of the problem are analyzed.Combining with the characteristics of the problem,the problem is decomposed into two phases:the time window selection phase and the construction of the time window sequence phase,and an auroral directed graph model is established to transform the problem into a path planning problem.Secondly,this thesis designed two kinds of data download task scheduling strategy.Considering with the problem itself and the characteristics of quantum genetic algorithm,we design a new encoding method to solve the problem.Finally,the algorithm is simulated and compared with CPLEX and other heuristic algorithms:greedy algorithm(GRA),a heuristic algorithm based on conflict rules(CHA),genetic algorithm(GA).The results of the simulation show that QGA is more widely used than other algorithms,and can also obtain a higher quality and more stable feasible solution.