莫海寧，鐘友坤

(1.廣西科技大學(xué)宏達(dá)威愛科技學(xué)院，柳州 545006；2.河池學(xué)院數(shù)理學(xué)院，宜州 546300)

0 引言

隨著日常生活自動化的提高，移動機器人在倉儲物流、工業(yè)生產(chǎn)等領(lǐng)域的應(yīng)用日益擴(kuò)大。路徑規(guī)劃是移動機器人完成自主定位與導(dǎo)航技術(shù)的關(guān)鍵問題之一。它是指移動機器人按照一定的規(guī)則在作業(yè)空間中找到從起點到終點的無碰撞最優(yōu)路徑[1]。近年來，路徑規(guī)劃問題上具有代表性的傳統(tǒng)算法有法、人工勢場法、強化學(xué)習(xí)算法、A*算法等。另外，許多仿生類算法，也被應(yīng)用于路徑規(guī)劃領(lǐng)域，例如蟻群算法、遺傳算法、灰狼算法、蝙蝠算法等。它們各自具有優(yōu)勢，都有著良好的表現(xiàn)。

煙花算法[2](FWA)是基于模擬煙花爆炸的現(xiàn)象提出的一種群體算法，其可以應(yīng)用于優(yōu)化領(lǐng)域。與其他群體算法不同的是，煙花算法設(shè)計了一種新的搜索方法即通過爆炸進(jìn)行尋優(yōu)，利用煙花個體之間互相作用得出爆炸范圍及火花數(shù)量。

然而，許多研究者很快發(fā)現(xiàn)基本的FWA算法在解決優(yōu)化問題時存在一些缺點；主要缺點包括收斂速度慢和精度低，因此提出了許多改進(jìn)算法。到目前為止，對FWA的研究主要集中在改善運算符方面。FWA最重要的改進(jìn)之一是增強的煙花算法(EFWA)[3]，對傳統(tǒng)FWA的操作進(jìn)行了全面的分析和修正?；贓FWA，提出了一種自適應(yīng)煙花算法(AFWA)[4]，這是首次嘗試通過檢測搜索過程的結(jié)果來調(diào)整沒有預(yù)定參數(shù)的爆炸幅度。在文獻(xiàn)[5]中，提出了一種動態(tài)搜索煙花算法(dynFWA)，該算法根據(jù)核心煙花的適應(yīng)值的大小，將所有煙花分為核心煙花和非核心煙花。并且通過改進(jìn)其他操作，提出了改進(jìn)的煙花算法[6]。自FWA提出以來，它已被應(yīng)用于許多領(lǐng)域[7]，包括數(shù)字濾波器設(shè)計、非負(fù)矩陣分解、垃圾郵件檢測、圖像識別、具有動態(tài)約束的桁架質(zhì)量最小化[8-12]等。

綜上所述，將煙花算法應(yīng)用到路徑規(guī)劃問題中，并且根據(jù)實際問題改善基本煙花算法在路徑規(guī)劃過程中存在的收斂速度慢、搜索空間小、易陷入局部極值等問題，提出相應(yīng)的改進(jìn)方法，從而提升機器人的路徑規(guī)劃效率。

1 基本煙花算法

在煙花算法中，假定優(yōu)化目標(biāo)函數(shù)如下：

MINf(x)∈R,xmin≤x≤xmax

(1)

式中，x表示煙花的當(dāng)前位置；xmin和xmax是x的取值范圍的上下界。本文選擇路徑距離作為優(yōu)化目標(biāo)函數(shù)。

煙花算法模擬煙花的爆炸過程，主要操作有爆炸操作、變異和選擇策略。

1.1 爆炸操作

爆炸過程中每個煙花適應(yīng)值不同，產(chǎn)生的火花個數(shù)也不一樣，第i個煙花產(chǎn)生的爆炸火花數(shù)如下：

(2)

式中，xi表示第i個煙花的位置；p為火花總數(shù)；ymax表示煙花的最大適應(yīng)值；c為一個很小的常數(shù)。為了防止在搜索過程中產(chǎn)生火花數(shù)太多或太少，因此對上式的si進(jìn)行了如下規(guī)定：

(3)

式中，a和b指為了限制種群范圍的常數(shù)值且a

(4)

在確定了爆炸范圍及數(shù)目后，第i個煙花z方向上的位置更新公式如下：

(5)

式中，k為被選的維度；rand(-1,1)為區(qū)間[-1,1]上的一個均勻隨機數(shù)。

1.2 高斯變異策略

為了提升煙花種群的豐富性，煙花算法引入了高斯變異策略。煙花xi的第k維坐標(biāo)進(jìn)行高斯變異時的表達(dá)式如下：

(6)

(7)

式中，e表示服從N(1,1)的高斯分布。通過上述操作可以得到更多種類的煙花個體，擴(kuò)大了算法搜索空間。式(7)為當(dāng)有火花個體躍出邊界時，對其進(jìn)行的映射操作，從而保證其在可行空間之內(nèi)。

1.3 選擇策略

為使煙花種群中優(yōu)勢個體進(jìn)入到下一代中，算法會在所有操作中的個體中進(jìn)行選擇，并將其作為下一代的煙花。其個體被選中的概率如下：

(8)

(9)

式中，K指所有煙花的位置結(jié)合，式(9)表示兩個體間的歐氏距離之和。

2 改進(jìn)方向

2.1 改進(jìn)爆炸范圍

為了提升算法尋優(yōu)效率，引入動態(tài)爆炸范圍。當(dāng)煙花產(chǎn)生適應(yīng)度值更好的火花時，煙花爆炸范圍會擴(kuò)大以提高全局探索能力，從而解決煙花算法易早熟的問題。具體計算表達(dá)式如下：

(10)

式中，g為當(dāng)前迭代代數(shù)；R1、R2是控制爆炸半徑的常數(shù)參數(shù)，其中R1取值范圍為(0,1)，R2為大于1的數(shù)。

2.2 導(dǎo)向因子

在基本煙花算法中，由于搜索過程中各個煙花間缺乏交流聯(lián)系，削弱了算法的搜索能力。因此提出一種導(dǎo)向因子改善此問題，即將適應(yīng)度值最高的3個個體設(shè)為L1、L2和L3，通過L1～L3引導(dǎo)其他劣勢煙花進(jìn)行搜索，其余的煙花定義為L4。L4級別低于其他3類級別。導(dǎo)向因子引導(dǎo)各類煙花個體的示意圖如圖1所示。

圖1 導(dǎo)向因子引導(dǎo)煙花更新位置圖示

如圖1所示，L4級別的煙花個體與L1、L2、L3級別個體之間的距離向量分別為DL1、DL2、DL3，它們的計算公式如式(11)所示：

(11)

式中，XL1、XL2、XL3分別表示L1、L2和L3煙花個體的當(dāng)前位置，表達(dá)式如式(12)所示，X表示當(dāng)前個體位置；F1、F2、F3是任意隨機向量。

(12)

式中，X′代表個體的最終位置，其中F、H為系數(shù)，具體計算方式如下：

H=2h·r1-h

(13)

F=2·r2

(14)

式中，h是收斂因子，在區(qū)間[0，2]上單調(diào)遞減；r1和r2取[0,1]之間的任意數(shù)。

2.3 自由變異策略

由于基本煙花算法中采用高斯變異，但是其變異過程中易出現(xiàn)重疊現(xiàn)象，導(dǎo)致算法陷入起點附近的最優(yōu)，因此提出一種自由變異策略，表達(dá)式如下：

xi,j=(xw,j-xb,j)xw,jrand(0,1)

(15)

式中，xb,j和xw,j分別表示當(dāng)前最優(yōu)及最劣煙花在第j維度上的位置；rand(0,1)表示在區(qū)間[0,1]上均勻分布的隨機數(shù)。

2.4 競爭學(xué)習(xí)策略

原有的選擇策略使得算法收斂速度較慢，因此提出一種競爭學(xué)習(xí)的選擇方法。煙花個體之間相互進(jìn)行競爭，若某個個體適應(yīng)度值不及此代中最好的煙花，就會通過學(xué)習(xí)來接近它，從而提升算法在優(yōu)勢煙花周圍的局部搜索性能，并提升收斂速度。另外，在迭代過程中一些劣勢煙花易陷入局部最優(yōu)，這時，通過縮小其與優(yōu)勢煙花的距離的方式，幫助其跳出局部最優(yōu)。相應(yīng)的表達(dá)式為：

(16)

2.5 算法流程

算法具體流程如下：

步驟1：初始化煙花算法各項參數(shù)，確定需要人為設(shè)定的參數(shù)取值。

步驟2：初始化所有煙花位置信息，并計算對應(yīng)的適應(yīng)度值，確定優(yōu)勢煙花，并且根據(jù)適應(yīng)度值設(shè)置級別。

步驟3：根據(jù)式(2)和式(4)，計算得出各個煙花的爆炸范圍及火花數(shù)。

步驟4：根據(jù)式(11)～式(14)計算導(dǎo)向因子，對L4個體的位置進(jìn)行更新。

步驟5：依據(jù)式(15)對煙花個體進(jìn)行變異操作，得出變異火花，并從所有火花中選出具有最優(yōu)適應(yīng)度值的火花。

步驟6：按照式(16)對備選的火花進(jìn)行競爭學(xué)習(xí)選擇操作。

步驟7：循環(huán)執(zhí)行步驟2～步驟6，直到滿足終止要求跳出循環(huán)。

3 仿真分析

3.1 環(huán)境建模

環(huán)境建模是指將實際環(huán)境信息映射至一個抽象空間上。機器人路徑規(guī)劃建模環(huán)境主要有柵格圖、可視圖、自由空間等。其中柵格地圖創(chuàng)建簡單且管理方便，因此本文采用柵格圖作為仿真環(huán)境。在柵格地圖中，黑色柵格代表障礙物，白色柵格代表可行區(qū)域，利用直角坐標(biāo)進(jìn)行定位。為了保證機器人運行的安全，將建模過程中規(guī)定，障礙物占用不足一格時將其膨脹為一格，且機器人禁止沿著障礙物邊緣運行。機器人柵格環(huán)境模型如圖2所示。假設(shè)柵格圖中，柵格號按從下至上，從左到右依次遞增。柵格地圖規(guī)格為m行n列，柵格號為K，柵格粒徑為1，則柵格中心坐標(biāo)可表示為：

(17)

式中，x、y分別為中心點的橫、縱坐標(biāo)；mod為取余操作；int表示求整。

圖2 柵格環(huán)境

3.2 參數(shù)設(shè)置

基于MATLAB2015b平臺搭建30×30柵格地圖環(huán)境，運行內(nèi)存8 GB，CPU 2.5 Hz，設(shè)置起點為(0.5,0.5)，終點為(29.5,29.5)。其他算法當(dāng)中的主要參數(shù)如表1所示。

表1 參數(shù)設(shè)置

3.3 仿真實例

(1)常規(guī)地形仿真?；诮－h(huán)境并根據(jù)上節(jié)設(shè)置的參數(shù)值，分別利用改進(jìn)的煙花算法和基本煙花算法進(jìn)行仿真實驗，因為煙花算法尋得的節(jié)點不一定連續(xù)，且可能跨越障礙物，因此將這些無效節(jié)點去除，另外生成相鄰節(jié)點從而形成有效的路徑。仿真結(jié)果分別如圖3和圖4所示，各項指標(biāo)對比如表2所示。

圖3 基本煙花算法仿真圖 圖4 改進(jìn)煙花算法仿真圖

表2 30×30環(huán)境指標(biāo)對比

從圖3、圖4及表2可以看出，相比于基本煙花算法，改進(jìn)的煙花算法規(guī)劃出的路徑長度更短，拐點數(shù)更少，并且收斂效率更高。具體表現(xiàn)為最短路徑長度減少約9.5%，迭代時間縮短約60.8%，收斂代數(shù)減少約73.7%，轉(zhuǎn)彎次數(shù)減少68.4%。這表明改進(jìn)煙花算法的路徑尋優(yōu)效果優(yōu)于基本煙花算法，因為在原算法基礎(chǔ)上加入了導(dǎo)向因子及采用了競爭學(xué)習(xí)策略，使得算法搜索效率更加高效，因此在運用改進(jìn)算法對移動機器人進(jìn)行路徑規(guī)劃時，能夠更好的適應(yīng)機器人實際運行環(huán)境，幫助移動機器人高效完成工作任務(wù)。

圖5 特殊地形仿真結(jié)果對比

(2)特殊地形仿真。為驗證算法在特殊地形下的性能，將本文算法與文獻(xiàn)[1]算法進(jìn)行對比，結(jié)果如圖5所示。其中實線為文獻(xiàn)[1]仿真結(jié)果，虛線為本文算法仿真結(jié)果。

根據(jù)上述結(jié)果，可以看出在特殊的地形下，本文改進(jìn)的煙花算法在轉(zhuǎn)向次數(shù)上遠(yuǎn)少于文獻(xiàn)[1]中算法，而文獻(xiàn)[1]只追求路徑距離的最短，忽視了轉(zhuǎn)彎所帶來的損耗，這也使得機器人在轉(zhuǎn)向上的能量消耗大大增加。由此可以看出在極端環(huán)境下，本文改進(jìn)的煙花算法優(yōu)勢更加明顯，展現(xiàn)出更強的環(huán)境適應(yīng)能力。

4 結(jié)束語

針對煙花算法在路徑規(guī)劃存在的問題，提出了相應(yīng)的改進(jìn)方法。首先，設(shè)計了一種自適應(yīng)策略，動態(tài)調(diào)整優(yōu)勢煙花的爆炸半徑。其次，在迭代過程中加入導(dǎo)向因子對劣勢煙花的搜索進(jìn)行指引；另外，引入自由變異策略和競爭學(xué)習(xí)機制，提高收斂效果及效率。仿真實驗可以得出，常規(guī)環(huán)境下本文算法相比于基本煙花算法，最短路徑長度減少約9.5%，迭代時間縮短約60.8%，收斂代數(shù)減少約73.7%，轉(zhuǎn)彎次數(shù)減少68.4%，而在特殊地形下也能展現(xiàn)出良好的環(huán)境適應(yīng)力，因此更有利于機器人完成作業(yè)任務(wù)。