Multi-satellite control resource scheduling based on ant colony optimization

摘要

The multi-satellite control resource scheduling problem (MSCRSP) is a kind of large-scale combinatorial optimization problem. As the solution space of the problem is sparse, the optimization process is very complicated. Ant colony optimization as one of heuristic method is wildly used by other researchers to solve many practical problems. An algorithm of multi-satellite control resource scheduling problem based on ant colony optimization (MSCRSP-ACO) is presented in this paper. The main idea of MSCRSP-ACO is that pheromone trail update by two stages to avoid algorithm trapping into local optima. The main procedures of this algorithm contain three processes. Firstly, the data get by satellite control center should be preprocessed according to visible arcs. Secondly, aiming to minimize the working burden as optimization objective, the optimization model of MSCRSP, called complex independent set model (C1SM), is developed based on visible arcs and working periods. Ant colony algorithm can be used directly to solve CISM. Lastly, a novel ant colony algorithm, called MSCRSP-ACO, is applied to CISM. From the definition of pheromone and heuristic information to the updating strategy of pheromone is described detailed. The effect of parameters on the algorithm performance is also studied by experimental method. The experiment results demonstrate that the global exploration ability and solution quality of the MSCRSP-ACO is superior to existed algorithms such as genetic algorithm, iterative repair algorithm and max-min ant system.