基于優(yōu)化麻雀搜索算法的水下機器人路徑規(guī)劃研究*

周凱莉 劉從軍，2

（1.江蘇科技大學計算機學院 鎮(zhèn)江 212003）

（2.江蘇科大匯峰科技有限公司 鎮(zhèn)江 212003）

1 引言

水下機器人（ROV/AUV）是海洋工程、科學調(diào)查的載體，工作水深可達4000m，是水下作業(yè)的必要工具。考慮使用路徑規(guī)劃［1］為無人船進行深海作業(yè)規(guī)劃最優(yōu)化的路徑，提供便捷服務(wù)。

智能算法在求解路徑規(guī)劃問題時對全局探索和局部開發(fā)這兩個基本流程可以起到很好的平衡作用，因此，無數(shù)研究者采用多種不同的智能仿生算法，不斷創(chuàng)新改進，推動現(xiàn)實生產(chǎn)運用。王成等［2］優(yōu)化傳統(tǒng)的蟻群算法進行無人船路徑規(guī)劃，針對傳統(tǒng)的蟻群算法（ACO）的固有局限性，即前期搜索效率低、早熟性收斂。通過更新信息素濃度時加入權(quán)重因子，解決了過快收斂；對算法死鎖出現(xiàn)，采取減少死亡的螞蟻數(shù)量對死鎖點信息素進行懲罰。但該算法后期未解決種群多樣性與收斂速度的矛盾，全局尋優(yōu)能力仍可提高。劉洋等［3］改進的遺傳算法，以較高的成功率規(guī)劃出可行路徑，且產(chǎn)生路徑較短。但并未改進遺傳算法容易出現(xiàn)過早收斂的問題。虞馥澤等［4］將遺傳算法與蟻群算法融合，用遺傳算法獲得較優(yōu)路徑，并將其用作蟻群算法的初始信息素設(shè)置，以引導(dǎo)蟻群算法進行更進一步的優(yōu)化搜索。其收斂性是要好于傳統(tǒng)的單一算法，尋優(yōu)效果與收斂性仍有提升的空間。

麻雀搜索算法（Sparrow Search Algorithm，SSA）是基于麻雀尋找食物行為的啟發(fā)式算法，應(yīng)用于路徑規(guī)劃時具有適用性強、參數(shù)少、全局搜索能力強、問題求解的快速性、全局優(yōu)化特征、早熟性收斂等優(yōu)點。薛建凱等［5］首次探討相應(yīng)規(guī)則并構(gòu)建數(shù)學模型，概括算法實施過程。該文實驗結(jié)論表明麻雀搜索算法具備自適應(yīng)性、高效性、魯棒性，對大規(guī)模路徑規(guī)劃問題和實時路徑規(guī)劃問題非常可行。湯安迪等［6］在薛建凱［5］的基礎(chǔ)上表示算法在迭代后期，由于種群多樣性降低，可能導(dǎo)致收斂速度和精度下降，進而陷入局部最優(yōu)解。采用立方映射混沌算子創(chuàng)建初始種群，為縮小搜索空間，加快收斂。利用反向選擇策略生成初始反向解，將其加入初始種群。此外，為減少算法陷入停滯的概率，使用高斯隨機游走策略生成新個體有助于避免出局部最優(yōu)解。

由于上述文獻中的群智能仿生算法實現(xiàn)路徑規(guī)劃都存在一些弊端，結(jié)合文獻［5］和文獻［6］，將麻雀算法適當優(yōu)化：如選擇Tent映射初始化麻雀種群，采用自適應(yīng)調(diào)整慣性權(quán)重策略［7］，通過增大或減小慣性權(quán)重值，最終提高全局搜索能力和收斂速度，提高求解的精度。同時考慮到算法后期的停滯問題，添加柯西變異來增加種群的多樣性。

2 路徑規(guī)劃模型

2.1 環(huán)境建模

下水機器人在進行水下作業(yè)需要實時的進行路徑規(guī)劃，首先需對工作區(qū)的環(huán)境進行建模［8］。選擇柵格法進行環(huán)境模擬，建立柵格地圖，假設(shè)當環(huán)境中的元素屬于自由區(qū)的面積大于障礙區(qū)域，則該象元取值為0，否則為1。其中自由柵格為白色，障礙柵格表示為黑色。將黑色象元用數(shù)字1 表示，白色象元用0 表示。最后采用序號法對每個柵格進行編號，順序從前往后，從上到下。圖1 為二維電子地圖，圖2 為二維柵格地圖，用柵格法表示的整個環(huán)境編號圖如圖3。

圖1 二維電子地圖

圖2 二維柵格地圖

圖3 二維柵格地圖

圖4 ISSA流程圖

定義初始柵格坐標為（1，1），g為任意柵格，f為所有柵格集合，記作f=｛g（1，1），g（1，2）…g（x，y）｝。

其中，a為柵格步長，在x，y方向上最大值分別為xmax，ymax，則每行柵格個數(shù)Nx與每列柵格數(shù)Ny如式（1）所示。

n為柵格的序號，柵格號與序號的關(guān)系如式（2）所示。

2.2 建立目標函數(shù)

模擬柵格地圖，最終目的是使水下機器人在安全的情況下找到最短的線路達到終點，問題轉(zhuǎn)化為求以下函數(shù)（3）的最小值。

3 基于優(yōu)化麻雀搜索算法的路徑規(guī)劃算法

3.1 麻雀搜索算法

麻雀搜索算法（Sparrow-Search-Algorithm，SSA）屬于智能仿生算法分支下的粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）［9～10］，但是能克服PSO 算法中一些局限性，如PSO 算法參數(shù)設(shè)定通常由實驗方法確定，導(dǎo)致方法的優(yōu)化性能與人的經(jīng)驗關(guān)系密切。麻雀搜索算法可以說是一種粒子群算法的改進，為算法性能最優(yōu)化提供了可能。

麻雀是雀科，一種小型鳥類的統(tǒng)稱。屬于一種群居雜食性鳥類，每次聚集十幾只或幾十只。規(guī)定由N只麻雀組成的種群，表示形式如式（4），該麻雀種群中的行為可以分為三類：搜索食物的發(fā)現(xiàn)者、跟隨者和警戒偵查者。發(fā)現(xiàn)者負責尋找食物，跟隨者會加入發(fā)現(xiàn)者的行列并向其移動以覓食，警戒偵查者負責發(fā)出危險警報。麻雀的總體比例不變，行為身份根據(jù)情況轉(zhuǎn)換。一旦偵查者警報，跟隨者會迅速散開到安全區(qū)域，而發(fā)現(xiàn)者會在群體中間隨機移動，靠近安全區(qū)域的跟隨者。

3.1.1 更新發(fā)現(xiàn)者位置

更新發(fā)現(xiàn)者位置是指根據(jù)當前搜索狀態(tài)，每個發(fā)現(xiàn)者的適應(yīng)度值的變化更新發(fā)現(xiàn)者的位置，更好地搜索目標，說明見式（5）。

上述公式［11］的描述中：當前迭代次數(shù)t，最大迭代次數(shù)itermax，第t次迭代時的第i個麻雀個體在第j維中的位置信息Xij；隨機數(shù)α∈（0，1）；每個因子均為1 的l×d矩陣L；方差為1 的正態(tài)分布的隨機數(shù)Q。

預(yù)警值R2∈（0，1）；預(yù)警安全值ST∈（0.5，1）。若R2＜ST，未發(fā)現(xiàn)捕食者，種群狀態(tài)安全，發(fā)現(xiàn)者將按正態(tài)分布隨機移動到當前位置附近。若R2≥ST，表示部分個體發(fā)現(xiàn)或遭遇捕食者。迭代過程中的發(fā)現(xiàn)者圍繞當前位置移動，移動范圍表示如式（6），其中，Y為移動位置值的變化范圍。

3.1.2 更新跟隨者位置

在SSA 中，跟隨者的位置可以根據(jù)發(fā)現(xiàn)者的位置和行為進行更新。跟隨者根據(jù)距離和方向來決定跟隨者的移動方式，發(fā)現(xiàn)者位置在迭代過程中更新如式（7）。

其中，Xbest為發(fā)現(xiàn)者所在位置，即當前最佳覓食地區(qū)；Xworst為當前糟糕位置。A為一個d×d矩陣，其中每個元素隨機分配1或者-1。若i≤n/2時，表示第i個跟隨者在附近覓食最佳區(qū)域，如果i＞n/2，表示適應(yīng)度低于第i個跟隨者沒有找的食物，需要飛到其它地方，提高適應(yīng)度值。

3.1.3 預(yù)警行為

在麻雀群體中，存在一個預(yù)警機制。大約有10%～30%的麻雀判斷是否需要發(fā)出預(yù)警信號，以采取某種行動以改變搜索策略。根據(jù)式（8）中的位置更新，警戒者的位置會進行相應(yīng)的調(diào)整。

其中，β為隨機步長控制系數(shù)，服從方差為1，均值為0 的正態(tài)分布［12］；K為隨機數(shù)，且K∈［-1，1］；第i個麻雀個體的適應(yīng)度值fi；當前最佳適應(yīng)度值fg；當前最糟糕的適應(yīng)度值fw；ε表示最小的參數(shù)，以避免分母為零。

3.2 優(yōu)化麻雀搜索算法

麻雀算法SSA 屬于啟發(fā)式算法之一，與人工蟻群算法結(jié)構(gòu)相似，具有良好的魯棒性和快速收斂性，綜合性能較好。它需要解決的問題與人工蟻群算法類似，例如平衡局部搜索和全局搜索，以盡量有效地避免陷入局部最優(yōu)解。為了進一步提高麻雀搜索算法的能力，采取一些優(yōu)化策略。

3.2.1 Tent混沌映射

混沌運動的特點可以用來提高算法的尋優(yōu)效率，在啟發(fā)式算法中得到廣泛應(yīng)用。優(yōu)化變量通過混沌映射線性地映射到混沌變量中［13］，然后根據(jù)混沌的遍歷性和隨機性進行優(yōu)化搜索。最后，將得到的解線性地轉(zhuǎn)化回優(yōu)化變量空間［14］。

伯努利變換基于伯努利分布進行二值轉(zhuǎn)換，根據(jù)某個概率閾值決定轉(zhuǎn)換的結(jié)果。將Tent 映射混沌和伯努利變換結(jié)合，可以產(chǎn)生一種混沌序列，在一定程度上增加隨機性。Tent 混沌映射的式（9），結(jié)合伯努利變換產(chǎn)生式（10）。

3.2.2 自適應(yīng)調(diào)整慣性權(quán)重策略

定義第i個麻雀在第j維上個體的搜索能力如式（11）所示。

從式（11）可以看出，如果Xij距x*較遠，且x*距Xbest較近，則ISA 的值較大。表明此時全局搜索能力較強，應(yīng)該適當減小慣性權(quán)重，增強局部搜索能力。如果Xij距x*較近，x*距Xbest較遠，則ISA的值較小，說明局部搜索能力較強，應(yīng)該增大慣性權(quán)重以提高全局搜索能力。

通過自適應(yīng)地調(diào)整慣性權(quán)重，算法可以在搜索的不同階段靈活地調(diào)整搜索行為，公式如式（12）所示。參數(shù)α∈（0，1］，本文將α設(shè)為常量0.3。在式（3）中引入自適應(yīng)慣量，重新更新發(fā)現(xiàn)者的位置，得到式（13）。

3.2.3 解決算法停滯問題

采用柯西變異［15］來增加種群的多樣性和搜索空間。選擇當前適應(yīng)度最佳的個體進行突變，并比較突變前后的位置，選擇較好的位置進行下一次迭代，表達式如式（14）。

3.3 優(yōu)化麻雀搜索算法流程

步驟1 根據(jù)工作環(huán)境的起始點與終點，確定水下機器人的工作區(qū)域；

步驟2 根據(jù)柵格法對水下機器人工作區(qū)域進行環(huán)境建模；

步驟3 隨機初始化麻雀種群，同時定義最大迭代次數(shù)，設(shè)置安全閾值；

步驟4 根據(jù)機器人工作的起始點，初始化種群，包括設(shè)定麻雀發(fā)現(xiàn)者和跟隨者的數(shù)量，以及預(yù)警偵查麻雀的占比。然后計算初始種群的適應(yīng)度，并對其進行排序，以選擇當前的最優(yōu)值與最差值；

步驟5 規(guī)劃麻雀搜索的路徑，根據(jù)式（11），更新發(fā)現(xiàn)者的位置；根據(jù)式（7），更新跟隨者的位置；根據(jù)式（8），更新警戒者的位置；

步驟6 更新路徑，如果本次結(jié)果優(yōu)于之前，則重新構(gòu)建新的路徑得到最佳情況；

步驟7 判斷算法是否進入停滯，重新將最優(yōu)個體進行柯西變異，重新初始化，循環(huán)；

步驟8 判斷是否達到最大迭代次數(shù)，若沒有，跳轉(zhuǎn)到步驟5；否則繼續(xù)下一步；

步驟9 搜索完成，輸出最優(yōu)結(jié)果，算法結(jié)束。

4 仿真與實驗

4.1 實驗環(huán)境與條件假設(shè)

為驗證該算法的具有實踐的可行性，選擇傳統(tǒng)的麻雀搜索SSA 文獻［5］進行對比仿真實驗，實驗結(jié)果驗證了優(yōu)化的麻雀算法ISSA的優(yōu)越性。

工作環(huán)境描述如下：障礙物為海面上的靜態(tài)其他船舶、深海暗礁、沉積物以及淺灘等。作業(yè)環(huán)境一：大小為20*20，起始點坐標為（0.5，0.5），終點坐標為（19.5，19.5），作業(yè)環(huán)境的柵格圖中柵格邊長為1。作業(yè)環(huán)境二：大小為30*30，起始點坐標為（0.5，0.5），終點坐標為（29.5，29.5），作業(yè)環(huán)境的柵格圖中柵格邊長為1。

設(shè)置本文算法與文獻［5］提出的算法，種群數(shù)量為50，安全值為0.8，發(fā)現(xiàn)者與跟隨者的比例分別的0.3，0.2。遵循公平性原則，最大迭代次數(shù)都是100次，如表1所示。

表1 麻雀搜索算法參數(shù)設(shè)置

4.2 實驗過程

4.2.1 作業(yè)環(huán)境一下的規(guī)劃對比

采用大小為20*20，起始點坐標為（0.5，0.5），終點坐標為（19.5，19.5），柵格圖中柵格邊長為1，深色的方格代表障礙區(qū)域，白色的方格代表自有可行區(qū)域。保持兩種算法的參數(shù)不變，進行100 次實驗，與文獻［5］SSA進行對比。圖5為SSA的路徑最佳規(guī)劃方案，圖6 為ISSA 的路徑最佳規(guī)劃方案，具體數(shù)據(jù)如表2所示。

表2 兩種算法在環(huán)境一中路徑規(guī)劃的結(jié)果比較

圖5 環(huán)境一SSA規(guī)劃方案

圖6 環(huán)境一ISSA規(guī)劃方案

由表2得出，本文優(yōu)化的ISSA的平均最短路徑為29.4587，優(yōu)于傳統(tǒng)SSA 平均最短路徑29.7915，降低了1.11%。在收斂次數(shù)方面，本文算法經(jīng)過15.367次迭代后就趨于收斂，且收斂路徑平均值為29.636；而文獻［5］經(jīng)過22.965 次才開始收斂，收斂路徑平均值為29.965，收斂路徑平均值降低了1.09 %，收斂迭代次數(shù)下降了33.1%。

4.2.2 作業(yè)環(huán)境二下的規(guī)劃對比

采用大小為30*30，起始點坐標為（0.5，0.5），終點坐標為（29.5，29.5），柵格圖中柵格邊長依然為1，深色的方格代表障礙區(qū)域，白色的方格代表自有可行區(qū)域。保持兩種算法的參數(shù)不變，進行100 次實驗，與文獻［5］SSA進行對比。圖7為SSA的路徑最佳規(guī)劃方案，圖8 為ISSA 的路徑最佳規(guī)劃方案，具體數(shù)據(jù)如表3所示。

表3 兩種算法在環(huán)境二中路徑規(guī)劃的結(jié)果比較

圖7 環(huán)境二SSA規(guī)劃方案

圖8 環(huán)境二SSA規(guī)劃方案

由表3得出，本文優(yōu)化的ISSA的平均最短路徑為45.7705，優(yōu)于傳統(tǒng)的SSA 平均最短路徑47.0178降低了2.65%。在平均收斂迭代次數(shù)方面，本文算法經(jīng)18.3741 次迭代后就趨于收斂，收斂路徑平均值47.0631；文獻［5］經(jīng)過26.2365 次才開始收斂，收斂路徑平均值48.5698。收斂路徑平均值降低了3.10%，平均收斂迭代次數(shù)下降了36.07%。

4.3 結(jié)果分析

綜上所述，本文優(yōu)化的麻雀搜索算法ISSA 與文獻［5］SSA 算法在兩種環(huán)境下進行100 次實驗比對，結(jié)果顯示ISSA 算法在在程序運行耗時，最短路徑、平均最短路徑、收斂路徑平均迭代次數(shù)、收斂路徑平均值等方面相較于SSA 算法優(yōu)勢明顯。并隨著環(huán)境的復(fù)雜程度增加，本文算法在上述方面的優(yōu)勢相對文獻［5］的SSA算法優(yōu)勢更加明顯。

5 結(jié)語

規(guī)劃出一條從初始點到終點的最優(yōu)路徑是解決水下機器人工作的先行問題，路徑的選擇，確保作業(yè)的效率。在分析群智能仿生算法的基礎(chǔ)上，針對群智能仿生算法搜索效率低、收斂速度慢等問題，本文提出了一種優(yōu)化的麻雀算法，該算法具有以下優(yōu)點：

1）新穎簡單，麻雀算法通過麻雀搜索食物與反捕食的過程，進行各類種群的更新。

2）引入Tent映射初始化麻雀種群，以此保證初始種群個體自隨機性，增加多樣性，提高ISSA 算法的收斂速度。

3）通過自適應(yīng)調(diào)整慣性權(quán)重策略平衡麻雀個體的局部搜索能力和全局搜索能力。同時增大或減小慣性權(quán)重值調(diào)整收斂速度，改善算法的精度。

4）添加柯西變異來增加種群的多樣性，提高算法的穩(wěn)定性。

通過實驗，將文本算法ISSA 與傳統(tǒng)SSA 進行了比較，實驗結(jié)果驗證了ISSA 在尋優(yōu)過程中擁有一定的優(yōu)越性，表明具有實際應(yīng)用的可行性。下一步的工作重點為研究麻雀算法運用在三維路徑規(guī)劃方面，并考慮對動態(tài)避障的可操作性。