基于多種群混沌遺傳算法的GEO目標服務任務規(guī)劃

尹 帥, 余建慧, 宋 斌, 郭延寧,*, 李傳江, 呂躍勇

(1. 哈爾濱工業(yè)大學航天學院, 黑龍江 哈爾濱 150001;2. 北京跟蹤與通信技術研究所, 北京 100094; 3. 上海宇航系統(tǒng)工程研究所, 上海 201109)

0 引 言

近年來,在軌加注、碎片清除、在軌維修等一系列航天器在軌服務技術逐漸興起[1],在軌服務技術的發(fā)展能有效降低航天運輸成本和任務風險,增強航天器的適應性、延長目標航天器壽命,發(fā)揮航天器滿載能力。比如,美國等相繼開展了“軌道快車”、任務擴展飛行器、“赫爾墨斯”飛船等[2],實現(xiàn)了多類型在軌服務任務;而“天源一號”衛(wèi)星、“天舟一號”貨運飛船等也實現(xiàn)了在軌加注飛行試驗。隨著航天發(fā)射任務的不斷增多,在軌服務技術必將呈現(xiàn)數(shù)量多、任務混合、自主性強等諸多特性。

當前在軌服務任務的研究大體可分為“一對多[3-4]”“多對多[5-8]”“P2P[9]”3種模式。“一對多”服務模式是空間多目標交會的基本模式;“多對多”模式為其衍生模式,拓展了在軌服務的規(guī)模;“P2P”模式是新興的服務模式,航天器可同時為服務者與被服務者,但這種模式成本代價高昂不適于大范圍推廣,不符合建立高效的在軌服務體系。因此,本文以“多對多”服務模式為基礎,研究在該模式下的在軌服務問題。任務規(guī)劃是在軌服務技術的頂層策略,其直接影響著在軌服務的經(jīng)濟效益,且其具有空間軌道動力學復雜、多局部最優(yōu)、多約束等特征,因此如何處理復雜變量及約束,提高算法的搜索效率是學者們普遍關注的焦點?，F(xiàn)有的任務規(guī)劃求解策略主要有兩種,一種是傳統(tǒng)優(yōu)化算法包含枚舉法[5]、分支定界法[7]等,這類方法能獲得整個搜索空間的全局最優(yōu)解,但僅能適用于小規(guī)模問題,否則容易陷入“維度災難”[10]。而另一種智能優(yōu)化算法如遺傳算法(genetic algorithm, GA)、模擬退火算法、粒子群優(yōu)化算法、禁忌搜索算法等[6,8,11-13]均可適用于中等以上規(guī)模的任務規(guī)劃問題,得到滿足模型約束的全局近似最優(yōu)解,其具有更廣泛高效的搜索性能。

由于航天器自身的燃料攜帶能力有限,單獨靠地面發(fā)射航天器進行燃料補給和碎片清除等任務具有較大的局限性,引入空間儲油站對服務航天器進行燃料補給提高了在軌服務方案的靈活性,健全了在軌服務的運行模式。因此,近些年來有學者借鑒地面車輛加油站背景,提出考慮空間中建設儲油站對航天器進行燃料補給[14],以提升在軌服務運行經(jīng)濟效益。文獻[15]考慮J2攝動下的多太陽同步軌道航天器在軌加注任務中燃料站的部署問題。文獻[16]比較了地面部署、低軌部署、同軌部署3種部署策略,證明了地球同步軌道(geosynchronous Earth orbit, GEO)衛(wèi)星采用同軌部署燃料站能獲得最大經(jīng)濟效益,并提出了一個儲油站帶有N個服務航天器的系統(tǒng)架構(gòu)。文獻[17]分別考慮了帶儲油站補給的在軌加注任務單目標及雙目標規(guī)劃問題。但是,上述的研究中都以單一的在軌服務任務為研究背景,鮮有考慮多任務混合的規(guī)劃問題,由于空間目標存在多種不同需求,航天器僅執(zhí)行單一任務不能完全發(fā)揮其滿載服務能力,增加了在軌服務任務的執(zhí)行成本。因此,考慮不同任務混合的可補給任務規(guī)劃問題能提高空間在軌服務系統(tǒng)性能,符合未來在軌服務發(fā)展的長期穩(wěn)定運行需求。

GEO是一類珍稀的特殊軌道資源,其軌道位置有限且分布的航天器大多代價高昂,為保障GEO航天器的運行壽命及軌道環(huán)境,本文以GEO的多對多航天器任務規(guī)劃問題為對象,提出一種多種群混沌GA(multi-group chaotic GA, MGCGA),主要的研究工作為:① 開展帶燃料補給的多任務混合的任務規(guī)劃問題研究,由此建立雙層任務規(guī)劃模型,其中外層為服務序列規(guī)劃,內(nèi)層為軌道機動規(guī)劃;② 考慮在軌燃料加注、碎片清除任務的執(zhí)行過程,設計基于Lambert的軌道機動優(yōu)化方案解決航天器交會問題;③ 采用混合編碼方式表征問題特性,引入立方體混沌映射算子提高初始種群的質(zhì)量及多樣性,設計多種群及精英個體保留機制平衡算法的多樣性及收斂性,實現(xiàn)對GEO區(qū)域的航天器任務規(guī)劃問題的有效求解。

1 在軌服務任務規(guī)劃模型構(gòu)建

面向在軌服務的航天器任務規(guī)劃屬于任務調(diào)度設計,是一類復雜的多空間交會組合優(yōu)化問題,其目的是在已知多個航天器資源情況下,滿足在軌服務的各類復雜約束,確定任務分配、交會序列及軌道轉(zhuǎn)移方案,實現(xiàn)任務收益的最大化。

1.1 問題描述

本文以GEO軌道中等待被加注燃料以延長壽命的航天器和對空間環(huán)境產(chǎn)生危險的碎片為研究對象,考慮航天器可往返儲油站補給燃料的方案,研究在軌燃料加注和碎片清除兩種任務模式,整體的多對多航天器任務規(guī)劃框架如圖1所示。

圖1 航天器任務規(guī)劃框架圖Fig.1 Spacecraft mission scheduling framework

在軌服務任務的主要流程如下。

(1) 將儲油站部署在GEO圓軌道上,航天器停泊在儲油站內(nèi)等待執(zhí)行任務,同時在GEO附近存在多個待加注燃料的目標航天器和待清除的碎片。

(2) 開始執(zhí)行任務時,確定服務航天器的服務序列及何時返回儲油站補給燃料。

(3) 各服務航天器具有滿足一種或兩種任務需求的能力,服務航天器利用其攜帶的載荷(如噴管對接、機械臂、網(wǎng)等)執(zhí)行在軌加注燃料任務和碎片清除任務。

(4) 每個服務航天器都按分配后的服務序列執(zhí)行任務,直到滿足所有目標的服務需求,當所有任務完成時,各個服務航天器返回儲油站。

1.2 在軌服務任務執(zhí)行策略

(1) 在軌燃料加注任務

空間目標交會是執(zhí)行燃料加注任務的核心問題,空間目標訪問任務規(guī)劃需要獲得任意兩目標在給定初始和終端狀態(tài)下的速度增量。對于兩目標之間轉(zhuǎn)移為雙脈沖交會問題,可以通過Lambert算法直接求解獲得[18-19]。Lambert問題作為天體動力學中研究最廣泛的問題之一,其應用是實際航天工程的熱點問題[20-24]。然而,當機動時間是待優(yōu)化的決策變量時,轉(zhuǎn)移速度增量不再是一個確定的值,最優(yōu)轉(zhuǎn)移速度增量需要通過優(yōu)化軌道機動方案獲得。

本文設計的交會機動方案的實質(zhì)是在給定時刻t內(nèi),結(jié)合沿軌飛行和軌道機動兩種飛行策略,確定最優(yōu)轉(zhuǎn)移時間及最小的速度增量。本文研究的Lambert機動示意圖如圖2所示。

圖2 Lambert機動示意圖Fig.2 Lambert maneuver diagram

通過模擬退火算法將圖2中t1,t2,t3作為優(yōu)化變量,求解軌道機動規(guī)劃模型,考慮基于Halley迭代的多圈Lambert機動策略[25],確定最優(yōu)的時間分配和最小速度增量,得到給定時間內(nèi)最優(yōu)Lambert轉(zhuǎn)移的軌道機動規(guī)劃方案。

(2) 在軌碎片清除策略

碎片清除任務中,同樣采用上述的交會機動方案實現(xiàn)與待清除目標交會,同時在清除GEO目標過程中需要服務航天器拖曳目標至墳墓軌道釋放并返回GEO,因此在碎片清除任務中考慮雙脈沖霍曼轉(zhuǎn)移為共面轉(zhuǎn)移方案[26]。

1.3 雙層規(guī)劃模型建立

本文研究的GEO目標服務任務規(guī)劃問題,具體假設如下:

(1) 目標及服務航天器的運行軌道均為圓軌道,且目標的優(yōu)先級相同;

(2) 服務航天器在滿足目標服務需求的情況下指派不受限制;

(3) 各服務航天器的服務時間是獨立且確定的;

(4) 不考慮航天器出現(xiàn)故障等不確定性情況;

(5) 不考慮目標姿態(tài)運動情況,服務航天器到達指定位置后即認為完成交會;

(6) 儲油站的燃料儲備充足。

通過建立雙層任務規(guī)劃模型以精細化描述GEO目標服務任務規(guī)劃問題。外層是服務序列規(guī)劃,由目標函數(shù)確定最優(yōu)的“服務航天器-目標-儲油站”服務序列;內(nèi)層是軌道機動規(guī)劃,即在單次交會過程中確定服務航天器機動方案。

1.3.1 外層規(guī)劃模型

圖3 單次任務的執(zhí)行過程Fig.3 Execution process of a single mission

針對GEO目標服務任務研究,主要考慮服務航天器降低燃料消耗問題,因此考慮目標函數(shù)f1為最小化所有服務航天器的總消耗燃料量。

(1)

約束條件如下。

(1) 服務次數(shù)約束:每個目標僅需要一個服務航天器服務。

(2)

式中:xij=1表示服務航天器j執(zhí)行對目標i的服務任務,xij=0表示不執(zhí)行任務。

(2) 單個目標服務任務時長約束:服務航天器的服務時間不能超過允許的時間上限Tser。

(3)

(4)

(4) 儲油站補給約束:服務航天器任務結(jié)束后需返回儲油站,且執(zhí)行多目標服務任務時可多次返回儲油站補給。

(5)

(5) 目標交會機動時間約束:服務航天器單次機動交會時間不能超過允許的時間上限Tlim1。

0

(6)

(6) 返回儲油站機動時間約束:服務航天器單次機動返回儲油站時間不能超過允許的時間上限Tlim2。

(7)

1.3.2 內(nèi)層軌道機動規(guī)劃模型

內(nèi)層軌道機動規(guī)劃模型在外層規(guī)劃模型給定的轉(zhuǎn)移時間基礎上,通過優(yōu)化求解第1.2節(jié)的Lambert機動方案,得到航天器單次交會過程中最優(yōu)速度增量消耗及時間ΔV1,ΔV2,t1,t2,t3,再通過齊奧爾科夫斯基公式將速度增量消耗轉(zhuǎn)換為消耗燃料質(zhì)量[17]。其中,ΔV1,ΔV2分別為兩次脈沖消耗的速度增量。

目標函數(shù)f2:采用圖2所示的雙脈沖Lambert軌道機動策略對應的最小速度增量。

minf2=ΔV1+ΔV2

(8)

約束條件如下。

(9)

(2) Lambert軌道機動轉(zhuǎn)移時長約束:

(10)

式(10)表示為外層規(guī)劃模型給定轉(zhuǎn)移時間tij后,優(yōu)化分配服務航天器在自身軌道運行時間t1、機動轉(zhuǎn)移時間t2、在目標軌道運行時間t3。

1.3.3 雙層規(guī)劃模型

內(nèi)層:

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

(11)

外層:

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

(12)

2 MGCGA

經(jīng)典的優(yōu)化算法如GA等求解任務規(guī)劃問題時容易出現(xiàn)收斂速度緩慢、陷入局部最優(yōu)甚至無解等情況,因此本文設計MGCGA提高問題的求解質(zhì)量。

2.1 混合染色體編碼

由上述建?？芍?本文研究的任務規(guī)劃問題包含離散變量和時間連續(xù)變量,為有效表征問題特性,因此算法中采用混合編碼將整數(shù)編碼、0-1編碼和二進制編碼結(jié)合生成染色體,編碼后的染色體構(gòu)成如圖4所示。

圖4 染色體構(gòu)成示意圖Fig.4 Chromosome composition diagram

該染色體由5部分組成,每部分由n個基因組成,將A部分目標序列和B部分服務航天器的服務序列用正整數(shù)變量表示,C部分返回儲油站的決策變量采用0-1變量表示,D、E部分服務航天器的交會時間和返回時間采用二進制數(shù)表示。

2.2 立方映射混沌算子

元啟發(fā)式算法在生成初始種群時通常采用隨機采樣的策略,可能存在分布集中、多樣性差的問題,影響算法的搜索效率。立方映射混沌算子的混沌優(yōu)化思想可產(chǎn)生更為均勻的種群以提升算法收斂速度及精度,同時,相比于文獻[8]中采取的Logistic映射相比,其產(chǎn)生種群的均勻性更好[27]。因此,本文采用立方映射混沌算子生成初始種群。立方映射混沌算子的公式如下:

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

-1

(13)

(14)

式中:y(z)為混沌變量;lmin和lmax分別為映射區(qū)間的上下界;uz為映射后變量值。主要步驟如下。

步驟 1在[-1,1]之間隨機取值作為初始的混沌變量,根據(jù)式(13)迭代200次,得到含有200個立方體映射算子的序列,保障混沌變量的均勻性與多樣性。

步驟 2同時將染色體A部分按升序進行排列,其原來對應的自然數(shù)位置作為染色體編碼序號;B部分根據(jù)A部分染色體編碼序號隨機分配可服務的目標,C、D、E部分同樣做步驟1的處理,其中C部分將大于0的元素置1,反之置0;D和E部分以式(14)映射到區(qū)間。

步驟 3篩選種群,選取適應度最優(yōu)的前80個染色體作為算法的初始種群。

2.3 多種群進化算子

為進一步豐富種群的多樣性、收斂性及提高解的質(zhì)量,本文考慮多種群思想同時進化求解,提高算法的求解質(zhì)量。

2.3.1 基于精英個體保留策略的選擇算子

為提升算法的全局收斂性,在選擇階段先考慮精英個體保留策略,保留種群中前10%最優(yōu)適應度值個體,種群中的剩余個體再通過輪盤賭策略進行選擇,具體流程如下。

步驟 1計算種群中個體的選中概率

(15)

式中:fc為個體適應度值;d為種群中染色體個數(shù)。

2.3.2 交叉算子、變異算子及修復重組策略

本文研究的航天器任務規(guī)劃為地面離線規(guī)劃,為確保離線規(guī)劃方案的最優(yōu)性,相比于傳統(tǒng)的多種群進化算法每隔數(shù)代進行交互的操作[8,28-30]。本文采用固定概率和自適應概率的交叉、變異算子生成的種群每代進行交互,提高種群中個體多樣性,避免求解方案陷入局部最優(yōu)的情況。

(1) 交叉算子

首先將種群中的染色體分為兩組,一個種群采用固定的交叉概率,另一個種群采取自適應交叉概率。交叉采用單點交叉方式。對染色體D和E部分進行順序交叉,圖5為交叉操作示意圖。自適應交叉概率計算方式為

P=αP1+(1-α)P2

(16)

(17)

式中:P1,P2分別為選取較大和較小的交叉概率;e為當前迭代次數(shù);emax為最大迭代次數(shù)。式(16)和式(17)表示為在進化初期通過交叉快速生成新個體,提高種群進化速度。

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

(2) 變異算子

在變異操作中,同樣令一個種群采用固定的變異概率,另一個種群采取自適應變異概率。變異過程中將染色體各部分直接進行均勻變異,同時D和E部分在一次均勻變異的基礎上再對各基因進行一次均勻變異,圖6為均勻變異操作示意圖。對應的自適應變異概率計算方式為

Q=βQ1+(1-β)Q2

(18)

(19)

式中:Q1和Q2分別為選取較大和較小的變異概率,在后期進化中隨著染色體交叉差異不明顯,需用變異操作避免陷入局部最優(yōu)。

圖6 均勻變異操作示意圖Fig.6 Uniform variation operation diagram

(3) 修復與重組策略

在交叉變異環(huán)節(jié)由于其隨機性容易出現(xiàn)不滿足模型約束的情況,需對染色體進行修復操作后再重組成新種群,具體如下。

步驟 1判斷染色體C部分決策變量是否滿足約束式(5),若不滿足,則調(diào)整變量令所有服務航天器服務最終目標后返回儲油站。

步驟 2將超過各服務航天器的自身燃料攜帶量的染色體序列重新分配。

步驟 3將進化后種群與選擇階段的前10%優(yōu)異個體重組,得到完整的新種群。

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

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

3 仿真分析

為驗證本文建立的模型及任務規(guī)劃算法的可行性和有效性,本文選取1個空間儲油站、4個服務航天器與9個目標作為實際仿真場景,其中5個目標為失效衛(wèi)星,需要在軌加注燃料,4個目標為碎片,等待服務航天器清除。仿真中的儲油站、服務航天器及目標軌道均設置為GEO圓軌道,軌道高度相同,采用國內(nèi)外實際運行中GEO衛(wèi)星的軌道傾角和升交點赤經(jīng),具體軌道參數(shù)如表1所示。服務航天器及目標的任務參數(shù)如表2和表3所示,服務航天器初始的攜帶燃料量及服務航天器補給量由算法優(yōu)化得到。

表1 軌道參數(shù)Table 1 Orbit parameters

表2 航天器任務參數(shù)Table 2 Spacecraft mission parameters

表3 目標任務參數(shù)Table 3 Target mission parameters

在時間方面,僅考慮服務任務的執(zhí)行時間及軌道機動時間,其中單次軌道機動時間不超過5天,在軌加注和碎片清除兩種任務的服務時間分別為6 000 s和7 200 s。將固定交叉概率和變異概率設置為0.8和0. 6,種群規(guī)模為80,自適應交叉和變異部分P1=0.9,P2=0.6,Q1=0.8,Q2=0.5,最大進化代數(shù)為100,軌道機動模型中的模擬退火算法初始溫度為0.2℃,內(nèi)循環(huán)次數(shù)為50,退溫次數(shù)為50,初始開采次數(shù)為0.5,退溫系數(shù)為0.8。為進一步測試MGCGA算法的性能,將常規(guī)GA、大鄰域搜索-自適應遺傳算法(large neighborhood search-adaptive genetic algorithm, LNS-AGA)[11]與MGCGA對比,如圖8所示為3種算法的收斂曲線。

在相同工況情況下,GA、LNS-AGA和MGCGA均迭代100次后終止,采用MGCGA、GA、LNS-AGA分別求解GEO目標服務任務問題,得到的目標函數(shù)值分別為2 891.35 kg、3 103.77 kg和3 038.17 kg。由圖8可以看出,MGCGA具有更好的全局收斂性,且求解的目標函數(shù)要優(yōu)于GA和LNS-AGA,由于采用混沌初始化種群有效提升了初始解的均衡性和多樣性,使得MGCGA在優(yōu)化初期就能得到較優(yōu)的解,同時多種群進化思想進一步提升了求解質(zhì)量。

圖8 3種算法的收斂曲線Fig.8 Convergence curves of three algorithms

GA的計算時間為10.98 h,LNS-AGA的計算時間為21.04 h,MGCGA計算時間為13.78 h。由于在單個目標交會階段均采用第1.2節(jié)的軌道機動規(guī)劃策略,GA、LNS-AGA與MGCGA的計算時間均較長。GA的計算時間要比MGCGA的計算時間略短,MGCGA的計算時間要比LNS-AGA的計算時間短,由于LNS-AGA采用了復雜的局部搜索,在進化過程中會更耗時。本文設計的MGCGA采用多種群進化策略使得每代種群中個體需要進行交互,相比于GA增加了算法的計算時間,但同時提升了種群中個體的多樣性。采用設計的自適應概率、種群交互、精英保留策略相結(jié)合的多種群進化策略能更好的平衡求解過程的多樣性與收斂性,立方混沌映射算子提升了MGCGA初始種群的均勻性,且求解得到的GEO目標服務任務規(guī)劃方案消耗的燃料更少。

通過MGCGA優(yōu)化得到完成所有任務后各服務航天器的總消耗燃料量(含目標待加注燃料量)為2 891.35 kg,服務序列(儲油站的序號為0)及結(jié)果如表4所示。其中,2 500 kg燃料用于加注給失效衛(wèi)星。服務航天器單次機動消耗的最大燃料量為46.19 kg及單次最長變軌時間為4.92天,軌道機動消耗燃料量占總消耗燃料量的13.54%。由表4中的任務規(guī)劃結(jié)果可以看出,航天器在連續(xù)執(zhí)行不同任務時通常僅執(zhí)行一次在軌加注任務,由于服務航天器采用燃料可補給方案,服務航天器傾向避免連續(xù)執(zhí)行多次的在軌加注任務,從而減少自身重量降低軌道機動的轉(zhuǎn)移代價,實現(xiàn)以最小的燃料消耗完成GEO目標服務任務,提升任務規(guī)劃方案的最優(yōu)性。通過仿真可以看出,得到的任務規(guī)劃結(jié)果滿足在軌服務任務的各類約束,同時本文設計的MGCGA能產(chǎn)生更好的規(guī)劃方案,適合求解此類在軌服務問題。

表4 任務規(guī)劃結(jié)果Table 4 Mission scheduling results

4 結(jié)束語

為有效解決多任務混合場景下的GEO目標服務任務規(guī)劃問題,建立了雙層任務規(guī)劃模型。在此基礎上,采用基于Lambert的軌道機動規(guī)劃策略實現(xiàn)空間目標交會,并結(jié)合雙脈沖霍曼轉(zhuǎn)移策略往返墳墓軌道。面向GEO空間目標多任務混合任務規(guī)劃問題,考慮各服務航天器可用燃料消耗、轉(zhuǎn)移時間和任務約束的情況下,以總消耗燃料量最小為目標,尋找最優(yōu)的服務序列和軌道機動參數(shù)。為解決連續(xù)-離散變量的組合優(yōu)化問題,采用混合編碼的方式表征決策變量,提出了MGCGA,通過立方映射混沌算子、多種群固定和自適應交叉概率個體的交互,以及精英個體保留策略充分平衡算法的多樣性與收斂性,實現(xiàn)任務規(guī)劃問題的有效求解。

未來研究將繼續(xù)探索儲油站的最優(yōu)部署,以提高任務的執(zhí)行效率,同時還將考慮任務執(zhí)行期間的不確定性因素,進一步提升規(guī)劃方案的魯棒性及實用性。