【作者】 陈峰；

【导师】 武小悦；

【作者基本信息】 国防科学技术大学 ， 控制科学与工程， 2010， 博士

【摘要】 多星测控调度是指对高中低轨等各类卫星合理地分配天地基测控资源以满足卫星的测控任务需求。多星测控调度问题是一个具有多时间窗口等复杂约束的大规模组合优化问题,涉及要素多且关系复杂,对其进行深入研究不仅可以为工程应用提供调度方案和方案评价结果,还可以对调度算法进行探索和分析,并在此基础上改进算法性能。本文针对多星测控调度问题的遗传算法框架,研究了相关的遗传算法。主要工作和创新如下：在模型方面,借鉴低轨卫星测控调度任务需求描述方式,在对中高轨卫星的轨道测量和轨道保持等需求进行分析的基础上,给出了高中低轨任务需求规范化描述；针对天基和地基测控资源的测控特点,以卫星任务需求加权满足率最大为目标,建立了测控资源的调度模型。遗传算法是一种具有全局搜索性能的随机搜索算法,在类似于多星测控调度问题的诸多领域取得了很好的应用效果。由于多星测控调度问题的搜索空间巨大,不易求解,而搜索策略又决定遗传算法的求解性能,因此,首先对遗传算法的求解策略进行研究,并在此基础上得出求解框架。遗传算法可以对整个解空间进行大范围的全局型搜索,也可以对解空间的部分区域进行细致的局部型搜索,虽然全局型搜索原理上可以得到问题的最优解,但对算法的实现技术有较高的要求,局部型搜索虽然从原理上不能保证得到最优解,但可以对重点区域进行详细搜索,稳定地得到满意解甚至是最优解,两种策略各具优势,因此,本文提出了基于全局和局部两种搜索策略的求解框架,并对两种策略共同使用的算法组件进行了设计。在全局型求解算法方面,由于搜索空间巨大,对随机型的遗传算法而言,容易造成收敛速度慢和求解时间长,而且还易陷入局部最优。针对初始算法求解易陷入局部最优和不稳定的缺陷,借鉴分散搜索多样化采样及局部寻优的思想,在原始GA全局的随机搜索中嵌入分散搜索,对多样化初始集产生方法、参考集更新方法、解组合方法和解提高方法等分散搜索要素进行了设计。针对长染色体和基因间较弱的相关性,借鉴路径连接的思想,提出了一种基于局部路径连接的定向交叉算子,利用构成初始解和引导解的要素的差异性,构建从初始解出发的分层搜索邻域,然后将邻域中满足模型约束的解作为交叉的结果。出于减少运算时间的考虑,提出了两阶段递进遗传算法,鉴于模型的目标函数在时间上具有一定的可分性,而且可以对调度方案的局部作出理想化的假设,以时间为依据将被调度弧段划分成两个部分。在对第一部分形成种群并作进化求解的基础上,将其最优解与第二部分弧段组合,并作进一步的进化求解。在局部型求解算法方面,要求能在减小搜索范围的同时尽可能地减小优秀解的丢失,确保算法的稳定性。针对问题特点,提出了合作型协同进化调度算法,为实现上述目的,加强协同性是算法设计的关键和难点。由于采用传统的子种群代表个体最优选择和随机选择容易使求解效果不稳定,综合考虑代表个体的协同性和计算开销,依据贪婪性强弱从每个子种群选择三个代表个体,并利用正交表进行个体适应度计算。其次,针对现有合作协同进化主要通过所有子种群代表个体拼接的全局协同进行整个种群进化、较少利用局部协同信息的现象,对每个个体设定一个能表明其与所有相邻子种群合作效果的进化性能指标——局部交互值,并将该交互值作为评价个体优劣和个体进行自适应变异的尺度之一,从机理上减少由于子种群代表个体选择的非全局性而造成的优秀个体的丢失。最后通过算例对所设计算法的整体性能和所作改进的效果进行了验证,结果表明本文设计的两种遗传进化策略都可以得到各种规模问题的高质量解,其中合作协同进化相比两阶段递进进化能以较多的时间来更稳定地获取更好的解。两种求解策略结合使用能够满足不同求解质量和求解时间要求下的多星测控调度需求。更多还原

【Abstract】 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.更多还原