一种基于离散粒子群的多星任务规划算法

韩 伟，张学庆

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

0 引言

空间遥感技术自1962年诞生以来，全球已发射了500余颗对地观测卫星，是目前世界上发射数目最多、应用范围最广、最具代表性的一类卫星。我国的卫星对地观测事业历经30余年的发展，取得了长足的进步。目前，我国已发射的对地观测卫星超过50颗，形成了气象、资源、海洋和环境减灾四大民用系列对地观测卫星体系，可以覆盖我国的陆地和海域的全部，以及周边国家和地区，总面积超过1 500万平方千米。

在2006年公布的《中华人民共和国国民经济和社会发展第十一个五年规划纲要》中将“高分辨率对地观测系统”列为16个重大科技专项与重大科技基础设施之一。预计在2020年，我国将形成全天候、全天时、全球覆盖的对地观测能力。

随着成像任务需求的快速增长、任务类型的复杂化和多样化，以及对地观测卫星的数量及种类的逐步增加，任务规划的复杂度大大增加，早期的卫星独立管控模式已经无法满足未来的需要，必须将多颗成像卫星进行综合规划调度。

因此，如何在多星多任务的情况下，充分利用对地观测卫星、合理规划和调度卫星资源、优化卫星任务配置，是一个重要而迫切需要解决的问题。

多星任务规划问题是NP-hard问题［1］，其求解空间随着任务数和资源数量的增加而迅速增加，针对大规模的任务规划问题，无法在合理的时间内计算最优解。而针对多星任务规划这类时效性较强的问题，在合理时间内得到问题的近似最优解更有实际意义。

群智能算法是一类卓有成效的求解最优化问题的搜索算法，借助评价函数对解的优劣进行判定，对目标函数和约束的要求更为宽松。相比传统算法，群智能算法的效率更高，每个群个体的能力十分简单，执行时间也比较短，算法实现简单，鲁棒性更强。群智能算法包括蚁群算法和粒子群算法等，在各个领域具有广泛应用［2－6］。

本文主要研究利用离散粒子群算法解决多星任务调度优化问题，提出了一种基于离散粒子群算法的多星任务规划算法。通过实验仿真表明，本文算法简单、灵活、易于扩展，能够有效地对问题实行求解。

1 对地观测任务规划模型

1．1 对地观测任务描述

对地观测卫星多以近地轨道绕地球运转，每天可绕地球运行多圈。单颗卫星可以对指定区域进行周期性观测，通过组网工作，多颗卫星可以持续观测指定区域。

为了增加单颗卫星的检测范围，很多对地观测卫星都搭载具有侧视功能的载荷，能够沿垂直于运行轨道的方向进行摆动，实现偏离星下线的目标的观测，因此，在指定时刻内，卫星的观测范围是一个以星下线为圆心的圆形区域。

由此可见，卫星的成像任务主要有点目标成像任务和区域目标成像任务2种。为简便起见，一般的处理方式是将区域成像任务进行分解成多个点任务，统称为单元任务，统一进行处理。

1．2 数学模型

从约束规划的角度来看，多星任务规划问题实际上就是将有限的系统资源分配给要求完成的任务的过程。

多星任务规划问题主要涉及2个集合:卫星集合S和任务集合T。其中卫星集合S表示为S={s1，s2，…，sk}，单元任务集合 T 表示为 T={t1，t2，…，tm}。

由于卫星可以执行多种观测任务，不同的任务有不同的优先级，通过将优先级转换为任务的权值，作为任务收益的重要参数。任务i的权值表示为tqi，其中 tqi＞0，且 i∈T。

由于对地观测任务的特性，任务只有在特定的时间窗口之内才能进行，因此其所对应的资源其实是卫星的时间窗口。TWk，i为卫星k执行单元任务i时可以使用的时间窗口集合，表示为:

虽然对于特定任务，在多个时间窗口都可以进行观测，但是其观测质量可能并不一样，通过将该因素量化，作为时间窗口的权值。对于任务i可见的时间 窗 口 j 的 权 值 表 示 为 wqi，j，其 中 wqi，j＞ 0，且 i∈T，j∈TWk，i。

根据不同的优化策略可以构建不同的优化目标函数。对于多星任务规划系统，常见的优化策略主要是在满足容量和波段等约束条件下得到最大化任务完成收益(包括任务权值和窗口权值)，即

式中，xi，j为决策变量，如果单元任务i执行任务时占用的时间窗口为 j，则 xi，j=1;否则，xi，j=0。

2 面向任务规划的离散粒子群算法

2．1 基本粒子群算法

粒子群优化(Particle Swarm Optimization)算法最早于1995年由James Kennedy和Russell Eberhart提出，是一种基于群智能的随机搜索算法［2］。

基本粒子群算法基于位置—速度模型，粒子在飞行过程中，通过调整自身的飞行轨迹，并借助于以前自身的最佳位置和整个粒子群曾经的最佳位置的最佳经验，不断调整自身的位置。因此，群中的每个粒子都要有记忆能力，并且可以对自身的最佳位置进行调整，整个粒子群可以对群体的最佳位置进行调整。对于一个最大化问题，较佳位置是指解空间中对应目标函数的值较大的一个点。

2．2 离散粒子群算法设计

基本粒子群算法及其改进算法［8，9］主要被用于在连续论域中搜索函数的最优值，其模型直观简单、参数较少、效率高、执行速度快。但是由于标准粒子群算法所描述的粒子状态和运动方式都是基于连续变量的，在针对建模在离散空间中的问题，如任务调度和路径规划等，粒子的速度和位置变化难以使用基本粒子群方程表示，因此基本粒子群算法完全不适合求解离散空间中的问题。为了解决在离散空间中求解问题，需要将粒子群算法离散化［10，11］。本文提出一种适合多星任务规划的离散粒子群算法。

2．2．1 离散编码方式

在离散粒子群算法中，每个粒子代表一个可行解。针对任务分配问题，每个粒子就代表将任务分配给相应的资源的一种方式。通过自然数对任务进行编码，对于n个任务，其编码为1～n，对于m个资源，其编码为1～m，粒子的长度等于任务的个数。如图1所示，假定任务的个数为5，任务的编码为1、2、3、4、5;资源的个数是 1、2、3、4。按照图 1 的方式为任务指派相应资源，如为任务1指派资源2，任务5 指派资源4 等，得到一个相应的解为(2，3，2，1，4)，因此该粒子就为(2，3，2，1，4)。

图1 离散粒子的编码方式

2．2．2 粒子位置变化公式

粒子群的位置是粒子的速度、粒子的个体最优值和全局最优值相互作用的结果，粒子根据自己的飞行经验不断调整自身位置和速度，向最优位置飞行。根据资源分配的特点，对粒子群方程进行重新定义:

由此可以看出，离散粒子群和基本粒子群类似，其粒子位置的更新也受3个方面因素的影响:粒子的当前状态、粒子的最优历史记录和群的历史最优记录，离散粒子群方程也分为3个部分。对于资源分配问题，粒子的速度由粒子内部的置换操作和粒子之间的替换操作表示。

首先，离散粒子群公式的第1部分是粒子的“惯性”操作，当粒子处于某一状态时，通过调整粒子内部的结构，得到粒子的位置更新，该操作表示为:

式(4)是式(2)的一部分。其计算过程如下:假设粒子的维度为n，生成一个位于区间［1，n］的随机数i，然后依据任务约束条件，从时间窗口集合TW中查询计算i可以置换到的位置集合，从中随机选择一个元素j进行置换，符号“⊗”表示2个粒子之间的置换操作，如图2所示。计算置换以后的粒子适应度，如果该适应度更接近最优值，称该置换为优势置换，记做dom(⊗)=1，否则称该置换为劣势置换，记做dom(⊗)=0。如果该置换是个优势置换，则执行i和j的置换。如果该置换是个劣势置换，按照一定的概率进行劣势替换，劣势替换规则为rand(0)＜α*w，其中函数 rand()生成［0，1］之间的随机数，α为门限值，w为惯性权重，在此采用线性递降权重策略，惯性权重的计算方式为:

式中，Tmax为最大进化代数，即设定的算法迭代次数;wmax为初始惯性权重，取值0.9;wmin为进化到最大代数的惯性权重，取值为0.4。

图2 粒子内部的置换操作

离散粒子群公式的第2部分是粒子的“自我认知”，除了自身的位置调整以外，粒子还可以根据历史上的最优记录调整自身位置，该操作在粒子“惯性”操作的基础之上执行，其表示形式如下:

从式(6)可以看出，该公式叠加到粒子的“惯性”操作之上。“⊕”表示2个粒子之间的替换操作，假设粒子的维度为n，生成2个位于区间［1，n］的随机数i和 j，不失一般性，设 i＜j，如图 3 所示，得到一个替换区间［i，j］，利用历史最优粒子位于区间［i，j］的部分替换掉当前粒子位于该区间的内容。首先判断该替换是否满足性能约束条件，如果不满足，则设置j=j－1，直到满足约束，或者到达 i＜j，如果替换满足约束条件，计算替换以后的粒子适应度，如果该适应度大于当前的适应度，称该替换为优势替换，记做dom(⊕)=1，否则称该置换为劣势替换，记做dom(⊕)=0。如果该替换是个优势替换，则执行该区间的替换。如果该置换是个劣势替换，按照一定的概率进行劣势替换，劣势替换规则为rand()＜β，其中函数rand()生成［0，1］之间的随机数，β为门限值，如果生成的随机数小于门限值，则执行该替换。

图3 粒子和自身历史最优记录的交叉操作

离散粒子群公式的第3部分粒子的“社会认知”，除了前面2步，粒子还可以根据整个粒子群的最优记录调整自身位置，该操作在粒子“自我认知”操作的基础之上执行，其表示形式为:

式(7)也是离散粒子群公式的一部分，叠加到粒子的“惯性”操作和“自我认知”操作之上。“⊕”表示2个粒子之间的替换操作，假设粒子的维度为n，生成2个位于区间［1，n］的随机数i和j，不失一般性，设 i＜j，如图4 所示，得到一个替换区间［i，j］，利用群最优粒子位于区间［i，j］的部分替换掉当前粒子位于该区间的内容。首先判断该替换是否满足约束条件，如果不满足，则设置j=j－1，直到满足约束，或者到达i＜j，如果该替换满足约束条件，接下来计算替换以后的粒子适应度，若该适应度更接近最优值，称该替换为优势替换，记做dom(⊕)=1，执行该替换操作;否则称该置换为劣势替换，记做dom(⊕)=0，按照一定的概率执行该替换，其替换按照规则rand()＜γ进行，其中函数 rand()生成［0，1］之间的随机数，γ为门限值，如果生成的随机数小于门限值，则执行该替换。

图4 粒子和群最优记录的替换操作

上述3步过程完成以后，当前粒子的位置调整也已经结束，得到了一个新的解。通过计算该粒子的适应度，如果该适应度优于个体历史最优记录，将其记做个体最优历史记录;如果该适应度优于群最优历史记录，将其标记为粒子群最优历史记录。

2．3 离散粒子群算法流程

离散粒子群由多个粒子组成，其核心通过粒子之间的协作，获得所求解问题的可接受解。其算法流程如下:

①设定粒子群的规模N，最大进化代数Tmax，惯性参数 wmax和 wmin，劣势置换门限值 α、β、γ。

②生成N个初始粒子。计算每个粒子的适应度，将初始解作为局部最优值，从中选择最优值作为全局最优值。

③判定算法是否达到终止条件(达到最大进化代数或者满足算法的收敛准则)，如果满足，算法终止，否则进入步骤④。

④更新步长，计算惯性权重w。

⑤对每个粒子执行粒子位置变化公式，更新粒子的位置，计算粒子的适应度。如果该适应度优于个体历史最优记录，将其记做个体最优历史记录;如果该适应度优于群最优历史记录，将其标记为粒子群最优历史记录。转入步骤③。

3 模拟仿真结果

本文研究设计了一个仿真算例:通过离散粒子群算法和数学编程语言(A Mathematical Programming Language，AMPL)的线性规划算法对比，以验证离散粒子群算法在解决多星任务规划问题中的能力。

在对地观测卫星任务规划领域内，并没有标准的测试数据集对不同的调度方法进行验证和对比。本文中，实验数据利用卫星仿真工具包(Satellite Tool Kit，STK)仿真生成，根据对地观测任务的特点，在一定的场景和地面站中添加卫星对象，任务的可视窗口由待观测任务的地理位置和遥感天线的物理特性决定，并设置任务与时间窗的权值对应关系;任务的权值由任务的类型决定。为了验证模型的可行性，假设调度目标在限定的范围内均匀分布。

假定分解后的待执行任务纬度为－60°～60°，经度0°～180°均匀分布，且任务的优先级为正整数，卫星和任务的可见性由卫星模拟软件仿真生成。

仿真实验中分别将卫星数目设定为:10、20、30、40、50、80、100，对每组卫星数根据指定的任务数和窗口数随机生成测试样例。对同一组数据分别利用AMPL线性规划工具包和离散粒子群算法实现(由Java语言实现第2节的算法)进行求解。离散粒子群算法的粒子数设为1 000，迭代次数设为10 000，惯性权重设为0.9，3个置换门限值都设为0.000 5。实验结果如表1所示，AMPL列和DPSO列分别表示2种算法的执行时间。

表1 仿真对比结果

由表1中的数据得到AMPL和DPSO两种算法的执行时间曲线图如图5所示。

由图5可以看出，当任务数增大时，AMPL执行时间曲线近似呈指数增长。因为多星任务规划问题本质上是个约束规划问题，而约束规划是NP问题，因此，当问题规模很大时，AMPL的效率就非常低。而离散粒子群算法的执行时间基本上随着问题规模的增长而线性增长，显示了该算法具有良好的可扩展性，能够有效处理较大规模的多星任务规划问题。

图5 2种算法的执行时间曲线

4 结束语

依据构建的多星任务规划模型，在上述模型的基础之上，利用离散粒子群算法完成对多星任务规划的求解。通过仿真实验表明，离散粒子群算法能够有效解决多星任务规划问题，特别是在任务规模较大的情况下展现了良好的可扩展性。综上所述，建立的多星任务规划模型是合理的，而算法能够对不同尺度的多星任务规划问题进行有效求解。

［1］ 胡海洋，张学庆，刘 喆，等．基于AMPL的多成像卫星任务调度与规划［J］．系统工程与电子技术，2012 34(3):517－522．

［2］ 邢旭东，周 旭，米 健．基于改进的人工蚁群的图像分割算法［J］．无线电通信技术，2013，39(6):71 －73，81．

［3］ 席 斌，李 帅，侯媛媛．基于多目标粒子群算法的异构网接入控制［J］．无线电通信技术，2012，38(4):42 －44，50．

［4］ 卢文清，何加铭，曾兴斌，等．基于多特征提取和粒子群算法的图像分类［J］．无线电通信技术，2014，40(2):90－93．

［5］ 高明哲，祝明波，邹建武．基于改进粒子群算法的单脉冲雷达多目标分辨［J］．无线电工程，2014，44(6):25－28．

［6］ 张 旺，王黎莉，伍 洋．基于遗传算法的阵列天线综合及分析［J］．无线电通信技术，2011，37(4):28 －30．

［7］ KENNEDY J，Eberhart R．Particle Swarm Optimization［C］∥ Proceeding of IEEE International Conference on Neural Networks．Piscataway，NJ:IEEE Service Center，1995:1942－1948．

［8］ SHI Y，Eberhart R．A Modified Particle Swarm Optimizer［C］∥ Proceedingof IEEE International Conference on Evolutionary Computation，1998:69 －73．

［9］ CLERCM，KENNEDY J．The Particle Swarm:Explosion，Stability，and Convergence in a Multidimensional Complex Space［J］．IEEE Transactions on Evolutionary Computation，2002，6(1):58 －73．

［10］ KENNEDYJ，Eberhart R，SHI Y．Swarm intelligence［M］．San Francisco:Morgan Kaufman Publishers，2001．

［11］ KENNEDY J，Eberhart R．Discrete Binary Version of the Particle Swarm Algorithm［M］．CSMC，1997．

［12］ CHEN E，LI J，LIU X．In Search of the Essential Binary Discrete Particle Swarm ［J］．Applied Soft Computing Journal，2011，11(3):3 260－3 269．