Research On Genetic Algorithm For Multi-Satellite TT&C Scheduling Problem

The scheduling of multi-satellite Tracking Telemetry and Command (TT&C) is to make the best satisfaction of TT&C task requirements of satellites by appropriately distributing TT&C resource from space and ground. The multi-satellite TT&C scheduling is a mass combinatorial optimization problem with complex constraints, such as multi-time windows. This problem relates to many elements and the relations between elements are complex. The deep research of integrated scheduling of TT&C resource not only provides scheduling alternatives and evaluation results for engineering application, but also explores and analyzes scheduling algorithm, and further improves algorithm performance. This dissertation puts forward the Genetic Algorithm (GA) framework and studies the related GA methods for integrated scheduling of TT&C resource. The main work and creation go as follows:On the aspect of model, the orbit measure and orbit holding requirements of middle and high satellites were analyzed, then according to the task requirement describing of low satellites, the normalized requirements description of all types of satellites was proposed. Following the performance constraints of TT&C resource from space and ground, the integrated scheduling model was established, with the objective of maximizing the weight summation satisfaction rate, and then the scheduling strategy models of TT&C resource were formulated.GA is a random search algorithm that searchs through the total space. Its applications in many areas similar to TT&C have acquired good effects. Because the multi-satellite TT&C scheduling problem has huge solution space and is difficult to solve, whereas the solving performance of GA is determined by search strategy, so the dissertation firstly studies the solving strategy and then elicits the solving framework. GA can implement large scale global search through the solution space and also can implement particular local search through part of the solution space. In theory, the global search can find the optimal solution, but because of the huge search space it calls for a better technique to carry out the algorithm. Oppositely, though the local search may not ensure to find the optimal solution, it can search particularly through the crucial area and steadily find the satisfactory or even the optimal solution. Both of the two strategies have their own advantages. So this dissertation puts forward the solving framework based on global and local strategy of GA and designs common components of them.On the aspect of global solving algorithm, for the random GA, because the huge search space it easily leads to a slow speed of convergence and a long time of solution, and prones to get into local optimization. To account for the weakness of simple genetic algorithm solving which prones to get into local optimization and instability, absorbing the characteristics of Scatter Search that samples diversified and optimizes locally, a hybridized genetic algorithm based on scatter search was proposed, embedding the global directed search in the global stochastic search. After problem was described, representation of feasible solution was designed which was convenient for searching roundly, then the process of algorithm was constructed, and the main elements of algorithm were presented, which included diversification generator controlled by input parameters, reference set generating and updating method based on quality and diversification principle, the combination method drawing on the good components of combination solutions, and the improvement method based on heuristic local searching. All usable time section encoding was designed to engage fine-grained searching. To overcome the difficulties of long chromosome and weak correlation between genes, a directed crossover operator based on local path relining was designed which was based on the idea of Path Re-linking, difference between Initial Solution and Guiding Solution was applied to construct the layering neighborhood of Initial Solution, and then the solution in the neighborhood that met the constraints of model became the crossing result. Considering reducing the calculating time, a two-stage successive genetic algorithm was put forwards. Whereas the model's object function was somewhat time separable and local part of the scheduling alternatives can be ideally hypothesized, the scheduled time windows were separated to two sections, after the population from first section was evolved, the gained optimized solution was combined with the second section, and then the evolution of the second phase goes further.On the aspect of local solving algorithm, it tries to minish the loss of better solution while minishing the search scale and ensures the stability of the algorithm. According to the characteristic of the problem, this dissertation proposes the scheduling algorithm based on cooperative co-evolution. In order to achieve the above purpose, enhancing the cooperation is the key and difficult point of algorithm design. Considering that adopting the traditional methods of best selection and random selection may make the scheduling algorithm instable, the methods for representation selection and the corresponding fitness computing are suggested. For the balance of representation cooperation and time spending, the method takes advantage of the idea of orthogonal design, selects three representations in each child population according to the degree of greediness, and computes individual fitness by orthogonal table. Representation individuals'cooperation of all child populations is used to drive the evolution of whole population in current cooperative co-evolution algorithm, and the local cooperative information used in the process is little. This dissertation made some improvements to the cooperative co-evolution for multi-satellite TT&C scheduling, which emphasized the local interaction function under global cooperation. A performance index for individual—Local Interaction Value(LIV) was proposed, which indicated its cooperative effectiveness with its neighbor populations, and took LIV as one of the measures of individual quality in the selection operation. For improving the mutation self-adaptation, the difference between LIV and sum of all child finesses was taken to determine the mutation probability. Above improvements can reduce the loss of excellent individuals due to the non-global characteristic of delegate individuals.Finally, we verify the algorithm performance and the effect of improvements by the calculating case. Results indicate that both genetic evolution strategies can find the high quality solution for various scale problems. Comparing with the two-stage successive evolution, the cooperative co-evolution can more stably acquire better solution in the price of spending more time. Combining to use the two algorithms can satisfy requirements of multi-satellite TT&C scheduling with different solution quality and solving time.