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

鄭洪清

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

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

鄭洪清

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

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

無人機；布谷鳥搜索算法；航路規(guī)劃

1 引言

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

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

2 航路規(guī)劃問題

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

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

2.2 航路編碼

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

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

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

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

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

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

2.3 編碼修正

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

算法1：修正初始解

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

2.4 解碼

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

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

2.5 航路性能評價

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

為第i段航路的耗油代價，

它與航程Li是成正比；

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

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

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

3.1 基本CS算法

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

布谷鳥尋窩的路徑和位置更新公式如下：

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

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

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

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

3.3 算法步驟

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

步驟2：由0-1矩陣判斷無人機在每一個柵格的飛行方向，求出其方向矩陣。

步驟3：隨機生成1-m個方向作為鳥巢nest的初始解。

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

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

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

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

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

4 仿真實例與分析

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

實驗一：4個威脅區(qū)域

對于不規(guī)則的4個威脅區(qū)域，其實驗結(jié)果如圖4所示。

實驗二：11個威脅區(qū)域

這里對威脅區(qū)域采取近似圓表示，半徑為威脅區(qū)域的有效距離，圓內(nèi)為威脅區(qū)。設(shè)威脅點坐標(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）。實驗結(jié)果如圖6所示。從圖4和圖6不難發(fā)現(xiàn)，采用改進(jìn)的布谷鳥搜索算法能夠規(guī)避風(fēng)險，安全快速到達(dá)目的地，并且提高了路徑規(guī)劃的成功率，算法更加穩(wěn)定。仿真結(jié)果表明本規(guī)劃算法設(shè)計的航線是可行的，但由于航路的拐角太多，不利于無人機的飛行，故對航路進(jìn)行了B樣條函數(shù)處理后的結(jié)果如圖5和圖7所示。

5 結(jié)束語

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

［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］稅薇，葛艷，韓玉.基于混合蟻群算法的無人機航路規(guī)劃，系統(tǒng)仿真學(xué)報，2011，30（04）：574-597.

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

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

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

［7］華珊珊.無人機航路自動規(guī)劃優(yōu)化方法研究與仿真，計算機仿真，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-），男，碩士，講師，研究方向為計算智能技術(shù)與應(yīng)用。