基于多种群混沌遗传算法的GEO目标服务任务规划

尹 帅, 余建慧, 宋 斌, 郭延宁,*, 李传江, 吕跃勇

(1. 哈尔滨工业大学航天学院, 黑龙江 哈尔滨 150001;2. 北京跟踪与通信技术研究所, 北京 100094; 3. 上海宇航系统工程研究所, 上海 201109)

0 引 言

近年来,在轨加注、碎片清除、在轨维修等一系列航天器在轨服务技术逐渐兴起[1],在轨服务技术的发展能有效降低航天运输成本和任务风险,增强航天器的适应性、延长目标航天器寿命,发挥航天器满载能力。比如,美国等相继开展了“轨道快车”、任务扩展飞行器、“赫尔墨斯”飞船等[2],实现了多类型在轨服务任务;而“天源一号”卫星、“天舟一号”货运飞船等也实现了在轨加注飞行试验。随着航天发射任务的不断增多,在轨服务技术必将呈现数量多、任务混合、自主性强等诸多特性。

当前在轨服务任务的研究大体可分为“一对多[3-4]”“多对多[5-8]”“P2P[9]”3种模式。“一对多”服务模式是空间多目标交会的基本模式;“多对多”模式为其衍生模式,拓展了在轨服务的规模;“P2P”模式是新兴的服务模式,航天器可同时为服务者与被服务者,但这种模式成本代价高昂不适于大范围推广,不符合建立高效的在轨服务体系。因此,本文以“多对多”服务模式为基础,研究在该模式下的在轨服务问题。任务规划是在轨服务技术的顶层策略,其直接影响着在轨服务的经济效益,且其具有空间轨道动力学复杂、多局部最优、多约束等特征,因此如何处理复杂变量及约束,提高算法的搜索效率是学者们普遍关注的焦点。现有的任务规划求解策略主要有两种,一种是传统优化算法包含枚举法[5]、分支定界法[7]等,这类方法能获得整个搜索空间的全局最优解,但仅能适用于小规模问题,否则容易陷入“维度灾难”[10]。而另一种智能优化算法如遗传算法(genetic algorithm, GA)、模拟退火算法、粒子群优化算法、禁忌搜索算法等[6,8,11-13]均可适用于中等以上规模的任务规划问题,得到满足模型约束的全局近似最优解,其具有更广泛高效的搜索性能。

由于航天器自身的燃料携带能力有限,单独靠地面发射航天器进行燃料补给和碎片清除等任务具有较大的局限性,引入空间储油站对服务航天器进行燃料补给提高了在轨服务方案的灵活性,健全了在轨服务的运行模式。因此,近些年来有学者借鉴地面车辆加油站背景,提出考虑空间中建设储油站对航天器进行燃料补给[14],以提升在轨服务运行经济效益。文献[15]考虑J2摄动下的多太阳同步轨道航天器在轨加注任务中燃料站的部署问题。文献[16]比较了地面部署、低轨部署、同轨部署3种部署策略,证明了地球同步轨道(geosynchronous Earth orbit, GEO)卫星采用同轨部署燃料站能获得最大经济效益,并提出了一个储油站带有N个服务航天器的系统架构。文献[17]分别考虑了带储油站补给的在轨加注任务单目标及双目标规划问题。但是,上述的研究中都以单一的在轨服务任务为研究背景,鲜有考虑多任务混合的规划问题,由于空间目标存在多种不同需求,航天器仅执行单一任务不能完全发挥其满载服务能力,增加了在轨服务任务的执行成本。因此,考虑不同任务混合的可补给任务规划问题能提高空间在轨服务系统性能,符合未来在轨服务发展的长期稳定运行需求。

GEO是一类珍稀的特殊轨道资源,其轨道位置有限且分布的航天器大多代价高昂,为保障GEO航天器的运行寿命及轨道环境,本文以GEO的多对多航天器任务规划问题为对象,提出一种多种群混沌GA(multi-group chaotic GA, MGCGA),主要的研究工作为:① 开展带燃料补给的多任务混合的任务规划问题研究,由此建立双层任务规划模型,其中外层为服务序列规划,内层为轨道机动规划;② 考虑在轨燃料加注、碎片清除任务的执行过程,设计基于Lambert的轨道机动优化方案解决航天器交会问题;③ 采用混合编码方式表征问题特性,引入立方体混沌映射算子提高初始种群的质量及多样性,设计多种群及精英个体保留机制平衡算法的多样性及收敛性,实现对GEO区域的航天器任务规划问题的有效求解。

1 在轨服务任务规划模型构建

面向在轨服务的航天器任务规划属于任务调度设计,是一类复杂的多空间交会组合优化问题,其目的是在已知多个航天器资源情况下,满足在轨服务的各类复杂约束,确定任务分配、交会序列及轨道转移方案,实现任务收益的最大化。

1.1 问题描述

本文以GEO轨道中等待被加注燃料以延长寿命的航天器和对空间环境产生危险的碎片为研究对象,考虑航天器可往返储油站补给燃料的方案,研究在轨燃料加注和碎片清除两种任务模式,整体的多对多航天器任务规划框架如图1所示。

图1 航天器任务规划框架图Fig.1 Spacecraft mission scheduling framework

在轨服务任务的主要流程如下。

(1) 将储油站部署在GEO圆轨道上,航天器停泊在储油站内等待执行任务,同时在GEO附近存在多个待加注燃料的目标航天器和待清除的碎片。

(2) 开始执行任务时,确定服务航天器的服务序列及何时返回储油站补给燃料。

(3) 各服务航天器具有满足一种或两种任务需求的能力,服务航天器利用其携带的载荷(如喷管对接、机械臂、网等)执行在轨加注燃料任务和碎片清除任务。

(4) 每个服务航天器都按分配后的服务序列执行任务,直到满足所有目标的服务需求,当所有任务完成时,各个服务航天器返回储油站。

1.2 在轨服务任务执行策略

(1) 在轨燃料加注任务

空间目标交会是执行燃料加注任务的核心问题,空间目标访问任务规划需要获得任意两目标在给定初始和终端状态下的速度增量。对于两目标之间转移为双脉冲交会问题,可以通过Lambert算法直接求解获得[18-19]。Lambert问题作为天体动力学中研究最广泛的问题之一,其应用是实际航天工程的热点问题[20-24]。然而,当机动时间是待优化的决策变量时,转移速度增量不再是一个确定的值,最优转移速度增量需要通过优化轨道机动方案获得。

本文设计的交会机动方案的实质是在给定时刻t内,结合沿轨飞行和轨道机动两种飞行策略,确定最优转移时间及最小的速度增量。本文研究的Lambert机动示意图如图2所示。

图2 Lambert机动示意图Fig.2 Lambert maneuver diagram

通过模拟退火算法将图2中t1,t2,t3作为优化变量,求解轨道机动规划模型,考虑基于Halley迭代的多圈Lambert机动策略[25],确定最优的时间分配和最小速度增量,得到给定时间内最优Lambert转移的轨道机动规划方案。

(2) 在轨碎片清除策略

碎片清除任务中,同样采用上述的交会机动方案实现与待清除目标交会,同时在清除GEO目标过程中需要服务航天器拖曳目标至坟墓轨道释放并返回GEO,因此在碎片清除任务中考虑双脉冲霍曼转移为共面转移方案[26]。

1.3 双层规划模型建立

本文研究的GEO目标服务任务规划问题,具体假设如下:

(1) 目标及服务航天器的运行轨道均为圆轨道,且目标的优先级相同;

(2) 服务航天器在满足目标服务需求的情况下指派不受限制;

(3) 各服务航天器的服务时间是独立且确定的;

(4) 不考虑航天器出现故障等不确定性情况;

(5) 不考虑目标姿态运动情况,服务航天器到达指定位置后即认为完成交会;

(6) 储油站的燃料储备充足。

通过建立双层任务规划模型以精细化描述GEO目标服务任务规划问题。外层是服务序列规划,由目标函数确定最优的“服务航天器-目标-储油站”服务序列;内层是轨道机动规划,即在单次交会过程中确定服务航天器机动方案。

1.3.1 外层规划模型

图3 单次任务的执行过程Fig.3 Execution process of a single mission

针对GEO目标服务任务研究,主要考虑服务航天器降低燃料消耗问题,因此考虑目标函数f1为最小化所有服务航天器的总消耗燃料量。

(1)

约束条件如下。

(1) 服务次数约束:每个目标仅需要一个服务航天器服务。

(2)

式中:xij=1表示服务航天器j执行对目标i的服务任务,xij=0表示不执行任务。

(2) 单个目标服务任务时长约束:服务航天器的服务时间不能超过允许的时间上限Tser。

(3)

(4)

(4) 储油站补给约束:服务航天器任务结束后需返回储油站,且执行多目标服务任务时可多次返回储油站补给。

(5)

(5) 目标交会机动时间约束:服务航天器单次机动交会时间不能超过允许的时间上限Tlim1。

0

(6)

(6) 返回储油站机动时间约束:服务航天器单次机动返回储油站时间不能超过允许的时间上限Tlim2。

(7)

1.3.2 内层轨道机动规划模型

内层轨道机动规划模型在外层规划模型给定的转移时间基础上,通过优化求解第1.2节的Lambert机动方案,得到航天器单次交会过程中最优速度增量消耗及时间ΔV1,ΔV2,t1,t2,t3,再通过齐奥尔科夫斯基公式将速度增量消耗转换为消耗燃料质量[17]。其中,ΔV1,ΔV2分别为两次脉冲消耗的速度增量。

目标函数f2:采用图2所示的双脉冲Lambert轨道机动策略对应的最小速度增量。

minf2=ΔV1+ΔV2

(8)

约束条件如下。

(9)

(2) Lambert轨道机动转移时长约束:

(10)

式(10)表示为外层规划模型给定转移时间tij后,优化分配服务航天器在自身轨道运行时间t1、机动转移时间t2、在目标轨道运行时间t3。

1.3.3 双层规划模型

内层:

minf2, s.t. (9)(10)

(11)

外层:

minf1, s.t. (1)～(7),(11)

(12)

2 MGCGA

经典的优化算法如GA等求解任务规划问题时容易出现收敛速度缓慢、陷入局部最优甚至无解等情况,因此本文设计MGCGA提高问题的求解质量。

2.1 混合染色体编码

由上述建模可知,本文研究的任务规划问题包含离散变量和时间连续变量,为有效表征问题特性,因此算法中采用混合编码将整数编码、0-1编码和二进制编码结合生成染色体,编码后的染色体构成如图4所示。

图4 染色体构成示意图Fig.4 Chromosome composition diagram

该染色体由5部分组成,每部分由n个基因组成,将A部分目标序列和B部分服务航天器的服务序列用正整数变量表示,C部分返回储油站的决策变量采用0-1变量表示,D、E部分服务航天器的交会时间和返回时间采用二进制数表示。

2.2 立方映射混沌算子

元启发式算法在生成初始种群时通常采用随机采样的策略,可能存在分布集中、多样性差的问题,影响算法的搜索效率。立方映射混沌算子的混沌优化思想可产生更为均匀的种群以提升算法收敛速度及精度,同时,相比于文献[8]中采取的Logistic映射相比,其产生种群的均匀性更好[27]。因此,本文采用立方映射混沌算子生成初始种群。立方映射混沌算子的公式如下:

y(z+1)=4y(z)3-3y(z),

-1

(13)

(14)

式中:y(z)为混沌变量;lmin和lmax分别为映射区间的上下界;uz为映射后变量值。主要步骤如下。

步骤 1在[-1,1]之间随机取值作为初始的混沌变量,根据式(13)迭代200次,得到含有200个立方体映射算子的序列,保障混沌变量的均匀性与多样性。

步骤 2同时将染色体A部分按升序进行排列,其原来对应的自然数位置作为染色体编码序号;B部分根据A部分染色体编码序号随机分配可服务的目标,C、D、E部分同样做步骤1的处理,其中C部分将大于0的元素置1,反之置0;D和E部分以式(14)映射到区间。

步骤 3筛选种群,选取适应度最优的前80个染色体作为算法的初始种群。

2.3 多种群进化算子

为进一步丰富种群的多样性、收敛性及提高解的质量,本文考虑多种群思想同时进化求解,提高算法的求解质量。

2.3.1 基于精英个体保留策略的选择算子

为提升算法的全局收敛性,在选择阶段先考虑精英个体保留策略,保留种群中前10%最优适应度值个体,种群中的剩余个体再通过轮盘赌策略进行选择,具体流程如下。

步骤 1计算种群中个体的选中概率

(15)

式中:fc为个体适应度值;d为种群中染色体个数。

2.3.2 交叉算子、变异算子及修复重组策略

本文研究的航天器任务规划为地面离线规划,为确保离线规划方案的最优性,相比于传统的多种群进化算法每隔数代进行交互的操作[8,28-30]。本文采用固定概率和自适应概率的交叉、变异算子生成的种群每代进行交互,提高种群中个体多样性,避免求解方案陷入局部最优的情况。

(1) 交叉算子

首先将种群中的染色体分为两组,一个种群采用固定的交叉概率,另一个种群采取自适应交叉概率。交叉采用单点交叉方式。对染色体D和E部分进行顺序交叉,图5为交叉操作示意图。自适应交叉概率计算方式为

P=αP1+(1-α)P2

(16)

(17)

式中:P1,P2分别为选取较大和较小的交叉概率;e为当前迭代次数;emax为最大迭代次数。式(16)和式(17)表示为在进化初期通过交叉快速生成新个体,提高种群进化速度。

图5 交叉操作示意图Fig.5 Interlacing operation diagram

(2) 变异算子

在变异操作中,同样令一个种群采用固定的变异概率,另一个种群采取自适应变异概率。变异过程中将染色体各部分直接进行均匀变异,同时D和E部分在一次均匀变异的基础上再对各基因进行一次均匀变异,图6为均匀变异操作示意图。对应的自适应变异概率计算方式为

Q=βQ1+(1-β)Q2

(18)

(19)

式中:Q1和Q2分别为选取较大和较小的变异概率,在后期进化中随着染色体交叉差异不明显,需用变异操作避免陷入局部最优。

图6 均匀变异操作示意图Fig.6 Uniform variation operation diagram

(3) 修复与重组策略

在交叉变异环节由于其随机性容易出现不满足模型约束的情况,需对染色体进行修复操作后再重组成新种群,具体如下。

步骤 1判断染色体C部分决策变量是否满足约束式(5),若不满足,则调整变量令所有服务航天器服务最终目标后返回储油站。

步骤 2将超过各服务航天器的自身燃料携带量的染色体序列重新分配。

步骤 3将进化后种群与选择阶段的前10%优异个体重组,得到完整的新种群。

本文提出的算法求解流程如图7所示。

图7 算法求解流程图Fig.7 Algorithmic solution flow chart

3 仿真分析

为验证本文建立的模型及任务规划算法的可行性和有效性,本文选取1个空间储油站、4个服务航天器与9个目标作为实际仿真场景,其中5个目标为失效卫星,需要在轨加注燃料,4个目标为碎片,等待服务航天器清除。仿真中的储油站、服务航天器及目标轨道均设置为GEO圆轨道,轨道高度相同,采用国内外实际运行中GEO卫星的轨道倾角和升交点赤经,具体轨道参数如表1所示。服务航天器及目标的任务参数如表2和表3所示,服务航天器初始的携带燃料量及服务航天器补给量由算法优化得到。

表1 轨道参数Table 1 Orbit parameters

表2 航天器任务参数Table 2 Spacecraft mission parameters

表3 目标任务参数Table 3 Target mission parameters

在时间方面,仅考虑服务任务的执行时间及轨道机动时间,其中单次轨道机动时间不超过5天,在轨加注和碎片清除两种任务的服务时间分别为6 000 s和7 200 s。将固定交叉概率和变异概率设置为0.8和0. 6,种群规模为80,自适应交叉和变异部分P1=0.9,P2=0.6,Q1=0.8,Q2=0.5,最大进化代数为100,轨道机动模型中的模拟退火算法初始温度为0.2℃,内循环次数为50,退温次数为50,初始开采次数为0.5,退温系数为0.8。为进一步测试MGCGA算法的性能,将常规GA、大邻域搜索-自适应遗传算法(large neighborhood search-adaptive genetic algorithm, LNS-AGA)[11]与MGCGA对比,如图8所示为3种算法的收敛曲线。

在相同工况情况下,GA、LNS-AGA和MGCGA均迭代100次后终止,采用MGCGA、GA、LNS-AGA分别求解GEO目标服务任务问题,得到的目标函数值分别为2 891.35 kg、3 103.77 kg和3 038.17 kg。由图8可以看出,MGCGA具有更好的全局收敛性,且求解的目标函数要优于GA和LNS-AGA,由于采用混沌初始化种群有效提升了初始解的均衡性和多样性,使得MGCGA在优化初期就能得到较优的解,同时多种群进化思想进一步提升了求解质量。

图8 3种算法的收敛曲线Fig.8 Convergence curves of three algorithms

GA的计算时间为10.98 h,LNS-AGA的计算时间为21.04 h,MGCGA计算时间为13.78 h。由于在单个目标交会阶段均采用第1.2节的轨道机动规划策略,GA、LNS-AGA与MGCGA的计算时间均较长。GA的计算时间要比MGCGA的计算时间略短,MGCGA的计算时间要比LNS-AGA的计算时间短,由于LNS-AGA采用了复杂的局部搜索,在进化过程中会更耗时。本文设计的MGCGA采用多种群进化策略使得每代种群中个体需要进行交互,相比于GA增加了算法的计算时间,但同时提升了种群中个体的多样性。采用设计的自适应概率、种群交互、精英保留策略相结合的多种群进化策略能更好的平衡求解过程的多样性与收敛性,立方混沌映射算子提升了MGCGA初始种群的均匀性,且求解得到的GEO目标服务任务规划方案消耗的燃料更少。

通过MGCGA优化得到完成所有任务后各服务航天器的总消耗燃料量(含目标待加注燃料量)为2 891.35 kg,服务序列(储油站的序号为0)及结果如表4所示。其中,2 500 kg燃料用于加注给失效卫星。服务航天器单次机动消耗的最大燃料量为46.19 kg及单次最长变轨时间为4.92天,轨道机动消耗燃料量占总消耗燃料量的13.54%。由表4中的任务规划结果可以看出,航天器在连续执行不同任务时通常仅执行一次在轨加注任务,由于服务航天器采用燃料可补给方案,服务航天器倾向避免连续执行多次的在轨加注任务,从而减少自身重量降低轨道机动的转移代价,实现以最小的燃料消耗完成GEO目标服务任务,提升任务规划方案的最优性。通过仿真可以看出,得到的任务规划结果满足在轨服务任务的各类约束,同时本文设计的MGCGA能产生更好的规划方案,适合求解此类在轨服务问题。

表4 任务规划结果Table 4 Mission scheduling results

4 结束语

为有效解决多任务混合场景下的GEO目标服务任务规划问题,建立了双层任务规划模型。在此基础上,采用基于Lambert的轨道机动规划策略实现空间目标交会,并结合双脉冲霍曼转移策略往返坟墓轨道。面向GEO空间目标多任务混合任务规划问题,考虑各服务航天器可用燃料消耗、转移时间和任务约束的情况下,以总消耗燃料量最小为目标,寻找最优的服务序列和轨道机动参数。为解决连续-离散变量的组合优化问题,采用混合编码的方式表征决策变量,提出了MGCGA,通过立方映射混沌算子、多种群固定和自适应交叉概率个体的交互,以及精英个体保留策略充分平衡算法的多样性与收敛性,实现任务规划问题的有效求解。

未来研究将继续探索储油站的最优部署,以提高任务的执行效率,同时还将考虑任务执行期间的不确定性因素,进一步提升规划方案的鲁棒性及实用性。