遗传算法在成像卫星计划编制中的应用

2013-10-18高朝晖岳群彬

无线电工程 2013年12期

高朝晖，岳群彬，李伟

(中国电子科技集团公司第五十四研究所，河北石家庄 050081)

0 引言

随着航天事业的不断发展和卫星种类数量的不断增加，我国逐渐拥有数量众多的多个系列成像观测卫星，如何有效地利用卫星摄影资源和地面站跟踪接收资源，制定高效可行的卫星和地面站任务计划将成为一个重要的问题。

由于星地资源的使用限制，通常用户的摄影需求不能被全部满足。如何在大量约束条件下，安排一个满意的星地任务计划，分配星地资源来完成更多的摄影任务，对于充分有效地发挥成像卫星的能力是至关重要的。基于此，研究人工智能优化算法领域中的遗传算法在成像卫星计划编制问题中的应用，实现星地资源的优化分配。

1 问题描述

卫星的计划编制是指根据卫星的可摄影时段和地面站的可接收时段，结合星上有效载荷的使用约束和业务规则，通过一系列的冲突消解和决策分析，最后安排出一个优化合理的卫星摄影计划和地面站接收计划。

星地资源分配问题的主要特点在于在决策分析过程中，目标存在可见时间窗口和约束限制条件。只有在可见时间窗口内且满足约束条件，目标才允许被摄影。因此，星地资源分配问题可描述为:从一个由目标的可见时间窗口组成的庞大的搜索解空间中选取一个子集，使这个子集满足所有的约束条件并使该次观测方案的评价值为最大［1］。

考虑到星地资源分配问题是NP完全问题，通常的线性规划方法不能有效地求解，基于上述约束，采用遗传算法实现了星地资源的自动优化分配，以获得尽可能多、尽可能重要、摄影效果尽可能好且优先满足等级较高用户的目标影像数据，充分有效地发挥成像观测卫星的能力。

2 遗传算法简介

2.1 基本原理

遗传算法是基于自然选择和自然遗传机制的搜索算法，它是一种有效的解决最优化问题的方法。遗传算法最早是由美国Michigan大学的John Holland和他的同事及学生提出的，它借鉴达尔文的物竞天择、优胜劣汰、适者生存的自然选择和自然遗传的机理，其本质是一种求解问题的高效并行全局搜索方法。算法从任一初始化的群体出发，通过随机选择、交叉和变异等遗传操作，使群体一代一代地进化到搜索空间中的优化区域，最后抵达最优解。算法的特点在于搜索过程中能够自动获取和积累有关搜索空间的知识，利用问题的固有知识来缩小搜索空间，并自适应地控制搜索过程，从而得到最优解或准最优解［2］。

遗传算法与其他算法相比，主要有以下4个方面的不同:①遗传算法所面向的对象是参数集的编码，而不是参数集本身;② 遗传算法的搜索是基于若干个点，而不是基于一个点;③ 遗传算法利用目标函数的信息，而不是导数或者其他辅助信息;④遗传算法的转化规则是概率性的，而不是确定性的［3］。

2.2 算法步骤

遗传算法的运行过程为—个典型的迭代过程，基本步骤如下:①选择编码方式;② 定义适应度函数f(x);③确定遗传策略，包括群体大小和选择、交叉、变异方法，确定交叉概率和变异概率等遗传参数;④随机初始化生成群体;⑤ 计算群体中个体位串解码后的适应值f(x);⑥ 按照遗传策略，运用选择、交叉和变异算子作用于群体，形成新一代群体;⑦判断新群体性能是否满足某一指标或者是否已完成预定迭代次数，不满足则返回步骤⑥或者修改遗传策略再返回步骤⑥，满足则退出［4］。

3 遗传算法的应用

在成像卫星运行管理控制中，需要合理安排星地资源，并满足长条带摄影、多站联合接收及应急处理等航天应用的特点，具体地，在分析提炼卫星摄影能力、星上存储能力、地面接收能力、数据处理能力约束以及有效载荷使用规则的基础上，基于遗传算法实现了星上载荷资源和地面接收资源的优化分配，据此编制出卫星和地面站的任务计划，从而提高了任务控制的合理性和资源使用的效率，获取尽可能多的目标区域影像数据，满足了后续遥感数据处理应用需求，增强了卫星任务控制的科学性和时效性。

首先确定了计划编制的时间区间、参与的地面站和目标区域，然后进行卫星轨道预报计算，结合目标区域的地理位置，计算出卫星对各个目标区域的访问时间，即摄影任务。该摄影任务即可作为遗传算法的输入，然后根据算法流程，对这些摄影任务不断进行进化迭代，达到预定迭代次数时即退出算法，遗传算法迭代流程如图1所示［5］。

图1 遗传算法的迭代流程

3.1 编码方式

遗传算法的编码方式有多种，比如二进制编码、整数编码、浮点数编码和混合编码等，这些编码方式各有其特定适应的问题，并且对遗传算法的性能影响很大［6］。

每个摄影任务只有“执行”和“不执行”2种状态，据此选择了二进制编码。每一个基因位表示一个卫星摄影任务，0表示不执行，1表示执行。每个个体(二进制串)表示一个可实施的观测方案，如 010111，表示只执行第 2、4、5、6 个摄影任务。

3.2 产生初始种群

依据算法理论，初始时要随机初始化一定数目的个体组成种群，但是由于计划编制的过程中存在大量的约束条件，随机初始化的个体很可能违反约束，导致所有个体的适应度都为0，这样在进化时就很难跳出局部的谷底［7］。

因此，在初始群体的产生算法中引入了适当的“选种”机制，以避免个体适应度全部或大部分为0的情况。具体的方法是使初始个体的基因位全部为零，即 000000。随着群体进化的逐渐进行，个体的适应度会逐渐增大，基因位会逐渐由0变为1，即越来越多的摄影任务会被执行，直至最优。

3.3 计算适应度

在具体应用中，适应度函数的设计要结合求解问题本身的要求而定。需要强调的是，适应度函数评估是选择操作的依据，适应度函数的设计直接影响到遗传算法的性能。个体的适应度在优胜劣汰的自然进化过程中起关键性作用，若定义不当则会直接误导算法向坏的方向进化。

成像卫星的使用约束主要包括以下几个方面:

①开机约束(最短和最长开机时间等);

②侧视约束(侧视速度、测试准备时间等);

③存储约束(固存容量限制等);

④联合接收约束;

⑤回放约束。

实际应用中，一个较优的摄影计划应该能够获得尽可能多、尽可能重要、拍摄效果尽可能好且优先满足等级较高用户的目标的摄影数据，因此，采用了多准则加权和的计划评价方法，主要包括以下分评价值:

①目标数目评价值f1;

②目标重要性评价值f2(如任务紧急程度和目标等级等);

③观测效果评价值f3(如云量因素和太阳高度角等);

④附加影响评价值f4(如用户等级和任务紧迫度等)。

基于此，定义个体的适应度为:

式中，X1、X2、X3、X4分别为各准则的权值;f1、f2、f3、f4可以根据观测目标的属性得出。结合实际需要，可以通过提高某一个准则的权重来获得侧重这一方向的观测计划［8］。

3.4 选择算子

选择是指从群体中选择优胜个体、淘汰劣质个体的操作，其目的是把优化的个体(或解)通过配对交叉产生新的个体再遗传到下一代。常用的选择算子有适应度比例方法、最佳个体保存方法、期望值方法、排序选择方法和排挤方法等［9］。

具体采用的是适应度比例方法。在该方法中，各个个体的选择概率和其适应度值成正比，定义第i个个体被选择的概率为［10］:即个体适应度越大，其被选择的概率就越高，反之亦然。

3.5 交叉算子

交叉是指把2个父代个体的部分结构加以替换重组而生成新个体的操作。交叉关键是交叉次数的选择，具体采用的方法是用交叉概率Pc作贝努利实验。如果实验成功，则选择的2个父代个体交叉配对;否则不交叉，进行下一轮选择。

基本的交叉算子有单点交叉、两点交叉、多点交叉一致交叉、二维交叉和树结构交叉等［11］。具体采用了单点交叉，即在个体串中随机设定一个交叉点。实行交叉时，该点后的2部分结构进行互换，并生成2个新的个体。

3.6 变异算子

变异是指对个体的某些基因位的值进行变动，其目的是使遗传算法具有局部搜索的能力和维持种群的多样性。

具体地，首先在群体中所有个体的基因串范围内随机确定基因位，然后用变异概率Pm作贝努利实验。如果实验成功，则对这些基因位的值进行变异，否则不变异。变异操作定义为对基因位的值进行逆转，即0→1或1→0。

在遗传算法中，交叉算子具有全局搜索能力，而变异算子具有局部搜索能力，通过交叉和变异的相互配合可使其兼顾全局和局部的均衡搜索能力［12］。

3.7 附加优化方法

在基本遗传算法的基础上，还采用了若干方法来优化算法的执行过程，使算法能更快地找到最优解。

3.7.1 精英解保留

精英解保留是指把群体中适应度高的个体不进行交叉变异而直接复制到下一代中，优点在于能保证算法终止时得到的最后结果一定是历代出现过的最高适应度的个体。具体的实现过程如下:取出新种群中的的最差个体s1适应度f1、旧种群中的最佳个体s2适应度f2。如果f1＜f2，则将s1替换为s2，同时将 f2置为0，然后更新 s1、f1、s2和 f2，返回步骤①，否则退出。

3.7.2 自适应变异

变异率在保持固定不变的情况下，一旦陷入局部最优，就很难跳出来。为了避免这种情况，根据交叉所得的2个个体的海明距离进行变化，使变异概率随着群体中的多样性程度而自适应调整，海明距离越小，概率越大，反之亦然。

4 仿真实验与结果分析

为验证计划编制模型和算法的有效性及效率，设计和实现了一个基于遗传算法的成像卫星计划编制原型系统［13］。针对实际的不同观测任务数据进行仿真实验，依据实际需求对成像卫星进行任务调度，主要包括以下方面:①卫星参数参考实际卫星特性设定;②卫星轨道数据由STK工具仿真计算得出;③卫星观测任务来自模拟的用户请求，观测任务数量为200;④地面站使用北京站、广州站、乌鲁木齐站和长春站，地理坐标依据城市坐标而定;⑤计划编制的时间段设为2013－03－2202:00:00到2013－03－2308:00:00;⑥使用随机生成的云量等级。

经过计算得出遗传算法的输入，即卫星摄影预案和地面站跟踪接收预案，如表1和表2所示。

表1 遗传算法输入—卫星1摄影预案

表2 遗传算法输入—地面站跟踪接收预案

设定遗传算法参数为:交叉概率0.85、变异概率0.08、最大世代数500代、群体规模100、染色体长度200。经过星地资源的冲突消解和优化分配，得到了最佳的观测方案，适应度值为7640.28，对应的卫星摄影计划和地面站跟踪接收计划如表3和表4所示。由于星上资源和地面接收资源的限制，算法自动将任务Task2、Task3和Task4的摄影预案删除，只保留了Task1和Task5，这样能保证整体的适应度值最大。

表3 遗传算法输出—卫星1摄影计划

表4 遗传算法输出—地面站跟踪接收计划

经遗传算法优化后的各观测方案很好地体现了在多个目标准则间的均衡考虑，优化解的分布性很好，不同的观测方案体现了各种目标准则下的优化结果和综合优化结果，有利于决策人员选择最终的卫星和地面任务计划。使用遗传算法来安排计划的效率远高于其他方法(如穷举法、贪婪法等)，基本有效地解决了在大量约束条件下合理安排卫星观测任务的问题，且制定的卫星摄影计划和地面站接收计划经过检验合理可行。

5 结束语

通过分析成像卫星计划编制中的星地资源分配问题，提出了一种复杂约束条件下成像卫星的资源调度方法，在此基础上设计了一种带约束的遗传算法应用模型，并将其应用于优化卫星任务计划的制定。原型系统仿真实验结果表明，该算法应用可满足成像卫星观测任务的多目标规划需求，很好地解决了成像卫星计划编制中的优化调度问题，提升了用户请求的满足程度，提高了卫星摄影资源及地面站跟踪接收资源的利用率。 ■

［1］陈国良，王煦法，庄镇泉，等.遗传算法及其应用［M］.北京:人民邮电出版社，2001.

［2］玄光男，程润伟.遗传算法与工程优化［M］.北京:清华大学出版社，2004.

［3］汪定伟，王俊伟.智能优化方法［M］.北京:高等教育出版社，2007.

［4］贺仁杰，李菊芳，姚锋，等.成像卫星任务规划技术［M］.北京:科学出版社，2010.

［5］玄光男，程润伟，唐加福.遗传算法与工程设计［M］.北京:科学出版社，2000.

［6］周明，孙树栋.遗传算法原理及应用［M］.北京:国防工业出版社，1999.

［7］杨启文，蒋静坪，张国宏.遗传算法优化速度的改进［J］.软件学报，2000，12(2):270 －275.

［8］戴晓晖，李敏强，寇纪松.遗传算法的性能分析研究［J］.软件学报，2001，12(5):742 －750.

［9］钱志勤，腾宏飞，孙治国.人机交互的遗传算法及其在约束布局优化中的应用［J］.计算机学报，2001，24(5):553－558.

［10］周明，孙树栋，彭炎午.用遗传算法规划移动机器人路径［J］.西北工业大学学报，1998，16(4):242 －246.

［11］周明，孙树栋，彭炎午.基于遗传模拟退火算法的机器人路径规划［J］.航空学报，1998，19(1):118 －120.

［12］刘大有，卢奕南，王飞.遗传程序设计方法［J］.计算机研究与发展，2001，38(2):213 －222.