趙儉輝,陸一鳴,蔡 波

(武漢大學計算機學院,湖北 武漢 430072)

1 引言

衛(wèi)星技術發(fā)展帶來了近地空間信息利用率的上升,其好處是多方面的:小到日常使用的衛(wèi)星導航、GPS定位系統(tǒng),大到天氣預報、農(nóng)時播報、地形地貌測繪等等。衛(wèi)星技術的高速發(fā)展在給予人們生活中巨大便利時,同樣提高了國家在科研、工業(yè)及農(nóng)業(yè)上的發(fā)展效率。衛(wèi)星硬件性能上的提高帶來了衛(wèi)星調(diào)度能力的不斷提升,同時也需要更加復雜而高效的調(diào)度方式來充分利用衛(wèi)星的觀測效能。在多衛(wèi)星協(xié)同觀測的情況下,如何規(guī)劃各衛(wèi)星需要觀測的目標,從而使觀測收益最大化同時減少資源消耗,就成了一個亟待解決的問題[1,2]。

衛(wèi)星觀測任務的規(guī)劃通常將任務視作多個時間窗模型[3],之后采用智能優(yōu)化算法或者深度學習方式對問題進行求解。在智能優(yōu)化算法方面,所采用方法有改進蟻群算法[4]、禁忌搜索方法[5]、貪心算法[6]、動態(tài)規(guī)劃[7,8]乃至多種算法的組合算法[9]等,通過對衛(wèi)星與目標在不同算法框架下建模,對衛(wèi)星的任務規(guī)劃乃至重規(guī)劃問題[10]進行求解。在深度學習方面,求解問題首先依賴于大量的衛(wèi)星規(guī)劃歷史數(shù)據(jù),并使用多種不同的神經(jīng)網(wǎng)絡模型(例如基于增廣拓撲協(xié)同神經(jīng)進化的預測模型[11]、改進指針模型[12])來預測衛(wèi)星規(guī)劃方案。

由于深度學習方法需要的大量歷史數(shù)據(jù),獲取數(shù)據(jù)較為困難且算法成效受歷史數(shù)據(jù)的優(yōu)劣影響很大。基于上述原因,本文在求解多星多點目標觀測任務規(guī)劃問題時選用了基于智能優(yōu)化算法的方法。通過對衛(wèi)星實際運行時的軌道參數(shù)、載荷參數(shù)以及目標優(yōu)先級等屬性建模,應用改進遺傳算法初步求解,并使用螢火蟲算法進一步增強算法框架的局部尋優(yōu)能力,最終得到更好的優(yōu)化結果。

2 衛(wèi)星觀測問題建模

2.1 衛(wèi)星約束模型

本文衛(wèi)星約束模型主要包含:衛(wèi)星分辨率約束、太陽高度角約束以及衛(wèi)星側擺動作約束。

2.1.1 分辨率約束

以光學相機CCD和雷達傳感器SAR作為衛(wèi)星執(zhí)行觀測任務的兩種主要載荷,其分辨率的計算分別如下:

1)CCD相機分辨率

(1)

式中S為CCD相機單個相元尺寸,H為衛(wèi)星離地高度,f為相機焦距,θ為衛(wèi)星此時的側擺角度。

2)SAR傳感器分辨率

(2)

式中c為光速,W為雷達帶寬,R為地球半徑,H為衛(wèi)星離地高度,θ為衛(wèi)星側擺角度。

2.1.2 太陽高度角約束

太陽高度角決定了衛(wèi)星觀測時的光照條件,對光學衛(wèi)星任務執(zhí)行十分重要,這一約束體現(xiàn)了傳感器在工作時對光照的依賴程度。

上圖中以北極圈內(nèi)一點為例,太陽高度角即為該點地平線與太陽光線夾角,大小為γ。在某地正午以外的其它時間中,當?shù)氐奶柛叨冉且匀缦鹿降玫?

圖1 太陽高度角約束

sinγ=sinαsinβ+cosαcosβcost

(3)

其中α為計算點的地理緯度,β為此時的太陽赤緯,t為計算位置的地方時(也叫時角)。太陽赤緯是太陽與地球中心連線與地球赤道面之間的夾角,在實際計算時,這一夾角的大小就是地球受太陽直射點的地理緯度。時角以360°代表一天的時間,以正午12點為界,更早的時間其時角為負而更晚的為正,以每小時15°的幅度進行均分。

在任一位置,當其地方時間為正午時,上述公式中cos(t)為1,由三角函數(shù)公式可知其正午時太陽高度角公式如下

sinγ=cos(α-β)→γ=90°-|α-β|

(4)

本文對目標進行時間窗計算時,把時間窗開始時間轉換為當?shù)氐胤綍r,并計算當?shù)禺敃r的太陽高度角。對于太陽高度角不符合衛(wèi)星有效載荷約束條件的時間窗口,在任務規(guī)劃前就舍去。

2.1.3 側擺動作約束

衛(wèi)星的側擺約束和自身的動作模板約束共同構成了衛(wèi)星觀測時的機動約束。

1)動作模板約束

對于所有衛(wèi)星而言,在觀測之前需要進行準備動作,同時在觀測結束后需要進行關機和衛(wèi)星機動回正操作,其過程如圖2所示。

圖2 動作模板約束

2)側擺約束

如圖2所示,在同一個動作模板內(nèi),部分衛(wèi)星可以通過連續(xù)側擺進行多次觀測。在問題建模中,當兩個目標的觀測時間窗彼此間隔時間大于兩個目標之間衛(wèi)星側擺需要的時間,即認為這兩個時間窗不發(fā)生沖突,否則時間窗沖突不能同時激活。現(xiàn)有衛(wèi)星側擺方式主要為階梯式與線性形式兩種。

表1表示了衛(wèi)星側擺設置的一般情況,在非線性側擺方式下,對于給定側擺角度α,先找出這一角度所述的側擺區(qū)間[ai,aj],則側擺角度α對應側擺耗時即為表中對應的ti。在線性側擺方式下,表1中最后一列表示了當側擺角度為該行對應上限角度時所用時間,對于給定側擺角度α∈[ai,aj],側擺時間計算公式使用插值計算方式,具體如下

表1 側擺耗時計算表

(5)

2.2 觀測問題建模

在處理多星多點觀測問題時,通常對于衛(wèi)星觀測范圍建立兩個觀測窗口,一個表示衛(wèi)星能夠觀察到的范圍,用于目標觀測時間窗的計算;另一個表示衛(wèi)星實際的瞬時觀測范圍,用來表明衛(wèi)星在某一時刻只能對前一窗口大范圍中的一小部分進行觀測。較小的窗口受到上文所列出的各種約束的限制。最終,根據(jù)衛(wèi)星個體、衛(wèi)星有效載荷、分辨率、地面目標可視窗口等因素,建立了如圖3所示的映射關系。

圖3 衛(wèi)星目標映射關系示意

圖4 改進的變異流程

圖5 改進遺傳-螢火蟲組合算法

由上述模型與問題,可以對涉及到的各項因素或變量進行如下定義:

①任務規(guī)劃場景時間起始于Tstart,結束于Tend。

②對于場景內(nèi)的衛(wèi)星,定義衛(wèi)星集合SA={Sat1, Sat2,…, Satn},n表示衛(wèi)星總數(shù);對于星上搭載的載荷,定義集合Si={Sen1,…, Senm},該集合表示衛(wèi)星i上搭載的所有m個載荷。

③對于單顆衛(wèi)星,設定其側擺最大幅度θ。

④對于可連續(xù)側擺衛(wèi)星,依照表1配置其角度-耗時,每顆衛(wèi)星各自側擺表項對應集合S-Cons={Cons1,…, Consn}相同位置元素。

⑤對于所有衛(wèi)星,配置其動作模板,各衛(wèi)星動作模板對應集合M={M1,…, Mn}中元素,而元素Mi={tbegin-i, tend-i, tgap-i}分別表示動作模板中的準備時間、恢復時間和動作模板間隔。

⑥對于地面各觀測目標,建立集合Target={Target1,…, Targeto},o為場景內(nèi)觀測目標總數(shù),同時各地面目標的優(yōu)先級對應集合p={p1,…, po}中的元素。

⑦分別建立以衛(wèi)星作為劃分和以目標作為劃分的時間窗集合。集合WSi表示衛(wèi)星i對所有目標進行觀測所獲得的時間窗口,集合WTj表示目標j被所有衛(wèi)星觀測的時間窗口,其中元素wijk表示衛(wèi)星i對目標j的第k個時間窗口,該窗口起始時間記為sijk,結束時間記為eijk。

⑧對于場景中所有的觀測時間窗口集合:

(6)

建立對應決策變量集合X,其中元素xijk表示衛(wèi)星i對于目標j的第k個時間窗口是否被激活,若激活表示衛(wèi)星i在這一時間窗口內(nèi)對目標j進行觀測,否則不觀測,xijk為0或1。

⑨建立集合profit={pro1,…, proo}表示最終任務分配完后各目標所能提供的收益量化。

根據(jù)上述定義,可得出以下目標和約束。

①所有目標的最終觀測收益綜合最大化

(7)

②所有的時間窗都應該處在任務場景的開始時間與結束時間之內(nèi),即

Tstart≤sijk≤Tend,Tstart≤eijk≤Tend

(8)

③對于所有時間窗口,需要首先完成太陽高度角約束與分辨率要求的約束,即縮小任務規(guī)劃范圍,減少有效時間窗數(shù)量。

④衛(wèi)星相鄰的觀測時間窗口,其時間差應當大于兩者之間側擺所要花費的時間

WSi(j+1)-WSij≥tside

(9)

其中tside可由式(5)獲得。

在任務規(guī)劃需要符合約束條件的同時,觀測收益的總和還需要考慮如下要求:對于高優(yōu)先級目標,其理應得到更多的觀測資源但不能因此而放棄對低優(yōu)先級目標的觀測。因此,最終達到的理想情況是所有目標均能得到觀測,且觀測資源的分配按照優(yōu)先級逐級遞減,各目標自身所分配到的觀測資源分布較為平均,不會出現(xiàn)集中觀測的情況。

3 改進遺傳-螢火蟲算法

3.1 改進遺傳算法

傳統(tǒng)遺傳算法由于不關注個體屬性與差異,導致在衛(wèi)星規(guī)劃問題中不可行解占據(jù)了解空間的絕大部分,如果不根據(jù)最終解碼規(guī)劃方案的可行與否來對種群個體分別進行處理,則算法性能會大幅降低,種群整體陷入不可行解的范圍,無法及時跳出到可行解所在的解空間區(qū)域。因此,針對多星觀測任務規(guī)劃問題,提出了一種改進的遺傳算法來解決解空間中具有多數(shù)不可行解的問題。

3.1.1 初始化與個體編碼

本文對于衛(wèi)星對點目標觀測的任務序列采取二進制編碼。在對每顆衛(wèi)星獨自進行時間窗排序后,將所有衛(wèi)星各自時間窗序列拼接為一個長序列即整個仿真場景內(nèi)的任務序列,序列中激活的時間窗標記為1,非激活時間窗標記為0,以此形成遺傳算法所需要的染色體。種群大小設置為150-250,迭代次數(shù)設置為500代。由于約束條件的存在,解空間中存在大量不可行解,種群內(nèi)個體過少或迭代次數(shù)過少會導致無法靠近可行解所在解空間,因此需要適當使用更大種群進行多次迭代。

3.1.2 個體選擇

遺傳算法通過交叉選擇出能夠生成下一代個體的本代親本,通常使用的選擇法有輪盤賭算法、精英保留法和錦標賽選擇法。本文使用輪盤賭算法和精英保留法結合的選擇方法。

精英保留法,通過保留每一代若干個適應度最高的個體,將其不做任何處理傳遞到下一代,從而保證本代最優(yōu)秀基因能夠完全保留。

輪盤賭選擇法,根據(jù)個體適應度按一定概率選擇親本,每一個體被選為親本的概率為

(10)

其中φ(i)為個體適應度值,max為種群個體數(shù),適應度越高的個體越容易被選擇。

在產(chǎn)生每一代新個體的過程中,文中的結合算法先使用精英選擇法保留種群中適應度前10的個體不做處理直接進入下一代,然后在本代種群中使用輪盤賭選擇法選擇親本,不斷交叉產(chǎn)生子代直到新種群數(shù)量達標。

3.1.3 交叉與變異

交叉與變異是遺傳算法尋優(yōu)主要手段。親本通過交叉算子兩兩重組,從而得到具有相似信息的子代。本文中交叉算子選擇了兩點交叉,隨機在親本上選擇兩個不同基因點位,兩親本對應位置的基因互相交換,進而產(chǎn)生兩個新個體。由于已使用了精英選擇法讓一部分較好的個體保持優(yōu)良形狀不變,因此剩余個體進行交叉的概率為1,新種群由不產(chǎn)生交叉的優(yōu)秀上代個體與必定交叉的新子代個體組成。

在改進遺傳算法中,本文的變異算子不同于傳統(tǒng)遺傳算法,其在前期替代交叉算子,作為主要尋優(yōu)手段,而不只是產(chǎn)生一定擾動,擴大搜索范圍這一作用。本文的改進遺傳算法通過分別處理可行解與不可行解,對多星多點目標觀測規(guī)劃問題進行優(yōu)化。具體策略為:對于不可行解,由于其不可行的原因在于任務序列沖突,因此需要減少任務數(shù)量;對于可行解,希望能更進一步獲得更優(yōu)解,因此需要增加任務數(shù)量。改進算法的變異過程流程圖如下:

3.1.4 適應度函數(shù)設計

在適應度計算環(huán)節(jié),同樣需要根據(jù)實際情況對個體使用不同計算方式。在解碼階段,染色體的基因序列被翻譯成場景內(nèi)各個衛(wèi)星的任務序列,從這一序列中可以獲得各個目標被觀測的次數(shù),綜合各個目標的優(yōu)先級,以及最終解碼得到的序列是否合法,用以計算得出個體最終的適應度。

多優(yōu)先級目標環(huán)境下的衛(wèi)星觀測任務籌劃問題的目的在于:讓高優(yōu)先級目標盡可能多被觀測到的同時,不至于擠占低優(yōu)先級目標的觀測窗口。設計適應度函數(shù)時遵循如下思路:高優(yōu)先級目標在同等條件下會提供更高的適應度,同時隨著高優(yōu)先級目標觀測次數(shù)的增多,其適應度逐漸下降,直到累積一定次數(shù)后,低優(yōu)先級目標此時會提供更高的適應度。這一思路可簡化為:未被觀測到的低優(yōu)先級目標,其適應度高于多次被觀測到的高優(yōu)先級目標。

最后,在上述方法前提下,需將可行解與不可行解做出區(qū)分,可行解的適應度應高于不可行解。同時由于下述兩點原因,不可行解的適應度不能直接設置為0:①高“適應度”的不可行解在將少部分沖突任務刪除后,產(chǎn)生高適應度可行解的可能性很大,直接剝奪該個體進入下一代的機會會使其部分優(yōu)良基因丟失;②在整個解空間中,不可行解的數(shù)量遠大于可行解,在種群迭代初期,整個種群中可能沒有可行解或只有很少可行解,在這種情況下如果不可行解的適應度直接設置為0,則算法收斂速度會非?？?失去了搜索的意義或者直接無法繼續(xù)運行,即沒有個體可進入下一代。

綜上所述,在實際的適應度計算中,選擇保證各個目標的優(yōu)先級在前期隨著觀測次數(shù)遞減,并最終成為定值,在初步計算完成之后,將可行解的適應度乘以可行解系數(shù)α,保證可行解在種群的頭部,而高優(yōu)先級不可行解在次一級的位置。最終的計算公式如下:

(11)

(12)

(13)

其中φ(i)為個體的最終適應度。

3.2 改進遺傳-螢火蟲組合算法

3.2.1 組合算法設計思路

在使用改進遺傳算法求解多星多點觀測規(guī)劃問題時,起到主要尋優(yōu)作用的是改進后的變異過程,通過對少部分基因點位的變異產(chǎn)生全新的解,從而產(chǎn)生可能的更優(yōu)解。在算法的進行過程中,對于高適應度個體以及交叉選擇過程的利用率并不高。同時,當算法種群收斂時,種群內(nèi)個體基本都為可行解,變異產(chǎn)生新個體的概率大幅降低,尋優(yōu)性能下降。

為了進一步提高改進遺傳算法的尋優(yōu)性能,提高算法進入后期時的尋優(yōu)能力,并且讓高優(yōu)先級個體對問題求解起到一定的導向作用,本文引入了螢火蟲算法[13],借鑒螢火蟲算法中“高亮度的螢火蟲會吸引低亮度的螢火蟲,而其它個體圍繞最優(yōu)個體搜索的同時也在慢慢向其靠近”的思想,使低適應度個體及不可行個體更快地向更優(yōu)解轉化。改進的遺傳-螢火蟲組合算法如下圖所示。

3.2.2 組合算法實現(xiàn)

由于在多星多點目標觀測規(guī)劃問題中,衛(wèi)星觀測時間窗具有數(shù)量大,狀態(tài)少的特點,各維度只有0-1兩個位置,在執(zhí)行改進遺傳-螢火蟲組合算法的靠近過程時難以直接套用螢火蟲算法模型。因此需要將模型進行一定修改,將螢火蟲算法中的“位置”與遺傳算法中的“基因編碼”,“移動距離”與“變異概率”進行對應轉化,從而解決模型使用上的問題。

由于螢火蟲算法有較強局部優(yōu)化能力,因此只有當種群中有一部分個體向最優(yōu)解靠攏時啟動算法,才能有較好效果;否則算法會向最初產(chǎn)生的不可行解靠攏,反而會降低性能。

組合后的改進遺傳-螢火蟲算法流程如下:

1)初始化種群

2)計算種群個體適應度,判斷當前種群是否出現(xiàn)最優(yōu)可行個體,是則進入3)否則4)。

3)執(zhí)行螢火蟲算法

具體而言,螢火蟲算法的核心步驟包括:

①初始化。確定種群數(shù)量、問題維度、迭代次數(shù)等,并隨機生成若干螢火蟲個體的位置,同時定義適應度函數(shù),即個體“亮度值”。

②靠近過程。螢火蟲間的吸引程度與其亮度、距離均相關,吸引度由以下公式計算得到

β=β0*e-γrij

(14)

式中β0為螢火蟲距離為0時的吸引度,也叫最大吸引度,通常設置為1;γ為吸引度系數(shù);rij為兩螢火蟲之間距離的平方。

各螢火蟲根據(jù)吸引度如下方式更新位置

(15)

多項式最后一項表示螢火蟲在靠近過程中進行的隨機擾動,該過程利于跳出局部最優(yōu)解。

③計算亮度。在靠近過程后,根據(jù)所有螢火蟲的新位置重新計算其適應度即亮度。

④判斷結束條件。若符合迭代次數(shù)或適應度閾值,則退出迭代并輸出最優(yōu)解,否則繼續(xù)。

本文在將螢火蟲算法與改進遺傳算法進行組合時,只取其中核心的“靠近”思想,將“靠近”視作低適應度個體向高適應度個體的定向變異,從而得到本步驟的下述操作。

使當前種群中適應度最低的后50個個體或者所有不可行個體向種群中的最優(yōu)個體定向變異(即螢火蟲算法的“靠近”過程)。每個差異點位的變異概率如下

p=e-λr

(16)

其中r為差異個數(shù),不選擇差異個數(shù)的平方作為計算參數(shù)的原因在于,問題本身的維度很高導致了差異可能較大,如果使用平方進行計算的話,則不可行解向可行解靠近的概率過小,會導致算法起不到預期作用。

4)對執(zhí)行螢火蟲算法之后的個體重新計算適應度,并使用精英保留法和輪盤賭法相結合的算法產(chǎn)生擁有足量個體的新種群。

5)對所有個體按照改進遺傳算法的處理方法進行變異操作。

6)判斷是否符合退出條件,是則轉7),不是則轉入步驟2)。

7)計算適應度,對所有個體進行排序,并將當代最優(yōu)個體與全流程最優(yōu)個體對比,擇其較優(yōu)者解碼,生成多星觀測任務規(guī)劃序列。

4 實驗結果與分析

在通過實驗測試本文改進遺傳-螢火蟲算法的性能時,一共設立了三個場景,分別對應“目標觀測條件差”、“目標觀測條件優(yōu)”以及“綜合場景”,以驗證改進遺傳-螢火蟲算法在不同仿真場景的表現(xiàn)均優(yōu)于其它優(yōu)化算法。

選擇用于比較的優(yōu)化算法時考慮到:貪心算法作為傳統(tǒng)優(yōu)化算法,具有使用簡單,運行速度快的優(yōu)點;遺傳-模擬退火算法作為常見的優(yōu)化算法組合也曾經(jīng)用于衛(wèi)星觀測規(guī)劃問題上(本實驗中的遺傳-模擬退火算法使用改進后的遺傳算法,提升了原算法的效能),具有一定的代表性。因此,將這兩種算法以及單獨的改進遺傳算法與本文的改進遺傳-螢火蟲組合算法進行實驗對比,下文中分別表述為:貪心算法、遺傳-模擬退火算法/GSA、本文改進遺傳算法/IGA、本文改進遺傳-螢火蟲算法/GFA。

4.1 觀測條件較差區(qū)域

觀測條件不佳有若干因素,例如點目標過于偏離衛(wèi)星星下點軌跡,衛(wèi)星觀測位置的太陽高度角過低,又或者目標分布過于密集導致沖突過多等。本場景選擇了北美洲西海岸區(qū)域的若干目標,具有密度大、部分目標偏離衛(wèi)星觀測范圍的特征,場景3D/2D示意如圖6所示。

圖6 以觀測條件較差區(qū)域為例的場景

場景內(nèi)共有衛(wèi)星5顆,目標16個,可激活時間窗總量為633,各算法執(zhí)行結果及智能優(yōu)化算法適應度迭代情況如表2、圖7所示。其中,結果表內(nèi)數(shù)據(jù)為10次實驗后的平均值。

表2 表觀測條件較差區(qū)域的規(guī)劃結果

圖7 觀測條件較差區(qū)域的適應度迭代圖

根據(jù)種群初始化方式,初始序列中激活時間窗的比例應當為時間窗總數(shù)的50%左右,但最后得出個體的時間窗總數(shù)只有25%左右,比例大大降低。分析原因有以下兩點:首先,隨著時間推移,衛(wèi)星星下點軌跡逐漸轉動,最終可能偏離北美洲西部區(qū)域,導致觀測目標脫離觀測范圍;其次,在規(guī)劃場景時間后期,部分衛(wèi)星的觀測區(qū)域雖然仍在北美洲西部附近,但目標本身分布較為密集,互相之間觀測沖突較多,衛(wèi)星對這些目標各自雖具有充分的觀測能力,但這些時間窗之間不能兼容,所以在選擇激活一個時間窗的同時需要拋棄大量的其它時間窗,最終導致規(guī)劃任務整體數(shù)量較少。

4.2 觀測條件較好區(qū)域

觀測條件較好區(qū)域意味著目標分布較為均勻,沖突少,且大致分布在衛(wèi)星觀測范圍之內(nèi)。該組實驗選擇了赤道附近的若干點目標,目標分布遵循上述原則。場景內(nèi)共有衛(wèi)星5顆,目標13個,可激活時間窗數(shù)量為574,規(guī)劃結果與適應度迭代情況分別如表3、圖8所示。

表3 表觀測條件較好區(qū)域的規(guī)劃結果

圖8 觀測條件較好區(qū)域的適應度迭代圖

相比觀測條件較差區(qū)域,本區(qū)域實驗可以看出,隨著衛(wèi)星觀測條件變好,算法規(guī)劃的結果也會提升,在該區(qū)域中,最終規(guī)劃結果中激活時間窗的比例只略低于初始化時的50%。且從圖8可發(fā)現(xiàn),在實驗中改進遺傳-螢火蟲算法能夠最快進入可行解所在區(qū)域,并在另外兩種算法逐漸收斂的后期依舊能找到更優(yōu)結果。

4.3 綜合區(qū)域

相比前兩組實驗,綜合區(qū)域更加符合實際應用時的仿真場景,即兼有密集目標與稀疏目標,目標分布不以衛(wèi)星觀測范圍為準,而是根據(jù)現(xiàn)實情況進行隨機分布。在該組實驗中,選取了從東南亞向北一直到中國大陸北部附近區(qū)域的一系列點目標。場景內(nèi)共有衛(wèi)星5顆,目標19個,任務總數(shù)為676個,規(guī)劃結果與適應度迭代情況如表4、圖9所示。

表4 綜合區(qū)域的規(guī)劃結果

圖9 綜合區(qū)域的適應度迭代圖

最終規(guī)劃結果占據(jù)場景內(nèi)任務總數(shù)的30%到40%,介于觀測條件較好區(qū)域與較差區(qū)域之間,說明多星多目標觀測任務規(guī)劃算法的結果同時受到算法性能和場景條件的影響。而在不同實驗條件下,改進遺傳-螢火蟲算法相比其它算法均有更好的尋優(yōu)性能,從圖7-9可以看出,其它算法在400代之后已經(jīng)收斂,而本文算法在400代之后仍有一定的尋優(yōu)能力。

5 結論

本文對遺傳算法應用于多星多目標觀測規(guī)劃問題進行了改進,使改進遺傳算法更適合解決這一問題,同時進一步結合螢火蟲算法的思想,使用該算法的優(yōu)越局部性對改進遺傳算法進行優(yōu)化,組合后的算法具有以下優(yōu)點:

1)提出的改進遺傳算法比傳統(tǒng)遺傳算法具有更強針對性,通過先行對規(guī)劃方案進行解碼判別,能夠較傳統(tǒng)算法更快跳出不可行解區(qū)域,找到可行解從而進入之后的選擇過程。

2)該組合算法對改進后的遺傳算法引入了之前尚未被應用在這一問題上的螢火蟲算法,用于提升遺傳算法中交叉、變異過程的篩選尋優(yōu)能力。單純的改進遺傳算法針對衛(wèi)星規(guī)劃問題過度依賴變異過程來產(chǎn)生更優(yōu)個體,而變異過程的隨機性太強,單次實驗的結果優(yōu)劣難以預料。螢火蟲算法較好的局部性恰好彌補了遺傳算法這方面的不足,通過讓多數(shù)不良個體定向向最優(yōu)個體靠攏,加大了算法在最優(yōu)解附近的搜索能力,同時讓交叉過程更多的發(fā)生在較優(yōu)個體中,顯著提升了算法性能。

另外,算法采用的是非機器學習的仿真優(yōu)化方案,沒有對于往期大量規(guī)劃數(shù)據(jù)的需求,不受過往較差規(guī)劃方案的影響;同時,通過仿真,能夠擺脫時間的約束,提前對衛(wèi)星的規(guī)劃作出決策與評估,降低了規(guī)劃成本。