基于改進(jìn)蝗蟲優(yōu)化算法的移動機(jī)器人路徑規(guī)劃*

徐亞杰 王海星

(①鄭州升達(dá)經(jīng)貿(mào)管理學(xué)院信息工程學(xué)院，河南 鄭州 451191;②河南理工大學(xué)電氣工程與自動化學(xué)院，河南 焦作 454003)

路徑規(guī)劃能力是移動機(jī)器人完成自主移動必須具備的能力之一，一直以來都備受國內(nèi)外學(xué)者的青睞，開展了大量的研究工作，許多移動機(jī)器人路徑規(guī)劃方法相繼被提出并應(yīng)有。從目前國內(nèi)外相關(guān)文獻(xiàn)來看，這些方法大致可分為傳統(tǒng)方法和智能方法兩類。傳統(tǒng)方法主要包括人工勢場法[1-2]、A*算法[3-4]等，它們的運算速度相對較慢，而智能算法在總體運算效率、路徑規(guī)劃效果等方面普遍要比傳統(tǒng)算法更優(yōu)。因此，基于智能算法的機(jī)器人路徑規(guī)劃的應(yīng)用也越來越多。如變步長蟻群算法[5]、自適應(yīng)遺傳算法[6]、改進(jìn)人工魚群算法[7]、混合灰狼算法[8]、混合粒子群算法[9]和鯨魚優(yōu)化算法[10]等多種智能算法都被應(yīng)用到了機(jī)器人的路徑規(guī)劃中，并且均得到了較為理想的路徑規(guī)劃效果。

2017年提出的蝗蟲優(yōu)化算法(grasshopper optimization algorithm, GOA)同前文提及的智能算法一樣，也是一種智能優(yōu)化算法，目前已得到廣泛應(yīng)用[11-13]。但GOA同前文所述的智能算法相似，算法本身存在有易陷入局部最優(yōu)、后期收斂精度不足等問題[14-15]，如果直接將其用于機(jī)器人的路徑規(guī)劃中，算法本身存在的缺陷勢必會對路徑規(guī)劃效果造成影響。因此，有必要對其缺陷進(jìn)行改進(jìn)設(shè)計，以達(dá)到提升機(jī)器人路徑規(guī)劃效果的目的。

本文以GOA為移動機(jī)器人路徑規(guī)劃方法，同時針對GOA存在的缺陷，對其進(jìn)行改進(jìn)設(shè)計，提出改進(jìn)蝗蟲優(yōu)化算法(improved grasshopper optimization algorithm, IGOA)，以提升機(jī)器人路徑規(guī)劃效果。機(jī)器人2種不同行駛環(huán)境的路徑規(guī)劃實例驗證了IGOA算法的有效性。

1 柵格法中的蝗蟲優(yōu)化算法

通過智能算法進(jìn)行移動機(jī)器人的路徑規(guī)劃包含兩部分內(nèi)容，一是進(jìn)行環(huán)境建模，二是通過智能算法反復(fù)迭代得到最優(yōu)路徑。進(jìn)行環(huán)境建模的方法有很多種，如可視圖法、單元分解法、幾何法和柵格法等，其中柵格法最簡單且應(yīng)用最為廣泛。

根據(jù)柵格法的原理，建立1個如圖1所示的10×10柵格的機(jī)器人行駛區(qū)域。圖1中，黑色柵格表示障礙物，將其賦值為1，即機(jī)器人不能觸碰或翻越該柵格；白色柵格表示可行區(qū)域，將其賦值為0，即機(jī)器人可在其上自由移動。路徑規(guī)劃從左上角的起點至右下角的終點，每步移動的長度在1×1正方形柵格內(nèi)，最長距離為斜對角。

2 蝗蟲優(yōu)化算法

眾所周知，GOA是模仿自然界蝗蟲的覓食行為而提出的一種智能仿生算法。在GOA中，蝗蟲個體所在的位置表示所求優(yōu)化問題的一個候選解，它主要受蝗蟲種群間的相互作用力、風(fēng)力和重力等3個因素的影響，可用式(1)所示的數(shù)學(xué)模型進(jìn)行表示。

Xi=Si+Gi+Ai

(1)

式中:Xi為第i只蝗蟲所處的位置；Si為第i只蝗蟲所受種群間相互作用力的影響；Gi為第i只蝗蟲所受外界重力的影響；Ai為第i只蝗蟲所受外界風(fēng)力的影響。在進(jìn)行數(shù)學(xué)優(yōu)化問題求解時，為了對數(shù)學(xué)模型進(jìn)行優(yōu)化，式(1)中的外界重力影響Gi和風(fēng)力影響Ai需要被替換為目標(biāo)食物的位置Td。這樣，式(1)就可以改寫成式(2)。

Xi=Si+Td

(2)

其中：Si主要通過式(3)計算。

(3)

(4)

式(3)中的s函數(shù)為計算蝗蟲種群間相互作用力的函數(shù)，其表達(dá)式如式(5)所示。

(5)

其中：f為吸引強(qiáng)度參數(shù)、r為吸引尺度參數(shù)。

在整個搜索迭代的過程中，蝗蟲每個位置優(yōu)劣的評價指標(biāo)為適應(yīng)度函數(shù)(目標(biāo)函數(shù))。對于移動機(jī)器人路徑規(guī)劃而言，適應(yīng)度函數(shù)通常采用得最多的是滿足移動路徑最短。在進(jìn)行優(yōu)化問題的求解過程中，式(2)被不斷用來循環(huán)迭代以得到最優(yōu)解，每完成一次迭代后得到的最優(yōu)適應(yīng)度值即被記錄為當(dāng)前得到的最優(yōu)解，最優(yōu)解所在位置即被視為目標(biāo)食物的位置Td，直至達(dá)到最大迭代次數(shù)。

3 改進(jìn)蝗蟲優(yōu)化算法

從蝗蟲優(yōu)化算法的基本原理可知，在其整個計算過程中，蝗蟲種群幾乎沒有變化，缺乏隨機(jī)因素，且沒有跳出局部最優(yōu)的機(jī)制，這就使得算法比較容易陷入局部最優(yōu)后無法跳出，最終影響優(yōu)化性能。文獻(xiàn)[14]提出了一種混合變異蝗蟲優(yōu)化算法(MMGOA)，通過柯西變異對蝗蟲位置進(jìn)行擾動，從而保證蝗蟲個體具有一定概率跳出局部最優(yōu)。而柯西分布概率密度函數(shù)可知，生成短步長的概率遠(yuǎn)高于長步長，這就使得對蝗蟲位置的擾動以小擾動為主，并不能保證蝗蟲真正能夠跳出局部最優(yōu)；文獻(xiàn)[15]提出了一種多目標(biāo)蝗蟲優(yōu)化算法(MOGOA)，通過曲線自適應(yīng)策略對參數(shù)進(jìn)行調(diào)控，從而一定程度上實現(xiàn)了算法前后搜索能力的平衡。而曲線自適應(yīng)策略的參數(shù)值前大后下，雖前期收斂較快，但在后期參數(shù)值較小時，容易導(dǎo)致陷入局部最優(yōu)。

針對上述問題，本文借鑒MMGOA和MOGOA對GOA的改進(jìn)思路，從兩個方面對GOA進(jìn)行改進(jìn)設(shè)計，得到IGOA算法。

3.1 Levy飛行局部搜索策略

Levy飛行策略是一種移動步長隨機(jī)性極強(qiáng)的行走方式，能夠保證生成長、短步長的概率大體相當(dāng)(柯西分布短步長的概率遠(yuǎn)大于長步長)。將Levy飛行隨機(jī)步長引入到GOA算法中，可以增強(qiáng)算法的隨機(jī)性和局部搜索能力，提高跳出局部最優(yōu)的概率。當(dāng)蝗蟲種群在完成一次迭代搜索后，通過Levy飛行步長對蝗蟲個體所在的位置進(jìn)行局部調(diào)整，如式(6)所示。

X=X+10×sts×L×X

(6)

其中：sts為一個閾值函數(shù)，用于控制飛行方法和變化概率，其計算方式如式(7)所示；L為Levy飛行步長，其計算方式如式(8)所示。

sts=sign(xtrans-1)+sign(xtrans+1)

(7)

其中：xtrans為[-3,3]之間的隨機(jī)數(shù)，sign為符號函數(shù)。

L=μ/|v|1/β

(8)

其中：參數(shù)β范圍為(0,2)，一般取1.5；參數(shù)μ、v服從式(9)所示的正太分布，標(biāo)準(zhǔn)差σμ、σv的取值根據(jù)式(10)計算。

(9)

(10)

在一定程度上，Levy飛行的引入為蝗蟲個體提供了一定的“視覺”，能夠讓蝗蟲個體“看清”自身周圍一片區(qū)域內(nèi)食物的情況，使得蝗蟲個體能夠在局部范圍內(nèi)進(jìn)行更有針對性的搜索。

3.2 線性遞減參數(shù)隨機(jī)跳出策略

為保證GOA前后搜索能力的平衡且具有跳出局部最優(yōu)的機(jī)制，提出線性遞減參數(shù)的隨機(jī)跳出策略(曲線自適應(yīng)策略雖在一定程上平衡了前后搜索能力，但在后期容易導(dǎo)致陷入局部最優(yōu))。當(dāng)蝗蟲個體搜索到當(dāng)前最優(yōu)解的位置后，利用該位置對原位置進(jìn)行替換，如果沒有搜索到最優(yōu)解，則啟動隨機(jī)跳出策略，其計算方式如式(11)所示。

Xi=(2×(0.5-rand(0,1))+1)×Xi

(11)

其中：Xi是蝗蟲i所在位置。假如搜索到的新Xi更優(yōu)，則對舊Xi進(jìn)行替換，替換一次則可認(rèn)為成功完成了一次跳出行為。為了保證跳出成功后的位置信息能夠被有效利用，將搜索迭代式(2)調(diào)整為式(12)：

Xi=Si+(1-p)×Td+p×Xi

(12)

其中：p是控制協(xié)調(diào)參數(shù)，首次迭代時為0。它按照式(13)進(jìn)行計算。

(13)

根據(jù)式(13)可知，當(dāng)蝗蟲個體未進(jìn)行跳出或者跳出失敗時，p仍然為0，這就保證了只有Si和Td能夠影響下一次迭代；當(dāng)蝗蟲個體完成了一次成功跳出后，p在后續(xù)的3次迭代中按照0.35的間隔逐步線性遞減為0，這就保證了蝗蟲個體在成功跳出一次局部最優(yōu)后能夠?qū)罄m(xù)3次迭代產(chǎn)生影響。

3.3 IGOA算法流程

根據(jù)GOA算法基本原理和3.1節(jié)、3.2節(jié)的描述，本文提出的IGOA算法流程如圖2所示。

4 機(jī)器人路徑規(guī)劃實例分析

本文一共構(gòu)建了2種機(jī)器人行駛環(huán)境來對本文所提IGOA方法在路徑規(guī)則中的有效性進(jìn)行驗證。2種環(huán)境分別為：在MATLAB中構(gòu)建的仿真20×20柵格地圖，用于模擬機(jī)器人較為簡單的行駛環(huán)境；在MATLAB中構(gòu)建的仿真40×40柵格地圖，用于模擬機(jī)器人較為復(fù)雜的行駛環(huán)境。同時，為驗證本文IGOA的路徑規(guī)劃性能，還將其與GOA、參考文獻(xiàn)[14]中的混合變異蝗蟲算法(MMGOA)、參考文獻(xiàn)[15]中多目標(biāo)蝗蟲算法(MOGOA)進(jìn)行對比分析。在進(jìn)行機(jī)器人路徑規(guī)劃時，上述4種方法中蝗蟲種群的規(guī)模均設(shè)置為30，迭代達(dá)到100次后均停止迭代，輸出最優(yōu)結(jié)果，MMGOA和MOGOA兩種方法的相關(guān)其余參數(shù)均按原文獻(xiàn)進(jìn)行設(shè)置。

4.1 仿真20×20柵格地圖分析

利用4種方法進(jìn)行仿真20×20柵格地圖中的機(jī)器人路徑規(guī)劃時，每種方法均獨立運行30次，記錄下每次計算的結(jié)果。表1給出了4種方法的計算結(jié)果統(tǒng)計，其中平均值為30次計算結(jié)果的平均值，耗時為規(guī)劃得到最短路徑的時間消耗；圖3給出了4種方法所得最短路徑的可視化結(jié)果；圖4給出了4種方法的迭代過程。

由表1、圖3和圖4的結(jié)果可知，從最短路徑指標(biāo)來看，IGOA分別比GOA、MMGOA和MOGOA縮短了9.3%、2%和3.9%；從最長路徑指標(biāo)來看，IGOA得到結(jié)果比其余3種方法的均要好，特別是比GOA得到的最短路徑還要好；從標(biāo)準(zhǔn)差指標(biāo)來看，IGOA的標(biāo)準(zhǔn)差最小，表明算法的穩(wěn)定性要好于其余3種；從耗時指標(biāo)來看，IGOA、MMGOA和MOGOA均是在GOA的基礎(chǔ)上進(jìn)行的改進(jìn)，因此算法較GOA的復(fù)雜度均有所增加，故耗時不如GOA更優(yōu)，雖然耗時增加，但得到的路徑均要好于GOA。以上分析結(jié)果表明，IGOA在5種評價指標(biāo)中，除耗時上不如GOA外，其余4種指標(biāo)均是要優(yōu)于GOA、MMGOA和MOGOA方法。

表1 仿真20×20柵格地圖計算結(jié)果

4.2 仿真40×40柵格地圖分析

利用4種方法進(jìn)行仿真40×40柵格地圖中的機(jī)器人路徑規(guī)劃，分別得到表2的計算結(jié)果、圖5的最短路徑可視化結(jié)果和圖6的迭代過程。

由表2、圖5和圖6的結(jié)果可知，隨著路徑環(huán)境的復(fù)雜，算法的優(yōu)勢得以更加明顯的體現(xiàn)。同時也可知，4種方法對仿真40×40柵格地圖的路徑規(guī)劃結(jié)果和仿真20×20柵格地圖的路徑規(guī)劃結(jié)果比較相似，即：IGOA在5種評價指標(biāo)中，除耗時上不如GOA外，其余4種指標(biāo)均是要優(yōu)于GOA、MMGOA和MOGOA方法。其中，IGOA的最短路徑指標(biāo)分別比GOA、MMGOA和MOGOA縮短了7.3%、3%和6.1%； IGOA的最長路徑同樣比GOA得到的最短路徑還要好； IGOA的標(biāo)準(zhǔn)差在0.1以下，而其余3種方法均大于0.1； IGOA的耗時同樣是排名第2。

表2 仿真40×40柵格地圖計算結(jié)果

5 結(jié)語

為有效提升移動機(jī)器人的路徑規(guī)劃效果，針對GOA存在的不足，將Levy飛行策略局部搜索策略和線性遞減參數(shù)隨機(jī)跳出策略引入到GOA，提出了IGOA算法。通過移動機(jī)器人3種環(huán)境下的路徑規(guī)劃實例驗證了IGOA算法在路徑規(guī)劃中的優(yōu)勢。