李月英

(鄭州科技學(xué)院電子與電氣工程學(xué)院，河南鄭州 450064)

0 前言

路徑規(guī)劃是移動(dòng)機(jī)器人研究的關(guān)鍵問(wèn)題之一，常簡(jiǎn)化為在復(fù)雜的地圖環(huán)境中，復(fù)雜約束條件下獲取最優(yōu)路徑規(guī)劃線路的優(yōu)化問(wèn)題。為更好地求解這類問(wèn)題，傳統(tǒng)路徑規(guī)劃方法可以實(shí)現(xiàn)移動(dòng)機(jī)器人的最優(yōu)路徑尋優(yōu)，如柵格法、人工勢(shì)場(chǎng)、連接圖法等[1-2]。但這些方法的求解效率較低，精度不足。為克服傳統(tǒng)路徑規(guī)劃方法存在的缺點(diǎn)，元啟發(fā)式智能算法引入隨機(jī)算子，具有快速、收斂精度高、易實(shí)現(xiàn)等優(yōu)點(diǎn)，被廣泛地應(yīng)用于求解各類復(fù)雜的移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題，如傳統(tǒng)的遺傳算法(Genetic Algorithm，GA)[3]，粒子群(Particle Swarm Optimization，PSO)算法[4]，人工蜂群(Artificial Bee Colony，ABC)算法[5]等。雖然傳統(tǒng)的元啟發(fā)式算法可以有效地解決移動(dòng)機(jī)器人路徑規(guī)劃，但是仍存在易陷入局部最優(yōu)的問(wèn)題。為此，研究學(xué)者著重于提高元啟發(fā)式算法的尋優(yōu)性能，采用多種改進(jìn)策略提出眾多算法如：改進(jìn)粒子群優(yōu)化算法[6], 改進(jìn)灰狼優(yōu)化算法[7]，改進(jìn)蟻群算法[8-10]，動(dòng)態(tài)分組蟻群算法[11]，煙花混合蟻群算法[12]，粒子群-蟻群算法[13]，量子風(fēng)驅(qū)動(dòng)優(yōu)化算法[14]，改進(jìn)ACO[15]等。相比傳統(tǒng)元啟發(fā)式算法，這些改進(jìn)算法可提升算法的全局尋優(yōu)精度和效率，應(yīng)用于求解移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題時(shí)，可使機(jī)器人有效地躲避障礙物，以較快的速度獲取較短的路徑規(guī)劃長(zhǎng)度。

烏燕鷗算法(Sooty Tern Optimization Algorithm， STOA)是一種模擬烏燕鷗群體生活行為(遷徙和撲食)的高效智能算法，與其他元啟發(fā)式算法相比，尋優(yōu)性能較好。針對(duì)高維復(fù)雜的優(yōu)化問(wèn)題，和其他算法一樣仍存在一定程度上的停滯現(xiàn)象，造成算法尋優(yōu)精度和效率低等[16]。

鑒于此，為提高STOA算法的性能，提出一種改進(jìn)的烏燕鷗算法(Improved Sooty Tern Optimization Algorithm，ISTOA)，并應(yīng)用于求解復(fù)雜環(huán)境下移動(dòng)機(jī)器人的路徑規(guī)劃問(wèn)題。算法的具體改進(jìn)方法為：在STOA算法初始化階段嵌入Circle混沌映射，保證種群的初始質(zhì)量；在遷徙階段混合正余弦非碰撞控制因子和自適應(yīng)Lévy飛行策略，協(xié)調(diào)算法全局搜索與局部探索；提出一種新穎的旋轉(zhuǎn)式翻筋斗策略并嵌入到撲食階段，提升算法的局部搜索能力。所提出算法的有效性通過(guò)不同的移動(dòng)路徑規(guī)劃問(wèn)題得以評(píng)估。

1 STOA算法

STOA算法是一種通過(guò)模擬烏燕鷗群體生活行為的智能算法，通過(guò)一些定義它被抽象為可循環(huán)迭代計(jì)算的數(shù)學(xué)模型。具體定義如下[15]：

定義1 遷徙位置更新。主要包含3種行為，避免碰撞見(jiàn)公式(1)和(2)，向最優(yōu)方向遷徙見(jiàn)公式(3)和(4)，靠近最優(yōu)位置見(jiàn)公式(5)。

C(k)=φ×P(k)

(1)

φ=2-[k×(2/kmax)]

(2)

式中：C(k)為烏燕鷗當(dāng)前未發(fā)生碰撞的遷移位置；P(k)為烏燕鷗個(gè)體當(dāng)前位置；φ為避免發(fā)生碰撞因子；k為當(dāng)前迭代次數(shù)；kmax為最大迭代次數(shù)。

M(k)=λ×[Pb(k)-P(k)]

(3)

λ=0.5×β

(4)

其中：M(k)為烏燕鷗當(dāng)前遷移位置;Pb(k)為當(dāng)前烏燕鷗最優(yōu)解位置；λ為全局可調(diào)因子；β為[0,1]范圍內(nèi)的隨機(jī)數(shù)。

D(k)=C(k)+M(k)

(5)

式中：D為烏燕鷗最終遷移位置。

定義2 撲食位置更新。在遷移過(guò)程中，烏燕鷗采用螺旋式撲食方法[見(jiàn)公式(6)]，在局部范圍內(nèi)進(jìn)行獵物的搜索。因此，烏燕鷗的位置更新見(jiàn)式(7):

(6)

式中：R為螺旋線半徑；θ為[0,2π]范圍內(nèi)的隨意u和v表示螺旋形狀的超參數(shù)。

P(k)=[D×(x′×y′×z′)]×Pb(k)

(7)

2 改進(jìn)烏燕鷗算法(ISTOA)

2.1 改進(jìn)STOA算法(ISTOA)簡(jiǎn)介

(1)種群混沌初始化

對(duì)STOA算法的種群初始化方式進(jìn)行混沌化，可以增強(qiáng)種群的初始均勻分布，提高算法的初始收斂速度和精度，因此采用Circle映射對(duì)其種群進(jìn)行初始化，見(jiàn)式(8)

(8)

(2)正弦控制非碰撞因子

由圖1可知：在STOA中，參數(shù)φ受迭代次數(shù)的影響逐漸線性遞減。線性下降方式制約著算法的全局搜索和局部搜索，影響算法尋優(yōu)性能。

圖1 非碰撞因子對(duì)比Fig.1 Comparison of non-collision factors

當(dāng)φ越大全局搜索能力越強(qiáng)，反之，局部搜索能力越強(qiáng)。為增強(qiáng)STOA算法的局部搜索能力，將φ修改為正弦控制方式的非線性遞減因子，見(jiàn)(9)。由圖1可知：采用正弦控制方式，可增強(qiáng)非碰撞因子φ的自我動(dòng)態(tài)調(diào)整能力，在迭代前期φ變化較快，迭代后期φ變化較慢。這樣可實(shí)現(xiàn)STOA算法的迭代前期快速全局搜索，迭代后期最大化地進(jìn)行局部搜索。

(9)

(3)旋轉(zhuǎn)式翻筋斗撲食策略

由于烏燕鷗算法無(wú)限逼近全局最優(yōu)解時(shí)，難以跳出最優(yōu)解的鄰域，導(dǎo)致陷入局部最優(yōu)。標(biāo)準(zhǔn)的翻筋斗策略可提高算法跳出局部的能力[17]。烏燕鷗翻斗撲食如圖2所示,在不同區(qū)域(即A、B、C等)以獵物為空翻支撐點(diǎn)，每次撲食過(guò)程中，當(dāng)前烏燕鷗會(huì)更新至獵物的對(duì)稱位置處。這種撲食的數(shù)學(xué)模型可式(10)：

(10)

圖2 標(biāo)準(zhǔn)的翻筋斗撲食策略Fig.2 A standard somersault strategy

由圖2可知，第i只烏燕鷗只能以固定的空翻步長(zhǎng)F分別隨機(jī)空翻在對(duì)應(yīng)的有限搜索區(qū)域A、B、C內(nèi)，但有限的區(qū)域會(huì)使烏燕鷗種群的多樣性減弱，不利于算法逃離局部最優(yōu)。為此，引入空翻旋轉(zhuǎn)角度β(0≤β≤2π)(見(jiàn)圖3)，顯而易見(jiàn)，隨著空翻旋轉(zhuǎn)角度β不斷地變化，可以有效地豐富烏燕鷗個(gè)體空翻空間，保持迭代后期種群的多樣性，進(jìn)一步提高算法的局部尋優(yōu)能力。采用這種旋轉(zhuǎn)式翻斗撲食策略見(jiàn)圖4，一方面可以增加空翻的空間，擴(kuò)大種群搜索空間，另一方面也可以保持種群的分布均勻性和多樣性，提升算法的尋優(yōu)性能。因此，對(duì)公式(10)中空翻旋轉(zhuǎn)角度β，改進(jìn)為旋轉(zhuǎn)式翻筋斗撲食位置更新方式見(jiàn)式(11)，即對(duì)STOA算法的烏燕鷗個(gè)體的撲食位置更新方式修改為旋轉(zhuǎn)式翻筋斗撲食位置模式見(jiàn)式(11)。

圖3 旋轉(zhuǎn)式翻斗單一撲食行為Fig.3 Single feeding behavior by rotary somersault

圖4 旋轉(zhuǎn)式翻斗群體撲食行為Fig.4 Group feeding behavior by rotary somersault

(11)

(4)自適應(yīng)Lévy飛行策略

為增強(qiáng)STOA算法全局尋優(yōu)能力，引入自適應(yīng)因子w，見(jiàn)式(12)。在STOA遷徙位置中引入自適應(yīng)因子和Lévy飛行因子可以提高算法的種群多樣性和擴(kuò)大探索空間，提高算法的收斂速度和收斂精度。Lévy飛行因子可由式(13)計(jì)算。因此，在STOA中，式(5)可修改為式(14)。

(12)

式中：wmax和wmin分別為初設(shè)的自適應(yīng)因子的最大和最小值。

Lévy(β)≈α-β

(13)

式中：α為隨機(jī)飛行搜索步長(zhǎng)；β∈(1,3]。

(14)

同時(shí)，STOA算法搜索后期，烏燕鷗落入最優(yōu)位置附近，由于此時(shí)的種群多樣性較弱，無(wú)法保證烏燕鷗能夠無(wú)限逼近最優(yōu)解，所以，采用Lévy飛行因子對(duì)烏燕鷗最優(yōu)個(gè)體變異，見(jiàn)式(15)

(15)

2.2 基于ISTOA的移動(dòng)機(jī)器人路徑規(guī)劃算法

綜合以上改進(jìn)方法，文中提出的基于ISTOA移動(dòng)機(jī)器人路徑規(guī)劃算法流程如圖5所示，步驟如下：

(1)初始化設(shè)置。搭建柵格地圖環(huán)境，設(shè)置機(jī)器人的起始與終止坐標(biāo)位置，設(shè)置ISTOA算法種群數(shù)量、最大迭代次數(shù)等；

(2)利用Circle映射對(duì)種群進(jìn)行初始化即式(8)，并評(píng)估初始最佳路徑長(zhǎng)度，確定初始最優(yōu)路徑信息；

(3)采用旋轉(zhuǎn)式翻斗進(jìn)行撲食位置更新即式(11)和式(6)；

(4)采用自適應(yīng)Lévy飛行方式更新遷徙位置，即式(1)(3)(4)(9)(12)(13)；

(5)重新評(píng)估路徑適應(yīng)度值更新最佳路徑長(zhǎng)度及路徑信息；

(6)用式(15)對(duì)其最優(yōu)路徑進(jìn)行變異；

(7)判斷是否滿足最大迭代次數(shù)，若是，則輸出全局最佳路徑長(zhǎng)度及最優(yōu)路徑信息，反之，返回步驟(3)繼續(xù)尋優(yōu)；

(8)算法尋優(yōu)結(jié)束，輸出最優(yōu)結(jié)果。

圖5 基于ISTOA的移動(dòng)機(jī)器人路徑規(guī)劃算法

3 路徑規(guī)劃實(shí)驗(yàn)仿真與分析

3.1 實(shí)驗(yàn)參數(shù)與地圖環(huán)境設(shè)置

為了驗(yàn)證所提ISTOA算法在路徑規(guī)劃上的有效性，采用柵格法構(gòu)建3種不同規(guī)格的地圖環(huán)境，如圖6—圖8所示。圖中黑色代表障礙物，白色代表可通行區(qū)域，并設(shè)置有始末點(diǎn)。為驗(yàn)證ISTOA算法在移動(dòng)機(jī)器人路徑規(guī)劃中的尋優(yōu)性能，選用STOA[16]、SOA[18]、SCA[19]和ISTOA算法進(jìn)行對(duì)比分析，實(shí)驗(yàn)結(jié)果評(píng)價(jià)指標(biāo)選取20次，各個(gè)算法獨(dú)立運(yùn)行獲得最小路徑長(zhǎng)度、平均路徑長(zhǎng)度、成功率、路徑長(zhǎng)度標(biāo)準(zhǔn)差和平均運(yùn)行時(shí)間。各算法種群數(shù)量選擇為100，最大迭代次數(shù)為700。起始柵格為S=1,3種不同規(guī)格的路徑柵格G=200、1 600、2 500。

圖6 20 m×20 m柵格化地圖Fig.6 The 20 m×20 m rasterization map

圖7 40 m×40 m柵格化地圖Fig.7 The 40 m×40 m rasterization map

圖8 50 m×50 m柵格化地圖Fig.8 The 50 m×50 m rasterization map

3.2 實(shí)驗(yàn)結(jié)果與分析

在20 m×20 m、40 m×40 m和50 m×50 m地圖環(huán)境下，4種算法的實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果見(jiàn)表1—表3，最優(yōu)路徑和迭代收斂曲線對(duì)比見(jiàn)圖9—圖11。

表1 20 m×20 m地圖路徑規(guī)劃統(tǒng)計(jì)結(jié)果

表2 40 m×40 m地圖路徑規(guī)劃統(tǒng)計(jì)結(jié)果

表3 50 m×50 m地圖路徑規(guī)劃統(tǒng)計(jì)結(jié)果

圖9 20 m×20 m地圖最優(yōu)路徑(a)與迭代收斂曲線(b)

圖10 40 m×40 m地圖最優(yōu)路徑(a)與迭代收斂曲線(b)

圖11 50 m×50 m地圖最優(yōu)路徑(a)與迭代收斂曲線(b)

由表1—表3統(tǒng)計(jì)結(jié)果可知：對(duì)于20 m×20 m、40 m×40 m和50 m×50 m地圖，ISTOA算法可分別獲得最短路徑長(zhǎng)度為30.500、60.036、73.439 m。與SOA、STOA和SCA算法相比，ISTOA的最短路徑長(zhǎng)度均短于其他算法，除了40 m×40 m地圖環(huán)境，ISTOA算法長(zhǎng)于STOA算法但短于SOA和SCA算法。對(duì)于平均路徑長(zhǎng)度和路徑長(zhǎng)度標(biāo)準(zhǔn)差，ISTOA算法均優(yōu)于其他算法。

從成功率來(lái)說(shuō)，對(duì)于所有的地圖環(huán)境，ISTOA算法成功率達(dá)到了100%，高于或者等于其他算法，全部能夠成功實(shí)現(xiàn)移動(dòng)機(jī)器人路徑最優(yōu)規(guī)劃。然而，其他算法成功率不穩(wěn)定。從平均耗時(shí)來(lái)看，對(duì)于所有的地圖環(huán)境，ISTOA算法耗時(shí)最長(zhǎng)，SCA算法耗時(shí)較短，SOA算法和STOA算法耗時(shí)居中。隨著地圖環(huán)境復(fù)雜性的增加，所有算法的耗時(shí)均增加。ISTOA算法的耗時(shí)增加是由于采用多種改進(jìn)策略，增強(qiáng)了算法種群的多樣性，提高了尋優(yōu)精度。

由圖9—圖10可知：對(duì)于不同規(guī)格的地圖環(huán)境，從最優(yōu)路徑來(lái)看，ISTOA算法路徑長(zhǎng)度短，路徑中的轉(zhuǎn)折次數(shù)較少，路徑平滑度較好，總能夠獲得較為合理的移動(dòng)機(jī)器人移動(dòng)路徑；從迭代收斂曲線來(lái)看，ISTOA算法迭代收斂曲線均位于其他算法下方，可以快速地獲得最優(yōu)路徑，收斂速度和全局最優(yōu)解均優(yōu)于其他算法?？擅黠@地看出，STOA算法容易在局部停滯，不易跳出局部極值，且全局收斂精度低。與STOA算法相比，ISTOA算法改善了STOA算法易陷入局部最優(yōu)的現(xiàn)象且全局收斂精度更高。在迭代初期，ISTOA算法就能夠快速下降，這是由于采用了Circle混沌映射提高了迭代初期的收斂速度。在迭代中后期，ISTOA算法可以快速地跳出局部最優(yōu)，這是旋轉(zhuǎn)式翻筋斗搜索策略的獨(dú)特優(yōu)勢(shì)所在，同時(shí)采用自適應(yīng)正余弦因子和Lévy飛行策略平衡了算法全局與局部之間搜索能力。

綜上所述，在復(fù)雜環(huán)境中，ISTOA算法可以快速地實(shí)現(xiàn)移動(dòng)機(jī)器人最優(yōu)路徑規(guī)劃，且擁有較好的尋優(yōu)能力。

4 結(jié)論

(1)為提高移動(dòng)機(jī)器人路徑尋優(yōu)效率與精度，利用Circle映射提高算法初始種群質(zhì)量，自適應(yīng)正余弦非碰撞控制因子和Lévy飛行協(xié)同算法全局與局部搜索，旋轉(zhuǎn)式翻筋斗避免算法早熟，提出了改進(jìn)烏燕鷗算法(ISTOA)。

(2)提出了一種新穎的旋轉(zhuǎn)式翻筋斗搜索策略，避免了算法在處理移動(dòng)機(jī)器人路徑規(guī)劃時(shí)易陷入局部極值。

(3)路徑規(guī)劃仿真實(shí)驗(yàn)表明：與SOA、STOA和SCA算法相比，ISTOA算法能實(shí)時(shí)地躲避障礙物，可提供較優(yōu)的路徑規(guī)劃尋優(yōu)結(jié)果，并且耗時(shí)較短、成功率高、穩(wěn)定性和魯棒性更強(qiáng)。