基于文化-禁忌搜索算法的巡飛彈航跡規(guī)劃*

黃雨楊,郝 峰

(西安現(xiàn)代控制技術(shù)研究所, 西安 710065)

0 引言

隨著技術(shù)的發(fā)展,以巡飛彈、無人機(jī)等為主的無人飛行器的集群作戰(zhàn),成為了現(xiàn)代戰(zhàn)爭(zhēng)的一種重要形式,而巡飛彈的航跡規(guī)劃則是其集群作戰(zhàn)任務(wù)規(guī)劃的一個(gè)重點(diǎn)。航跡規(guī)劃是一個(gè)NP-hard問題,需要良好的算法保證規(guī)劃的完備性和高效性。近年來,國內(nèi)外的研究以航跡規(guī)劃為目標(biāo)設(shè)計(jì)了多種算法,例如,步長可變的稀疏A*算法[1],自適應(yīng)學(xué)習(xí)粒子群算法[2],遺傳算法與蟻群算法的組合算法[3],結(jié)合Voronoi圖的遺傳算法[4],基于文化算法的改進(jìn)算法[5-6],以及新出現(xiàn)的以灰狼算法[7]、蝗蟲算法[8]為例的仿生算法等。

文中設(shè)計(jì)了基于文化算法與禁忌搜索算法的組合算法,并加入變異機(jī)制和Boids模型分離機(jī)制。同時(shí),通過作戰(zhàn)環(huán)境和任務(wù)的建模,對(duì)算法進(jìn)行航跡規(guī)劃仿真,并與其它算法相比較,驗(yàn)證了本算法全局搜索速度和局部搜索能力的改善。

1 算法簡述

1.1 文化算法

文化算法(culture algorithm,CA)的概念由Reynolds于1994年引入[9],算法模擬對(duì)象為以人類為例的高等動(dòng)物種群進(jìn)化過程。搜索空間由信仰空間和種群本身組成,種群的進(jìn)化受到信仰空間的指導(dǎo),而種群的進(jìn)化結(jié)果也會(huì)影響信仰空間,幫助信仰空間完成更新。兩個(gè)空間互相影響進(jìn)化,從而可以得到先進(jìn)的個(gè)體。算法兩層空間分別以不同的速度進(jìn)行更新,且相互影響,對(duì)于解決復(fù)雜的優(yōu)化問題具有明顯的優(yōu)勢(shì)。通過改變文化知識(shí)的更新方式、種群受知識(shí)的影響速度、兩層空間之間信息的傳播方式等途徑,可以對(duì)文化算法進(jìn)行優(yōu)化[10-11]。

1.2 禁忌搜索算法

禁忌搜索算法(tabu search,TS)是一種現(xiàn)代啟發(fā)式算法[12],是對(duì)人類智能記憶機(jī)制的模擬,通過禁忌表和特赦準(zhǔn)則控制搜索空間。該算法全局搜索能力強(qiáng),能有效防止陷入局部最優(yōu)的問題,但其本身依賴初始解的選取,不良的初始解會(huì)大幅增加搜索時(shí)間。近年來的算法研究設(shè)計(jì)中,通常將禁忌搜索算法與其余仿生算法結(jié)合成組合算法,提高算法的搜索效率[13]。

2 航跡規(guī)劃問題建模

2.1 環(huán)境模型及代價(jià)函數(shù)

巡飛彈執(zhí)行任務(wù)時(shí)受到的環(huán)境威脅,主要分為地形威脅和敵方防備威脅。構(gòu)造多個(gè)二元指數(shù)函數(shù),可以分別建立山峰、坡地、谷地模型,求和后即為整體地圖模型。考慮到實(shí)際地形的起伏性,在地形上添加小幅白噪聲函數(shù),使之更接近真實(shí)情況。

敵方防備威脅主要有雷達(dá)威脅與防空導(dǎo)彈威脅。分別記兩種威脅概率為Pradar和Pmissile,記雷達(dá)在半徑R1內(nèi)探測(cè)概率固定,且最大探測(cè)半徑為R2;記導(dǎo)彈殺傷概率為Rkill,最大探測(cè)半徑為Rmax,則有相應(yīng)模型為:

得到各威脅概率后,即可得到全地圖威脅模型,建立代價(jià)函數(shù)。本模型構(gòu)建的航跡代價(jià)受航跡長度、威脅概率以及爬升高度影響,具體為C=∑[w1f1(li)+w2f2(pi)+w3f3(hi)]。式中f1(li)、f2(pi)、f3(hi)分別為基于航跡長度、威脅概率、爬升高度計(jì)算得到的代價(jià)函數(shù),分別乘以權(quán)重后得到總航跡代價(jià)。

2.2 巡飛彈約束條件

巡飛彈的航跡需要滿足如下約束條件:

1)最大轉(zhuǎn)彎角:巡飛彈轉(zhuǎn)彎時(shí),轉(zhuǎn)彎角不能超過規(guī)定值；

2)最大爬升/俯沖角:巡飛彈在上升和下降時(shí)爬升/俯沖角不能超過規(guī)定值；

3)最小直飛距離:巡飛彈在任意航跡段中保持直線飛行狀態(tài),到端點(diǎn)附近開始轉(zhuǎn)彎，而巡飛彈不能一直保持轉(zhuǎn)彎狀態(tài),需在轉(zhuǎn)彎后直線飛行一定距離；

4)最大航跡距離:由于燃料有限,巡飛彈的航跡總長有最大距離限制；

5)最小飛行高度:巡飛彈飛行過程中,需要保持距離地面一定的高度；

6)到達(dá)目標(biāo)方向角:巡飛彈到達(dá)目標(biāo)時(shí)存在方向角約束,即末端航跡的方向角需在一定范圍內(nèi)。

2.3 搜索空間建模

根據(jù)地圖和威脅模型,可對(duì)搜索空間進(jìn)行建模。設(shè)定一個(gè)威脅概率上限p,高于這一概率的區(qū)域視為禁飛區(qū)。確定禁飛區(qū)后,在地圖中將其對(duì)應(yīng)高度修改,使高度明顯大于其余區(qū)域。根據(jù)代價(jià)函數(shù)和威脅模型,不難得出,在同一水平位置,當(dāng)巡飛彈保持較低高度飛行時(shí),無論是防空導(dǎo)彈威脅概率還是爬升高度代價(jià)都相對(duì)較低,所以,為了簡化搜索空間,降低搜索耗時(shí),可以將三維空間轉(zhuǎn)化為二維的最小威脅曲面[14],在曲面上進(jìn)行搜索規(guī)劃,提高搜索效率的同時(shí),保證盡可能低的路徑代價(jià)。曲面建立規(guī)則如下:

1)根據(jù)最小飛行高度及地圖各點(diǎn)海拔,確定各點(diǎn)的最低高度。

2)剔除禁飛區(qū),設(shè)置禁飛區(qū)內(nèi)點(diǎn)的曲面高度為-5 000 m，并記錄,以便區(qū)分。

3)針對(duì)山峰模型,考慮到峰頂高度較高,在爬升角受限的情況下會(huì)拔高整個(gè)地圖,從而導(dǎo)致代價(jià)和威脅概率明顯提高。因此,將山峰處坡度較大點(diǎn)所包圍的山峰部分設(shè)置為禁飛區(qū),進(jìn)行剔除并記錄。

4)從所有可飛點(diǎn)中選取最高點(diǎn),根據(jù)最大爬升/俯沖角約束提升其周圍所有可飛點(diǎn)對(duì)應(yīng)曲面高度,然后再以這些擴(kuò)展點(diǎn)為中心,進(jìn)一步提升外側(cè)可飛點(diǎn)對(duì)應(yīng)曲面高度,直至更新所有點(diǎn)高度,以保證各點(diǎn)之間的路徑可飛,從而完成最小威脅曲面的構(gòu)建。

3 算法設(shè)計(jì)與實(shí)現(xiàn)

3.1 航跡編碼及迭代方法

本次規(guī)劃設(shè)定起始點(diǎn)坐標(biāo)為(50 m,50 m),目標(biāo)點(diǎn)坐標(biāo)為(10 000 m,10 000 m),最小直飛距離為200 m?？紤]到只在最小威脅曲面上搜索,故每條航跡的編碼均為行數(shù)為2的矩陣,每一列代表對(duì)應(yīng)航跡點(diǎn)的坐標(biāo)。定義基礎(chǔ)航跡為:

生成新航跡的操作為將兩條可飛航跡的水平面坐標(biāo)按隨機(jī)比例組合,所得結(jié)果為水平坐標(biāo)編碼,可保證航跡同樣位于最小威脅曲面上。因此,只需要檢測(cè)新航跡是否滿足轉(zhuǎn)彎角約束和禁飛區(qū)限制,即可判斷其可飛性。

3.2 Boids模型分離機(jī)制

使用文化算法需要防止子代過于接近,因此,采用Boids鳥群模型中的分離機(jī)制,即鳥群個(gè)體間距離過近時(shí),會(huì)選擇分離,防止碰撞[15]。分離機(jī)制具體表現(xiàn)為,若子代集中為一個(gè)解或全部存在于禁忌表中,則對(duì)種群進(jìn)行分離操作,將規(guī)范知識(shí)恢復(fù)為初態(tài),保留種群1/10的染色體,隨機(jī)生成剩余染色體,得到新的種群;同時(shí),在單次迭代中提高變異概率,以加強(qiáng)全局搜索。這一方法能有效防止解過于集中導(dǎo)致后續(xù)搜索失去意義,同時(shí)分離機(jī)制也能提高“爬山”能力,跳出局部最優(yōu)解。

3.3 算法步驟設(shè)計(jì)

為了提高后期的局部搜索能力,引入變異機(jī)制,具體為采用生成初始航跡種群的規(guī)則,在最小威脅曲面上,按照3.1的規(guī)則隨機(jī)改變一部分的航跡點(diǎn)。

采用禁忌表對(duì)形勢(shì)知識(shí)的更新進(jìn)行限制,優(yōu)先將不屬于禁忌表的較優(yōu)航跡選作形勢(shì)知識(shí),利用形勢(shì)知識(shí)的改變來更改種群的進(jìn)化方向。同時(shí),按照3.2中的分離機(jī)制,建立知識(shí)的重置規(guī)則,加強(qiáng)算法跳出局部最優(yōu)解的能力。

算法具體步驟如下:

1)設(shè)置各項(xiàng)參數(shù),按3.1的規(guī)則生成初始種群。分離標(biāo)志初態(tài)為0。

2)沿兩側(cè)邊界得到兩條航跡,作為規(guī)范知識(shí)。對(duì)初始種群按可飛性分類,分別選取最優(yōu)航跡。若最優(yōu)可飛航跡代價(jià)更小,則作為形勢(shì)知識(shí);反之,則按兩航跡代價(jià)占比,從兩者中隨機(jī)選擇一條航跡作為形勢(shì)知識(shí);若不存在可飛航跡,則選擇最優(yōu)不可飛航跡作為形勢(shì)知識(shí)。若存在可飛航跡,選取最優(yōu)可飛航跡為初始最優(yōu)解。

3)若分離標(biāo)志為1,則按3.2所述分離機(jī)制進(jìn)行分離操作。重置規(guī)范知識(shí),保留當(dāng)前種群最優(yōu)的1/10,其余染色體按照3.1的初始航跡種群生成規(guī)則重置。

4)根據(jù)信仰空間及變異機(jī)制產(chǎn)生子代,并計(jì)算其代價(jià)及可飛性。

5)按代價(jià)對(duì)兩代航跡進(jìn)行排序,隨后確定新種群。優(yōu)先選取可飛且代價(jià)較小的航跡,其余航跡以可飛性劃分,按比例分別選取相對(duì)較優(yōu)的航跡。

6)按接受概率及新的種群更新信仰空間,利用禁忌表限制形勢(shì)知識(shí)的選取。若種群中所有航跡均處于禁忌表中,則取代價(jià)最小的航跡作為形勢(shì)知識(shí),同時(shí)將分離標(biāo)志置為1;否則,按2)的規(guī)則選取航跡作為形勢(shì)知識(shí),同時(shí)將分離標(biāo)志置為0。

7)根據(jù)航跡代價(jià)選取最優(yōu)可飛航跡,與當(dāng)前最優(yōu)解比較,更新最優(yōu)解。

8)若迭代滿足終止條件,則輸出最優(yōu)解為最終規(guī)劃航跡;否則,返回步驟3)。

4 算法仿真

4.1 離線航跡規(guī)劃

仿真使用PC機(jī)處理器為Intel? Xeon? CPU E3-1230 v6 @ 3.50 GHz,在Matlab 2016a上進(jìn)行。在2.3中建立的搜索空間模型中進(jìn)行航跡規(guī)劃。設(shè)計(jì)仿真種群個(gè)體數(shù)為40,迭代次數(shù)為80,進(jìn)行仿真,得到航跡如圖1所示,搜索時(shí)間為15.61 s,航跡代價(jià)為15 946.21,長度為15 577.39 m,平均高度為254.22 m。實(shí)際上,在本模型中,從不同側(cè)繞過威脅區(qū)域,可得到若干個(gè)局部最優(yōu)解,而仿真可得其余所有局部最優(yōu)解的最小代價(jià)在16 400附近。故而本次規(guī)劃航跡與最優(yōu)解相近,并未陷入局部最優(yōu)解中。最優(yōu)解航跡代價(jià)與迭代次數(shù)關(guān)系如圖2所示。

圖1 規(guī)劃所得航跡

圖2 最優(yōu)航跡代價(jià)-迭代次數(shù)折線圖

可以看出,10次迭代內(nèi),搜索已迅速找到全局最優(yōu)解所在區(qū)域,此時(shí)搜索耗時(shí)在3 s以內(nèi),而在之后的搜索中,利用變異機(jī)制和分離機(jī)制能不斷得到代價(jià)更小的航跡。由此可見,改進(jìn)的文化-禁忌搜索算法在全局搜索和局部尋優(yōu)上效果良好。下文分別采用文化算法,帶變異的文化算法(culture algorithm with mutation,CAM),以及粒子群算法(particle swam optimization,PSO)在本模型上進(jìn)行航跡規(guī)劃。調(diào)整迭代次數(shù),使各算法消耗時(shí)間相近,各運(yùn)行100次,結(jié)果如表1所示。此外,使用步長固定的稀疏A*算法進(jìn)行規(guī)劃并比較。

表1 不同算法的航跡規(guī)劃結(jié)果

比較數(shù)據(jù)可看出,改進(jìn)的文化-禁忌搜索算法雖然每次迭代耗時(shí)略高,但由于全局搜索和局部搜索能力的明顯優(yōu)勢(shì),能在更小種群、更少迭代次數(shù)下,得到代價(jià)更小的航跡,同時(shí)還改善了其余算法可能陷入局部最優(yōu)解的缺點(diǎn)。此外,與步長固定的A*算法相比,本算法受網(wǎng)格化約束程度小。由此可見,本算法無論在航跡規(guī)劃,還是在其他復(fù)雜優(yōu)化問題中,都具有良好的性能。

4.2 實(shí)時(shí)航跡規(guī)劃

在先前的仿真中,采用改進(jìn)的文化-禁忌搜索算法可以在較短時(shí)間內(nèi)得到較理想的航跡,故可利用這一性能,減少迭代次數(shù),進(jìn)行實(shí)時(shí)航跡規(guī)劃。巡飛彈按離線規(guī)劃的航跡飛行,途中檢測(cè)到威脅區(qū)域變化,隨后預(yù)留一定的飛行時(shí)間(本次仿真設(shè)為5 s),以該時(shí)間后的下一個(gè)航跡點(diǎn)作為起點(diǎn),進(jìn)行航跡規(guī)劃,規(guī)避新的威脅。在不同的飛行時(shí)間將其中一個(gè)雷達(dá)威脅的中心由(7 500 m,5 000 m)移動(dòng)至(8 500 m,5 000 m),分別進(jìn)行實(shí)時(shí)航跡規(guī)劃,結(jié)果如圖3所示。兩次規(guī)劃分別耗時(shí)3.45 s、3.47 s,航跡可飛且代價(jià)較小,滿足要求。

圖3 實(shí)時(shí)規(guī)劃航跡

5 總結(jié)

文中將文化算法與禁忌搜索算法相結(jié)合,并加入變異機(jī)制,以及Boids鳥群模型的分離機(jī)制,對(duì)算法性能進(jìn)行了優(yōu)化,得到了改進(jìn)的文化-禁忌搜索算法。相比于其他各類算法,本算法能在短時(shí)間內(nèi)跳出局部最優(yōu),有助于快速規(guī)劃航跡;而當(dāng)規(guī)劃時(shí)間充足時(shí),迭代后期算法的局部尋優(yōu)能力良好。因此,本算法性能優(yōu)勢(shì)明顯,對(duì)于理論上和工程上的航跡規(guī)劃均有很大作用。