基于遺傳禁忌算法的多星協(xié)同任務(wù)規(guī)劃方法

張澤華，張加友，張嘉凱，馬松靖，李宇哲

(哈爾濱工程大學(xué) 航天與建筑工程學(xué)院，黑龍江 哈爾濱 150001)

0 引言

對(duì)地觀測(cè)衛(wèi)星利用星載傳感器觀測(cè)地面目標(biāo)以獲取關(guān)鍵信息，在大地測(cè)繪和自然災(zāi)害檢測(cè)等多種應(yīng)用場(chǎng)景中具有關(guān)鍵作用。隨著對(duì)地觀測(cè)應(yīng)用的不斷深入，任務(wù)需求量急劇攀升，同時(shí)多頻次、多模式、多傳感器等復(fù)雜觀測(cè)需求也逐漸增多，很多情況下單一衛(wèi)星無(wú)法完成這些復(fù)雜的觀測(cè)需求。在此背景下，多星協(xié)同對(duì)地觀測(cè)成為當(dāng)前對(duì)地觀測(cè)的主要方式[1-2]。

多星協(xié)同任務(wù)規(guī)劃問(wèn)題是一個(gè)多維多選的組合優(yōu)化問(wèn)題，目前主要采用智能優(yōu)化算法解決此類問(wèn)題。文獻(xiàn)[3-5]基于蟻群算法對(duì)多星成像調(diào)度問(wèn)題開(kāi)展了研究，提出了一系列改進(jìn)蟻群算法。文獻(xiàn)[6]基于遺傳算法引入向量編碼，研究了新的交叉和變異算子、新的計(jì)算適應(yīng)度方法以及保持最優(yōu)個(gè)體的新方法。文獻(xiàn)[7]設(shè)計(jì)了一種基于圈次進(jìn)行交叉和變異的遺傳算法，并與蟻群算法進(jìn)行仿真比對(duì)，驗(yàn)證了其有效性。文獻(xiàn)[8]利用蒙特卡洛法和雙重停機(jī)條件對(duì)遺傳算法進(jìn)行了改進(jìn)，提出了一種改進(jìn)型自適應(yīng)遺傳算法，并通過(guò)實(shí)驗(yàn)表明了該算法在全局搜索能力和算法收斂速度方面的提高。文獻(xiàn)[9]研究了雙遺傳算法與模擬退火算法、雙蟻群算法與禁忌搜索算法2類求解方法，并通過(guò)實(shí)驗(yàn)數(shù)據(jù)證明了算法的有效性和適用性。文獻(xiàn)[10]基于遺傳算法設(shè)計(jì)了新的編碼方式，開(kāi)發(fā)了一種新型遺傳算法進(jìn)行求解對(duì)地觀測(cè)衛(wèi)星的調(diào)度問(wèn)題。文獻(xiàn)[11-12]提出了一種將高斯偽譜法與遺傳算法相結(jié)合的混合方法，通過(guò)遺傳算法生成規(guī)劃調(diào)度的可行解，再用高斯偽譜法優(yōu)化能量和時(shí)間。該混合方法在能量效率、計(jì)算效率和姿軌平滑方面具有優(yōu)越性。

本文在上述研究基礎(chǔ)上,提出了一種基于遺傳禁忌算法的多星協(xié)同任務(wù)規(guī)劃方法，該方法分為2個(gè)階段：第1階段為遺傳搜索階段，第2階段為禁忌搜索階段，兼具了遺傳算法較強(qiáng)的全局尋優(yōu)能力和禁忌搜索算法較強(qiáng)的局部尋優(yōu)能力。同時(shí)，通過(guò)仿真驗(yàn)證了算法的穩(wěn)定性和有效性。

1 多星協(xié)同任務(wù)規(guī)劃問(wèn)題模型

多星協(xié)同任務(wù)規(guī)劃問(wèn)題可概述為在指定場(chǎng)景時(shí)間內(nèi)，根據(jù)用戶提出的需求任務(wù)集合和衛(wèi)星資源信息，通過(guò)規(guī)劃調(diào)度給每個(gè)任務(wù)匹配滿足約束的衛(wèi)星觀測(cè)時(shí)段，并保證衛(wèi)星成像窗口不沖突。

由于一個(gè)任務(wù)可以被多顆衛(wèi)星可見(jiàn)，且一顆衛(wèi)星對(duì)一個(gè)任務(wù)的可見(jiàn)窗可能存在多個(gè)，即存在可見(jiàn)窗集合。假設(shè)衛(wèi)星有n顆，任務(wù)有m個(gè)，那么可見(jiàn)窗個(gè)數(shù)為m×n，多星多任務(wù)可見(jiàn)窗集合如表1所示，衛(wèi)星n對(duì)任務(wù)m的可見(jiàn)窗集合為Wmn。

多星協(xié)同任務(wù)規(guī)劃問(wèn)題就是基于表1中的多星多任務(wù)可見(jiàn)窗集合，通過(guò)任務(wù)規(guī)劃得到合理的衛(wèi)星觀測(cè)方案。

表1 多星多任務(wù)可見(jiàn)窗集合Tab.1 Visible window collection for multiple multi-satellite missions

1.1 基本假設(shè)

多星協(xié)同任務(wù)規(guī)劃問(wèn)題涉及到的對(duì)象之間的關(guān)系復(fù)雜，并不能顧及到所有的具體細(xì)節(jié)和實(shí)際約束問(wèn)題。在充分考慮到現(xiàn)實(shí)應(yīng)用情況的基礎(chǔ)上，本文對(duì)實(shí)際問(wèn)題做出了如下的基本假設(shè)和簡(jiǎn)化：

① 假設(shè)觀測(cè)目標(biāo)都是預(yù)處理后的固定點(diǎn)目標(biāo)；

② 假設(shè)衛(wèi)星存儲(chǔ)器的容量無(wú)限制；

③ 一般情況下，衛(wèi)星能量約束用側(cè)擺次數(shù)和總開(kāi)機(jī)時(shí)間等標(biāo)準(zhǔn)來(lái)描述，本文采用最大觀測(cè)任務(wù)數(shù)來(lái)描述；

④ 衛(wèi)星姿態(tài)調(diào)整及穩(wěn)定時(shí)間按照常數(shù)處理；

⑤ 假設(shè)每個(gè)任務(wù)只被觀測(cè)一次，且每個(gè)任務(wù)的觀測(cè)時(shí)長(zhǎng)相同。

1.2 數(shù)學(xué)模型

多星協(xié)同任務(wù)規(guī)劃問(wèn)題的數(shù)學(xué)模型如下：

f=α×maxf1+β×maxf2+γ×maxf3，

(1)

(2)

(3)

(4)

(5)

SEj≤SMaxEj，?j∈S，

(6)

STij,ETij∈Wij,?i∈T,?j∈S，

(7)

(8)

|CBij|≤SMaxCBj,?i∈T,?j∈S，

(9)

(10)

式(1)為優(yōu)化目標(biāo)函數(shù)，是由3個(gè)子目標(biāo)加權(quán)建立。其中，α,β,γ分別為3個(gè)子目標(biāo)的權(quán)重，且滿足0<α<1,0<β<1,0<γ<1,0<α+β+γ<1。3個(gè)權(quán)重值可以根據(jù)具體任務(wù)需求自定義，在本文中，取α=0.7，β=0.2，γ=0.1。式(2)為子目標(biāo)1，表示觀測(cè)任務(wù)集合的總收益值最大；式(3)為子目標(biāo)2，表示觀測(cè)任務(wù)集合的總完成度最大；式(4)為子目標(biāo)3，表示衛(wèi)星集合的側(cè)擺角之和最小，其中g(shù)(CBij)為側(cè)擺角歸一化函數(shù)，假設(shè)每顆衛(wèi)星的最大成像側(cè)擺角均為60°，則可設(shè)g(CBij)=2cos(CBij)-1。

式(5)表示每個(gè)任務(wù)最多被觀測(cè)一次；式(6)表示衛(wèi)星觀測(cè)任務(wù)數(shù)應(yīng)小于最大觀測(cè)任務(wù)數(shù)，即本文中描述的能量約束；式(7)表示衛(wèi)星觀測(cè)任務(wù)的觀測(cè)時(shí)段應(yīng)在可見(jiàn)窗內(nèi)；式(8)表示衛(wèi)星觀測(cè)任務(wù)集合中相鄰觀測(cè)任務(wù)之間應(yīng)滿足過(guò)渡時(shí)間約束；式(9)表示衛(wèi)星進(jìn)行任務(wù)觀測(cè)時(shí)應(yīng)滿足衛(wèi)星最大成像側(cè)擺角約束；式(10)主要針對(duì)光學(xué)衛(wèi)星，光學(xué)衛(wèi)星觀測(cè)任務(wù)時(shí)應(yīng)滿足太陽(yáng)高度角約束。

2 遺傳禁忌算法

2.1 基本思想

遺傳算法[13-14]是于1975年基于進(jìn)化生物學(xué)提出的，主要由初始化種群、遺傳算子和適應(yīng)度函數(shù)組成，遺傳算子中包括交叉、變異和選擇等。遺傳算法具備較強(qiáng)的全局擇優(yōu)能力，但容易過(guò)早收斂。禁忌搜索算法[15-16]于1986年基于局部鄰域搜索提出，主要由鄰域結(jié)構(gòu)、禁忌表和藐視準(zhǔn)則等組成。禁忌搜索算法具有較好的局部搜索能力，但初始解的質(zhì)量對(duì)其影響較大。

多星協(xié)同任務(wù)規(guī)劃問(wèn)題中任務(wù)成像觀測(cè)時(shí)間解集搜索空間很大，本文綜合遺傳算法和禁忌搜索算法的優(yōu)勢(shì)，分2個(gè)階段進(jìn)行問(wèn)題求解。第1階段，利用遺傳算法搜索效率較高的特點(diǎn)，采用遺傳算法進(jìn)行問(wèn)題的初步求解；第2階段，發(fā)揮禁忌搜索算法較強(qiáng)的局部搜索能力，并考慮初始解對(duì)禁忌搜索的影響，以遺傳算法的優(yōu)化結(jié)果為初始解，利用禁忌搜索算法對(duì)規(guī)劃問(wèn)題進(jìn)行再次求解，從而得到更優(yōu)的結(jié)果。

2.2 編碼與個(gè)體可行性處理

2.2.1 編碼

依據(jù)表1，將可見(jiàn)窗集合用一個(gè)矩陣M來(lái)表示，即：

(11)

基于式(11)中的矩陣，創(chuàng)建每個(gè)任務(wù)目標(biāo)所對(duì)應(yīng)的可見(jiàn)窗有序集合：M1,M2,…,MN,其中Mi=W1i∪W2i∪…∪Wni。給每顆衛(wèi)星進(jìn)行編號(hào)排序，每顆衛(wèi)星的可見(jiàn)窗按照可見(jiàn)開(kāi)始時(shí)間排序，在整個(gè)計(jì)算過(guò)程中順序固定不變。由此，可以令個(gè)體染色體的維度為二維，第一維表示觀測(cè)任務(wù)的衛(wèi)星，第二維表示該衛(wèi)星觀測(cè)任務(wù)的觀測(cè)開(kāi)始時(shí)間，并且分別用衛(wèi)星序號(hào)和觀測(cè)開(kāi)始時(shí)間位置序號(hào)進(jìn)行表示。由于衛(wèi)星觀測(cè)任務(wù)的可見(jiàn)窗可能由多個(gè)不連續(xù)的可見(jiàn)弧段組成，所以需要將可見(jiàn)窗連續(xù)化進(jìn)而得到衛(wèi)星觀測(cè)任務(wù)的觀測(cè)開(kāi)始時(shí)間位置序號(hào)，如圖1所示。

圖1 可見(jiàn)窗連續(xù)化示意Fig.1 Visible window continuity

假設(shè)衛(wèi)星對(duì)目標(biāo)的可見(jiàn)窗有3個(gè)，第1個(gè)開(kāi)始時(shí)間為0，結(jié)束時(shí)間為2，可見(jiàn)時(shí)長(zhǎng)為2；第2個(gè)開(kāi)始時(shí)間為5，結(jié)束時(shí)間為10，可見(jiàn)時(shí)長(zhǎng)為5；第3個(gè)開(kāi)始時(shí)間為15，結(jié)束時(shí)間為18，可見(jiàn)時(shí)長(zhǎng)為3。根據(jù)可見(jiàn)時(shí)長(zhǎng)的比例進(jìn)行連續(xù)化，若觀測(cè)開(kāi)始時(shí)間位置為4，則對(duì)應(yīng)第2個(gè)窗口的時(shí)間位置為7。

根據(jù)上面的描述，通過(guò)編碼產(chǎn)生的染色體可以表示為：

D={(x1,y1),(x2,y2),…,(xm,ym)}，

(12)

式中，xi= 0,1,2,…,n表示對(duì)任務(wù)Ti進(jìn)行觀測(cè)的衛(wèi)星序號(hào)；yi=0,1,2,…,l表示該衛(wèi)星觀測(cè)任務(wù)Ti的觀測(cè)開(kāi)始時(shí)間位置序號(hào)。根據(jù)前述假設(shè)可知，每個(gè)任務(wù)最多被觀測(cè)一次，所以若xi取值為0，就表示該任務(wù)不被觀測(cè)。

2.2.2 個(gè)體可行性處理

為保證個(gè)體滿足約束條件，需要對(duì)其進(jìn)行可行性處理，該處理是針對(duì)個(gè)體中的每一個(gè)任務(wù)進(jìn)行如下操作：

① 衛(wèi)星能量約束判斷。判斷該任務(wù)所選觀測(cè)衛(wèi)星是否滿足式(6)，若不滿足，則進(jìn)行衛(wèi)星序號(hào)突變，再重新判斷，直至挑選出滿足該約束的衛(wèi)星。若所有可見(jiàn)衛(wèi)星都不滿足該約束，則將該任務(wù)的觀測(cè)衛(wèi)星序號(hào)置為0。

② 衛(wèi)星相鄰任務(wù)時(shí)間窗口沖突判斷。判斷該任務(wù)的觀測(cè)時(shí)段是否滿足式(8)，若不滿足，則進(jìn)行觀測(cè)開(kāi)始時(shí)間位置序號(hào)突變，再重新判斷?？梢?jiàn)窗長(zhǎng)度遠(yuǎn)大于成像時(shí)長(zhǎng)，因此存在大量觀測(cè)開(kāi)始時(shí)間位置序號(hào)突變結(jié)果，本文設(shè)定觀測(cè)開(kāi)始時(shí)間位置序號(hào)突變次數(shù)上限，若其突變次數(shù)達(dá)到該上限仍未找到滿足約束的觀測(cè)時(shí)段，則進(jìn)行衛(wèi)星序號(hào)突變。若所有可見(jiàn)衛(wèi)星的可見(jiàn)窗突變?cè)谶_(dá)到突變次數(shù)上限時(shí)都未找到滿足約束的觀測(cè)時(shí)段，則將該任務(wù)的觀測(cè)衛(wèi)星序號(hào)置為0。

③ 衛(wèi)星側(cè)擺角約束判斷。判斷該任務(wù)所選觀測(cè)衛(wèi)星是否滿足式(9)，若不滿足，則依照第②步中的先突變觀測(cè)開(kāi)始時(shí)間位置序號(hào)后突變衛(wèi)星序號(hào)的方法進(jìn)行處理。

2.3 遺傳搜索階段

基于式(6)染色體結(jié)構(gòu)，隨機(jī)初始化種群，并對(duì)種群中個(gè)體進(jìn)行可行性處理。設(shè)定迭代次數(shù)，對(duì)種群進(jìn)行遺傳迭代，每代種群的個(gè)體都需進(jìn)行可行性處理，直至達(dá)到迭代次數(shù)，輸出最優(yōu)個(gè)體，即為遺傳搜索階段優(yōu)化結(jié)果。遺傳搜索階段流程如圖2所示，圖中符號(hào)Pm表示變異概率。

圖2 遺傳搜索階段流程Fig.2 Genetic search phases

2.3.1 交叉算子

將種群中的個(gè)體進(jìn)行兩兩隨機(jī)配對(duì)形成父代和母代染色體，父代和母代染色體通過(guò)部分基因片段的交叉產(chǎn)生子代個(gè)體。染色體交叉示意圖如圖3所示，隨機(jī)選取2個(gè)整數(shù)index1和index2，并滿足0

圖3 染色體交叉示意Fig.3 Chromosomal crossover

2.3.2 變異算子

根據(jù)本文的編碼方式，變異算子包括衛(wèi)星序號(hào)突變和觀測(cè)開(kāi)始時(shí)間位置序號(hào)突變2種。

觀測(cè)開(kāi)始時(shí)間位置序號(hào)突變示意圖如圖4所示，若個(gè)體染色體在index1和index2處發(fā)生觀測(cè)開(kāi)始時(shí)間位置序號(hào)突變，則從連續(xù)化可見(jiàn)窗結(jié)果中隨機(jī)突變新的觀測(cè)開(kāi)始時(shí)間位置序號(hào)。

圖4 觀測(cè)開(kāi)始時(shí)間位置序號(hào)突變示意Fig.4 Observation start time position sequence number mutation

衛(wèi)星序號(hào)突變示意圖如圖5所示，若個(gè)體染色體在index1和index2處發(fā)生衛(wèi)星序號(hào)突變，首先判斷突變處基因是否還存在其他可見(jiàn)衛(wèi)星，若存在，選擇新的可見(jiàn)衛(wèi)星，同時(shí)選擇新的觀測(cè)開(kāi)始時(shí)間位置序號(hào)，若不存在，將衛(wèi)星序號(hào)置為0，即該任務(wù)不被觀測(cè)。

圖5 衛(wèi)星序號(hào)突變示意Fig.5 Satellite number mutation

2.3.3 選擇算子

本文采用錦標(biāo)賽方法與雙敗淘汰制的結(jié)合進(jìn)行選擇。假設(shè)子代與父代個(gè)體形成的混合種群個(gè)體總數(shù)為N0，選擇后新一代種群個(gè)體數(shù)為N。將所有個(gè)體隨機(jī)分成10組，每組采用錦標(biāo)賽方法將前N/10名判定獲勝進(jìn)入勝者組，其余個(gè)體進(jìn)入敗者組。敗者組中采用錦標(biāo)賽方法將前N/2名判定復(fù)活進(jìn)入復(fù)活組，其余個(gè)體判定最終失敗進(jìn)行淘汰。勝者組中同樣采用錦標(biāo)賽方法將前N/2名判定最終勝利進(jìn)入勝利組，后N/2名進(jìn)入復(fù)活組。最后，復(fù)活組的所有個(gè)體爭(zhēng)搶最后的N/2個(gè)名額，爭(zhēng)奪方式依舊是錦標(biāo)賽方法，將前N/2名判定最終勝利進(jìn)入勝利組。至此，選擇算子操作結(jié)束，勝利組即為新一代種群，具體操作流程如圖6所示。

圖6 選擇算子操作流程Fig.6 Selection operator workflow

2.4 禁忌搜索階段

禁忌搜索算法的初始解可以隨機(jī)產(chǎn)生，但其初始解的優(yōu)劣對(duì)搜索的性能影響較大。因此，本文將遺傳搜索階段的優(yōu)化結(jié)果作為初始解進(jìn)行禁忌搜索。禁忌搜索階段流程如圖7所示。

圖7 禁忌搜索階段流程Fig.7 Tabu search phases

2.4.1 鄰域結(jié)構(gòu)

鄰域結(jié)構(gòu)是指由當(dāng)前解通過(guò)鄰域函數(shù)產(chǎn)生另一個(gè)解的方式，通過(guò)鄰域函數(shù)產(chǎn)生的解會(huì)有多個(gè)，這些解構(gòu)成當(dāng)前解的鄰域解集。鄰域結(jié)構(gòu)的設(shè)計(jì)方法有很多，并且針對(duì)不同的問(wèn)題會(huì)有不同的鄰域結(jié)構(gòu)設(shè)計(jì)方法。在本文中以遺傳算法中的染色體為初始解的結(jié)構(gòu)，由此設(shè)計(jì)出一種類似于遺傳算法中變異算子的鄰域結(jié)構(gòu)，如圖8所示。

圖8 鄰域結(jié)構(gòu)示意Fig.8 Neighborhood structure

首先隨機(jī)選擇變異任務(wù)編號(hào)，其次選擇變異該任務(wù)的可見(jiàn)衛(wèi)星編號(hào)，最后選擇變異該可見(jiàn)衛(wèi)星的觀測(cè)開(kāi)始時(shí)間位置序號(hào)。

試驗(yàn)地設(shè)在建三江勝利農(nóng)場(chǎng)科技園區(qū)；土壤情況為草甸白漿土；土壤養(yǎng)分含量：速氮：182m/kg，速磷：32.2mg/kg，速鉀：67mg/kg，有機(jī)質(zhì) 35.5mg/kg，PH 值 5.4.

2.4.2 禁忌表

本文中鄰域結(jié)構(gòu)設(shè)計(jì)時(shí)考慮了變異任務(wù)編號(hào)、變異任務(wù)的可見(jiàn)衛(wèi)星編號(hào)、變異可見(jiàn)衛(wèi)星的觀測(cè)開(kāi)始時(shí)間位置序號(hào)，因此本文基于禁忌長(zhǎng)度和上述3個(gè)變異序號(hào)進(jìn)行設(shè)計(jì)禁忌表，禁忌表結(jié)構(gòu)如下：

TabuL={(a1,b1,c1,d1),(a2,b2,c2,d2),…,(aL,bL,cL,dL)}，

(13)

式中，L表示禁忌表中存儲(chǔ)的禁忌解的個(gè)數(shù)；ai=1,2,3，…，T表示當(dāng)前禁忌解的禁忌長(zhǎng)度，T為初始禁忌長(zhǎng)度；bi=1,2,…,m表示染色體上選擇變異的任務(wù)位置編號(hào)，m為任務(wù)個(gè)數(shù)，即染色體上的基因個(gè)數(shù)；ci=1,2,…,nvs表示所選定任務(wù)選擇變異后的衛(wèi)星編號(hào)，nvs為任務(wù)的可見(jiàn)衛(wèi)星個(gè)數(shù)；di=1,2,…,l表示所選定衛(wèi)星選擇變異后的觀測(cè)開(kāi)始時(shí)間位置編號(hào)。

2.4.3 藐視準(zhǔn)則

當(dāng)通過(guò)鄰域結(jié)構(gòu)生成的候選解屬于禁忌表中的禁忌解時(shí)，需要進(jìn)行藐視準(zhǔn)則判斷。判斷準(zhǔn)則如下：若該禁忌解優(yōu)于當(dāng)前最佳解則視為該禁忌解藐視禁忌準(zhǔn)則，可以將其解禁，并將其更新為當(dāng)前解和當(dāng)前最佳解；否則該禁忌解無(wú)法藐視禁忌準(zhǔn)則，無(wú)法解禁。

3 仿真驗(yàn)證

3.1 仿真場(chǎng)景設(shè)置

本文仿真場(chǎng)景中仿真時(shí)長(zhǎng)為1 d。設(shè)置了4顆衛(wèi)星，4顆衛(wèi)星除了軌道傾角不同外，其他參數(shù)一致，具體參數(shù)值如表2所示。設(shè)置了7種觀測(cè)任務(wù)群規(guī)模，任務(wù)群規(guī)模分別為100，150，200，250，300，350，400，不同規(guī)模任務(wù)群均為在全球范圍內(nèi)隨機(jī)生成。

表2 衛(wèi)星參數(shù)Tab.2 Satellite parameters

3.2 算法穩(wěn)定性測(cè)試

針對(duì)規(guī)模為300的任務(wù)群，本文通過(guò)種群數(shù)分別為150，200，250的3種情況進(jìn)行算法求解來(lái)對(duì)算法的穩(wěn)定性進(jìn)行測(cè)試，得到3種情況下種群最優(yōu)個(gè)體適應(yīng)度曲線，測(cè)試結(jié)果如圖9所示。

由圖9可以看出，種群數(shù)分別為150，200，300三種情況下，最優(yōu)個(gè)體適應(yīng)度收斂的迭代次數(shù)不同，隨著種群數(shù)增加，收斂的迭代次數(shù)增加，但均在50次迭代之內(nèi)收斂。同時(shí)，在迭代過(guò)程中每次迭代的適應(yīng)度值不同，但3種情況下最終收斂的適應(yīng)度值相近。由此可以說(shuō)明,不同種群數(shù)下，算法求解的種群最優(yōu)個(gè)體適應(yīng)度相近，驗(yàn)證了算法的穩(wěn)定性。

圖9 不同種群數(shù)適應(yīng)度曲線Fig.9 The fitness curve of different population numbers

3.3 不同任務(wù)群規(guī)模仿真比對(duì)

本文對(duì)7種不同規(guī)模的任務(wù)群進(jìn)行仿真測(cè)試，測(cè)試中種群數(shù)量為200，迭代次數(shù)為400，得到每一種規(guī)模下種群最優(yōu)個(gè)體適應(yīng)度曲線、最優(yōu)個(gè)體總收益值曲線、最優(yōu)個(gè)體總完成度曲線以及最優(yōu)個(gè)體總側(cè)擺角曲線，仿真結(jié)果如圖10～圖13所示。

圖10 不同任務(wù)群規(guī)模適應(yīng)度曲線Fig.10 The fitness curve of different task group scales

圖11 不同任務(wù)群規(guī)?？偸找嬷登€Fig.11 The total revenue value curve of different task group scales

圖12 不同任務(wù)群規(guī)?？偼瓿啥惹€Fig.12 The total completion degree curve of different task group scales

圖13 不同任務(wù)群規(guī)?？倐?cè)擺角曲線Fig.13 The total roll angle curve of different task group scales

本文中數(shù)學(xué)模型的優(yōu)化目標(biāo)函數(shù)由總收益值、總完成度以及總側(cè)擺角值3個(gè)子目標(biāo)組成，為了對(duì)上述適應(yīng)度曲線的分析結(jié)果進(jìn)行進(jìn)一步驗(yàn)證，對(duì)不同任務(wù)群規(guī)模的總收益值、總完成度以及總側(cè)擺角值進(jìn)行分析。該仿真場(chǎng)景中衛(wèi)星最大側(cè)擺角為60°，因此式(4)中側(cè)擺角歸一化函數(shù)設(shè)為g(CBij)=2cos(CBij)-1。

圖11、圖12和圖13分別為不同任務(wù)群規(guī)?？偸找嬷登€、總完成度曲線和總側(cè)擺角曲線。

由圖11和圖12可以看出，前3種任務(wù)群規(guī)模的總收益值和總完成度相近，且大于后4種任務(wù)群規(guī)模。因此，圖10中前3種任務(wù)群規(guī)模的最終收斂適應(yīng)度值相近，且大于后4種任務(wù)群規(guī)模，與前面采用場(chǎng)景可完成任務(wù)數(shù)閾值分析的結(jié)果一致。由這3幅圖可以看出其曲線變化趨勢(shì)與圖10一致，7種任務(wù)群規(guī)模均在迭代150次后達(dá)到最優(yōu)，且隨著任務(wù)群規(guī)模增大，總收益值、總完成度和總側(cè)擺角遞減。

由此，將規(guī)模為300的任務(wù)群的優(yōu)化目標(biāo)函數(shù)值及其3個(gè)子目標(biāo)函數(shù)值進(jìn)行分析，如圖14所示。由圖14可以看出,3個(gè)子目標(biāo)函數(shù)值變化趨勢(shì)及適應(yīng)度值的變化趨勢(shì)一致，同時(shí)適應(yīng)度曲線較靠近總收益值曲線，該結(jié)果主要由于本文中子目標(biāo)總收益值的權(quán)重占比較大。

圖14 任務(wù)群規(guī)模300的優(yōu)化目標(biāo)值曲線Fig.14 The optimization objective function value curve of the task group size of 300

4 結(jié)束語(yǔ)

任務(wù)規(guī)劃是多星協(xié)同對(duì)地觀測(cè)研究中的關(guān)鍵點(diǎn)，規(guī)劃結(jié)果的優(yōu)劣直接關(guān)系著衛(wèi)星資源的利用效率和觀測(cè)任務(wù)的執(zhí)行質(zhì)量。針對(duì)多星協(xié)同對(duì)地觀測(cè)中的任務(wù)規(guī)劃問(wèn)題，提出了一種基于遺傳算法和禁忌搜索算法的多星協(xié)同任務(wù)規(guī)劃算法。該方法利用遺傳算法實(shí)現(xiàn)優(yōu)化問(wèn)題的初步求解，完成全局解空間的搜索；將遺傳算法求得的初步解作為輸入，利用禁忌搜索算法實(shí)現(xiàn)優(yōu)化問(wèn)題的進(jìn)一步求解，完成局部解空間的細(xì)致搜索。所提出的方法綜合了遺傳算法全局尋優(yōu)和禁忌搜索算法局部尋優(yōu)的優(yōu)勢(shì)，解決了多星協(xié)同對(duì)地觀測(cè)的任務(wù)規(guī)劃問(wèn)題。通過(guò)不同種群數(shù)下的仿真測(cè)試驗(yàn)證了算法的穩(wěn)定性，通過(guò)不同任務(wù)群規(guī)模的仿真驗(yàn)證了算法的有效性。