带预估选择的Memetic算法求解多星测控资源调度问题  

A Memetic Algorithm with Predictive Selection for Multi-Satellite TT&C Resources Scheduling Problems

作　　者：张雁[1] 党群[1] 黄永宣[1] 

机构地区：[1]西安交通大学系统工程研究所,西安710049

出　　处：《西安交通大学学报》2009年第10期37-41,共5页Journal of Xi'an Jiaotong University

基　　金：国家自然科学基金资助项目(60875043)

摘　　要：针对当前多星航天测控资源调度系统模型描述复杂、求解算法不适合大型算例的问题,利用系统约束条件的二元化特点建立了多星测控资源调度系统在一类特殊图上的最大独立集模型,进而针对该模型解空间结构多峰密布、欺骗性强的问题,提出了一种带预估选择机制的改进型Memetic算法.在分析交叉操作可达域的基础上,设计了一种能快速预估交叉操作最大收益的预估算子,通过预估运算,每个个体从几个待选交叉对象中可选择出最有利的一个对象,以在有希望区域间实现搜索的转移.大型Benchmark算例上的仿真结果表明,所提预估选择机制能减弱原模型欺骗性的影响,使Memetic算法的性能平均提高了17%.Focusing on the problems that the model description of the multi-satellite spacecraft tracking, telemetry and command （TT＆C） resources scheduling systems are commonly complicated and that the existing solution algorithms are usually not appropriate to large scale instances, the multi-satellite TT＆C resources scheduling system is converted into a maximum independent set （MIS） problem in a special class of graphs by exploiting the binary-structure of the system constraints. Then a new Memetic algorithm with predictive selection is proposed to solve the strong deceptive problem that comes from highly multi-peak distributed structure of the MIS. An efficient and fast predictive operator is designed based on the analysis of the reachable domains. The operator can predict the maximum accessible profit of the crossover operation with different objects, and selects the best crossover object from several candidate ones, thereby searches for promising solutions. Simulation results on large scale benchmark graphs show that, the predictive selection strategy reduces effects of the deceptive problem and that the performance of Memetic algorithm is improved at an average of 17%.

关 键 词：航天测控 资源调度 最大独立集 MEMETIC算法 

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]