改進(jìn)人工蜂群算法的無人機(jī)航跡規(guī)劃研究*

徐流沙，吳梅，袁志敏

（1.西北工業(yè)大學(xué)自動(dòng)化學(xué)院，西安710072；2.陜西飛機(jī)工業(yè)（集團(tuán)）有限公司設(shè)計(jì)研究院，陜西漢中723213）

改進(jìn)人工蜂群算法的無人機(jī)航跡規(guī)劃研究*

徐流沙1，吳梅1，袁志敏2

（1.西北工業(yè)大學(xué)自動(dòng)化學(xué)院，西安710072；2.陜西飛機(jī)工業(yè)（集團(tuán)）有限公司設(shè)計(jì)研究院，陜西漢中723213）

如何快速地規(guī)劃出滿足約束條件的飛行航跡，是實(shí)現(xiàn)無人機(jī)自主飛行的關(guān)鍵。將改進(jìn)的人工蜂群算法應(yīng)用于求解無人機(jī)航跡規(guī)劃問題，同時(shí)在人工蜂群算法的偵察階段引入差分進(jìn)化算法的思想。通過仿真實(shí)驗(yàn)并與標(biāo)準(zhǔn)人工蜂群算法比較，結(jié)果表明此算法能夠有效加快收斂速度，提高最優(yōu)航跡精度，是解決航跡規(guī)劃和其他高維復(fù)雜函數(shù)優(yōu)化的有效方法。

無人機(jī)，航跡規(guī)劃，人工蜂群算法，差分進(jìn)化算法

0　引言

無人機(jī)（UAV）航跡規(guī)劃（Path Planning）是無人機(jī)任務(wù)規(guī)劃系統(tǒng)的核心之一，它一般指在確定無人機(jī)起飛位置、目標(biāo)位置和飛行途中的目標(biāo)任務(wù)后的一系列優(yōu)化問題，根據(jù)無人機(jī)的機(jī)動(dòng)性能，飛行的地理環(huán)境及威脅等信息規(guī)劃出一條滿足飛行條件的最優(yōu)或者次優(yōu)路徑。航跡規(guī)劃對于提高飛機(jī)生存率、增強(qiáng)作戰(zhàn)效能具有十分重要的意義。

人工蜂群（Artificial Bee Colony，ABC）算法是一種新興群體智能優(yōu)化技術(shù)，它基于蜂群的智能采蜜行為及自治、分工和自組織，是由土耳其Erciyes大學(xué)Dervis Karaboga［1］在2007年提出。ABC算法結(jié)合全局搜索和局部搜索的方法來使蜜蜂在食物源的探索和開采兩個(gè)方面達(dá)到很好的平衡。Karaboga與Basturk［2］通過5個(gè)常見基準(zhǔn)函數(shù)測試得出，ABC算法與遺傳算法、進(jìn)化算法和粒子群算法一樣具有良好的優(yōu)化性能，但是，目前ABC算法作為一種新的隨機(jī)優(yōu)化算法，在接近全局最優(yōu)解時(shí)，仍存在著搜索速度變慢、過早收斂、個(gè)體的多樣性減少，甚至陷入局部最優(yōu)解等難題。然而，ABC算法因有勞動(dòng)分工和協(xié)作機(jī)制，算法更靈活，易與其他技術(shù)結(jié)合以改進(jìn)原算法。本文首先介紹適用于ABC算法的航跡表示方法，并在這基礎(chǔ)上結(jié)合約束條件，構(gòu)造合理的目標(biāo)函數(shù)，再對ABC算法進(jìn)行一些改進(jìn)，并將其應(yīng)用于無人機(jī)航跡規(guī)劃。

1　問題描述

無論針對何種飛行器，航跡規(guī)劃問題都包含了一些相同的基本要素：規(guī)劃空間建模、航跡表示、約束條件解析、目標(biāo)函數(shù)確定、規(guī)劃算法選?。?］。

1.1規(guī)劃空間與航跡表示

不考慮地形高度信息，認(rèn)為無人機(jī)都是以同一高度飛行，所以航跡規(guī)劃在二維歐氏空間中進(jìn)行搜索。威脅和障礙，如地形高度、氣象環(huán)境、地方防空火力與雷達(dá)部署等，可以用封閉圖形表示，如圓、多邊形等。對于非圓形不規(guī)則威脅區(qū)可視作若干圓形威脅區(qū)的組合，本文用圓表示威脅和障礙。因此，威脅信息可表示為Nthreat×3的矩陣，每行為（Txi，Tyi，Ri），其中Nthreat為威脅個(gè)數(shù)，（Txi，Tyi）為第i個(gè)威脅的坐標(biāo)，Ri為威脅半徑。當(dāng)然也可以定義各個(gè)威脅源的威脅指數(shù)，本文認(rèn)為威脅指數(shù)都相等。

確定起點(diǎn)S，終點(diǎn)G后，航跡規(guī)劃在S，G之中，規(guī)劃出一條可行且較優(yōu)的航跡。用空間位置點(diǎn)序列{S，P1，…，PD，G}表示飛行航跡，P1，…，PD為中間節(jié)點(diǎn)，D為定值，各相鄰航跡節(jié)點(diǎn)用直線段連接。為了計(jì)算簡單，通過坐標(biāo)平移與變換［4］，將起點(diǎn)S映射到原點(diǎn)，終點(diǎn)G映射到X軸上，SG等分成D+1段，并在等分點(diǎn)上作垂直于X軸的直線，則P1，…，PD分別在各自垂線上，這樣只需要保存P1，…，PD的縱坐標(biāo)x1，x2，…，xD即可，因此，這一航跡可表示為X=（x1，x2，…，xD），對應(yīng)著ABC算法中的一個(gè)蜜源，如圖1所示。

圖1　航跡點(diǎn)分布

有個(gè)缺點(diǎn)就是，這樣規(guī)劃出來的航跡是橫坐標(biāo)的函數(shù)，即不能迂回。不過在實(shí)際應(yīng)用中，為了減少導(dǎo)航誤差，也不希望無人機(jī)迂回行進(jìn)。

1.2約束條件

為保證規(guī)劃結(jié)果合理可用，需要考慮飛行器自身的物理限制和使用要求。在二維規(guī)劃空間主要包括以下幾個(gè)方面［5］。

1.2.1最小航跡段長度

開始改變飛行姿態(tài)前必須保持直飛，它有最短距離的限制，也即最短航跡長度。這一限制取決于飛行器的機(jī)動(dòng)能力和導(dǎo)航要求。如圖1所示，只需保證等分間隔大于最小航段長度。

1.2.2最大拐彎角

它限制了生成的航跡只能在小于或等于預(yù)先確定的最大拐彎角范圍內(nèi)轉(zhuǎn)彎。該約束條件取決于飛行器的機(jī)動(dòng)性能和飛行任務(wù)。例如，在緊密編隊(duì)飛行中，飛行器應(yīng)避免劇烈轉(zhuǎn)彎，否則將導(dǎo)致很大的碰撞風(fēng)險(xiǎn)。設(shè)Pk為第k個(gè)中間節(jié)點(diǎn)，則最大拐彎角約束為：

式中ak=PkPk-1，‖ai‖為向量ai的長度，默認(rèn)P0為S，PD+1為G。

1.2.3最大航跡長度

它限制了航跡的長度必須小于或等于一個(gè)預(yù)先設(shè)置的最大距離Lmax。它取決于飛行器所攜帶的燃料以及特定任務(wù)中到達(dá)目標(biāo)所允許的飛行時(shí)間，該約束為：

1.2.4端點(diǎn)方向約束

為了保證順利完成某些任務(wù)，要求飛行器按特定方向區(qū)間接近目標(biāo)。按照圖1，固定端點(diǎn)方向，則點(diǎn)PD也就確定，規(guī)劃維數(shù)減少。

1.3目標(biāo)函數(shù)

1.3.1威脅代價(jià)

無人機(jī)在空間中的點(diǎn)x處受第j個(gè)威脅的影響指數(shù)主要與無人機(jī)和威脅間的距離dxj有關(guān)，具體計(jì)算可采用如下方式：

式中：Kj為一參數(shù)，反映第j個(gè)威脅的強(qiáng)度，默認(rèn)都為1；a＞1，b＞1，將規(guī)劃空間相對于威脅j劃成3個(gè)區(qū)域，威險(xiǎn)區(qū)、次安全區(qū)、安全區(qū)。

這樣在表達(dá)式中，要計(jì)算第i段的航跡的威脅指數(shù)需要沿第i段進(jìn)行積分，為了減少計(jì)算量，只計(jì)算該段航跡的若干個(gè)點(diǎn)的威脅指數(shù)的平均值，再乘以該航跡段的長度。則：

式中，Nthreat為已知威脅源的個(gè)數(shù)，li/6表示第i段航跡的1/6處，如圖2所示。

圖2　威脅代價(jià)計(jì)算

1.3.2油耗代價(jià)

假設(shè)無人機(jī)飛行速度為常值，則油耗可簡單地認(rèn)為與航跡長度成正比。

1.3.3轉(zhuǎn)彎代價(jià)

綜合以上，目標(biāo)函數(shù)為：

式中，X=（x1，x2，…，xD），x1，x2，…，xD分別為點(diǎn)P1，P2，…，PD的縱坐標(biāo)，且

表示規(guī)劃區(qū)域大小，w1，w2，w3為相應(yīng)權(quán)系數(shù)。

航跡規(guī)劃問題的數(shù)學(xué)描述即是：

2　規(guī)劃算法

2.1人工蜂群算法

采蜜的群體智能通過不同角色之間的交流、轉(zhuǎn)換及協(xié)作來實(shí)現(xiàn)。ABC算法模擬實(shí)際蜜蜂采蜜機(jī)制處理函數(shù)優(yōu)化問題，將人工蜂群分為3類：采蜜蜂、跟隨蜂、偵察蜂。優(yōu)化問題的解及相應(yīng)的函數(shù)值抽象為蜜源的位置和花蜜的數(shù)量。每只采蜜蜂都對應(yīng)一個(gè)蜜源，采蜜蜂采蜜過程則抽象為在當(dāng)前蜜源附近搜索新蜜源，若優(yōu)于當(dāng)前蜜源就將其替換。對于航跡規(guī)劃，X代表某一蜜源，則J（X）為該蜜源質(zhì)量。

首先偵察蜂在無先驗(yàn)條件下發(fā)現(xiàn)初始蜜源并記憶，之后尋找最優(yōu)蜜源的過程為：偵察蜂轉(zhuǎn)變成采蜜蜂進(jìn)行采蜜；跟隨蜂根據(jù)蜜源信息在某種機(jī)制下選取合適的蜜源并轉(zhuǎn)換成采蜜蜂采蜜，得到本次循環(huán)的最終標(biāo)記蜜源，這樣反復(fù)循環(huán)尋找最佳蜜源；但是如果在采蜜過程中，蜜源經(jīng)若干次搜索不變，相應(yīng)的采蜜蜂變成偵查蜂，重新搜索新的蜜源。具體步驟如下［7］：

1）初始化ABC參數(shù)：蜂群總數(shù)NP，最大迭代次數(shù)Nmax，蜜源放棄閾值limit；

2）按照式（7）隨機(jī)產(chǎn)生NP/2個(gè)初始蜜源Xi=（xi1，xi2，…，xiD），i=1，2，…，NP/2，rand為［0，1］中的隨機(jī)數(shù)，j=1，2，…，D；

3）當(dāng)前迭代次數(shù)為iter=1；

4）若iter＜Nmax，repeat；

5）采蜜蜂在蜜源附近按式（8）搜索新蜜源；

式中，k為隨機(jī)生成，且不等于i，φij為［-1，1］間的隨機(jī)數(shù)，控制搜索范圍。

6）貪婪準(zhǔn)則，根據(jù)式（6）比較前后蜜源優(yōu)劣，若搜索后蜜源優(yōu)于搜索前，則代替先前蜜源；

7）跟隨蜂根據(jù)處于蜜源處的采蜜蜂釋放的花蜜信息，按輪盤賭方式選擇蜜源，并在其附近按式（2）搜索新蜜源；

8）貪婪準(zhǔn)則，根據(jù)式（6）比較跟隨蜂及采蜜蜂搜索的蜜源的質(zhì)量，若優(yōu)于則替換；

9）若某些蜜源經(jīng)limit次循環(huán)不變，放棄該蜜源，相應(yīng)采蜜蜂變成偵查蜂，按式（7）隨機(jī)產(chǎn)生新蜜源；

2.2算法改進(jìn)

2.2.1初始蜜源

初始解是算法進(jìn)行搜索的起點(diǎn)，如果生成的初始群體不夠合理，對算法的性能有很大影響。

在ABC算法中，初始群體生成是隨機(jī)的，為此，有必要對初始群體的生成方法進(jìn)行改進(jìn)，改進(jìn)的目的是使得初始群體個(gè)體分布較為均勻，所以采取了小區(qū)間生成法：先將第j（j=1，2，…，D）個(gè)參數(shù)的取值范圍分成蜜源總數(shù)NP/2個(gè)等值小區(qū)間，分別記作I1，j，I2，j，…，INP/2，j，再生成一個(gè)NP/2×D矩陣E={eij}，其中E的每列為1，2，…，NP/2的隨機(jī)排列，則第i個(gè)蜜源的各個(gè)參數(shù)分別在小區(qū)間Ii，ei1，Ii，ei2，…，Ii，eiD中隨機(jī)生成。這樣生成的初始個(gè)體將會(huì)均勻地分布在整個(gè)解空間上，保證了初始群體含有較豐富的模式，增強(qiáng)了搜索收斂于全局最優(yōu)點(diǎn)的可能。仿真實(shí)驗(yàn)證明，這種方法生成的初始群體性質(zhì)優(yōu)良，可加快算法的收斂速度，很好地改善算法的收斂性能。

2.2.2選擇機(jī)制

ABC算法中，跟隨蜂是以輪盤賭的形式選擇蜜源，形式如下：

式中，fiti為第i個(gè)蜜源的適應(yīng)值。對于第j只跟隨蜂，面對第i個(gè)蜜源，如果rand≤Pi，則選擇該蜜源，若rand＞Pi則放棄，直到第j只跟隨蜂找到屬于自己的蜜源。

這是一種基于貪婪策略的選擇方式，會(huì)使種群多樣性降低，從而引起過早收斂和提前停滯的現(xiàn)象。在自由搜索算法中，提出了一個(gè)重要概念——靈敏度，通過與信息素（與優(yōu)化問題的適應(yīng)度值有關(guān)）配合選擇區(qū)域，理論上可以搜索更多區(qū)域，這就在很大程度上避免了陷入局部最優(yōu)；所搜索區(qū)域的信息素必須適應(yīng)其靈敏度，這就使算法有導(dǎo)向作用，決定了目標(biāo)函數(shù)在搜索空間中的收斂和發(fā)散。這種區(qū)域選擇的方式與跟隨蜂選擇蜜源的方式是類似的，所以可以考慮將靈敏度與信息素配合的方式代替輪盤賭的方式［8］。步驟如下：

1）計(jì)算所有蜜源的適應(yīng)度值fit；

2）計(jì)算第i個(gè)蜜源的信息素：

3）隨機(jī)產(chǎn)生第j個(gè)跟隨蜂的靈敏度S（j）～U［0，1］；

4）找出配合第j個(gè)跟隨蜂靈敏度的蜜源：隨機(jī)找出i，滿足nf（i）≥S（j），即靈敏度越高的跟隨蜂，越能找到質(zhì)量更高的蜜源。

2.2.3偵察蜂尋找新的蜜源

在標(biāo)準(zhǔn)ABC算法中，當(dāng)某一蜜源經(jīng)過limit次采蜜后，仍未得到質(zhì)量更好的蜜源，說明陷入局部最優(yōu)，則會(huì)在規(guī)劃空間隨機(jī)生成新的蜜源代替該蜜源。這樣做對提高全局收斂性的幫助有限，同時(shí)因?yàn)闆]有綜合現(xiàn)有蜜源信息，使得搜索過于盲目，降低收斂速度。對此，可以引入差分進(jìn)化法中的變異和交叉操作。

差分進(jìn)化（Differential Evolution，DE）算法是一種采用浮點(diǎn)矢量編碼在連續(xù)空間中進(jìn)行隨機(jī)搜索的優(yōu)化算法。DE的原理簡單，受控參數(shù)少，實(shí)施隨機(jī)、并行、直接的全局搜索，易于理解和實(shí)現(xiàn)。算法的基本思想是：對當(dāng)前種群進(jìn)行變異和交叉操作，產(chǎn)生另一個(gè)新種群；然后利用基于貪婪思想的選擇操作對這兩個(gè)種群進(jìn)行一對一的選擇，從而產(chǎn)生最終的新一代種群。

（1）變異操作

對蜜源Xi=（xi1，xi2，…，xiD）進(jìn)行變異操作，得到相對應(yīng)的變異個(gè)體Vi=（vi1，vi2，…，viD），即：

式中，Xbest為當(dāng)前全局最佳蜜源，參數(shù)r1，r2∈{1，2，…，NP/2}互異且不等于i，Xbest稱為父代基向量；（Xr1-Xr2）稱作父代差分向量；F為縮放比因子。雖然有時(shí)用隨機(jī)選擇的個(gè)體作為父代基向量可能更加合適，但對大多數(shù)例子，使用Xbest可以加速收斂。如果使用Xbest時(shí)導(dǎo)致早熟收斂，則應(yīng)考慮使用隨機(jī)個(gè)體［9］。

（2）交叉操作

將Xi與Vi交叉產(chǎn)生子代個(gè)體，Ui=（ui1，ui2，…，uiD）為保證第i個(gè)蜜源的演化，首先通過隨機(jī)選擇，使得Ui至少有一位由Vi貢獻(xiàn)，而對其他位，可利用一個(gè)交叉概率因子CR∈［0，1］，決定Ui中哪些位由Xi貢獻(xiàn)，哪些位由Vi貢獻(xiàn)。如果rand＜CR，則該位由Vi貢獻(xiàn)，即CR越大，Vi貢獻(xiàn)越多。當(dāng)CR=1時(shí)，Ui=Vi，即如下：

式中，rand（j）為［0，1］之間的均勻分布隨機(jī)數(shù)；rand（i）為{1，2，…，D}之間的隨機(jī)量。

最后，將Ui替代Xi成為第i個(gè)蜜源進(jìn)入下一次循環(huán)，并更新相應(yīng)蜜源質(zhì)量信息。

在文獻(xiàn)［4］中，作者在ABC算法的最后階段，利用混沌算子對所有個(gè)體進(jìn)行操作得到一序列新個(gè)體，再從中選取最優(yōu)進(jìn)入下一次迭代。本文也可以基于差分進(jìn)化算法，采用同樣的方式進(jìn)行迭代［10］。經(jīng)過實(shí)驗(yàn)，這樣做可以減少迭代次數(shù)，并有可能找到更優(yōu)解?？墒菍τ诤桔E規(guī)劃，目標(biāo)函數(shù)是關(guān)于航跡的復(fù)雜函數(shù)，規(guī)劃程序運(yùn)行時(shí)間主要花費(fèi)在航跡代價(jià)的計(jì)算上，這種方法有可能降低規(guī)劃效率。

3　仿真實(shí)驗(yàn)

在仿真實(shí)驗(yàn)中，參數(shù)選取如下：

初始條件：起點(diǎn)設(shè)為（0，0），終點(diǎn)為（0，310），航跡點(diǎn)數(shù)D=30，x1min，x2min，…，xDmin=-150，x1max，x2max，…，xDmax=150，威脅源如下頁圖3，圖4同心圓所示；最小航跡段長度為10，最大拐彎角為π/3，不限最大航跡長度；

ABC控制參數(shù)為：NP=60，Nmax=1 000，limit=60，F(xiàn)=0.5，CR=0.8。

也即算法終止條件為迭代次Nmax=1 000，運(yùn)行過程中輸出每一次迭代的最優(yōu)航跡代價(jià)，迭代結(jié)束再用圖形輸出最優(yōu)航跡，如圖3，圖4所示。本文同時(shí)對標(biāo)準(zhǔn)ABC算法和改進(jìn)ABC算法進(jìn)行航跡規(guī)劃，觀察兩種算法在何時(shí)趨于收斂，并比較兩者航跡的優(yōu)劣。

圖3　標(biāo)準(zhǔn)ABC算法

圖4改進(jìn)ABC算法

圖3是標(biāo)準(zhǔn)ABC算法所生成的航跡，由圖可以看出，算法陷入了局部最優(yōu)，經(jīng)多次仿真實(shí)驗(yàn)，算法平均大概在600次迭代收斂，平均航跡代價(jià)為315。

圖4是改進(jìn)ABC算法所生成的航跡，較之圖3有了很大改善，航跡變得平滑且代價(jià)大幅減少，收斂速度也加快許多，平均迭代300次左右收斂，平均航跡代價(jià)為265?？梢钥闯觯倪M(jìn)的ABC算法能夠有效地加快收斂速度和收斂精度。

4　結(jié)束語

本文用ABC算法求解無人機(jī)航跡規(guī)劃這一多約束、難建模的復(fù)雜優(yōu)化問題。針對ABC算法的不足，提出了幾項(xiàng)改進(jìn)，并在MATLAB環(huán)境下對所提方法進(jìn)行仿真實(shí)驗(yàn)，結(jié)果表明，所作的改進(jìn)有效地提高了收斂精度和減少規(guī)劃時(shí)間，同時(shí)也驗(yàn)證了ABC算法在航跡規(guī)劃問題上的可行性。文中假設(shè)威脅源已知且固定不變，如果威脅源發(fā)生了動(dòng)態(tài)變化，則需要進(jìn)行實(shí)時(shí)的動(dòng)態(tài)航跡規(guī)劃，下一步將對此進(jìn)行研究。

［1］Karaboga D，Basturk B.A Powerful and Efficient Algorithm for Numerical Function Optimization:Artificial Bee Colony（ABC）algorithm［J］.Journal of Global Optimization，2007，39（3）:459-71.

［2］Karaboga D，Basturk B.On the Performance of Artificial Bee Colony（ABC）Algorithm［J］.Applied Soft Computing，2008，8（1）:687-97.

［3］王維平，劉娟.無人飛行器航跡規(guī)劃方法綜述［J］.飛行力學(xué)，2010，28（002）:6-10.

［4］Xu C，Duan H，Liu F.Chaotic Artificial Bee Colony Approach to Uninhabited Combat Air Vehicle（UCAV）Path Planning［J］.Aerospace Science and Technology，2010，14（8）:535-41.

［5］Szczerba R J，Galkowski P，Glicktein I，et al.Robust Algorithm for Real-time Route Planning［J］.Aerospace and Electron ic Systems，IEEE Transactions on，2000，36（3）: 869-78.

［6］李少華，魏海光，周成平，等.一種海上無人飛行器的快速航跡規(guī)劃方法［J］.四川兵工學(xué)報(bào)，2011，32（12）：73-76.

［7］胡中華.基于智能優(yōu)化算法的無人機(jī)航跡規(guī)劃若干關(guān)鍵技術(shù)研究［D］.南京：南京航空航天大學(xué)，2011.

［8］畢曉君，王艷嬌.改進(jìn)人工蜂群算法［J］.哈爾濱工程大學(xué)學(xué)報(bào)，2012，33（1）:117-23.

［9］謝曉鋒，張文俊，張國瑞，等.差異演化的實(shí)驗(yàn)研究［J］.控制與決策，2004，19（1）:49-52.

［10］高衛(wèi)峰，劉三陽，姜飛，等.混合人工蜂群算法［J］.系統(tǒng)工程與電子技術(shù)，2011，33（5）:1167-70.

Research on Path Planning of UAV Based on Improved ABC Algorithm

XU Liu-sha1，WU Mei1，Yuan Zhi-min2
（1.College of Automation，Northwestern Polytechnical University，Xi’an 710072，China；
2.Research Institute，Shaanxi Aircraft Industry（Group）Co.Ltd，Hanzhong 723213，China）

It is critical for autonomous planning of Unmanned Aerial Vehicles（UAV）that how to plan the flight path quickly which fulfills some constraints.This paper applies improved Artificial Bee Colony（ABC）algorithm to solve the problem of UAV path planning and introduce the idea of Differential Evolution（DE）algorithm in the scout bee phase of ABC algorithm.Compared with the standard ABC algorithm，it shows that this algorithm can effectively accelerate the convergence speed and improve the accuracy of the optimal path through the simulation experiments，which proves the feasibility，effectiveness and robustness of this method on the path planning and other high-dimensional complex function optimization.

unmanned aerial vehicles，path planning，artificial bee colony algorithm，differential evolution

V279

A

1002-0640（2015）01-0062-05

2013-11-13

：2014-02-17

中國航空科學(xué)基金資助項(xiàng)目（20100753007）

徐流沙（1988-），男，湖北通山人，碩士研究生。研究方向：航跡規(guī)劃。