基于改進火烈鳥搜索算法的移動機器人路徑規劃*

馬 兵，呂彭民，劉永剛，韓紅安，周 強，胡永濤

（1.長安大學道路施工技術與裝備教育部重點實驗室，陜西 西安 710064；2.河南衛華重型機械股份有限公司，河南 長垣 453400；3.河南工學院電氣工程與自動化學院，河南 新鄉 453003）

0 引 言

近年來，移動機器人最優路徑規劃是帶有復雜約束的優化問題。然而，傳統元啟發式算法在求解機器人路徑規劃問題時，存在搜索效率低和尋優精度不高等不足之處。為彌補這些不足，研究學者從改善算法尋優性能的角度出發，提出了眾多的改進算法。如：改進蟻群算法［1，2］，變步長蟻群算法［3］，多步長蟻群算法［4］，改進遺傳算法［5］，改進果蠅算法［6］，改進灰狼優化算法［7］，改進粒子群優化算法［8］，改進正余弦算法［9］，煙花-蟻群混合算法［10］等。雖然，文獻中已有算法可提高求解移動機器人路徑規劃問題的尋優效率和精度，但是，在復雜的地圖環境下，仍存在局部搜索停滯和搜索效率低的問題。

受火烈鳥遷徙和覓食行為啟發的火烈鳥搜索算法（flamingo search algorithm，FSA）是一種比較新穎的算法，與其他算法相比，FSA具有較好的穩定性和魯棒性，可用于求解電路問題、路徑規劃、網絡入侵預防系統等實際問題［11］。但對高維度復雜的問題時，仍存在易陷入局部最優、精度低、尋優效率低等問題，鑒于此，融合了自適應Sigmoid 非線性種群動態調整因子，混合精細分級搜索策略和逐維隨機鏡面反射學習策略，提出一種改進的FSA（improved FSA，IFSA），提高算法的搜索效率和求解精度，通過移動機器人路徑規劃問題，驗證了所提出算法的有效性。

1 移動機器人路徑規劃環境建模

柵格化是移動機器人路徑規劃中通用的環境建模方法［12］。移動機器人路徑規劃環境可簡化為由一定數量的相同柵格化區域組成，移動機器人等效為一個質點，可在每個柵格的中心點處自由移動。將移動機器人的運動空間由黑色柵格和白色柵格劃分，黑色指障礙物柵格用1 表示。白色指無障礙物柵格用0 表示。按照從左至右，從上至下的劃分順序，將移動機器人運動空間劃分為相同的柵格，并對每個柵格進行坐標編號。每個柵格的坐標（xi，yi）可由式（1）確定［1］

式中l為柵格的邊長，mm為地圖的維度。

2 IFSA

2.1 FSA

1）火烈鳥覓食行為

首先，火烈鳥利用鳥喙在一定范圍內進行食物掃描，易發現更多的食物；其次，發現食物較多的火烈鳥，通過與其余火烈鳥之間的交流來指引火烈鳥不斷向食物多的地方移動；最后，通過部分火烈鳥靠雙足不斷移動到食物豐富的區域。這種覓食行為可用式（2）來描述

式中和分別為火烈鳥在第k+1 次和第k次迭代時在種群中第j維中的覓食位置為火烈鳥的當前最優覓食位置，ζ1和ζ2為-1或者1 的隨機數，α1和α2均服從標準正態分布，C為隨機擴散系數，其服從自由度n的卡方分布。

2）火烈鳥遷徙行為

當覓食區域食物匱乏時，火烈鳥群體會利用雙足整體遷徙到其他區域，繼續尋找更多的食物。這種遷徙行為可用式（3）來描述

式中和分別為火烈鳥在第k+1次和第k次迭代時在種群中第j維中的鳥腳位置為種群中第j維的火烈鳥當前最優位置，β為服從自由度n的高斯隨機數。

FSA算法步驟如下：1）火烈鳥種群初始化，定義算法初始參數，種群數量N，最大迭代次數kmax，第1部分遷徙火烈鳥比例為MPb。2）評估適應度函數的值，確定最優火烈鳥位置和適應度值。3）更新參與覓食的火烈鳥的數量MPr＝rand［0，1］×N×（1 -MPb）及參與第2部分遷徙的火烈鳥數量MPt＝N×（1 -MPb）-MPr。4）根據式（3）更新火烈鳥的遷徙位置和式（2）更新火烈鳥的覓食位置。5）判斷是否達到最大迭代次數，若是，則轉到步驟（6）；否則，返回步驟（2）繼續尋優。6）輸出火烈鳥最優位置和最優適應度值。

2.2 IFSA

1）自適應Sigmoid種群比例因子策略

FSA中，遷徙火烈鳥種群比例因子MPb是固定值，且覓食火烈鳥種群受MPb影響，這就容易導致在迭代搜索過程中，算法的種群自我調整能力較低，使得算法尋優能力弱。因此，引入Sigmoid函數對MPb進行非線性處理，如式（4）

式中MPb0為遷徙火烈鳥種群初始比例因子。

在整個迭代過程中，種群比例因子變化情況，如圖1 所示。由圖1可知，隨著迭代次數增加，一方面，種群比例因子MPb，MPr和MPt呈現非線性變化。另一方面，MPb和MPt之間的產異性ΔD1逐漸增大，這有利于算法的全局搜索，同時MPr和MPt之間的產異性ΔD2也隨之逐漸增大，這有利于算法的局部搜索。這就說明了自適應Sigmoid 種群比例因子策略有利于平衡算法的全局搜索與局部搜索，提高算法的尋優能力。

圖1 種群比例因子變化

2）自適應混合精細分級搜索策略

在火烈鳥覓食過程中，食物源的分布不均性影響著火烈鳥種群的移動。當引導覓食的火烈鳥獲得的食物源處于局部最優附近鄰域時，其余的火烈鳥會移動且聚集處于停滯狀態。這樣會導致種群位置的多樣性降低，增加了算法陷入局部極值的可能性。鑒于此，將覓食過程根據迭代次數劃分為3 個階段，采用自適應混合精細分級搜索策略：第1階段：當k＜kmax／4 時，采用原有的覓食搜索方式；第2階段：當kmax／4≤k≤3kmax／4 時，利用正余弦振蕩特性［13］，引入自適應精英引導正余弦搜索方式，這樣有利于增加種群多樣性提高算法局部搜索能力；第3 階段：當3kmax／4 ＜k≤kmax時，利用黃金分割方式，不斷地細化搜索空間，引入用黃金正弦搜索方式［14］，豐富算法的搜索空間，進一步平衡算法的“搜索”與“開發”提高算法全局尋優能力。因此，整個覓食過程火烈鳥的位置更新可按式（5）進行

式中r1為［0，2π］內隨機數，r2為［0，π］內隨機數，r3為服從高斯分布的隨機數。φ為自適應非線性調整因子取值范圍為［0，1］，可由式（6）計算

3）逐維隨機鏡面反射學習策略

a.隨機鏡面反射學習策略

傳統的鏡面反射學習（specular reflection learning，SRL）策略如圖2，為增加算法尋優過程中，個體A0（即當前解X）沿入射線A經過鏡面的反射，沿反射線B產生個體B0（即反向解X*），根據點X產生當前解和X*產生的反向解之間擇優選擇進入下一次迭代［15］。

圖2 傳統SRL模型

根據SRL模型，由X產生的反向解X*可用式（7）表示

式中λ為反射影響系數，可由式（8）定義

式中ξ，R0，κ1和κ2均為［0，1］內的隨機數。

雖然，在算法尋優過程中，SRL策略可以豐富種群多樣性。但是，對于復雜高維問題，SRL 的隨機性較弱，無法有效地增強搜索空間內的種群多樣性。為進一步增強種群多樣性，提高算法的收斂速度和求解精度。本文提出一種隨機SRL（random SRL，RSRL）策略，如圖3所示。由點產生一個隨機反向解替代點B0原有反向解，這樣可以增強SRL的隨機性，增強種群跳出局部極值的能力。因此，在RSRL中，由式（9）替代式（7）

圖3 RSRL模型

式中η為服從高斯分布的［0，1］內的隨機數。

b.逐維RSRL策略

FSA中，火烈鳥種群位置更新過程中，各維度之間存在互相干擾，影響算法的收斂精度與速度。為此，在火烈鳥種群更新后，引入逐維RSRL策略，增加各維度之間的信息交流，以保留精英方式進行逐維RSRL，豐富種群搜索空間，增強種群多樣性，降低了保證算法的收斂效率和尋優精度。火烈鳥位置更新參照式（10）

式中為種群在j維數上的反向解，UB（j）和LB（j）為種群在j維上的上下限為種群在j維數上的當前解。

2.3 基于IFSA的移動機器人路徑規劃

具體步驟如下：1）采用柵格化法構建地圖，初始化機器人起始點和終點，設置算法的初始參數。2）初始化火烈鳥種群的位置及評估適應度函數值確定初始最優位置。3）按照式（4）和式（6）分別更新MPb和φ。4）按照式（3）更新火烈鳥的遷徙位置。5）按照式（5）分段更新火烈鳥的覓食位置。6）按照式（7）～式（10）對火烈鳥的位置進行學習。7）重新評估適應度值，更新最優火烈鳥位置和適應度值。8）是否達到最大迭代次數，若是則輸出最優路徑，否則返回步驟（3）繼續尋優。

3 路徑規劃實驗仿真

分別選擇FSA［11］、灰狼優化（GWO）算法［16］、正余弦算法（SCA）［13］和IFSA 應用于移動機器人路徑規劃問題中。算法的最大迭代次數設置為1 000，獨立運行次數為30。選取3種不同大小的柵格化地圖（即20 m×20 m，30 m×30 m，40 m×40 m）。圖4給出不同算法在不同地圖中的最優路徑和迭代收斂曲線，表1為實驗仿真統計結果。

表1 4 種算法在不同地圖中的路徑規劃結果

從最短路徑長度來看，由表1 結果可知，對于20 m ×20 m的柵格地圖，IFSA，SCA和FSA可獲得最小路徑長度為30.500 6 m，其結果優于GWO 算法。對于30 m ×30 m 的柵格地圖，IFSA和FSA尋優可得最小路徑為44.235 1 m，明顯優于GWO和SCA。對于40 m ×40 m 的柵格地圖，GWO 算法擁有最小的路徑長度為58.784 8 m，但是IFSA 的最小路徑長度優于FSA 和SCA。因此，對于復雜的地圖環境下，IFSA可提供較好的最優路徑長度結果。這表明了IFSA 具有較好的尋優能力。

從平均路徑和路徑標準差來看，由表1 結果可知，對3 種地圖環境，與SCA，FSA 和GWO 算法相比，IFSA 可以提供較小的平均路徑長度。對于20 m ×20 m 和40 m ×40 m的柵格地圖，IFSA路徑標準差劣于SCA 算法，但優于FSA和GWO。這些結果表明，IFSA 具有較好的穩定性和魯棒性。

從收斂曲線和路徑最優規劃路線來看，由圖4 可知，FSA迭代前期存在嚴重的停滯現象，但與其他算法相比，IFSA可以以較少迭代次數和轉彎次數獲取最優的移動機器人路徑規劃方案。

4 結 論

本文融合了自適應Sigmoid非線性種群動態調整因子，混合精細分級搜索策略和逐維RSRL 策略，提高了IFSA 的尋優精度和搜索效率，克服了FSA 在解決移動機器人路徑規劃時存在易陷入早熟的問題。與其他算法相比，對于復雜的路徑規劃問題，IFSA體現出了較好的實際適用性。