鄭洪清

（廣西外國(guó)語(yǔ)學(xué)院 信息工程學(xué)院，南寧 530222）

改進(jìn)CS算法在無(wú)人機(jī)航路規(guī)劃中的應(yīng)用

鄭洪清

（廣西外國(guó)語(yǔ)學(xué)院 信息工程學(xué)院，南寧 530222）

目前，智能算法成為求解無(wú)人機(jī)航路規(guī)劃問(wèn)題的主流方法，其重點(diǎn)是在無(wú)人機(jī)安全的前提下，如何快速到達(dá)目的地。針對(duì)這一問(wèn)題，本文提出一種離散型布谷鳥(niǎo)搜索算法的航路規(guī)劃方法，設(shè)計(jì)了基于八個(gè)方向的整形編碼，采用航行的方向表示路徑。仿真實(shí)驗(yàn)表明，該航路規(guī)劃算法效率高，穩(wěn)定性好，是一種行之有效的航路規(guī)劃方法，且具有一定的推廣意義。

無(wú)人機(jī)；布谷鳥(niǎo)搜索算法；航路規(guī)劃

1 引言

無(wú)人機(jī)航路規(guī)劃的任務(wù)是在待定的規(guī)劃空間內(nèi)，在給定約束條件下尋找一條從起點(diǎn)到終點(diǎn)的最佳航路，它本質(zhì)上是一個(gè)多約束的優(yōu)化問(wèn)題，而航路規(guī)劃算法是航路規(guī)劃的靈魂，目前國(guó)內(nèi)外學(xué)者提出了多種規(guī)劃方法，如遺傳算法［1］、粒子群算法［2］、人工勢(shì)場(chǎng)法［3］和蟻群算法［4］等。這些算法存在各自的缺陷。人工勢(shì)場(chǎng)法隨著柵格數(shù)的增加迅速變慢，遺傳算法早熟，易陷入局部最優(yōu)。布谷鳥(niǎo)搜索算法（Cuckoo search algorithm， CS）是一種新型的全局搜索算法，它是通過(guò)布谷鳥(niǎo)的雷維飛行隨機(jī)選擇鳥(niǎo)巢下蛋的行為來(lái)完成尋優(yōu)的過(guò)程，其在工程優(yōu)化等實(shí)際問(wèn)題中得到廣泛應(yīng)用，但基本的布谷鳥(niǎo)搜索算法并不能直接應(yīng)用于無(wú)人機(jī)航路規(guī)劃問(wèn)題的求解。

為了克服基本布谷鳥(niǎo)搜索算法存在的這一問(wèn)題，本文提出一種改進(jìn)的布谷鳥(niǎo)搜索算法，設(shè)計(jì)一種基于八個(gè)移動(dòng)方向的整形編碼，通過(guò)修正編碼及解碼，使其適合求解無(wú)人機(jī)航路規(guī)劃問(wèn)題，通過(guò)仿真實(shí)驗(yàn)，結(jié)果表明該方法的可行性和有效性。

2 航路規(guī)劃問(wèn)題

2.1 飛行環(huán)境和任務(wù)描述

無(wú)人機(jī)在飛行之前需要對(duì)航路進(jìn)行規(guī)劃，根據(jù)地形信息和敵情信息自動(dòng)生成最佳航路。由于無(wú)人機(jī)飛行高度較高，地形不能實(shí)現(xiàn)遮蔽，因此只考慮其水平航跡，將三維航路規(guī)劃轉(zhuǎn)換為二維問(wèn)題。無(wú)人機(jī)飛行的任務(wù)區(qū)域如圖1所示，對(duì)任務(wù)區(qū)域進(jìn)行柵格化，建立如下所示的坐標(biāo)系。圓圈表示威脅區(qū)，其飛行任務(wù)是從s點(diǎn)到t點(diǎn)既短又安全的最佳航路。

2.2 航路編碼

通過(guò)上節(jié)的內(nèi)容，將部分柵格信息摘錄如圖2所示，0表示可飛行區(qū)域；1表示障礙區(qū)域，若障礙區(qū)不滿一格時(shí)，擴(kuò)充為一個(gè)格子。

在柵格圖中，每個(gè)柵格的序號(hào)是從左至右、從上到下依次遞增的順序從1開(kāi)始編號(hào)，用公式（1）進(jìn)行轉(zhuǎn)換：

（1）式中的i 表示行，j表示列。算法的編碼直接關(guān)系到算法的效率與可行性，一個(gè)好的算法應(yīng)該與具體問(wèn)題相關(guān)?，F(xiàn)有的研究是在柵格化后的電子地圖上有針對(duì)性地進(jìn)行編碼。文獻(xiàn)［5］采用y軸的坐標(biāo)作為編碼，文獻(xiàn)［6］將坐標(biāo)軸進(jìn)行旋轉(zhuǎn)后再取縱坐標(biāo)進(jìn)行編碼；文獻(xiàn)［7］直接采用航路點(diǎn)的坐標(biāo)作為編碼；文獻(xiàn)［8］采用起飛點(diǎn)、目標(biāo)點(diǎn)和航路點(diǎn)的節(jié)點(diǎn)信息作為編碼；文獻(xiàn)［4］將柵格區(qū)域轉(zhuǎn)換為一個(gè)有向圖，將每一個(gè)柵格區(qū)域?qū)?yīng)到有向圖中的節(jié)點(diǎn)，用鄰接矩陣來(lái)反映節(jié)點(diǎn)之間的連通信息，其空間復(fù)雜度O（n4），而本文設(shè)計(jì)一種新的編碼方式，即無(wú)人機(jī)的航行方向，無(wú)人機(jī)在每一個(gè)柵格處，航行的方向至多為8個(gè)，如圖3所示。以圖2為例將柵格中的每一個(gè)區(qū)域?qū)?yīng)到方向矩陣A中（在該例中只顯示了3個(gè)方向，方向增多依次類推），其空間復(fù)雜度為O（n2）。因此本文的航路編碼采用整型編碼，路徑節(jié)點(diǎn)的直角坐標(biāo)采用文獻(xiàn)［4］的計(jì)算公式：

（2）式中的Pm為柵格的大小，為取余函數(shù)，為取整函數(shù)。

方向節(jié)點(diǎn)集合w=｛1，2，…，m｝，m為移動(dòng)方向的數(shù)目，故從起點(diǎn)到目標(biāo)點(diǎn)航路以方向的形式表示為：

Path=｛S，L1，L2，…，Ln，E｝，其中Ln的取值為w集合中的某一個(gè)。

2.3 編碼修正

隨機(jī)產(chǎn)生的初始解代表的是每一個(gè)柵格的方向，由于飛行區(qū)域有許多威脅區(qū)，有些方向是不可行的，因此需依據(jù)方向矩陣A加以修正，其思想如下：

算法1：修正初始解

對(duì)于鳥(niǎo)巢內(nèi)的每一個(gè)值，判斷在方向矩陣相應(yīng)的行里是否存在，若存在，則隨機(jī)選擇一個(gè)賦給鳥(niǎo)巢，否則賦為0。

2.4 解碼

利用上述思想求得的最優(yōu)解是方向矩陣，因此應(yīng)將其解碼為航路節(jié)點(diǎn)信息，算法2偽代碼如下：

通過(guò)該算法可以將編碼解碼為航路的具體節(jié)點(diǎn)，ls表示柵格的列數(shù)。

2.5 航路性能評(píng)價(jià)

在確定飛機(jī)航路之前，要確定每條航路的性能指標(biāo)，它主要包括耗油代價(jià)和威脅代價(jià)，航路的目標(biāo)就是使得總代價(jià)最小，本文采用（3）式來(lái)評(píng)價(jià)航路性能［4］

為第i段航路的耗油代價(jià)，

它與航程Li是成正比；

為第i 段航路的威脅代價(jià)，k為權(quán)重系數(shù)，可以根據(jù)無(wú)人機(jī)的要求做出傾向性選擇，k∈［0，1］。為了準(zhǔn)確計(jì)算每段航路的威脅代價(jià)，在每段航路中找出5個(gè)均勻分布點(diǎn)并計(jì)算每個(gè)點(diǎn)到威脅源的威脅代價(jià)，累加求和即為該航段的威脅代價(jià)。其計(jì)算公式定義為：

式中的n為飛機(jī)當(dāng)前所能探測(cè)到的威脅個(gè)數(shù)，Kj為第j個(gè)威脅的強(qiáng)度；Rij為該航路上的點(diǎn)到第j 個(gè)威脅中心的距離。

3 基于CS算法的無(wú)人機(jī)航路規(guī)劃

3.1 基本CS算法

布谷鳥(niǎo)搜索算法是由英國(guó)劍橋大學(xué)學(xué)者 YANG Xin-she和DEB Suash對(duì)布谷鳥(niǎo)尋窩產(chǎn)卵的行為進(jìn)行模擬，提出了一種新的搜索算法，即Cuckoo Search算法（CS）［9］。由于這種算法簡(jiǎn)單、高效且易于實(shí)現(xiàn)，并在各個(gè)領(lǐng)域得到廣泛應(yīng)用。該算法將模擬布谷鳥(niǎo)尋窩產(chǎn)卵的自然過(guò)程，把待解決問(wèn)題的參數(shù)編碼構(gòu)成鳥(niǎo)巢，多個(gè)鳥(niǎo)巢構(gòu)成種群，種群中的個(gè)體通過(guò)布谷鳥(niǎo)的Levy飛行選擇鳥(niǎo)巢和一定概率拋棄鳥(niǎo)巢來(lái)更新種群。經(jīng)過(guò)多次迭代直至得到最后的優(yōu)化結(jié)果。

布谷鳥(niǎo)尋窩的路徑和位置更新公式如下：

（5）式中乘法，?表示步長(zhǎng)，L（ λ）為L(zhǎng)evy隨機(jī)搜索路徑，并且L～u=t-λ，（1＜λ≤3）。通過(guò)位置更新后，用隨機(jī)數(shù)r∈［0，1］與pa對(duì)比，表示第i 個(gè)鳥(niǎo)巢在第t 代的鳥(niǎo)巢位置，⊕表示點(diǎn)若r＞pa，則對(duì)進(jìn)行隨機(jī)改變，反之不變。最后保留測(cè)試值較好的一組鳥(niǎo)巢位置

3.2 改進(jìn)的CS算法

基本的CS算法適合求解連續(xù)優(yōu)化問(wèn)題，根據(jù)上一節(jié)編碼的分析和結(jié)合無(wú)人機(jī)航路規(guī)劃的特點(diǎn)， 需改進(jìn)布谷鳥(niǎo)搜索算法使其適合求解無(wú)人機(jī)航路規(guī)劃問(wèn)題。通過(guò)公式（6）和（7）將其離散化。，此時(shí)仍把記為。

其中stepsize 為（5）式Levy飛行所產(chǎn)生的步長(zhǎng)，m為方向的個(gè)數(shù)。

3.3 算法步驟

步驟1：將飛行區(qū)域柵格化并轉(zhuǎn)化為0-1矩陣。

步驟2：由0-1矩陣判斷無(wú)人機(jī)在每一個(gè)柵格的飛行方向，求出其方向矩陣。

步驟3：隨機(jī)生成1-m個(gè)方向作為鳥(niǎo)巢nest的初始解。

步驟4：利用算法（1）生成有效矩陣。

步驟5：用公式（3）計(jì)算當(dāng)前的最優(yōu)值fmin及最優(yōu)解fbest。

步驟6：利用公式（5）產(chǎn)生新解，并用公式（6）和（7）進(jìn)行離散化處理，再利用算法（1）加以修正。

步驟7： 利用公式（3）重新評(píng)估最優(yōu)值fnew和最優(yōu)解fbest1，如果fnew＜fmin則用fnew，fbest1替換原來(lái)的最優(yōu)值及最優(yōu)解，否則不變。

步驟8：判斷循環(huán)是否結(jié)束，如果是，根據(jù)算法（7）進(jìn)行解碼，輸出航路點(diǎn)信息；否則跳轉(zhuǎn)步驟6。

4 仿真實(shí)例與分析

為了檢測(cè)所提出算法的性能，實(shí)例運(yùn)行在處理器為Celeron（R）雙核CPU T3100， 1.90GHZ 、內(nèi)存為2G的PC上，以Matlab R2010a編寫代碼。假設(shè)無(wú)人機(jī)的飛行區(qū)域?yàn)?0km×20km的電子地圖，按1km×1km進(jìn)行20等分，S表示起點(diǎn)，T表示終點(diǎn)，用不同的形狀表示威脅區(qū)域。參數(shù)設(shè)置為：種群規(guī)模25，總迭代次數(shù)為50；權(quán)重系數(shù)k =0.4。每個(gè)實(shí)驗(yàn)獨(dú)立運(yùn)行10次。

實(shí)驗(yàn)一：4個(gè)威脅區(qū)域

對(duì)于不規(guī)則的4個(gè)威脅區(qū)域，其實(shí)驗(yàn)結(jié)果如圖4所示。

實(shí)驗(yàn)二：11個(gè)威脅區(qū)域

這里對(duì)威脅區(qū)域采取近似圓表示，半徑為威脅區(qū)域的有效距離，圓內(nèi)為威脅區(qū)。設(shè)威脅點(diǎn)坐標(biāo)為：（2，18），（2.5，13），（3，5），（7.5，4），（8，9），（7.5，15），（12，11），（12.5，6.5），（11，3），（14.5，2），（18，3），（17，6.5）；威脅半徑（1，1.5，1，1，1，2.5，2，1.5，1， 0.5，1，1.5）。實(shí)驗(yàn)結(jié)果如圖6所示。從圖4和圖6不難發(fā)現(xiàn)，采用改進(jìn)的布谷鳥(niǎo)搜索算法能夠規(guī)避風(fēng)險(xiǎn)，安全快速到達(dá)目的地，并且提高了路徑規(guī)劃的成功率，算法更加穩(wěn)定。仿真結(jié)果表明本規(guī)劃算法設(shè)計(jì)的航線是可行的，但由于航路的拐角太多，不利于無(wú)人機(jī)的飛行，故對(duì)航路進(jìn)行了B樣條函數(shù)處理后的結(jié)果如圖5和圖7所示。

5 結(jié)束語(yǔ)

利用一種新型的布谷鳥(niǎo)搜索算法對(duì)無(wú)人機(jī)航路規(guī)劃問(wèn)題時(shí)行分析與研究，設(shè)計(jì)了一種基于八個(gè)移動(dòng)方向的編碼方式，并提出離散型的布谷鳥(niǎo)搜索算法求解該問(wèn)題，通過(guò)實(shí)驗(yàn)仿真，表明該方法的可行性，同時(shí)該方法可應(yīng)用于類似的路線規(guī)劃問(wèn)題，具有一定的推廣作用。

［1］K E Parsopoulos，M N Vrahatis.Unified Particle Swarm Optimization in Dynamic Environments［J］.EvoWork，2005，3449：590-599.

［2］Hwang，Y K，Ahuja N.A Potential Field Approach to Path Planning［J］.IEEE Transactions on Robotics and Automation （S1042-296X），1992，8（01）：23-32.

［3］稅薇，葛艷，韓玉.基于混合蟻群算法的無(wú)人機(jī)航路規(guī)劃，系統(tǒng)仿真學(xué)報(bào)，2011，30（04）：574-597.

［4］魚(yú)佳欣，周春來(lái)，劉東平.改進(jìn)遺傳算法的無(wú)人機(jī)航路規(guī)劃與仿真，計(jì)算機(jī)仿真，2013，30（12）：17-20.

［5］鄭銳，馮振明，陸明泉.基于遺傳算法的無(wú)人機(jī)航路規(guī)劃優(yōu)化研究，計(jì)算機(jī)仿真，2011，28（06）：88-91.

［6］邱小湖，邱永成.優(yōu)化蟻群算法在無(wú)人機(jī)航路規(guī)劃中的應(yīng)用，計(jì)算機(jī)仿真，2010，27（09）：102-105.

［7］華珊珊.無(wú)人機(jī)航路自動(dòng)規(guī)劃優(yōu)化方法研究與仿真，計(jì)算機(jī)仿真，2013，30（04）：45-48.

［8］YANG X S，DEB S.Cuckoo search via Levy flights［C］. proceedings of World Congress on nature & Biologically Inspired Computing，India：IEEE Publications，2009：210-214.

10.16640/j.cnki.37-1222/t.2016.20.129

鄭洪清（1978-），男，碩士，講師，研究方向?yàn)橛?jì)算智能技術(shù)與應(yīng)用。