基于改進(jìn)量子進(jìn)化算法的巡航導(dǎo)彈航路規(guī)劃方法

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

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

基于改進(jìn)量子進(jìn)化算法的巡航導(dǎo)彈航路規(guī)劃方法

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

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

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

運(yùn)籌學(xué);巡航導(dǎo)彈;航路規(guī)劃;改進(jìn)量子進(jìn)化算法

0 引言

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

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

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

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

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

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

1.1 航路約束條件

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

1.2 規(guī)劃空間描述

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

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

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

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

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

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

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

圖2 航路點(diǎn)分布范圍Fig.2 Distributing area of waypoint

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

1.3 航路代價(jià)指標(biāo)

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

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

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

式中‖·‖表示兩個(gè)航路點(diǎn)之間的歐式距離。

高度指標(biāo)J2(p)為中間航路點(diǎn)高度的總和,即

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

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

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

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

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

2.1 航路編碼

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

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

2.2 適應(yīng)度函數(shù)

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

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

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

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

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

2.3 量子位觀測

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

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

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

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

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

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

2.4 染色體繁殖機(jī)制

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

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

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

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

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

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

2.5 動態(tài)量子門

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

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

量子門旋轉(zhuǎn)角極大地影響算法的搜索效率和精度。在搜索初期,算法需要較大的旋轉(zhuǎn)角以粗粒度探索未知空間;而在搜索后期,隨著解的質(zhì)量的提升,算法需要逐步減小旋轉(zhuǎn)角以細(xì)粒度搜索當(dāng)前空間。本文使用動態(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]間的均勻隨機(jī)數(shù)。

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

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

2.6 算法步驟

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

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

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

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

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

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

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

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

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

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

3 仿真實(shí)例

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

為了比較不同算法規(guī)劃航路的優(yōu)劣,表3列出了8種算法在30次仿真實(shí)驗(yàn)中搜索到的最優(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的航路均成功實(shí)現(xiàn)了威脅規(guī)避,且航路相對平滑,但航路航程較長,說明這4種算法未能實(shí)現(xiàn)航路的優(yōu)選,均不同程度地陷入了局部最優(yōu)。與之相比,基于IQEA的最優(yōu)航路均成功實(shí)現(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)航路的三維顯示和剖面圖,其中剖面圖中橫軸為航路點(diǎn)與發(fā)射點(diǎn)之間沿旋轉(zhuǎn)坐標(biāo)系橫軸的相對距離,縱軸為絕對高度值,曲線代表航路點(diǎn)高度,陰影部分則表示地面高度。從圖5中可以看出,基于IQEA的最優(yōu)航路能夠有效利用地形進(jìn)行遮蔽,在保持安全離地高度的條件下能夠盡量降低離地飛行高度,能夠更好地進(jìn)行地形回避和地形跟隨。

4 結(jié)論

巡航導(dǎo)彈航路規(guī)劃是一個(gè)復(fù)雜的多約束多目標(biāo)非線性優(yōu)化問題,由于巡航導(dǎo)彈射程遠(yuǎn)、作戰(zhàn)區(qū)域廣闊,規(guī)劃出一條可行航路需要很長的時(shí)間和極大內(nèi)存。本文針對單枚巡航導(dǎo)彈的航路規(guī)劃問題,確定了航路搜索的規(guī)劃空間,建立了航路評價(jià)的代價(jià)指標(biāo);在實(shí)數(shù)編碼QEA中引入了染色體概率表達(dá)特性,充分利用相位角編碼和量子染色體概率表達(dá)特性的優(yōu)點(diǎn),使得每一條染色體均能以一定概率表達(dá)優(yōu)化問題的所有可行解,克服傳統(tǒng)的二進(jìn)制量子比特編碼在求解數(shù)值優(yōu)化問題時(shí)編碼效率低下、求解精度低的缺點(diǎn);借鑒GA的進(jìn)化思想,在IQEA中引入交叉和變異算子,增強(qiáng)算法跳出局部最優(yōu)解的能力,提高算法搜索的穩(wěn)定性和可靠性,同時(shí)采用自適應(yīng)變步長量子門實(shí)現(xiàn)量子門旋轉(zhuǎn)角的動態(tài)變化,有效保證種群的多樣性和進(jìn)化的方向性。仿真結(jié)果表明,基于IQEA的巡航導(dǎo)彈航路規(guī)劃方法能夠更加穩(wěn)定、快速地搜索到代價(jià)更低的航路,規(guī)劃航路能夠有效利用地形遮蔽,并實(shí)現(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] 劉鋼,老松楊,譚東風(fēng),等.反艦導(dǎo)彈航路規(guī)劃問題的研究現(xiàn)狀與進(jìn)展[J].自動化學(xué)報(bào),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].宇航學(xué)報(bào),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] 何兵,劉剛,趙鵬濤,等.基于改進(jìn)量子遺傳法的巡航導(dǎo)彈水平航跡規(guī)劃[J].計(jì)算機(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í)數(shù)編碼量子進(jìn)化算法[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] 高輝,張銳.改進(jìn)實(shí)數(shù)編碼量子進(jìn)化算法及其在參數(shù)估計(jì)中的應(yīng)用[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] 謝曉方,孫濤,歐陽中輝.反艦導(dǎo)彈航路規(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é)進(jìn)化多子群蟻群算法的多無人作戰(zhàn)飛機(jī)協(xié)同航跡規(guī)劃研究[J].兵工學(xué)報(bào),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.計(jì)算群體智能基礎(chǔ)[M].譚營,譯。北京:清華大學(xué)出版社,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—),男,教授,博士生導(dǎo)師。E-mail:ywfang2008@sohu.com