基于改進(jìn)麻雀搜索算法的機(jī)器人路徑規(guī)劃

摘要：針對(duì)麻雀搜索算法（Sparrow Search Algorithm，SSA）在機(jī)器人路徑規(guī)劃上存在的搜索精度不足和搜索速度較慢的問題，文章提出一種改進(jìn)的麻雀搜索算法（Improved Sparrow Search Algorithm， ISSA）。在ISSA中，引入Levy飛行策略和正余弦策略來優(yōu)化傳統(tǒng)SSA出現(xiàn)的極易陷入局部最優(yōu)值、收斂速度慢等問題。在MATLAB 2022b軟件平臺(tái)上，利用不同形式的柵格地圖來從算法的適應(yīng)度、路徑規(guī)劃的長度進(jìn)行仿真驗(yàn)證。仿真結(jié)果表明，使用ISSA規(guī)劃機(jī)器人最優(yōu)路徑時(shí)，路徑規(guī)劃的距離分別可以縮短1.3571 m、2.6924 m和9.8786 m，從效率上分別提升了4.5%、8.2%和13.7%。

關(guān)鍵詞：麻雀搜索算法；路徑規(guī)劃；Levy飛行策略；正余弦策略

中圖分類號(hào)：TP311.1 文獻(xiàn)標(biāo)志碼：A

0 引言

近年來，機(jī)器人路徑規(guī)劃已經(jīng)成為一個(gè)研究熱點(diǎn)［1］。通過優(yōu)化機(jī)器人的路徑規(guī)劃算法，可以進(jìn)一步提升機(jī)器人的自主導(dǎo)航和決策能力，從而實(shí)現(xiàn)更高效、更智能的工作任務(wù)執(zhí)行［2］。目前，優(yōu)化路徑規(guī)劃算法的應(yīng)用已相當(dāng)廣泛，一種智能仿生算法在眾多算法中脫穎而出，成為目前解決路徑規(guī)劃的第一選擇［3］。本文將重點(diǎn)研究這類智能仿生算法中的SSA，通過仿生學(xué)原理，模擬麻雀覓食行為的特點(diǎn)，提高機(jī)器人路徑規(guī)劃的效率。

在對(duì)SSA算法進(jìn)行運(yùn)用時(shí)，會(huì)發(fā)現(xiàn)其具體缺點(diǎn)［4-7］。SSA算法計(jì)算量較大，收斂速度較慢，且在搜索過程中容易陷入局部最優(yōu)。這些問題限制了SSA算法在復(fù)雜路徑規(guī)劃問題中的應(yīng)用效果，須進(jìn)一步改進(jìn)和優(yōu)化。本文在SSA算法的基礎(chǔ)上引入了Levy飛行策略和正余弦策略，以此來解決SSA算法易于陷入局部最優(yōu)和收斂速度緩慢的問題，縮短機(jī)器人在路徑規(guī)劃中的行駛距離，提升路徑規(guī)劃的效率。這一改進(jìn)不僅能夠提升機(jī)器人的工作性能，還有助于提高整個(gè)系統(tǒng)的效率和響應(yīng)速度。

1 柵格地圖

本文為了更好地驗(yàn)證優(yōu)化后的SSA算法，將利用不同大小的柵格地圖進(jìn)行測試。如圖1所示，柵格地圖中有黑色和白色方格［8］，黑色方格表示障礙物，機(jī)器人不可通過，白色方格則可以自由通行。

2 改進(jìn)的麻雀優(yōu)化算法

2.1 麻雀算法描述

麻雀種群覓食時(shí)的特點(diǎn)主要包括以下幾點(diǎn)［9］：

（1）麻雀種群分為2類，分別是發(fā)現(xiàn)者、跟隨者；

（2）發(fā)現(xiàn)者是位于食物資源較多位置的麻雀，并決定種群的搜索方向。發(fā)現(xiàn)者占整個(gè)種群的10%～30%；

（3）跟隨者是為了食物不斷靠近發(fā)現(xiàn)者的麻雀；

（4）發(fā)現(xiàn)者和跟隨者的身份不是固定的，當(dāng)跟隨者所處位置的食物較多時(shí)，身份就會(huì)轉(zhuǎn)變。但發(fā)現(xiàn)者和跟隨者所占比例不變；

（5）發(fā)現(xiàn)者和跟隨者中有部分麻雀負(fù)責(zé)偵查警戒，當(dāng)預(yù)警值大于安全值時(shí)就會(huì)發(fā)出警報(bào)，并帶領(lǐng)種群離開危險(xiǎn)區(qū)域。

倘若在d維搜索空間中有m只麻雀在尋找食物，麻雀的位置可以描述為［10］：

式（1）中，gi，k（i=1，2，3，…，d）是第i只麻雀位置的第k維分量。麻雀適應(yīng)度值的大小表示該麻雀所處位置的食物量，適應(yīng)度值越小，食物越多。適應(yīng)度值可以表示為：

式（2）中，F(xiàn)G代表麻雀種群的適應(yīng)度值；Fi=f（［gi，1，gi，2，…，gi，d］）（i=1，2，3，…，m）是第i只麻雀的適應(yīng)度值。依據(jù)適應(yīng)度值將麻雀種群進(jìn)行從小到大排序，發(fā)現(xiàn)者的適應(yīng)度值較小，占種群的10%～30%。發(fā)現(xiàn)者的位置公式為：

式（3）中，r是迭代次數(shù)；Gri，k（i=1，2，3，…，d）代表在第r次迭代期間，第i只麻雀的第k維分量；θ∈［0，1］和Ra∈［0，1］是服從均勻分布的隨機(jī)數(shù)；Ra代表警報(bào)值；itermax是最大迭代次數(shù)；TH∈［0.5，1.0］是安全閾值；Gu是服從標(biāo)準(zhǔn)正態(tài)分布的隨機(jī)矩陣。

跟隨者的適應(yīng)度值較大，所處位置食物較少，其位置公式為：

式（4）中，Grworst表示第r次迭代，適應(yīng)度值最大的麻雀位置；v是一個(gè)1×d的單位向量；Gr+1best表示下一次迭代時(shí)，適應(yīng)度值最小的麻雀位置；C是1×d的向量，其元素從集合｛-1，1｝中隨機(jī)取值；C+=CT（CCT）-1。

此外，一旦麻雀察覺到潛在危險(xiǎn)時(shí)，會(huì)展現(xiàn)出反捕食行為，它們被叫作警戒者，警戒者的位置公式為：

式（5）中，Grbest是此次迭代的最佳位置；φ是服從標(biāo)準(zhǔn)正態(tài)分布的隨機(jī)數(shù)，負(fù)責(zé)控制步長；ω∈［0，1］是服從均勻分布的隨機(jī)數(shù)；Fi是第i只麻雀的適應(yīng)度值；Fworst和Fbest分別是全局最大適應(yīng)度值和全局最小適應(yīng)度值；μ是一個(gè)無窮小常數(shù)，用來防止更新公式分母為0。

2.2 引入Levy飛行策略

為改進(jìn)SSA算法陷入局部最優(yōu)的問題，本文將Levy飛行策略引入到麻雀警戒者的公式中［11］，以此降低麻雀陷入局部最優(yōu)的風(fēng)險(xiǎn)，且不影響局部搜索操作，從而提高算法尋優(yōu)能力和跳出局部極值的能力。警戒者位置更新公式如下［12］：

2.3 引入正余弦策略

針對(duì)SSA算法收斂速度慢的現(xiàn)象，本文在發(fā)現(xiàn)者的位置更新公式中引入正余弦算法（Sine Cosine Algorithm，SCA），將正余弦模型振蕩變化特性作用于發(fā)現(xiàn)者的更新位置，提高SSA算法的全局搜索能力［13］。基本的正余弦算法的步長搜索因子公式為：

r1=a-ar/itermax（7）

式（7）中，a為常數(shù)，本文設(shè)置為1；r為當(dāng)前迭代次數(shù)；itermax為最大迭代次數(shù)。步長搜索因子r1呈線性遞減趨勢(shì)［14］。

為了更好地對(duì)SSA算法進(jìn)行優(yōu)化，本文將步長搜索因子分成2個(gè)部分，前一個(gè)部分用于SSA算法前期的尋優(yōu)，后一部分用于SSA算法后期的尋優(yōu)。前期尋優(yōu)和后期尋優(yōu)時(shí)使用的步長搜索因子公式分別為：

式（8）和式（9）中，η為調(diào)節(jié)系數(shù)，η≥1；α=1；itermax為最大迭代次數(shù)。

將上述優(yōu)化的步長搜索因子引入SSA，得到新的發(fā)現(xiàn)者位置更新公式為：

式（10）中，r2∈［0，2π］，是一個(gè)隨機(jī)數(shù)，表示麻雀的移動(dòng)距離；r3∈［0，2］，是一個(gè)隨機(jī)數(shù)，表示最優(yōu)位置對(duì)下一個(gè)位置的影響度。

2.4 ISSA算法執(zhí)行步驟

本文提出的改進(jìn)SSA算法的流程如圖2所示。

具體步驟如下。

步驟1：對(duì)ISSA算法中的參數(shù)進(jìn)行初始化，并設(shè)置麻雀種群的大小，將部分種群劃分為發(fā)現(xiàn)者和跟隨者，給出初始位置，迭代次數(shù)設(shè)置為r=1；

步驟2：計(jì)算每個(gè)麻雀的目標(biāo)函數(shù)，即適應(yīng)度值；

步驟3：使用式（4）、式（6）和式（10）更新麻雀發(fā)現(xiàn)者、跟隨者和警戒者的位置；

步驟4：判斷是否達(dá)到最優(yōu)解，如果沒有達(dá)到，則返回步驟2，如果已經(jīng)達(dá)到，則輸出最優(yōu)解并結(jié)束。

3 試驗(yàn)仿真與分析

為了驗(yàn)證本文對(duì)SSA算法改進(jìn)的效果，在不同的柵格地圖上進(jìn)行SSA和ISSA的仿真試驗(yàn)，柵格地圖由面積為1 m2的正方形構(gòu)成。本文采用的柵格環(huán)境均是以校園的建筑物和道路的狀況為基礎(chǔ)而建立的。試驗(yàn)仿真在MATLAB 2022b軟件中實(shí)現(xiàn)。

本文選用了2種尺寸的柵格地圖，分別是20 m×20 m的柵格地圖和40 m×40 m的柵格地圖，在這2種柵格地圖上隨機(jī)生成障礙，以此來驗(yàn)證SSA和ISSA優(yōu)化功能。如圖3所示是在20 m×20 m的柵格地圖上對(duì)比2種算法的結(jié)果，圖4所示是在40 m×40 m的柵格地圖上對(duì)比2種算法的結(jié)果，其中，虛線表示優(yōu)化后的SSA算法，實(shí)線表示未優(yōu)化的SSA算法。

如圖3—4所示，不管是面積大的柵格地圖還是面積小的柵格地圖，ISSA優(yōu)化出來的路徑比SSA優(yōu)化出來的路徑要更短、更光滑。

為了進(jìn)一步驗(yàn)證ISSA的效果，如圖5—6所示分別表示圖3和圖4這2種情況下的適應(yīng)度變化。

通過對(duì)比圖5—6的實(shí)驗(yàn)結(jié)果，可以清晰地看到ISSA與SSA在路徑規(guī)劃性能上的差異。在面積小的柵格地圖上，雖然最初迭代時(shí)，ISSA的適應(yīng)度值變化趨勢(shì)沒有原始SSA那么明顯，但隨著迭代次數(shù)的增多，ISSA的優(yōu)勢(shì)逐漸顯現(xiàn)。ISSA能夠有效地跳出局部最優(yōu)值，避免了算法過早收斂于非全局最優(yōu)解的問題。同時(shí)，ISSA的收斂速度也得到了顯著提升，這意味著算法能夠在更短的時(shí)間內(nèi)找到高質(zhì)量的路徑解決方案；在40 m×40 m的隨機(jī)柵格地圖上，ISSA的性能優(yōu)勢(shì)更加突出，它不僅在效率上有了明顯提升，適應(yīng)度收斂速度也顯著加快。這得益于ISSA算法在全局搜索和局部精細(xì)調(diào)整之間的平衡處理，使得算法能夠在大尺寸的柵格地圖上依然保持高效的路徑規(guī)劃能力。

4 結(jié)語

為了解決原始SSA在機(jī)器人路徑規(guī)劃中所面臨的搜索精度低、收斂速度慢等問題，本文突破性地引入了Levy飛行策略，這一策略不僅能夠有效增強(qiáng)SSA的全局搜索能力，還有效降低了算法陷入局部最優(yōu)的風(fēng)險(xiǎn)，再通過優(yōu)化正余弦策略中的步長搜索因子來解決原始SSA中收斂速度慢的問題，從而提高機(jī)器人在路徑規(guī)劃上的搜索精度和搜索速度。結(jié)果表明：（1）相較于傳統(tǒng)的SSA，本文提出的ISSA算法在避免陷入局部最優(yōu)方面取得了顯著成效，并且顯著提升了算法的收斂速度。這一改進(jìn)使得ISSA在解決機(jī)器人路徑規(guī)劃問題時(shí)更具優(yōu)勢(shì)，能夠快速找到全局最優(yōu)解，為機(jī)器人的高效導(dǎo)航和決策提供有力支持。（2）從本文的3個(gè)試驗(yàn)中可以看出，使用ISSA規(guī)劃機(jī)器人最優(yōu)路徑時(shí)，路徑規(guī)劃的距離分別可以縮短1.3571 m、2.6924 m和9.8786 m，從效率上分別提升4.5%、8.2%和13.7%，并且在復(fù)雜度越高的地圖上，ISSA算法在路徑規(guī)劃方面具有顯著優(yōu)勢(shì)，其規(guī)劃出的路徑具有更大的提升空間。這意味著通過不斷優(yōu)化和調(diào)整算法參數(shù)，ISSA算法有望生成更加高效、安全且無碰撞的路徑，從而進(jìn)一步提升機(jī)器人的運(yùn)動(dòng)性能和任務(wù)執(zhí)行效率。這種提升空間的存在使得ISSA算法成為未來機(jī)器人路徑規(guī)劃領(lǐng)域研究和應(yīng)用的重要方向。

參考文獻(xiàn)

［1］劉佳瑞.《全球人工智能教育發(fā)展報(bào)告》（節(jié)選）漢譯實(shí)踐報(bào)告［D］.南京：南京郵電大學(xué)，2022.

［2］姚舜一.面向多樣動(dòng)態(tài)環(huán)境的強(qiáng)化學(xué)習(xí)機(jī)器人導(dǎo)航算法研究［D］.北京：中國科學(xué)技術(shù)大學(xué)，2022.

［3］崔煒，朱發(fā)證.機(jī)器人導(dǎo)航的路徑規(guī)劃算法研究綜述［J］.計(jì)算機(jī)工程與應(yīng)用，2023（19）：10-20.

［4］SUN H Z，WANG J，CHEN C，et al. ISSA-ELM： A net work security situation prediction model［J］.Electronics，2023（1）：25-45.

［5］LIU H T，DAI J Y，CHEN X Y. A moving window double locally weighted extreme learning machine on an improved sparrow searching algorithm and its case study on a hema tite grinding process［J］.Processes，2023（1）：169.

［6］ZHOU S H，XIE H，ZHANG C C，et al. Wavefront-shaping focusing based on a modified sparrow search algorithm［J］.Optik-International Journal for Light and Electron Optics，2021（35）：167516.1-167516.38.

［7］劉睿，莫愿斌.增強(qiáng)型麻雀搜索算法及其工程優(yōu)化應(yīng)用［J］.小型微型計(jì)算機(jī)系統(tǒng)，2022（3）：497-505.

［8］唐建亞，盛帆，鄭建.利用柵格地圖評(píng)判路基路面壓實(shí)遍數(shù)的方法：江蘇省公路學(xué)會(huì)學(xué)術(shù)論文集（2017年）［C］.南京：江蘇省公路學(xué)會(huì)，2018.

［9］JIAN B L，LIANG G S，PENG Y L，et al. A hybrid variational mode decomposition and sparrow search algorithm-based least square support vector machine model for monthly runoff forecasting［J］.Water Supply，2022（6）：5698-5715.

［10］JIANGUO Z，ZHONGTIAN X，SHIGUO W. A novel hybrid learning paradigm with feature extraction for carbon price prediction based on Bi-directional long short-term memory network optimized by an improved sparrow search algorithm［J］.Environmental Science and Pollution Research International，2022（43）：65585-65598.

［11］施磊，郝武幫，郭曉龍.基于Levy飛行策略和改進(jìn)灰狼算法的光伏陣列MPPT研究［J］.電力科學(xué)與工程，2023（6）：17-24.

［12］福州大學(xué).一種基于Levy搜索的混沌人工蜂群算法：CN108629400A［P］.2018-10-09.

［13］溫州大學(xué).一種基于改進(jìn)正余弦優(yōu)化算法的乳腺癌圖像特征選擇方法：CN112085059B［P］.2023-10-20.

［14］趙永奇.正余弦算法的改進(jìn)及應(yīng)用研究［D］.淮北：淮北師范大學(xué)，2020.

Robot path planning based on improved sparrow search algorithm

Abstract： Aiming at the problems of insufficient search accuracy and slow search speed in robot path planning of Sparrow Search Algorithm （SSA）， this paper proposes an improved Sparrow Search Algorithm （ISSA）. In ISSA， Levy flight strategy and sine-cosine strategy are introduced to optimize the problems of traditional SSA， such as easily falling into local optimal value and slow convergence speed. On the Matlab2022b software platform， different forms of grid maps are used to simulate and verify the algorithm’s fitness and the length of path planning. The simulation results show that when using ISSA to plan the optimal path of the robot， the distance of path planning can be shortened by 1.3571 m， 2.6924 m and 9.8786 m， respectively， and the efficiency is improved by 4.5%， 8.2% and 13.7%， respectively.

Key words： sparrow search algorithm; path planning; levy flight strategy; sine and cosine strategy