張磊,方洋旺,柴棟,雍霄駒

(空軍工程大學航空航天工程學院,陜西西安 710038)

基于改進量子進化算法的巡航導彈航路規(guī)劃方法

張磊,方洋旺,柴棟,雍霄駒

(空軍工程大學航空航天工程學院,陜西西安 710038)

針對巡航導彈作戰(zhàn)區(qū)域廣闊、航路規(guī)劃效率低的問題,提出了基于改進量子進化算法(IQEA)的巡航導彈航路規(guī)劃方法。首先分析并確定巡航導彈航路規(guī)劃空間,建立航路評價的代價指標;針對實數(shù)編碼量子進化算法容易早熟、陷入局部最優(yōu)的缺點,引入染色體的概率表達特性,使得每條染色體均能以一定概率表達優(yōu)化問題的所有可行解;借鑒遺傳算法的思想,在IQEA中引入染色體繁殖機制,結(jié)合動態(tài)量子門實現(xiàn)染色體的進化,實現(xiàn)算法局部搜索和全局搜索的平衡。仿真實驗結(jié)果表明,基于帶繁殖機制的IQEA的航路規(guī)劃算法能夠快速、穩(wěn)定地搜索到代價更低的航路,所規(guī)劃航路能夠有效進行威脅規(guī)避、地形回避和地形跟隨。

運籌學;巡航導彈;航路規(guī)劃;改進量子進化算法

0 引言

巡航導彈航路規(guī)劃是在給定的戰(zhàn)場環(huán)境中,綜合考慮導航精度和機動能力的限制,充分利用地形和敵情信息,為巡航導彈規(guī)劃出從起始點到目標點、在一定的評價指標下性能最優(yōu)或次優(yōu)的飛行軌跡,使巡航導彈能夠進行地形跟隨和回避、規(guī)避敵方威脅,提升作戰(zhàn)效能[1]。由于巡航導彈射程遠、作戰(zhàn)區(qū)域廣闊,通常的規(guī)劃算法搜索出一條可行航路需要很長的時間,難以滿足現(xiàn)代戰(zhàn)爭對作戰(zhàn)反應時間越來越高的要求。因此需要提高航路規(guī)劃算法的效率,在限定時間內(nèi)搜索出航路性能最優(yōu)且滿足各種約束條件的航路。

量子進化算法(QEA)[2-5]自提出以來,被廣泛應用于函數(shù)優(yōu)化、參數(shù)估計、工業(yè)控制、路徑優(yōu)化等領域,能夠以較小的種群規(guī)模實現(xiàn)快速收斂和全局尋優(yōu),其主要特征在于:1)量子位的概率幅表示使得量子染色體能夠以概率表達所有狀態(tài);2)從量子染色體到二進制解的觀測機制;3)通過量子門旋轉(zhuǎn)使得整個種群趨向當前最優(yōu)解帶來的快速收斂性。從本質(zhì)上講,巡航導彈航路規(guī)劃是三維空間中的路徑搜索,是一個具有連續(xù)搜索空間的多約束多目標非線性優(yōu)化問題[6]。目前,已經(jīng)有學者將量子進化算法應用到飛行器航路規(guī)劃中。文獻[7]將量子進化算法應用到無人機航路的搜索和選擇過程中,采用量子門旋轉(zhuǎn)角動態(tài)調(diào)整策略,引入交叉和變異策略實現(xiàn)航路的優(yōu)選。文獻[8]改進了量子染色體的進化策略,使之比基本的QEA具有更高的搜索效率。采用二進制量子比特編碼的進化算法在求解組合優(yōu)化問題時表現(xiàn)出優(yōu)越的性能,然而對于航路規(guī)劃問題而言,這種編碼方式與實際航路相去甚遠,算法的執(zhí)行效率較低,無法滿足搜索精度的要求。與之相比,實數(shù)編碼在概念上更加接近問題空間,從規(guī)劃空間到問題空間和搜索空間的映射都十分直觀。

近年來,許多學者都對實數(shù)編碼QEA進行了研究。Zhao等[9]提出了一種實數(shù)編碼混沌QEA,采用實數(shù)及其相位角進行編碼,實現(xiàn)了神經(jīng)網(wǎng)絡權(quán)重值的調(diào)節(jié)和學習。高輝等[10-11]基于3倍體編碼,利用量子門旋轉(zhuǎn)和互補雙變異算子進化,在保持解的多樣性的同時具有較好的收斂速度。Li等[12]提出了一種基于Bloch球面坐標的量子位編碼算法,采用Bloch球面坐標表示優(yōu)化問題的可行解,能夠避免觀測量子位產(chǎn)生的隨機性,可用于連續(xù)數(shù)值優(yōu)化問題的求解,提高搜索效率。上述研究均采用實數(shù)編碼,基于量子門旋轉(zhuǎn)策略保證進化的方向性,盡量維持群體多樣性和算法收斂性之間的平衡。然而由于缺少了問題可行解的概率表達和隨機觀測,編碼樣本多樣性被極大降低,量子門旋轉(zhuǎn)策略使得所有染色體都朝向當前最優(yōu)染色體快速演化,算法容易陷入局部最優(yōu),極易早熟。

本文在實數(shù)編碼QEA的基礎上,結(jié)合巡航導彈航路規(guī)劃的特點,改進量子進化算法(IQEA)的編碼方式、引入染色體概率表達機制和繁殖機制,實現(xiàn)更加快速、穩(wěn)定的航路搜索。

1 航路規(guī)劃問題描述

巡航導彈航路規(guī)劃問題主要包括約束條件、規(guī)劃空間和代價指標等要素,其定義一般可描述[13]為:在某個作戰(zhàn)環(huán)境中,為巡航導彈規(guī)劃出從預定發(fā)射點S到目標點E的一系列航路點(P1,P2,…, Pn),使得在滿足航路約束條件C的前提下,根據(jù)給定的航路代價指標J,有:

1.1 航路約束條件

由于戰(zhàn)場環(huán)境、導彈機動性能和作戰(zhàn)任務的限制,規(guī)劃航路需要滿足一定的約束條件,主要包括地形約束、射程約束、速度約束、最小直飛距離約束、最大拐彎角約束、最大爬升/俯沖角約束、攻擊進入角約束和攻擊時間約束等。關(guān)于航路約束條件,文獻[13]進行了詳細論述,在此不再贅述。

1.2 規(guī)劃空間描述

巡航導彈航路規(guī)劃是三維空間中的航路點搜索,理論上戰(zhàn)場的任何位置都有可能成為中間航路點。而實際上,由于巡航導彈性能和作戰(zhàn)意圖的約束,航路點的搜索只能在有限的區(qū)域中進行。如圖1所示,巡航導彈的任務是從S點發(fā)射、攻擊位于E點的目標,目標位于巡航導彈最大有效射程之內(nèi),即

式中:LSE為發(fā)射點S與目標點E之間的距離;Lmax為最大有效射程。

圖1 規(guī)劃空間示意圖Fig.1 Path planning space

由于最大有效射程的限制,巡航導彈的規(guī)劃空間即為圖1中所示的虛線長方形包含的空間區(qū)域,記為Ω,虛線長方形的長為Lmax,寬為

定理巡航導彈規(guī)劃航路滿足最大有效射程限制的必要條件為所有航路點Pi都位于規(guī)劃空間Ω內(nèi),即所有飛出此區(qū)域的巡航導彈都無法完成任務。

證明以S點為原點,SE連線為橫軸建立坐標系,則S的坐標為(0,0),E的坐標為(LSE,0).若存在航路點Pi(xi,yi)?Ω,則航路總長L滿足:

假設巡航導彈在攻擊過程中會持續(xù)向目標點方向飛行,不存在迂回的反方向飛行,同時由于巡航導彈依次序經(jīng)過n個中間航路點,因此中間航路點的分布也是從發(fā)射點開始,依次由近及遠分布。如圖2所示,用n條垂線(圖中垂直虛線段)將SE之間的連線n+1等分,則第i個航路點Pi的搜索區(qū)域就被限定在圖中以第i條垂線為中心線的陰影部分區(qū)域中,其中陰影部分長方形的長和寬分別為

圖2 航路點分布范圍Fig.2 Distributing area of waypoint

巡航導彈航路規(guī)劃需要地形信息的支持,由于實際地形極不規(guī)則,難以用數(shù)學模型精確描述,地形數(shù)據(jù)庫能夠提供的地形數(shù)據(jù)都是以柵格形式存儲的。而在實際規(guī)劃過程中,可能用到規(guī)劃區(qū)域中任意一點的高層數(shù)據(jù),這就需要通過對已知數(shù)據(jù)進行插值來獲取不在柵格上的位置的高度數(shù)據(jù)。設z(x,y)為柵格化的高層數(shù)據(jù),插值獲得的航路點Pi(xi,yi,hi)處的高度為g(xi,yi),則航路點Pi的絕對高度zi為式中:hi為航路點的離地高度。

1.3 航路代價指標

航路代價指標的建立是巡航導彈航路規(guī)劃的基礎[14]。對于一條可行航路p=[S,P1,P2,…,Pn, E],其綜合航路代價J(p)由航程指標J1(p)、高度指標J2(p)和威脅指標J3(p)組成[13],即

式中:w1、w2和w3分別為航程指標、高度指標和威脅指標的權(quán)系數(shù)。

航程指標J1(p)為航路段長度的總和,即

式中‖·‖表示兩個航路點之間的歐式距離。

高度指標J2(p)為中間航路點高度的總和,即

巡航導彈的飛行速度一般較慢,一旦被敵方發(fā)現(xiàn)就很容易被攔截。為簡化計算,將戰(zhàn)場中的各種威脅源等效為圓形區(qū)域,采用{(x,y),R,K}來描述一個威脅區(qū)域,其中(x,y)為威脅區(qū)域中心坐標,R為威脅區(qū)域半徑,K為威脅等級。一般而言,航路離威脅源越近、被威脅區(qū)域覆蓋的長度越長,威脅也就越大,因而威脅指標J3(p)要使航路盡量遠離威脅源,使巡航導彈能夠在威脅較小的區(qū)域飛行。定義威脅指標J3(p)為所有航路段所受威脅的總和[15],即

式中:T(·)表示兩個航路點之間航路段的威脅值, T(·)的具體計算公式為

式中:Kj表示第j個威脅源的威脅等級;Rj為第j個威脅源的威脅半徑;dj為第j個威脅源到該航路段的距離;lj為該航路段被第j個威脅源覆蓋的長度。

2 巡航導彈航路規(guī)劃方法

按照前文描述,巡航導彈航路規(guī)劃問題就轉(zhuǎn)化為如何優(yōu)化規(guī)劃空間中的n個中間航路點的坐標,使航路代價指標J(p)最小的問題。

2.1 航路編碼

航路編碼就是在染色體和實際航路間建立映射

式中:[qi,1,…,qi,n]和[qi,n+1,…,qi,2n]分別對應于n個中間航路點在水平面內(nèi)的橫坐標值x和縱坐標值y;[qi,2n+1,…,qi,3n]為n個中間航路點的離地高度h;θi,j為第i個染色體的第j個量子位對應的相位角,θi,j∈[-π/2,π/2].

2.2 適應度函數(shù)

適應度函數(shù)用于計算種群中染色體,即備選航路的適應度值,以判斷備選航路的優(yōu)劣并通過量子門旋轉(zhuǎn)引導整個群體向最優(yōu)航路逼近。適應度函數(shù)是航路染色體的優(yōu)勢函數(shù),航路代價指標越小,則表示該航路的染色體就越適應環(huán)境,其適應度就越高;反之,航路代價指標越大,則表示該航路的染色體越不適應環(huán)境,其適應度就越低。本文選擇航路代價的倒數(shù)作為適應度函數(shù):

式中:f(Qi)為染色體Qi的適應度函數(shù);F(pi)為染色體Qi所表示航路pi的代價。

由于種群采用隨機初始化,種群中既有可行航路,又有不可行航路。若pi為可行航路,其綜合代價可根據(jù)1.3節(jié)中的方法計算,即

若pi為不可行航路,其航路代價中除航程代價、高度代價和威脅代價外,還應加上約束違背量,則其綜合代價為

式中vi為約束違背參數(shù),取值為違背約束條件的個數(shù)。

2.3 量子位觀測

在IQEA中,相位角不再表示一個確定的角度值,而是通過觀測操作以一定的概率表現(xiàn)為區(qū)間[-π/2,π/2]上的所有角度值,那么所有相位角映射到解空間后,由于量子位的疊加態(tài)特性,種群中的染色體Qi表示的也就不是一條確定的航路,而是能夠以一定概率表示規(guī)劃空間中的所有航路。經(jīng)過觀關(guān)系,即用染色體表示規(guī)劃空間中的備選航路。設初始種群Q={Q1,Q2,…,Qm},其中m為種群規(guī)模。對于單枚巡航導彈的離線航路規(guī)劃而言,其發(fā)射點和目標點是固定的,因此只需要對n個中間航路點進行編碼。本文中每個航路點的空間位置信息由水平坐標(x,y)和離地高度h描述,則采用定長實數(shù)編碼的備選航路Qi(i=1,2,…,m)的染色體結(jié)構(gòu)為測操作,相位角θi,j的觀測值O(θi,j)為

式中:rando是[0,1]間的均勻隨機數(shù);PO是[0,1]間的常數(shù),稱為觀測概率;ri,j為滿足一定分布條件的隨機數(shù),使得O(θi,j)在相位角空間的分布與O(θi,j)和θi,j之間的距離呈反比,越遠離θi,j,概率越小。

隨機數(shù)ri,j集中體現(xiàn)了量子算法的概率表達特性,決定觀測后染色體在搜索空間的分布,因此選擇合適的分布函數(shù)至關(guān)重要。本文分別選擇正態(tài)分布、指數(shù)分布和柯西分布進行研究,不同的分布函數(shù)將產(chǎn)生不同的IQEA.

服從正態(tài)分布的隨機數(shù)的概率密度函數(shù)為

服從指數(shù)分布的隨機數(shù)為

式中:rand1為[-1,1]上均勻分布隨機數(shù);rand2服從參數(shù)為γ的指數(shù)分布,其概率密度函數(shù)為

2.4 染色體繁殖機制

為了進一步豐富算法的種群多樣性,增強算法跳出局部最優(yōu)解的能力,提高全局尋優(yōu)能力、穩(wěn)定性和可靠性,文中在IQEA里引入繁殖機制。在遺傳算法中,繁殖就是對父代種群進行交叉、變異和選擇操作形成子代種群的過程[16]。其中交叉操作通過隨機選擇兩個或多個父代染色體生成新的染色體;變異操作通過隨機改變父代染色體的基因值生成新染色體;而選擇操作則基于一定的規(guī)則對種群中的染色體進行優(yōu)勝劣汰,保證種群的數(shù)量和質(zhì)量。

在本文中,交叉算子以概率Px按照以下步驟生成新染色體:1)在父代種群中隨機選擇兩個不同的染色體Qr1和Qr2,r1≠r2;2)新染色體Qm+i定義為Qr1和Qr2的隨機加權(quán)和,即

式中:υ為柯西分布的參數(shù)。

種群中的染色體Qi經(jīng)過觀測,產(chǎn)生了一個新的染色體O(Qi),這兩個染色體中只有一個能夠保留。IQEA采用的是一種“貪婪”的操作,只有當染色體O(Qi)的適應度f(O(Qi))高于原有染色體Qi的適應度f(Qi)時,O(Qi)才會被保留,即

式中:j=1,2,…,sm,sm為變異產(chǎn)生新染色體的數(shù)量;ζj為[0,1]間的均勻隨機數(shù)。

經(jīng)過交叉和變異操作,種群中共有m+sx+sm個染色體,選擇操作的主要目標就是在保持種群良好多樣性的同時,保留種群中的優(yōu)良個體并保持種群規(guī)模。結(jié)合(μ+,λ)選擇和隨機選擇[16],在產(chǎn)生sx+sm個新染色體后,對所有染色體進行適應度排序,首先保留適應度最高的τm(0≤τ≤1)個染色體,而余下的(1-τ)m個染色體則從剩余的適應度較低的(1-τ)m+sx+sm個染色體中隨機選擇。

2.5 動態(tài)量子門

染色體進化是QEA搜索的核心,是種群提高適應度的關(guān)鍵手段,QEA通過量子門旋轉(zhuǎn)策略,可使種群最終收斂到最優(yōu)解。由于量子門旋轉(zhuǎn)的實質(zhì)就是改變量子位的相位角,因此旋轉(zhuǎn)門對量子位的操作就可以通過相位角的加減實現(xiàn)。在IQEA中,對于t代種群中的染色體Qi(t),經(jīng)過動態(tài)量子門旋轉(zhuǎn),其t+1代染色體Qi(t+1)的第j個量子位的相位角為

式中:Γθi,j(t)為量子門旋轉(zhuǎn)的轉(zhuǎn)角;θb,j(t)為t代最優(yōu)染色體的第j個量子位的相位角。

量子門旋轉(zhuǎn)角極大地影響算法的搜索效率和精度。在搜索初期,算法需要較大的旋轉(zhuǎn)角以粗粒度探索未知空間;而在搜索后期,隨著解的質(zhì)量的提升,算法需要逐步減小旋轉(zhuǎn)角以細粒度搜索當前空間。本文使用動態(tài)旋轉(zhuǎn)角代替固定旋轉(zhuǎn)角,在算法迭代過程中動態(tài)調(diào)整旋轉(zhuǎn)角。對于染色體Qi(t),其動態(tài)旋轉(zhuǎn)角為

式中:i=1,2,…,sx,sx為交叉產(chǎn)生新染色體的數(shù)量; ζ為[0,1]間的均勻隨機數(shù)。

變異操作的目標是在種群中引入新的基因,提高種群多樣性。一般情況下,為了不破壞種群的質(zhì)量,變異概率通常較低。作為一種次要的新染色體生成方法,變異操作以概率Pm采用完全隨機初始化的方法產(chǎn)生一個新的染色體加入到種群中,即

式中:Γθ0為初始旋轉(zhuǎn)角;λ為調(diào)整轉(zhuǎn)角變化率的正常數(shù);NCmax為最大迭代次數(shù)。

2.6 算法步驟

基于IQEA的巡航導彈航路規(guī)劃算法步驟為:

步驟1仿真參數(shù)初始化;

步驟2t=0,按照攻擊進入角約束初始化種群;

步驟3執(zhí)行交叉操作,得到sx個新航路染色體;

步驟4執(zhí)行變異操作,得到sm個新航路染色體;

步驟5計算m+sx+sm個染色體的適應度,執(zhí)行選擇操作獲得m個染色體;

步驟6觀測染色體Qi(t),確定染色體O(Qi);

步驟7計算O(Qi)的適應度,保留Qi(t)和O(Qi)中適應度較高染色體;

步驟8執(zhí)行動態(tài)量子門旋轉(zhuǎn)操作;

步驟9t=t+1,終止條件判斷;若滿足,輸出最優(yōu)航路,算法結(jié)束;否則轉(zhuǎn)到步驟3.

3 仿真實例

為驗證基于IQEA的巡航導彈航路規(guī)劃算法的有效性和優(yōu)越性,在Pentium Dual 2.2 GHz,2 G內(nèi)存的PC上分別進行基于遺傳算法(GA)、粒子群優(yōu)化(PSO)算法、微分進化算法(DEA)、實數(shù)編碼量子進化算法(RQEA)和IQEA的巡航導彈航路規(guī)劃仿真,操作系統(tǒng)為Windows XP,編程環(huán)境為Matlab2010b.仿真中地形為計算機模擬產(chǎn)生的500 km×500 km的方形區(qū)域,威脅為模擬生成的圓形區(qū)域。對所有的仿真實驗,均采用以下參數(shù):

1)中間航路點為15個,最大迭代次數(shù)為500;

2)代價函數(shù)中系數(shù)均取為1/3;

3)安全飛行離地高度區(qū)間為[50 m,300 m];

4)最大拐彎角為60°,最大爬升/俯沖角為30°;

5)有效射程為800 km;最小直飛距離20 km;

6)設置戰(zhàn)場環(huán)境數(shù)據(jù)如表1所示;

7)不同算法的參數(shù)設置如下:采用GA,交叉概率為0.5,變異概率為0.1;采用PSO算法,慣性權(quán)重為0.729,加速常數(shù)為1.494;采用DEA,放縮因子為0.5,交叉常量為0.9;采用RQEA,Γθ0=15°,λ=6,無量子位概率表達;采用IQEA,PO=0.1,Γθ0=15°, λ=6,其中:IQEA1、IQEA2和IQEA3均不帶繁殖機制,分別采用γ=0.3的雙指數(shù)分布、σ=0.5的正態(tài)分布和υ=0.2的柯西分布;IQEA4帶繁殖機制,交叉概率為0.9,變異概率為0.1,采用υ=0.2的柯西分布進行量子位觀測。

表1 威脅信息Tab.1 Information of threats

種群規(guī)模取30,8種算法分別對表1中的戰(zhàn)場環(huán)境運行30次仿真實驗,分別記錄每次仿真的最優(yōu)航路代價、生成可行航路的次數(shù)、生成可行航路的迭代次數(shù)(未生成則記為800)和仿真總時間,并求取仿真結(jié)果中的最優(yōu)代價、最劣代價、平均值和標準差等相關(guān)統(tǒng)計量,如表2所示。

表2 仿真結(jié)果Tab.2 Simulation results

通過對比表2中的數(shù)據(jù)不難發(fā)現(xiàn),IQEA的綜合性能優(yōu)于其他4種算法:1)GA在每次實驗中都能夠很快搜索到可行航路,且由于仿真中給不可行航路以極大的懲罰值,使得GA搜索出來的航路平均代價值最小,但是算法的整體尋優(yōu)能力極差,搜索到的航路代價較大,所有航路幾乎都無法滿足巡航導彈對安全性的要求,不適用于復雜環(huán)境中遠程巡航導彈的航路規(guī)劃問題的求解;2)PSO、DEA和RQEA僅能夠在50%左右的實驗中搜索到可行航路,與之相比,4種IQEA均能保證80%以上的概率生成可行航路,具有較高的算法穩(wěn)定性;3)IQEA的最優(yōu)代價、平均代價和標準差均小于PSO、DEA和RQEA,表明IQEA能夠更加穩(wěn)定地找到代價更小的航路,具有較強的尋優(yōu)能力;4)與PSO、DEA和RQEA相比,IQEA均能很快搜索到可行航路,所需迭代次數(shù)大幅減少,具有較快的收斂速度。

對比IQEA1～IQEA3的數(shù)據(jù)和收斂曲線(見圖3)可以看出,IQEA3性能最優(yōu),IQEA2次之,而IQEA1較差,其主要原因在于3種算法中量子位觀測值的分布特性的差異?？挛鞣植驾^廣闊的尾部使得IQEA3的觀測過程中,有更大可能獲得更多、更加優(yōu)秀的解;而雙指數(shù)分布的分布特性使得觀測過程中個體過于集中在當前解附近,在觀測過程中獲得較優(yōu)個體的可能性較小。因此在多次航路規(guī)劃過程中,IQEA3所規(guī)劃航路的代價相對較小,且收斂速度快,規(guī)劃時間也較少。IQEA4中的繁殖機制大大豐富了種群的多樣性,增強了算法跳出局部最優(yōu)的能力,提高了算法生成可行航路的概率和可靠性,大幅提高了航路規(guī)劃算法的性能:1)從30次實驗中搜索的航路平均代價可以看出,IQEA4在平均意義上能夠搜索出代價更小的航路,具有極強的全局尋優(yōu)能力;2)IQEA4搜索出的航路代價的標準差極小,算法的穩(wěn)定性很高;3)IQEA4搜索出可行航路的迭代次數(shù)大幅減少,生成可行航路平均僅需1.802 8 s,比IQEA3減少了70%以上,且在同樣條件下能夠搜索出代價更低的航路,算法收斂速度更快。

圖3 算法收斂曲線Fig.3 Convergences of fitness

圖3顯示的是算法收斂曲線,描述了30次仿真實驗的平均適應度的變化趨勢。由于實驗中適應度定義為代價值的倒數(shù),平均適應度實際上是每次實驗獲得的最優(yōu)航路代價值的倒數(shù)的平均值。從圖3中可以看出,IQEA4的收斂曲線位于圖像最上方,說明算法具有更快的收斂速度。

為了比較不同算法規(guī)劃航路的優(yōu)劣,表3列出了8種算法在30次仿真實驗中搜索到的最優(yōu)航路的航程;圖4顯示了最優(yōu)航路的水平投影,圖4(a)中分別為GA、PSO、DEA和RQEA規(guī)劃出的最優(yōu)航路,圖4(b)為本文提出的IQEA規(guī)劃出的最優(yōu)航路,圖4中虛線圓代表模擬的威脅區(qū)域?；贕A和PSO的航路均穿過了威脅區(qū)域,未能有效規(guī)避威脅,且航路轉(zhuǎn)彎較多;基于DEA和RQEA的航路均成功實現(xiàn)了威脅規(guī)避,且航路相對平滑,但航路航程較長,說明這4種算法未能實現(xiàn)航路的優(yōu)選,均不同程度地陷入了局部最優(yōu)。與之相比,基于IQEA的最優(yōu)航路均成功實現(xiàn)了威脅規(guī)避、航路更為平滑且總航程較小。

表3 最優(yōu)航路航程Tab.3 Lengths of optimal paths

圖4 最優(yōu)航路的水平投影Fig.4 Horizontal projections of optimal paths

圖5 最優(yōu)航路三維顯示及其剖面圖Fig.5 3D view and cutaway view of optimal paths

圖5分別為8種算法搜索的最優(yōu)航路的三維顯示和剖面圖,其中剖面圖中橫軸為航路點與發(fā)射點之間沿旋轉(zhuǎn)坐標系橫軸的相對距離,縱軸為絕對高度值,曲線代表航路點高度,陰影部分則表示地面高度。從圖5中可以看出,基于IQEA的最優(yōu)航路能夠有效利用地形進行遮蔽,在保持安全離地高度的條件下能夠盡量降低離地飛行高度,能夠更好地進行地形回避和地形跟隨。

4 結(jié)論

巡航導彈航路規(guī)劃是一個復雜的多約束多目標非線性優(yōu)化問題,由于巡航導彈射程遠、作戰(zhàn)區(qū)域廣闊,規(guī)劃出一條可行航路需要很長的時間和極大內(nèi)存。本文針對單枚巡航導彈的航路規(guī)劃問題,確定了航路搜索的規(guī)劃空間,建立了航路評價的代價指標;在實數(shù)編碼QEA中引入了染色體概率表達特性,充分利用相位角編碼和量子染色體概率表達特性的優(yōu)點,使得每一條染色體均能以一定概率表達優(yōu)化問題的所有可行解,克服傳統(tǒng)的二進制量子比特編碼在求解數(shù)值優(yōu)化問題時編碼效率低下、求解精度低的缺點;借鑒GA的進化思想,在IQEA中引入交叉和變異算子,增強算法跳出局部最優(yōu)解的能力,提高算法搜索的穩(wěn)定性和可靠性,同時采用自適應變步長量子門實現(xiàn)量子門旋轉(zhuǎn)角的動態(tài)變化,有效保證種群的多樣性和進化的方向性。仿真結(jié)果表明,基于IQEA的巡航導彈航路規(guī)劃方法能夠更加穩(wěn)定、快速地搜索到代價更低的航路,規(guī)劃航路能夠有效利用地形遮蔽,并實現(xiàn)威脅規(guī)避、地形回避和地形跟隨。

References)

[1] Helgason R V,Kennington J L,Lewis K R.Cruise missile mission planning:a heuristic algorithm for automatic path generation[J]. Journal of Heuristics,2001,7(5):473-494.

[2] Narayanan A,Moore M.Quantum-inspired genetic algorithms[C]∥Proceedings of 1996 IEEE International Conference on Evolutionary Computation.Nogaya,Japan:IEEE,1996:61-66.

[3] Han K H,Kim J H.Quantum-inspired evolutionary algorithm for a class of combinatorial optimization[J].IEEE Transactions on Evolutionary Computation,2002,6(6):580-593.

[4] Han K H,Kim J H.Quantum-inspired evolutionary algorithms with a new termination criterion,HεGate,and two-phase scheme[J]. IEEE Transactions on Evolutionary Computation,2004,8(2): 156-169.

[5] Kim Y,Kim J H,Han K H.Quantum-inspired multi objective evolutionary algorithm for multiobjective 0/1 knapsack problems[C]∥IEEE Congress on Evolutionary Computation.Vancouver,Canada: IEEE,2006:2601-2606.

[6] 劉鋼,老松楊,譚東風,等.反艦導彈航路規(guī)劃問題的研究現(xiàn)狀與進展[J].自動化學報,2013,39(4):347-359.

LIU Gang,LAO Song-yang,TAN Dong-feng,et al.Research status and progress on anti-ship missile path planning[J].Acta Automatica Sinica,2013,39(4):347-359.(in Chinese)

[7] 孫陽光,丁明躍,周成平,等.基于量子遺傳算法的無人飛行器航跡規(guī)劃[J].宇航學報,2010,31(3):648-654.

SUN Yang-guang,DING Ming-yue,ZHOU Cheng-ping,et al. Route planning based on quantum genetic algorithm for UAVs[J]. Journal of Astronautics,2010,31(3):648-654.(in Chinese)

[8] 何兵,劉剛,趙鵬濤,等.基于改進量子遺傳法的巡航導彈水平航跡規(guī)劃[J].計算機仿真,2012,29(9):109-112

HE Bing,LIU Gang,ZHAO Peng-tao,et al.Horizontal route planning of cruise missile based on the improved quantum genetic algorithm[J].Computer Simulation,2012,29(9):109-112. (in Chinese)

[9] Zhao S F,Xu G H,Tao T F,et al.Real-coded chaotic quantuminspired genetic algorithm for training of fuzzy neural networks[J]. Computers and mathematics with Applications,2009,57(11/ 12):2009-2015.

[10] 高輝,徐光輝,張銳,等.實數(shù)編碼量子進化算法[J].控制與決策,2008,23(1):87-90.

GAO Hui,XU Guang-hui,ZHANG Rui,et al.Real coded quantum evolutionary algorithm[J].Control and Decision, 2008,23(1):87-90.(in Chinese)

[11] 高輝,張銳.改進實數(shù)編碼量子進化算法及其在參數(shù)估計中的應用[J].控制與決策,2011,26(3):418-422.

GAO Hui,ZHANG Rui.Improved real-coded quantum evolutionary algorithms and its application on parameter estimation[J].Control and Decision,2011,26(3):418-422.(in Chinese)

[12] Li P,Li S.Quantum-inspired evolutionary algorithm for continuous space optimization based on Bloch coordinates of qubits[J]. Neurocomputing,2008,72(1/2/3):581-591

[13] 丁明躍,鄭昌文,周成平,等.無人飛行器航跡規(guī)劃[M].北京:電子工業(yè)出版社,2009:110-119.

DING Ming-yue,ZHENG Chang-wen,ZHOU Cheng-ping,et al. Route planning for unmanned aerial vehicles[M].Beijing:Publishing House of Electronics Industry,2009:110-119.(in Chinese)

[14] 謝曉方,孫濤,歐陽中輝.反艦導彈航路規(guī)劃技術(shù)[M].北京:國防工業(yè)出版社,2010:23-30.

XIE Xiao-fang,SUN Tao,OUYANG Zhong-hui.Path planning for anti-ship missile[M].Beijing:National Defense Industry Press,2010:23-30.(in Chinese)

[15] 蘇菲,彭輝,沈林成.基于協(xié)進化多子群蟻群算法的多無人作戰(zhàn)飛機協(xié)同航跡規(guī)劃研究[J].兵工學報,2009,30(11): 1562-1568

SU Fei,PENG Hui,SHEN Lin-cheng.Research on multi-UCAV cooperative route planning based on coevolutionary multi-ant-colony algorithm[J].Acta Armamentarii,2009,30(11):1562-1568.(in Chinese)

[16] Andries P E.計算群體智能基礎[M].譚營,譯。北京:清華大學出版社,2009:112-134.

Andries P E.Fundamentals of computational swarm intelligence [M].Tan Ying,translated.Beijing:Tsinghua University Press, 2009:112-134.(in Chinese)

Cruise Missile Path Planning Based on Improved Quantum Evolutionary Algorithm

ZHANG Lei,FANG Yang-wang,CHAI Dong,YONG Xiao-ju
(School of Aeronautics and Astronautics,Air Force Engineering University,Xi'an 710038,Shaanxi,China)

For the low efficiency of cruise missile path planning,a novel path planning algorithm is proposed based on improved quantum evolutionary algorithm(IQEA).The search space is constructed based on path constraints,and the criteria of path estimation are presented.Probabilistic representation quantum chromosome is introduced to represent all the feasible solutions probabilistically to solve the premature problem.The genetic algorithm is used for reference,and the breeding strategy is introduced to IQEA.The dynamic quantum rotation gate is used to update the chromosomes to realize a good balance between local and global searches.Simulation results show that IQEA with breeding strategy can generate flight path with lower cost rapidly and steadily.

operation research;cruise missile;path planning;improved quantum evolutionary algorithm

V249.1

A

1000-1093(2014)11-1820-08

10.3969/j.issn.1000-1093.2014.11.013

2013-12-13

張磊(1985—),男,博士研究生。E-mail:szl1985@163.com;

方洋旺(1966—),男,教授,博士生導師。E-mail:ywfang2008@sohu.com