基于差分进化算法的卫星任务未安排原因分析
2017-10-16董理君
孙 龙，李 晖，赵 曼,董理君,吴 杰
(中国地质大学(武汉) 计算机学院，湖北 武汉 430074)
基于差分进化算法的卫星任务未安排原因分析
孙 龙，李 晖，赵 曼,董理君,吴 杰
(中国地质大学(武汉) 计算机学院，湖北 武汉 430074)
在卫星任务规划过程中，由于卫星资源有限、卫星约束限制与任务冲突导致卫星任务未安排，在实际工程中需要确切地了解其任务未安排的具体原因。针对以上问题，提出了一种基于差分进化算法的卫星任务未安排原因分析方法，通过将未安排的任务插入原观测序列，采用差分进化算法演化接收窗口，并对演化结果进行约束处理及评价，得到其在规划过程中未安排的原因。实验结果表明，该方法能够准确给出未安排任务的原因，方便用户对任务进行决策。
差分进化算法；卫星任务规划；约束处理及评价；卫星任务未安排原因
AbstractIn the mission planning process,satellite missions are not scheduled because the satellite resource is limited and the satellite constraints conflict with the mission.It’s required in actual projects to understand exactly the reason for not scheduling the mission.To solve the above problem,an analysis method based on differential evolution algorithm is proposed.By inserting the unscheduled task into the original observation sequences,using the differential evolution algorithm to evolve the receiving window,and performing constraint processing and evaluation of the evolutionary results,the reason why the task is not scheduled is obtained.Experiment results show that this method can precisely give the reasons why a task is not scheduled,making it convenient for users to make decisions on the task.
KeywordsDE algorithm;mission planning;constraint processing and evaluation;reason for not scheduling satellite missions
0 引言
对地观测卫星成像[1]是卫星在距离地球一定轨道高度上运行，所载有效载荷根据需求对地球上特定区域进行观测，在飞入地面站上空时，把观测到的数据传输到地面接收站，地面接收站对接收到的数据进行处理和加工得到用户所需产品和数据。但受限于卫星有限的资源，要充分完成各个用户的成像需求是非常困难的，必然会导致卫星任务在规划的过程中被调整甚至被删除[2]，当卫星任务未安排时，有必要明确给出卫星任务未安排的原因，方便用户了解卫星规划任务是由于哪些约束限制导致任务未安排。
针对卫星任务规划，目前处理的主流方法是采用群智能优化算法[3]来解决多星任务规划这类时效性较强的问题[4]，如Pemberton[5]提出了基于动态规划思想的迭代方法，按照某种规则对成像目标排序分组，将前面分组的调度结果作为后面分组调度的约束进行求解。郭浩[6]等针对敏捷卫星任务调度问题，综合考虑卫星工作时长、卫星姿态调整时间、能量和固存容量等约束条件，提出了一种改进的蚁群算法对卫星任务规划进行求解。同时，大量研究实验表明[7]，禁忌搜索算法[8-9]、遗传算法[10]和模拟退火算法[11]在成像卫星对地观测任务规划问题中表现良好，但上述卫星规划算法，在任务规划的过程中，针对卫星任务规划未给出任务未安排原因，均只有最终的规划结果，无法直观反映卫星任务规划方案，同时，随着用户成像需求的日益增加、卫星数量的增加、不同载荷的成像卫星的出现[12]，对于任务未安排原因的需求也将变得越来越明显。
为补充卫星任务规划过程中对于未安排任务的处理，增加卫星任务规划的科学性及可靠性，本文提出了一种针对卫星任务未安排原因的分析模型，在保证不改变原有规划方案的基础上，对未安排的任务进行未安排原因分析，对实际工程提供了一系列参考方法，具有指导意义。
1 卫星任务未安排原因分析模型
1.1 模型表示
卫星任务规划是根据用户任务需求，在满足卫星资源约束的条件下，尽可能充分利用卫星资源，完成用户提出的任务需求，制定卫星任务的观测和接收计划[13]。对卫星任务未安排原因的分析依赖于卫星任务规划，区别在于是针对已知的观测任务进行规划，在任务规划的过程中给出具体的卫星任务未安排的原因。
因此，卫星任务未安排原因的分析实质上与卫星任务规划是同一类问题，即带约束的组合优化问题[14]。
一个带约束的组合优化问题P可以定义为4元组P=
对于本文中的卫星任务未安排原因分析模型，定义如下：
① 变量集合V：是由规划预案中的观测元任务和未安排的元任务、接收元任务组成；
② 值域集合D：对观测元任务而言，其值域为任务的选择情况，对接收元任务而言，其值域为卫星可选的数传方式；
③ 约束集合C：表示卫星任务规划中所涉及的约束，这些约束包括指令模板冲突和数传方式约束等；
④ 优化目标集合D：表示卫星任务规划的优化目标，优化目标可以是卫星完成任务数最多、观测时长最长、适应值最高等。
1.2 求解过程
对卫星任务规划的求解过程而言，由于卫星资源的特殊性、地面观测目标的复杂性和地面接收站的分散性，卫星执行的成像任务会受到诸多的限制[15]。因此，本文在求解卫星任务未安排原因时，采用的处理方式是将未安排的任务逐个插入原预案中，通过预处理、演化接收窗口的方式找到任务未安排的原因。
基于差分进化算法的卫星任务未安排原因的基本求解过程可以划分为3个主要阶段，如图1所示。
图1 卫星任务未安排原因求解模型
第1阶段，通过读取常规任务规划得到的卫星任务规划预案，包括卫星观测任务预案和卫星接收任务预案信息，确定原规划预案中观测任务的选择情况。
第2阶段，主要分为预处理、约束检验及任务评价2个操作，最终得到任务未安排原因。下面对第2阶段进行的操作进行描述。
(1) 任务预处理
任务预处理操作主要针对未安排的观测元任务的一些属性进行过滤，排除一些由于任务侧摆角度、接收资源等限制而导致任务未安排的原因，主要有以下几点：
① 相同需求相同轨道的任务。将观测预案中安排了的观测元任务按照相同需求相同轨道对任务进行分类，检测当前未安排的任务是否和观测预案中某个安排了的任务是同轨同需求，如果是则说明是由于相同需求相同轨道的任务只能做一个而导致该任务未安排。
② 相同需求相同子需求的非监测类任务。检测方法与①类似，如果待检测的未安排任务与观测预案中的元任务是相同需求的非监测类任务，则说明是由于相同需求相同子需求的非监测类任务只能做一个而导致该任务未安排。
③ 最大侧摆角度。检测该未安排的观测元任务侧摆角是否超出卫星的最大侧摆角度，如果是则说明是由于侧摆角度超出限制而导致该任务未安排。
④ 接收资源。检测该未安排的观测元任务后面所有的接收窗口时间，去除原接收预案中使用的接收窗口，得到对于该任务可用的接收窗口，判断是否能够回放该任务所需要的接收时长，如果不能则说明是因为接收资源不足导致该任务未安排。
(2) 任务约束检验及评价
如果通过预处理未能得到任务未安排的原因，那么可以通过插入该任务找到由于其他约束项而导致任务未安排的原因。常规任务规划在得到了观测预案和接收预案后，逐个选择未安排的任务进行插入，得到观测元任务集(观测预案中规划出的观测元任务和当前插入的未安排的观测元任务)，即固定了染色体的观测部分。染色体接收部分，是将所有的接收窗口进行随机选择，采用差分进化算法进行处理。对接收演化后得到的最优接收窗口进行选择，然后对得出的最优染色体进行各类约束处理，当遇到不满足其中某项约束时，终止执行，给出任务未安排的具体约束冲突原因。
这些约束冲突包括：单圈次侧摆次数冲突、单圈次工作时间冲突、指令模板冲突、任务关机时间约束冲突和卫星固存约束冲突。
第3阶段，是根据第2阶段获取的卫星未安排原因，将其写入观测预案中，供用户进行查阅。
2 差分进化算法对模型的应用
差分进化算法[16]是一种基于群体差异的启发式搜索算法，是通过模仿生物群体内个体间的合作与竞争产生的启发式群体智能来指导优化搜索的一种算法。
针对卫星任务未安排原因分析的模型，本文采用差分进化算法来演化卫星任务的接收窗口，在任务规划的过程中给出任务未安排的原因。
2.1 编码设计
卫星任务未安排原因分析的求解对象是如何将未安排的观测元任务在不影响原预案的情况下合理分配接收窗口，使其完成任务规划，若不能完成，则给出不能安排的具体原因，故编码方案采用整数编码，一条染色体表示元任务的状态，编码设计如图2所示。
① 染色体的结构主要由观测元任务序列和接收元任务序列拼接而成，观测元任务序列的基因位表示任务的选中状态，接收元任务序列的基因位表示卫星选择的数传方式。
② 基因位的取值范围为[0,di)，其中对观测元任务序列，di取0或1，表示观测任务的选中状态；接收元任务序列，表示卫星任务不同数传方式对应的序号。染色体初始化时，染色体基因位中观测部分序列全部置1，设置为全选中状态，接收部分序列中的数值随机产生。
③ 染色体的长度为观测任务序列的长度和接收任务序列的长度之和。
图2 染色体的编码设计
2.2 应用过程
差分进化算法在分析卫星任务未安排原因的过程中主要用于演化接收窗口，得到最优的染色体，最终对染色体进行解码，通过约束处理判断染色体是否满足约束，不满足约束则给出该原因而导致任务未安排。算法演化接收窗口的过程如图3所示。
在通过差分进化算法得到接收窗口后，对最优染色体解码后的预案进行约束处理及评价，在约束处理及评价过程中，依次对任务进行单个的约束项处理，如先检测指令模板约束，再检测单圈次侧摆次数约束等，一旦检测不通过，则输出该原因作为待检测任务的未安排原因。
图3 差分进化算法演化接收窗口流程
3 实验及结果分析
3.1 测试数据
测试数据选自卫星任务规划的观测元任务预案，针对同一方案编号，对应的观测元任务会选择一定的数传方式进行数传，若其数传模式为空，则表示该任务未安排，此时需要对其未安排原因进行分析，某一预案相关信息如表1所示。
表1 规划预案信息
FABHGCYRWBHSCMSGCKSSJGCJSSJ917113899记录2014-02-1910:45:302014-02-1910:50:30917113913Null2014-02-2113:12:402014-02-2113:18:40917113901记录2014-02-1912:57:102014-02-1912:58:10917113907实传2014-02-1915:37:432014-02-1915:43:37917113903记录2014-02-2001:26:002014-02-2001:31:00917113908记录2014-02-2011:09:342014-02-2011:18:34917113910实传2014-02-2014:26:002014-02-2014:33:00917113904记录2014-02-2016:15:202014-02-2016:18:50917113912记录2014-02-2111:33:232014-02-2111:42:33917113905实传2014-02-2114:49:022014-02-2114:57:02917113902Null2014-02-1914:02:002014-02-1914:08:00917113906Null2014-02-2200:36:002014-02-2200:41:00917113909Null2014-02-2012:49:382014-02-2012:55:38917113900记录2014-02-1902:24:202014-02-1902:30:30
本文所采用的符号含义如下：FABH：方案编号；GCYRWBH：待检测的元任务编号；SCMS：数传方式；GCKSSJ：观测开始时间；GCJSSJ：观测结束时间；WAPYY：未安排原因；GCXQBH：观测需求编号；GDQH：轨道圈号；ZXQBH：子需求编号；XJYQ：相机要求；GCLX：观测类型。
3.2 算法参数设置
由于采用差分进化算法演化接收窗口，而差分进化算法对遗传算子的取值有很大的依赖性，不同的算子演化效果有着明显的不同。当种群大小设置较大时，算法收敛速度较缓，规划效率比较低。迭代次数的选择也是需要慎重的，当迭代次数过大时会影响规划速度，迭代次数过低会导致不能收敛到全局最优。所以，在演化接收窗口算法的参数选择上，本文做了大量测试，最终确定相关参数如下：种群大小：100个个体；迭代代数：50代；变异概率：0.8；拉伸因子：0.7。
3.3 实验结果与分析
为了对各种任务未安排原因均进行测试，本文进行了大量的实例测试，将其分为2个测试实例集，分别为预处理未安排原因测试集、约束处理及评价未安排原因测试集。
3.3.1 测试用例1
未安排任务通过预处理操作找到的部分任务未安排原因如表2所示。
表2 观测任务规划预案
FABHGCYRWBHWAPYY90715071相同需求、相同轨道、相同载荷的任务只能做一个,与编号为15074的观测元任务冲突!110216587相同需、相同轨道、相同载荷的任务只能做一个,与编号为16658的观测元任务冲突!910544101相同需求、相同轨道、相同载荷的任务只能做一个,与编号为44102的观测元任务冲突!910444103相同需求、相同轨道、相同载荷的任务只能做一个,与编号为44104的观测元任务冲突!923044106相同需求、相同子需求、非调查类点目标的任务只能做一个,与编号为44105的冲突!924344107相同需求、相同子需求、非调查类点目标的任务只能做一个,与编号为44110的冲突!
从表2中可以得到部分任务未安排的原因，为了验证结果的正确性，部分观测任务以及与之冲突的观测任务信息如表3和表4所示。
表3 待检测任务与原预案中任务
GCYRWBHGCXQBHGDQHZXQBHXJYQ15071338745421A相机15074338745421A相机165873361,336247221,1A相机166583361,336247221,1A相机4410136036401B相机4410236036401B相机4410336036381B相机4410436036381B相机4410636036401B相机4410536036401B相机
表4 待检测任务与原预案中任务
GCYRWBHGCXQBHZXQBHGCLX4410636031其他4410536031其他4410736031定标4411036031定标
表3和表4可以看出，未安排的任务与观测预案中规划的观测任务的需求编号、子需求编号和观测类型发生冲突，可以验证给出的未安排原因的正确性。
通过预处理的方式可以将不参与规划的约束项导致任务未安排原因排查出来，这种方式具有十分高效的特点。
3.3.2 测试用例2
在预处理排查部分卫星任务未安排原因时，只是针对观测元任务自身的属性进行初步过滤，并未真正采用差分进化算法进行规划求解。当预处理操作无法得出任务未安排原因时，需要采用约束处理及评价的方式找到任务未安排的原因。
约束处理及评价处理排查任务未安排原因的部分规划数据如表5所示。
表5 约束处理及评价排查任务未安排原因测试数据
FABHGCYRWBHGCKSSJGCJSSJWAPYY8908440602015-04-1705:33:002015-04-1705:33:30关机时间冲突!6420352402014-09-3009:54:542014-09-3010:05:00常规任务数传调整冲突1269179622014-03-2010:57:022014-03-2011:06:02常规任务指令模板冲突9234440602015-04-1705:33:002015-04-1705:33:30观测时间冲突9229160072014-03-0519:37:002014-03-0519:39:00数传模式不满足约束!9067440762015-04-1513:05:002015-04-1513:08:00单圈次侧摆次数超出限制!1074161512014-03-1011:48:162014-03-1011:58:50固存溢出或无回放窗口9119440792015-04-1512:00:002015-04-1512:05:05单圈次工作时间超出限制!8943440752015-04-1513:05:002015-04-1513:05:30接收窗口不足!
以表5中规划预案9119中观测元任务编号为44079的观测元任务分析为例，参与规划的任务有18个，规划结果中，安排了10个，其中编号为44079的观测元任务被删除。
被删除的原因分析如下：对比编号为44079号的任务，其观测开始于2015-04-15 12:00:00，其观测时长有305 s，查看其接收计划，在其之前有接收计划，开始于2015-04-15 11:30:00，接收时长有480 s，二者相距时间不到1 h，在一个圈次内，如2个同时安排，单圈工作时间约束条件限制必然使得此接收提前结束，进而引起在编号为44079的观测任务之前的数传任务没有完整的下传，从而导致固存无法在前一个任务接收完后进行清空固存操作，固存一直被占用而接近耗尽，最终导致编号为44079号的任务因没有充足的固存而无法进行观测，因此编号44079的任务必须删除。
3.4 实验结论
通过对比分析实验结果，得出以下结论：
① 基于差分进化算法的卫星任务规划分析模型能有效排查在任务规划过程中某些任务的未安排原因，且测试过程中对任务未安排的原因分析的结果与预期分析一致；
② 在进行约束处理及任务评价排查任务未安排原因时，需要借助差分进化算法演化接收窗口，采用这种方式能保证在拥有足够的接收窗口供观测元任务使用时，最大化完成任务数，即不改变原始预案的结果，同时能分析出任务未安排的原因。
4 结束语
本文根据实际工程需要，提出了一种基于差分进化算法的卫星任务未安排原因分析模型，并设计了实验数据进行了测试。测试结果表明，本文提出的基于差分进化算法的卫星任务未安排原因分析模型能有效地求解卫星规划过程中关于某些任务未安排问题。本文展示了部分测试数据规划出来的任务未安排原因，通过对其未安排原因分析，验证了本文提出模型和处理方法的有效性及正确性。因而在实际工程应用中，这种基于差分进化算法的卫星任务未安排原因分析模型具有一定的应用价值。
本文对模型的构建比较简单，模型考虑的约束项仅仅列出了个别项，同时，给出的任务未安排原因没有特别详尽具体，在后续的研究中，还需要扩充模型，针对不同的卫星添加不同的约束项，使其具有通用性，给出更为详尽具体的任务未安排原因。
[1] 顾中舜,陈英武.对地观测卫星任务规划问题研究[J].飞行器测控学报,2007,26(6)：7-13.
[2] 贺仁杰,高鹏,白保存,等.成像卫星任务规划模型,算法及其应用[J].系统工程理论与实践,2011,31(3)：411-422.
[3] HABET D,VASQUEZ M.Solving the Selecting and Scheduling Satellite Photographs Problem with a Consistent Neighborhood Heuristic[C]∥IEEE International Conference on Tools with Artificial Intelligence,IEEE,2004:302-309.
[4] 韩伟,张学庆.一种基于离散粒子群的多星任务规划算法[J].无线电工程,2015,45(1):1-4.
[5] PEMBERTON J C,GREENWALD L G.On the Need for Dynamic Scheduling of Imaging Satellites[J].International Archives of Photogrammetry Remote Sensing and Spatial Information Sciences,2002,34(1)：165-171.
[6] 郭浩,邱涤珊,伍国华,等.基于改进蚁群算法的敏捷成像卫星任务调度方法[J].系统工程理论实践,2012,32(11)：2533-2539.
[7] LEMA TRE M,VERFAILLIE G,JOUHAUD F,et al.Selecting and Scheduling Observations of Agile Satellites[J].Aerospace Science & Technology,2002,6(5):367-381.
[8] LIN W C,LIAO D Y.A Tabu Search Algorithm for Satellite Imaging Scheduling[J].Systems,Man and Cybernetics,2004 IEEE International Conference on IEEE,2004(2)：1601-1606.
[9] CORDEAU J F,LAPORTE G.Maximizing the Value of an Earth Observation Satellite Orbit[J].Journal of the Operational Research Society,2005,56(8):962-968.
[10] WOLFE W J,SORENSEN S E.Three Scheduling Algorithms Applied to the Earth Observing Systems Domain[J].Management Science,2000,46(1):148-166.
[11] 徐欢,祝江汉,王慧林.基于模拟退火算法的电子侦察卫星任务规划问题研究[J].装备指挥技术学院学报,2010,21(3)：62-66.
[12] 韩琼.多星联合成像任务规划技术研究[D].北京:中国科学院大学,2013.
[13] 姜维,郝会成,李一军.对地观测卫星任务规划问题研究述评[J].系统工程与电子技术,2013,35(9)：1878-1885.
[14] 姜维,庞秀丽,郝会成.成像卫星协同任务规划模型与算法[J].系统工程与电子技术,2013,35(10)：2093-2101.
[15] 王军民,王鹏,李菊芳.成像卫星鲁棒性调度策略研究[J].系统工程与电子技术,2010,32(1):109-114.
[16] 刘波,王凌,金以慧.差分进化算法研究进展[J].控制与决策,2007,22(7)：721-729.
ResearchonDifferentialEvolutionAlgorithmforAnalysisofReasonforNotSchedulingSatelliteMissions
SUN Long,LI Hui,ZHAO Man,DONG Li-jun,WU Jie
(SchoolofComputerScience,ChinaUniversityofGeosciences,WuhanHubei430074,China)
TP302.1
A
1003-3106(2017)11-0067-06
孙龙男，(1990—)，硕士研究生。主要研究方向：智能计算与智能信息处理。
10.3969/j.issn.1003-3106.2017.11.15
孙龙,李晖,赵曼,等.基于差分进化算法的卫星任务未安排原因分析[J].无线电工程,2017,47(11):67-72.[SUN Long,LI Hui,ZHAO Man,et al.Research on Differential Evolution Algorithm for Analysis of Reason for Not Scheduling Satellite Missions[J].Radio Engineering,2017,47(11):67-72.]
2017-01-10
湖北省自然科学基金资助项目(2016CFB278)。
李晖女，(1967—)，教授，硕士生导师。主要研究方向：智能计算与智能信息处理。
