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

周凱莉 劉從軍，2

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

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

1 引言

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

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

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

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

2 路徑規(guī)劃模型

2.1 環(huán)境建模

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

圖1 二維電子地圖

圖2 二維柵格地圖

圖3 二維柵格地圖

圖4 ISSA流程圖

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

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

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

2.2 建立目標(biāo)函數(shù)

模擬柵格地圖，最終目的是使水下機(jī)器人在安全的情況下找到最短的線路達(dá)到終點(diǎn)，問(wèn)題轉(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è)定通常由實(shí)驗(yàn)方法確定，導(dǎo)致方法的優(yōu)化性能與人的經(jīng)驗(yàn)關(guān)系密切。麻雀搜索算法可以說(shuō)是一種粒子群算法的改進(jìn)，為算法性能最優(yōu)化提供了可能。

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

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

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

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

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

3.1.2 更新跟隨者位置

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

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

3.1.3 預(yù)警行為

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

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

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

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

3.2.1 Tent混沌映射

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

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

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

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

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

通過(guò)自適應(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 解決算法停滯問(wèn)題

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

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

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

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

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

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

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

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

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

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

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

4 仿真與實(shí)驗(yàn)

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

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

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

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

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

4.2 實(shí)驗(yàn)過(guò)程

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

采用大小為20*20，起始點(diǎn)坐標(biāo)為（0.5，0.5），終點(diǎn)坐標(biāo)為（19.5，19.5），柵格圖中柵格邊長(zhǎng)為1，深色的方格代表障礙區(qū)域，白色的方格代表自有可行區(qū)域。保持兩種算法的參數(shù)不變，進(jìn)行100 次實(shí)驗(yàn)，與文獻(xiàn)［5］SSA進(jìn)行對(duì)比。圖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)過(guò)15.367次迭代后就趨于收斂，且收斂路徑平均值為29.636；而文獻(xiàn)［5］經(jīng)過(guò)22.965 次才開(kāi)始收斂，收斂路徑平均值為29.965，收斂路徑平均值降低了1.09 %，收斂迭代次數(shù)下降了33.1%。

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

采用大小為30*30，起始點(diǎn)坐標(biāo)為（0.5，0.5），終點(diǎn)坐標(biāo)為（29.5，29.5），柵格圖中柵格邊長(zhǎng)依然為1，深色的方格代表障礙區(qū)域，白色的方格代表自有可行區(qū)域。保持兩種算法的參數(shù)不變，進(jìn)行100 次實(shí)驗(yàn)，與文獻(xiàn)［5］SSA進(jìn)行對(duì)比。圖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；文獻(xiàn)［5］經(jīng)過(guò)26.2365 次才開(kāi)始收斂，收斂路徑平均值48.5698。收斂路徑平均值降低了3.10%，平均收斂迭代次數(shù)下降了36.07%。

4.3 結(jié)果分析

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

5 結(jié)語(yǔ)

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

1）新穎簡(jiǎn)單，麻雀算法通過(guò)麻雀搜索食物與反捕食的過(guò)程，進(jìn)行各類種群的更新。

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

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

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

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