面向衛星的在軌服務任務規劃方法*

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

(1. 國防科技大學 系統工程學院， 湖南 長沙 410073; 2. 中國科學院 空天信息創新研究院， 北京 100094)

衛星是一類特殊的空間設備，具有高投入、高風險、一次發射、長期使用的特點，且由于發射費用以及客觀環境條件的限制，其無法與地面設備一樣進行經常性的維護、保養和升級。太空空間環境的復雜與惡劣使得衛星經常在運行期間出現各種損耗、破壞甚至功能失效的情況。

隨著空間技術的革新與發展，空間在軌服務(On-Orbit Servicing，OOS)逐漸興起，為解決當前衛星所面臨的困境提供了極大的幫助。空間在軌服務是指在太空中利用在軌服務航天器執行針對各種航天器的維護、升級、裝配等空間任務的過程[1]?？臻g在軌服務為衛星等在軌航天系統提供了新型的維修和保養模式，實現了傳統模式無法完成的空間服務任務。

目前在軌服務任務規劃研究按照服務星與目標星的數量和功能不同可大致分為三類：

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

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

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

本文針對“多對多”在軌服務模式，研究面向衛星的在軌服務任務規劃方法，按照問題特性將問題劃分為在軌服務資源分配和在軌服務路徑規劃兩個子問題，并構建相應的數學模型，同時設計了求解兩個子問題的兩階段在軌服務任務規劃算法。

1 數學模型

1.1 問題描述

面向衛星的在軌服務任務規劃問題可定義為：根據目標衛星的不同維修服務需求，考慮在軌服務航天器各種使用約束，設計相應任務規劃方法以實現對在軌服務航天器資源有效利用和配置，在其能力范圍內最大化在軌服務航天器資源利用效率，并最大化滿足目標衛星的服務需求。

在軌服務任務規劃問題本質上是一個多空間目標交會的復雜組合優化問題，本文的空間目標交會基于Lambert變軌模式。要求解這個問題，需要解決兩個問題：一是任務分配，即給出哪些任務由哪些服務航天器完成；二是軌跡優化，即給出服務航天器執行任務的具體飛行航跡。根據該問題特性，可將面向衛星的在軌服務任務規劃問題劃分為兩層：以在軌服務資源分配為外層優化、在軌服務路徑規劃為內層優化，外層優化確定在軌服務對象、內層優化根據外層服務方案規劃機動路徑并同時將規劃結果反饋給外層，建立雙層優化模型。

1.2 雙層優化模型

1.2.1 外層優化：在軌服務資源分配

針對在軌服務航天器資源分配問題，考慮三個目標：一是衛星重要度Ci，表示服務該衛星所能獲得的收益；二是服務持續時間Tij，旨在提高在軌服務的效率；三是軌道機動燃料消耗均衡性指標f，分配方案中的在軌服務航天器軌道機動的燃料消耗應盡量均衡。在軌服務資源分配問題可建模如下：

(1)

(2)

其中：M、N表示服務航天器和目標衛星數目；xij為決策變量，若在軌服務航天器j參與服務目標衛星i，則取值為1，否則為0；w1、w2、w3分別表示三個優化目標的權重；Tijmin表示服務航天器j與目標星i交會的最早時間。 第一個約束表示對于每個目標衛星，只需要被一個服務航天器服務；第二個約束表示由于軌道機動條件以及攜帶燃料總量限制，每個服務航天器只能服務一個目標衛星。

1.2.2 內層優化：在軌服務路徑規劃

(3)

(4)

2 問題求解方法

2.1 基于多種群并行進化的混沌遺傳算法

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

2.1.1 混沌優化思想

利用混沌優化生成初始種群的過程如下所示。

Step3：利用基于序號的非連續離散映射方法將這400個混沌變量映射為400個染色體個體，對這400個個體進行適應度評價，選擇最優的50個作為初始種群。

2.1.2 多種群并行進化思想

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

傳統的多種群方法一般是每進化固定的X代，然后再進行種群交流，如果X選擇過小，多個種群很快便會趨于同質化，各個種群沒有足夠的獨立進化時間，使各個種群的個體趨于一致；如果X過大，則會出現種群收斂慢的問題。因此，本文設計自適應的方法對X進行調整：種群進化初期，X取一個較大的值使各個種群有充足的時間進行獨立進化，然后各個種群分享各自的最優解，這樣可以使算法更容易跳出局部最優解，提高種群質量的同時增加個體的多樣性；在種群進化后期，X取一個較小的值，從而使種群快速收斂并趨于穩定。自適應調整方法為：

(5)

2.1.3 算法流程

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

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

2.2 基于全局坐標轉換的NSGA-Ⅱ+GSDE算法

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

SDE的基本思想是將收斂性差的個體移到更加擁擠的區域，使其密度更大，從而在進化過程中能夠被淘汰。估計個體p的密度時，SDE通過比較個體p周圍的其他個體與p在不同目標上的收斂性來對這些個體進行坐標變換，將坐標變換之后的個體p的密度作為其密度評價。更具體地，如果某個個體q的某個目標值比p好，那么將它轉移到與p的該目標值相同的位置上，即對個體q進行坐標變換，將q的該目標值變為與p相同的目標值，其他目標值不變。

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

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

(6)

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

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)為個體q′1和個體q′2的第一個目標值，一共有M個目標。

對于SDE坐標變換，按照如下方式進行坐標調整：

(8)

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

對本文研究問題M=2，NSGA-Ⅱ的基于SDE的擁擠度計算為：

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分別代表個體p相鄰的兩個個體qi-1和qi+1經過SDE變換之后的個體，q′(i-1)(1)和q′(i+1)(1)分別代表第q′i-1和q′i+1的第一個目標值，q′(i-1)(2)和q′(i+1)(2)分別代表q′i-1和q′i+1的第二個目標值。為進一步考慮個體在整個種群中的全局收斂性，對SDE算子進行改進，利用該個體的全局收斂性對SDE密度進行調整，NSGA-Ⅱ的基于GSDE的擁擠度計算為：

(10)

利用改進的基于全局坐標轉換的GSDE擁擠度算子替換NSGA-Ⅱ的擁擠度算子，NSGA-Ⅱ+GSDE算法的流程如圖2所示。

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

3 實驗驗證

3.1 場景設置

構建仿真場景(2018-10-01 T 00-00-00至2018-10-02 T 00-00-00)，以中國20顆成像衛星為服務目標，應用本文所提出的兩階段在軌服務任務規劃方法調度15顆在軌服務星，其中目標星和服務星的軌道參數隨機生成，并賦予目標星隨機不同的重要度取值，驗證本文方法的可行性和有效性。

3.2 算例驗證

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

(a) 隨機初始化

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

(a) 單種群進化

實驗3：圖5描述了傳統遺傳算法、基于多種群并行進化的混沌遺傳算法、離散粒子群算法在

(a) 傳統遺傳算法

本節所述的目標衛星分配問題上的算法收斂結果。由圖可知，本文所提算法在初始解質量和收斂性上優勢相對較大。

實驗4：為了更加全面地評價本文提出算法的有效性，將該實驗數據應用在進化多目標優化領域的8個經典算法上，與本文提出的NSGA-Ⅱ+GSDE算法進行比較，參與實驗對比的算法分別為：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種算法結果如圖6所示。對比其他算法，本文設計的NSGA-Ⅱ+GSDE算法能夠獲得更加優秀的帕累托前沿、產生更好的在軌服務方案，多目標優化也為決策者在時間效率和成本耗費兩方面提供了權衡選擇的空間，更加適合用于求解在軌服務任務規劃問題。

(a) NAGA-Ⅱ+GSDE

4 結論

本文研究面向衛星的在軌服務任務規劃問題，基于問題特性將原問題分解為在軌服務資源分配和在軌服務路徑規劃兩層并建立雙層規劃模型，設計了在軌服務任務規劃方法對問題進行了求解，并通過多個對比實驗驗證了所提方法的有效性和可行性。