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

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

0 引 言

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

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

1 移動機器人路徑規(guī)劃環(huán)境建模

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

式中l(wèi)為柵格的邊長，mm為地圖的維度。

2 IFSA

2.1 FSA

1）火烈鳥覓食行為

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

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

2）火烈鳥遷徙行為

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

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

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

2.2 IFSA

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

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

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

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

圖1 種群比例因子變化

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

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

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

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

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

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

圖2 傳統(tǒng)SRL模型

根據(jù)SRL模型，由X產(chǎn)生的反向解X*可用式（7）表示

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

式中ξ，R0，κ1和κ2均為［0，1］內(nèi)的隨機數(shù)。

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

圖3 RSRL模型

式中η為服從高斯分布的［0，1］內(nèi)的隨機數(shù)。

b.逐維RSRL策略

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

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

2.3 基于IFSA的移動機器人路徑規(guī)劃

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

3 路徑規(guī)劃實驗仿真

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

表1 4 種算法在不同地圖中的路徑規(guī)劃結(jié)果

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

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

從收斂曲線和路徑最優(yōu)規(guī)劃路線來看，由圖4 可知，F(xiàn)SA迭代前期存在嚴重的停滯現(xiàn)象，但與其他算法相比，IFSA可以以較少迭代次數(shù)和轉(zhuǎn)彎次數(shù)獲取最優(yōu)的移動機器人路徑規(guī)劃方案。

4 結(jié) 論

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