基于蟻群的天基預(yù)警多目標(biāo)優(yōu)化算法

程禹， 魏承， 游斌弟， 趙陽(yáng)， 吳限德

(1.哈爾濱工業(yè)大學(xué) 航天學(xué)院，黑龍江 哈爾濱 150001； 2.哈爾濱工程大學(xué) 航天與建筑工程學(xué)院，黑龍江 哈爾濱 150001)

天基紅外系統(tǒng)具有覆蓋范圍廣、預(yù)警速度快、作戰(zhàn)用途多等特點(diǎn)，在反導(dǎo)信息保障中占據(jù)重要地位[1],受到了美國(guó)、俄羅斯等軍事強(qiáng)國(guó)的高度關(guān)注和大力投入[2-3]。天基預(yù)警系統(tǒng)傳感器調(diào)度優(yōu)化是天基預(yù)警系統(tǒng)的關(guān)鍵問題。多傳感器調(diào)度優(yōu)化是一個(gè)存在監(jiān)控沖突的多目標(biāo)、動(dòng)態(tài)、復(fù)雜多約束的非線性優(yōu)化問題[4]。在傳感器調(diào)度問題中，優(yōu)化目標(biāo)之間存在沖突，如何在改善目標(biāo)評(píng)價(jià)的同時(shí)不使另一個(gè)目標(biāo)的評(píng)價(jià)惡化，實(shí)現(xiàn)多個(gè)目標(biāo)共同優(yōu)化，這就是多目標(biāo)優(yōu)化問題(multiobjective optimization problem，MOP)[5]。與單目標(biāo)優(yōu)化問題不同，在解決MOP問題時(shí)，需要尋找所有目標(biāo)中最權(quán)衡的解[6]。

國(guó)內(nèi)外實(shí)驗(yàn)室、科研機(jī)構(gòu)和工程單位已經(jīng)開發(fā)了許多基于規(guī)則的元啟發(fā)式算法[7]解決多傳感器調(diào)度優(yōu)化問題。然而，盡管它們具有高效率的特點(diǎn)，但元啟發(fā)式算法也存在若干限制，例如，大多數(shù)算法在每次運(yùn)行中生成單個(gè)解決方案，并且按照固定邏輯進(jìn)行決策。這些局限性推動(dòng)了替代解決方案技術(shù)的發(fā)展。

多目標(biāo)進(jìn)化算法(multiobjective optimization evolutionary algorithm,MOEAs)是基于進(jìn)化的元啟發(fā)式算法，是解決高度復(fù)雜的MOP問題的常用方法之一[8]。文獻(xiàn)中提供了多種MOEAs方法，例如非支配排序遺傳算法Ⅱ(NSGA-Ⅱ)[9]或基于分解的多目標(biāo)進(jìn)化算法(MOEA/D)[10]。MOEAs采用了基于帕累托排序的選擇機(jī)制，即基于帕累托最優(yōu)性對(duì)解決方案進(jìn)行排名，使非支配解決方案被選擇的概率更高。然而，基于帕累托的MOEAs在處理具有多目標(biāo)的MOP問題時(shí)表現(xiàn)不佳[11-12]。

蟻群優(yōu)化算法(ant colony optimization,ACO)最初的目的是解決組合優(yōu)化問題，多年來ACO不僅應(yīng)用在天基預(yù)警系統(tǒng)中[4]，同時(shí)在空間碎片清除、中繼數(shù)據(jù)傳輸和地面目標(biāo)觀測(cè)等航天領(lǐng)域也有比較成熟的應(yīng)用[13-15]，解決了動(dòng)態(tài)任務(wù)分配和多目標(biāo)優(yōu)化等關(guān)鍵問題[5，16]。雖然，多目標(biāo)蟻群優(yōu)化算法(multiobjective optimization ant colony optimization,MOACO)已經(jīng)廣泛應(yīng)用在多目標(biāo)優(yōu)化問題的研究[17]，但是，MOACO是一個(gè)離散優(yōu)化算法，對(duì)于天基預(yù)警任務(wù)規(guī)劃這種多目標(biāo)連續(xù)優(yōu)化問題，需要進(jìn)行改進(jìn)。本文引入了基于指標(biāo)的連續(xù)搜索空間的多目標(biāo)蟻群優(yōu)化算法(iMOACO)。該算法在最先進(jìn)的MOEAs方面具有足夠競(jìng)爭(zhēng)力[18]。

1 天基預(yù)警連續(xù)搜索域蟻群多目標(biāo)優(yōu)化算法

1.1 搜索算法ACO_R

基于指標(biāo)的連續(xù)搜索空間蟻群優(yōu)化算法是一種基于ACO元啟發(fā)式的多目標(biāo)優(yōu)化算法。對(duì)于天基預(yù)警這種連續(xù)問題，ACO的一個(gè)典型拓展是ACO_R，與遺傳算法、概率學(xué)習(xí)方法和其他與螞蟻相關(guān)的算法相比，ACO_R已呈現(xiàn)出良好的計(jì)算結(jié)果。ACO_R還被用作2個(gè)連續(xù)領(lǐng)域MOACO算法的搜索方法。因此提出一種以ACO_R為搜索算法的天基預(yù)警規(guī)劃算法。

1.2 基于R2的天基預(yù)警方案排序算法

給定Pareto前沿近似值A(chǔ)，指標(biāo)的一元版本定義為：

(1)

天基預(yù)警方案排序算法的主要目的是創(chuàng)建一個(gè)非顯性排序方案。首先，優(yōu)化一組目標(biāo)的解決方案，并將解決方案放在排序的最前面。然后，刪除這些已排名的點(diǎn)，并以相同的方式分配第2個(gè)方案，依此類推，直到?jīng)]有更多的點(diǎn)需要進(jìn)行排名。該方案的優(yōu)點(diǎn)是在選擇壓力較大的問題上都具有良好的性能。

關(guān)于式(1)中效用函數(shù)的選擇，本文使用了價(jià)值標(biāo)度函數(shù)(achivement scalarizing function，ASF)。ASF的定義為：

(2)

式中：r為參考向量；λ為權(quán)重向量，維數(shù)均為Λ={λi|i=1,2，…,N}。為了定義效用函數(shù)集，需要?jiǎng)?chuàng)建一組權(quán)重向量Λ={λi|i=1,2，…,N}。使用創(chuàng)建網(wǎng)格{m,h}的單純形網(wǎng)格設(shè)計(jì)(simplex lattice design,SLD)計(jì)算Λ，其中m是目標(biāo)數(shù)，h是比例參數(shù)。這個(gè)結(jié)構(gòu)由每個(gè)目標(biāo)函數(shù)的所有可能的比例組合組成。因此，權(quán)重向量的系數(shù)是在0和1之間取h+1個(gè)均勻分布的值，即：

(3)

圖1 基于R2的天基預(yù)警方案排序算法Fig.1 Sorting algorithm of space-based early warning scheme based on R2

在基于R2的天基預(yù)警方案排序算法中，假設(shè)規(guī)劃結(jié)果集合p.F:中的每個(gè)規(guī)劃結(jié)果p.F:都具有以下結(jié)構(gòu)：

p.F: 目標(biāo)向量；p.α: 權(quán)重向量λ的當(dāng)前價(jià)值；p.u*: 獲得最優(yōu)價(jià)值；p.rank: 由算法分配的解的排列結(jié)果。

1.3 更新參考點(diǎn)

引入了2個(gè)重要的參考向量：理想向量z*和最低點(diǎn)向量znad。前者保留每個(gè)目標(biāo)的最小值，后者由帕累托最優(yōu)前沿的解得到的最大目標(biāo)值組成。這些向量在目標(biāo)的規(guī)范化過程中特別相關(guān)。

基于R2的天基預(yù)警結(jié)果排序算法要求對(duì)目標(biāo)向量進(jìn)行歸一化，以生成排序。進(jìn)行歸一化：

(4)

本文提出了一種機(jī)制，分別生成理想向量和最低點(diǎn)向量的統(tǒng)計(jì)近似值z(mì)min和zmax。在每次迭代中監(jiān)控當(dāng)前總體的最低點(diǎn)，確定距離真正帕累托前沿的解有多接近。方差越高代表解離帕累托前沿越遠(yuǎn)。

圖2 更新參考點(diǎn)Fig.2 Update reference point

1.4 基于指標(biāo)的天基預(yù)警連續(xù)搜索空間蟻群優(yōu)化算法

在本節(jié)中，描述了用于構(gòu)建基于指標(biāo)的天基預(yù)警連續(xù)搜索空間蟻群優(yōu)化算法的基本機(jī)制(參見算法3)。該方案是ACO元啟發(fā)式算法的一個(gè)推廣，用于求解以ACO_R為搜索引擎，無變量相關(guān)機(jī)制的連續(xù)多目標(biāo)優(yōu)化問題。該優(yōu)化算法的2個(gè)主要特點(diǎn)如下：1)使用了一個(gè)不同的信息素存檔方式，它根據(jù)方案排序算法存儲(chǔ)最好的解決方案；2)信息素更新過程促進(jìn)了新創(chuàng)建的解決方案與存儲(chǔ)在存檔中的當(dāng)前解決方案之間的競(jìng)爭(zhēng)。

每個(gè)螞蟻a∈A和信息素p∈Γ，其中A表示一組螞蟻，Γ表示信息素檔案，具有以下結(jié)構(gòu)：

x: 決策變量；F: 目標(biāo)向量；Fnorm: 歸一化目標(biāo)向量；α: 當(dāng)前利益值；u*: 最優(yōu)利益值。

天基預(yù)警連續(xù)空間蟻群優(yōu)化算法需要6個(gè)參數(shù)：Gmax、q、ε、ξ、α和h。Gmax是最大的蟻群代數(shù)。參數(shù)q和ξ由基于ACO_R的搜索引擎使用。參考向量的更新需要參數(shù)α和ε，分別是方差閾值和公差閾值。最后，h是用于在SLD上構(gòu)造單純形格的比例參數(shù)，以創(chuàng)建N個(gè)權(quán)重向量集。N同樣被用作螞蟻數(shù)量和信息素存檔Γ的基數(shù)。這一決定是基于R2指標(biāo)的μ-最優(yōu)分布，即如果有μ≥N的解決方案μ和權(quán)重向量N，解決方案μ-N將不會(huì)對(duì)R2指標(biāo)值產(chǎn)生影響。

如圖4所示是天基預(yù)警連續(xù)搜索空間蟻群優(yōu)化算法描述。首先計(jì)算N個(gè)權(quán)重向量集，然后根據(jù)信息素存檔Γ使用統(tǒng)一分布進(jìn)行初始化并計(jì)算z*和znad。然后創(chuàng)建并初始化記錄實(shí)例。使用天基預(yù)警方案排序算法對(duì)Γ中的觀測(cè)方案進(jìn)行排序，確定解的質(zhì)量。之后執(zhí)行算法的主循環(huán)，直到超過最大迭代次數(shù)。每個(gè)螞蟻使用ACO_R的標(biāo)準(zhǔn)機(jī)制生成一個(gè)新的預(yù)警觀測(cè)方案。然后計(jì)算理想觀測(cè)方案和最低點(diǎn)觀測(cè)方案的統(tǒng)計(jì)近似值。在這之后描述了信息素更新過程。設(shè)Ψ=A∪Γ。然后，對(duì)所有解的目標(biāo)向量進(jìn)行歸一化，目的是通過天基預(yù)警方案排序算法進(jìn)行排序。隨后，根據(jù)如下指標(biāo)：切換次數(shù)、疲勞度和觀測(cè)時(shí)長(zhǎng)，按遞增順序?qū)Ζ＿M(jìn)行排序。排序?qū)⒋_保把些接近帕累托最優(yōu)集的解排在最前端。將前N個(gè)觀測(cè)方案復(fù)制到存檔中然后刪除了Γ的所有觀測(cè)方案。如上所述，信息素的更新過程促進(jìn)了新創(chuàng)造的信息素和舊信息素之間的競(jìng)爭(zhēng)，目的是保留那些使R2指標(biāo)值最大化的觀測(cè)方案。在搜索過程結(jié)束時(shí)，返回Γ的內(nèi)容作為帕累托前沿近似值。

圖3 天基預(yù)警連續(xù)搜索空間蟻群優(yōu)化算法流程Fig.3 Ant colony optimization algorithm flow of space-based early warning continuous search space

圖4 基于規(guī)則的元啟發(fā)式算法計(jì)算結(jié)果Fig.4 Results of rule based meta heuristic algorithm

下面分析天基預(yù)警連續(xù)空間蟻群優(yōu)化算法的計(jì)算復(fù)雜性。新解決方案的產(chǎn)生需要O(N2n)。更新參考向量需要O(Nm)。對(duì)A和Γ以及目標(biāo)向量做標(biāo)準(zhǔn)化需要O(Nm)。天基預(yù)警方案排序算法的計(jì)算復(fù)雜度是O(N2(logN+m))(其中N=|P|，P為規(guī)劃結(jié)果集合)。從Γ中移除之前的解決方案需要O(1)。從ψ中復(fù)制最好的前N個(gè)值到Γ中需要O(N(n+m))。最后，再次執(zhí)行天基預(yù)警排序算法，這里需要O(N2(logN+m))，其間，排序工作占用了O(NlogN)。因此，天基預(yù)警連續(xù)空間蟻群優(yōu)化算法每步迭代的計(jì)算復(fù)雜度為O(N2(logN+m+n))，存儲(chǔ)數(shù)據(jù)的計(jì)算復(fù)雜度為O(N(n+m))。

2 仿真測(cè)試與分析

2.1 仿真場(chǎng)景設(shè)計(jì)

本文參考了美國(guó)低軌天基預(yù)警系統(tǒng)STSS(space tracking and surveillance system)，即空間跟蹤與監(jiān)視系統(tǒng)，其主要任務(wù)是彈道導(dǎo)彈初段，中段及末段跟蹤與識(shí)別。

2.1.1 天基預(yù)警系統(tǒng)組成

本文仿真場(chǎng)景星座采用的是Walker-Delta構(gòu)型，用衛(wèi)星數(shù)目T、軌道面數(shù)P、相位參數(shù)F描述，用來表示，整個(gè)系統(tǒng)由24顆衛(wèi)星組成。

天基預(yù)警系統(tǒng)的星座構(gòu)架T/P/F為24/3/1，地1個(gè)軌道面初始時(shí)刻的升交點(diǎn)赤經(jīng)為0°，第1個(gè)軌道面第1顆衛(wèi)星初始時(shí)刻的幅角為0°，為了滿足全球覆蓋，所以采用極地軌道，其軌道傾角為90°；每顆衛(wèi)星的軌道高度為1 600 km。

2.1.2 天基預(yù)警系統(tǒng)的工作方式

天基預(yù)警系統(tǒng)中每顆低軌衛(wèi)星采用臨邊觀測(cè)跟蹤傳感器，采用短波長(zhǎng)探測(cè)方式。臨邊以上的工作方式指的是自衛(wèi)星與地球切線開始向切線上方掃描的過程，臨邊即沿切線的含義。臨邊觀測(cè)本質(zhì)上是一種基于空域的觀測(cè)方式。

2.2 算法對(duì)比

本節(jié)基于該場(chǎng)景將天基預(yù)警連續(xù)搜索空間蟻群多目標(biāo)優(yōu)化算法與基于規(guī)則的元啟發(fā)式算法[7]以及動(dòng)態(tài)蟻群算法[19]進(jìn)行對(duì)比。

天基預(yù)警任務(wù)中，由于星座均勻分布，因此目標(biāo)分布越集中，預(yù)警系統(tǒng)的可用資源越少，對(duì)算法的要求越高。因此，為了全面比較3種算法，將導(dǎo)彈設(shè)置為相同發(fā)射點(diǎn)不同落點(diǎn)，并設(shè)計(jì)了資源充足，資源緊缺和資源嚴(yán)重不足3種場(chǎng)景。算法評(píng)價(jià)值為優(yōu)化目標(biāo)的加權(quán)和：

(5)

2.2.1 資源充足場(chǎng)景仿真

資源充足場(chǎng)景選擇2枚單彈頭的二級(jí)導(dǎo)彈作為觀測(cè)目標(biāo)。2枚導(dǎo)彈選擇了相同的發(fā)射點(diǎn)，不同的飛行高度和不同的目標(biāo)點(diǎn)。這種情況對(duì)任務(wù)規(guī)劃算法的壓力較低，以此來比較3種算法在資源充足場(chǎng)景中的能力。

1)彈道參數(shù)

2枚導(dǎo)彈選擇相同發(fā)射點(diǎn)經(jīng)度：100°、緯度：41°、高度：1 km，同時(shí)，彈道高度和目標(biāo)點(diǎn)相距較遠(yuǎn)，使得預(yù)警資源比較充足，通過下面的計(jì)算結(jié)果比較3種算法的不同能力。

表1 導(dǎo)彈參數(shù)Table 1 Missile parameters

2)計(jì)算結(jié)果

資源充足場(chǎng)景中，3種算法總觀測(cè)時(shí)長(zhǎng)比較接近，均可以獲得長(zhǎng)時(shí)間覆蓋目標(biāo)的觀測(cè)結(jié)果。同時(shí)，多目標(biāo)蟻群算法的傳感器切換次數(shù)和單星觀測(cè)時(shí)長(zhǎng)均小于前2種算法，顯示出優(yōu)異的優(yōu)化性能，在資源充足場(chǎng)景中更合理的利用觀測(cè)資源。

表2 評(píng)價(jià)指標(biāo)Table 2 Evaluating indicator

2.2.2 資源緊缺場(chǎng)景仿真

資源緊缺場(chǎng)景選擇5枚中遠(yuǎn)射程導(dǎo)彈作為觀測(cè)目標(biāo)。5枚導(dǎo)彈選擇了相同的發(fā)射點(diǎn)，不同的飛行高度和不同的目標(biāo)點(diǎn)。相比于上一個(gè)場(chǎng)景，本場(chǎng)景對(duì)資源的需求量更大，以此來比較3種算法在資源緊缺場(chǎng)景中的能力。

1)彈道參數(shù)

5枚導(dǎo)彈選擇相同的發(fā)射點(diǎn)經(jīng)度100°、緯度41°、高度1 km，并且選擇中遠(yuǎn)射程導(dǎo)彈，相比于上一場(chǎng)景中的近程導(dǎo)彈，對(duì)預(yù)警系統(tǒng)的資源需求量更大。

2)計(jì)算結(jié)果

資源緊缺場(chǎng)景中元啟發(fā)式算法雖然也獲得了滿足覆蓋時(shí)間的優(yōu)化結(jié)果，但單星觀測(cè)時(shí)長(zhǎng)平均值為827.2 s，高于另2個(gè)算法，傳感器疲勞度較高，因此評(píng)價(jià)值最低。動(dòng)態(tài)蟻群算法的優(yōu)化結(jié)果擁有最長(zhǎng)的目標(biāo)覆蓋時(shí)間，同時(shí)單星觀側(cè)時(shí)長(zhǎng)低于元啟發(fā)式算法，因此評(píng)價(jià)值較高。多目標(biāo)蟻群算法的優(yōu)化結(jié)果不僅平均切換次數(shù)最少，同時(shí)單星觀側(cè)時(shí)間也遠(yuǎn)低于前兩種算法，對(duì)3種優(yōu)化目標(biāo)的均衡性和尋優(yōu)性最好，因此高評(píng)價(jià)值最高。

圖5 動(dòng)態(tài)蟻群算法計(jì)算結(jié)果Fig.5 Results of dynamic ant colony algorithm

圖6 連續(xù)域蟻群算法結(jié)果Fig.6 Continuous domain ant colony algorithm results

表3 導(dǎo)彈參數(shù)Table 3 Missile parameters

2.2.3 資源嚴(yán)重不足場(chǎng)景仿真

資源嚴(yán)重不足場(chǎng)景選擇8枚遠(yuǎn)程導(dǎo)彈作為觀測(cè)目標(biāo)。8枚導(dǎo)彈選擇相同發(fā)射點(diǎn)經(jīng)度100°、緯度41°、高度1 km，并同時(shí)發(fā)射，因此預(yù)警系統(tǒng)資源無法同時(shí)觀測(cè)所有目標(biāo)，導(dǎo)彈飛行高度分布在1 200～3 100 km不等，射程在3 406～6 089 km不等，在滿足資源嚴(yán)重不足的條件的同時(shí)，豐富彈道種類，以檢驗(yàn)算法普遍性。此場(chǎng)景仿真目的是對(duì)天基預(yù)警系統(tǒng)傳感器資源嚴(yán)重不足的情況進(jìn)行仿真，測(cè)試3種算法在資源嚴(yán)重不足場(chǎng)景中的能力。

1)彈道參數(shù)

圖7 基于規(guī)則的元啟發(fā)式算法計(jì)算結(jié)果Fig.7 Results of rule based meta heuristic algorithm

圖8 動(dòng)態(tài)蟻群算法計(jì)算結(jié)果Fig.8 Results of dynamic ant colony algorithm

圖9 連續(xù)域蟻群算法結(jié)果Fig.9 Continuous domain ant colony algorithm results

表4 評(píng)價(jià)指標(biāo)Table 4 Evaluating indicator

表5 導(dǎo)彈參數(shù)Table 5 Missile parameters

2)計(jì)算結(jié)果

資源嚴(yán)重不足場(chǎng)景中，元啟發(fā)式算法的總觀測(cè)時(shí)長(zhǎng)，但同時(shí)存在切換次數(shù)多和單星疲勞度高等問題，元啟發(fā)式算法為固定邏輯搜索算法，在資源壓力較大時(shí)，存在多目標(biāo)優(yōu)化性能弱的問題。動(dòng)態(tài)蟻群算法通過隨機(jī)尋優(yōu)的方式，優(yōu)化結(jié)果中切換次數(shù)和疲勞度2個(gè)優(yōu)化目標(biāo)均優(yōu)于元啟發(fā)式算法，但仍沒有多目標(biāo)蟻群算法的尋優(yōu)結(jié)果理想。多目標(biāo)蟻群算法在滿足總觀測(cè)時(shí)長(zhǎng)的前提下，切換次數(shù)和疲勞度均低于另外2種算法，可見，在資源嚴(yán)重不足的場(chǎng)景中，多目標(biāo)蟻群優(yōu)化算法具有更好的優(yōu)化性能。

圖10 基于規(guī)則的元啟發(fā)式算法計(jì)算結(jié)果Fig.10 Results of rule based meta heuristic algorithm

圖11 動(dòng)態(tài)蟻群算法計(jì)算結(jié)果Fig.11 Results of dynamic ant colony algorithm

圖12 連續(xù)域蟻群算法結(jié)果Fig.12 Continuous domain ant colony algorithm results

表6 評(píng)價(jià)指標(biāo)Table 6 Evaluating indicator

3 結(jié)論

1)本文針對(duì)天基預(yù)警系統(tǒng)傳感器調(diào)度問題中，本文根據(jù)任務(wù)中的約束情況，提出了一種天基預(yù)警連續(xù)搜索空間多目標(biāo)蟻群優(yōu)化算法，解決了傳統(tǒng)蟻群算法在天基預(yù)警任務(wù)規(guī)劃中存在多目標(biāo)權(quán)衡能力差，連續(xù)搜索空間計(jì)算效率低等問題。

2)本文以擴(kuò)展蟻群算法為搜索引擎，采用基于R2指標(biāo)的天基預(yù)警方案排序算法來尋找最優(yōu)解。該算法適用于天基預(yù)警星座系統(tǒng)對(duì)彈道導(dǎo)彈等具有紅外特性運(yùn)動(dòng)目標(biāo)的跟蹤方案優(yōu)化問題。

3)本文參考美國(guó)天基預(yù)警系統(tǒng)設(shè)計(jì)仿真場(chǎng)景，并將算法與元啟發(fā)式和動(dòng)態(tài)蟻群算法在資源充足、資源緊缺和資源嚴(yán)重不足3種仿真場(chǎng)景中進(jìn)行對(duì)比仿真，仿真結(jié)果基于蟻群的天基預(yù)警多目標(biāo)優(yōu)化算法在3種場(chǎng)景中均表現(xiàn)出良好的優(yōu)化性能。