基于混沌蜂群算法的USV 路徑規劃

蘭 瑩，章 甜

(上海海事大學，上海 201306)

0 引 言

路徑規劃通常分為兩類，一類是全局路徑規劃，即在已知的環境中，依照距離最短、能耗最低、耗時最短為目標，找到一條避開障礙物的最優路徑，全局最優的典型算法包括A*算法、D*算法等。二類是局部路徑規劃，即事先并不完全知道地圖環境，根據當前已探知的信息完成路徑選擇。近年來，不少學者將全局路徑優化算法與智能算法相結合，尤其是新興智能優化算法的使用。吳豐君[1]提出了基于協作思想的改進粒子群優化算法，鄭佳春等[2]提出一種基于混合模擬退火與粒子群優化的無人艇路徑規劃算法，倪生科等[3]提出一種基于混合遺傳算法的船舶避碰路徑規劃，YUE 等[4]介紹了一種基于蟻群算法的無人小車路徑規劃算法，王鵬等[5]提出一種混合自適應蟻群算法的AUV 路徑規劃方法，田屏[6]提出一種基于混沌搜索改進的人工蜂群算法。

人工蜂群算法（ABC）于2005 年由Karaborg 提出，在函數優化方面的效果明顯[7]，相比于上述優化算法，人工蜂群算法具有參數設置少、計算簡單、收斂快等特點。但同樣容易陷入局部最優，本文將基于人工蜂群算法結合Logistics 混沌映射產生雇傭蜂的混合算法，優化USV 作業路徑。

1 模型建立

為方便問題分析，對無人艇作以下假設：

1）船載監測設備已探知小船周圍障礙物位置；

2）無人艇行駛的環境為二維平面，忽略水面波浪所致小船起伏；

3）忽略障礙物高度，每一個障礙物占據一個二維柵格；

4）無人艇、目標點、障礙物位置均處于柵格中心點；

5）無人艇最大轉向角為45°。

而路徑規劃之前，通常要對無人艇的作業環境進行建模。常見的環境建模法包括頂點圖、鄰接圖、柵格法等，其中最為常見的即柵格法建模，通過柵格將地圖環境進行存儲，包括起點、終點、障礙點信息。柵格地圖的距離計算通常有3 種方式。

1）曼哈頓距離。曼哈頓距離即坐標系中兩點的絕對軸距之和，其表達式如下式：

2）切比雪夫距離。切比雪夫距離被稱為棋盤距離，其表達式下式：

3）歐幾里得距離。其值直接可以看作兩個位置點在歐式空間中的兩點的直線距離，其表達式如下式：

無人艇的最大轉向角設定為45°，曼哈頓距離只能支持橫向、縱向的移動，故距離計算選擇可以斜向行走的切比雪夫距離。

假設無人艇單位時間內移動的距離為R，則根據探測器探測范圍距離內的海域按柵格進行等距劃分，每一行、每一列的柵格數為：

其中：Ymax和Xmax分別為探測范圍內的縱向、橫向的最遠距離。

無人艇路徑規劃是避免碰撞的前提下，保證路徑長度最短，是一個典型的約束最優問題，數學模型描述如下：

約束條件[8]為 gi( X)≤0,i=1,2,···,p。

對于此類帶約束非線性最優化問題，可以將其轉化為無約束最優化問題，等價于一個能量優化函數E，其由路徑長度函數（Ei）和碰撞懲罰函數（Ec）組成。

含有N 個路徑節點的情況，路徑長度函數El為所有線段長度之和，即

碰撞懲罰函數Ec為無人小船在作業過程中，全部路徑節點的碰撞懲罰函數能量之和，即

其中權值 μl+ μc=1，目標函數為：

2 蜂群算法與改進

人工蜂群算法（Artificial Bee Colony Algorithm，ABC 算法）是一個由蜂群行為啟發的算法，在2005 年由Karaboga 小組為優化代數問題而提出。人工蜂群算法包含3 個基本元素：蜜源、雇傭蜂、偵察蜂[9]。其中蜜源代表問題解空間內的各種可行解，每個解是Xi(1,2···,m)一個D 維向量。雇傭蜂則是用來引領蜂群，并保存蜜源的相關信息，其數量和蜜源數量相等。偵察蜂則需要在蜜源附近隨機搜索新的蜜源，選中蜜源后，雇傭蜂繼續引領蜂群保存蜜源信息，并留下較優解。循環直至算法結束。

在標準人工蜂群中，蜜源更新位置公式如下：

式中： K ∈(1,2···,S N) ，SN 是種群規模，j ∈(1,2···,d)，即隨機選取下標。Rij是[-1，1]之間的隨機數。

偵察蜂的蜜源選擇概率公式：

針對傳統蜂群算法的不足，本文提出在信息素更新時引入混沌算子，通過混沌序列的全空間遍歷和變異操作的特性來增加算法種群多樣性，迭代后期則去除混沌擾動避免振蕩。

引入混沌序列對隨機數序列進行動態調整改進，目的是當一定參數設置下，混沌序列的輸出可以呈現完全無序，隨機，遍歷狀態，起源于蟲口模型的Logistic 混沌序列在 μ= 4 時（ μ為增長率），系統處于混沌工作狀態[10]，公式如下：

式中： τij(0) 為 初 值， τij(t)指算 法 在 第iter 次迭代時的值，根據混沌理論，當初值 τij(0)不等于0.25，0.5，0.75 時，序列完全處于混沌態，提高搜索多樣性。

圖1～圖4 為處于混沌狀態的隨機序列和特殊值下的混沌序列。

圖 1 μ=4 τ=0.3Fig.1 μ=4 τ=0.3

圖 2 μ=4 τ=0.6Fig.2 μ=4 τ=0.3

圖 3 μ=4 τ=0.9Fig.3 μ=4 τ=0.9

圖 4 μ=4 τ=0.25Fig.4 μ=4 τ=0.25

當雇傭蜂轉變為偵察蜂時，將產生一個D 維隨機向 量 τ0=[τ01,τ02,···τ0D]， τ0∈[0,1]并 不 等 于 特 殊 值。τ0作為初始值，由Logistic 混沌映射式得到蜜源附近多個鄰域解，從而得到經混沌操作后的新蜜源：

目的是 將 τij映射到 優化變量上，是在 雇傭蜂所在的蜜源為中心，以 Rij為半徑的區域上。算法流程圖如圖5 所示。

圖 5 算法流程圖Fig.5 Flow chart of algorithm

1）建立柵格化環境模型。

2）設置混合混沌ABC 算法的基本參數，包括種群大小，最大迭代次數itermax，當前迭代次數iter，蜜源數量。

3）雇傭蜂階段，根據蜜源更新公式隨機搜索附近新蜜源，貪心原則，選擇更優的蜜源位置。

4）偵察蜂階段，根據概率選擇公式，對雇傭蜂所分享的蜜源信息進行選擇。

5）偵察蜂階段，重新根據蜜源更新公式在新被選中的蜜源附近進行搜索，計算收益度，收益度高的置為當前蜜源，否則不變。

6）迭代進行，當蜜源未更新次數達到limit 值，雇傭蜂轉變為偵察蜂，利用混算搜索算子搜索新蜜源。

3 算法仿真

蜜源表示可能的最優解，即設置在Win10 環境下，基于Matlab2016b 安照表1 初始化數據進行仿真計算，結果如圖6～圖9 所示。

表 1 初始化數據Tab.1 Initialization data

圖 6 傳統ABC 算法路徑結果Fig.6 Path results of traditional ABC algorithm

圖 7 傳統ABC 算法迭代圖Fig.7 Iterative diagram of traditional ABC algorithm

圖 8 混沌ABC 算法路徑結果Fig.8 Path result of chaotic ABC algorithm

由圖6 和圖7 可以看出，改進后的混沌ABC 算法比傳統ABC 算法明顯降低了路徑長度。由圖8 和圖9可以看出，改進后的算法有效避免了ABC 算法的早熟收斂問題。

圖 9 混沌ABC 算法迭代圖Fig.9 Iterative diagram of chaotic ABC algorithm.

4 結 語

提出結合混沌局部搜索算法的改進人工蜂群算法，用以解決USV 的路徑規劃問題。該算法利用Logistcis 混沌序列的全空間遍歷特性避免ABC 算法陷入局部最優，從而快速找到全局最優解。算例測試表明，與傳統蜂群算法相比，改進后的算法在求解質量上有了提升，能夠有效解決傳統ABC 算法局部收斂的問題，避免早熟收斂，并能為無人艇規劃出一條可通行且較優的路徑。