面向衛(wèi)星的在軌服務(wù)任務(wù)規(guī)劃方法*

劉曉路，許英杰，賀仁杰，路 帥

(1. 國(guó)防科技大學(xué) 系統(tǒng)工程學(xué)院， 湖南 長(zhǎng)沙 410073; 2. 中國(guó)科學(xué)院 空天信息創(chuàng)新研究院， 北京 100094)

衛(wèi)星是一類特殊的空間設(shè)備，具有高投入、高風(fēng)險(xiǎn)、一次發(fā)射、長(zhǎng)期使用的特點(diǎn)，且由于發(fā)射費(fèi)用以及客觀環(huán)境條件的限制，其無(wú)法與地面設(shè)備一樣進(jìn)行經(jīng)常性的維護(hù)、保養(yǎng)和升級(jí)。太空空間環(huán)境的復(fù)雜與惡劣使得衛(wèi)星經(jīng)常在運(yùn)行期間出現(xiàn)各種損耗、破壞甚至功能失效的情況。

隨著空間技術(shù)的革新與發(fā)展，空間在軌服務(wù)(On-Orbit Servicing，OOS)逐漸興起，為解決當(dāng)前衛(wèi)星所面臨的困境提供了極大的幫助?？臻g在軌服務(wù)是指在太空中利用在軌服務(wù)航天器執(zhí)行針對(duì)各種航天器的維護(hù)、升級(jí)、裝配等空間任務(wù)的過(guò)程[1]?？臻g在軌服務(wù)為衛(wèi)星等在軌航天系統(tǒng)提供了新型的維修和保養(yǎng)模式，實(shí)現(xiàn)了傳統(tǒng)模式無(wú)法完成的空間服務(wù)任務(wù)。

目前在軌服務(wù)任務(wù)規(guī)劃研究按照服務(wù)星與目標(biāo)星的數(shù)量和功能不同可大致分為三類：

一是“一對(duì)多”模式，指一顆服務(wù)星對(duì)多顆目標(biāo)星進(jìn)行服務(wù)。Zhou等[2]研究基于燃料站的“一對(duì)多”加注模式的在軌加注任務(wù)規(guī)劃問(wèn)題，以推進(jìn)劑消耗及任務(wù)持續(xù)時(shí)間最小化為目標(biāo)，將問(wèn)題視為多變量組合優(yōu)化問(wèn)題；鄭紅星等[3]采用脈沖機(jī)動(dòng)變軌與基于遺傳算法的序列規(guī)劃相結(jié)合的方法，利用霍曼轉(zhuǎn)移、異面圓軌道轉(zhuǎn)移和Lambert轉(zhuǎn)移等算法建立數(shù)學(xué)模型，針對(duì)同面與異面服務(wù)兩種情況進(jìn)行仿真與結(jié)果分析；朱嘯宇等[4]研究航天器在軌燃料加注任務(wù)規(guī)劃問(wèn)題，提出了一種基于聚類分析的在軌加注任務(wù)調(diào)度及優(yōu)化算法；Alfriend等[5]研究地球同步軌道小衛(wèi)星群在軌加注任務(wù)調(diào)度問(wèn)題，將該任務(wù)規(guī)劃問(wèn)題轉(zhuǎn)化為旅行商問(wèn)題(Traveling Salesman Problem, TSP)進(jìn)行求解；余婧[6]針對(duì)在軌服務(wù)任務(wù)規(guī)劃問(wèn)題，提出了一套可應(yīng)用于“P2P”“一對(duì)多”和混合模式的在軌加注任務(wù)規(guī)劃系統(tǒng)建模與優(yōu)化方法。

二是“多對(duì)多”模式，指多顆服務(wù)星對(duì)多顆目標(biāo)星進(jìn)行服務(wù)。歐陽(yáng)琪等[7]針對(duì)地球同步軌道衛(wèi)星(GEOsynchronous satellite, GEO)在軌加注任務(wù)規(guī)劃問(wèn)題進(jìn)行研究，成功地將在軌加注問(wèn)題轉(zhuǎn)化成TSP問(wèn)題求解；譚迎龍等[8]以GEO航天器為加注對(duì)象，對(duì)“多對(duì)多”模式的航天器在軌加注作業(yè)調(diào)度問(wèn)題進(jìn)行研究，首先以軌道轉(zhuǎn)移燃耗為優(yōu)化目標(biāo)，考慮時(shí)間、燃料等約束條件，建立了在軌加注作業(yè)調(diào)度問(wèn)題的數(shù)學(xué)模型；Shen等[9-10]解決了基于多圈Lambert問(wèn)題的最優(yōu)雙脈沖問(wèn)題，指出在軌加注調(diào)度的目的是找到總?cè)己淖钚〉淖顑?yōu)加注服務(wù)順序以及最佳時(shí)間分配方案；梁彥剛等[11]通過(guò)設(shè)計(jì)決策變量,考慮時(shí)間、燃耗等約束,建立了基于0-1整數(shù)規(guī)劃的任務(wù)模型,采用NSGA-Ⅱ算法求解；張琪新等[12]綜合考慮目標(biāo)航天器的服務(wù)優(yōu)先級(jí)、加注任務(wù)的燃耗成本與時(shí)間成本，建立一種多約束的在軌加注任務(wù)模型，并采用粒子群算法對(duì)模型進(jìn)行了仿真。

三是“P2P”模式，指衛(wèi)星既可以作為服務(wù)星也可以同時(shí)作為目標(biāo)星。都柄曉[13]針對(duì)異面圓軌道分布式加注任務(wù)規(guī)劃問(wèn)題,考慮同一軌道面內(nèi)的衛(wèi)星位置互換,將該問(wèn)題表述為一個(gè)非完全的賦權(quán)三部圖匹配問(wèn)題，采用遺傳算法對(duì)異面衛(wèi)星間的變軌進(jìn)行求解。

本文針對(duì)“多對(duì)多”在軌服務(wù)模式，研究面向衛(wèi)星的在軌服務(wù)任務(wù)規(guī)劃方法，按照問(wèn)題特性將問(wèn)題劃分為在軌服務(wù)資源分配和在軌服務(wù)路徑規(guī)劃兩個(gè)子問(wèn)題，并構(gòu)建相應(yīng)的數(shù)學(xué)模型，同時(shí)設(shè)計(jì)了求解兩個(gè)子問(wèn)題的兩階段在軌服務(wù)任務(wù)規(guī)劃算法。

1 數(shù)學(xué)模型

1.1 問(wèn)題描述

面向衛(wèi)星的在軌服務(wù)任務(wù)規(guī)劃問(wèn)題可定義為：根據(jù)目標(biāo)衛(wèi)星的不同維修服務(wù)需求，考慮在軌服務(wù)航天器各種使用約束，設(shè)計(jì)相應(yīng)任務(wù)規(guī)劃方法以實(shí)現(xiàn)對(duì)在軌服務(wù)航天器資源有效利用和配置，在其能力范圍內(nèi)最大化在軌服務(wù)航天器資源利用效率，并最大化滿足目標(biāo)衛(wèi)星的服務(wù)需求。

在軌服務(wù)任務(wù)規(guī)劃問(wèn)題本質(zhì)上是一個(gè)多空間目標(biāo)交會(huì)的復(fù)雜組合優(yōu)化問(wèn)題，本文的空間目標(biāo)交會(huì)基于Lambert變軌模式。要求解這個(gè)問(wèn)題，需要解決兩個(gè)問(wèn)題：一是任務(wù)分配，即給出哪些任務(wù)由哪些服務(wù)航天器完成；二是軌跡優(yōu)化，即給出服務(wù)航天器執(zhí)行任務(wù)的具體飛行航跡。根據(jù)該問(wèn)題特性，可將面向衛(wèi)星的在軌服務(wù)任務(wù)規(guī)劃問(wèn)題劃分為兩層：以在軌服務(wù)資源分配為外層優(yōu)化、在軌服務(wù)路徑規(guī)劃為內(nèi)層優(yōu)化，外層優(yōu)化確定在軌服務(wù)對(duì)象、內(nèi)層優(yōu)化根據(jù)外層服務(wù)方案規(guī)劃?rùn)C(jī)動(dòng)路徑并同時(shí)將規(guī)劃結(jié)果反饋給外層，建立雙層優(yōu)化模型。

1.2 雙層優(yōu)化模型

1.2.1 外層優(yōu)化：在軌服務(wù)資源分配

針對(duì)在軌服務(wù)航天器資源分配問(wèn)題，考慮三個(gè)目標(biāo)：一是衛(wèi)星重要度Ci，表示服務(wù)該衛(wèi)星所能獲得的收益；二是服務(wù)持續(xù)時(shí)間Tij，旨在提高在軌服務(wù)的效率；三是軌道機(jī)動(dòng)燃料消耗均衡性指標(biāo)f，分配方案中的在軌服務(wù)航天器軌道機(jī)動(dòng)的燃料消耗應(yīng)盡量均衡。在軌服務(wù)資源分配問(wèn)題可建模如下：

(1)

(2)

其中：M、N表示服務(wù)航天器和目標(biāo)衛(wèi)星數(shù)目；xij為決策變量，若在軌服務(wù)航天器j參與服務(wù)目標(biāo)衛(wèi)星i，則取值為1，否則為0；w1、w2、w3分別表示三個(gè)優(yōu)化目標(biāo)的權(quán)重；Tijmin表示服務(wù)航天器j與目標(biāo)星i交會(huì)的最早時(shí)間。 第一個(gè)約束表示對(duì)于每個(gè)目標(biāo)衛(wèi)星，只需要被一個(gè)服務(wù)航天器服務(wù)；第二個(gè)約束表示由于軌道機(jī)動(dòng)條件以及攜帶燃料總量限制，每個(gè)服務(wù)航天器只能服務(wù)一個(gè)目標(biāo)衛(wèi)星。

1.2.2 內(nèi)層優(yōu)化：在軌服務(wù)路徑規(guī)劃

(3)

(4)

2 問(wèn)題求解方法

2.1 基于多種群并行進(jìn)化的混沌遺傳算法

針對(duì)外層優(yōu)化在軌服務(wù)資源分配問(wèn)題，一些傳統(tǒng)的目標(biāo)分配方法穩(wěn)定性較差，總是在某些運(yùn)行狀態(tài)下出現(xiàn)收斂慢、陷入局部最優(yōu)解甚至無(wú)法收斂的情況。因此本文提出了基于多種群并行進(jìn)化的混沌遺傳算法(Chaotic Genetic Algorithm based on Multi-group parallel evolution, MCGA)：首先借鑒于混沌優(yōu)化思想，利用混沌算子的遍歷性特點(diǎn)對(duì)初始種群進(jìn)行混沌產(chǎn)生，提高了初始種群的全局質(zhì)量和多樣性，從而提高算法的穩(wěn)定性；其次設(shè)計(jì)了多個(gè)具有不同參數(shù)的種群并行進(jìn)化的機(jī)制，使得算法能夠更加容易地跳出局部最優(yōu)解，并提高了算法收斂的能力。借助混沌算子生成高質(zhì)量的初始種群以及多種群并行進(jìn)化跳出局部最優(yōu)解，可以有效提高算法的穩(wěn)定性和魯棒性。

2.1.1 混沌優(yōu)化思想

利用混沌優(yōu)化生成初始種群的過(guò)程如下所示。

Step3：利用基于序號(hào)的非連續(xù)離散映射方法將這400個(gè)混沌變量映射為400個(gè)染色體個(gè)體，對(duì)這400個(gè)個(gè)體進(jìn)行適應(yīng)度評(píng)價(jià)，選擇最優(yōu)的50個(gè)作為初始種群。

2.1.2 多種群并行進(jìn)化思想

本文利用多種群并行進(jìn)化的思想對(duì)方法進(jìn)行改進(jìn)。多種群并行進(jìn)化是多個(gè)種群按照不同參數(shù)進(jìn)行種群進(jìn)化操作，每個(gè)種群分別進(jìn)行獨(dú)立進(jìn)化，每進(jìn)化X代，各個(gè)種群互相交流各自的最優(yōu)個(gè)體。由于各個(gè)種群按照不同參數(shù)進(jìn)化，可以產(chǎn)生具有不同特征的個(gè)體，從而保證了種群的多樣性；同時(shí)種群之間進(jìn)行最優(yōu)解的交流，可以提高解的質(zhì)量和算法的收斂速度；并且在進(jìn)化過(guò)程中吸收別的種群的個(gè)體可以有效使種群跳出局部最優(yōu)解。

傳統(tǒng)的多種群方法一般是每進(jìn)化固定的X代，然后再進(jìn)行種群交流，如果X選擇過(guò)小，多個(gè)種群很快便會(huì)趨于同質(zhì)化，各個(gè)種群沒(méi)有足夠的獨(dú)立進(jìn)化時(shí)間，使各個(gè)種群的個(gè)體趨于一致；如果X過(guò)大，則會(huì)出現(xiàn)種群收斂慢的問(wèn)題。因此，本文設(shè)計(jì)自適應(yīng)的方法對(duì)X進(jìn)行調(diào)整：種群進(jìn)化初期，X取一個(gè)較大的值使各個(gè)種群有充足的時(shí)間進(jìn)行獨(dú)立進(jìn)化，然后各個(gè)種群分享各自的最優(yōu)解，這樣可以使算法更容易跳出局部最優(yōu)解，提高種群質(zhì)量的同時(shí)增加個(gè)體的多樣性；在種群進(jìn)化后期，X取一個(gè)較小的值，從而使種群快速收斂并趨于穩(wěn)定。自適應(yīng)調(diào)整方法為：

(5)

2.1.3 算法流程

基于上述的混沌優(yōu)化初始種群生成以及多種群并行進(jìn)化的方法，本文所提出的基于多種群并行進(jìn)化的混沌遺傳算法流程如圖1所示。

圖1 基于多種群并行進(jìn)化的混沌遺傳算法流程Fig.1 Diagram of chaotic genetic algorithm based on multi-group parallel evolution

2.2 基于全局坐標(biāo)轉(zhuǎn)換的NSGA-Ⅱ+GSDE算法

解的多樣性和收斂性是多目標(biāo)優(yōu)化所期望的目標(biāo)，但是對(duì)于內(nèi)層優(yōu)化在軌服務(wù)路徑規(guī)劃問(wèn)題，由于變軌時(shí)間、變軌速度等決策變量搜索空間大、數(shù)量多，容易存在收斂難的問(wèn)題，對(duì)解的收斂性相比于多樣性有更高的需求，因此引入基于坐標(biāo)轉(zhuǎn)換的密度算子[14](Shift-based Density Estimation，SDE)增強(qiáng)算法的收斂性，并根據(jù)問(wèn)題特點(diǎn)引入全局擁擠度的概念，將SDE改進(jìn)為基于全局坐標(biāo)轉(zhuǎn)換的GSDE(global shift-based density estimation)算子，從而進(jìn)一步增強(qiáng)算法的收斂速度。

SDE的基本思想是將收斂性差的個(gè)體移到更加擁擠的區(qū)域，使其密度更大，從而在進(jìn)化過(guò)程中能夠被淘汰。估計(jì)個(gè)體p的密度時(shí)，SDE通過(guò)比較個(gè)體p周圍的其他個(gè)體與p在不同目標(biāo)上的收斂性來(lái)對(duì)這些個(gè)體進(jìn)行坐標(biāo)變換，將坐標(biāo)變換之后的個(gè)體p的密度作為其密度評(píng)價(jià)。更具體地，如果某個(gè)個(gè)體q的某個(gè)目標(biāo)值比p好，那么將它轉(zhuǎn)移到與p的該目標(biāo)值相同的位置上，即對(duì)個(gè)體q進(jìn)行坐標(biāo)變換，將q的該目標(biāo)值變?yōu)榕cp相同的目標(biāo)值，其他目標(biāo)值不變。

對(duì)于群體P中個(gè)體p，其基于SDE的密度D′(p,P)可以計(jì)算為：

D′(p,P)=D(dist(p,q′1),…,dist(p,q′N-1))

(6)

其中：dist(p,q′1)是個(gè)體p和q′1之間的距離，q′1是經(jīng)過(guò)坐標(biāo)變換之后的個(gè)體；D代表密度計(jì)算方式，取決于不同的多目標(biāo)算法，如對(duì)于NSGA-Ⅱ算法，其密度計(jì)算方式為虛擬擁擠度距離，即計(jì)算個(gè)體p相鄰的兩個(gè)個(gè)體組成的矩形的長(zhǎng)度和寬度之和，則NSGA-Ⅱ的基于SDE的密度計(jì)算為

D′(p,P)=D(dist(q′1(1),q′2(1)),…,dist(q′1(M),q′2(M)))

(7)

其中，q′1(1)、q′2(1)為個(gè)體q′1和個(gè)體q′2的第一個(gè)目標(biāo)值，一共有M個(gè)目標(biāo)。

對(duì)于SDE坐標(biāo)變換，按照如下方式進(jìn)行坐標(biāo)調(diào)整：

(8)

其中，p(j)代表個(gè)體p的第j個(gè)目標(biāo)值，pi(j)代表個(gè)體pi的第j個(gè)目標(biāo)值，qi(j)代表個(gè)體qi的第j個(gè)目標(biāo)值，q′i(j)代表變換之后個(gè)體的第j個(gè)目標(biāo)值。

對(duì)本文研究問(wèn)題M=2，NSGA-Ⅱ的基于SDE的擁擠度計(jì)算為：

D′(p,P)=D(dist(q′1(1),q′2(1)),…,dist(q′1(M),q′2(M)))

=|q′(i-1)(1)-q′(i+1)(1)|+|q′(i-1)(2)-q′(i+1)(2)|

(9)

其中，q′i-1和q′i+1分別代表個(gè)體p相鄰的兩個(gè)個(gè)體qi-1和qi+1經(jīng)過(guò)SDE變換之后的個(gè)體，q′(i-1)(1)和q′(i+1)(1)分別代表第q′i-1和q′i+1的第一個(gè)目標(biāo)值，q′(i-1)(2)和q′(i+1)(2)分別代表q′i-1和q′i+1的第二個(gè)目標(biāo)值。為進(jìn)一步考慮個(gè)體在整個(gè)種群中的全局收斂性，對(duì)SDE算子進(jìn)行改進(jìn)，利用該個(gè)體的全局收斂性對(duì)SDE密度進(jìn)行調(diào)整，NSGA-Ⅱ的基于GSDE的擁擠度計(jì)算為：

(10)

利用改進(jìn)的基于全局坐標(biāo)轉(zhuǎn)換的GSDE擁擠度算子替換NSGA-Ⅱ的擁擠度算子，NSGA-Ⅱ+GSDE算法的流程如圖2所示。

圖2 NSGA-Ⅱ+GSDE算法流程Fig.2 Diagram of NSGA-Ⅱ+GSDE

3 實(shí)驗(yàn)驗(yàn)證

3.1 場(chǎng)景設(shè)置

構(gòu)建仿真場(chǎng)景(2018-10-01 T 00-00-00至2018-10-02 T 00-00-00)，以中國(guó)20顆成像衛(wèi)星為服務(wù)目標(biāo)，應(yīng)用本文所提出的兩階段在軌服務(wù)任務(wù)規(guī)劃方法調(diào)度15顆在軌服務(wù)星，其中目標(biāo)星和服務(wù)星的軌道參數(shù)隨機(jī)生成，并賦予目標(biāo)星隨機(jī)不同的重要度取值，驗(yàn)證本文方法的可行性和有效性。

3.2 算例驗(yàn)證

實(shí)驗(yàn)1：對(duì)本文提出的基于混沌優(yōu)化的初始種群生成策略進(jìn)行實(shí)驗(yàn)對(duì)比分析。選擇采用了混沌優(yōu)化生成初始種群的遺傳算法與隨機(jī)初始化種群的遺傳算法作為對(duì)比算法，算法的交叉概率和變異概率均設(shè)置為0.8和0.2，種群規(guī)模為50，最大進(jìn)化代數(shù)為200，適應(yīng)度根據(jù)資源分配模型計(jì)算，兩者求解資源分配問(wèn)題的最優(yōu)解的進(jìn)化過(guò)程如圖3所示。由圖可知，混沌優(yōu)化初始化產(chǎn)生的初始種群全局質(zhì)量和多樣性優(yōu)于隨機(jī)初始化，算法更加穩(wěn)定。

(a) 隨機(jī)初始化

實(shí)驗(yàn)2：對(duì)本文提出的多種群并行進(jìn)化策略進(jìn)行分析與實(shí)驗(yàn)對(duì)比。選擇傳統(tǒng)的單種群進(jìn)化遺傳算法與雙種群并行進(jìn)化的遺傳算法作為對(duì)比算法，傳統(tǒng)遺傳算法的交叉概率和變異概率為0.8和0.2，采用了雙種群并行進(jìn)化策略的遺傳算法兩個(gè)種群的交叉概率分別為0.5和0.9、變異概率分別為0.1和0.3，得到的兩者算法收斂結(jié)果如圖4所示。由圖可知，并行進(jìn)化更有助于算法跳出局部最優(yōu)并提高算法的收斂性。

(a) 單種群進(jìn)化

實(shí)驗(yàn)3：圖5描述了傳統(tǒng)遺傳算法、基于多種群并行進(jìn)化的混沌遺傳算法、離散粒子群算法在

(a) 傳統(tǒng)遺傳算法

本節(jié)所述的目標(biāo)衛(wèi)星分配問(wèn)題上的算法收斂結(jié)果。由圖可知，本文所提算法在初始解質(zhì)量和收斂性上優(yōu)勢(shì)相對(duì)較大。

實(shí)驗(yàn)4：為了更加全面地評(píng)價(jià)本文提出算法的有效性，將該實(shí)驗(yàn)數(shù)據(jù)應(yīng)用在進(jìn)化多目標(biāo)優(yōu)化領(lǐng)域的8個(gè)經(jīng)典算法上，與本文提出的NSGA-Ⅱ+GSDE算法進(jìn)行比較，參與實(shí)驗(yàn)對(duì)比的算法分別為：NSGA-Ⅱ、NSGA-Ⅲ、RVEA(reference vector guided evolutionary algorithm)、SPEA2 (strength Pareto evolutionary algorithm2)、Two-Arch2 (two-archive algorithm2)、GrEA (grid-based evolutionary algorithm)、HypE (hypervolume-based evolutionary algorithm)、MOEAD (multi-objective evolutionary algorithm based on decomposition)。9種算法結(jié)果如圖6所示。對(duì)比其他算法，本文設(shè)計(jì)的NSGA-Ⅱ+GSDE算法能夠獲得更加優(yōu)秀的帕累托前沿、產(chǎn)生更好的在軌服務(wù)方案，多目標(biāo)優(yōu)化也為決策者在時(shí)間效率和成本耗費(fèi)兩方面提供了權(quán)衡選擇的空間，更加適合用于求解在軌服務(wù)任務(wù)規(guī)劃問(wèn)題。

(a) NAGA-Ⅱ+GSDE

4 結(jié)論

本文研究面向衛(wèi)星的在軌服務(wù)任務(wù)規(guī)劃問(wèn)題，基于問(wèn)題特性將原問(wèn)題分解為在軌服務(wù)資源分配和在軌服務(wù)路徑規(guī)劃兩層并建立雙層規(guī)劃模型，設(shè)計(jì)了在軌服務(wù)任務(wù)規(guī)劃方法對(duì)問(wèn)題進(jìn)行了求解，并通過(guò)多個(gè)對(duì)比實(shí)驗(yàn)驗(yàn)證了所提方法的有效性和可行性。