基于雙種群進(jìn)化算法的對地觀測衛(wèi)星一體化調(diào)度研究

周忠寶，李瑞陽，常中祥*，陳恩銘，劉書源

(1.湖南大學(xué) 工商管理學(xué)院，湖南 長沙 410082；2.應(yīng)急管理智能決策技術(shù)湖南省重點實驗室，湖南 長沙 410082)

0 引言

近年來，我國航天事業(yè)快速發(fā)展，氣象、海洋、陸地資源衛(wèi)星和商業(yè)化遙感衛(wèi)星在軌數(shù)量已穩(wěn)居世界第二，尤其是近幾年發(fā)展迅速的商業(yè)化遙感衛(wèi)星在區(qū)域治理、災(zāi)害監(jiān)測和評估與救援等方面提供了重要的技術(shù)支撐[1]。然而，面對迅速增長的觀測需求，有限的對地觀測衛(wèi)星資源仍顯得異常寶貴，如何對衛(wèi)星資源進(jìn)行統(tǒng)籌規(guī)劃，在有限的時間內(nèi)利用更少的資源來完成更多觀測需求已經(jīng)成為衛(wèi)星管控領(lǐng)域的重要問題[2]。對地觀測衛(wèi)星任務(wù)可以分為衛(wèi)星成像觀測和成像數(shù)據(jù)回傳2個階段，而以往的研究中會優(yōu)先某一階段或聚焦單一階段進(jìn)行[3]。因此，研究高效、實用的對地觀測衛(wèi)星一體化調(diào)度方法對衛(wèi)星資源的高效利用具有重要意義[4]。

自1996年Bensana等人[5]提出衛(wèi)星日常管理問題以來，衛(wèi)星任務(wù)規(guī)劃問題已經(jīng)得到了廣泛且深入的研究[2-6]。2002年，Lematre[7]正式提出敏捷衛(wèi)星成像規(guī)劃問題，分析了敏捷成像的特點并從理論上證明敏捷衛(wèi)星成像規(guī)劃問題為高度復(fù)雜的NP-Hard問題。自此，國內(nèi)外的大量學(xué)者圍繞衛(wèi)星任務(wù)規(guī)劃問題展開了一系列研究，整體可分為3類[3]：第1類為分離式調(diào)度，類似于文獻(xiàn)[7]的研究，此類研究在任務(wù)規(guī)劃過程中只關(guān)注一個階段，如文獻(xiàn)[8-12]只關(guān)注成像觀測，而文獻(xiàn)[13-15]只關(guān)注數(shù)據(jù)回傳；第2類為妥協(xié)式調(diào)度，此類研究在任務(wù)規(guī)劃過程中重點對某一階段進(jìn)行優(yōu)化，并將另一階段轉(zhuǎn)化為約束條件，在任務(wù)規(guī)劃過程中一定程度上兼顧了2個階段[16-17]；第3類為一體化調(diào)度(亦稱綜合調(diào)度)，即在任務(wù)規(guī)劃過程中綜合考慮衛(wèi)星成像觀測和成像數(shù)據(jù)回放2個階段[18]，近年來已有部分學(xué)者開始聚焦于此類模型的構(gòu)建及相關(guān)算法的設(shè)計[19-21]。Chang等人[3]通過多種測試場景下的仿真實驗證明了一體化調(diào)度在上述3類調(diào)度中展現(xiàn)出巨大優(yōu)勢，因此本文在后續(xù)研究中也將采取此種調(diào)度模式，在問題假設(shè)和模型構(gòu)建中綜合考慮2個階段，從而實現(xiàn)二者協(xié)同優(yōu)化。

衛(wèi)星任務(wù)規(guī)劃問題作為一種復(fù)雜的組合優(yōu)化問題，無法在多項式時間內(nèi)求得其最優(yōu)解，而且在實際應(yīng)用中往往存在規(guī)模龐大、約束復(fù)雜和目標(biāo)不唯一等問題，這導(dǎo)致很難找到適用于所有問題的通用算法[2]。因此，大量學(xué)者將研究重點聚焦在衛(wèi)星任務(wù)規(guī)劃問題求解算法的設(shè)計，得益于進(jìn)化算法簡潔且高效的特性，遺傳算法[9,13,22]、蟻群算法[8,15,23]和差分進(jìn)化算法[24-25]等進(jìn)化算法在衛(wèi)星任務(wù)規(guī)劃問題的算法設(shè)計中得到了廣泛的應(yīng)用[4]。

以上研究雖然已經(jīng)能夠在一定程度上解決衛(wèi)星任務(wù)規(guī)劃的問題，但是仍然存在約束不全面或求解質(zhì)量不穩(wěn)定等問題。因此，本文針對對地觀測衛(wèi)星一體化調(diào)度問題，基于存在約束的雙種群進(jìn)化算法(Constrained Dual-Population Evolutionary Algorithm，c-DPEA)，結(jié)合啟發(fā)式規(guī)則設(shè)計了求解算法，為對地觀測衛(wèi)星資源的高效利用提供了一種高效、可靠的解決方案。

1 對地觀測衛(wèi)星一體化調(diào)度問題

對地觀測衛(wèi)星一體化調(diào)度問題中包括對地觀測衛(wèi)星、地面站以及觀測任務(wù)3個對象。每個任務(wù)可分為衛(wèi)星成像觀測和成像數(shù)據(jù)回傳2個階段，分別受到對地觀測衛(wèi)星與觀測任務(wù)的可見時間窗口限制和對地觀測衛(wèi)星與地面站的可見時間窗口限制。為明晰本文研究問題的重點和邊界，做出以下合理假設(shè)：

① 本文只考慮點目標(biāo)，即衛(wèi)星一次過境可以完整觀測的地面目標(biāo)；

② 由于衛(wèi)星觀測需求遠(yuǎn)大于衛(wèi)星觀測資源，假設(shè)每個目標(biāo)至多只能被觀測一次，且成像數(shù)據(jù)也至多回傳一次；

③ 衛(wèi)星為“記錄—回放”模式，即只有先完成地面目標(biāo)觀測，才可以進(jìn)行成像數(shù)據(jù)回放；

④ 成像數(shù)據(jù)按照“先記錄，先回放”的原則進(jìn)行數(shù)據(jù)回傳，且成像數(shù)據(jù)不可分割；

⑤ 若觀測數(shù)據(jù)被回傳或過期，則其所占據(jù)的衛(wèi)星存儲空間被釋放；

⑥ 觀測成像的數(shù)據(jù)產(chǎn)生速率和數(shù)據(jù)回傳速率一般成固定比例，在此處為方便計算，假設(shè)每個觀測任務(wù)的成像速率和回傳速率相等；

⑦ 同一衛(wèi)星在同一時刻只能與一個地面站進(jìn)行數(shù)據(jù)傳輸，且受最短工作時間約束；

⑧ 假設(shè)衛(wèi)星一直處于開機(jī)狀態(tài)，不考慮設(shè)備故障、特殊工況等問題，不考慮中繼衛(wèi)星。

對地觀測衛(wèi)星一體化調(diào)度問題的描述包括元素構(gòu)成和約束條件，可將其表示為P：

P={St,Et,GT,S,OTW,G,DTW,OT,DT,Cons}，

(1)

式中，[St,Et]為有效調(diào)度時間范圍，本文假設(shè)有效調(diào)度時間為24 h；GT={gt1,gt2,…,gtnGT}為地面目標(biāo)集合，每個地面目標(biāo)gti具有屬性：成像時長di，數(shù)據(jù)有效期oi，任務(wù)優(yōu)先級ωi；S={s1,s2,…,snS}為對地觀測衛(wèi)星集合，集合中共包含nS=|S|個衛(wèi)星，每個衛(wèi)星的最小成像時間均為d0，最大存儲空間為Θ；OTWij={otwij1,otwij2,…,otwijn(OTWij)}為衛(wèi)星sj與地面目標(biāo)gti的可見窗口集合，otwijk是衛(wèi)星sj上地面目標(biāo)gti的第k個可見時間窗口，集合中共包含n(OTWij)=|OTWij|個可見窗口，每個可見窗口具有屬性：窗口開始時間ostijk，窗口結(jié)束時間oetijk；G={g1,g2,…,gn(G)}為地面站集合，集合中共包含n(G)=|G|個地面站，每一個地面站的最短工作時間為d0；DTWlj={dtwlj1,dtwlj2,…,dtwljn(DTWlj)}為衛(wèi)星sj與地面站gl的可見窗口集合(亦稱傳輸窗口)，dtwljq是衛(wèi)星sj與地面站gl的第q個可見時間窗口，集合包括n(DTWlj)=|DTWlj|個可見目標(biāo)，每個可見窗口具有屬性：窗口開始時間dstljq，窗口結(jié)束時間detljq；OT={ot1,ot2,…,otn(OT)}為有效調(diào)度時間范圍內(nèi)，調(diào)度形成的觀測成像任務(wù)集合，包括n(OT)=|OT|個任務(wù)，每個觀測任務(wù)oti具有屬性：觀測目標(biāo)gti，執(zhí)行觀測任務(wù)的衛(wèi)星si，觀測任務(wù)開始時間ost′ijk，觀測任務(wù)結(jié)束時間oet′ijk；DT={dt1,dt2,…,dtn(DT)}為有效調(diào)度時間范圍內(nèi)，調(diào)度形成的數(shù)據(jù)回傳任務(wù)集合，集合包括n(DT)=|DT|個任務(wù)，每個數(shù)傳任務(wù)dtv(其中v=ljq)具有屬性：數(shù)傳任務(wù)對應(yīng)的觀測任務(wù)集合dSetv，執(zhí)行數(shù)傳任務(wù)的衛(wèi)星sv，數(shù)傳任務(wù)開始時間dst′ljq，數(shù)傳任務(wù)結(jié)束時間det′ljq；Cons為對地觀測衛(wèi)星一體化調(diào)度問題中所包含的所有約束條件，下面將對此部分內(nèi)容進(jìn)行詳細(xì)闡述。

2 對地觀測衛(wèi)星一體化調(diào)度模型

在對地觀測衛(wèi)星一體化調(diào)度問題中，綜合考慮觀測和數(shù)傳2個環(huán)節(jié)，因此對一個地面目標(biāo)只有完成觀測成像并在有效期內(nèi)完成成像數(shù)據(jù)回傳才可稱為一次成功的對地觀測，所以考慮Chang等人[3]提出的最小數(shù)據(jù)獲取失敗率f1(P)作為本模型的第一個優(yōu)化目標(biāo)：

(2)

同樣需要考慮如何在任務(wù)執(zhí)行過程中盡量使用較少的能源消耗。因此本模型的第2個優(yōu)化目標(biāo)為能源消耗率f2(P)，即觀測和數(shù)傳任務(wù)所使用的能源消耗占最大能源消耗的比例為：

(3)

式中，TEC為衛(wèi)星消耗的能源綜合；MEC為執(zhí)行所有觀測任務(wù)并用盡所有傳輸窗口所能產(chǎn)生的最大能源消耗。TEC的計算方法如下：

TEC=(nOT×eo+od×ro)+(nDT×ed+td×rd)+ct×rc+rt×rr，

(4)

式中，eo為觀測任務(wù)啟動能耗；od為全體觀測任務(wù)的執(zhí)行總時長；ro為觀測成像耗能功率；ed為數(shù)傳任務(wù)啟動能耗；td為全體數(shù)傳任務(wù)的傳輸總時長；rd為數(shù)據(jù)回傳耗能功率；ct和rt分別為姿態(tài)機(jī)動和天線校對的總時長；rc和rr分別為姿態(tài)機(jī)動功率和天線校對功率。類似的，可以計算得到MEC：

MEC=nGT×(eo+ro×max(di))+

nDTW×(ed+rd×max(detljq-dstljq))+rc×nGT×ρ+rr×nDTW×σ。

(5)

綜合以上，可以得到對地觀測衛(wèi)星一體化調(diào)度模型：

min{f1(P),f1(P)}，

(6)

s.t.

xi≤1，

(7)

ostijk·xi≤ost′ijk·xi≤oet′ijk·xi≤oetijk·xi，

(8)

(9)

(ost′i2jk2-oet′i1jk1)·OTAi1i2≥ρ·OTAi1i2，

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(dst′lj2q2-det′lj1q1)·DTAv1v2≥σ·DTAv1v2，

(17)

(18)

xi∈{0,1}。

(19)

本文綜合考慮衛(wèi)星成像觀測和數(shù)據(jù)回傳2個階段的工作，因此模型中需要兼顧2個階段中的各類約束[3]，數(shù)學(xué)模型中各公式含義如下：

3 基于雙種群進(jìn)化算法的衛(wèi)星一體化調(diào)度算法設(shè)計與實現(xiàn)

衛(wèi)星一體化調(diào)度問題是一類典型的約束多目標(biāo)優(yōu)化問題(Constrained Multiobjective Optimization Problems，CMOPs)，具有變量類型復(fù)雜、強(qiáng)約束和多目標(biāo)等求解難點。近年來，協(xié)同進(jìn)化算法的出現(xiàn)為解決此類復(fù)雜優(yōu)化問題提供了新的方向[26]。進(jìn)化算法在解決無約束多目標(biāo)優(yōu)化問題(Multi-objective Optimization Problems，MOPs)時已經(jīng)顯現(xiàn)出巨大的優(yōu)勢，然而CMOPs由于約束條件的存在求解時往往具有更大的挑戰(zhàn)[27]。Ming等人[28]針對存在約束的多目標(biāo)優(yōu)化問題提出了一種基于雙種群的協(xié)同進(jìn)化算法c-DPEA，該算法通過2個種群的互補(bǔ)和協(xié)作，實現(xiàn)了算法在求解CMOPs的過程中對收斂性和多樣性的兼顧。2個種群在處理不可行解時分別采取不同的方案，其中種群1為多樣性導(dǎo)向，注重解的目標(biāo)值優(yōu)化，保留種群中擁有良好目標(biāo)值不可行解，保證最終解的多樣性；而種群2則以可行性為導(dǎo)向，優(yōu)先保留可行解，追求更快的收斂速度。2個種群相互補(bǔ)充并在生成子代的過程中進(jìn)行信息交換，從而實現(xiàn)兼顧收斂性、多樣性和可行性的高效進(jìn)化。

3.1 基于排序的雙種群適應(yīng)度分配

Ming等人[28]在c-DPEA算法中提出了一種基于排序的自適應(yīng)適應(yīng)度分配方法bCAD，適應(yīng)度計算函數(shù)形式如下，

(20)

(21)

3.2 基于貪婪策略的種群初始化

由于衛(wèi)星一體化調(diào)度問題的復(fù)雜性，直接應(yīng)用進(jìn)化算法無法在短時間內(nèi)獲得優(yōu)質(zhì)解。通過啟發(fā)式規(guī)則形成較好的初始種群勢必有利于子代種群在優(yōu)化迭代的過程中快速向真實前沿靠攏，因此本文也在種群初始化過程中采用了一類受到廣泛使用的貪婪策略。具體流程如下：

① 隨機(jī)生成觀測任務(wù)開始時刻，并將觀測任務(wù)序列中的所有任務(wù)初始化為“執(zhí)行”；

② 首先對每顆衛(wèi)星的所有觀測任務(wù)按照優(yōu)先級由高到低排序；

③ 按照順序?qū)τ^測任務(wù)依次執(zhí)行時間窗口約束檢查，如果不滿足，則將對應(yīng)任務(wù)刪除，并對下一個觀測任務(wù)執(zhí)行時間窗口約束檢查，否則對觀測任務(wù)執(zhí)行④；

④ 對當(dāng)前觀測任務(wù)的前、后相鄰任務(wù)執(zhí)行時間沖突檢查，如存在時間沖突則刪除較低優(yōu)先級的觀測任務(wù)；

⑤ 按照“先觀測，先回傳”的原則生成數(shù)傳任務(wù)序列和數(shù)傳任務(wù)開始時間；

⑥ 再次進(jìn)行約束檢查，刪除無法在有效期內(nèi)回傳的觀測任務(wù)，得到初始解。

3.3 遺傳算子設(shè)計

由于本文中包含整數(shù)變量和實數(shù)變量2類變量，此處引入2類交叉算子和2類變異算子。交叉算子和變異算子均在一定概率下執(zhí)行。

交叉算子：針對整數(shù)變量，使用2點交叉算子，隨機(jī)選擇交配池中的2個個體，在觀測任務(wù)序列片段或數(shù)傳任務(wù)序列片段中隨機(jī)選擇2個交叉點，交換兩交叉點間的片段，即完成交叉操作。針對實數(shù)變量，使用模擬二進(jìn)制交叉(Simulated Binary Crossover，SBX)。

變異算子：針對整數(shù)變量，按照一定的變異概率對種群中的個體執(zhí)行變異操作，即選中一個個體后，隨機(jī)選擇一個變異位，改變變異位原始值，即將0改為1或?qū)?改為0。針對實數(shù)變量，采用多項式變異。

3.4 種群更新

在每一代結(jié)束時，將種群1和種群2中的個體合并為一個種群規(guī)模為2N的組合種群，然后通過二元錦標(biāo)賽從組合種群中選擇個體進(jìn)入交配池。首先對組合種群基于bCAD進(jìn)行排名，然后從組合種群中隨機(jī)選出的2個解，選擇bCAD分配排名更好的一個進(jìn)入交配池，在形成規(guī)模為2N的交配池后，通過引入交叉算子和變異算子產(chǎn)生種群規(guī)模為N的后代種群。

(22)

其中，

(23)

(24)

式中，γ為2個種群中相同解占種群規(guī)模的比例。

種群2則是通過將所有的不可行解投影至Fmax，F(xiàn)max為整個種群在各目標(biāo)維度的最大值所組成的負(fù)理想點，修正如式(25)所示，其中wf為Fmax所屬的單位向量。種群2通過對不可行解的修正，在種群更新過程中盡快實現(xiàn)對不可行解的淘汰，從而實現(xiàn)可行性導(dǎo)向的種群進(jìn)化，即：

(25)

2個種群差異化的更新方式結(jié)合bCAD自適應(yīng)適應(yīng)度分配方法，最終使得本算法能夠?qū)崿F(xiàn)在廣泛搜索的同時兼顧快速收斂，使得求解質(zhì)量和求解效率均得到保證。

3.5 操作算子設(shè)計

作為一種混合整數(shù)規(guī)劃問題，直接使用進(jìn)化算法求解衛(wèi)星一體化調(diào)度問題往往很難得到較好的結(jié)果。隨著啟發(fā)式規(guī)則的引入，通過一些操作算子對種群個體的任務(wù)序列進(jìn)行破壞和修復(fù)，能夠極大地改善算法的尋優(yōu)效率[29]。為此，本文引入4類破壞算子和對應(yīng)的4類修復(fù)算子，具體情況如下。

(1) 破壞算子

① 優(yōu)先級準(zhǔn)則破壞算子，按照優(yōu)先級從低到高對所有已調(diào)度任務(wù)進(jìn)行排序，并按照次序刪除任務(wù)，即優(yōu)先刪除低優(yōu)先級任務(wù)，并將對應(yīng)任務(wù)存入禁忌池。

② 能耗準(zhǔn)則破壞算子，按照能耗從高到低對所有已調(diào)度任務(wù)進(jìn)行排序，并按照次序刪除任務(wù)，即優(yōu)先刪除高能耗任務(wù)，并將對應(yīng)任務(wù)存入禁忌池。

③ 隨機(jī)準(zhǔn)則破壞算子，將所有已調(diào)度任務(wù)隨機(jī)排序，并按照次序刪除任務(wù)，并將對應(yīng)任務(wù)存入禁忌池。

④ 擁堵度準(zhǔn)則破壞算子，按照擁堵度(每個觀測任務(wù)時間窗口與其他觀測任務(wù)時間窗口發(fā)生沖突的次數(shù))由高到低將所有已調(diào)度任務(wù)排序，然后按照次序刪除任務(wù)，并將對應(yīng)任務(wù)存入禁忌池。

(2) 修復(fù)算子

① 優(yōu)先級準(zhǔn)則修復(fù)算子，按照優(yōu)先級從高到低對所有未調(diào)度且不在禁忌池內(nèi)的任務(wù)進(jìn)行排序，并按照次序依次嘗試插入任務(wù)，即優(yōu)先插入高優(yōu)先級任務(wù)。

② 能耗準(zhǔn)則修復(fù)算子，按照能耗從低到高對所有未調(diào)度且不在禁忌池內(nèi)的任務(wù)排序，然后按照次序依次嘗試插入任務(wù)，即優(yōu)先插入低能耗任務(wù)。

③ 隨機(jī)準(zhǔn)則修復(fù)算子，將所有未調(diào)度且不在禁忌池內(nèi)的任務(wù)排序，然后按照次序依次嘗試插入任務(wù)。

④ 擁堵度準(zhǔn)則修復(fù)算子，按照擁堵度由低到高將所有未調(diào)度且不在禁忌池內(nèi)的任務(wù)排序，然后按照次序依次嘗試插入任務(wù)。

本算法在每次迭代產(chǎn)生子代后，隨機(jī)選取一部分子代執(zhí)行約束檢查，然后進(jìn)行任務(wù)刪除和任務(wù)插入操作。將生成的新子代重新放回全部子代，通過環(huán)境選擇進(jìn)入后續(xù)種群。

3.6 算法實現(xiàn)

本研究算法步驟如下：

① 設(shè)置種群規(guī)模、最大迭代次數(shù)和插入概率等參數(shù)；

② 基于貪婪規(guī)則產(chǎn)生初始種群，并對種群中每個個體進(jìn)行混合整數(shù)編碼；

③ 對個體進(jìn)行沖突檢查和處理，然后復(fù)制得到種群1和種群2；

④ 判斷是否達(dá)到最大迭代次數(shù)，如果達(dá)到最大迭代次數(shù)則輸出種群2，否則執(zhí)行⑤；

⑤ 通過錦標(biāo)賽選擇產(chǎn)生交配池；

⑥ 通過交叉、變異得到子代種群，并隨機(jī)對子代種群執(zhí)行沖突檢查和任務(wù)插入；

⑦ 通過種群1和種群2的環(huán)境選擇，更新種群1和種群2，然后執(zhí)行④。

算法流程如圖1所示。

圖1 算法流程Fig.1 Algorithm flow

4 算例與分析

為了驗證基于雙種群進(jìn)化算法對衛(wèi)星一體化調(diào)度問題求解的收斂速度，采用Chang等人提出的基于現(xiàn)實的模擬實例生成方法產(chǎn)生模擬數(shù)據(jù)建立仿真算例，模擬數(shù)據(jù)產(chǎn)生過程中設(shè)定如下：

① 對地觀測衛(wèi)星：設(shè)定衛(wèi)星數(shù)量為10顆，分別為“高分”系列衛(wèi)星(GF0101，GF0201，GF0601)、“高景”系列衛(wèi)星(SV01，SV02，SV03，SV04)以及資源系列衛(wèi)星(ZY02C，ZY3，ZY0104)；

② 地面站：設(shè)定為4個，密云站(40°N/117°E)、喀什站(39°N/76°E)、三亞站(18°N/109°E)和挪威站(67°N/21°E)；

③ 地面目標(biāo)：設(shè)定為中國境內(nèi)隨機(jī)產(chǎn)生的100個地面目標(biāo)，所有地面目標(biāo)的中心點均勻分布于我國大陸范圍內(nèi)(3°～53°N以及74°～133°E)，地面目標(biāo)的優(yōu)先級服從均勻分布[1,10]，需求成像時長服從均勻分布[5,20]，單位s，數(shù)據(jù)有效期計算方式參照文獻(xiàn)[3]。

其他參數(shù)設(shè)定為：觀測任務(wù)啟動能耗eo=500 J，觀測成像耗能功率ro=50 W，數(shù)傳任務(wù)啟動能耗ed=500 J，數(shù)據(jù)回傳耗能功率rd=80 W。姿態(tài)機(jī)動功率和天線校對功率rc和rr均為100 W。姿態(tài)機(jī)動時間ρ設(shè)定為100 s，天線校對時間σ設(shè)定為100 s。

算法的主要參數(shù)設(shè)定為：種群規(guī)模100，最大迭代次數(shù)100，交叉概率為0.9，變異概率為0.1，4類破壞操作算子和4類修復(fù)操作算子的選擇概率均為0.25，插入概率(選擇執(zhí)行約束檢查和任務(wù)刪除與插入的概率)為0.5。

經(jīng)過30次運行加入貪婪策略的c-DPEA衛(wèi)星一體化調(diào)度算法，得到運行結(jié)果如表1所示。

表1 算法運行整體情況Tab.1 Description of algorithm operation

經(jīng)過多次實驗發(fā)現(xiàn)，不同的任務(wù)插入概率下操作算子對最優(yōu)解和收斂速度均產(chǎn)生不同的影響，這里采用多目標(biāo)優(yōu)化評價指標(biāo)超體積(Hypervolume，HV)對不同任務(wù)插入概率下的進(jìn)化過程進(jìn)行分析[30]。

此處以0.1為間隔選取[0,1]內(nèi)的11個值為插入概率，并設(shè)置最大迭代次數(shù)為100時得到各個個體的超體積，如圖2所示。在以上各個情況下分別得到最終代帕累托前沿，如圖3所示，橫縱坐標(biāo)分別為目標(biāo)函數(shù)值，目標(biāo)函數(shù)已經(jīng)做了無量綱化的處理。

圖2 不同插入概率下的HVFig.2 HV with different insert rates

圖3 不同插入概率下的收斂分布Fig.3 Convergence distribution with different insert rates

不難發(fā)現(xiàn)，隨著插入概率的增大，種群將能夠搜索到更優(yōu)的前沿，但與此同時算法的收斂速度也隨之下降，因此在實際問題中可以根據(jù)精度需求設(shè)置合理的插入概率，從而實現(xiàn)求解質(zhì)量和求解速度的兼顧。

在求解質(zhì)量方面，本文選取Chang等人[3]提出的ALNS+NSGA-II算法作為比較對象，分別選取100地面目標(biāo)、200地面目標(biāo)、300地面目標(biāo)和500地面目標(biāo)4種測試場景對算法進(jìn)行測驗，每個算法都以相同的初始解進(jìn)行迭代尋優(yōu)，得到最終的帕累托前沿，如圖4所示，各子圖橫縱坐標(biāo)為目標(biāo)1和目標(biāo)2的函數(shù)值。可以看到，基于貪婪策略的c-DPEA算法在各個場景下均可以獲得更為寬廣的帕累托前沿，即算法可以更為廣泛地搜索整個空間，求得更具多樣性的解。由于最大迭代次數(shù)的限制，c-DPEA算法所獲得的部分前沿劣于ALNS+NSGA-II，然而通過設(shè)置更大的最大迭代次數(shù)，即通過犧牲一定的求解速度，可以進(jìn)一步獲得更為優(yōu)秀的帕累托前沿，從而實現(xiàn)解的進(jìn)一步優(yōu)化，如圖5所示。

(a) 100 targets

(b) 200 targets

(c) 300 targets

(d) 500 targets圖4 c-DPEA和ALNS+NSGA-II的收斂分布Fig.4 Convergence distribution of c-DPEA and ALNS+NSGA-II

圖5 不同最大迭代次數(shù)下的c-DPEA帕累托前沿Fig.5 Pareto front of c-DPEA with different maximum iterations

5 結(jié)束語

針對一類同時關(guān)注對觀測成像任務(wù)和成像數(shù)據(jù)回傳任務(wù)的對地觀測衛(wèi)星一體化調(diào)度問題進(jìn)行了分析和建模。基于現(xiàn)實應(yīng)用場景構(gòu)建了對地觀測衛(wèi)星一體化調(diào)度模型，并設(shè)計了與之對應(yīng)的混合整數(shù)規(guī)劃模型。通過對模型中約束條件和問題特性進(jìn)行分析，設(shè)計了一種基于貪婪策略的初始解生成方法，在c-DPEA算法中引入操作算子設(shè)計了針對衛(wèi)星一體化調(diào)度問題的貪婪雙種群進(jìn)化算法。該方法通過雙種群的互補(bǔ)和協(xié)作，兼顧了衛(wèi)星一體化調(diào)度問題求解過程中的求解多樣性和收斂速度。

本文仍存在一些不足，算法中將操作算子的權(quán)重設(shè)為恒定值，可以通過引入自適應(yīng)的權(quán)重更新方法幫助子代個體在解空間內(nèi)更為快速、廣泛地探索，從而進(jìn)一步提高算法求解質(zhì)量和收斂速度，實現(xiàn)算法效率的進(jìn)一步提升。此外，本文只考慮了4類操作算子，未來還可以引入更多類型的操作算子來進(jìn)一步提高算法對衛(wèi)星一體化調(diào)度的求解能力。