敏捷成像衛(wèi)星調(diào)度的改進(jìn)量子遺傳算法

王海蛟，賀 歡，楊 震

(1. 中國(guó)科學(xué)院大學(xué)，北京 100190；2. 中國(guó)科學(xué)院國(guó)家空間科學(xué)中心，北京 100190)

0 引 言

成像衛(wèi)星調(diào)度問(wèn)題的本質(zhì)是為成像衛(wèi)星選取觀測(cè)任務(wù)，指定觀測(cè)時(shí)間。相比于傳統(tǒng)成像衛(wèi)星，敏捷成像衛(wèi)星增加了俯仰和偏航兩個(gè)自由度，這使敏捷成像衛(wèi)星具備更強(qiáng)的對(duì)地觀測(cè)能力。然而，這也使得敏捷成像衛(wèi)星調(diào)度問(wèn)題的解空間變大，且管控中敏捷成像衛(wèi)星的觀測(cè)開始時(shí)間是一個(gè)具有連續(xù)值域的變量，非敏捷衛(wèi)星調(diào)度所采用的組合優(yōu)化的調(diào)度方法不再適用[1]。

國(guó)內(nèi)外許多學(xué)者都就敏捷成像衛(wèi)星調(diào)度問(wèn)題進(jìn)行了研究：Lema Tre[2]研究了單顆敏捷衛(wèi)星調(diào)度中的任務(wù)選擇問(wèn)題，在只考慮單圈軌道的敏捷成像衛(wèi)星調(diào)度問(wèn)題的情況下，建立簡(jiǎn)化模型，并提出貪婪算法、動(dòng)態(tài)規(guī)劃、約束滿足、局部搜索四種不同的算法。Habet[3]等對(duì)禁忌搜索算法進(jìn)行改進(jìn)，采用一致性滲透的采樣方法來(lái)加搜索空間，同時(shí)，引入局部窮舉搜索算法，提高算法的優(yōu)化結(jié)果。Sun[4]等針對(duì)敏捷衛(wèi)星成像調(diào)度問(wèn)題，提出一種改進(jìn)的遺傳算法，顯著提升了調(diào)度效果。Hao[5]等建立一種考慮任務(wù)消耗、任務(wù)完成率、應(yīng)用效益的多目標(biāo)敏捷成像衛(wèi)星調(diào)度模型，并提出一種結(jié)合蟻群算法(ACO)和遺傳算法(GA)的雜合算法。劉嵩[6]等就敏捷成像衛(wèi)星自主規(guī)劃問(wèn)題進(jìn)行研究，采用建立衛(wèi)星動(dòng)作序列模版方式，設(shè)計(jì)多種啟發(fā)式規(guī)則建立一種單星自主規(guī)劃模型。Geng[7]等建立了一種二進(jìn)制與整數(shù)變量混存的調(diào)度模型，并提出一種二進(jìn)制與整數(shù)雜合編碼的遺傳算法求解敏捷成像衛(wèi)星調(diào)度問(wèn)題，并結(jié)合一個(gè)啟發(fā)式規(guī)則選取觀測(cè)開始時(shí)間。郝會(huì)成[8]等基于誠(chéng)信機(jī)制的可解約合同網(wǎng)任務(wù)分配方法，設(shè)計(jì)了招投標(biāo)機(jī)制和評(píng)標(biāo)策略等，提出一種Multi-Agent敏捷衛(wèi)星任務(wù)規(guī)劃調(diào)度方法。Zang[9]等提出了一種改進(jìn)的遺傳算法，通過(guò)高質(zhì)量初始解快速的生成敏捷成像衛(wèi)星的規(guī)劃方案。王建江[10]等引入非約束支配路徑的概念，提出基于標(biāo)記更新思想的動(dòng)態(tài)路徑搜索算法(DPSA)對(duì)成像衛(wèi)星調(diào)度問(wèn)題進(jìn)行求解，DPSA算法在犧牲一定求解效率的基礎(chǔ)上,能夠提高調(diào)度效果。嚴(yán)珍珍[11]等人將均勻設(shè)計(jì)思想引入蟻群算法設(shè)計(jì)，提出一種改進(jìn)的蟻群算法，目的在于解決蟻群算法參數(shù)設(shè)計(jì)難的問(wèn)題。孫凱[12]等針對(duì)敏捷衛(wèi)星對(duì)地觀測(cè)中直拍直傳、立體成像等復(fù)雜任務(wù)需求以及成像觀測(cè)、數(shù)據(jù)下傳、對(duì)日定向等九種衛(wèi)星動(dòng)作，設(shè)計(jì)了基于專家知識(shí)的多種啟發(fā)式規(guī)則，用于決定任務(wù)安排并同時(shí)安排衛(wèi)星動(dòng)作序列。

這些研究大都將敏捷成像衛(wèi)星調(diào)度抽象為考慮能源、存儲(chǔ)、時(shí)序等約束的優(yōu)化問(wèn)題。模型的決策變量多采用單一整數(shù)或者二進(jìn)制數(shù)。然而，單一決策變量常常導(dǎo)致在求解算法中編碼長(zhǎng)度過(guò)長(zhǎng)，影響求解效率。同時(shí)，二進(jìn)制與整數(shù)的決策變量也難以有效表達(dá)敏捷成像衛(wèi)星解空間連續(xù)問(wèn)題。就求解算法而言，現(xiàn)有研究多采用智能優(yōu)化算法和啟發(fā)式算法,這些算法有的采用二進(jìn)制或者整數(shù)編碼，如遺傳算法；有的采用實(shí)數(shù)編碼，如蟻群算法；而采用混合編碼的研究還較為少見。

量子遺傳算法是目前應(yīng)用較為廣泛的一種量子優(yōu)化算法，相比于傳統(tǒng)智能優(yōu)化算法具有很好的尋優(yōu)和收斂性能。量子遺傳算法在量子空間進(jìn)行尋優(yōu)搜索的特性也可以很好解決連續(xù)搜索問(wèn)題[15]。

本文針對(duì)敏捷成像衛(wèi)星調(diào)度問(wèn)題中解空間大，解空間離散與連續(xù)并存的難題，提出一種多種決策變量混合的敏捷成像衛(wèi)星調(diào)度模型；與經(jīng)典衛(wèi)星調(diào)度模型不同，多種決策變量混合的調(diào)度模型將任務(wù)的接受與否，任務(wù)時(shí)間窗口選擇，任務(wù)觀測(cè)開始時(shí)間選擇分別用不同決策變量進(jìn)行表征，可以更好描述敏捷衛(wèi)星調(diào)度問(wèn)題。以此為基礎(chǔ)，本文提出一種二進(jìn)制與實(shí)數(shù)雜合編碼的改進(jìn)量子遺傳算法；雜合編碼可以有效表達(dá)敏捷成像衛(wèi)星離散與連續(xù)并存的解空間。此外，雜合編碼的二進(jìn)制部分與實(shí)數(shù)部分在尋優(yōu)過(guò)程中并行搜索，有助于提高算法效率和求解質(zhì)量。同時(shí)，由于量子優(yōu)化算法的量子疊加態(tài)可以提高種群多樣性，使得改進(jìn)的量子遺傳算法具有優(yōu)良的尋優(yōu)和收斂性能，可以快速有效求解敏捷成像衛(wèi)星調(diào)度問(wèn)題。

1 多決策變量的敏捷成像衛(wèi)星調(diào)度模型

1.1 問(wèn)題分析

相比于傳統(tǒng)成像衛(wèi)星，敏捷成像衛(wèi)星多了俯仰和偏航兩個(gè)自由度，使得任務(wù)的可用時(shí)間窗口變多，且時(shí)間窗口變長(zhǎng)。相比于一般的成像調(diào)度問(wèn)題，除選定任務(wù)的時(shí)間窗口，還需在選定時(shí)間窗口內(nèi)選擇具體的觀測(cè)時(shí)間，使敏捷成像衛(wèi)星的調(diào)度具有更大難度。如圖1所示，對(duì)于非敏捷成像衛(wèi)星而言，僅能在特定的時(shí)間觀測(cè)目標(biāo)，而敏捷成像衛(wèi)星對(duì)目標(biāo)的觀測(cè)時(shí)間則可以在[t1,t2]這樣一個(gè)連續(xù)時(shí)段中選擇。

大部分現(xiàn)有研究多以整數(shù)或者二進(jìn)制決策變量來(lái)對(duì)該問(wèn)題進(jìn)行建模，客觀上會(huì)把敏捷成像衛(wèi)星調(diào)度問(wèn)題的解空間離散化，不同的離散化粒度對(duì)搜索求解質(zhì)量有很大的影響(如圖2中(a)，時(shí)間窗口0被離散化為開始時(shí)間是t0,t1,t2的三個(gè)時(shí)間窗口)。若直接采用連續(xù)變量進(jìn)行表征，又會(huì)復(fù)雜化問(wèn)題，降低求解效率(如圖2中(a)，直接采用觀測(cè)時(shí)間To作為決策變量，在連續(xù)時(shí)間域上進(jìn)行搜索)。

針對(duì)以上敏捷成像衛(wèi)星調(diào)度問(wèn)題的特性，本文將敏捷衛(wèi)星成像調(diào)度的問(wèn)題描述為由兩個(gè)離散域搜索和一個(gè)連續(xù)域搜索并存的優(yōu)化問(wèn)題，具體描述如下：

給定可用敏捷成像衛(wèi)星集合和待完成的任務(wù)集合，每個(gè)任務(wù)具有多個(gè)通過(guò)過(guò)境分析等預(yù)處理獲得時(shí)間窗口，形成任務(wù)的時(shí)間窗口集合。敏捷成像衛(wèi)星調(diào)度是在滿足衛(wèi)星使用約束的前提下，從任務(wù)集合選定一組待觀測(cè)任務(wù)(離散域搜索)；然后為這些選定的任務(wù)從其時(shí)間窗口集合選擇一個(gè)時(shí)間窗口(離散域搜索)，并從所選時(shí)間窗口中指定任務(wù)開始觀測(cè)時(shí)間(連續(xù)域搜索)；調(diào)度目標(biāo)是最大化衛(wèi)星的應(yīng)用效益，本文選取完成任務(wù)優(yōu)先級(jí)之和作為衛(wèi)星應(yīng)用效益的度量值。通過(guò)分開描述任務(wù)選擇和任務(wù)觀測(cè)時(shí)間確定，避免了時(shí)間窗口在問(wèn)題建模階段的離散化，從而使得模型和搜索算法能更好覆蓋敏捷成像問(wèn)題的解空間。

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

1.2.1符號(hào)定義

為描述方便，首先給出以下符號(hào)定義：

(1)觀測(cè)任務(wù)

(2)敏捷成像衛(wèi)星

(3)時(shí)間窗口

(1)

其中，rα是t時(shí)刻的橫滾角度，φα是t時(shí)刻的俯仰角度；該序列可用Satellite Tool Kit (STK)在時(shí)間窗口預(yù)處理階段獲得。

(4)決策變量及其值域

與一般敏捷成像衛(wèi)星調(diào)度模型不同，本文采取多決策變量描述敏捷成像衛(wèi)星調(diào)度中的決策，定義如下：

任務(wù)選擇決策變量xi：xi=1表示第i個(gè)任務(wù)被選擇，xi=0表示不選擇。

時(shí)間窗口選擇決策變量yi：yi表示給第i個(gè)任務(wù)選擇的時(shí)間窗口的序號(hào)；若yi=k則安排任務(wù)在第k個(gè)時(shí)間窗口Wi,k上執(zhí)行。

成像時(shí)間決策變量ti：ti代表第i個(gè)任務(wù)的開始觀測(cè)時(shí)間。

1.2.2敏捷成像衛(wèi)星調(diào)度的問(wèn)題模型

基于上述分析與定義，敏捷成像衛(wèi)星調(diào)度問(wèn)題可以轉(zhuǎn)換為帶約束的多變量混合優(yōu)化問(wèn)題，問(wèn)題求解就是找出一組決策變量集合，并滿足以下條件：

(2)

(3)

(4)

(5)

ti+di+ftran(p,i,j)≤tj

(6)

(7)

與一般的衛(wèi)星調(diào)度模型不同，本文所建立的調(diào)度模型中，分別采用二進(jìn)制、整數(shù)、實(shí)數(shù)三種決策變量來(lái)表達(dá)敏捷成像衛(wèi)星調(diào)度中關(guān)于任務(wù)選擇、時(shí)間窗口選擇、成像時(shí)間選擇這三種不同值域的決策，更好表達(dá)了敏捷成像衛(wèi)星調(diào)度問(wèn)題。此外，基于該模型，在本文第三節(jié)所提出的改進(jìn)的量子遺傳算法中，可以用一位編碼表達(dá)一個(gè)任務(wù)的所有時(shí)間窗口，簡(jiǎn)化了編碼結(jié)構(gòu)；同時(shí)無(wú)需進(jìn)行任務(wù)唯一執(zhí)行的約束檢查(式(5))，使算法在以該模型為基礎(chǔ)進(jìn)行搜索時(shí)，避開一部分不可行解，提高搜索效率。

但該模型中二進(jìn)制決策變量xi、整數(shù)決策變量yi、實(shí)數(shù)決策變量ti并存，是一個(gè)復(fù)雜的復(fù)合變量規(guī)劃問(wèn)題，常見的成像衛(wèi)星調(diào)度求解算法難以適應(yīng)。因此，本文提出一種改進(jìn)的量子遺傳算法用以求解敏捷成像衛(wèi)星調(diào)度問(wèn)題。

2 改進(jìn)的量子遺傳算法

常見的智能優(yōu)化算法有PSO,遺傳算法,差分進(jìn)化等,這些算法各有優(yōu)劣，如PSO和差分進(jìn)化高效但易限于局部最優(yōu)，遺傳算法收斂速度較慢等。

2.1 量子遺傳算法簡(jiǎn)介

Han[14]等基于量子比特和量子疊加態(tài)概念，結(jié)合遺傳算法提出一種量子遺傳算法，由于量子系統(tǒng)可以表達(dá)疊加態(tài)，從而一條量子狀態(tài)的染色體可以描述多種系統(tǒng)狀態(tài)，相比于傳統(tǒng)遺傳算法，使量子遺傳算法具有更好的種群多樣性和收斂性。一個(gè)雙態(tài)量子位的狀態(tài)可以表示為：

|r=α|0+β|1

(8)

式中：α和β分別代表|0和|1的量子態(tài)概率幅，它們滿足歸一化條件：

(9)

目前常見的量子遺傳算法大多采用量子比特幅的量子態(tài)編碼結(jié)構(gòu)，如式：

(10)

對(duì)應(yīng)的實(shí)體染色體編碼一般采用二進(jìn)制編碼結(jié)構(gòu)[16]，如式(11)：

s=(b0,…,bi,…,bm),bi∈{0,1}

(11)

實(shí)體染色體基因位取值一般通過(guò)觀測(cè)函數(shù)計(jì)算得出，觀測(cè)函數(shù)形如式(12)：

bi=f(αi,βi)

(12)

與傳統(tǒng)遺傳算法不同，量子遺傳算法的搜索尋優(yōu)是在相位空間中利用量子門更新量子位概率幅實(shí)現(xiàn)。

量子遺傳算法基本流程如圖4所示：

量子遺傳算法雖然具有很好的性能和特性，但目前大多數(shù)量子遺傳算法采用基于量子位測(cè)量的二進(jìn)制編碼方式或?qū)崝?shù)編碼方式，存在解碼復(fù)雜等問(wèn)題?；诹孔游粶y(cè)量的二進(jìn)制編碼方式或?qū)崝?shù)編碼方式也不能有效適應(yīng)本文所提出的多種決策變量混合的敏捷成像衛(wèi)星調(diào)度模型。因此，本文提出一種二進(jìn)制與實(shí)數(shù)混合的雜合編碼；以雜合編碼為基礎(chǔ)，將多決策變量的敏捷成像衛(wèi)星調(diào)度模型的解空間映射到量子空間中，從而引入量子遺傳算法求解敏捷成像衛(wèi)星調(diào)度離散與連續(xù)并存的優(yōu)化問(wèn)題。

2.2 改進(jìn)的量子遺傳算法

針對(duì)敏捷成像衛(wèi)星調(diào)度問(wèn)題，本文對(duì)量子遺傳算法進(jìn)行以下適應(yīng)性改進(jìn)：提出二進(jìn)制與實(shí)數(shù)編碼相結(jié)合的染色體編碼方式，將敏捷成像衛(wèi)星的解空間映射到相位空間；雜合編碼的二進(jìn)制編碼部分和實(shí)數(shù)編碼部分在相位空間分別更新，由不同觀測(cè)函數(shù)測(cè)量并解碼生成敏捷衛(wèi)星調(diào)度模型中的決策變量，實(shí)現(xiàn)連續(xù)域與離散域的并行搜索；同時(shí)，采用混沌序列、量子旋轉(zhuǎn)門和量子非門相結(jié)合的方式進(jìn)行種群更新。

2.2.1雜合染色體編碼

如第1節(jié)中所述，敏捷成像衛(wèi)星調(diào)度問(wèn)題中的決策分為三部分：第一，任務(wù)是否選擇執(zhí)行；第二，若任務(wù)被選擇執(zhí)行，則從其時(shí)間窗口選擇一個(gè)時(shí)間窗口；第三，在選擇的時(shí)間窗口中選擇開始觀測(cè)時(shí)間。n個(gè)任務(wù)的觀測(cè)方案可以表示為：

V={(x0,y0,t0),…,(xi,yi,ti),…,(xn,yn,tn)}

(13)

式中：xi,yi,ti分別是第二節(jié)中多決策變量調(diào)度模型中關(guān)于觀測(cè)任務(wù)選擇，時(shí)間窗口選擇和成像時(shí)間選擇的決策變量。

本文提出一種二進(jìn)制與實(shí)數(shù)雜合的染色體編碼方式對(duì)敏捷成像衛(wèi)星的調(diào)度方案進(jìn)行編碼，編碼方法如式所示：

X={(b0,u0),…,(bi,ui),…,(bn,un)}

(14)

(15)

ui=yi+zi,yi∈{0,1,…,m},zi∈[0，1]

(16)

式中：X代表一個(gè)成像方案的雜合染色體編碼。(bi,ui)代表第i個(gè)任務(wù)的染色體編碼。ui是一個(gè)實(shí)數(shù)，它的整數(shù)部分代表任務(wù)時(shí)間窗口選擇，小數(shù)部分代表觀測(cè)時(shí)間在所選時(shí)間窗口內(nèi)部的滑動(dòng)比例。m是第i個(gè)任務(wù)時(shí)間窗口數(shù)目。雜合染色體的解碼策略在2.2.2節(jié)給出。

圖5為一個(gè)雜合編碼染色體的示例，圖中染色體所代表的含義為任務(wù)0拒絕；任務(wù)1接受，觀測(cè)安排在任務(wù)1的第1個(gè)時(shí)間窗口，開始時(shí)間為第1個(gè)時(shí)間窗口開始時(shí)間延遲20%窗口時(shí)長(zhǎng)；任務(wù)2接受，觀測(cè)安排在第1個(gè)時(shí)間窗口，開始時(shí)間為第1個(gè)時(shí)間窗口開始時(shí)間延遲30%窗口時(shí)長(zhǎng)。

雜合染色體的編碼長(zhǎng)度僅和任務(wù)數(shù)目有關(guān)，不隨衛(wèi)星數(shù)目和時(shí)間窗口數(shù)目增多而增長(zhǎng)，有助于在衛(wèi)星數(shù)目多時(shí)提高算法效率。相比于二進(jìn)制或者整數(shù)的編碼方法，雜合染色體的編碼結(jié)構(gòu)簡(jiǎn)單，解碼容易。

2.2.2雜合編碼的量子概率幅編碼及觀測(cè)函數(shù)

在量子遺傳算法中，染色體的進(jìn)化是在量子空間中進(jìn)行。雜合染色體的量子位概率幅編碼與雜合染色體相對(duì)應(yīng)，分為兩部分：

A.染色體二進(jìn)制編碼的量子概率幅編碼

染色體二進(jìn)制編碼的量子概率幅定義如式(17)：

(17)

對(duì)應(yīng)的觀測(cè)函數(shù)如式(18),α0為選定的閾值，本文中選定α0=0.5：

(18)

任務(wù)選擇決策變量由雜合染色體二進(jìn)制部分解碼得出：xi=bi。

B.染色體實(shí)數(shù)部分的量子概率幅編碼

染色體實(shí)數(shù)部分的量子概率幅編碼定義如式(19)：

(19)

對(duì)應(yīng)的觀測(cè)函數(shù)如式(20)：

(20)

式中：m是第i個(gè)任務(wù)時(shí)間窗口數(shù)目。

時(shí)間窗口選擇決策變量的取值是雜合染色體實(shí)數(shù)部分的整數(shù)部分，計(jì)算方法如式(21)：

(21)

成像時(shí)間決策變量計(jì)算方法如式(22)和式(23)：

zi=ui-yi

(22)

(23)

2.2.3基于量子旋轉(zhuǎn)門和量子非門的個(gè)體更新

量子遺傳算法通過(guò)量子門更新染色體基因位的量子概率幅更新種群。本文選取量子旋轉(zhuǎn)門和量子非門進(jìn)行種群更新，考慮交叉算子需要個(gè)體之間進(jìn)行交叉拷貝，會(huì)降低算法的運(yùn)行效率，本文沒(méi)有選取交叉算子。

A.基于混沌序列的量子旋轉(zhuǎn)門個(gè)體更新

利用量子旋轉(zhuǎn)門對(duì)染色體第i個(gè)基因位的更新如式所示：

(24)

(25)

本文通過(guò)混沌序列確定轉(zhuǎn)角大小。利用混沌遍歷性對(duì)每個(gè)基因位設(shè)置不同的轉(zhuǎn)角，可引入隨機(jī)性增加種群多樣性，降低早熟可能。轉(zhuǎn)角大小計(jì)算方法如式(26)：

(26)

(27)

式中：l為待更新染色體在種群排序，N為種群規(guī)模，μ為混沌系數(shù)，本文取μ=4, Δθ0=0.0785。顯然，對(duì)于排序越靠前的染色體，其轉(zhuǎn)角Δθi會(huì)受限變小，從而減小種群退化的可能。

B.基于量子非門的個(gè)體更新

在基于量子旋轉(zhuǎn)門的種群更新中，各染色體依靠當(dāng)前最優(yōu)染色體引導(dǎo)進(jìn)行更新，若當(dāng)前最優(yōu)染色體是一個(gè)局部最優(yōu)解，就可能導(dǎo)致早熟現(xiàn)象。為增強(qiáng)種群的多樣性，減小早熟的可能，考慮到量子非門無(wú)需當(dāng)前最優(yōu)染色體的介入，本文同時(shí)采用量子非門對(duì)種群進(jìn)行擾動(dòng)更新。具體而言，就是依據(jù)變異概率隨機(jī)選擇數(shù)條染色體，然后隨機(jī)選取選中染色體的部分基因位，對(duì)這些基因位施加量子非門操作。量子非門更新公式定義如式(28)所示

(28)

2.2.4約束檢查與收益計(jì)算

約束檢查時(shí)，按照時(shí)序約束式(6)，成像時(shí)長(zhǎng)約束式(4)，存儲(chǔ)約束式(3)的順序逐個(gè)檢查每個(gè)觀測(cè)任務(wù)安排的可行性；當(dāng)有任務(wù)沖突時(shí)，優(yōu)先退出低優(yōu)先級(jí)的任務(wù)。衛(wèi)星的應(yīng)用效益是所有可行任務(wù)的優(yōu)先級(jí)之和，計(jì)算方法如式(29)：

(29)

2.2.5改進(jìn)的量子遺傳算法流程

基于以上設(shè)計(jì)與改進(jìn)，本文將量子遺傳算法引入敏捷成像衛(wèi)星調(diào)度問(wèn)題中。改進(jìn)的量子遺傳算法的流程如圖6所示：

3 仿真校驗(yàn)與結(jié)果分析

本節(jié)通過(guò)仿真對(duì)多決策變量的敏捷成像衛(wèi)星調(diào)度模型的有效性和改進(jìn)的量子遺傳算法的優(yōu)越性進(jìn)行校驗(yàn)。

3.1 仿真設(shè)定

仿真采用的計(jì)算機(jī)的配置為酷瑞i7, intel雙核處理器,主頻 2.4 GHz，內(nèi)存為4 G，操作系統(tǒng)為windows 7，編程環(huán)境為pyhon3.5。由于衛(wèi)星調(diào)度領(lǐng)域還沒(méi)有公認(rèn)的任務(wù)測(cè)試集合，因此本文設(shè)計(jì)了一個(gè)可以依據(jù)不同輸入生成不同規(guī)模調(diào)度問(wèn)題的生成器。問(wèn)題生成器可以通過(guò)輸入不同的空間范圍和時(shí)間范圍，生成觀測(cè)任務(wù)目標(biāo)序列。為描述方便，本文在后續(xù)仿真試驗(yàn)中將m顆衛(wèi)星n個(gè)任務(wù)的問(wèn)題記為m×n。仿真參數(shù)見表1。

表1 仿真參數(shù)Table1 Parameters of Simulations

任務(wù)的觀測(cè)目標(biāo)為在輸入空間范圍內(nèi)隨機(jī)產(chǎn)生的點(diǎn)目標(biāo)，任務(wù)的成像要求時(shí)長(zhǎng)在3～5 s之間，任務(wù)優(yōu)先級(jí)在1～10之間。衛(wèi)星星載存儲(chǔ)器的最大容量設(shè)為240 G，瞬時(shí)視場(chǎng)角度設(shè)為3°，最大俯仰角度35°，最大側(cè)擺角度45°，姿態(tài)穩(wěn)定時(shí)間為10 s，俯仰機(jī)動(dòng)角速度為3(°)/s,側(cè)擺機(jī)動(dòng)角速度為3(°)/s。

3.2 仿真結(jié)果分析

為測(cè)試本文所提出的雜合編碼的量子遺傳算法在敏捷衛(wèi)星調(diào)度問(wèn)題中的性能，本文做了6組不同規(guī)模的仿真(4×100, 4×200, 4×300, 5×100, 5×200, 5×300)，并與基于雜合編碼的遺傳算法(HGA)和二進(jìn)制編碼的遺傳算法(GA)[9],量子遺傳算法(QGA)[14],蟻群算法(ACO)[11]的運(yùn)行結(jié)果進(jìn)行對(duì)比。其中HGA的編碼方式和解碼策略采用本文所提出的雜合編碼方法。所有算法的姿態(tài)轉(zhuǎn)換時(shí)間均采用本文的方法計(jì)算。每組仿真共運(yùn)行10次，選取總收益和運(yùn)行耗時(shí)的平均值作為評(píng)估指標(biāo)。仿真中算法所用的參數(shù)見表2。仿真結(jié)果見表3，表4。

表2 量子遺傳算法/遺傳算法參數(shù)Table 2 Parameters of QGA, HGA and GA

表3 算法調(diào)度結(jié)果對(duì)比(衛(wèi)星數(shù)目：4)Table 3 Performance comparison (Satellites: 4)

表4 算法調(diào)度結(jié)果對(duì)比(衛(wèi)星數(shù)目：5)Table 4 Performance comparison (Satellites: 5)

從表3，表4中可以看出，在相同的問(wèn)題規(guī)模下，HQGA獲得的收益最高，耗時(shí)最少。HGA和BGA相比具有更高收益和更低的時(shí)間消耗，這說(shuō)明在相同的搜索機(jī)制下，采用雜合編碼有利于提高求解質(zhì)量和運(yùn)行效率。對(duì)比HQGA和HGA，采用量子優(yōu)化機(jī)制的HQGA比HGA的收益更高，說(shuō)明引入量子優(yōu)化機(jī)制的有效性。同時(shí)，HQGA無(wú)需交叉操作，免去了一部分交叉拷貝帶來(lái)的時(shí)間消耗。

進(jìn)一步分析可以看出在HQGA在相同任務(wù)規(guī)模下的耗時(shí)大致相同(4×100規(guī)模下35.28 s, 5×100規(guī)模下36.02 s, 4×200規(guī)模下77.40 s, 5×200規(guī)模下79.62 s)，類似的現(xiàn)象也出現(xiàn)在HGA的仿真結(jié)果上，這是因?yàn)樾l(wèi)星數(shù)目的上升會(huì)增加可用的時(shí)間窗口，加長(zhǎng)二進(jìn)制編碼長(zhǎng)度，從而增加解碼時(shí)間消耗。而本文提出的雜合編碼長(zhǎng)度僅和任務(wù)數(shù)目相關(guān)，衛(wèi)星數(shù)目的上升不會(huì)對(duì)算法運(yùn)行造成影響。

綜上所述，本文所提出的基于雜合編碼改進(jìn)的、量子遺傳算法在敏捷成像衛(wèi)星調(diào)度這種解空間離散與連續(xù)并存的優(yōu)化問(wèn)題上具有很好尋優(yōu)和收斂性能,可以有效解決敏捷成像衛(wèi)星調(diào)度問(wèn)題。

4 結(jié) 論

本文針對(duì)敏捷成像衛(wèi)星調(diào)度中面臨的解空間大、離散搜索與連續(xù)搜索并存的問(wèn)題，提出一種基于雜合編碼的改進(jìn)量子遺傳算法(HQGA)。雜合編碼具有編碼長(zhǎng)度短，解碼簡(jiǎn)單等優(yōu)勢(shì)；同時(shí)，基于量子優(yōu)化機(jī)制，雜合編碼的二進(jìn)制部分與實(shí)數(shù)部分可以在量子空間獨(dú)立并行更新，從而提高算法的尋優(yōu)與收斂性能。仿真試驗(yàn)結(jié)果表明，基于雜合編碼的量子遺傳算法可以有效解決敏捷成像衛(wèi)星調(diào)度問(wèn)題。