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

黃雨楊,郝 峰

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

0 引言

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

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

1 算法簡述

1.1 文化算法

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

1.2 禁忌搜索算法

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

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

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

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

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

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

2.2 巡飛彈約束條件

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

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

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

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

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

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

6)到達目標方向角:巡飛彈到達目標時存在方向角約束,即末端航跡的方向角需在一定范圍內。

2.3 搜索空間建模

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

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

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

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

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

3 算法設計與實現(xiàn)

3.1 航跡編碼及迭代方法

本次規(guī)劃設定起始點坐標為(50 m,50 m),目標點坐標為(10 000 m,10 000 m),最小直飛距離為200 m。考慮到只在最小威脅曲面上搜索,故每條航跡的編碼均為行數(shù)為2的矩陣,每一列代表對應航跡點的坐標。定義基礎航跡為:

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

3.2 Boids模型分離機制

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

3.3 算法步驟設計

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

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

算法具體步驟如下:

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

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

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

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

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

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

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

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

4 算法仿真

4.1 離線航跡規(guī)劃

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

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

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

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

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

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

4.2 實時航跡規(guī)劃

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

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

5 總結

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