（信息与通信工程专业论文）卫星任务规划算法综合评价技术研究.pdf

国防科学技术大学研究生院硕士学位论文 摘要 卫星通过星载传感器从太空获取地面影像数据，已经成为勘测和研究地球资 源的重要手段。为了更好地利用现有卫星资源，发挥其最大综合效益，近年来， 已经有多种规划算法应用于卫星任务规划领域，取得了一定的实际成果。面对众 多规划算法，在进行卫星任务规划时，如何综合评价、科学选择算法是一个急待 解决的问题。此外，随着航天事业的发展，实际应用不断变化，也对规划算法的 进一步扩展提出了更高的要求。 目前，已有学者对现有卫星任务规划算法的性能进行了比较和评价，具有一 定的参考价值。但是，由于缺乏标准的测试数据和统一的评价指标，也没有形成 规范的评价方法，这些比较和评价工作并不能直接指导具体规划时的算法选择和 后续的算法扩展。因此，深入研究卫星任务规划算法综合评价技术，是卫星任务 规划领域进一步发展的客观要求，具有十分重要的理论和实际意义。 为此，本文对算例自动生成、算法评价指标、综合评价方法等关键技术进行 了研究，设计实现了一个卫星任务规划算法综合评价方案。论文主要的研究内容 和创新点如下： 1 、在对卫星任务规划问题进行深入分析的基础上，指出现有算法比较评价工 作的局限性，进而提出新的卫星任务规划算法综合评价方案。 2 、系统地考察了大量卫星观测目标的真实历史数据，依靠成熟的统计学理论， 建立了卫星观测目标模型。并以此为基础，根据不同的评价目的，自动生成对应 类型的卫星规划任务作为测试算例。 3 、对任务规划算法的各方面性能进行抽象，形成了相应的评价指标。基于 a h p 算法思想，将任务规划算法评价指标进行层次分解，建立了一个高可扩展评 价指标体系，并对其合理性、冗余性、完整性进行了充分讨论。 4 、综合主客观两方面经验和知识，建立了科学的综合评价方法，对单个评价 指标值进行综合，形成算法评价结论。利用上述评价结论，基于粗糙集理论，实 现了算法自动选择，给出了卫星任务规划算法进一步发展的可行方向。 5 、基于本文提出的综合评价方案，设计实现了任务规划算法评价管理系统， 对现有规划算法进行综合评价与管理。所得评价结论直接应用于实际运行的卫星 地面指挥系统，指导了具体规划时的算法选择，并为后续的算法扩展提供了依据。 主题词：卫星任务规划算法、综合评价、算例自动生成、评价指标体系 第i 页 国防科学技术大学研究生院硕士学位论文 a b s t r a c t s a t e l l i t e so b t a i nt h ee a r t h si m a g ed a t af r o ms p a c et h r o u g ho n - b o a r ds e n s o r s ， w h i c hh a sb e c o m ea l li m p o r t a n tm e a n so fi n v e s t i g a t i n ga n dr e s e a r c h i n gt h ee a r t h s r e s o u r c e s i nr e c e n ty e a r s ，i no r d e rt om a k eb e r e ru s eo ft h ee x i s t i n gs a t e l l i t er e s o u r c e s ， v a r i o u sa l g o r i t h m sh a v eb e e np r o p o s e da n da p p l i e di ns a t e l l i t em i s s i o ns c h e d u l i n g ， w h i c ha c h i e v e ds o m ef r u i t f u lr e s u l t s w h e ns c h e d u l i n g ，i nf a c eo fa l lt h e s ea l g o r i t h m s ， h o wt oc o m p r e h e n s i v e l ye v a l u a t ea n d r e a s o n a b l yc h o o s et h e mh a sb e c o m i n gap r e s s i n g p r o b l e m i na d d i t i o n ，a st h ea e r o s p a c ei n d u s t r yd e v e l o p s ，t h ep r a c t i c a la p p l i c a t i o n s c h a n g ec o n s t a n t l y ，w h i c h s e t sah i g h e rd e m a n dt ot h ef u r t h e re x t e n s i o no ft h e s c h e d u l i n ga l g o r i t h m s a tp r e s e n t , s o m er e s e a r c h e r sh a v ed o n eal o to fw o r ki nc o m p a r i n ga n de v a l u a t i n g t h ep e r f o r m a n c eo ft h ee x i s t i n gs a t e l l i t es c h e d u l i n ga l g o r i t h m s ，w h i c ht os o m ee x t e n ti s m e a n i n g f u l b u t , d u et ot h el a c ko fs t a n d a r dt e s td a t a ，u n i f i e dm e a s u r e m e n t sa n d s c i e n t i f i ce v a l u a t i o nm e t h o d s ，t h ee x i s t i n gc o m p a r i s o na n de v a l u a t i o nc o u l dn o t d i r e c t l yg u i d es e l e c t i n ga l g o r i t h m sw h i l es c h e d u l i n ga n de x t e n d i n gt h e mf o r w a r d a sa r e s u l t , t od e e p l ys t u d yt h ec o m p r e h e n s i v ee v a l u a t i o nt e c h n o l o g yo fs a t e l l i t em i s s i o n s c h e d u l i n ga l g o r i t h m si st h eo b j e c t i v ed e m a n do fs c i e n t i f i cd e v e l o p m e n to ns a t e l l i t e m i s s i o ns c h e d u l i n g ，w h i c hh a sg r e a tt h e o r e t i c a la n dp r a c t i c a ls i g n i f i c a n c e ， t ot h i se n d ，t h i st h e s i ss t u d i e dt h ek e yt e c h n o l o g i e si ne x a m p l ea u t o m a t i c g e n e r a t i o n , m e a s u r e m e n t sa r c h i t e c t u r e ， c o m p r e h e n s i v ee v a l u a t i o n , a n db u i l ta c o m p r e h e n s i v ee v a l u a t i o ns c h e m eo f s a t e u i t em i s s i o ns c h e d u l i n ga l g o r i t h m s n 坞m a i n w o r ka n di r m o v a f i o i l sa r e 嬲f o l l o w s ： 1 b a s e do nd e e pa n a l y s i so ft h es a t e l l i t em i s s i o ns c h e d u l i n gp r o b l e m ，t h e l i m i t a t i o n so fe x i s t i n gc o m p a r i s o na n de v a l u a t i o nw e r ep o i n t e do u t ，a n dt h e n , a c o m p r e h e n s i v ee v a l u a t i o ns c h e m ew a sp u tf o r w a r d 2 a f t e rr e s e a r c h e dag r e a td e a lo fr e a ls a t e l l i t eo b s e r v i n gt a r g e t s ，t h e s a t e l l i t e o b s e r v i n gt a r g e tm o d e l w a sb u i l tu n d e rt h em a t u r es t a t i s t i c st h e o r y b a s e do nt h i s m o d e l ，s a t e l l i t eo b s e r v i n gt a r g e t s ，i e t h et e s te x a m p l e s ，c o u l db ea u t o m a t i cg e n e r a t e d a c c o r d i n gt od i f f e r e n te v a l u a t i o np u r p o s e s 3 w i 血v a r i o u sa s p e c t so fa l g o r i t h m sp e r f o r m a n c ea b s t r a c t e d ，t h ec o r r e s p o n d i n g e v a l u a t i o nm e a s u r e m e n t sw e r ef o r m e d t h e n ，a c c o r d i n gt ot h e 址口a l g o r i t h m ，t h e s e e v a l u a t i o nm e a s u r e m e n t sw e r ed i v i d e di n t od i f f e r e n tl e v e l s ，a n dah i g h - s c a l a b l e e v a l u a t i o nm e a s u r e m e n t sa r c h i t e c t u r ew a sb u i l t ，w i t hi t sr a t i o n a l i t y ，r e d u n d a n c y ，a n d i n t e g r i t yt h o r o u g h l yd i s c u s s e d 4 c o n s i d e r i n gb o t hs u b j e c t i v ea n do b j e c t i v ee x p e r i e n c ea n dk n o w l e d g e ，t h e s c i e n t i f i c c o m p r e h e n s i v e m e t h o d sw e r ep u tf o r w a r d ，t h r o u g hw h i c ht h es i n g l e m e a s u r e m e n t sw e r es y n t h e s i z e d ，a n dt h ee v a l u a t i o nc o n c l u s i o nw a sf o r m e d a c c o r d i n g 第i i 页 国防科学技术大学研究生院硕士学位论文 t ot h ec o n c l u s i o n sa b o v e ，a l g o r i t h ma u t o m a t i cs e l e c t i o n ，b a s e do nr o u g hse tt h e o r y ， w i l l si m p l e m e n t e d ，a n dt h ep o s s i b l ee x t e n d i n gd i r e c t i o nw a sp o i l l t e do u t 5 b a s e do nt h ec o m p r e h e n s i v ee v a l u a t i o ns c h e m e ，am i s s i o ns c h e d u l i l l ga l g o r i t h m e v a l u a t i o n m a n a g e m e n ts y s t e mw a si m p l e m e n t e d n l ee v a l u a t i o nc o n c l u s i o n sg a i n e d b yt h i ss y s t e mc o u l db ed i r e c t l ye m p l o y e di ns e l e c t i n ga l g o r i t h m sw h i l es c h e d u l i n ga n d e x t e n d i n ga l g o r i t h m si nt h ef u t u r e k e yw o r d s s a t e l l i t em i s s i o ns c h e d u l i n ga l g o r i t h m ；c o m p r e h e n s i v ee v a l u a t i o n ； e x a m p l e sa u t o m a t i cg e n e r a t i o n ；e v a l u a t i o nm e a s u r e m e n t sa r c h i t e c t u r e 国防科学技术大学研究生院硕士学位论文 表目录 表3 1 经验分布表1 7 表3 2 卫星观测目标数据2 8 表4 1 指标比较的标度定义。4 1 表4 2 平均随机一致性指标表4 2 表4 3 测试数据5 0 表4 4 算法1 评价结果表。5 0 表4 5 算法2 评价结果表5 0 表4 6 现有综合规划算法评价结论5 2 表4 7 现有动态调整算法评价结论5 2 第页 国防科学技术大学研究生院硕士学位论文 图目录 图2 1 卫星观测过程 7 图2 2 卫星任务规划算法综合评价方案示意图1 2 图3 。1 基于时间轴生成算例界面。2 1 图3 2 动态调整算例生成界面2 2 图3 3 算法服务软件架构图2 3 图3 4 算法服务通信过程图2 4 图3 5 卫星观测目标规划结果。2 9 图4 1 卫星任务规划算法评价指标集31 图4 2 基于蚯口算法的高可扩展框架3 5 图4 3 评价指标值4 8 图4 4 任务优先综合评价指标集一4 9 图4 5 综合评价值51 图5 1 任务规划算法评价管理系统业务流程图。5 4 图5 2 任务规划算法评价管理系统组成图5 5 图5 3 评价主流程界面_ 。5 8 图5 4 评价管理界面。5 8 图5 5 任务规划算法库界面：。5 9 第v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文题目：里星堡垒拯到簋洼绫佥：翌俭盐盔狃窥 学位论文作者签名： 篮交盘 日期：加d 8 年1 1 月，日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：里星堡垒拯划簋洼绽企迁盆拉盔盟窥 学位论文作者签名：燃日期：上叩凸年，月，多日 作者指导教师签名：垄；至日期：。h 谚年月日 国防科学技术大学研究生院硕士学位论文 第一章绪论 1 , 1 课题研究背景 对地观测卫星从太空获取地面影像数据，具有覆盖区域广、持续时间长、不 受空域国界限制等独特的优势。随着经济的发展和科技的进步，人们对各类地球 遥感信息的需求不断扩大。越来越多的国家和地区对观测卫星有较强烈的需求， 也期望借助卫星项目带动自身航天技术的发展，开始竞相发展自己的卫星【l 】。 对地观测卫星在一定高度的轨道高速飞行，在其能够扫描到的区域内有很多 目标都可能被观测。由于每个目标都具有一定的观测时间窗口长度，而星载设备 也必须满足自身约束条件，所以，对地观测卫星不可能在一次规划时间范围内完 成所有观测需求。为了缓解这种供求矛盾，必须对卫星任务进行规划。卫星任务 规划具体是指：在综合考虑观测资源约束和用户观测需求的基础上，将观测资源 分配给相互竞争的多个任务，最大限度地满足用户观测需求【l j 。 卫星任务规划是一个复杂的问题，构建问题分析模型需要首先考察实际应用 需求，对不同卫星的观测约束条件进行抽象，在此基础上分析约束条件间的关系， 然后进行问题的描述。由于各国对地观测卫星系统性能指标( 如控制精度、控制 方式及存储特性等) 及其工作模式各不相同，卫星的约束条件区别较大，据此产 生了多种不同类型的任务规划模型，目前主要有：数学规划模型【2 】【3 】，约束满足模 型 4 1 ，序列决策模型 5 1 ，图模型【6 l ，通用问题模型 7 1 等。 ， 1 ： 基于上述模型，卫星任务规划算法也各不相同。其中较具代表性的包括：禁 忌搜索算法 7 1 、分枝定界算法【引、多目标遗传算法【9 】、贪婪算法f l o 】、标记更新算法 等，取得了一定的实际成果。由于卫星任务规划问题的复杂度较高，近似算法 逐渐成为任务规划问题求解的主要方法；而精确算法在观测任务较多时效率相对 较低，一般只适于小规模问题或经过分解的子问题。 然而，面对众多的规划算法，仅仅进行简单的分类和比较并不能在实际规划 过程中指导具体算法的选择，也难以指出算法迸一步发展的可行方向。因此，深 入研究卫星任务规划问题，对各类规划算法进行科学的评价，已经成为学者们积 极探索盼一个问题。 “综合评价 作为系统工程学科的重要组成部分，能够对多属性体系结构描 述的对象系统做出全局性、整体性的评价，已经广泛应用于经济学、管理科学、 绩效评价等领域，对卫星任务规划算法的评价工作具有很好的借鉴意义。目前较 为成熟的综合评价方法有【1 2 】：d e l p h i 法，主成分分析法，层次分析法，模糊综合 评价法，人工智能评价法和信息熵法等。 第1 页 国防科学技术大学研究生院硕士学位论文 1 2 课题研究现状 目前，对卫星任务规划问题的研究正处于快速发展阶段，问题建模、规划算 法等方面均有新的理论和实践成果不断涌现。而卫星任务规划算法综合评价技术 的研究则相对较少，可供检索的资料也不多，其理论模型和评价方法的研究尚不 完善，发展前景十分广阔。 1 2 1 规划算法研究 近年来，已经有多种规划算法应用于卫星任务规划领域。从计算结果考虑， 这些算法可以分为精确算法和近似算法两类。 精确算法的目的是求得问题的最优解或者最优解集，一般用于观测任务数较 少、问题规模小的情况或是用来求解经分解后的子问题。目前较具代表性的精确 算法有： v e r f a i l l i e t 8 】等在值约束满足模型( v c s p ) 的基础上提出了r u s s i a nd o l ls e a r c h 算法，其主要思想类似于分枝定界法：将一个搜索分解成连续的，多嵌套的子问 题，保留每次子问题的搜索结果，用这些结果来调整较大嵌套问题的下界，从而 达到提高搜索速度的目的。 g a b r e l t l l 】在成像约束的有向无圈图的基础上，应用标记校正的思想求取多目标 条件成像路径，并进行决策选择，用来解决s p o t 5 卫星的任务规划问题。张帆【6 j 同样在有向无圈图模型的基础上，提出了基于最早生成优先策略和基于侧视角度 最小优先策略的多目标最短路径算法。由于g a b r e l 和张帆的方法都没有考虑到开 关机时间约束对有向图的拓扑结构的影响，因而不能得到实际问题的多目标优化 解集。 h a r r i s o n b 3 】使用穷尽搜索的思想求解规模较小的任务规划问题。a b r a m s o n 1 4 】 采用整数线性规划法解决小型成像卫星的实时任务规划问题。m a n c e l l l 5 j 在整数线 性规划模型基础上，采用列生成算法解决灵巧卫星任务规划问题。 近似算法是指那些并不保证得到问题的最优解或最优解集的算法，其主要目 的是搜索可有效计算的优化结果。由于卫星任务规划问题的复杂性，目前，较多 的研究工作集中于近似算法上： w e i c h e n gl i n 1 6 】利用拉格朗日松弛法及线性规划技术产生近似优化的任务规 划方案。 v a s q u e z 及h a o 7 】使用禁忌搜索算法对相应的背包问题模型进行求解。贺仁杰 【l 刀针对提出的问题分析模型给出了相应的禁忌搜索算法； p e m b e r t o n 1 s 提出了一种基于动态规划思想的迭代求解方法。他的基本思想是 第2 页 国防科学技术大学研究生院硕士学位论文 首先按照某种规则对所有观测目标排序并分组，然后按分组顺序对每组中的观测 目标都采用完全算法求得最优解。在规划过程中，前面分组的规划结果将作为后 面分组规划的约束条件。h a l l 1 9 j 等采用动态规划思想确定最长路径问题的上下界。 l e m a i t r e 4 】使用约束规划方法和局部搜索算法实施任务规划。s h e r w o o d 2 0 】等人 在用于e o 1 卫星的a s p e n ( a u t o m a t e ds c h e d u l i n ga n dp l a n n i n ge n v i r o n m e n t ) 系 统中采用了一种基于局部搜索的算法，首先生成一个初始规划方案，然后通过调 整变量取值进行冲突消解，直到获得可行规划方案。 m u r a o k a b o 等在a s t e r 规划系统中，采用贪婪算法求解对地观测卫星规划问 题，每次都选取重要等级最高的观测目标，如果该目标不能进行安排，则选取下 一个观测目标。p o t t e r 2 l j 等人在l a n d s a t 7 卫星规划系统中以观测任务的重要等级为 依据，使用贪婪思想安排观测任务。 美国国家航空航天局针对多颗卫星及小卫星群开发了多个原型及实用系统【9 】， 系统中使用了遗传算法等近似算法。张帆【6 1 用进化算法求解多目标优化路径进行任 务规划。王钧【2 2 j 根据卫星的成像约束条件建立了多目标任务调度模型，并在此基 础上采用遗传算法进行规划。 1 2 2 算法性能比较与评价 由于实际应用中任务规划的方法众多，很多学者对这些方法的性能进行了比 较分析。 w o l f e 和s o r e n s e n l 2 3 比较了三种不同算法，即贪婪算法、具有前看( 1 0 0 k a h e a d ) 功能的贪婪算法以及遗传算法。在贪婪算法中，所有观测目标按照主要等级进行 排序，然后按顺序依次选择，根据约束条件安排最佳成像时刻。具有前看功能的 贪婪算法在选择下一个观测任务时考虑到了对其他观测任务的影响。遗传算法中 定义了相应的交叉、变异算子，允许撤销已经安排的观测任务，从而得到一个较 好的规划方案。实验表明，当问题规模较大时遗传算法取得的规划效果最好。 b e n s a n a 等人p j 基于值约束满足问题模型比较了完全搜索算法( 深度优先搜索、 动态规划、r u s s i a nd o l ls e a r c h ) 和近似搜索算法( 贪婪搜索、禁忌搜索) 在不同 问题规模情况下的性能。实验证明，完全搜索算法可用于求解小规模问题的最优 解，而禁忌搜索可以在合理的时间内得到较大规模问题的一个满意解。 v a s q u e l 7 基于多背包问题模型比较了完全搜索算法( 分枝定界算法) 、近似搜 索算法( 伪随机算法、贪婪搜索、禁忌搜索) ，在实验结论中认为分枝定界算法 在小规模问题上最优，而禁忌搜索在较大规模问题上的性能优于其他几类算法。 v e r f a i l l i e l 2 4 1 针对灵巧成像卫星任务规划问题，比较了贪婪算法( g r e e d y a l g o r i t h m ) 、动态规划算法( d y n a m i cp r o g r a m m i n ga l g o r i t h m ) 、约束规划算法 第3 页 国防科学技术大学研究生院硕士学位论文 ( c o n s t r a i n tp r o g r a m m i n ga p p r o a c h ) 、局部搜索算法( l o c a ls e a r c ha l g o r i t h m ) 四 种方法，在其结论中认为动态规划算法在线性约束条件下效果较好，而局部搜索 算法在非线性约束条件下效果较好。 g l o b u s t 9 】针对多颗成像卫星任务规划的十个实际问题，比较了随机爬山算法 ( s t o c h a s t i cc l i m b i n gh i l l ) 、模拟退火算法( s i m u l a t e da n n e a l i n g ) 、遗传算法 ( g e n e t i ca l g o r i t h m ) 、随机采样算法( i t e r a t e ds a m p l i n g ) 、吱呀轮算法( s q u e a k y 帆e e l ) 五类方法，在其结论中认为模拟退火算法的效果较好。 1 - 2 3 现有研究的特点与不足 根据上述总结的研究现状来看，任务规划问题相关研究的特点如下： 1 、由于各国独立开发专属的对地观测卫星规划系统，其规划问题的实际与具 体的星载观测设备紧密相关，卫星观测约束条件也有较大区别，也因此产生了多 种类型的任务规划模型及算法。 2 、由于对地观测卫星任务规划问题的复杂性，使得近似算法成为对地观测卫 星任务规划问题求解的主要方法，如贪婪算法、遗传算法、禁忌搜索算法等；而 精确算法在观测目标数目众多时资源占用率大，效率低下，计算时间长，一般只 适用于小规模问题。 基于上述情况，目前已有的算法比较、评价工作基本上都遵循下述思路： 1 、首先结合本国卫星的固有特性抽象出观测约束条件，建立任务规划模型； 2 、然后，对于特定问题模型，采用各种规划算法进行求解。并针对算法性能 的某几个方面建立优化目标函数。 3 、最后比较算法规划结果，计算优化目标函数值，得出结论。 现有研究的不足之处如下： 1 、在不影响结果正确性的前提下，现有模型往往对卫星任务规划问题及约束 条件进行一定的简化，以降低模型复杂程度。但我国系列卫星的观测约束条件繁 多、约束关系复杂，许多约束不能简化考虑，因此基于现有模型产生的测试算例 不具备通用性。 2 现有研究对任务规划结果一般都只采用单目标评价函数，或者求解多个目标 的加权和，将其转化成单目标评价。没有形成统一的评价指标和规范的评价方法， 可能导致结果中多目标信息的丢失。 3 、目前尚未有成形的算法评价专用系统问世，由于问题建模、算法设计及实 现、工具应用、实验计算等过程中可能出现误差，个体的规划实验难以重现。可 见，已有的算法比较分析结果并不能作为普适的结论，也就不能直接指导具体规 划时的算法选择和后续的算法扩展工作。 第4 页 国防科学技术大学研究生院硕士学位论文 1 3 论文的研究意义、研究内容与组织结构 i 3 1 论文的研究意义 卫星任务规划涉及到多种规划算法，论文尝试通过建立和管理多种条件下的 测试算例集和算法评价指标库，采用科学的综合评价方法，对这些算法进行定量 和定性评价。上述工作的成果可以用于界定各类规划算法的适用范围，在卫星任 务规划过程中指导规划算法的选择，并为日后的算法扩展提供参考依据。对各类 算法进行科学的综合评价，克服了现有比较评价方法的局限性，具有非常重要的 学术价值及实际意义。 1 3 2 论文的研究内容 l 、针对现有算法比较、分析工作的不足，提出了一套新的卫星任务规划算法 综合评价方案。即首先建立可重用的测试算例库和高可扩展的算法评价指标体系， 然后调用规划算法库中的具体算法对指定算例进行规划，最后比较分析测试算例 和规划结果，计算评价指标集中的各个指标值，并依靠科学的综合评价方法形成 评价结论。 2 、针对卫星规划问题实际，系统地考察了大量卫星观测目标的真实历史数据， 依靠成熟的数理统计理论，建立卫星观测目标模型。并以此为基础，根据不同的 评价目的，自动生成对应类型的卫星任务，作为测试算例，存放于测试算例库中。 3 、对任务规划算法的各方面性能进行抽象，形成相应的评价指标。基于a h p 算法思想，将任务规划算法的评价指标进行层次分解，建立了一个高可扩展评价 指标体系，并对其合理性、冗余性、完整性进行讨论。 4 、综合主客观两方面经验和知识，建立科学的综合评价方法，对单个评价指 标值进行综合，形成算法评价结论。利用上述评价结论，基于粗糙集理论，实现 算法自动选择，给出卫星任务规划算法进一步发展的可行方向。 5 、基于本文提出的综合评价方案，针对当前广泛应用的卫星任务规划算法， 设计实现任务规划算法评价管理系统，介绍主要功能模块的关键技术实现。 1 3 3 论文的组织结构 第一章，绪论。首先介绍论文的研究背景与国内外研究现状，然后介绍了论 文的研究意义、研究内容与组织结构。 第二章，卫星任务规划算法综合评价的问题分析与总体设计。分析了卫星任 务规划算法综合评价问题，提出了套卫星任务规划算法综合评价方案，并介绍 第5 页 国防科学技术大学研究生院硕士学位论文 了据此方案形成的卫星任务规划算法综合评价总体框架。 第三章，算法规划测试。建立了卫星观测目标模型，并以此为基础，介绍了 生成算例的几种不同方式。最后描述了算法服务及任务规划算法库的实现。 第四章，规划结果评价。给出了基于a h p 层次结构的高可扩展评价指标体系， 建立了两类科学的综合评价方法。最后，作为算法评价结论的应用，描述了基于 粗糙集的算法自动选择技术以及算法扩展的可行方向。 第五章，任务规划算法评价管理系统。在实际运行的卫星任务规划系统中， 设计实现了任务规划算法评价管理系统，并介绍了系统的主要功能模块及关键技 术实现。 第六章，总结与展望。总结全文的主要工作和研究成果，并指出进一步研究 方向。 第6 页 国舫科学技术大学研究生院硕士学位论文 第二章卫星任务规划算法综合评价的问题分析与总体设计 近年来，已经有多种规划算法应用于卫星任务规划领域。然而，由于各个规 划算法的自身特性不同，针对多种类型的任务规划问题，如何选择合适的任务规 划算法至关重要。此外，随着航天工业的向前发展，任务规划问题不断复杂化， 如何发现并克服现有算法的缺陷，如何根据规划需要开发新的算法，成为了卫星 任务规划领域另一个急待解决的问题。 为此，本章介绍了卫星观测过程，研究了卫星任务规划问题及算法。并以此 为基础，分析了卫星任务规划算法综合评价问题，提出了卫星任务规划算法综合 评价的总体设计。 2 1 卫星任务规划问题及算法 2 11 卫星观测过程溉述 对地观测卫星运行于特定轨道上，其观测活动大致包含三项内容，如下图： 1 、数据获取：卫星通过星载传感器获取目标图像信息，并将观测数据记录在 存储介质上。 2 、数据传输：卫星通过无线传输方式，将观测数据实时或延时发送至地面站。 3 、数据处理：相关人员获得观测数据后，经过加工处理从中获取各种信息。 鼍 畏 一雷泛 ，中一一专l ，7 7 j 釜：、 图2 l 卫星观测过程 为了提高分辨率，便于图像判读和目标识别，对地观测卫星一般都运行于近 地极回归或准回归低轨道上，根据轨道根数的不同，可以观测一定的地面区域。 卫星对地面的覆盖情况直接影响着对地观测卫星对目标的可视程度，卫星离 地面越高则观测区越大，有利于覆盖更多地面目标。但是，考虑到分辨率因素， 特别是对于可见光和红外相机成像卫星来说，轨道高度越低则受气象、光照影响 因素越小分辨率就越高，更有利于图像的后期处理和信息提取。 第7 页 国防科学技术大学研究生院硕士学位论文 2 1 2 卫星任务规划问题 对地观测卫星在一定的轨道高度高速飞行，只有在其卫星扫描条带内的目标 才可能被观测。而每个目标都具有一定的观测时间窗口长度，星载设备也受到自 身姿态调整能力、存储器容量等约束条件的限制，所以，对地观测卫星不可能在 一次规划时间范围内完成所有观测需求。 这就要求对卫星任务进行规划，尽可能提高卫星观测的综合效益。具体而言， 就是针对观测任务数据，综合考虑卫星、地面站的规划资源约束，生成卫星观测 方案和地面站接收方案。 基于观测任务和约束条件的分析，总结当前卫星任务规划问题特点如下【2 2 】： 1 、所有待处理观测任务在规划前已经确定，不考虑观测任务集的动态变化； 2 、任意时刻，一颗对地观测卫星只处理一个任务； 3 、只考虑点目标观测任务，即每个任务仅代表一个点目标。如果是大范围的 区域观测任务，则先按照一定原则将其分解为多个点目标； 4 、观测任务具有原子性，即一旦开始观测就必须完成： 5 、卫星进行数传时只能有一种传输状态，即回放和时传不能同时进行。 由上述分析可知，卫星任务规划问题可以归纳为：在一定的规划原则下，合 理配置卫星、地面站资源，从观测任务集合中找到一个尽可能优化的子集。反映 到数学上，是一个多目标组合优化问题( m u l t i - o b j e c t i v ec o m b i n a t o r i a lo p t i m i z a t i o n ， m o c o ) 2 6 1 2 7 】【2 8 】。 多目标组合优化是指具有n 个变量、m 个目标函数，并定义了可行解集的特 定约束条件的离散优化问题。由于多个目标函数往往相互冲突，与一般的组合优 化问题不同，m o c o 一般不存在一个在所有目标函数上都能达到最优的解。而且 相对于单目标优化，m o c o 考虑多个目标函数，问题复杂度更高，求解难度更大。 2 1 3 卫星任务规划算法 卫星任务规划，作为一个多目标组合优化问题，各个任务间存在无法比较的 同等偏好关系，一般不存在一个在所有目标函数上都能达到最优的解，即最优解 o p t i m a ls o l u t i o n ；然而，一个解可能在某个目标上性能优异，但在其他目标上评价 较差，这种解称为可行解c o n s i s t e n ts o l u t i o n l 2 9 1 。 可行解的数目往往很多，卫星任务规划算法就是要针对卫星任务规划问题， 融入领域知识、专家经验等信息，折衷考虑各个目标函数，在可行解集中搜索或 者逼近最优解。根据优化搜索的策略不同，目前主要的卫星任务规划算法可以大 致分为以下三类p o j ： 第8 页 国防科学技术大学研究生院硕士学位论文 1 、树搜索t r e es e a r c h 【j u j 树搜索是一种在问题的解空间树上搜索优化解的方法。般步骤为： ( 1 ) 选取规划任务集合中某个任务作为当前扩展结点，并产生其所有孩子结点； ( 2 ) 在产生的孩子结点中，抛弃不可能产生可行解( 或最优解) 的结点。将其 余的孩子结点加入活结点表； ( 3 ) 从活结点表中选择下一个活结点作为新的扩展结点。常用的选择方式有深 度优先和最大收益优先两类； ( 4 ) 如此循环，直到找到问题的可行解( 或最优解) 或活结点表为空。 树搜索方法寻求中小规模规划问题的最优解效率很高，广泛应用于整数线性 规划模型、约束规划模型的求解，并在所有的剪枝算法和大部分动态规划、人工 智能规划算法中使用。 2 、邻域搜索l o c a ls e a r c h 圳 邻域搜索算法在当前解的局部邻域进行搜索，逐步逼近最优解。一般步骤为： ( 1 ) 确定临近关系，即定义当前解的邻域； ( 2 ) 选取规划任务集合中的某个任务作为规划起点，即初始的部分优化解； ( 3 ) 按照一定算法遍历当前部分优化解的邻域，并从中选择一个新解加入； ( 4 ) 根据预设准则停止搜索或者最后重新开始搜索。 邻域搜索方法具有良好的精度，在多数情况下能很好的逼近最优解。但是许 多参数需要合理的设置才能使算法有效，具体实现时的困难在于将规划约束映射 到邻域选择准则上，对经验和技巧的要求比较高。根据参数设置的不同，邻域搜 索方法流行的变体主要包括禁忌搜索、模拟退火、遗传算法等。 3 、贪婪搜索g r e e d ys e a r c h 3 2 j 贪婪搜索是一种不追求最优解，只希望得到较为满意解的方法。一般步骤为： ( 1 ) 选取一种度量标准，多数情况下可以通过对多个优化目标函数进行综合得 到。按这种度量标准对所有规划任务进行排序。 ( 2 ) 选取规划任务集合中的某个任务作为规划起点，即初始的部分优化解； ( 3 ) 按照上述排序依次考查规划任务集合中的剩余任务，如果这个任务和当前 已有的部分优化解加在一起可以产生一个可行解，则将其加入这个部分优化解中。 ( 4 ) 达到预设条件时结束搜索。这个结束条件可以是规划任务集合遍历结束， 或者搜索时间限制等等。 贪婪搜索算法以当前情况为基础作最优选择，不考虑各种可能的整体情况， 从而省去了为逼近最优解要穷尽所有可能而耗费的大量时间，因此一般可以快速 得到满意的解。不同的度量标准、部分优化解起点和结束条件导致了贪婪算法的 不同变体，包括基本的贪婪算法、随机选择的重复贪婪搜索和各类启发式算法等。 第9 页 国防科学技术大学研究生院硕士学位论文 2 2 卫星任务规划算法综合评价问题分析 由上文分析可见，卫星任务规划问题已经得到了各国研究人员的广泛关注， 并在卫星任务规划算法的研制上取得了许多有价值的成果。然而，实际规划中如 何选择规划算法以及如何根据规划需要改进现有算法、开发新的算法，仍然没有 得到很好的解决。为此，需要引入系统工程科学中的“系统评价”理论【3 3 】，对卫 星任务规划算法进行综合评价。 评价( e v a l u a t i o n ) 是指“根据确定的目的来测定对象系统的属性，并将这种属性 变为客观定量的计值或者主观效用的行为”1 3 4 j 。 综合评价( c o m p r e h e n s i v ee v a l u a t i o n ) 是指“对多属性体系结构描述的对象系统 做出全局性、整体性的评价 【35 1 。即对评价对象的全体，根据所给的条件，采用 一定的方法给每个评价对象赋予一个评价值，再据此排序或择优。 由此，卫星任务规划算法综合评价可定义为：根据一定目的，考察卫星任务 规划算法的各方面性能，对其做出全局性、整体性的评价。 2 2 1 综合评价的研究对象 综合评价的研究对象是卫星任务规划算法。作为一个复杂的综合体，无法用 一个严谨的数学形式对卫星任务规划算法进行绝对完整的描述。因此，任务规划 算法综合评价所要考察的具体问题，即为具体规划时，用户普遍关心的算法性能， 主要包括以下几个方面： 1 、任务完成情况 任务完成情况是指：算法规划结果中的卫星观测方案、地面站跟踪接收方案 对实际规划任务或者测试算例中的卫星观测任务、地面站跟踪接收任务的完成程 度。规划算法应该使卫星观测获得尽可能高的综合效益。主要表现在下述几点： ( 1 ) 完成尽可能多的目标； ( 2 ) 完成重要性等级尽可能高的目标； ( 3 ) 完成目标的成像效果尽可能好。 2 、资源利用情况 资源利用情况是指：算法规划结果中的卫星观测方案、地面站跟踪接收