改进遗传与萤火虫算法的多星多目标任务规划

赵俭辉,陆一鸣,蔡 波

(武汉大学计算机学院,湖北 武汉 430072)

1 引言

卫星技术发展带来了近地空间信息利用率的上升,其好处是多方面的:小到日常使用的卫星导航、GPS定位系统,大到天气预报、农时播报、地形地貌测绘等等。卫星技术的高速发展在给予人们生活中巨大便利时,同样提高了国家在科研、工业及农业上的发展效率。卫星硬件性能上的提高带来了卫星调度能力的不断提升,同时也需要更加复杂而高效的调度方式来充分利用卫星的观测效能。在多卫星协同观测的情况下,如何规划各卫星需要观测的目标,从而使观测收益最大化同时减少资源消耗,就成了一个亟待解决的问题[1,2]。

卫星观测任务的规划通常将任务视作多个时间窗模型[3],之后采用智能优化算法或者深度学习方式对问题进行求解。在智能优化算法方面,所采用方法有改进蚁群算法[4]、禁忌搜索方法[5]、贪心算法[6]、动态规划[7,8]乃至多种算法的组合算法[9]等,通过对卫星与目标在不同算法框架下建模,对卫星的任务规划乃至重规划问题[10]进行求解。在深度学习方面,求解问题首先依赖于大量的卫星规划历史数据,并使用多种不同的神经网络模型(例如基于增广拓扑协同神经进化的预测模型[11]、改进指针模型[12])来预测卫星规划方案。

由于深度学习方法需要的大量历史数据,获取数据较为困难且算法成效受历史数据的优劣影响很大。基于上述原因,本文在求解多星多点目标观测任务规划问题时选用了基于智能优化算法的方法。通过对卫星实际运行时的轨道参数、载荷参数以及目标优先级等属性建模,应用改进遗传算法初步求解,并使用萤火虫算法进一步增强算法框架的局部寻优能力,最终得到更好的优化结果。

2 卫星观测问题建模

2.1 卫星约束模型

本文卫星约束模型主要包含:卫星分辨率约束、太阳高度角约束以及卫星侧摆动作约束。

2.1.1 分辨率约束

以光学相机CCD和雷达传感器SAR作为卫星执行观测任务的两种主要载荷,其分辨率的计算分别如下:

1)CCD相机分辨率

(1)

式中S为CCD相机单个相元尺寸,H为卫星离地高度,f为相机焦距,θ为卫星此时的侧摆角度。

2)SAR传感器分辨率

(2)

式中c为光速,W为雷达带宽,R为地球半径,H为卫星离地高度,θ为卫星侧摆角度。

2.1.2 太阳高度角约束

太阳高度角决定了卫星观测时的光照条件,对光学卫星任务执行十分重要,这一约束体现了传感器在工作时对光照的依赖程度。

上图中以北极圈内一点为例,太阳高度角即为该点地平线与太阳光线夹角,大小为γ。在某地正午以外的其它时间中,当地的太阳高度角以如下公式得到:

图1 太阳高度角约束

sinγ=sinαsinβ+cosαcosβcost

(3)

其中α为计算点的地理纬度,β为此时的太阳赤纬,t为计算位置的地方时(也叫时角)。太阳赤纬是太阳与地球中心连线与地球赤道面之间的夹角,在实际计算时,这一夹角的大小就是地球受太阳直射点的地理纬度。时角以360°代表一天的时间,以正午12点为界,更早的时间其时角为负而更晚的为正,以每小时15°的幅度进行均分。

在任一位置,当其地方时间为正午时,上述公式中cos(t)为1,由三角函数公式可知其正午时太阳高度角公式如下

sinγ=cos(α-β)→γ=90°-|α-β|

(4)

本文对目标进行时间窗计算时,把时间窗开始时间转换为当地地方时,并计算当地当时的太阳高度角。对于太阳高度角不符合卫星有效载荷约束条件的时间窗口,在任务规划前就舍去。

2.1.3 侧摆动作约束

卫星的侧摆约束和自身的动作模板约束共同构成了卫星观测时的机动约束。

1)动作模板约束

对于所有卫星而言,在观测之前需要进行准备动作,同时在观测结束后需要进行关机和卫星机动回正操作,其过程如图2所示。

图2 动作模板约束

2)侧摆约束

如图2所示,在同一个动作模板内,部分卫星可以通过连续侧摆进行多次观测。在问题建模中,当两个目标的观测时间窗彼此间隔时间大于两个目标之间卫星侧摆需要的时间,即认为这两个时间窗不发生冲突,否则时间窗冲突不能同时激活。现有卫星侧摆方式主要为阶梯式与线性形式两种。

表1表示了卫星侧摆设置的一般情况,在非线性侧摆方式下,对于给定侧摆角度α,先找出这一角度所述的侧摆区间[ai,aj],则侧摆角度α对应侧摆耗时即为表中对应的ti。在线性侧摆方式下,表1中最后一列表示了当侧摆角度为该行对应上限角度时所用时间,对于给定侧摆角度α∈[ai,aj],侧摆时间计算公式使用插值计算方式,具体如下

表1 侧摆耗时计算表

(5)

2.2 观测问题建模

在处理多星多点观测问题时,通常对于卫星观测范围建立两个观测窗口,一个表示卫星能够观察到的范围,用于目标观测时间窗的计算;另一个表示卫星实际的瞬时观测范围,用来表明卫星在某一时刻只能对前一窗口大范围中的一小部分进行观测。较小的窗口受到上文所列出的各种约束的限制。最终,根据卫星个体、卫星有效载荷、分辨率、地面目标可视窗口等因素,建立了如图3所示的映射关系。

图3 卫星目标映射关系示意

图4 改进的变异流程

图5 改进遗传-萤火虫组合算法

由上述模型与问题,可以对涉及到的各项因素或变量进行如下定义:

①任务规划场景时间起始于Tstart,结束于Tend。

②对于场景内的卫星,定义卫星集合SA={Sat1, Sat2,…, Satn},n表示卫星总数;对于星上搭载的载荷,定义集合Si={Sen1,…, Senm},该集合表示卫星i上搭载的所有m个载荷。

③对于单颗卫星,设定其侧摆最大幅度θ。

④对于可连续侧摆卫星,依照表1配置其角度-耗时,每颗卫星各自侧摆表项对应集合S-Cons={Cons1,…, Consn}相同位置元素。

⑤对于所有卫星,配置其动作模板,各卫星动作模板对应集合M={M1,…, Mn}中元素,而元素Mi={tbegin-i, tend-i, tgap-i}分别表示动作模板中的准备时间、恢复时间和动作模板间隔。

⑥对于地面各观测目标,建立集合Target={Target1,…, Targeto},o为场景内观测目标总数,同时各地面目标的优先级对应集合p={p1,…, po}中的元素。

⑦分别建立以卫星作为划分和以目标作为划分的时间窗集合。集合WSi表示卫星i对所有目标进行观测所获得的时间窗口,集合WTj表示目标j被所有卫星观测的时间窗口,其中元素wijk表示卫星i对目标j的第k个时间窗口,该窗口起始时间记为sijk,结束时间记为eijk。

⑧对于场景中所有的观测时间窗口集合:

(6)

建立对应决策变量集合X,其中元素xijk表示卫星i对于目标j的第k个时间窗口是否被激活,若激活表示卫星i在这一时间窗口内对目标j进行观测,否则不观测,xijk为0或1。

⑨建立集合profit={pro1,…, proo}表示最终任务分配完后各目标所能提供的收益量化。

根据上述定义,可得出以下目标和约束。

①所有目标的最终观测收益综合最大化

(7)

②所有的时间窗都应该处在任务场景的开始时间与结束时间之内,即

Tstart≤sijk≤Tend,Tstart≤eijk≤Tend

(8)

③对于所有时间窗口,需要首先完成太阳高度角约束与分辨率要求的约束,即缩小任务规划范围,减少有效时间窗数量。

④卫星相邻的观测时间窗口,其时间差应当大于两者之间侧摆所要花费的时间

WSi(j+1)-WSij≥tside

(9)

其中tside可由式(5)获得。

在任务规划需要符合约束条件的同时,观测收益的总和还需要考虑如下要求:对于高优先级目标,其理应得到更多的观测资源但不能因此而放弃对低优先级目标的观测。因此,最终达到的理想情况是所有目标均能得到观测,且观测资源的分配按照优先级逐级递减,各目标自身所分配到的观测资源分布较为平均,不会出现集中观测的情况。

3 改进遗传-萤火虫算法

3.1 改进遗传算法

传统遗传算法由于不关注个体属性与差异,导致在卫星规划问题中不可行解占据了解空间的绝大部分,如果不根据最终解码规划方案的可行与否来对种群个体分别进行处理,则算法性能会大幅降低,种群整体陷入不可行解的范围,无法及时跳出到可行解所在的解空间区域。因此,针对多星观测任务规划问题,提出了一种改进的遗传算法来解决解空间中具有多数不可行解的问题。

3.1.1 初始化与个体编码

本文对于卫星对点目标观测的任务序列采取二进制编码。在对每颗卫星独自进行时间窗排序后,将所有卫星各自时间窗序列拼接为一个长序列即整个仿真场景内的任务序列,序列中激活的时间窗标记为1,非激活时间窗标记为0,以此形成遗传算法所需要的染色体。种群大小设置为150-250,迭代次数设置为500代。由于约束条件的存在,解空间中存在大量不可行解,种群内个体过少或迭代次数过少会导致无法靠近可行解所在解空间,因此需要适当使用更大种群进行多次迭代。

3.1.2 个体选择

遗传算法通过交叉选择出能够生成下一代个体的本代亲本,通常使用的选择法有轮盘赌算法、精英保留法和锦标赛选择法。本文使用轮盘赌算法和精英保留法结合的选择方法。

精英保留法,通过保留每一代若干个适应度最高的个体,将其不做任何处理传递到下一代,从而保证本代最优秀基因能够完全保留。

轮盘赌选择法,根据个体适应度按一定概率选择亲本,每一个体被选为亲本的概率为

(10)

其中φ(i)为个体适应度值,max为种群个体数,适应度越高的个体越容易被选择。

在产生每一代新个体的过程中,文中的结合算法先使用精英选择法保留种群中适应度前10的个体不做处理直接进入下一代,然后在本代种群中使用轮盘赌选择法选择亲本,不断交叉产生子代直到新种群数量达标。

3.1.3 交叉与变异

交叉与变异是遗传算法寻优主要手段。亲本通过交叉算子两两重组,从而得到具有相似信息的子代。本文中交叉算子选择了两点交叉,随机在亲本上选择两个不同基因点位,两亲本对应位置的基因互相交换,进而产生两个新个体。由于已使用了精英选择法让一部分较好的个体保持优良形状不变,因此剩余个体进行交叉的概率为1,新种群由不产生交叉的优秀上代个体与必定交叉的新子代个体组成。

在改进遗传算法中,本文的变异算子不同于传统遗传算法,其在前期替代交叉算子,作为主要寻优手段,而不只是产生一定扰动,扩大搜索范围这一作用。本文的改进遗传算法通过分别处理可行解与不可行解,对多星多点目标观测规划问题进行优化。具体策略为:对于不可行解,由于其不可行的原因在于任务序列冲突,因此需要减少任务数量;对于可行解,希望能更进一步获得更优解,因此需要增加任务数量。改进算法的变异过程流程图如下:

3.1.4 适应度函数设计

在适应度计算环节,同样需要根据实际情况对个体使用不同计算方式。在解码阶段,染色体的基因序列被翻译成场景内各个卫星的任务序列,从这一序列中可以获得各个目标被观测的次数,综合各个目标的优先级,以及最终解码得到的序列是否合法,用以计算得出个体最终的适应度。

多优先级目标环境下的卫星观测任务筹划问题的目的在于:让高优先级目标尽可能多被观测到的同时,不至于挤占低优先级目标的观测窗口。设计适应度函数时遵循如下思路:高优先级目标在同等条件下会提供更高的适应度,同时随着高优先级目标观测次数的增多,其适应度逐渐下降,直到累积一定次数后,低优先级目标此时会提供更高的适应度。这一思路可简化为:未被观测到的低优先级目标,其适应度高于多次被观测到的高优先级目标。

最后,在上述方法前提下,需将可行解与不可行解做出区分,可行解的适应度应高于不可行解。同时由于下述两点原因,不可行解的适应度不能直接设置为0:①高“适应度”的不可行解在将少部分冲突任务删除后,产生高适应度可行解的可能性很大,直接剥夺该个体进入下一代的机会会使其部分优良基因丢失;②在整个解空间中,不可行解的数量远大于可行解,在种群迭代初期,整个种群中可能没有可行解或只有很少可行解,在这种情况下如果不可行解的适应度直接设置为0,则算法收敛速度会非常快,失去了搜索的意义或者直接无法继续运行,即没有个体可进入下一代。

综上所述,在实际的适应度计算中,选择保证各个目标的优先级在前期随着观测次数递减,并最终成为定值,在初步计算完成之后,将可行解的适应度乘以可行解系数α,保证可行解在种群的头部,而高优先级不可行解在次一级的位置。最终的计算公式如下:

(11)

(12)

(13)

其中φ(i)为个体的最终适应度。

3.2 改进遗传-萤火虫组合算法

3.2.1 组合算法设计思路

在使用改进遗传算法求解多星多点观测规划问题时,起到主要寻优作用的是改进后的变异过程,通过对少部分基因点位的变异产生全新的解,从而产生可能的更优解。在算法的进行过程中,对于高适应度个体以及交叉选择过程的利用率并不高。同时,当算法种群收敛时,种群内个体基本都为可行解,变异产生新个体的概率大幅降低,寻优性能下降。

为了进一步提高改进遗传算法的寻优性能,提高算法进入后期时的寻优能力,并且让高优先级个体对问题求解起到一定的导向作用,本文引入了萤火虫算法[13],借鉴萤火虫算法中“高亮度的萤火虫会吸引低亮度的萤火虫,而其它个体围绕最优个体搜索的同时也在慢慢向其靠近”的思想,使低适应度个体及不可行个体更快地向更优解转化。改进的遗传-萤火虫组合算法如下图所示。

3.2.2 组合算法实现

由于在多星多点目标观测规划问题中,卫星观测时间窗具有数量大,状态少的特点,各维度只有0-1两个位置,在执行改进遗传-萤火虫组合算法的靠近过程时难以直接套用萤火虫算法模型。因此需要将模型进行一定修改,将萤火虫算法中的“位置”与遗传算法中的“基因编码”,“移动距离”与“变异概率”进行对应转化,从而解决模型使用上的问题。

由于萤火虫算法有较强局部优化能力,因此只有当种群中有一部分个体向最优解靠拢时启动算法,才能有较好效果;否则算法会向最初产生的不可行解靠拢,反而会降低性能。

组合后的改进遗传-萤火虫算法流程如下:

1)初始化种群

2)计算种群个体适应度,判断当前种群是否出现最优可行个体,是则进入3)否则4)。

3)执行萤火虫算法

具体而言,萤火虫算法的核心步骤包括:

①初始化。确定种群数量、问题维度、迭代次数等,并随机生成若干萤火虫个体的位置,同时定义适应度函数,即个体“亮度值”。

②靠近过程。萤火虫间的吸引程度与其亮度、距离均相关,吸引度由以下公式计算得到

β=β0*e-γrij

(14)

式中β0为萤火虫距离为0时的吸引度,也叫最大吸引度,通常设置为1;γ为吸引度系数;rij为两萤火虫之间距离的平方。

各萤火虫根据吸引度如下方式更新位置

(15)

多项式最后一项表示萤火虫在靠近过程中进行的随机扰动,该过程利于跳出局部最优解。

③计算亮度。在靠近过程后,根据所有萤火虫的新位置重新计算其适应度即亮度。

④判断结束条件。若符合迭代次数或适应度阈值,则退出迭代并输出最优解,否则继续。

本文在将萤火虫算法与改进遗传算法进行组合时,只取其中核心的“靠近”思想,将“靠近”视作低适应度个体向高适应度个体的定向变异,从而得到本步骤的下述操作。

使当前种群中适应度最低的后50个个体或者所有不可行个体向种群中的最优个体定向变异(即萤火虫算法的“靠近”过程)。每个差异点位的变异概率如下

p=e-λr

(16)

其中r为差异个数,不选择差异个数的平方作为计算参数的原因在于,问题本身的维度很高导致了差异可能较大,如果使用平方进行计算的话,则不可行解向可行解靠近的概率过小,会导致算法起不到预期作用。

4)对执行萤火虫算法之后的个体重新计算适应度,并使用精英保留法和轮盘赌法相结合的算法产生拥有足量个体的新种群。

5)对所有个体按照改进遗传算法的处理方法进行变异操作。

6)判断是否符合退出条件,是则转7),不是则转入步骤2)。

7)计算适应度,对所有个体进行排序,并将当代最优个体与全流程最优个体对比,择其较优者解码,生成多星观测任务规划序列。

4 实验结果与分析

在通过实验测试本文改进遗传-萤火虫算法的性能时,一共设立了三个场景,分别对应“目标观测条件差”、“目标观测条件优”以及“综合场景”,以验证改进遗传-萤火虫算法在不同仿真场景的表现均优于其它优化算法。

选择用于比较的优化算法时考虑到:贪心算法作为传统优化算法,具有使用简单,运行速度快的优点;遗传-模拟退火算法作为常见的优化算法组合也曾经用于卫星观测规划问题上(本实验中的遗传-模拟退火算法使用改进后的遗传算法,提升了原算法的效能),具有一定的代表性。因此,将这两种算法以及单独的改进遗传算法与本文的改进遗传-萤火虫组合算法进行实验对比,下文中分别表述为:贪心算法、遗传-模拟退火算法/GSA、本文改进遗传算法/IGA、本文改进遗传-萤火虫算法/GFA。

4.1 观测条件较差区域

观测条件不佳有若干因素,例如点目标过于偏离卫星星下点轨迹,卫星观测位置的太阳高度角过低,又或者目标分布过于密集导致冲突过多等。本场景选择了北美洲西海岸区域的若干目标,具有密度大、部分目标偏离卫星观测范围的特征,场景3D/2D示意如图6所示。

图6 以观测条件较差区域为例的场景

场景内共有卫星5颗,目标16个,可激活时间窗总量为633,各算法执行结果及智能优化算法适应度迭代情况如表2、图7所示。其中,结果表内数据为10次实验后的平均值。

表2 表观测条件较差区域的规划结果

图7 观测条件较差区域的适应度迭代图

根据种群初始化方式,初始序列中激活时间窗的比例应当为时间窗总数的50%左右,但最后得出个体的时间窗总数只有25%左右,比例大大降低。分析原因有以下两点:首先,随着时间推移,卫星星下点轨迹逐渐转动,最终可能偏离北美洲西部区域,导致观测目标脱离观测范围;其次,在规划场景时间后期,部分卫星的观测区域虽然仍在北美洲西部附近,但目标本身分布较为密集,互相之间观测冲突较多,卫星对这些目标各自虽具有充分的观测能力,但这些时间窗之间不能兼容,所以在选择激活一个时间窗的同时需要抛弃大量的其它时间窗,最终导致规划任务整体数量较少。

4.2 观测条件较好区域

观测条件较好区域意味着目标分布较为均匀,冲突少,且大致分布在卫星观测范围之内。该组实验选择了赤道附近的若干点目标,目标分布遵循上述原则。场景内共有卫星5颗,目标13个,可激活时间窗数量为574,规划结果与适应度迭代情况分别如表3、图8所示。

表3 表观测条件较好区域的规划结果

图8 观测条件较好区域的适应度迭代图

相比观测条件较差区域,本区域实验可以看出,随着卫星观测条件变好,算法规划的结果也会提升,在该区域中,最终规划结果中激活时间窗的比例只略低于初始化时的50%。且从图8可发现,在实验中改进遗传-萤火虫算法能够最快进入可行解所在区域,并在另外两种算法逐渐收敛的后期依旧能找到更优结果。

4.3 综合区域

相比前两组实验,综合区域更加符合实际应用时的仿真场景,即兼有密集目标与稀疏目标,目标分布不以卫星观测范围为准,而是根据现实情况进行随机分布。在该组实验中,选取了从东南亚向北一直到中国大陆北部附近区域的一系列点目标。场景内共有卫星5颗,目标19个,任务总数为676个,规划结果与适应度迭代情况如表4、图9所示。

表4 综合区域的规划结果

图9 综合区域的适应度迭代图

最终规划结果占据场景内任务总数的30%到40%,介于观测条件较好区域与较差区域之间,说明多星多目标观测任务规划算法的结果同时受到算法性能和场景条件的影响。而在不同实验条件下,改进遗传-萤火虫算法相比其它算法均有更好的寻优性能,从图7-9可以看出,其它算法在400代之后已经收敛,而本文算法在400代之后仍有一定的寻优能力。

5 结论

本文对遗传算法应用于多星多目标观测规划问题进行了改进,使改进遗传算法更适合解决这一问题,同时进一步结合萤火虫算法的思想,使用该算法的优越局部性对改进遗传算法进行优化,组合后的算法具有以下优点:

1)提出的改进遗传算法比传统遗传算法具有更强针对性,通过先行对规划方案进行解码判别,能够较传统算法更快跳出不可行解区域,找到可行解从而进入之后的选择过程。

2)该组合算法对改进后的遗传算法引入了之前尚未被应用在这一问题上的萤火虫算法,用于提升遗传算法中交叉、变异过程的筛选寻优能力。单纯的改进遗传算法针对卫星规划问题过度依赖变异过程来产生更优个体,而变异过程的随机性太强,单次实验的结果优劣难以预料。萤火虫算法较好的局部性恰好弥补了遗传算法这方面的不足,通过让多数不良个体定向向最优个体靠拢,加大了算法在最优解附近的搜索能力,同时让交叉过程更多的发生在较优个体中,显著提升了算法性能。

另外,算法采用的是非机器学习的仿真优化方案,没有对于往期大量规划数据的需求,不受过往较差规划方案的影响;同时,通过仿真,能够摆脱时间的约束,提前对卫星的规划作出决策与评估,降低了规划成本。