梁景潤(rùn),劉麗桑,陳炯暉,張友淵,陳家煜
(1. 福建理工大學(xué) 電子電氣與物理學(xué)院,福建 福州 350118;2. 福建省工業(yè)集成自動(dòng)化行業(yè)技術(shù)開發(fā)基地,福建 福州 350118)
在移動(dòng)機(jī)器人領(lǐng)域,路徑規(guī)劃是指從起始點(diǎn)至目標(biāo)點(diǎn)規(guī)劃出一條安全、平滑和最短的路徑[1]。路徑規(guī)劃在智能倉(cāng)儲(chǔ)、智能物流、柔性制造和自動(dòng)駕駛等領(lǐng)域應(yīng)用廣泛,路徑規(guī)劃算法也一直是研究熱點(diǎn)。傳統(tǒng)的全局路徑規(guī)劃算法有Dijkstra、A*、PRM和RRT等。為了解決貨運(yùn)索道的路徑規(guī)劃問題,張飛凱等[2]對(duì)Dijkstra算法進(jìn)行了優(yōu)化,減少了路徑搜索的計(jì)算量。謝春麗等[3]引入跳點(diǎn)搜索算法對(duì)A*算法進(jìn)行改進(jìn),有效節(jié)省了算法的運(yùn)行時(shí)間和內(nèi)存開銷。為了提高路徑的安全性,程謙等[4]對(duì)PRM算法進(jìn)行優(yōu)化,使路徑連接更多的采樣點(diǎn)并增加了路徑在彎道處與障礙物的距離。為了實(shí)現(xiàn)移動(dòng)機(jī)器人在狹隘通道上的路徑規(guī)劃,陳法法等[5]對(duì)RRT算法進(jìn)行了改進(jìn),在增加道路探索成功率的同時(shí)減少了路徑成本。然而,這些傳統(tǒng)的全局路徑規(guī)劃算法大多存在尋路時(shí)間長(zhǎng)、內(nèi)存開銷大和復(fù)雜度較高等缺點(diǎn)。
近年來(lái),一些智能優(yōu)化算法如粒子群算法(PSO)、遺傳算法(GA)、螢火蟲優(yōu)化算法(FA)、蟻群算法(ACO)、灰狼優(yōu)化算法(GWO)和麻雀搜索算法(SSA)等也被引進(jìn)移動(dòng)機(jī)器人的路徑規(guī)劃領(lǐng)域。師瑋等[6]提出一種改進(jìn)的PSO方法來(lái)優(yōu)化工業(yè)機(jī)械臂的運(yùn)動(dòng)軌跡,減少了必需的運(yùn)動(dòng)時(shí)間,提高運(yùn)動(dòng)軌跡優(yōu)化的精度。陳高遠(yuǎn)等[7]提出了一種用于移動(dòng)機(jī)器人路徑規(guī)劃的改進(jìn)GA算法,并用PSO進(jìn)行局部搜索,以加快GA算法的收斂速度,防止其陷入局部最優(yōu)。針對(duì)移動(dòng)機(jī)器人在運(yùn)動(dòng)過程中存在實(shí)際運(yùn)動(dòng)軌跡與預(yù)設(shè)軌跡偏差過大等問題,于飛等[8]通過對(duì)ACO進(jìn)行改進(jìn),完成了移動(dòng)機(jī)器人的按需規(guī)劃,并最小化了移動(dòng)機(jī)器人的運(yùn)動(dòng)軌跡與預(yù)設(shè)軌跡的偏差。虞馥澤等[9]提出了一種改進(jìn)的FA并用于求解多機(jī)器人的路徑規(guī)劃問題,在提高路徑安全性的同時(shí)減少路徑長(zhǎng)度。劉志強(qiáng)等[10]采用多種策略對(duì)傳統(tǒng)的GWO進(jìn)行了改進(jìn),解決了該算法收斂速度慢和容易陷入局部最優(yōu)等問題,提高了算法的尋優(yōu)精度,并減少了算法的規(guī)劃路徑的長(zhǎng)度。
上述研究成果從多個(gè)角度為解決移動(dòng)機(jī)器人的路徑規(guī)劃難題提供思路,但還有一些問題有待解決,如算法規(guī)劃的路徑過長(zhǎng)、路徑轉(zhuǎn)彎次數(shù)過多和路徑不夠平滑等[11]。針對(duì)這些問題,本研究提出了一種基于Logistic混沌映射、自適應(yīng)慣性因子和柯西變異等多種先進(jìn)策略改進(jìn)的麻雀搜索算法,以期改善麻雀初始種群的分布,提高算法初始解的質(zhì)量,平衡算法的全局探索能力與局部勘探能力,增強(qiáng)算法跳出局部最優(yōu)解的能力。
麻雀搜索算法是一種元啟發(fā)式群智能優(yōu)化算法,來(lái)源于麻雀種群的捕食和反捕食行為特征具有結(jié)構(gòu)簡(jiǎn)單、調(diào)優(yōu)參數(shù)少和易于實(shí)現(xiàn)等優(yōu)點(diǎn)[12]。然而,麻雀搜索算法與其他智能優(yōu)化算法一樣,也存在初始種群質(zhì)量不高、搜索區(qū)域分布不均和易陷入局部最優(yōu)等缺點(diǎn)[13]。
一般地,麻雀種群主要被劃分為發(fā)現(xiàn)者和跟隨者。其中,發(fā)現(xiàn)者主要幫助麻雀種群發(fā)現(xiàn)食物源,并引領(lǐng)麻雀種群向食物源靠近。除發(fā)現(xiàn)者外,大部分的麻雀為跟隨者,主要跟隨發(fā)現(xiàn)者來(lái)獲取食物[14]。此外,麻雀種群在捕食過程中還會(huì)隨機(jī)選擇一小部分的麻雀?jìng)€(gè)體作為偵查者,大約占整個(gè)種群的10%~20%。當(dāng)發(fā)現(xiàn)天敵時(shí),偵查者會(huì)向整個(gè)麻雀群體發(fā)出警告信號(hào),整個(gè)麻雀群體必須盡快逃到其他安全的地方。
假設(shè)麻雀種群的集合矩陣表示為:
X=[x1,x2,x3,…,xp]T
(1)
其中,xi=[xi,1,xi,2,…,xi,d],i=(1,2,…,p),p代表麻雀種群的數(shù)量,d代表變量的維數(shù),則麻雀種群的適應(yīng)度函數(shù)用式(2)表示。
F(x)=[f(x1),f(x2),…,f(xn)]T
(2)
其中,f(xi)=[f(xi,1),f(xi,2),…,f(xi,d)],表示第i個(gè)麻雀的適應(yīng)度值。
一般地,優(yōu)先獲得食物的麻雀將成為發(fā)現(xiàn)者,其適應(yīng)度值也會(huì)相應(yīng)變好,從而幫助整個(gè)麻雀種群獲得食物。發(fā)現(xiàn)者的位置更新方式[15]可用式(3)表示。
(3)
表1 4種算法的性能對(duì)比Tab.1 Comparison performance of four algorithms
除了發(fā)現(xiàn)者,大多數(shù)麻雀都是跟隨者,跟從發(fā)現(xiàn)者獲取食物。跟隨者的位置更新方式[15]如式(4):
(4)
式中,Xworst代表麻雀種群中適應(yīng)度最差的麻雀?jìng)€(gè)體,Z為1×d的矩陣,且Z′=ZT(ZZT)-1。當(dāng)i≤(n/2)時(shí),表明第i個(gè)跟隨者的適應(yīng)度值較好,可以獲得充足的食物;反之,則代表其適應(yīng)度值較差,需要到其他地方去補(bǔ)充食物。
為了安全起見,麻雀種群中通常會(huì)被選擇一小部分的麻雀?jìng)€(gè)體作為警戒者。警戒者的位置更新方式[15]如式(5):
(5)
式中,Xbest表示全局最佳位置。λ是一個(gè)服從[0,1]正態(tài)分布的步長(zhǎng)可控的隨機(jī)數(shù)。k代表麻雀的行進(jìn)方向,是[-1,1]范圍的均勻隨機(jī)數(shù)。fi和fg分別代表當(dāng)前的全局最佳和最差的適應(yīng)度值。ε為避免分母為0的最小常數(shù)。fi=fg表示麻雀處于種群的邊緣,容易受到天敵的襲擊。
綜上,傳統(tǒng)的麻雀搜索算法有以下缺點(diǎn):
(1)麻雀種群在初始化時(shí)是隨機(jī)創(chuàng)建的,導(dǎo)致種群分布不均,種群多樣性較差,算法的初始解質(zhì)量較低。
(2)發(fā)現(xiàn)者的位置更新方式具有一定的局限性,無(wú)法平衡全局搜索能力和局部挖掘能力。當(dāng)預(yù)警值小于所設(shè)定的安全閾值時(shí),發(fā)現(xiàn)者的搜索能力將會(huì)隨著算法的迭代次數(shù)的增加而慢慢降低,導(dǎo)致算法的空間搜索區(qū)域不足,算法收斂效率較低。
(3)最差和最優(yōu)麻雀?jìng)€(gè)體缺乏交流反饋,面對(duì)復(fù)雜的工程優(yōu)化問題時(shí)容易陷入局部最優(yōu)解。
針對(duì)麻雀種群在后期迭代過程中存在種群多樣性較差等問題,本研究采用Logistic混沌映射生成初始麻雀種群來(lái)豐富其多樣性,提高算法初始解的質(zhì)量。
混沌現(xiàn)象是一種可自主產(chǎn)生的特定非線性現(xiàn)象,具有確定規(guī)律的隨機(jī)性和周期性等特點(diǎn),可以不重復(fù)地搜索其整個(gè)工作空間范圍。而Logistic混沌映射作為一種典型的混沌映射模型,與Tent混沌映射和Sine混沌映射等相比,具有更均勻的分布特征和可控的隨機(jī)性。因此,本研究采用Logistic混沌映射初始化麻雀種群來(lái)豐富其多樣性,從而提高算法初始解的質(zhì)量。Logistic混沌映射的數(shù)學(xué)表達(dá)式[16]如式(6):
Xt+1=μ·Xt·(1-Xt)
(6)
其中,Xt+1為t+1代的麻雀?jìng)€(gè)體,Xt為t代的麻雀?jìng)€(gè)體。μ∈(0,4],且當(dāng)μ=4時(shí),Logistic混沌映射達(dá)到完全映射狀態(tài)。經(jīng)過Logistic混沌映射構(gòu)建麻雀的初始種群,增加了麻雀初始種群的規(guī)模和多樣性。相較于由隨機(jī)策略產(chǎn)生的麻雀初始種群,使用Logistic混沌映射形成的麻雀種群的分布更加均勻,種群多樣性更高。Logistic混沌映射方法不僅改善了麻雀種群的邊緣聚集情況,而且使得麻雀種群在非邊緣地區(qū)的分布更加均勻,擴(kuò)大了算法的搜索范圍,提高了算法的搜索效率。
傳統(tǒng)的麻雀搜索算法由于在算法迭代初期就開始逼近全局最優(yōu)解,可能導(dǎo)致其在后期迭代過程中全局空間的搜索能力下降、探索范圍變窄、容易落入局部最優(yōu)值。針對(duì)這一問題,本研究采用了自適應(yīng)慣性因子法更新麻雀種群的發(fā)現(xiàn)者的位置。通過引入自適應(yīng)慣性因子,在算法迭代初期增大自適應(yīng)慣性因子,集中探索全局空間區(qū)域;在算法迭代后期減小自適應(yīng)慣性因子,專注于發(fā)現(xiàn)者的最佳位置的挖掘,使得算法能在全局搜索能力和局部勘探能力之間得到均衡,降低了算法陷入局部最優(yōu)的風(fēng)險(xiǎn)。
利用自適應(yīng)慣性因子改進(jìn)發(fā)現(xiàn)者的位置更新方式如式(7):
(7)
其中,自適應(yīng)慣性因子λ可表示如式(8):
(8)
式中相關(guān)變量已在公式(3)中闡明,不再贅述。
針對(duì)傳統(tǒng)的麻雀搜索算法在面對(duì)復(fù)雜的工程優(yōu)化問題時(shí)易陷入局部最優(yōu)解等缺點(diǎn),本研究采用柯西變異算法進(jìn)一步增強(qiáng)最差麻雀?jìng)€(gè)體與最優(yōu)麻雀?jìng)€(gè)體的交流反饋,提高了算法的收斂效率和躍出局部最優(yōu)解的能力。
傳統(tǒng)的算法在更新跟隨者的位置后,適應(yīng)度值最差的麻雀?jìng)€(gè)體一般很難定位到獵物的位置。若在實(shí)際的捕食過程中有目的地增強(qiáng)最差個(gè)體與最優(yōu)個(gè)體的交流反饋,既能進(jìn)一步降低最差麻雀?jìng)€(gè)體的適應(yīng)度值,又能對(duì)最優(yōu)麻雀?jìng)€(gè)體的位置起擾動(dòng)作用,有助于算法躍出局部最優(yōu)解。因此,在傳統(tǒng)算法的基礎(chǔ)上,通過融合柯西變異算法的交流反饋階段可以提高算法的尋優(yōu)精度以及收斂速度,用公式表達(dá)[17]如式(9):
(9)
通過融合柯西變異算法增強(qiáng)了麻雀種群中最差麻雀?jìng)€(gè)體與最優(yōu)麻雀?jìng)€(gè)體的交流反饋,使得最差麻雀?jìng)€(gè)體能快速飛往獵物的位置,進(jìn)一步降低了最差麻雀?jìng)€(gè)體的適應(yīng)度值,提高了算法的收斂效率。
此外,通過柯西變異算法的隨機(jī)小步長(zhǎng)對(duì)當(dāng)前的局部最優(yōu)麻雀?jìng)€(gè)體的位置進(jìn)行擾動(dòng),實(shí)現(xiàn)全局最優(yōu)解附近的不斷搜索,持續(xù)更新當(dāng)前最優(yōu)麻雀?jìng)€(gè)體的位置和適應(yīng)度值,擴(kuò)大了算法的搜索區(qū)域,增強(qiáng)了算法的全局搜索能力和規(guī)避局部最優(yōu)的能力。
將基于多策略改進(jìn)的麻雀搜索算法(LAFSSA)應(yīng)用于移動(dòng)機(jī)器人的全局路徑規(guī)劃,基本流程如圖 1所示。
圖1 LAFSSA路徑規(guī)劃流程圖Fig.1 Flow chart of LAFSSA for path planning
對(duì)于移動(dòng)機(jī)器人的全局路徑規(guī)劃尋優(yōu)問題,適應(yīng)度函數(shù)的構(gòu)造通常需要考慮路徑規(guī)劃的兩個(gè)特性:一是移動(dòng)機(jī)器人不能與障礙物發(fā)生碰撞;二是移動(dòng)機(jī)器人在當(dāng)前環(huán)境模型中規(guī)劃的全局路徑是最短的。因此,本研究從路徑長(zhǎng)度和避障函數(shù)兩個(gè)方面構(gòu)造LAFSSA的適應(yīng)度函數(shù)。
假設(shè)Pi(xi,yi)和Pi+1(xi+1,yi+1)分別是算法規(guī)劃的路徑點(diǎn)序列P′={P0,P1,…,Pi,Pi+1,…,Pm-1}中相鄰的兩個(gè)路徑點(diǎn),則算法規(guī)劃的全局最短路徑可由路徑點(diǎn)序列P′中相鄰的路徑點(diǎn)的歐式距離求得,表示如式(10):
(10)
式中,(xi,yi)和(xi+1,yi+1)分別為路徑點(diǎn)Pi和Pi+1對(duì)應(yīng)環(huán)境模型中的橫坐標(biāo)和縱坐標(biāo)。m代表路徑點(diǎn)序列P′對(duì)應(yīng)環(huán)境模型中的路徑點(diǎn)個(gè)數(shù)。
除了需要考慮移動(dòng)機(jī)器人的全局最優(yōu)路徑長(zhǎng)度最短,還需要避免移動(dòng)機(jī)器人的路徑穿過障礙物。因此,本研究提出一個(gè)懲罰函數(shù)F2,當(dāng)移動(dòng)機(jī)器人的路徑將與障礙物發(fā)生碰撞時(shí),對(duì)其進(jìn)行懲罰,從而避免了移動(dòng)機(jī)器人的路徑穿過障礙物,與障礙物保持一定的距離,用公式(11)表示:
F2=φ·Q
(11)
式中,φ為懲罰因子,Q為障礙物在環(huán)境模型中的位置。
綜上可知,LAFSSA的移動(dòng)機(jī)器人全局路徑規(guī)劃的總的適應(yīng)度函數(shù)公式為:
(12)
為方便模擬出移動(dòng)機(jī)器人周圍的真實(shí)環(huán)境,構(gòu)建了兩個(gè)地圖環(huán)境模型如圖2所示。其中,x,y分別表示地圖環(huán)境模型的長(zhǎng)和寬。環(huán)境模型1的地圖大小為20×20,上三角形表示移動(dòng)機(jī)器人的起點(diǎn)位置,其坐標(biāo)為(1,1);五角星表示移動(dòng)機(jī)器人的終點(diǎn)位置,其坐標(biāo)為(20,20)。環(huán)境模型2的地圖大小為40×40,上三角形表示移動(dòng)機(jī)器人的起點(diǎn)位置,其坐標(biāo)為(1,1);五角星表示移動(dòng)機(jī)器人的終點(diǎn)位置,其坐標(biāo)為(40,40)。通過比較可知,圖 2(b)的環(huán)境模型比圖 2(a)的更加復(fù)雜,這對(duì)移動(dòng)機(jī)器人的路徑規(guī)劃將是一個(gè)挑戰(zhàn)。
圖2 地圖環(huán)境模型Fig.2 Environmental model mapping
實(shí)驗(yàn)的仿真環(huán)境為處理器Intel(R) Core(TM) i7-5500 @ 2.40 GHz、內(nèi)存8 GB和裝有MATLAB R2017b軟件的Windows7 64位系統(tǒng)的筆記本電腦。
為驗(yàn)證所提的LAFSSA的有效性,分別使用蟻群優(yōu)化算法(ACO)、鯨魚優(yōu)化算法(WOA)、麻雀搜索算法(SSA)和所提的改進(jìn)麻雀搜索算法(LAFSSA)在環(huán)境模型1、2中進(jìn)行移動(dòng)機(jī)器人的全局路徑規(guī)劃。仿真實(shí)驗(yàn)中,ACO、WOA和SSA的種群規(guī)模設(shè)置為50,最大迭代次數(shù)設(shè)置為200。
對(duì)于環(huán)境模型1,使用ACO、WOA、SSA和LAFSSA規(guī)劃出移動(dòng)機(jī)器人的全局路徑如圖3所示。
圖3 4種算法在環(huán)境模型1中的規(guī)劃路徑Fig.3 Path planned by four algorithms in environmental model 1
由圖3可知,在環(huán)境模型1中,算法規(guī)劃的路徑長(zhǎng)度從短到長(zhǎng)依次為:LAFSSA、ACO、WOA、SSA。算法規(guī)劃的路徑轉(zhuǎn)向次數(shù)從少到多依次為:LAFSSA、SSA、WOA、ACO。因此,綜合考慮路徑長(zhǎng)度和路徑轉(zhuǎn)折次數(shù)作為算法的衡量標(biāo)準(zhǔn)時(shí),所提的LAFSSA均是最優(yōu)的。
從圖4可以更加直觀地看到ACO、WOA、SSA和LAFSSA在環(huán)境模型1中移動(dòng)機(jī)器人全局路徑的尋優(yōu)效果表現(xiàn)。算法的收斂精度從高到低依次為L(zhǎng)AFSSA、ACO、WOA和SSA。算法的收斂速度從快到慢依次為L(zhǎng)AFSSA、SSA、ACO和WOA。因此,綜合考慮算法的收斂精度和收斂速度,LAFSSA在環(huán)境模型1中的路徑尋優(yōu)效果比ACO、WOA和SSA等算法更好。
圖4 4種算法在環(huán)境模型1中的收斂曲線圖Fig.4 Convergence curve of four algorithms in environmental model 1
為進(jìn)一步驗(yàn)證LAFSSA的可靠性,使用ACO、WOA、SSA和LAFSSA等算法在環(huán)境模型2中規(guī)劃出移動(dòng)機(jī)器人的全局路徑,如圖 5所示。
由圖5可知,在環(huán)境模型2中,算法規(guī)劃的路徑長(zhǎng)度從短到長(zhǎng)依次為:LAFSSA、WOA、SSA、ACO。算法規(guī)劃的路徑轉(zhuǎn)向次數(shù)從少到多依次為:LAFSSA、WOA、SSA、ACO。因此,對(duì)于更加復(fù)雜的環(huán)境模型2,LAFSSA在路徑長(zhǎng)度和路徑轉(zhuǎn)折次數(shù)等方面的性能均優(yōu)于ACO、WOA和SSA等算法。
圖5 4種算法在環(huán)境模型2中的規(guī)劃路徑Fig.5 Path planned by four algorithms in environmental model 2
ACO、WOA、SSA和LAFSSA等4種算法在環(huán)境模型2中的收斂曲線如圖6所示。
圖6 4種算法在環(huán)境模型2中的收斂曲線圖Fig.6 Convergence curve of four algorithms in environmental model 2
由圖6可得知,所提4種算法的收斂精度從高到低依次為L(zhǎng)AFSSA、WOA、SSA和ACO,收斂速度從快到慢依次為L(zhǎng)AFSSA、ACO、SSA和WOA。因此,從算法的收斂精度和收斂速度等方面綜合考慮,與ACO、WOA和SSA等算法相比,LAFSSA在環(huán)境模型2中的全局路徑規(guī)劃效果更好。此外,地圖環(huán)境越復(fù)雜,LAFSSA的競(jìng)爭(zhēng)力越顯著。
綜上,與ACO、WOA和SSA等算法相比,LAFSSA在路徑長(zhǎng)度和路徑轉(zhuǎn)折次數(shù)等方面均表現(xiàn)出較好的性能。為更突出LAFSSA的優(yōu)越性,綜合考慮路徑長(zhǎng)度、路徑轉(zhuǎn)折次數(shù)和算法耗時(shí)等3個(gè)指標(biāo),總結(jié)了ACO、SSA、WOA和LAFSSA等算法的性能如表1所示。
由表1的結(jié)果可知,在環(huán)境模型1和環(huán)境模型2中,與ACO、WOA和SSA等算法相比,本研究所提LAFSSA規(guī)劃的移動(dòng)機(jī)器人的路徑長(zhǎng)度更短,路徑轉(zhuǎn)折次數(shù)更少,算法耗時(shí)更低,移動(dòng)機(jī)器人的路徑尋優(yōu)時(shí)間更少,規(guī)劃路徑的平滑性也被有效提升。
針對(duì)傳統(tǒng)的SSA在求解移動(dòng)機(jī)器人的路徑規(guī)劃問題時(shí)存在路徑長(zhǎng)度長(zhǎng)、路徑轉(zhuǎn)折次數(shù)多和路徑搜索耗時(shí)等問題,本研究提出了一種基于多種先進(jìn)策略改進(jìn)的SSA,稱為L(zhǎng)AFSSA。該算法引入Logistic混沌映射策略生成麻雀初始種群,增加麻雀種群的多樣性,提高算法初始解的質(zhì)量。此外,本研究提出一種自適應(yīng)慣性因子法用于改進(jìn)SSA中發(fā)現(xiàn)者的位置更新策略,進(jìn)一步平衡算法的全局搜索能力和局部勘探能力。為防止陷入局部最優(yōu),該算法融合柯西變異算法增強(qiáng)最差麻雀?jìng)€(gè)體與最優(yōu)麻雀?jìng)€(gè)體的交流反饋。在環(huán)境模型1和環(huán)境模型2中進(jìn)行的移動(dòng)機(jī)器人的路徑規(guī)劃仿真實(shí)驗(yàn),驗(yàn)證了所提LAFSSA的有效性。與SSA相比,LAFSSA規(guī)劃的路徑長(zhǎng)度平均縮短了45.49%,路徑轉(zhuǎn)折次數(shù)平均減少了36.11%,算法耗時(shí)平均減少了29.04%,具有較高的尋優(yōu)精度和較好的路徑平滑效果,在解決移動(dòng)機(jī)器人的路徑規(guī)劃問題時(shí)具有更加顯著的優(yōu)勢(shì)。