基于分布式協(xié)同進化的星座自主任務(wù)規(guī)劃算法

高天旸, 胡笑旋, 夏 維

(1. 合肥工業(yè)大學(xué)管理學(xué)院, 安徽 合肥 230009; 2. 過程優(yōu)化與智能決策教育部重點實驗室, 安徽 合肥 230009)

0 引 言

對地觀測衛(wèi)星,即遙感衛(wèi)星,是一種廣泛應(yīng)用于地面勘探、環(huán)境監(jiān)測、氣象預(yù)測、軍事偵查等重要領(lǐng)域的戰(zhàn)略資源。在傳統(tǒng)遙感衛(wèi)星系統(tǒng)應(yīng)用過程中,衛(wèi)星任務(wù)規(guī)劃通常在地面進行,在應(yīng)對突發(fā)需求時制定的新方案往往需要等待下一次衛(wèi)星過境測控站才能上注執(zhí)行,這極大地限制了遙感衛(wèi)星系統(tǒng)的響應(yīng)速度[1-2]。隨著星載計算能力的提升,衛(wèi)星任務(wù)規(guī)劃自主化成為了可能,自主化即減弱衛(wèi)星運行對地面系統(tǒng)的依賴,將任務(wù)規(guī)劃運算交由星載芯片進行,能一定程度擺脫測控可見性的限制[3-4]。當(dāng)前,遙感衛(wèi)星系統(tǒng)不斷由多星向星群、星座發(fā)展,其星間協(xié)作關(guān)系愈加密切,星座協(xié)同自主任務(wù)規(guī)劃逐漸成為自主化衛(wèi)星管理與控制方法的主要發(fā)展方向[5]。

星座協(xié)同自主任務(wù)規(guī)劃旨在為不同物理結(jié)構(gòu)的星座系統(tǒng)設(shè)計采用不同組織結(jié)構(gòu)的協(xié)同策略與相應(yīng)的優(yōu)化算法,從而令星座內(nèi)各星互相協(xié)同合作以共同制訂整體任務(wù)執(zhí)行方案。自主協(xié)同星座的組織結(jié)構(gòu)主要可分為全集中式、集中協(xié)調(diào)式、并行集中式(部分分布式)與全分布式4類,其中前三者可以被歸納為層級化結(jié)構(gòu)[6]。文獻[7-8]面向主從結(jié)構(gòu)星座系統(tǒng),設(shè)計了一種全集中式混合動態(tài)變異遺傳算法與兩種重規(guī)劃方法,其方案由主星規(guī)劃形成并分發(fā)至各從星執(zhí)行。文獻[9]提出了一種集中協(xié)調(diào)式規(guī)劃策略,先由主星將任務(wù)信息廣播至各從星,各從星評估自身觀測能力與成本形成報告返還主星,最終由主星選定各任務(wù)執(zhí)行星。文獻[10]提出了一種多維多智能體協(xié)作模型,主星使用基于合同網(wǎng)協(xié)議的分配方法,通過公告、招標(biāo)、授予等步驟對各從星進行任務(wù)分配與重分配。在層級化結(jié)構(gòu)中,各星被分為主星與從星兩種角色,主星負責(zé)對系統(tǒng)進行統(tǒng)籌規(guī)劃并主持星間協(xié)調(diào)過程,從星被動地接收來自主星的籌劃結(jié)果、進行自我方案規(guī)劃并參與協(xié)調(diào)過程。采用層級化結(jié)構(gòu)的方法具有清晰的規(guī)劃流程,能快速形成有效方案,但由于其流程圍繞主星節(jié)點開展,對其的計算能力與通信環(huán)境的要求較高,因此主要應(yīng)用于擁有高算力節(jié)點或穩(wěn)定通信總線的星座系統(tǒng)。

在采用層級化結(jié)構(gòu)的自主星座中,當(dāng)主星遭遇意外而失效時,整個系統(tǒng)將陷入癱瘓,而采用全分布式結(jié)構(gòu)則可避免此類問題。文獻[11-12]將主星損壞后星座內(nèi)剩余各從星看作多個互相通信與協(xié)商的獨立智能體,并分別對其效用函數(shù)進行識別,提出了基于效用的后悔博弈、煙霧信號博弈和基于廣播的博弈作為分布式協(xié)商策略,并改進混合動態(tài)變異遺傳算法以使其適用于分布式優(yōu)化環(huán)境。文獻[13]設(shè)計了一種多星智能體協(xié)調(diào)協(xié)商任務(wù)分配算法,率先收到任務(wù)信息的衛(wèi)星向其所有鄰近星廣播以構(gòu)成群組,群組內(nèi)各星首先評估自身對各任務(wù)的執(zhí)行意向,隨后共同進入一種基于最大增益信息算法的分布式協(xié)調(diào)迭代優(yōu)化過程以形成最終分配方案。文獻[14-15]提出了一種基于任務(wù)聯(lián)盟構(gòu)建的星間協(xié)作方法,各星智能體通過基于信任度的知識傳播策略以不斷傳遞已知任務(wù)信息與他星執(zhí)行意向信息,并據(jù)此改進自身意向以優(yōu)化整體任務(wù)分配方案。在全分布式結(jié)構(gòu)中,各星作為平等個體共同參與協(xié)調(diào)優(yōu)化過程,通過積極的通信交互以對任務(wù)分配進行協(xié)調(diào)并生成相應(yīng)的執(zhí)行方案。采用全分布式結(jié)構(gòu)的方法可利用不同星間的通信能力組成信息網(wǎng)絡(luò)以支持其協(xié)調(diào)過程,從而使各星承擔(dān)的通信與計算壓力更加平均,適用于不具備強算力節(jié)點或星間通信能力不穩(wěn)定的星座系統(tǒng)。

基于上述分析,本文進一步探究全分布式結(jié)構(gòu)方法對各星計算資源的運用方式,提出了一種全分布式星座協(xié)同迭代優(yōu)化策略,將制定多星整體方案的總問題轉(zhuǎn)換為多個制訂單星方案的分問題。在該策略中,各星被看作為獨立智能體,通過“接收”“更新”“發(fā)布”的三階段協(xié)作行為在相應(yīng)分問題解空間中探索總問題的優(yōu)質(zhì)解。在此基礎(chǔ)上,本文設(shè)計了一種分布式多智能體合作式協(xié)同進化遺傳算法,該算法對不同衛(wèi)星方案進行編碼形成多個亞種群,利用不同自主衛(wèi)星的計算資源實現(xiàn)各亞種群并行進化,并通過各亞種群特征信息的傳播與接受過程來協(xié)調(diào)任務(wù)在各星間的分配。同時,設(shè)計了一種包含時間窗間重疊度因素與自適應(yīng)機制的適應(yīng)度函數(shù),能夠有效引導(dǎo)各亞種群共同朝著提升整體方案質(zhì)量的方向進化,進一步增強算法的尋優(yōu)能力。最后,本文在S698PM嵌入式開發(fā)環(huán)境下進行仿真實驗,結(jié)果表明,所提出方法在小規(guī)模問題中能求得與CPLEX效果相當(dāng)?shù)膬?yōu)質(zhì)解,在大規(guī)模問題中表現(xiàn)出比貪婪算法與集中式遺傳算法更強的優(yōu)化能力,同時在惡劣通信環(huán)境下展現(xiàn)出良好的適應(yīng)性,適用于不同拓撲結(jié)構(gòu)的星座系統(tǒng)。

1 問題描述

在一個由多顆自主遙感衛(wèi)星組成的星座系統(tǒng)中,各星除了基本的觀測與通信能力外,還都擁有一定的星載算力,且具有計算任務(wù)目標(biāo)訪問時間窗的功能。如圖1所示,當(dāng)一批待觀測任務(wù)集合信息以地面上注或星上自生成等方式到達星座中任一衛(wèi)星,該星作為規(guī)劃發(fā)起星,需要調(diào)動星座內(nèi)的其他衛(wèi)星與其共同針對該任務(wù)集合進行分配與規(guī)劃,以求整體方案中的被執(zhí)行的任務(wù)權(quán)重的總和最大。該任務(wù)集合中包含一定數(shù)量的地面點目標(biāo),對其中任一目標(biāo)的觀測都需要占用一顆遙感衛(wèi)星的一段工作時間,且執(zhí)行時間段必須在該衛(wèi)星對目標(biāo)的可見時間窗內(nèi)。

1.1 概念定義

(1) 任務(wù):T={t1,t2,…,ti,…,tNT}表示一批剛到達的待規(guī)劃任務(wù)集合,NT為集合中任務(wù)的數(shù)量,其中每一個任務(wù)ti可以通過一個二元組ti=(tvi,di)表示,i為任務(wù)序號,tvi表示該任務(wù)的權(quán)重,di表示該任務(wù)所需觀測持續(xù)時間。

(2) 衛(wèi)星:S={s1,s2,…,sj,…,sNS}表示星座系統(tǒng)中所有衛(wèi)星的集合,NS為集合中衛(wèi)星的數(shù)量。

1.2 多星任務(wù)規(guī)劃問題模型

根據(jù)上述定義對星座內(nèi)的多星任務(wù)規(guī)劃問題進行建模,可得模型如下:

(1) 決策變量

(2) 目標(biāo)函數(shù)

在系統(tǒng)整體執(zhí)行方案中所有被安排執(zhí)行的任務(wù)的總權(quán)重之和最大。

(1)

(3) 約束條件

(2)

(3)

(4)

其中,式(2)表示每個觀測任務(wù)最多只能被執(zhí)行一次;式(3)表示同一衛(wèi)星對先后兩個任務(wù)的觀測持續(xù)時間不能有重疊;式(4)表示每個任務(wù)執(zhí)行持續(xù)時間必須在其可見時間窗內(nèi)。

1.3 全分布式環(huán)境下單星規(guī)劃分問題

在全分布式環(huán)境下,受限于全局信息(他星任務(wù)可見性與初始執(zhí)行狀態(tài))的缺失,單星智能體在協(xié)調(diào)優(yōu)化過程中對星座內(nèi)多星任務(wù)規(guī)劃問題的探索能力僅限于對自身規(guī)劃方案進行調(diào)整。如圖2所示,將制定多星整體方案的總問題轉(zhuǎn)化為多個制訂單星方案的分問題并分別交由對應(yīng)各星智能體進行獨立探索。各分問題模型僅包含與本星方案相關(guān)的決策變量,其余變量則通過讀取他星方案作為已知常量輸入,而目標(biāo)函數(shù)與約束條件則與總問題相同。將各分問題的解組合即可形成總問題的解,各星通過探索不同的單星方案組合以對整體方案進行尋優(yōu)。

(5)

(6)

2 分布式協(xié)同規(guī)劃算法

針對上述遙感星座自主協(xié)同任務(wù)規(guī)劃問題,本文設(shè)計了一整套的全分布式協(xié)同優(yōu)化策略與相應(yīng)規(guī)劃算法,本節(jié)將對其進行具體描述。

2.1 全分布式星座協(xié)同迭代優(yōu)化策略

受啟發(fā)于文獻[19]中描述的分布式多智能體組合優(yōu)化啟發(fā)式(combinatorial optimization heuristic for distributed agents, COHDA)算法,本文設(shè)計了一種基于“接收”“更新”“發(fā)布”的三階段協(xié)作行為的全分布式星座協(xié)同迭代優(yōu)化策略,如圖3所示。

其主要流程如下。

步驟1發(fā)起星將任務(wù)集合信息廣播至星座內(nèi)其余各星,各星隨即針對任務(wù)集合進行自我規(guī)劃形成本星初始方案并儲存至本星方案集,系統(tǒng)進入方案優(yōu)化階段。

步驟2在方案優(yōu)化階段中,各星不斷循環(huán)進行以下三階段行為:① 向星座內(nèi)其余各星發(fā)送本星方案集中的方案;② 將從他星接受到的最新方案儲存至本星方案集;③ 根據(jù)方案集中的他星最新方案優(yōu)化更新自身方案并儲存至本星方案集,隨后返回階段①。

步驟3當(dāng)?shù)竭_預(yù)設(shè)的運行時限后,方案優(yōu)化階段結(jié)束,此時各星上儲存的方案集內(nèi)容均相同,都包含各星最新提出的本星方案,但不同星方案之間仍可能存在重復(fù)執(zhí)行沖突;各星對其進行規(guī)則統(tǒng)一的沖突消解后形成最終整體方案。

2.2 多智能體合作式協(xié)同進化遺傳算法

基于上述全分布式星座協(xié)同迭代優(yōu)化策略,本文設(shè)計了一種多智能體合作式協(xié)同進化遺傳算法(distributed agent-collaborative coevolution genetic algorithm,DA-CCGA),CCGA[20]是傳統(tǒng)遺傳算法的變體,其使用多個并行進化的亞種群將對復(fù)雜問題的優(yōu)化搜索過程分解為對多個較簡單的分問題并行搜索,具有對分布式計算環(huán)境的先天適應(yīng)性[21]。DA-CCGA由CCGA融合上述全分布式優(yōu)化策略而形成,令代表不同星方案的亞種群分布于相應(yīng)星上,各星亞種群相對獨立地進化以探索本星方案分問題,并通過交換種群特征信息以輔助適應(yīng)度評價過程。DA-CCGA如算法1所示。

算法1 DA-CCGA輸入:衛(wèi)星集合S;本星編號sid;待規(guī)劃元任務(wù)集合T;待規(guī)劃任務(wù)的本星時間窗集合TWsid;傳播周期Pspread;規(guī)劃運行時限Ptmax輸出:最終整體規(guī)劃方案P*1初始化最優(yōu)印象集I*sid與抽樣印象集Isamsid2初始化本星初始亞種群P0sid←init(TWsid)3計算初始亞種群適應(yīng)度estimate(P0sid,I*sid,Isamsid)4向他星傳播印象集spread(P0sid,I*sid,Isamsid)5初始化代數(shù)計數(shù)g←16 While 當(dāng)前運行耗時ptPspread then15 向他星傳播印象集spread(P0sid,I*sid,Isamsid)16 增加代數(shù)計數(shù)g←g+117 End while18從最優(yōu)印像集中提取最終方案P*←extract(I*sid)19 Return P*

(1) 染色體編碼與解碼

(2) 印象集

非小細胞肺癌表皮生長因子受體基因突變274例分析…………………………………………………… 王 艷等（20）：2817

在DA-CCGA中,各星儲存的方案集被擴充為“印象集”,即本星記錄的對他星亞種群特征個體的印象,包括“最優(yōu)印象集”,即已知最新的各亞種群最優(yōu)方案個體集合,與“抽樣印象集”,即已知最新的從各亞種群隨機抽取的方案個體集合。印象集中的所有方案個體均依據(jù)“最后更新時間戳”進行管理。各星通過不斷地傳播、接收、更新再傳播印象集信息,以滿足各亞種群在進行適應(yīng)度評價時對他星方案信息的需求。

(3) 適應(yīng)度函數(shù)

如圖5所示,各星亞種群中單條染色體的適應(yīng)度值為其與他星染色體組成的整體方案的計算值,計算函數(shù)如下:

(7)

(4) 適應(yīng)度評價過程

(8)

(5) 亞種群協(xié)作策略

如圖6所示,傳播種群特征即向所有鄰近星發(fā)送本星儲存的印象集信息,在每次發(fā)送前需要隨機從本星亞種群中抽取的一個方案個體以更新本星抽樣印象集。而接受種群特征即接收來自他星的印象集信息并根據(jù)其時間戳更新本星印象集,若接收后本星印象集發(fā)生變化則需重新計算本星亞種群內(nèi)所有個體的適應(yīng)度。

(6) 交叉與變異

如圖8所示,變異算子隨機作用于染色體的某個基因位上,將該基因位的執(zhí)行任務(wù)去除后嘗試重新插入除任務(wù)以外的任務(wù)后得到變異后的染色體。

(7) 最終整體方案提取

3 仿真實驗分析

為了驗證本文所提出的方法的適用性與有效性,本節(jié)使用S698PM嵌入式開發(fā)環(huán)境模擬星座系統(tǒng)中分布式星載算力以對其自主任務(wù)規(guī)劃過程進行仿真實驗,該星座由5顆自主遙感衛(wèi)星組成,其中2顆為中軌衛(wèi)星,其余3顆為低軌。實驗?zāi)M五星星座在一定規(guī)劃運行時限內(nèi)對一定規(guī)模任務(wù)集合在特定規(guī)劃時域內(nèi)的方案進行自主規(guī)劃,規(guī)劃使用的任務(wù)點目標(biāo)坐標(biāo)數(shù)據(jù)為隨機生成,其可見時間窗數(shù)據(jù)由仿真軟件模擬計算。

3.1 參數(shù)與通信環(huán)境敏感性測試

為了測試部分重要參數(shù)與星間通信環(huán)境變化對于DA-CCGA效能的影響,使用相應(yīng)不同設(shè)置的多組實驗進行對比分析,每組重復(fù)運行50次并計算平均目標(biāo)函數(shù)值,在測試中,待規(guī)劃任務(wù)數(shù)量為1 000,規(guī)劃時域長度為12 h,規(guī)劃運行時限為30 min(1 800 s)。

(1) 傳播周期影響

在DA-CCGA中,由于各亞種群的適應(yīng)度評價過程依賴于對其他亞種群特征信息的獲取,故各衛(wèi)星在優(yōu)化過程中進行種群特征傳播的頻率變化必然會對算法效能造成影響,為探究其具體影響模式,設(shè)置不同傳播周期時長的實驗組進行對比,最終結(jié)果如圖10所示。

可見,傳播周期變化對算法效能的影響并非是單向的,過短或過長的傳播周期均會降低算法的尋優(yōu)能力與穩(wěn)定性,這通常是因為過于頻繁的傳播與接收將導(dǎo)致各星反復(fù)對亞種群進行重新評估,在大量占用計算資源的同時過度限制各亞種群的搜索方向,妨礙了搜索過程的有效進行。當(dāng)傳播周期適中(15～20 s)時算法優(yōu)化效能達到峰值,此時各星在整個規(guī)劃過程中可向他星傳播種群特征信息89～119次。隨后繼續(xù)增加傳播周期至450 s(傳播4次),算法仍能以良好的穩(wěn)定性得到滿意解(與峰值的平均差距小于1.1%),但當(dāng)傳播周期增加至600 s(傳播2次)以上時,在尋優(yōu)能力降低的同時算法的穩(wěn)定性也受到顯著影響?？梢奃A-CCGA能以較低的星間通信頻率到達接近高頻率的效果,對惡劣的星間通信環(huán)境具有良好的適應(yīng)性,但仍需要一定次數(shù)的星間通信以支持其各亞種群的有效進化。

(2) 啟發(fā)式因子影響

(3) 星間拓撲與通信能力影響

在現(xiàn)實應(yīng)用環(huán)境中,不同星座系統(tǒng)在不同時刻可能擁有不同的星間拓撲結(jié)構(gòu)與相應(yīng)的通信能力,為了檢驗DA-CCGA對不同通信環(huán)境的適應(yīng)能力,設(shè)置以下通信拓撲場景,所有場景時長均為30 min:

① 穩(wěn)定通信環(huán)境場景

S:其中一星與其他所有星之間可以穩(wěn)定互相通信,其余星之間無法通信,即星形拓撲結(jié)構(gòu);

C:所有衛(wèi)星均可以穩(wěn)定與左右兩鄰星互相通信通信以組成環(huán)形拓撲結(jié)構(gòu);

L:去除環(huán)形拓撲中某兩星的相互通信能力以形成線形拓撲結(jié)構(gòu);

A:所有衛(wèi)星均可以穩(wěn)定與任意另一星互相通信的網(wǎng)狀拓撲結(jié)構(gòu)。

② 不穩(wěn)定通信環(huán)境場景

M:由仿真軟件模擬計算出2021年1月18日18:00至2021年1月18日18:30時間段內(nèi)各星間真實可見性組成的不穩(wěn)定通信環(huán)境場景；

S30-A30:場景開始后的30 s內(nèi)為“S”,場景結(jié)束前的30 s內(nèi)為“A”,其余時間任意兩星間均無法通信;

S1-A30:場景開始后的1 s內(nèi)為“S”,場景結(jié)束前的30 s內(nèi)為“A”,其余時間任意兩星間均無法通信。

使用以上通信環(huán)境設(shè)置不同實驗組進行對比,最終結(jié)果如圖12所示。

如圖12(a)所示,在穩(wěn)定通信環(huán)境場景中,不同星間拓撲結(jié)構(gòu)實驗組的結(jié)果均十分相似,其中A與C拓撲結(jié)構(gòu)略優(yōu),S與L拓撲結(jié)構(gòu)稍次之,可見DA-CCGA對不同拓撲結(jié)構(gòu)的星座具有較強的適用性,但通信機會在星座內(nèi)分布較為廣泛且平均的拓撲結(jié)構(gòu)依然能對算法效能產(chǎn)生正向的影響。

如圖12(b)所示,DA-CCGA在M中的表現(xiàn)與其在穩(wěn)定通信環(huán)境場景各實驗組中的非常接近,這再一次驗證了DA-CCG對惡劣的星間通信環(huán)境的適應(yīng)性。而S30-A30與S1-A30均為僅允許衛(wèi)星在規(guī)劃運行開始后與結(jié)束前的小段時間內(nèi)進行通信的極端惡劣通信環(huán)境場景,但對算法性能的影響卻有巨大差距。算法在S30-A30中的表現(xiàn)僅略遜于各穩(wěn)定通信環(huán)境場景與M(差距在0.4%以內(nèi)),而S1-A30的結(jié)果卻與M擁有4.98%的差距,由此可見DA-CCGA適應(yīng)惡劣通信環(huán)境的前提是:各星在優(yōu)化搜索過程的初期擁有足夠的通信機會以充分了解他星初始亞種群的種群特征,從而有效指導(dǎo)本星亞種群在整個運行過程中的進化。

3.2 對比實驗

DA-CCGA作為一種全分布式搜索算法,可充分地利用分布于星座內(nèi)的計算資源以不斷對問題進行尋優(yōu),但同時其搜索優(yōu)化過程卻依賴于各節(jié)點間的通信協(xié)調(diào)。為了具體對比DA-CCGA與傳統(tǒng)集中式方法的尋優(yōu)能力,設(shè)置了多組不同問題規(guī)模的實驗組,分別使用貪婪插入(greedy insert, GI)算法、集中式遺傳算法(centralized genetic algorithm,CGA)與DA-CCGA進行優(yōu)化求解,同時將第1.2節(jié)中描述的多星任務(wù)規(guī)劃模型線性化后使用CPLEX嘗試求其精確解與上述算法優(yōu)化結(jié)果進行對比,其中CGA僅使用單顆模擬衛(wèi)星算力運行,CGA與DA-CCGA均重復(fù)運行50次并計算平均目標(biāo)函數(shù)值,最終結(jié)果如表1所示。表1中“—”表示無法求解;規(guī)劃運行時限僅針對CGA與DA-CCGA,而CPLEX運行耗時并未給出。

表1 算法對比測試結(jié)果

當(dāng)問題規(guī)模較小(任務(wù)量小于等于250)時,GI、CGA與DA-CCGA均能以較短的運行時間得出與CPLEX精確解相同或相近的結(jié)果,當(dāng)問題規(guī)模擴大(任務(wù)量大于250)時,CPLEX由于模型約束數(shù)量限制被超過而無法求解,而CI、CGA與DA-CCGA之間的差距逐漸擴大,且DA-CCGA一直具有明顯的優(yōu)勢。以1 000任務(wù)數(shù)測試組為例,如圖13所示,從單次運行結(jié)果的分布區(qū)間來看,DA-CCGA的穩(wěn)定性略優(yōu)于CGA,兩者的尋優(yōu)效率都隨著運行時間的延長而減緩,但DA-CCGA的減緩速度明顯低于CGA,當(dāng)?shù)竭_25 min時,CGA已趨于收斂,而DA-CCGA則仍具有可繼續(xù)優(yōu)化的趨勢。最終DA-CCGA搜索到的最優(yōu)解目標(biāo)函數(shù)值平均比CGA高出2.85%?？梢?DA-CCGA對于星座任務(wù)規(guī)劃問題,特別是大規(guī)模問題,具有相較于傳統(tǒng)集中式方法更強的優(yōu)化搜索能力。

4 結(jié) 論