蘭 瑩，章 甜

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

0 引 言

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

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

1 模型建立

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

1）船載監(jiān)測設(shè)備已探知小船周圍障礙物位置；

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

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

4）無人艇、目標(biāo)點(diǎn)、障礙物位置均處于柵格中心點(diǎn)；

5）無人艇最大轉(zhuǎn)向角為45°。

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

1）曼哈頓距離。曼哈頓距離即坐標(biāo)系中兩點(diǎn)的絕對軸距之和，其表達(dá)式如下式：

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

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

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

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

其中：Ymax和Xmax分別為探測范圍內(nèi)的縱向、橫向的最遠(yuǎn)距離。

無人艇路徑規(guī)劃是避免碰撞的前提下，保證路徑長度最短，是一個典型的約束最優(yōu)問題，數(shù)學(xué)模型描述如下：

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

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

含有N 個路徑節(jié)點(diǎn)的情況，路徑長度函數(shù)El為所有線段長度之和，即

碰撞懲罰函數(shù)Ec為無人小船在作業(yè)過程中，全部路徑節(jié)點(diǎn)的碰撞懲罰函數(shù)能量之和，即

其中權(quán)值 μl+ μc=1，目標(biāo)函數(shù)為：

2 蜂群算法與改進(jìn)

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

在標(biāo)準(zhǔn)人工蜂群中，蜜源更新位置公式如下：

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

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

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

引入混沌序列對隨機(jī)數(shù)序列進(jìn)行動態(tài)調(diào)整改進(jìn)，目的是當(dāng)一定參數(shù)設(shè)置下，混沌序列的輸出可以呈現(xiàn)完全無序，隨機(jī)，遍歷狀態(tài)，起源于蟲口模型的Logistic 混沌序列在 μ= 4 時（ μ為增長率），系統(tǒng)處于混沌工作狀態(tài)[10]，公式如下：

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

圖1～圖4 為處于混沌狀態(tài)的隨機(jī)序列和特殊值下的混沌序列。

圖 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āng)雇傭蜂轉(zhuǎn)變?yōu)閭刹旆鋾r，將產(chǎn)生一個D 維隨機(jī)向 量 τ0=[τ01,τ02,···τ0D]， τ0∈[0,1]并 不 等 于 特 殊 值。τ0作為初始值，由Logistic 混沌映射式得到蜜源附近多個鄰域解，從而得到經(jīng)混沌操作后的新蜜源：

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

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

1）建立柵格化環(huán)境模型。

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

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

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

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

6）迭代進(jìn)行，當(dāng)蜜源未更新次數(shù)達(dá)到limit 值，雇傭蜂轉(zhuǎn)變?yōu)閭刹旆?，利用混算搜索算子搜索新蜜源?/p>

3 算法仿真

蜜源表示可能的最優(yōu)解，即設(shè)置在Win10 環(huán)境下，基于Matlab2016b 安照表1 初始化數(shù)據(jù)進(jìn)行仿真計算，結(jié)果如圖6～圖9 所示。

表 1 初始化數(shù)據(jù)Tab.1 Initialization data

圖 6 傳統(tǒng)ABC 算法路徑結(jié)果Fig.6 Path results of traditional ABC algorithm

圖 7 傳統(tǒng)ABC 算法迭代圖Fig.7 Iterative diagram of traditional ABC algorithm

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

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

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

4 結(jié) 語

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