改進CS算法在無人機航路規劃中的應用

鄭洪清

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

改進CS算法在無人機航路規劃中的應用

鄭洪清

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

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

無人機；布谷鳥搜索算法；航路規劃

1 引言

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

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

2 航路規劃問題

2.1 飛行環境和任務描述

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

2.2 航路編碼

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

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

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

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

方向節點集合w=｛1，2，…，m｝，m為移動方向的數目，故從起點到目標點航路以方向的形式表示為：

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

2.3 編碼修正

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

算法1：修正初始解

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

2.4 解碼

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

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

2.5 航路性能評價

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

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

它與航程Li是成正比；

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

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

3 基于CS算法的無人機航路規劃

3.1 基本CS算法

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

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

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

3.2 改進的CS算法

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

其中stepsize 為（5）式Levy飛行所產生的步長，m為方向的個數。

3.3 算法步驟

步驟1：將飛行區域柵格化并轉化為0-1矩陣。

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

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

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

步驟5：用公式（3）計算當前的最優值fmin及最優解fbest。

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

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

步驟8：判斷循環是否結束，如果是，根據算法（7）進行解碼，輸出航路點信息；否則跳轉步驟6。

4 仿真實例與分析

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

實驗一：4個威脅區域

對于不規則的4個威脅區域，其實驗結果如圖4所示。

實驗二：11個威脅區域

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

5 結束語

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

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

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

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

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

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