限定搜索區(qū)域的分層遺傳算法無(wú)人機(jī)路徑規(guī)劃

王 景,李京華,倪 寧,武琳靜

(西北工業(yè)大學(xué)電子信息學(xué)院,陜西西安 710129)

0 引言

無(wú)人機(jī)路徑規(guī)劃是指在保證無(wú)人機(jī)自身存活的前提下,尋找滿足無(wú)人機(jī)性能約束及戰(zhàn)場(chǎng)環(huán)境限制的可行路徑[1]。通常無(wú)人機(jī)在執(zhí)行任務(wù)時(shí),機(jī)載自動(dòng)駕駛儀根據(jù)地面路徑規(guī)劃器預(yù)先生成的路徑,及時(shí)調(diào)整無(wú)人機(jī)飛行狀態(tài),使其始終按預(yù)設(shè)路徑飛行。因此一條安全航路,能使無(wú)人機(jī)有效地規(guī)避威脅、縮短航程,在提高無(wú)人機(jī)的生存能力、偵查效率以及遠(yuǎn)程打擊精確度等方面起了關(guān)鍵性的作用[2]。

路徑規(guī)劃問(wèn)題本質(zhì)上是一類大空間的非線性優(yōu)化問(wèn)題。自20世紀(jì)70年代以來(lái),隨著人工智能的發(fā)展,遺傳算法在解決大空間、非線性、全局尋優(yōu)等復(fù)雜問(wèn)題時(shí)有著傳統(tǒng)方法所不具備的獨(dú)特優(yōu)越性,開(kāi)始被廣泛地應(yīng)用于路徑規(guī)劃問(wèn)題的求解[3-6]。

針對(duì)路徑規(guī)劃問(wèn)題,國(guó)內(nèi)外學(xué)者做了大量的研究。Beard等人[7-8]通過(guò)構(gòu)造Voronoi圖對(duì)任務(wù)區(qū)域的威脅進(jìn)行劃分并得到待選路徑段,再通過(guò)Dijkstra算法求解無(wú)人機(jī)的最優(yōu)路徑,該算法的不足之處在于其將所有威脅設(shè)想為點(diǎn),而這種假設(shè)不能區(qū)分不同威脅的危險(xiǎn)程度。文獻(xiàn)[9]利用傳統(tǒng)遺傳算法在無(wú)人機(jī)任務(wù)區(qū)域內(nèi)進(jìn)行路徑規(guī)劃,由于傳統(tǒng)遺傳算法易陷入局部最優(yōu)解[10],并且該算法沒(méi)有對(duì)路徑規(guī)劃算法的搜索區(qū)域進(jìn)行限制,導(dǎo)致計(jì)算時(shí)間較長(zhǎng)而無(wú)法滿足實(shí)時(shí)性的要求。針對(duì)上述問(wèn)題,本文提出一種新的路徑規(guī)劃方法,限定搜索區(qū)域的分層遺傳算法無(wú)人機(jī)路徑規(guī)劃方法。

1 分層遺傳算法

遺傳算法的概念由Fraser教授于1957年首次提出,由Holland教授在其專著[11]中給出了遺傳算法系統(tǒng)的框架模型。經(jīng)過(guò)60多年的發(fā)展,已產(chǎn)生了若干改進(jìn)的遺傳算法。分層遺傳算法[12]就是其中之一,由于子種群間交叉、變異操作的引入,使分層遺傳算法可以有效克服簡(jiǎn)單遺傳算法易陷入局部最優(yōu)解的缺點(diǎn),從而提高了算法的尋優(yōu)性能。分層遺傳算法的操作流程如圖1所示。

圖1 分層遺傳算法流程圖Fig.1 The flow chart of HGA

圖1 中,設(shè)有N個(gè)子種群P1,P2,…,PN,每個(gè)子種群中有n個(gè)染色體。令子種群P1,P2,…,PN獨(dú)立地運(yùn)行簡(jiǎn)單遺傳算法,記為GA 1,GA 2,…,GA n。當(dāng)N個(gè)子種群獨(dú)立進(jìn)化若干代后,高一級(jí)的遺傳算法將每個(gè)子種群視為一個(gè)“染色體”,而將其中的染色體視為“基因”;與子種群內(nèi)的所執(zhí)行的選擇、交換及變異操作類似,高一級(jí)的遺傳算法隨機(jī)選取若干子種群,并根據(jù)子群間的遷移率,在子種群間執(zhí)行以染色體為基本單位的交換和變異操作。

2 限定搜索區(qū)域分層遺傳算法路徑規(guī)劃

將分層遺傳算法用于求解路徑規(guī)劃問(wèn)題時(shí),需要解決的核心問(wèn)題是:1)種群的初始化方式;2)數(shù)據(jù)的編碼格式的確定;3)代價(jià)函數(shù)的選擇。這3個(gè)問(wèn)題處理的優(yōu)劣直接決定路徑優(yōu)化的效率和結(jié)果。

2.1 限定搜索區(qū)域的種群初始化

以往的路徑規(guī)劃算法通常都是在整個(gè)任務(wù)區(qū)域內(nèi)搜索優(yōu)化路徑,因此,當(dāng)利用分層遺傳算法尋找優(yōu)化航路時(shí),初始種群,即初始路徑節(jié)點(diǎn)是隨機(jī)分布在無(wú)人機(jī)的整個(gè)任務(wù)區(qū)域內(nèi)的,如圖2所示。

圖2 分布在整個(gè)任務(wù)區(qū)域內(nèi)的初始種群Fig.2 The initial population distributed in the entire mission area

一方面這會(huì)消耗大量的計(jì)算時(shí)間;另一方面,又會(huì)使路徑規(guī)劃算法搜索到繞行路徑,大大增加了無(wú)人機(jī)的航程。所以有必要根據(jù)威脅的分布情況,盡可能縮小算法的搜索區(qū)域,約束路徑節(jié)點(diǎn)的分布,從而減少繞行航路的出現(xiàn)并縮短路徑的長(zhǎng)度。

設(shè)無(wú)人機(jī)的任務(wù)區(qū)域是20 km×20 km正方形區(qū)域,航路的起點(diǎn)為[0,0],目標(biāo)點(diǎn)為[20,20],將起點(diǎn)與目標(biāo)點(diǎn)間的連線看作一條理想航路,一般希望無(wú)人機(jī)盡可能沿這條理想航路飛行,從而在安全規(guī)避威脅的前提下最大限度地縮短航程,所以只需考慮集中分布在起始點(diǎn)與目標(biāo)點(diǎn)連線兩側(cè)的威脅,在該區(qū)域內(nèi)進(jìn)行路徑規(guī)劃便可得到期望的優(yōu)化路徑,如圖3中路徑1。而圖3中的路徑2,雖然保證了無(wú)人機(jī)的飛行安全,但大大增加了航行路徑的長(zhǎng)度,我們希望盡可能避免這類繞行路徑的產(chǎn)生。

圖3 遺傳算法可能搜索到的最優(yōu)路徑Fig.3 The optimal paths that GA could find

基于該想法,本文提出了如下的限定搜索區(qū)域算法 (Restricted Searching Area Algorithm-RSAA),來(lái)使初始化種群優(yōu)化:

1)求起點(diǎn)start與目標(biāo)點(diǎn)Target間的連線:y=ksT?x+bsT,將這條連線定義為無(wú)人機(jī)的理想航路;

2)將威脅中心在無(wú)人機(jī)任務(wù)區(qū)域內(nèi)的所有威脅源的集合記為T;

3)將任務(wù)區(qū)內(nèi)威脅源分為理想航路的“上側(cè)威脅源”和理想航路的“下側(cè)威脅源”,記為 Tu=[Tu1,Tu2,…,Tu k],Tl=[Tl1,Tl2,…,Tl p],Tu∩ Tl=T;

4)分別計(jì)算上側(cè)威脅源與下側(cè)威脅源到理想航路的距離du=[du1,du2,…,duk]以及dl=[dl1,dl2,…,dl p];

5)尋找與理想航路距離最遠(yuǎn)的上側(cè)威脅源和下側(cè)威脅源,分別記為Cu和Cl;

6)若m個(gè)威脅源[C1,C2,…,Cm]與理想航路的距離相同,則查詢威脅源[C1,C2,…,Cm]的半徑,將半徑最大的威脅源作為C u或C l;

7)若m個(gè)威脅源[C1,C2,…,Cm]與理想航路的距離相同且威脅半徑相同,則計(jì)算這m個(gè)威脅源與起點(diǎn)(x0,y 0)距離[d1,d2,…,dm],將與(x0,y0)距離最遠(yuǎn)的威脅源作為Cu或Cl;

8)從起點(diǎn)(x0,y0)分別向Cu和Cl遠(yuǎn)離理想航路的一側(cè)做切線,切點(diǎn)為Bu和 Bl,射線SBu和SBl所構(gòu)成的放射狀區(qū)域即為限定搜索區(qū)域。

與圖2進(jìn)行對(duì)比,在圖 4中可以看到,使用RSAA后,所有的初始種群,即初始路徑節(jié)點(diǎn)都嚴(yán)格分布在限定搜索區(qū)域內(nèi)。

圖4 使用RSAA算法后生成的初始種群Fig.4 Theinitial population using RSAA

2.2 數(shù)據(jù)編碼方案

由于本文使用的代價(jià)函數(shù)是在二維直角坐標(biāo)系下建立的,故采用浮點(diǎn)數(shù)編碼的方式對(duì)路徑節(jié)點(diǎn)的二維直角坐標(biāo)進(jìn)行編碼。

設(shè)初始點(diǎn)Start=[x0,y 0],目標(biāo)點(diǎn) Target=[x G,y G],種群中的染色體由一組路徑節(jié)點(diǎn)的二維直角坐標(biāo)組成,最終的優(yōu)化路徑可表示為:

式中,n為子種群中的染色體數(shù),nCP為路徑節(jié)點(diǎn)數(shù)。

2.3 代價(jià)函數(shù)

理想的代價(jià)函數(shù)應(yīng)具有在無(wú)人機(jī)接近威脅或總航程增大時(shí)能迅速增大,當(dāng)無(wú)人機(jī)遠(yuǎn)離威脅或總航程縮短時(shí)能迅速減小的性質(zhì)。本文的代價(jià)函數(shù)表示為:

式中,wd為距離代價(jià)權(quán)值,ws為威脅代價(jià)權(quán)值,wDir方向修正權(quán)值,wC為懲罰代價(jià)權(quán)值,wd+ws=1,Di,i+1為相鄰兩節(jié)點(diǎn)i,i+1之間路徑的距離代價(jià)函數(shù),可表示為:

Si,i+1為路徑節(jié)點(diǎn)i,i+1之間路徑的威脅代價(jià)函數(shù),可表示為:

式中,di為路徑節(jié)點(diǎn)i到所有威脅中心距離的最小值,d i+1為路徑節(jié)點(diǎn)i+1到所有威脅中心距離的最小值,di,i+1為節(jié)點(diǎn)i,i+1之間路徑到所有威脅中心距離的最小值。

當(dāng)確定了編碼方案和代價(jià)函數(shù)后,就可按照如圖1所示的分層遺傳算法操作流程進(jìn)行遺傳操作,完成無(wú)人機(jī)航路的尋優(yōu)。

3 算法仿真

本文采用Matlab R2007b進(jìn)行路徑規(guī)劃算法的仿真。關(guān)鍵仿真參數(shù)設(shè)定如下:無(wú)人機(jī)任務(wù)區(qū)域?yàn)?0 km×20 km的正方形區(qū)域,航路起始點(diǎn)Start=[0,0],目標(biāo)點(diǎn)Target=[20,20],路徑節(jié)點(diǎn)數(shù)為5,子種群數(shù)為5,最大進(jìn)化代數(shù)為40代;使用隨機(jī)遍歷抽樣選擇法進(jìn)行選擇復(fù)制操作;交換則采用了單點(diǎn)交換,交換率Px=0.7;變異率Pm=0.1;每進(jìn)化10代在子種群間進(jìn)行一次交換和變異操作。

在種群大小為150時(shí),單獨(dú)使用HGA對(duì)給定路徑規(guī)劃問(wèn)題進(jìn)行30次求解;將限定搜索區(qū)域算法與分層遺傳算法結(jié)合,采用RSAA+HGA的方式,分別在種群大小為150和100的條件下對(duì)同一路徑規(guī)劃問(wèn)題進(jìn)行30次求解,仿真結(jié)果如圖5—圖7以及表1所示。

圖5 種群數(shù)為150時(shí)HGA運(yùn)行30次所得的最優(yōu)路徑Fig.5 The optimal path generated by HGA after 30 generations,popsize=150

圖6 種群數(shù)為150時(shí)RSAA+HGA運(yùn)行30次所得的最優(yōu)路徑Fig.6 The optimal path generated by RSAA+HGA after 30 generations,popsize=150

圖7 種群數(shù)為100時(shí)RSAA+HGA運(yùn)行30次所得的最優(yōu)路徑Fig.7 The optimal path generated by RSAA+HGA after 30 generations,popsize=100

圖中符號(hào)‘*’表示路徑節(jié)點(diǎn),虛線表示限定搜索區(qū)域的邊界,粗實(shí)線表示最終的優(yōu)化路徑。當(dāng)種群數(shù)為150時(shí),從表1中可以看出,當(dāng)使用RSAA+HGA搜索優(yōu)化路徑時(shí),雖然計(jì)算時(shí)間有所增加,但從“可行路徑/運(yùn)行次數(shù)”一項(xiàng)看出,RSAA+HGA的方式有效提高了路徑規(guī)劃算法的穩(wěn)定性,并縮短了最優(yōu)路徑的長(zhǎng)度。當(dāng)種群規(guī)模減小至原種群規(guī)模的2/3時(shí),RSAA+HGA在保證算法性能基本不變的前提下大幅減少了計(jì)算時(shí)間。同時(shí)從“繞行路徑/可行路徑”一項(xiàng)可以看出,RSAA+HGA有效防止了繞行路線的出現(xiàn)。

表1 算法性能比較Tab.1 Comparison of algorithms'performance

4 結(jié)論

本文針對(duì)遺傳算法的無(wú)人機(jī)路徑規(guī)劃存在的問(wèn)題進(jìn)行了分析和研究,提出了新的無(wú)人機(jī)路徑規(guī)劃方法,該方法根據(jù)威脅的分布情況,盡可能縮小算法的搜索區(qū)域,約束路徑節(jié)點(diǎn)的分布,限定了搜索區(qū)域,并用分層遺傳算法在該區(qū)域內(nèi)尋找最優(yōu)路徑。仿真結(jié)果表明:新方法提高了尋優(yōu)算法的穩(wěn)定性,克服了簡(jiǎn)單遺傳算法在無(wú)人機(jī)路徑規(guī)劃尋優(yōu)時(shí)易陷入局部最優(yōu)解的缺點(diǎn),消除了繞行路徑的生成,并提高了算法的優(yōu)化搜索效率。下一階段,本文將圍繞著如何在威脅分布更為復(fù)雜的區(qū)域內(nèi)確定搜索區(qū)域而展開(kāi)。

[1]嚴(yán)建林,李春濤.無(wú)人機(jī)航路規(guī)劃技術(shù)研究進(jìn)展[J].航空計(jì)算技術(shù),2007,37(5):123-125.YAN Jianlin,LI Chuntao.Developments of Autonomous Aircraft Route-planning Research[J].Aeronautical Computing Technique,2007,37(5):123-125.

[2]馬云紅,周德云.基于遺傳算法的無(wú)人機(jī)航路規(guī)劃[J].電光與控制,2005,12(5):24-27.MA Yunhong,ZHOU DeYun.A genetic algorithm for path planning of UAV[J].Electronics Optics&Control,2005,12(5):24-27.

[3]Yao-hong Qu,Quan Pan,Jian-guo Yan.Flight Path Planning of UAV Based on Heuristically Search and Genetic Algorithms[C]//Industrial Electronics Society,IECON 2005.31st Annual Conference of IEEE.US:IEEE,2005:45-49.

[4]Wing Kwong Chung,Yangsheng Xu.A Generalized 3-D Path Planning Method for Robots Using Genetic Algorithm with An Adaptive Evolution Process[C]//Intelligent Control and Automation(WCICA)8th World Congress.US:WCICA,2010:1354-1360.

[5]Sadati N,Taheri J.Genetic Algorithm in Robot Path Planning Problem in Crisp and Fuzzified Environments[C]//Industrial Technology,2002.IEEE ICIT'02.2002 IEEEInternational Conference.US:IEEE,2002:175-180.

[6]Davies T,Jnifene A.Multiple Waypoint Path Planning for a Mobile Robot using Genetic Algorithms,Computational Intelligence for Measurement Systems and Applications[C]//Proceedings of 2006 IEEE International Conference.US:IEEE,2006:21-26.

[7]Randal W Beard.Coordinated Target Assignment and Intercept for Unmanned Air Vehicles[C]//Proceedings of the 2002 IEEE International Conference on Robotics&Automation.Washington DC:IEEE,2002,2581-2586.

[8]Randal W Beard.Autonomous Hierarchical Control of Multiple Unmanned Combat Air Vehicles(UCAVs)[C]//Proceedings of the American Control Conference Anchorage.US:ACCA,2002:274-279.

[9]Ioannis K Nikolos,Kimon P,Valavanis.Evolutionary Algorithm Based Offline/Online Path Planner for UAV Navigation[J].IEEE TRANSACTIONSON SYSTEMS,MAN,AND CYBERNETICS-PA RT B:CYBERNETICS,2003,33(6):898-912.

[10]劉勇,康立山,陳毓屏.非數(shù)值并行算法——遺傳算法[M].北京:科學(xué)出版社,1997.

[11]John H Holland.Adaptation in Natural and Artificial Systems[M].US:University of Michigan Press,Ann Arbor,1975.

[12]王小平,曹立明.遺傳算法-理論、應(yīng)用與軟件實(shí)現(xiàn)[M].西安:西安交通大學(xué)出版社,2002.