采用混合遺傳算法的敏捷衛(wèi)星自主觀測任務(wù)規(guī)劃

高新洲，郭延寧，馬廣富，張海博，李文博

(1.哈爾濱工業(yè)大學(xué) 航天學(xué)院，哈爾濱 150001; 2.北京控制工程研究所，北京 100190)

敏捷對(duì)地觀測衛(wèi)星(agile earth observation satellite, AEOS)擁有良好的姿態(tài)機(jī)動(dòng)能力，在民用和軍用領(lǐng)域都有著廣闊的應(yīng)用前景，比如環(huán)境保護(hù)、國土普查、抗震減災(zāi)以及制空權(quán)、制天權(quán)、制海權(quán)等。在AEOS的運(yùn)行過程中，對(duì)AEOS提前根據(jù)目標(biāo)點(diǎn)特性進(jìn)行任務(wù)規(guī)劃至關(guān)重要，可有效發(fā)揮AEOS性能，獲取更多的觀測收益[1]。而在任務(wù)規(guī)劃過程中，AEOS需要對(duì)多個(gè)目標(biāo)點(diǎn)進(jìn)行規(guī)劃，同時(shí)也要考慮到衛(wèi)星在觀測過程中所面臨的多種狀態(tài)、控制等復(fù)雜約束條件，因此，國內(nèi)外越來越多的學(xué)者開始進(jìn)行衛(wèi)星任務(wù)規(guī)劃方面的研究。

Michel等[2]提出了對(duì)點(diǎn)目標(biāo)以及區(qū)域目標(biāo)的分割和觀測方法，綜合分析了時(shí)間約束、姿態(tài)機(jī)動(dòng)約束、存儲(chǔ)容量和能量的約束，同時(shí)考慮到了天氣的不確定性，并提出了相應(yīng)的優(yōu)化目標(biāo)函數(shù)。他們分別對(duì)比了貪婪算法、動(dòng)態(tài)規(guī)劃算法、局部搜索算法這幾種算法的求解效率。趙琳等[3]對(duì)敏捷衛(wèi)星的單星單軌任務(wù)規(guī)劃問題進(jìn)行了研究，引入了任務(wù)—姿態(tài)協(xié)同規(guī)劃思想，并根據(jù)任務(wù)—姿態(tài)協(xié)同規(guī)劃數(shù)學(xué)模型設(shè)計(jì)了自適應(yīng)偽譜遺傳算法(APGA)，用以求解滿足調(diào)整時(shí)間最優(yōu)的任務(wù)規(guī)劃問題。耿遠(yuǎn)卓等[4]利用團(tuán)劃分算法對(duì)多個(gè)點(diǎn)目標(biāo)進(jìn)行了聚類，考慮了衛(wèi)星的時(shí)間窗口約束以及最大加速度約束，在傳統(tǒng)的蟻群算法的基礎(chǔ)上引入了啟發(fā)式尋優(yōu)策略和新的信息素更新策略，加快了算法的收斂性。丁祎男等[5]面向單星的任務(wù)規(guī)劃問題，在綜合分析遺傳算法與禁忌搜索算法優(yōu)缺點(diǎn)的基礎(chǔ)上，提出了遺傳禁忌混合算法，該算法能夠解決算法的早熟問題，同時(shí)能夠加快算法收斂速度。王海蛟等[6]針對(duì)敏捷衛(wèi)星的調(diào)度問題，采用了二進(jìn)制與實(shí)數(shù)雜合的編碼方式，將量子優(yōu)化機(jī)制引入了遺傳算法中，提出了改進(jìn)的量子遺傳算法，提高了搜索效率。Tangpattanakul等[7]針對(duì)單星的任務(wù)規(guī)劃問題，提出了一種基于知識(shí)的多目標(biāo)局部搜索方法(IBMOLS)，該方法實(shí)質(zhì)上是局部搜索算法與遺傳算法的綜合方法，能夠比遺傳算法更快地收斂。Chu等[8]研究了由低分辨率和高分辨率的衛(wèi)星組成的雙星任務(wù)規(guī)劃問題，對(duì)雙星協(xié)同任務(wù)規(guī)劃問題進(jìn)行建模，提出了分支限定的求解方法。Lee等[9]面向多星任務(wù)規(guī)劃問題，主要考慮了衛(wèi)星能源以及存儲(chǔ)容量的約束，利用遺傳算法進(jìn)行求解，就不同的應(yīng)用場景進(jìn)行了仿真。Zheng等[10]將多星的星上任務(wù)規(guī)劃問題建模為約束優(yōu)化問題，同時(shí)在現(xiàn)有的用于衛(wèi)星任務(wù)規(guī)劃的遺傳算法的基礎(chǔ)上，提出了求解速度更快的混合動(dòng)態(tài)變異遺傳算法(HDMGA)。黃生俊等[11]對(duì)知識(shí)定義、知識(shí)更新規(guī)則和任務(wù)沖突處理策略做了詳細(xì)描述，并綜合蟻群算法的反饋特性和模擬退火算法的局部搜索特性,設(shè)計(jì)了一種基于知識(shí)的改進(jìn)模擬退火算法。何磊等[12]考慮了光學(xué)成像敏捷衛(wèi)星中的云層遮擋問題，采用了預(yù)判和二分法進(jìn)行云層遮擋時(shí)間窗口的計(jì)算，并針對(duì)這一問題提出了相應(yīng)的蟻群算法進(jìn)行求解，提高了光學(xué)成像衛(wèi)星的成像效率。Tipaldi等[13]結(jié)合了規(guī)劃系統(tǒng)和動(dòng)態(tài)重規(guī)劃的能力深入分析了馬爾科夫決策過程(MDP)模型的自主規(guī)劃方法，驗(yàn)證了該方法在實(shí)際應(yīng)用中的性能。郝會(huì)成等[14]將免疫遺傳算法與蟻群算法等相結(jié)合，提出了基于混合遺傳求解算法，同樣提高了算法的求解速度。Xu等[15]考慮了衛(wèi)星的資源約束條件，在此基礎(chǔ)上提出了基于優(yōu)先權(quán)的結(jié)構(gòu)算法，用于最大化觀測收益。董軒鴻[16]研究了對(duì)觀測目標(biāo)的條帶劃分策略，設(shè)計(jì)了改進(jìn)的遺傳算法。

綜合來看，目前已有很多文獻(xiàn)應(yīng)用遺傳算法等智能優(yōu)化算法來解決衛(wèi)星的任務(wù)規(guī)劃問題[3,5,7,10]。雖然應(yīng)用遺傳算法可以求解出衛(wèi)星的最優(yōu)觀測序列，但是傳統(tǒng)的遺傳算法在交叉、變異等尋優(yōu)過程仍有許多值得改進(jìn)的地方，因此有必要對(duì)遺傳算法的變異過程做出改進(jìn)，進(jìn)而提升算法的求解效率。同時(shí)，如果規(guī)劃問題的適應(yīng)度函數(shù)過于簡單[17]，往往不能真實(shí)地反映衛(wèi)星的實(shí)際觀測情況，因此有必要對(duì)適應(yīng)度函數(shù)做出改進(jìn)。

基于上述考慮，本文提出了禁忌退火遺傳混合算法，并將其應(yīng)用于求解AEOS的任務(wù)規(guī)劃問題。首先提出了本文的適應(yīng)度函數(shù).此函數(shù)綜合考慮了衛(wèi)星在觀測過程中的多種約束條件，能夠較為真實(shí)地反映衛(wèi)星的實(shí)際觀測情況。其次介紹了禁忌退火遺傳混合算法。此算法對(duì)遺傳算法的變異過程做出了改進(jìn)，將禁忌搜索算法與模擬退火算法的尋優(yōu)過程的優(yōu)勢引入到了遺傳算法的變異過程，提升了遺傳算法的鄰域搜索能力，節(jié)省了算法的運(yùn)行時(shí)間，適用于AEOS的任務(wù)規(guī)劃問題。

1 任務(wù)規(guī)劃問題建模

1.1 任務(wù)規(guī)劃問題描述

AEOS在運(yùn)行過程中，主要通過橫滾軸和俯仰軸進(jìn)行姿態(tài)機(jī)動(dòng)。星上攜帶有攝像頭，可以對(duì)地面實(shí)施觀測任務(wù)。如圖1所示，衛(wèi)星沿滾動(dòng)軸的最大姿態(tài)機(jī)動(dòng)角度為θmax/2，沿俯仰軸的最大姿態(tài)機(jī)動(dòng)角度為ξmax/2。當(dāng)衛(wèi)星經(jīng)過目標(biāo)點(diǎn)上空時(shí)，需要提前對(duì)目標(biāo)點(diǎn)的觀測序列做出規(guī)劃，得到滿足觀測約束下的最優(yōu)/次優(yōu)觀測序列。

圖1 AEOS觀測示意

衛(wèi)星觀測目標(biāo)點(diǎn)時(shí)，會(huì)獲得相應(yīng)的收益，在對(duì)單目標(biāo)的持續(xù)觀測和目標(biāo)間的姿態(tài)機(jī)動(dòng)過程中，衛(wèi)星需要消耗一定能量。因此，構(gòu)建的目標(biāo)優(yōu)化函數(shù)必須綜合考慮觀測收益及觀測代價(jià)(即能量消耗)，在滿足各種約束條件情況下，通過優(yōu)化算法獲得衛(wèi)星對(duì)目標(biāo)點(diǎn)的觀測序列。

1.2 適應(yīng)度函數(shù)的建立

定義如下變量：M為目標(biāo)點(diǎn)集合，M={m1,m2,…,mn}，其中mi為第i個(gè)目標(biāo)點(diǎn)，n為目標(biāo)點(diǎn)總數(shù)；ttwsi為衛(wèi)星對(duì)mi可見的時(shí)間窗口的開始時(shí)間；ttwei為衛(wèi)星對(duì)mi可見的時(shí)間窗口的結(jié)束時(shí)間；tsi為衛(wèi)星對(duì)mi的實(shí)際開始觀測時(shí)間；tei為衛(wèi)星對(duì)mi的實(shí)際結(jié)束觀測時(shí)間；di為衛(wèi)星對(duì)mi的實(shí)際觀測的持續(xù)時(shí)間，即di=tei-tsi；trij為衛(wèi)星從觀測mi到觀測mj轉(zhuǎn)過的姿態(tài)機(jī)動(dòng)角度；pi為mi的任務(wù)優(yōu)先級(jí)，pi取值越大，意味著mi的優(yōu)先級(jí)越高；wi為衛(wèi)星觀測mi獲得的收益，即wi=di·pi；posi=(lgti,lati)為mi的經(jīng)、緯度坐標(biāo)，其中l(wèi)gti為mi的經(jīng)度；lati為mi的緯度，決策變量si和Fij的定義如下：

(1)

(2)

基于上述定義的變量，考慮如下適應(yīng)度函數(shù):

(3)

上式表示的函數(shù)由觀測收益與衛(wèi)星姿態(tài)機(jī)動(dòng)的能量消耗兩部分組成. 式中：si·wi為衛(wèi)星觀測某一目標(biāo)點(diǎn)所帶來的收益，收益與目標(biāo)點(diǎn)優(yōu)先級(jí)成正比；f1+si·di為衛(wèi)星觀測過程中消耗的能量，其中si·di為持續(xù)觀測某一目標(biāo)點(diǎn)的能耗，f1為衛(wèi)星姿態(tài)機(jī)動(dòng)的能耗，與衛(wèi)星姿態(tài)機(jī)動(dòng)過程中勻加速與勻減速的時(shí)間Δt有關(guān)；η為衛(wèi)星的能耗系數(shù)，是一個(gè)常數(shù)。Δt的計(jì)算方法如下。

本文假設(shè)衛(wèi)星在目標(biāo)點(diǎn)之間姿態(tài)機(jī)動(dòng)時(shí)，每個(gè)軸均以最大力矩Tmax進(jìn)行機(jī)動(dòng)，根據(jù)衛(wèi)星需要轉(zhuǎn)過的角度大小分為兩種情況考慮，如圖2的兩種情況所示。圖2(a)對(duì)應(yīng)大角度機(jī)動(dòng)情況，圖2(b)對(duì)應(yīng)小角度的情況。

綜上所述，考慮f1為

(4)

式中，Δt為衛(wèi)星進(jìn)行勻加速與勻減速過程的總時(shí)間。綜合式(3)、(4)可得

(5)

圖2 求解衛(wèi)星姿態(tài)機(jī)動(dòng)角度示意

從式(5)可以看出，f取得最大值是本文的優(yōu)化目標(biāo)，即在考慮到衛(wèi)星的能量消耗的情況下盡可能多地獲得觀測收益。

1.3 AEOS任務(wù)規(guī)劃的約束條件

下面給出AEOS任務(wù)規(guī)劃的約束條件。

如果目標(biāo)點(diǎn)mi被觀測，那么觀測的持續(xù)時(shí)間區(qū)間必須被包含在衛(wèi)星對(duì)mi可見的時(shí)間窗口內(nèi)，即

ttwsi≤tsi，ttwei≥tei,若si=1

(6)

衛(wèi)星結(jié)束觀測mi以后，必須在mj的時(shí)間窗口結(jié)束之前完成姿態(tài)機(jī)動(dòng)才可以觀測mj，即

tsi+trij+di≤ttwej,若Fij=1

(7)

考慮如下衛(wèi)星軌道動(dòng)力學(xué)約束：

(8)

以及如下衛(wèi)星姿態(tài)角約束、姿態(tài)角速度約束、姿態(tài)角加速度約束:

|θ|≤θmax，|ξ|≤ξmax

(9)

ωθ≤ωθmax，ωξ≤ωξmax

(10)

αθ≤αθmax，αξ≤αξmax

(11)

此外，還需要考慮如下衛(wèi)星姿態(tài)轉(zhuǎn)移時(shí)間約束:

trij=f(rs,posi,posj,Tmax)

(12)

式中，時(shí)間trij與兩個(gè)目標(biāo)點(diǎn)的經(jīng)緯度以及AEOS的最大機(jī)動(dòng)力矩Tmax相關(guān)，計(jì)算方法如圖2所示。其中AEOS需要機(jī)動(dòng)的角度θ的求解采用了文獻(xiàn)[17]的方法，如圖3所示。

圖3 AEOS姿態(tài)機(jī)動(dòng)角度的求解

在圖3中，Rei和Rej分別為mi和mj在地心慣性坐標(biāo)系(ECI)中的坐標(biāo)，具體公式為

(13)

式中:ω為地球自轉(zhuǎn)角速度，Re為地球半徑。

圖3中Res為衛(wèi)星在ECI中的坐標(biāo)，可通過下式求得：

(14)

式中:Rs為衛(wèi)星的軌道半徑，Ω為升交點(diǎn)赤經(jīng)，ψ為近地點(diǎn)幅角，α為衛(wèi)星轉(zhuǎn)過的角度，可由下式確定：

α=E+ωst

(15)

式中:E為衛(wèi)星開始觀測時(shí)刻的真近點(diǎn)角，ωs為衛(wèi)星的角速度，t為當(dāng)前的時(shí)刻。

由圖3中可得下式

(16)

因此，衛(wèi)星從觀測mi姿態(tài)機(jī)動(dòng)到mj所需轉(zhuǎn)動(dòng)的角度θ可通過下式求得：

θ=arccos

(17)

綜合式(17)與圖2，即可最終求得衛(wèi)星的姿態(tài)機(jī)動(dòng)時(shí)間trij。

2 禁忌退火遺傳混合算法

對(duì)于大規(guī)模的衛(wèi)星任務(wù)規(guī)劃問題，傳統(tǒng)的遺傳算法很難在較短的運(yùn)算時(shí)間內(nèi)給出最優(yōu)的觀測序列。因此，有必要對(duì)遺傳算法的尋優(yōu)過程做出改進(jìn)。相對(duì)于傳統(tǒng)的遺傳算法變異方法，本文提出的禁忌退火變異方法能夠有效提高算法的求解搜索效率，節(jié)省算法的運(yùn)行時(shí)間。

2.1 初始種群生成

本文采用整數(shù)編碼來解決衛(wèi)星的任務(wù)規(guī)劃問題。整數(shù)編碼與二進(jìn)制編碼等其他編碼方式相比，能夠更直觀地表示衛(wèi)星的觀測序列，也便于算法搜尋鄰域解。

采用整數(shù)編碼方式的每個(gè)染色體(也稱作解、個(gè)體)分別代表一種可行的觀測序列。染色體上的每個(gè)基因所對(duì)應(yīng)的數(shù)字即為目標(biāo)點(diǎn)，如圖4所示。

圖4 整數(shù)編碼的染色體

圖4代表一條長度為6的染色體，表示衛(wèi)星需要觀測6個(gè)目標(biāo)點(diǎn)，且最先5號(hào)目標(biāo)點(diǎn)，最后觀測6號(hào)目標(biāo)點(diǎn)。

設(shè)地面上目標(biāo)點(diǎn)總數(shù)為n，AEOS需要從n個(gè)目標(biāo)點(diǎn)中選取N個(gè)目標(biāo)點(diǎn)進(jìn)行觀測，種群規(guī)模為M。種群初始化的方法為，隨機(jī)生成M個(gè)觀測序列，其中每個(gè)觀測序列都是N個(gè)不大于n且互不重復(fù)的正整數(shù)，即同一個(gè)目標(biāo)點(diǎn)不會(huì)重復(fù)被觀測。在此后算法的每一次迭代過程中，都會(huì)首先計(jì)算種群中每一條染色體所對(duì)應(yīng)的適應(yīng)度函數(shù)值。

2.2 適應(yīng)度函數(shù)計(jì)算

適應(yīng)度函數(shù)值的大小是衡量種群中每個(gè)個(gè)體優(yōu)劣程度的重要指標(biāo)。對(duì)于每一個(gè)給定的觀測序列，為了計(jì)算此序列所對(duì)應(yīng)的適應(yīng)值，需要首先確定衛(wèi)星能否依次觀測此序列所有的目標(biāo)點(diǎn)。過程如下：

Step1比較當(dāng)前的時(shí)間t與mi的時(shí)間窗口結(jié)束時(shí)間ttwei。如果t>ttwei，則mi無法被觀測，令si=0，i=i+1，繼續(xù)執(zhí)行step1。如果t

Step2比較t與ttwsi。如果t>ttwsi，則執(zhí)行step3。如果t

Step3計(jì)算trij。如果t+trij>ttwei，則mi無法被觀測，令si=0，i=i+1，執(zhí)行step1。如果t+trij

Step4計(jì)算trij。如果t+trijttwei，則mi無法被觀測，令si=0，i=i+1，執(zhí)行step1。

Step5如果t+trijttwsi，令t=t+trij+di，i=i+1，執(zhí)行step1。

從i=1起，重復(fù)執(zhí)行上述過程，直至i=N，即可得到每個(gè)觀測序列所對(duì)應(yīng)的si以及Fij。將si、Fij以及關(guān)于每個(gè)目標(biāo)點(diǎn)的wi等變量帶入式(5)即可求得每個(gè)觀測序列所對(duì)應(yīng)的適應(yīng)值的大小，每個(gè)個(gè)體的優(yōu)劣程度也就可以依次確定。

2.3 選擇、交叉操作

本文采用精英保留策略以及輪盤賭法對(duì)種群進(jìn)行選擇、交叉操作。精英保留策略將第g代種群中的若干優(yōu)秀個(gè)體當(dāng)做父本直接傳遞到第g+1代種群。隨后根據(jù)輪盤賭法從父本中選擇父本進(jìn)行交叉運(yùn)算，生成若干子代，使得第g+1代的種群規(guī)模為M。

輪盤賭法的計(jì)算過程如下所示：

(18)

(19)

式中:Fi為第i個(gè)父本對(duì)應(yīng)的適應(yīng)值，Qi為第i個(gè)父本被選擇的概率，Pi為從第1個(gè)父本直至第i父本的累加概率。其中，各父本按照適應(yīng)度從大到小的順序排列。

第i個(gè)父本被選中參與交叉過程的方法如下：產(chǎn)生一個(gè)介于0和1之間的隨機(jī)數(shù)r，如果該隨機(jī)數(shù)滿足Pi-1

圖5 交叉操作

經(jīng)過交叉操作得到的子代往往都含有相同的基因。比如圖5中，子代1的6和3都是重復(fù)出現(xiàn)的元素。因此，需要進(jìn)行去重復(fù)操作，使每個(gè)子代的各個(gè)基因之間都兩兩互不重復(fù)。去重復(fù)操作是將每個(gè)子代中重復(fù)的基因隨機(jī)用沒有出現(xiàn)在該子代染色體中的基因替代，如圖6所示。

圖6 去重復(fù)操作

2.4 禁忌退火變異

本文給出了禁忌退火變異(tabu search-simulated annealing mutation，TSSAM)。首先給出了禁忌搜索算法和模擬退火算法的相關(guān)定義；其次介紹了TSSAM的具體過程；最后分析了TSSAM對(duì)于傳統(tǒng)的變異方法的改進(jìn)之處。

2.4.1 禁忌搜索算法

禁忌搜索算法(tabu search algorithm,TS)尋優(yōu)策略為，從初始解的鄰域解集中選取最優(yōu)解或者是未被禁忌的最優(yōu)解作為新的初始搜索解，直至算法收斂。禁忌搜索算法通過不斷更新禁忌表來避免在一個(gè)鄰域內(nèi)重復(fù)搜索，進(jìn)而提高算法的全局搜索能力，加快算法收斂速度。禁忌搜索算法的一些定義如下。

1)初始解。參與禁忌搜索的最開始的解，在本文中即為參與變異的個(gè)體x0。

2)鄰域解集。初始解x0的鄰域解構(gòu)成的集合。對(duì)于采用整數(shù)編碼方式的染色體來講，鄰域解采用2-opt形式，即通過互換兩個(gè)基因位上的元素來產(chǎn)生鄰域解，如圖7所示。鄰域解集的規(guī)模與染色體的長度有關(guān)。

圖7 產(chǎn)生鄰域解

3)候選解。x0產(chǎn)生的鄰域解集中的最優(yōu)解或者是未被禁忌的最優(yōu)解，用于同x0比較，決定是否要用候選解替換x0。

4)禁忌表。用于記錄被禁忌的前若干次的操作。對(duì)于采用整數(shù)編碼的染色體來講，禁忌表是一個(gè)N×N的矩陣。其中N為染色體長度。禁忌表中第i行第j列的數(shù)字ai,j表示交換i,j兩個(gè)位置上元素的操作當(dāng)前被禁忌的次數(shù)。如果禁忌表中該位置上元素為0，則表示此操作當(dāng)前未被禁忌。在算法最開始的時(shí)候，禁忌表初始化為零矩陣。

5)禁忌長度。被禁忌的操作不允許被選取的最大次數(shù)。禁忌長度與染色體長度有關(guān)。禁忌長度記為Ltabu。

2.4.2 模擬退火算法

模擬退火算法(simulated annealing algorithm,SA)的尋優(yōu)過程為，假定一個(gè)著火物體，其溫度隨迭代過程指數(shù)下降。每次迭代時(shí)，在當(dāng)前解的鄰域內(nèi)隨機(jī)搜尋可行解，利用Metropolis法則判斷是否接受鄰域內(nèi)可行解，循環(huán)此過程直至算法收斂。

1)退火溫度。SA中物體的溫度，記為T。物體的退火溫度T從初始溫度T0開始，隨迭代過程指數(shù)下降。

2)退溫率。物體的退火溫度的衰減速度K。物體溫度的退溫策略為T(n+1)=K·T(n)，其中n為迭代次數(shù)。K滿足0

3)Metropolis法則。如果在當(dāng)前解s0的鄰域內(nèi)搜尋到的可行解s1優(yōu)于當(dāng)前解，則以概率1接受s1作為新的當(dāng)前解。如果s1劣于s0，則以一定概率p接受s1作為新的當(dāng)前解。此概率p與當(dāng)前的溫度T以及s1，s0適應(yīng)值的差有關(guān)，計(jì)算公式如下：

p=exp(ΔE/T)

(20)

式中:ΔE為s1與s0適應(yīng)度函數(shù)的差值，且ΔE<0；T為當(dāng)前系統(tǒng)的溫度。

2.4.3 禁忌退火變異算法(TSSAM)

決定種群中某一個(gè)體是否參與變異的方法如下：生成隨機(jī)數(shù)r，如果變異率大于r，那么對(duì)當(dāng)前個(gè)體執(zhí)行TSSAM操作。TSSAM步驟如下：

Step1對(duì)于每一個(gè)參與變異的個(gè)體x0，首先產(chǎn)生此個(gè)體的鄰域解集。x0也稱作禁忌搜索的初始解。隨后將x0產(chǎn)生的鄰域解按照從優(yōu)到劣的順序進(jìn)行排列，記最優(yōu)鄰域解為x1。先將x1作為候選解。

Step2將候選解x1與初始解x0進(jìn)行比較。如果x1的適應(yīng)度函數(shù)值大于x0，執(zhí)行step3。如果x1的適應(yīng)值小于x0，執(zhí)行step4。

Step3將x1作為x0變異后的個(gè)體傳回到種群中，同時(shí)更新禁忌表。記由x0得到x1的方法為互換第i1,j1個(gè)基因位上的元素。更新禁忌表的方法為：對(duì)禁忌表中所有非零元素執(zhí)行如下操作：

(21)

隨后考慮下一個(gè)參加變異的個(gè)體，執(zhí)行Step1。

Step4搜索x0的鄰域解集中未被禁忌的最優(yōu)解，將此最優(yōu)解記為新的候選解x2。將x0與x2的目標(biāo)優(yōu)化函數(shù)值的差記為ΔE，ΔE<0。產(chǎn)生一個(gè)隨機(jī)數(shù)r，如果滿足exp(ΔE/T)>r，則接受x2作為變異后的個(gè)體傳回到種群中，同時(shí)更新禁忌表，隨后考慮下一個(gè)參加變異的個(gè)體，執(zhí)行step1。記由x0得到x2的方法為互換i2,j2基因位上的元素。更新禁忌表的方法為對(duì)禁忌表中所有非零元素執(zhí)行如下操作：

(22)

生成隨機(jī)數(shù)r，如果滿足exp(ΔE/T)

重復(fù)執(zhí)行上述過程，直至種群完成變異。

當(dāng)種群中的所有參與變異的個(gè)體變異完成以后，更新退火溫度，即令T(n+1)=K·T(n)，開始種群下一代的迭代進(jìn)化過程。

傳統(tǒng)遺傳算法的變異過程本質(zhì)是從參與變異的個(gè)體的鄰域解集內(nèi)隨機(jī)選擇一個(gè)解作為變異后的個(gè)體，而這一變異過程往往具有隨機(jī)性。與傳統(tǒng)的變異過程相比，TSSAM引入禁忌搜索算法中的鄰域解集，在鄰域解集中尋找可行解。如果變異個(gè)體的鄰域解集中的最優(yōu)解優(yōu)于此個(gè)體，那么接受最優(yōu)解為變異后的個(gè)體；反之，則通過Metropolis法則以一定概率接受未被禁忌的最優(yōu)解作為變異后的個(gè)體。

綜上分析，TSSAM兼具禁忌搜索算法與模擬退火算法的優(yōu)點(diǎn)，既能夠擴(kuò)大解的搜索范圍，又能夠利用Metropolis法則提升算法的尋優(yōu)能力，極大改善了遺傳算法的變異過程，加快了算法的收斂過程。

本文設(shè)計(jì)的TSSAM算法的流程圖如圖8所示。

圖8 TSSAGA流程圖

3 典型AEOS任務(wù)規(guī)劃問題驗(yàn)證

本文通過仿真驗(yàn)證了禁忌退火遺傳混合算法提出的禁忌退火遺傳混合算法在AEOS任務(wù)規(guī)劃問題中的有效性。

3.1 仿真參數(shù)設(shè)置

考慮AEOS如下參數(shù),見表1。

表1 衛(wèi)星參數(shù)

通過STK建立上述衛(wèi)星的場景，在場景中隨機(jī)生成若干個(gè)衛(wèi)星可見的目標(biāo)點(diǎn)，并為這些目標(biāo)點(diǎn)隨機(jī)指定1～10的任務(wù)優(yōu)先級(jí)。這些目標(biāo)點(diǎn)的范圍為20°N～50°N，110°E～130°E。仿真時(shí)間從2020年3月24日04∶00∶00開始，到2020年3月25日04∶00∶00結(jié)束。通過STK可以解算出衛(wèi)星對(duì)目標(biāo)點(diǎn)可見的時(shí)間窗口。

為了充分驗(yàn)證算法的有效性，將禁忌退火遺傳混合算法(TSSAGA)分別與禁忌遺傳算法(TSGA)、退火遺傳算法(SAGA)以及普通的遺傳算法(GA)進(jìn)行對(duì)比仿真實(shí)驗(yàn)。

綜上所述，目前可確定的各算法參數(shù)見表2。

表2 確定的參數(shù)

3.2 仿真結(jié)果分析

本文設(shè)置了2組不同規(guī)模的對(duì)比仿真實(shí)驗(yàn)來驗(yàn)證TSSAGA在AEOS任務(wù)規(guī)劃中的性能。第1組實(shí)驗(yàn)為從50個(gè)目標(biāo)點(diǎn)中選20個(gè)目標(biāo)點(diǎn)進(jìn)行觀測，即染色體長度N=20。上文中未給出的各個(gè)算法其他參數(shù)見表3。

表3 未確定的參數(shù)(目標(biāo)點(diǎn)個(gè)數(shù)∶50)

第2組實(shí)驗(yàn)為從100個(gè)目標(biāo)點(diǎn)中選50個(gè)進(jìn)行觀測，染色體長度N=50。各算法其他參數(shù)見表4。

表4 未確定的參數(shù)(目標(biāo)點(diǎn)個(gè)數(shù)∶100)

為了盡可能詳盡全面地比較算法的求解能力，每組對(duì)比實(shí)驗(yàn)中，每種算法進(jìn)行50次蒙特卡洛仿真實(shí)驗(yàn)，隨后比較算法的平均適應(yīng)度函數(shù)值以及算法達(dá)到收斂的總耗時(shí)。算法收斂的判斷標(biāo)準(zhǔn)為，連續(xù)15次迭代的最優(yōu)解相同。對(duì)50個(gè)目標(biāo)點(diǎn)進(jìn)行規(guī)劃的對(duì)比試驗(yàn)結(jié)果見表5。

表5 任務(wù)規(guī)劃結(jié)果對(duì)比(目標(biāo)點(diǎn)個(gè)數(shù)∶50)

為了進(jìn)一步驗(yàn)證算法的有效性，將每種算法分別運(yùn)算10組，每組進(jìn)行50次蒙特卡洛仿真實(shí)驗(yàn)并取平均值，對(duì)比試驗(yàn)結(jié)果如圖9所示。最優(yōu)的觀測序列見表6。對(duì)100個(gè)點(diǎn)進(jìn)行規(guī)劃的對(duì)比實(shí)驗(yàn)結(jié)果見表7。同樣地，將每種算法分別運(yùn)算10組，每組進(jìn)行50次蒙特卡洛仿真實(shí)驗(yàn)并取平均值，對(duì)比試驗(yàn)結(jié)果如圖10所示。最優(yōu)的觀測序列見表8。

圖9 算法對(duì)比結(jié)果(目標(biāo)點(diǎn)個(gè)數(shù)∶50)

表6 任務(wù)規(guī)劃結(jié)果(目標(biāo)點(diǎn)個(gè)數(shù)∶50)

表7 任務(wù)規(guī)劃結(jié)果對(duì)比(目標(biāo)點(diǎn)個(gè)數(shù)∶100)

圖10 算法對(duì)比結(jié)果(目標(biāo)點(diǎn)個(gè)數(shù)∶100)

表8 任務(wù)規(guī)劃結(jié)果(目標(biāo)點(diǎn)個(gè)數(shù)∶100)

綜合表5與表7可知，求解相同規(guī)模的任務(wù)規(guī)劃問題，TSSAGA收斂最快，且收益高于其他算法。相比于GA，TSAG和SAGA節(jié)省了20%～30%的運(yùn)算時(shí)間，TSSAGA節(jié)省了約40%的運(yùn)算時(shí)間。相比于傳統(tǒng)遺傳算法的變異過程，TSSAGA在變異過程中引入了禁忌搜索的方法以及Metropolis法則，極大地提升了算法的搜索效率以及尋優(yōu)能力，節(jié)省了算法的收斂時(shí)間，有較高的工程應(yīng)用價(jià)值。

4 結(jié) 論

1)面向敏捷對(duì)地觀測衛(wèi)星觀測大規(guī)模地面點(diǎn)目標(biāo)這一實(shí)際工程問題，考慮了衛(wèi)星面臨的多種約束條件，建立了對(duì)應(yīng)的適應(yīng)度函數(shù)。

2)改進(jìn)了傳統(tǒng)遺傳算法的變異過程，提出了禁忌退火變異方法，此方法兼具了禁忌搜索算法與模擬退火算法的有點(diǎn)，提高了整個(gè)算法的尋優(yōu)能力，加快了算法的收斂速度。

3)仿真結(jié)果表明，禁忌退火遺傳混合算法與傳統(tǒng)的遺傳算法相比，節(jié)省了約40%的算法優(yōu)化時(shí)間，大幅提高了智能優(yōu)化算法求解敏捷對(duì)地觀測衛(wèi)星任務(wù)規(guī)劃問題的求解效率。