基于物理規(guī)劃的多星多站訪問規(guī)劃

王力堯, 張 進(jìn), 周洪喜, 王柯茂

(1. 國(guó)防科技大學(xué)空天科學(xué)學(xué)院, 湖南 長(zhǎng)沙 410073; 2. 空天任務(wù)智能規(guī)劃與仿真湖南省重點(diǎn)實(shí)驗(yàn)室, 湖南 長(zhǎng)沙 410073; 3. 中國(guó)人民解放軍第95031部隊(duì), 廣東 廣州 510000; 4. 中國(guó)人民解放軍第63757部隊(duì), 黑龍江 佳木斯 154002)

0 引 言

地面設(shè)施對(duì)衛(wèi)星的訪問包括跟蹤、遙控、干擾、信息傳輸和導(dǎo)彈打擊等。隨著在軌衛(wèi)星種類與數(shù)量的不斷增加,尤其是星鏈(StarLink)、一網(wǎng)(OneWeb)、克依伯(Kuiper)等低軌巨型星座的發(fā)展[1-3],近地軌道衛(wèi)星的數(shù)量增加到了一個(gè)新的量級(jí)[4],地面設(shè)備對(duì)衛(wèi)星的訪問任務(wù)也隨之增加。一方面,需要不斷增加地面設(shè)施的能力與部署數(shù)量;另一方面,也需要研究高效的地面設(shè)施調(diào)度方案。因此,近年來,多星多站的任務(wù)指派問題日益受到重視[5-7]。

多星多站訪問任務(wù)指派問題,屬典型的非確定性多項(xiàng)式困難問題,主要采用搜索算法和啟發(fā)式算法進(jìn)行求解[8]。Burrowbridge[9]針對(duì)多低軌衛(wèi)星優(yōu)化調(diào)度,采用貪婪算法求解;王海波等[10]針對(duì)天地測(cè)控資源聯(lián)合調(diào)度問題建立了考慮多種約束的模型,采用蟻群算法與模擬退火算法進(jìn)行求解。

由于多星多站訪問在工程實(shí)際中往往具有多個(gè)方面的設(shè)計(jì)目標(biāo),需要采用多目標(biāo)優(yōu)化方法求解。多目標(biāo)優(yōu)化問題,常通過加權(quán)法、約束法、混合法及分層賦權(quán)法將問題轉(zhuǎn)換為單目標(biāo)優(yōu)化問題進(jìn)行求解,或基于帕累托最優(yōu)的概念直接求解獲得多目標(biāo)最優(yōu)解集[11-13]。前者應(yīng)用的難點(diǎn)在于不好確定權(quán)重,而后者在變量較多時(shí),搜索空間將隨變量維數(shù)增加而呈指數(shù)增長(zhǎng),導(dǎo)致算法無法收斂或陷入局部最優(yōu),計(jì)算成本和復(fù)雜性均會(huì)成倍增加[14-15]。

針對(duì)要解決的大規(guī)模多目標(biāo)問題[16],本文建立了一種考慮成本和收益的多星多站非完全訪問規(guī)劃模型,采用基于物理規(guī)劃的差分進(jìn)化算法進(jìn)行求解,并與加權(quán)法、約束法和基于帕累托最優(yōu)的進(jìn)化算法進(jìn)行了對(duì)比[17]。

1 考慮成本和收益的多星多站非完全訪問問題

如圖1所示,M套地面設(shè)施需要在一定時(shí)間內(nèi)對(duì)N個(gè)目標(biāo)衛(wèi)星進(jìn)行訪問,區(qū)別于衛(wèi)星測(cè)控與通信調(diào)度問題,這里的訪問每次需要付出可觀的成本,但并不限制具體形式,訪問形式可以是觀測(cè)感知、測(cè)控[18],也可以是干擾、攔截[19-20]等;其次,每次訪問的收益,受衛(wèi)星重要性的影響,且對(duì)同一衛(wèi)星的再次訪問存在一定的收益衰減;再次,每次訪問需要在空間可見的基礎(chǔ)上,根據(jù)具體任務(wù)需求考慮多類約束要求,即每次訪問需要在可行窗口內(nèi)進(jìn)行;最后,同一地面設(shè)施在同一時(shí)刻只能訪問一個(gè)目標(biāo)衛(wèi)星,其相鄰訪問的窗口有最小時(shí)間間隔要求。

圖1 多星多站訪問示意圖Fig.1 Multi-station accessing multi-satellite skematic diagram

根據(jù)任務(wù)的不同,地面設(shè)施對(duì)空間目標(biāo)的訪問窗口計(jì)算考慮的約束不同。常考慮的約束包括仰角、距離、高度、陽照等,一種表現(xiàn)為以球錐為基礎(chǔ)并進(jìn)一步多向切割的空間幾何關(guān)系[21],另一種是以火箭或?qū)椛仙蛇_(dá)域?yàn)榛A(chǔ)的以非線性曲線為母線的旋轉(zhuǎn)體的變形[22-24]。當(dāng)然,進(jìn)一步還可以考慮速度、相對(duì)速度、交會(huì)角等約束[25]。將衛(wèi)星軌跡和地面設(shè)備空間可達(dá)域求交,可以計(jì)算出M個(gè)地面設(shè)施對(duì)N個(gè)目標(biāo)衛(wèi)星滿足約束的窗口集合的wmn:

wmn=

{wmnk|m=1,2,…,M;n=1,2,…,N;k=1,2,…,Kmn}

(1)

式中:wmnk={tmnk,in,tmnk,out}表示地面設(shè)施m對(duì)衛(wèi)星n的第k個(gè)訪問窗口,包含窗口的開始時(shí)間tmnk,in與結(jié)束時(shí)間tmnk,out信息;Kmn表示地面設(shè)施m對(duì)衛(wèi)星n的窗口數(shù)量。

記地面設(shè)施m對(duì)所有衛(wèi)星的窗口集合為wgm,所有地面設(shè)施對(duì)衛(wèi)星n的窗口集合為wsn,它們都是窗口集合wmn的子集。

2 規(guī)劃模型

根據(jù)窗口信息,建立多站對(duì)多星訪問的多目標(biāo)優(yōu)化規(guī)劃模型。

2.1 設(shè)計(jì)變量

設(shè)計(jì)變量x表示地面設(shè)施對(duì)目標(biāo)衛(wèi)星訪問的窗口指派關(guān)系,如式(1)所示。設(shè)計(jì)變量的元素個(gè)數(shù)等于訪問任務(wù)指派的最多次數(shù),設(shè)計(jì)變量每個(gè)元素對(duì)應(yīng)窗口集合wmn中的一組指派關(guān)系。

x=

(2)

式中:Ks表示對(duì)單顆衛(wèi)星的最大訪問次數(shù)。設(shè)計(jì)變量x與wsn,j中窗口信息的對(duì)應(yīng)關(guān)系滿足下式:

xj=xn+(k-1)N→wsn,xn+(k-1)N, (xn+(k-1)N=0,1,…Ksn)

(3)

式中:Ksn表示衛(wèi)星n的窗口個(gè)數(shù)。當(dāng)xn+(k-1)N≠0時(shí),表示對(duì)衛(wèi)星n進(jìn)行第k次訪問采用的時(shí)間窗口是wsn,xn+(k-1)N;當(dāng)xj=0時(shí),表示未進(jìn)行本次訪問。

為了便于問題描述,定義變量bxj和wxj代表指派xj對(duì)應(yīng)的地面設(shè)施編號(hào)和窗口信息。

2.2 約束條件

地面設(shè)施對(duì)衛(wèi)星訪問還需要滿足以下約束條件:

(1) 指派窗口間隔。地面設(shè)施連續(xù)兩次訪問任務(wù)之間要有足夠的時(shí)間間隔tmin interval以滿足兩次訪問之間的設(shè)備調(diào)試和任務(wù)準(zhǔn)備要求,可表征為

tbm+1,in-tbm,out≥tmin interval

(4)

(2) 訪問資源限制。由于設(shè)備壽命、人員精力、耗材數(shù)量等訪問資源的有限性,每個(gè)地面設(shè)施所能指派的最大訪問次數(shù)不超過Kg。

(3) 衛(wèi)星被訪問次數(shù)限制。單顆衛(wèi)星最多被訪問Ks次,更多的訪問不再具有收益。

2.3 優(yōu)化目標(biāo)

對(duì)于多星多站訪問問題,需要考慮成本、收益、時(shí)間等多方面因素,最終表征為3個(gè)優(yōu)化目標(biāo):

(1) 任務(wù)結(jié)束時(shí)間σ1。如式(5)所示,即最后一次訪問的結(jié)束時(shí)間,是對(duì)任務(wù)完成快速性的評(píng)價(jià)。

(5)

(2) 考慮成功率的訪問收益σ2。如式(6)所示,即從不同衛(wèi)星多次訪問獲取的訪問收益之和。

(6)

式中:μn為衛(wèi)星n的訪問收益;kn為第n顆衛(wèi)星被訪問的次數(shù);ζ為單次訪問的成功概率。

(3) 訪問成本σ3。如式(7)所示,即訪問任務(wù)的資源消耗,表現(xiàn)為訪問次數(shù)與單次訪問成本υ的函數(shù)。

(7)

綜上,在任務(wù)時(shí)間內(nèi),對(duì)M個(gè)地面設(shè)施訪問N個(gè)衛(wèi)星的三目標(biāo)優(yōu)化問題,選擇物理規(guī)劃總期望值最小作為優(yōu)化目標(biāo),如下所示:

(8)

3 基于物理規(guī)劃與差分進(jìn)化算法的多目標(biāo)優(yōu)化方法

對(duì)于指派方案的優(yōu)劣,可以通過物理規(guī)劃函數(shù)進(jìn)行評(píng)價(jià)。物理規(guī)劃是由美國(guó)Messac[26]提出的一種處理多目標(biāo)優(yōu)化設(shè)計(jì)問題的方法,主要根據(jù)設(shè)計(jì)人員對(duì)各目標(biāo)的期望設(shè)置的偏好區(qū)間,將多目標(biāo)優(yōu)化問題轉(zhuǎn)換為單目標(biāo)優(yōu)化問題,進(jìn)而求解。具體的優(yōu)化計(jì)算,使用差分進(jìn)化算法[27-28],其控制參數(shù)少、尋優(yōu)精度高、魯棒性強(qiáng)、易于工程實(shí)現(xiàn),被廣泛應(yīng)用于各領(lǐng)域的優(yōu)化問題[29-30]。

差分進(jìn)化算法求解的計(jì)算流程圖如圖2所示。

圖2 差分時(shí)化算法求解流程圖Fig.2 Flowchart of the resolving of the differential evolution algorithm

首先,通過地面設(shè)施和衛(wèi)星的信息,計(jì)算出任務(wù)時(shí)間內(nèi)所有可供選擇的訪問窗口wmn;其次,配置并計(jì)算物理規(guī)劃參數(shù);再次,通過差分進(jìn)化算法進(jìn)行優(yōu)化;最終,輸出滿足要求的計(jì)算結(jié)果。

對(duì)于差分進(jìn)化算法,采用整數(shù)變量,決策變量為第2.1節(jié)中的設(shè)計(jì)變量x。對(duì)于差分進(jìn)化算法的適應(yīng)度λi,首先配置物理規(guī)劃函數(shù):任務(wù)結(jié)束時(shí)間σ1與訪問成本σ3為Class-1s型、考慮成功率的訪問收益σ2為Class-2s型;其次,確定各指標(biāo)的偏好區(qū)間,生成物理規(guī)劃函數(shù);最后,計(jì)算物理規(guī)劃函數(shù)值,并將其作為差分進(jìn)化算法的適應(yīng)度λi,并代入差分進(jìn)化算法進(jìn)行求解。

4 算例分析

將本文提出的規(guī)劃方法,分別應(yīng)用于不同規(guī)模問題的求解。

4.1 小規(guī)模問題求解

表1 小規(guī)模問題地面設(shè)施位置

表2 目標(biāo)衛(wèi)星信息

表3 小規(guī)模問題物理規(guī)劃參數(shù)配置

計(jì)算任務(wù)期間內(nèi)所有窗口信息如表4所示。

表4 小規(guī)模問題訪問窗口信息

接著,進(jìn)行優(yōu)化計(jì)算,結(jié)果如表5所示,解的指標(biāo)情況如表6所示。

表5 小規(guī)模問題規(guī)劃方案

表6 小規(guī)模問題結(jié)果評(píng)價(jià)

4.2 大規(guī)模問題求解

表7 大規(guī)模問題目標(biāo)衛(wèi)星信息

在任務(wù)時(shí)段內(nèi),根據(jù)衛(wèi)星與地面設(shè)施的時(shí)空關(guān)系,計(jì)算出訪問窗口集合wmn。所有的衛(wèi)星均有訪問窗口,共有2 505個(gè)窗口,不同地面設(shè)施的窗口數(shù)基本不隨經(jīng)度變化改變,但隨緯度增高而增多。

4.2.1 基于本文方法的算例分析

以表8參數(shù)配置物理規(guī)劃函數(shù),以多目標(biāo)的物理規(guī)劃值作為差分進(jìn)化的適應(yīng)度進(jìn)行求解,重復(fù)計(jì)算10次,解的指標(biāo)情況如表9所示。其中,第一組解對(duì)應(yīng)的指派甘特圖為圖3,圖中不同顏色代表不同星座,每個(gè)指派的標(biāo)號(hào)為衛(wèi)星編號(hào),對(duì)應(yīng)的指標(biāo)評(píng)價(jià)為表10,所有指標(biāo)均得到了較為滿意的優(yōu)化。

表8 大規(guī)模問題物理規(guī)劃參數(shù)配置

表9 基于差分進(jìn)化算法和物理規(guī)劃的大規(guī)模問題指派結(jié)果統(tǒng)計(jì)

表10 大規(guī)模問題結(jié)果評(píng)價(jià)

圖3 基于差分進(jìn)化算法和物理規(guī)劃的大規(guī)模指派結(jié)果Fig.3 Assignment results based on differential evolution algorithm and physical programming for large-scale problems

4.2.2 比較分析

通過加權(quán)法、約束法和優(yōu)勢(shì)帕累托均衡算法(strength Pareto evolutionary algorithm,SPEA)求解上述問題,與本文方法比較。其中,加權(quán)法的目標(biāo)函數(shù)fweight為

fweight=σ1/3 600-2σ2+σ3

(9)

在約束法中,參考物理規(guī)劃的結(jié)果,將任務(wù)結(jié)束時(shí)間σ1、訪問成本σ3作為約束,設(shè)置σ1<140 400,設(shè)置σ3<100,以考慮成功率的訪問收益σ2為目標(biāo)函數(shù)fconstraint;使用SPEA求解3個(gè)目標(biāo)函數(shù)的問題。

采用加權(quán)法、約束法和物理規(guī)劃分別進(jìn)行了10組計(jì)算,采用SPEA求解了非支配解集,不同算法結(jié)果的盒圖如圖4～圖6所示。

圖4 任務(wù)結(jié)束時(shí)間σ1的盒圖Fig.4 Boxplot of end time of task σ1

圖5 考慮成功率的訪問收益σ2的盒圖Fig.5 Boxplot of visit income based on success rate σ2

圖6 訪問成本σ3的盒圖Fig.6 Boxplot of visit cost σ3

相較于本文方法,加權(quán)算法在任務(wù)結(jié)束時(shí)間和成功率兩個(gè)指標(biāo)上表現(xiàn)較差。因?yàn)?個(gè)優(yōu)化目標(biāo)互相制約、單位和數(shù)量級(jí)并不統(tǒng)一,其權(quán)值較難確定,需要反復(fù)實(shí)驗(yàn)。在本實(shí)驗(yàn)中,權(quán)值是參考物理規(guī)劃方法計(jì)算結(jié)果給出的,即使如此,計(jì)算結(jié)果也并無優(yōu)勢(shì)。

約束法將問題的約束從3個(gè)增加到了5個(gè),令可行解空間進(jìn)一步縮小,算法收斂困難。約束法對(duì)單一優(yōu)化指標(biāo)(任務(wù)結(jié)束時(shí)間)的優(yōu)化程度甚至差于本文方法,這說明本問題中,約束對(duì)結(jié)果的影響程度超過了優(yōu)化目標(biāo)的影響。同時(shí),也較難確定優(yōu)化目標(biāo)轉(zhuǎn)化的不等式約束參數(shù)的值。

在利用SPEA求解時(shí),由于多約束和多目標(biāo)同時(shí)存在,算法收斂較慢,較難獲得可行解[15],獲得的可行解也很難通過遺傳變異生成新的可行解,導(dǎo)致優(yōu)化困難。求得的非支配解集大小為443,將它和物理規(guī)劃方法的解進(jìn)行非優(yōu)超排序,發(fā)現(xiàn)無法互相優(yōu)超。這說明物理規(guī)劃的解也在帕累托最優(yōu)前沿上。

5 結(jié) 論

本文針對(duì)多星多站訪問這一大規(guī)模多目標(biāo)優(yōu)化問題,建立了考慮成本和收益的多星多站非均衡指派規(guī)劃模型,通過物理規(guī)劃將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題,采用差分進(jìn)化算法進(jìn)行優(yōu)化求解。仿真結(jié)果表明:提出的方法獲得的多星多站訪問方案兼顧了任務(wù)時(shí)間、收益和訪問成本3個(gè)指標(biāo),實(shí)現(xiàn)了不同目標(biāo)間的有效折衷權(quán)衡;相較于加權(quán)法、約束法,所提方法參數(shù)配置簡(jiǎn)單、算法尋優(yōu)能力更強(qiáng),收斂更好;所提方法獲得的解與優(yōu)勢(shì)帕累托均衡算法獲得的非支配解集無法互相優(yōu)超,驗(yàn)證了其最優(yōu)性。下一步將探索自適應(yīng)的變滿意區(qū)間物理規(guī)劃,進(jìn)一步提高算法性能與求解效果。