（控制科学与工程专业论文）基于背包模型和进化算法的多星侦察任务调度问题研究.pdf

国防科学技术大学研究生院硕j j 学位论文 摘要 随着现代战争对空间信息的依赖越来越大，使用多星组网进行侦察和监视己 成为侦察卫星发展的一种必然模式。为了充分利用卫星资源并有效满足用户需求， 多星侦察任务调度问题已成为一个迫切需要解决的问题。 本文从两个部分展开多星侦察任务调度问题的研究：模型设计与多目标优化 算法设计。在第部分中，基于标准模型的思路设计，取得通用性和兼容 牛较好 的模型；在第二部分中，基于p a r e t o 最优的概念，使用进化算法解决多目标优化 问题，最终形成了任务调度问题的解决方案。 本文的成果归纳为两个方面： l 在对成像任务进行深入分析的基础上，对约束条件进行分层，为各种约束 提出了不同的处理方式，以成像任务为“物品”，把侦察时间窗u 归结为具有多 重属性的“背包”，提出了“相容性列表”的概念来描述物品与背包的复杂对应 关系，获得了能够基本涵盖现有约束、能够适应未来技术发展的多维动态背包模 型，从而归结为一个多目标优化问题。 2 为了求解获得的多目标优化问题，在明确了p a r e t o 最优的概念以及多目标 优化问题的难点之后，重点阐述了文化算法的设计思想，把多层信念空间文化算 法应用到多维动态背包模型，基于分离设计思想设计了进化算法，形成了任务调 度问题的b a g c u l 解决方案。 仿真结果验证了所提解决方案的有效性和计算效能。本论文的成果，既为使 用标准模型研究成像侦察卫星任务调度问题提供了一种新思路，也是把文化算法 应用到多目标优化问题的一种有益尝试。 主题词：任务调度；多目标优化；进化算法；背包模型；成像侦察卫星；文 化算法 第i 页 国防科学技术大学研究生院硕士学位论文 a b s t r a c t a sm o d e mw a r ss h o wi n c r e a s i n gd e p e n d e n c eo ns p a c ei n f o r m a t i o n ，i th a sb e c o m e n e c e s s a r yt ou s es a t e l l i t eg r o u p i n gi no b s e r v a t i o na n dd e t e c t i o nw h e nd e v e l o p i n g r e c o n n a i s s a n c es a t e l l i t e s a i m i n ga te f f i c i e n tu s a g eo fs a t e l l i t er e s o u r c e sa n ds a t i s f a c t i o n f o ru s e r s d e m a n d s ， m u l t i - s a t e l l i t eo b s e r v a t i o nt a s k s c h e d u l i n g ( m s o t s ) h a s b e c o m ea nu r g e n tp r o b l e mt ob es o l v e d t h i sp a p e rt a c k l e sm s o t si nt w oa s p e c t s ：m o d e ld e s i g na n dm u l t i - o b j e c t i v e o p t i m i z a t i o n i nt h ef i r s tp a r t ，am o d e lw i t hb o t hg e n e r a l i t ya n dc o m p a t i b i l i t yh a sb e e n d e v e l o p e d ，f o l l o w i n gt h ei d e ao fs e e k i n gas t a n d a r dm o d e l i nt h es e c o n dp a r t ，b a s e do n t h en o t i o no fp a r e t oo p t i m i z a t i o n ，e v o l u t i o n a r ya l g o r i t h mi s a p p l i e d i ns o l v i n gt h e m u l t i - o b j e c t i v eo p t i m i s a t i o np r o b l e m ( m o p ) ，r e s u l t i n g i n as c h e m ef o rt h e t a s k s c h e d u l i n gp r o b l e m a c h i e v e m e n t si nt h i sp a p e ri ss u m m a r i e da r et w oa s p e c t s 1o nt h eb a s i so fat h o r o u g ha n a l y s i so ft h ei m a g i n gt a s k ，a l lt h ec o n s t r a i n t sa r e l a y e r e db e f o r et h e yc a nb eh a n d l e di nd i f f e r e n tw a y s t a k i n gi m a g i n gt a s k sa so b j e c t s ， i n d e n t i f y i n gr e c o n n a i s s a n c et i m ew i n d o w st ob a g sw i t hm u l t i - f o r mc h a r a c t e r i t i c s ，u s i n g a “c o m p a t i b l el i s t ”t od e s c r i b et h ec o m p l e xc o r r e s p o n d e n c eb e t w e e no b j e c t sa n db a g s ， am u l t i - d e m e n s i o n a ld y n a m i ck n a p s a c km o d e l ( m d d k ) i sa c h i e v e d ，w h i c hc o v e r s e x i s t i n gc o n s t r a i n t sa n dh o l d se x t e n s i v ep r o p e r t i e sf o rp o s s i b l et e c h n o l o g yd e v e l o p m e n t i nf u t u r e i nt h i sw a ym s o t si ss u m m a r i e da sam o p ， 2 i ns o l v i n gt h er e s u l t i n gm o p ，ac u l t u r e a l g o r i t h m ( c a ) w i t hm u l t i l a y e r e d b e l i e fs p a c ei sa p p l i e dt om d d k , w h i c hi sb a s e do nap i v o t a ls t a t e m e n to fc aa f t e ra n i n t r o d u c t i o no fp a r e t o o p t i m i s a t i o n a n das p e c i f i c a t i o no fd i f f i c u l t i e si nm o p t h e r e a f t e r ，a p p l y i n gt h es e p e r a t i o ns k i l li nm d d k ，as o l u t i o ns c h e m en a m e d b a g c u li sd e v e l o p e df o rm s o t s s i m u l a t i o nr e s u k ss h o wt h ee r i e c t i v e n e s sa n dc o m p u t a t i o ne f f i c i e n c yo ft h e s c h e m e t h er e s u l t so ft h i sp a p e rp r o v i d e san e wd i r e c t i o nf o rs o l v i n gm o t su s i n g s t a n d a r dm o d e i s ，a sw e l la sa l li n s t r u c t i v et r yi na p p l y i n gc at om o p 。 k e yw o r d s ：t a s ks c h e d u l i n g ；m u l t i o b j e c t i v eo p t i m i z a t i o n ；e v o l u t i o n a r y a l g o r i t h m ；k n a p s a c km o d e l ；i m a g i n gr e c o n n a i s s a n c es a t e l l i t e ；c u l t u r e a l g o r i t h m 第i i 贞 国防科学技术大学研究生院硕士学位论文 图目录 图2 ，l 星载遥感器观测范围与实际观测场景的关系示意图1 2 图2 。2 星下点轨迹示意图。1 2 图2 3 多星侦察系统组成示意图1 6 图2 4 成像侦察卫星任务调度问题技术实现的三个阶段1 8 图3 1 卫星任务调度问题与背包问题的对比1 9 图4 1p a r e t o 支配关系与p a r e t o 最优层3 0 图4 2 三类密度评估方法示意图3 3 图4 3 实现精英策略的方法3 4 图4 4 剪枝操作可能引起的外部种群退化3 5 图4 5 文化算法框架3 6 图4 6 文化算法伪代码3 7 图4 7g e m o s 基本框图4 0 图4 8 染色体结构图4l 图4 9 染色体编码合法性校正步骤一4 2 图4 10 染色体初始编码的g r i a 方法步骤4 3 图4 1 l 任务序列交叉算了实现步骤4 4 图4 。1 2 任务序列变异算子：基因交换4 4 图4 1 3 任务序列变异算子：任务转移4 5 图4 1 4 任务序列变异算子：任务交换4 5 图4 15 编码甄别策略4 6 图4 i6 单层信念空间文化算法解域示意图4 9 图4 17 多层信念空间文化算法结构5 0 图5 1 典型场景示例5 7 图5 21 1 x m l 的内容5 9 第页 围防科学技术大学研究生院硕士学位论文 表目录 表1 1 国内外成像卫星调度领域研究丁作总结5 表3 1 相容性条件列表2 6 表5 1 卫星轨道数据表5 5 表5 2 卫星星载遥感器性能参数5 6 表5 3 分布式卫星系统观测任务集5 7 表5 4 每颗观测卫星的观测任务5 9 表5 5 任务调度结果6 0 表5 6 进化世代数为1 5 0 时的算法性能对比6 2 表5 7 进化t 廿= 代数为3 0 0 时的算法性能对比6 2 表5 8 进化世代数为5 0 0 时的算法性能对比6 2 第1 i i 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意 学位论文题目： 基王蜚鱼搓型塑进丝篡洼的垒星值塞堡盘迥廑问塑盟究 学位论文作者签名： 捧牺e l 期：沁g 年月i 。日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印，缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文作者签名：堇垒塑 作者指导教师签名： 了乍乞 日期：认同2 年1 1 月jo 日 日期： lj 年i - 月l 日 围防科学技术大学研究生院硕士学位论文 1 1 1 问题的提出 第一章绪论 1 1问题来源与研究目的 现代战争中，能否快速准确地感知战场态势进而获取信息优势是取得胜利的 关键。战场态势的感知源于对战场的侦察和监视，在众多的侦察手段中，侦察卫 星具有侦察范围人，提供信息迅速、可靠，可长期反复侦察和监视，不受国界限 制，可提供近实时的信息等特点。人造卫星特别是军用侦察卫星1 的出现，改变了 传统的侦察方式，也改变了作战的空间和时限概念。可以说在现代战争条件下， 只有具有实时或近实时的卫星侦察、监视及预警能力，从而缩短“观测、判断、 决策、行动”作战链路的时间，才能将广泛部署的武器平台和陆、海、空部队的 作战能力集成起来，最终夺取战争胜利。 成像侦察卫星【2 。6 1 主要通过光学、电子或光电系统获取地面目标图像信息。当 卫星在某一轨道上运行时，可以根据需求对地面特定目标实施成像，所获得的图 像信息通过数传通道实时传输至地面接收站或是记录在胶片、存储器上，通过回 收或以无线电传输方式延时送回地面，图像信息在地面数据处理中心经加工处理 和判读识别，从中获取各种军事情报。 现代战争对空间信息支持的依赖越来越大，通过一两颗成像侦察卫星来获取 整个战场的有用信息已远远不能满足实际需求。多星组网进行侦察和监视，已成 为侦察卫星发展的一种必然模式【7 1 。随着卫星作战应用需求的日益迫切，我国也开 始研究将各种型号的侦察卫星组网，组成多星侦察系统【8 1 ，以更快更准更伞面地获 得空间信息优势。 成像侦察卫星的任务是根据用户的需求获取感兴趣地区的军事信息，一个侦 察任务可以分为两部分主要工作，信息获取和数据下传。不管是信息获取还是数 据的回传，都需要卫星与目标( 侦察目标，地面站或中继卫星) 可见时才能执行， 这在时间上大大限制了卫星资源的可用性。由于成像侦察卫星是在轨运行的，卫 星的存储器、燃料和电源等资源的补充也非常困难。同时，成像侦察卫星研制成 本高，研制周期长。一些卫星重达十几吨，耗资几十亿美元，制造耗时十几年。 这些都使得成像侦察卫星在轨的时间和资源显得十分宝贵。为了有效的利用成像 侦察卫星宝贵的轨道资源，实现在有限的时间内尽可能满足不同用户、不同优先 级的成像侦察需求，需要制定合理的任务计划，对多颗卫星进行综合任务调度， 笫l 页 国防科学技术大学研究生院硕士学位论文 均衡考虑各种凶素，统分配资源，发挥卫星系统的最大综合效益。 为了合理有效的利用卫星资源，从而充分发挥航天侦察系统的作战能力，一 方面我们总是希望任务调度的结果能包含尽量多的成像侦察任务，另一方面我们 又希望任务调度的结果对资源的消耗尽量少。因此，在任务调度过程中需要考虑 对结果的多目标评价，从而提出了多目标综合任务调度问题【9 - 1 0 】。 本文的主要工作即分析卫星运行、工作机制及约束因素并建立问题分析模型， 以此为基础综合多种影响因素，设计多目标进化算法，进行优化决策，实现侦察 卫星运行过程的优化调度。 1 1 2 研究意义 目前，我国在卫星应用方面采用的主要是单星任务管理模式，即每颗甲星及 其应用系统自成体系，由各自专门的机构负责管理，相互之间缺乏协调和配合。 随着卫星技术和信息技术的发展，现代战争对侦察卫星成像任务的需求量也将快 速增加，对成像任务的时效性、准确性要求将更加严格，任务管理的复杂度也将 大人增加，现有的各卫星独立运行管理的工作模式显然已无法满足未来的需要。 此外，成像侦察卫星对地面目标( 包括陆地和海洋) 实施观测活动，具有观 测范围大、时效性好、不受国界和地理条件限制、运行时间长等特点。但由于卫 星有其特殊的运动规律，无法长时间在目标上空盘旋飞行，只能周期性的对目标 实施观测，同时卫星有效载荷在使用方法和容鼍一卜也有很多限制。因此，为了充 分发挥成像侦察卫星资源的效益，满足信息化条件下的快速信息获取需求，迫切 需要把多颗成像侦察卫星资源作为相互协作配合的整体进行一体化考虑，对成像 侦察卫星调度问题进行研究。 课题研究意义1 5 a o 在于： ( 1 ) 成像侦察卫星及其相关技术在现代战争中发挥着重要的作用。作为成像 侦察卫星地面指挥控制的关键支撑技术，成像侦察卫星综合任务调度问题已经成 为了实际应用中的一个重要的研究内容； ( 2 ) 成像侦察卫星综合任务调度问题涉及成像任务数据预处理，综合任务调 度模式，任务调度模型，任务调度算法等多个方面。具有较多的技术难点，研究 合理的成像侦察卫星综合任务调度问题模型和成像侦察卫星综合任务调度问题算 法，对提高成像侦察卫星系统综合效益有重要的意义： ( 3 ) 通过卫星综合任务调度，给出卫星系统最大化满足作战任务需求的能力， 以此评估卫星系统的整体应用能力，辅助用户进行侦察需求的调整。 ( 4 ) 通过卫星综合任务调度，分析现有系统配置的性能，辅助决策者进行系 第2 页 国防科学技术大学研究生院硕士学位论文 统酣置的调整，如补发卫星、卫星变轨、增设地面站、移动地曲站变址等。 1 2 国内外研究现状 算法研究必然是建立在一定的模型之上的，就多星侦察任务调度问题来说， 研究主要从问题分析模型、优化求解算法两个方面进行。由于当前各国成像侦察 卫星发展水平差异较大，各种成像卫星参数各异、运行于不同轨道，且对应的成 像日标数日为几十至数千个，作为成像计划编制的核心，侦察卫星成像调度问题 也就分为多类：根据参与调度的卫星数罱可分为单星成像调度和多星成像调度； 根据调度方案是否作调整可分为静态调度和动态调度；根据制定调度的地点分为 在线( o n - l i n e ) 调度和离线( o f f - l i n e ) 调度。 1 - 2 1 成像侦察卫星任务调度问题研究现状 1 2 1 1 成像侦察卫星任务调度问题模型研究现状 为了问题求解的方便，大多数研究都根据实际需求建立了繁简不一的问题分 析模型。这些模型主要分为三个类别，第一类是数学规划模型：第二类是约束满 足问题模型及其改进；而第三类转化为一种通用问题模型。 在国外的研究中： p e m b e r t o n t l 、w o l f e ( 1 2 1 在研究中没有考虑存储器容量约束和数传任务需求的 情况下，且假定任务间不存在任何的时问和逻辑关系的条件下，建立了数学规划 模型。法国欧空局的b e m a n a i l 3 l 等人针对s p o t 5 卫星，建立了整数规划模型。 l e m a i t r e 1 4 1 针对敏捷卫星( a g i l es a t e l l i t e ) ，在没有考虑存储器容量约束的条件下， 建立了约束满足问题模型。b e n s a n a t l 5 】针对s p o t 任务规划研究中，考虑成像侦察 卫星存储器容量约束，侧视条件约束等多种约束的条件下，提出了一种值约束满 足问题模型，但足没有考虑数传任务需求。d a m i a n i t l 6 l 针对成像任务的动态变化建 立了成像卫星自主任务规划的序列决策模型。g a b r e l t 1 针对单颗成像卫星的任务规 划问题，建立了一种无圈有向图模型，且利用无圈有向图的成像路径表示任务规 划结果。s m i t h 1 8 】采用a s p e n 建模语言建立了e o 1 的状态动作模型。v a s q u e z t l 9 1 等人将s p o t 5 卫星的任务规划问题转化为0 1 背包问题。此外，目前实际虑用 中还存在许多针对具体卫星的专用建模方式，例如p o t t e r 2 0 1 等人针对l a n d s a t 7 设计 的任务调度模型，以及m u r a o k a | 2 l 】等人针对对地观测卫星设计的a s t e r 规划模型 等。 在国内的研究中： 哈尔滨工业大学的杨家军【2 2 1 在考虑小卫星自主运行模糊特性所引起的规划与 第3 页 国防科学技术大学研究生院硕士学位论文 调度的动态特性条件- 卜，提出了任务规划与调皮的模糊智能模型。 中国科学院空间科学与应用研究中心的代树武，刘洋 2 3 - 2 5 1 等人提出了卫星模 型、推理机支持下的智能规划与调度技术结构和采用分层a g e n t 控制的自主控制 系统，主要用于将卫星成像计划分解成比较详细的操作指令序列。 国防科学技术大学的贺仁杰f 2 6 j 在调度约束条件分析和一些基本假设的基础 上，建立了两种问题求解模型：约束满足问题模型和混合整数规划模型。刘洋1 2 7 j 针对有新成像任务到达的情况建立了动态约束满足调度模型。张万鹏【8j 针对多星侦 察系统的任务特点，设计了一种多星任务规划调度建模框架，模型包括四个部分： 活动，资源，事件和约束。张帆1 7 针对卫星的优化成像目标序列求解，建立了一种 无圈有向图模型。张正强【2 8 】针对单星的自主控制问题，建立了智能成像卫星的规 划域模型，但没有考虑存储器容量约束、时间窗口约束以及数传任务需求等多种 限制。王例旧】针对成像卫星综合任务调度问题，基于全局优化模式，建立了多目 标任务调度模型：基于阶段优化模式，建立了综合任务调度问题的多目标有向图 模型。+ 军民【29 l 在研究了不确定条件下的成像卫星调度问题，建立了成像卫星鲁 棒性调度模型和成像卫星动态调度模型。 在成像调度应用领域，我国的各颗遥感卫星进行成像计划编制时，都是由操 作人员根据用户需求及卫星的各种约束条件，需要经过长时间的分析，选取一种 可行的成像方案，资源利用率低下，需消耗大量的人力和物力，昂贵的卫星有效 载荷资源未得到充分利用。 1 2 1 2 成像侦察卫星任务调度问题算法研究现状 成像侦察卫星任务调度算法主要分为完全搜索算法和不完全搜索算法两类【7 】。 由于成像卫星任务调度问题的特点和复杂性，目前大多数研究工作主要集中在不 完全搜索算法上。 在国外的研究中： p e m b e r t o n t l lj 提出了一种对大规模问题的迭代求解方法。w o l f e 和s o r e n s e n 1 2 】 比较了贪婪算法、具有前瞻( 1 0 0 k a h e a d ) 功能的贪婪算法以及遗传算法等i 种算 法。在贪婪算法中，所有地面目标按照优先级别进行排序，然后按顺序依次选择， 根据约束条件安排最佳成像时刻。具有前瞻功能的贪婪算法在选择下一个成像任 务时需要考虑其对其他成像任务的影响。遗传算法中，定义了相应的交叉、变异 算子，允许撤销已经安排的成像任务，可以得到一个较好的规划方案。文中的实 验证明，当问题规模较大时遗传算法取得的调度效果最好。l e m a i t r e j 采用约束规 划方法和局部搜索算法对相应的问题模型进行求解。b e n s a n a i l 5 1 等人基于值约束满 足问题模型比较了完全搜索算法( 深度优先搜索、动态规划、r u s s i a nd o l ls e a r c h ) 第4 页 国防科学技术大学研究生院硕士学位论文 和不完全搜索算法( 贪婪搜索、禁忌搜索) 在不同问题规模情况卜的性能。义中 给出的实验证明，完全搜索算法可用于求解小规模问题的最优解，而禁忌搜索可 以在合理的时问内得到较人规模问题的一个满意解。g a b r e l ! 】针对s p o t 5 卫星的 任务规划问题，采用标记校正算法对无圈有向图模型进行求解。s h e r w o o d 3 0 】等人 在用于e o - l 卫星的a s p e n 系统中采用了一种基于局部搜索的算法。v a s q u e z 等 人1 1 9 j 针对建立的背包问题模型，采用禁忌搜索算法进行求解。 表1 1 国内外成像卫星调度领域研究工作总结 5 研究人员单时间算法模型多目标优化。 位系统 处理方式崩 b e n s a n a 等 l9 9 6 深度优先搜索、禁忌搜索，动态每 规划、r u s s i a nd o l ls e a r c h ，约束次 满足只 a s t e r1 9 9 8 贪婪算法考 a s p e n1 9 9 8 局部邻域搜索 虑 l a n d s a t7l9 9 8 改进的贪婪算法 优 b u r r o w b r i d g e 1 9 9 9 贪婪算法 化 l e m a i t r e 等 2 0 0 0 局部邻域搜索、约束规划 芭 p em b e r t o n 2 0 0 0 启发式搜索 w o l f e 等 2 0 0 0 贪婪算法、具有向前看的贪婪算 目 法、遗传算法 标 g r e a s2 0 0 0 基于 i l o gs o l v e r 及s t k 函 s c h e d u l e r 数 v e r f a i l l i e 等【2 2 0 0 l 贪婪算法、动态规划、约束规划、 局部邻域搜索 v a s q u e s 2 0 0 1 禁忌搜索算法 f r a n k 等 2 0 0 2 启发式搜索算法 g l o b u s 等 2 0 0 2 遗传算法 g a b r e l 等 2 0 0 2 标记校正算法同时优化三 个目标函数 s t k s c h e d u l e r2 0 0 3 贪婪算法、神经网络每次只考虑 国防科大系统 2 0 0 4 贪婪算法、禁忌搜索算法，动态 优化单一目 ：j ：程研究所约束满足 标函数 在国内的研究中： 国防科学技术大学贺仁杰1 2 6 1 针对不同的两种问题求解模型给出了相应的禁 忌搜索算法和列生成算法。刘洋【2 7 j 设计了模型求解的动态回溯算法和基于局部修 改的递进规划算法。张万鹏【8 l 采用基于动态优先级的局部邻域搜索算法完成了问题 模型的求解。张帆【7 1 基于遗传算法针对单星轨道罔次的任务规划问题提出了最短路 径优化算法。张正强【2 8 1 采用基于任务网络的引导式状态空间搜索算法和采用基于 任务网络的后向状态空间搜索算法求解了单颗自丰成像小卫星的规划域模型。王 第5 页 国防科学技术大学研究生院硕十学位论文 钧i lo 】针对成像卫星综合任务测度问题，基于全局优化模式，给出了一种基于s p e a 2 算法的多目标综合任务调度算法；基于阶段优化模式，首先提出了一种基于拍摄 概率的成像任务预分配方法，将多星任务调度转化为单星任务调度：然后给出了 种基于多目标进化算法的成像路径搜索算法用于求解单星的任务调度问题。王 军民【2 9 j 提出了基于偏好的分层多目标遗传算法用于求解成像卫星鲁棒性调度模 型：提出了动态插入任务启发式算法用于求解成像卫星动态调度模型。在表1 1 中， 我们对近年来国内外在成像卫星调度领域的研究工作进行了总结。 1 2 1 3 多目标进化算法研究现状 成像侦察卫星任务调度问题本质上是一个多日标、多约束、强耦合的复杂多 目标优化与决策问题。结合多目标优化领域的先进研究成果可以对问题进行有效 解决。为此，论文对相关多目标优化理论的研究现状进行总结。 多目标优化问题在现实世界中的普遍存在性以及求解的困难性，促使人们付 出了很多精力米寻求解决的方洲3 1 1 。早在1 7 7 2 年，f r a n k l i n 【3 2 1 就提出了多目标问 题矛盾如何协调的问题。1 8 9 6 年p a r e t o1 3 3 1 首次从数学角度提出了多目标最优决策 问题，并引入了p a r e t o 最优解的概念。1 9 5 1 年，k o o p m a n s 弘】在生产和分配问题中 提出有效向量的概念，与此同时，k u h n p s i 等人给出了向莆极值问题有效解的必要 条件。至此，多目标优化逐渐受到人们的关注。从2 0 世纪5 0 年代末到9 0 年代初， 先后出现了加权和法、目标规划法、占约束法等基于权重的多目标优化方法。 这些传统的多目标优化问题的求解方法往往是加上决策者的偏爱信息后，将 多个优化目标通过一定的变换转换为一个优化目标，然后采用单目标优化方法进 行解决，得到反映决策者偏好信息的一个解。但是，这样做存在几大缺点【3 6 】： ( 1 ) 不同性质的目标之间单位不一致，不易作比较； ( 2 ) 各目标加权值的分配带有较大的主观性； ( 3 ) 优化目标仅为各目标的加权和，优化过程中各目标的优度进展不可操作； ( 4 ) 各目标之间通过决策变量相互制约，往往存在相互矛盾的目标，致使加权 目标函数的拓扑结构十分复杂。 近十年来，随着进化计算( e v o l u t i o n a r yc o m p u t a t i o n ) 技术和群智能( s w a r m i n t e l l i g e n c e ) 方法的兴起以及在科研和实践中的广泛应用，多目标优化技术的发展 更为迅猛，应用这些技术和方法水解多目标优化问题成为当前一个热门的研究领 域。 由于这些方法具有高度的并行机制，可以对多个目标同时进行优化，因此多 目标优化问题的求解方法也开始由目标组合方式逐步向基于p a r e t o 的向量优化方 法发展。这些方法主要包括：多目标进化算法、多目标粒子群算法、多目标蚁群 第6 页 国防科学技术大学研究生院硕士学位论文 算法等。其中，多目标粒予群算法和多目标蚁群算法相对起步较晚，开展的不够 广泛，有许多理论问题有待于进步的研究和探讨，而多目标进化算法由于易于 实现，搜索效率较高，在电子学、环保学、金融学、经济学、几何学、物理学信 息及资源等众多领域中都得到了成功的应用。因此，论文基于进化多i q 标优化理 论解决成像侦察卫星任务调度问题。 进化算法具有高度的并行机制，可以对多个目标同时进行优化，在求解多目 标优化问题时具有其它方法不可比拟的优势。因此，进化算法作为多目标优化问 题的求解方法得到了相当程度的关注 3 7 - 4 4 】。早在1 9 6 7 年，r o s e n b e r g 在其博士学 位论文中就曾提到可用遗传算法求解多目标优化问题 4 5 1 。1 9 8 5 年，s c h a f f e r 提出 的向量评估遗传算法( v e g a ) 【4 6 i ，开创了用进化算法求解多目标优化问题的先河。 2 0 世纪9 0 年代以后，学术界掀起了多目标进化算法的研究热潮，在人- t 生命和进 化计算学科，多目标进化算法己经成为一个相当热门的研究领域。2 0 0 1 年3 月， 在瑞士的苏黎世大学召开了国际第一次进化多准则优化的会议。在此后的许多重 要的国际学术会议上都设有专门的多目标进化算法会议专题，关于多目标进化算 法的的论文的数量急剧增加。 日前多目标进化算法已经成为解决多目标优化问题的一个强有力的工具。大 致说来，多目标进化算法的发展可以分为两个阶段【47 】：第一代算法的研究重点是 如何将多目标优化问题中的p a r e t o 最优概念与进化算法结合起来，引导进化过程 寻找p a r e t o 最优解，同时如何保持种群的多样性：第二代多目标进化算法的突出 特点是将精英策略( e l i t i s m ) 引入到算法设计中，以避免由于随机因素引起的非劣 解丢失，增强算法的收敛性。 1 第一代多目标进化算法 a 非劣分层遗传算法( n o n d o m i n a t e ds o r t i n gg e n e t i ca l g o r k h m ，n s g a ) ： n s g a 由s r i n i v a s 和d e b 提州48 1 ，其基本思想是利用g o i d b e r g 提卅的基于p a r e t o 优劣性分类选择的方法突出好的个体，以及用小生境方法来维持种群的多样性。 在选择之前，基于非劣性对种群进行分类：当前种群中所有的非劣解归为类( 记 为第一层) ，然后忽略这些非劣解，再从种群剩余的个体中选出当前非劣解归为 一类( 记为第二层) ，如此直至完成对整个种群的分类。个体的初始适应值即为 其位于的层数。为了保持种群的多样性，采用适应值共享机制修正每一层中个体 的适应度。由于第一一层中的个体总是具有最大的适应度，因此，被选中的概率很 大，这使得种群向着非劣解所在的区域收敛。同时，共享机制的采用使得非劣解 尽可能的均匀分布在非劣区域( 即问题的p a r e t o 最优层) 。 b 小生境p a r e t o 遗传算法( n i c h e dp a r e t og e n e t i ca l g o r i t h m ，n p g a ) ：n p g a 第7 页 国防科学技术大学研究生院硕士学位论文 由h o r n 等提出1 4 9 ，采用了基于p a r e t o 优劣性的锦标赛选择方法，每次从种群中随 机选择两个个体，然后从种群中随机选取一定数量的其他个体组成参赛组，参与 非劣最优解的比较。如果两个个体中的一个劣于参赛组中的所有个体，而另一个 体至少支配参赛组中的一个个体，则后一个体在竞赛中得胜。如果两个个体都支 配或劣于参赛组中的所有个体，即认为平局，然后根据共享适应值进一步决定其 输赢。因为n p g a 的非劣最优解选择是基于种群的部分而非全体，因此能很快找 到一些好的非劣最优解域，并能维持一个较长的种群更新期。 c 多目标遗传算法( m u l t i o b j e c t i v eg e n e t i ca l g o r i t h m ，m o g a ) ：m o g a 由 f o n s e c a 和f l e m i n g 提出【5 0 1 。m o g a 采用了一种基于p a r e t o 排序的适应度赋值策略： 对于每个个体，根据当前种群中支配其的个体数目确定其排序r a n k ，等级越高表 示种群中支配该个体的个体越多，从而个体的性能越差。同时，m o g a 采用共享 函数与小生境技术来提高种群多样性。 2 第二代多目标进化算法 第二代m o e a 的突出特点是将精英策略引入算法设计中，其中有些算法是第 一代算法的改进算法。代表算法如下： a 非劣分层遗传算法i i ( n s g a i i ) ：d e b 等提出了n s g a 的改进算法 n s g a i i1 5 ，与n s g a 采用了相同的评价个体p a r e t o 优劣性的方法，但是提高了 非劣分层算法的效率，降低了计算复杂度。n s g a 1 1 采用了拥挤距离方法来评价 个体的密度信息，避免了适应值共享方法的共享参数选择问题。最重要的是， n s g a i i 引入了精英策略：为保护在进化过程中出现的优秀个体，将父代种群和 予代种群合并成一个新的种群，然后对该种群进行非劣排序，选择新种群中的前n 个个体作为进行新一轮进化操作的下一代种群。 b 小生境p a r e t o 遗传算法2 ( n p g a 2 ) ：e r i c k s o n 等提出了n p g a 的改进算 法n p g a 2 1 52 ，与n p g a 的主要区别在于，n p g a 2 算法采用了与m o g a 中相同的 基于p a r e t o 排序的适应度计算方法，然后基于此进行锦标赛选择，对平局的情况 与n p g a 一样，采用小生境计数计算，连续更新适应度共享。此外，n p g a 2 还采 用了与n s g a - i i 类似的精英策略。 c 强度p a r e t o 进化算法( s t r e n g t hp a r e t oe v o l u t i o n a r ya l g o r i t h m ，s p e a ) 及其 改进算法s p e a 2 ：s p e a 5 3 】及s p e a 2 1 5 4 1 算法由z i t z l e r 和t h i e l e 等提出，这两个算 法都利用一个外部种群存储进化过程中找到的非劣解，在每一代中，将非劣解复 制到外部种群中以实现精英策略。s p e a 对外部种群中的每一个个体，赋一个强度 值，该强度值与m o g a 中个体的p a r e t o 排序类似，个体的适应值为外部种群中支 配该个体的个体强度值之和，然后采用一种聚类方法来维持种群的多样性。s p e a 2 第8 页 国防科学技术大学研究生院硕士学位论文 在三个方面对s p e a 进行了改进：1 ) 通过综合考虑某个个体支配的个体数日和被 支配的个体数日，对适应值计算策略进行了改进；2 ) 采用了一种最近邻域密度估 计方法，提高了搜索效率；3 ) 改进了外部种群的剪枝方法，避免丢失边界点。 d p a r e t o 存档进化策略( p a r e t oa r c h i v ee v o l u t i o n a r ys t r a t e g y ，p a e s ) ：p a e s 由k n o w l e s 等提出【5 5 】。p a e s 采用了结合外部种群的( 1 + 1 ) 进化策略，即一个父个 体产生一个子个体，同时利用外部种群存储进化过程中找到的非劣解。p a e s 通过 对目标函数空间进行网格划分来估计个体的密度值，进而作为维持种群多样性的 基硎j 。 1 2 2 现有研究的特点和不足 ( 1 ) 由于成像侦察卫星任务调度问题的复杂度较高，现有研究大多基于一些 简化的模型，不考虑某些实际的约束条件，如存储器容量约束、时间窗口约束等， 这样基于简化模型求解得到的调度方案很难满足实际问题的要求。 ( 2 ) 缺乏对成像侦察卫星任务调度问题共性的分析、归纳和总结，现有研究 大多是针对特定型号的卫星，建立的模型i 一星载设备密切相关，不具有一般性和 通用性，且都具有一定缺陷。 ( 3 ) 缺乏对调度算法的深入研究，调度算法大多都针对具体型号卫星的简化 模型，灵活性和适应性较差。 ( 4 ) 成像侦察卫星任务调度问题从本质上归结为一个多目标优化问题，优化 目标包括时间代价、资源消耗等，优化其中任何的单一优化目标都不能反映问题 的本质。目前开展多目标任务调度的研究还不多。多目标优化问题目前仍然是一 个开放式问题( o p e np r o b l e m ) ，结合新的优化设计思想进行算法的改进是很有意 义的。 1 3 研究思路与论文结构 针对上述研究的不足，本文的研究着眼于模型研究，并在问题求解时尝试新 型多目标优化算法，以求在通用性和求解效率上得到提升。 如果要求具有通用性，模型设计势必要向标准模型靠拢。背包模型是一种可 行的选择。把多星侦察任务纳入到背包模型中去，并尽可能减少关键要素的损失， 需要对问题进行深入分析，也可能需要对背包模型适当调整。 如果获得了标准模型为基础的任务调度模型，就可以尝试应用标准问题的解 决框架。本文选择的是文化算法，这是一种较新的进化算法框架，已经在进化问 题的解决中显示了其在种群规模控制、收敛性等方面的优势。本文将其用到多目 第9 页 国防科学技术大学研究生院硕：l 学位论文 标优化问题的解决中，以划望获得满意的结果。 论文各章内容安排如下： 第二章从成像侦察的原理出发，逐步明确了多星侦察任务调度的问题关键， 对存在的多种约束进行分类，阐述了调度目标，在回顾成像任务组织实施过程中 明确了研究的难点和针对性。 第三章是模型设计，以成像任务和可见时间窗口为主要关注点，在明确各自 属性和相互约束的基础上，建立了多维动态背包模型，结合相容性列表的概念完 成了模型设计。 第四章是算法设计，回顾了多目标优化的基本概念和关键问题，阐述了文化 算法的基本思想，基于分离设计的原则，在任务相关性设计中完成了编码和进化 算子的设计，在任务无关性设计中引入多层信念空间的设计，最终形成了调度问 题的b a g c u l 解决方案。 第五章是仿真验证，介绍了仿真环境设置，通过实例验证了b a g - c u l 方案 的有效性，并结合对比仿真分析了该方案的特点和优势。 第i 0 页 国防科学技术大学研究生院硕士学位论文 第二章多星侦察调度问题分析 多星侦察系统是一个具有多资源、多用户、多任务需求的复杂星地大系统， 研究多星侦察系统的任务建模及规划调度技术，首先需要对系统的组成、任务需 求和任务特点等进行分析，总结出任务模型的要素，进而设计合理的建模方式， 用于解决多星侦察系统侦察计划生成的问题。本章对多星侦察系统进行任务分析。 2 1 单星成像侦察问题 成像侦察卫星具有多种类别1 5 】，按获取图像的方式分类，分为回收型和传输型