应用于卫星自主任务调度的改进遗传算法

赵萍，陈志明

南京航空航天大学 航天学院, 南京 210016

应用于卫星自主任务调度的改进遗传算法

赵萍，陈志明﹡

南京航空航天大学 航天学院, 南京 210016

针对具有侧摆能力的对地观测卫星的自主任务调度问题，对卫星自主任务调度问题和约束条件进行了描述，针对卫星自主任务调度NP-hard的特点，构建了基于目标收益及多约束卫星任务调度模型。设计了一种改进的遗传算法，从遗传操作的各个部分进行算法优化。首先将小区间法应用于初始种群生成，保证了种群的多样性，并且交叉和变异算子均引入自适应概率；同时采用两代竞争技术来避免“早熟”现象，提高算法的效率和鲁棒性。算法还采用最优保留策略用来保存进化中的最优解，使得算法收敛于全局最优。对局部多冲突观测任务应用该改进遗传算法，并针对区域密集目标的观测问题设计了仿真试验，与传统模拟退火算法及免疫蚁群遗传混合算法进行了比较，验证了该算法的有效性和收敛效果。

对地观测卫星；卫星侧摆角；自主任务调度；建模；改进遗传算法；自适应概率

观测卫星是利用星载传感器，根据用户的需求对地面目标成像，具有观测效果好、覆盖区域广、持续时间长等特点，已经在环境监测，灾害预报以及军事作战等领域得到了应用[1]。

对地观测卫星调度问题的输入是来自用户的任务要求。每个任务有自己特定的有效时间窗口，在这些时间段以外，命令就没有意义了。但是由于各种资源、时间等约束，不一定所有的任务都能够被执行。所以，卫星在满足各种约束的情况下，应尽可能多完成请求的任务[2]。从卫星接收的所有观测任务请求中，根据星上资源以及卫星对任务的时间窗口约束，利用算法快速选择待观测的任务序列，完成对卫星观测任务的调度。所以，对地观测卫星调度的输出是无冲突待观测的任务序列。

随着卫星数量和观测任务数量的增多以及卫星机动能力的增强，任务调度问题的规模呈指数的增长。观测卫星的调度问题已经被证明是NP-hard问题，问题的指数爆炸特征明显，很难求解[3]。观测卫星的任务调度问题涉及许多非线性约束，求解目标不唯一，所以并不存在适用于所有问题的算法[4]。现有的研究一般将卫星的任务调度问题转化成组合优化问题进行求解。

文献[3]针对敏捷卫星提出的约束模型，比较了约束调度、动态调度以及局部搜索等求解算法。文献[5]构建了敏捷卫星任务调度的数学模型，用模拟退火算法和遗传算法相结合的混合遗传算法进行求解。文献[6]针对多星对区域目标的观测调度问题设计了贪婪随机变邻域搜索算法、禁忌搜索和模拟退火算法，提高了算法的求解效率。文献[7]设计了一种新的遗传算法并将该优化算法应用于实际的卫星任务调度问题模拟。偏置随机密钥遗传算法[8](BRKGA)可以有效地解决组合优化问题，文献[8]提出了一种混合解码的方法，并对敏捷地球观测卫星进行了试验。文献[9]提出了一种基于指标的多目标局部搜索算法(IBMOLS)解决多目标优化问题，并且将IBMOLS的结果与偏置随机密钥遗传算法的结果进行比较。也有学者对各种算法性能进行了比较分析，文献[10]在卫星任务调度中比较了模拟退火算法、遗传算法、爬山算法等性能。

从现有的研究可以看出，智能优化算法在求解卫星任务调度问题上有很大的优势。同时，现有的研究中，任务的调度模型都较为简单，没有考虑或简化了卫星侧摆角、转换时间等约束；很少有针对密集任务的观测调度算法[11]。针对这些问题，本文提出了快速计算观测卫星侧摆角的方法，对卫星自主任务调度问题构建了基于目标收益及多约束的任务调度模型，最后设计了一种改进的自适应遗传算法应用于卫星局部冲突观测任务的调度。并针对区域密集目标的观测问题设计了仿真试验，将试验结果与传统模拟退火算法及其他改进遗传算法进行了比较，验证了算法的有效性。

1 卫星对地观测侧摆角计算

为了扩大卫星对地观测的范围，通常在卫星上采用侧摆技术，使得卫星能够沿着垂直星下点轨迹的方向也进行观测[1]。卫星的侧摆角是指星载遥感器沿着垂直轨道方向转动与星地连线之间形成的夹角。如图1所示，假设观测的目标点在A(λ,φ)处，S是卫星的位置，O为地心，S′(λs,φs)是星地连线与地面的交点，并且AS′垂直于星下点轨迹，H为卫星的高度，Re为地球半径，FOV视场角，β为侧摆角。

图1 卫星对地覆盖示意Fig.1 Illustration of ground coverage of satellite

文献[1]给出了计算卫星侧摆角的方法。根据目标点和星下点的经纬度坐标，利用文献[12]中给出的方法求解侧摆角。具体方法如下：

该算法基于以下两点前提：1)弧度为1′的弧长在地球上对应的距离长度是1海里；2)1海里=1.852 km。首先，计算出AS′：

计算 arccos(·)的时候，如果是弧度要转换成角度进行计算AS′。

地心覆盖角∠AOS：

则侧摆角β：

2 任务调度问题的描述和模型建立

2.1 任务调度问题的描述

卫星对地观测的步骤如下：用户给出成像任务要求，可能包括不同的任务类型，不同的优先级等要求。卫星任务观测系统根据得到的任务信息，卫星自身位置信息以及星上传感器和可用能源约束进行相应的任务调度，最大限度地完成用户提交的任务请求。从上述过程可知，任务调度在整个卫星成像应用过程中起着关键作用，主要解决卫星资源的有效分配和调度。

传统的任务调度大多由地面站直接进行任务调度，然后向卫星传递执行指令。相比于传统的依赖于地面站的任务调度，星上自主任务调度有自己的优势：1)卫星的效能进一步提高。2)能够快速响应任务冲突。3)提高紧急任务的应对能力。4)减少对地面测控的依赖，卫星具有较高的自主能力。此外，对军用卫星来说，自主任务调度能够减少星地之间通信的概率，提高卫星的生存能力。

为了提高卫星的整体效能，本文采取一种星上自主调度算法，事先对卫星的姿态机动角度和相机成像时刻进行调度。对于敏捷卫星而言，多目标成像的时间和顺序都不再唯一。因此，有必要对多个目标的成像时间和顺序进行研究。同时对任务的优先级进行甄别，在任务出现冲突时，使高级别任务优先于低级别任务。

观测范围以及问题的假设如下:

敏捷卫星具有不止一维的自由度，能够绕俯仰、滚转、偏航三个轴变化。敏捷卫星的观测范围远大于普通的卫星，观测的时间也更为灵活，目标可以位于星下点之前或之后。所以任务成像的时间和顺序都不再唯一。

敏捷卫星自主任务调度问题是一个非常复杂的问题，涉及条件约束繁多，在解决问题时不可能考虑所有约束[14]。所以，在建立问题模型之前，做出以下合理假设。

1)假设卫星只携带一个星载传感器，并且任意时刻只能执行一个任务，不考虑中断去执行其他任务。

2)只考虑卫星的侧摆能力。

3)不考虑云层遮挡，天气变化等对任务调度的影响。

4)不考虑卫星工作时发生故障等问题。

2.2 问题建模

卫星自主任务调度问题建模主要是卫星根据获取的用户观测请求以及星上资源约束进行任务的观测调度，最大限度地完成观测任务。下面两部分主要介绍任务调度的星上约束以及任务调度的目标函数。

(1)约束条件

主要考虑的约束如下：

1)时间窗约束：

2)任意两次成像操作之间不能有交叠，任意两次拍摄之间必须有任务的准备时间，包括开机准备时间和卫星角度变换需要的时间等。

式中：ski为从任务k结束到任务i开始的准备时间。

3)侧摆角约束:

式中：endi为任务i的结束时间；Anglei为观测任务i时的侧摆角；v为卫星侧摆时的角速度。式(6)表示当前任务到下一次任务的时间要足够多来完成侧摆角转换。

4)太阳高度角约束:

式中：ASun,min为完成任务的最小太阳高度角；ai(t)为t时刻卫星执行任务i的太阳高度角。

5)能量约束：

式中：ei为完成任务i消耗的能量；εki为从任务k结束到任务i开始的准备操作消耗能量；E为可用的星上总能量；xi表示任务i是否被完成，1表示被完成，否则为0；xki表示从任务k到任务i的转换，存在转换则为1，否则为0。

6)星上存储容量约束：

式中：M为星上总存储容量；mi为完成任务i需要占用的容量。

(2)目标函数

卫星任务调度的目标是在给定的时间范围中，在满足卫星各类约束条件的情况下，尽可能获得更多的卫星任务完成收益。这里只考虑单一目标函数。任务调度的目标函数如下：

式中：Bi为完成任务i的收益，Bi≥0；αi是表示任务i的是否完成的二元变量，完成为1，否则为0。

最大化任务完成收益，这里面任务的收益Bi与观测任务的优先级成正比，优先级大的任务收益相对应较高。

(3)适应度函数

遗传算法中使用适应度来评价个体的性能用以指导搜索。适应度高的个体遗传到下一代的概率大一些。本文的目标函数是最大值函数，所以定义一个与目标函数相近的适应度函数来评价个体的性能。适应度函数定义如下：

式中：Bi表示完成任务i的收益，Bi≥0；Ci表示任务i是否被选中，1表示被选中完成，0则表示没有。

3 改进的遗传算法

卫星的任务调度问题已经被证明是一种NP-hard问题，很难通过解析或计算求解最优解。许多研究已经成功将各种改进过的遗传算法应用于解决卫星的任务调度问题[14-15]。遗传算法的主要步骤是将问题的解空间进行编码，构成染色体，再生成一个由染色体产生的初始种群，根据需要优化问题的目标函数来构造适应度函数，对种群对环境的适应度进行评估。适应度高的个体被保留下来，经过交叉、变异等遗传算子产生新的更加优异的种群，不断进行迭代，最终收敛到一个比较好的解，这个解接近问题的最优解。遗传算法作为一种优化方法，也存在自身的局限性：1)遗传算法容易出现过早收敛现象(早熟)；2)在快要接近最优解时在最优解附近收敛较慢等。本文在遗传算法的基础上进行一定的改进，提高算法的收敛性能。将该算法应用到卫星任务调度模型的求解。

3.1 编码和初始种群生成

i∈1,2,…，N

染色体编码结构的一个简单示例如下所示：

本文采用的产生初始群体的方法叫小区间生成法[17]。具体的步骤是：把优化区间分成若干个小区间，在各个小区间内随机产生一个初始个体。这样生成的初始群体会均匀分布在整个空间，保证了初始群体的丰富性，增强了搜索收敛于全局最优的可能性。同时初始种群中保留全1个体，这是无约束下最优解。

3.2 遗传算子

(1)复制操作

为了保证较好的个体不会因为遗传操作被破坏，采取两代竞争遗传算法[18]的操作。将父代的个体全部复制保留与子代一起进行选择操作。

(2)交叉算子

本文中采用的是优选的交叉操作，在父代中随机产生两个个体，保留适应度较大的个体，将上面的操作进行两次，得到两个保留下来的个体。将得到的两个体格进行自适应单点交叉。交叉概率表示如下:

(12)

式中：fc为两个交叉个体中的适应度较大的值；fmax,favg分别是群体中的个体适应度最大值和平均值。

(3)变异算子

遗传算法使用交叉算子从全局的角度出发找到了一些较好的个体编码结构，它们已经接近最优解了。但使用交叉算子无法对局部细节进行搜索。使用变异算子能够改善遗传算法的局部搜索能力。本文采用基本位变异，以变异概率指定变异点做变异操作，在该算法中就是进行取反操作，0变成1或者1变成0。在该算法中采用的是自适应变异概率，即：

式中：Pm1=0.1；Pm2=0.001； fmax为群体的最大适应度；favg为群体的平均适应度值；fc为要变异的个体的适应值。

(4)选择算子

上文提到采用两代竞争遗传，将父代与产生的子代一起进行选择操作。具体的步骤如下：1)将最优个体保存下来，将两代个体中适应度最大的个体直接保存下来。这种方法称为精英保存策略[19]，研究表明，保留最优个体的遗传算法以概率1收敛到全局最优解。该步骤保证了全局收敛性。2)两两竞争选择，将除了最优个体以外的全部个体进行两两竞争选择，随机选出两个个体，保留适应度较大的。重复该操作，一直到产生完整的下一代。

(5)终止条件

该算法的终止条件为种群稳定，规定最大迭代次数，若群体中最大适应度与平均适应度差值小于10-6或者达到最大迭代次数则终止。

4 算法仿真

在STK中设置仿真场景，总共设置了500个观测目标，500个待观测目标主要是针对单圈次观测，某块区域的密集观测，示意如图2所示。算法用Matlab 2013a在1.8 GHz CPU,4G内存的计算机上实现。设定卫星的高度为500 km，卫星的视场角为8°，侧摆能力为40°，卫星机动角速度为2(°)/s。卫星模型是J4扰动模型，考虑可见光对观测影响。将STK与Matlab互联，在Matlab中获取卫星和目标点的参数，用上面提出的算法进行仿真。同时将改进的遗传算法的仿真结果与传统的模拟退火算法以及文献[13]中提出的免疫遗传蚁群混合算法仿真结果进行比较。

图2 500个观测目标与星下点轨迹示意Fig.2 Illustration of 500 targets and ground track

500个目标点中单圈次只有96个目标点在给定的时间内可以观测到。对于可观测96个目标，按照可见时间窗口的开始时间进行排序得到任务序列。对应于每个观测目标，给定对应的任务收益进行仿真。

图3是该算法一次仿真迭代的过程，是种群平均适应度和最大适应度随着迭代次数的变化。从图3可以看出初始种群因为保留了所有任务均选中的全1个体，所以最大适应度值最大。因不满足条件很快被放弃，种群迭代初始的适应度比较低，但是经过上述改进的遗传算法，一段时间内上升幅度较大，但到迭代最后则趋于平稳。

表1是为了比较该算法与模拟退火算法(SA)与免疫遗传蚁群混合算法(IACOGA)的仿真结果，采用同样的数据源进行模拟退火算法和免疫遗传蚁群混合算法进行仿真。从表1可以看出，改进遗传算法的收益百分比>免疫遗传蚁群混合算法收益百分比>模拟退火算法收益百分比。而达到全局收敛的时间关系则是，改进遗传算法收敛时间<模拟退火算法收敛时间<免疫遗传蚁群混合算法收敛时间。由表1可以看出，模拟退火算法的收益百分比最差，而免疫遗传蚁群混合算法的收益百分比与本文提出的改进遗传算法相近，但是，IACOGA算法的运行时间较长，使用蚁群算法改进遗传算法，虽然可以得到较好的初始解，但是时间代价很大。而本文的算法在达到较好的收益率的同时，运行时间很少，收敛速度很快。

图3 种群最大适应度和平均适应度的变化值Fig.3 Maximum fitness and average fitness of every population

仿真次数AGA仿真时间/sAGA收益百分比/%SA仿真时间/sSA收益百分比/%IACOGA仿真时间/sIACOGA收益百分比/%10 9993 81 6787 9347 6293 621 0194 41 7688 5316 6491 131 1195 21 7589 9333 6793 441 0393 31 6886 2336 0093 351 0195 41 7186 4319 0591 861 0395 81 7086 8334 0192 271 0695 41 7487 8339 7091 681 1292 11 6888 0335 6192 690 9693 51 6985 2314 4291 8101 2092 91 6485 9316 7291 9

5 结束语

观测卫星的自主任务调度涉及到多种组合约束问题，同时要求卫星能够快速对得到的任务请求进行调度，所以对任务调度算法的要求较高。对于任务可见窗口有重叠，任务比较密集的卫星观测调度问题，应该要考虑卫星侧摆能力与到达指定侧摆角度需要的机动时间等约束。本文给出了快速计算侧摆角的方法，并且对卫星对地观测问题进行基于各类约束以及任务完成收益的建模，设计了改进遗传算法来求解，使用小区间法保留初始种群的多样性，并且对于遗传算子均引入自适应概率，同时采用两代竞争算法保证优的个体被保存，实施最优保存策略。试验验证，该算法相较于传统的模拟退火算法以及免疫遗传蚁群混合算法，具有更好的收敛速度和全局收敛性。

References)

[1] 贾志军,杨敏,孙洋,等. 卫星对地观测中的侧摆策略[J]. 四川兵工学报,2014(7):128- 130.

JIA Z J, YANG M, SUN Y, et al.Swinging strategy on Earth observing satellites[J]. Journal of Sichuan Ordnance, 2014(7):128-130(in Chinese).

[4] 贺仁杰, 高鹏,白保存,等. 成像卫星任务规划模型、算法及其应用[J]. 系统工程理论与实践,2011(3):411-422.

HE R J, GAO P, BAI B C, et al. Models,algorithms and applications to the mission planning system of imaging satellites[J]. Systems Engineering-Theory & Practice,2011(3):411-422(in Chinese).

[5] 李玉庆,徐敏强,王日新.三轴稳定卫星点目标观测任务优化调度技术[J].吉林大学学报(工学版),2008,38(6):1447-1451.

LI Y Q, XU M Q,WANG R X, et al. Scheduling observations of spot object of three-axis stabilized satellites[J]. Journal of Jilin University (Engineering and Technology Edition), 2008, 38(6):1447-1451(in Chinese).

[6] 阮启明. 面向区域目标的成像侦察卫星调度问题研究[D].长沙:国防科技大学,2005.

[7] BAEK S, HAN S, CHO K, et al. Development of a scheduling algorithm and GUI for autonomous satellite missions[J]. Acta Astronautica, 2011, 68(7): 1396-1402.

[8] TANGPATTANAKUL P, JOZEFOWIEZ N, LOPEZ P. Multi-objective optimization for selecting and scheduling observations by agile Earth observing satellites[M]∥Parallel Problem Solving from Nature-PPSN XII. Berlin: Springer, 2012: 112-121.

[9] TANGPATTANAKUL P, JOZEFOWIEZ N, LOPEZ P. A multi-objective local search heuristic for scheduling Earth observations taken by an agile satellite[J]. European Journal of Operational Research, 2015, 245(2): 542-554.

[10] GLOBUS A, CRAWFORD J, LOHN J, et al. Scheduling Earth observing fleets using evolutionary algorithms: problem description and approach[C]∥Proceedings of the 3rd International NASA Workshop on Planning and Scheduling for Space, 2002:27-29.

[11] 郭浩,邱涤珊,伍国华,等. 基于改进蚁群算法的敏捷成像卫星任务调度方法[J]. 系统工程理论与实践,2012(11):2533-2539.

GUO H, XIU D S,WU G H, et al. Tasks scheduling method for an agile imaging satellite based on improved ant colony algorithm[J]. Systems Engineering-Theory & Practice, 2012(11): 2533-2539(in Chinese).

[12] Geoscience Australia. Distance calculation algorithms[EB/OL].(2013-05)[2016-01-08].http:∥www.ga.gov.au/sc-entific-topics/positioning-navigation/geodesy/geodetic-techniques/distance-calculation-algorithms.

[13] 郝会成,姜维,李一军. 基于混合遗传算法的敏捷卫星任务规划求解[J]. 科学技术与工程,2013(17):4972-4978.

HAO H C, LI W, LI Y J. Mission planning for agile Earth observation satellites based on hybrid genetic algorithm[J]. Science Technology and Engineering, 2013,17: 4972-4978(in Chinese).

[14] 向仍湘. 敏捷卫星任务调度技术研究[D].长沙：国防科学技术大学,2010.

[15] DJAMAL H, MICHEL V. Saturated and consistent neighborhood for selecting and scheduling photographs of agile Earth observing satellite[C]. MIC2003: The Fifth Metaheuristics International Conference.

[16] VERFAILLIE G, LEMATRE M. Selecting and scheduling observations for agile satellites: some lessons from the constraint reasoning community point of view[C]. The Seventh International Conference on Practical and Principles of Constraint Programming. France, 2001.

[17] 高玮,尹志喜. 现代智能仿生算法及其应用[M].北京:科学出版社,2011: 58-61.

[18] 于海斌,王浩波,徐心和.两代竞争遗传算法及其应用研究[J].信息与控制,2000,29(4): 309-314.

YU H B, WANG H B, XU X H. A genetic algorithm with competitive selection between adjacent two generations and its applications to tsp[J]. Information and Control, 2000,29(4): 309-314 (in Chinese).

[19] 李小平, 王风儒. 优解保留遗传算法收敛性研究[J].电机与控制学报,2000,4(1): 52- 54.

LI X P, WANG F R. Research on convergence of elitist genetic algorithm[J]. Electric Machines And Control, 2000, 4(1): 52-54 (in Chinese).

(编辑：高珍)

An adapted genetic algorithm applied to satellite autonomous task scheduling

ZHAO Ping，CHEN Zhiming*

College of Astronautics, Nanjing University of Aeronautics & Astronautics, Nanjing 210016, China

Aiming at solving the problem of autonomous task scheduling of earth observing satellites with the ability of swinging,satellite autonomous task scheduling problem and constraints were described.A single-objective multi-constraints model was built according to the NP-hard character of satellite autonomous task scheduling problem.An adapted genetic algorithm was designed.All of the genetic operations of genetic algorithms were optimized. Firstly, mini-region method was applied to generate of the original population to ensure the diversity of population. Adaptive probabilities were used for crossover and mutation operation. Two generations competitive technology was used to avoid the premature and improve the efficiency and the robustness of the algorithm. The algorithm also uses the optimization reserved strategy to preserve the optimal solution, which makes the algorithm converge to the global.The adapted genetic algorithm was applied to the local multi-conflict tasks observation and designed simulation experiments of the observation of regional dense targets. The results are compared with results of simulated annealing algorithm and immune ant colony genetic algorithm,and it shows that the proposed algorithm is more effective and it has a better convergence.

Earth observation satellite；satellite swinging angle；autonomous task scheduling；modeling；adapted genetic algorithm;adaptive probability

10.16708/j.cnki.1000-758X.2016.0064

2016-05-04；

2016-07-13；录用日期：2016-08-22；

时间：2016-12-16 11:29:09

http:∥www.cnki.net/kcms/detail/11.1859.V.20161216.1129.006.html

国家自然科学基金(61403197)；江苏省自然科学基金(BK20130816/BK20140830)

赵萍(1991-)，女，硕士研究生，zhaoping_nuaa@163.com,研究方向为编队卫星在轨自主任务规划

*通讯作者：陈志明(1984-)，男，讲师，lchenzhiming@nuaa.edu.cnl，研究方向为分布式卫星测控技术、星载计算机设计管理

赵萍,陈志明.应用于卫星自主任务调度的改进遗传算法[J].中国空间科学技术,2016,36(6)：47-54.

ZHAOP,CHENZM.Anadaptedgeneticalgorithmappliedtosatelliteautonomoustaskscheduling[J].ChineseSpaceScienceandTechnology, 2016,36(6)：47-54(inChinese).

TP301.6

A

http:∥zgkj.cast.cn