肖輝輝，段艷明

(河池學(xué)院 計(jì)算機(jī)與信息工程學(xué)院，廣西 宜州 546300)

0 引言

隨著智能機(jī)器人開始廣泛應(yīng)用于社會(huì)生活的各個(gè)領(lǐng)域，移動(dòng)機(jī)器人的路徑規(guī)劃問(wèn)題成為當(dāng)前學(xué)術(shù)界的研究熱點(diǎn)之一。移動(dòng)機(jī)器人路徑規(guī)劃是指機(jī)器人能避開環(huán)境中的障礙物，找到一條從起始點(diǎn)到目標(biāo)終點(diǎn)的無(wú)碰撞、路徑最短且安全的優(yōu)化路徑[1]。國(guó)內(nèi)外學(xué)者對(duì)移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題進(jìn)行了大量研究，并提出了很多求解方法。目前解決移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題的主要方法有局部路徑規(guī)劃與全局路徑規(guī)劃，局部路徑規(guī)劃主要是基于傳感器信息的路徑規(guī)劃，而全局路徑規(guī)劃主要是對(duì)環(huán)境模型的路徑規(guī)劃[2]。近年來(lái)，群智能優(yōu)化算法因其具有良好的優(yōu)化能力，開始越來(lái)越多地應(yīng)用于移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題的求解，并取得了良好效果。潘桂彬等[3]構(gòu)建一種新型改進(jìn)蛙跳算法對(duì)移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題進(jìn)行求解，在改進(jìn)算法的更新機(jī)制中融入種群最優(yōu)個(gè)體與歐氏距離策略，并把對(duì)該問(wèn)題的求解轉(zhuǎn)換為對(duì)最小化優(yōu)化問(wèn)題的求解，根據(jù)測(cè)試環(huán)境中的目標(biāo)與阻礙物處所定義個(gè)體適應(yīng)度，實(shí)驗(yàn)結(jié)果檢驗(yàn)了新算法具有良好的路徑優(yōu)化能力；王慧等[4]構(gòu)建一種對(duì)粒子個(gè)體極值增加加權(quán)平均值與慣性權(quán)重的改進(jìn)粒子群算法，并應(yīng)用于移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題求解，獲得了較好的實(shí)驗(yàn)結(jié)果，提高了復(fù)雜環(huán)境下移動(dòng)機(jī)器人導(dǎo)航的精準(zhǔn)性；劉潔等[5]利用群體離散度與種群個(gè)體演化速度對(duì)慣性權(quán)重進(jìn)行動(dòng)態(tài)調(diào)整，通過(guò)對(duì)算法慣性權(quán)重的改進(jìn)策略，使粒子群算法在一定程度上避免了早熟收斂，提升了算法性能，在求解移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題中也獲得了較好效果。

花授粉優(yōu)化算法是一種新型群智能優(yōu)化算法，為了提高FPA的全局優(yōu)化能力，諸多學(xué)者對(duì)其進(jìn)行了改進(jìn)研究。Zhou等[6]將精英反向?qū)W習(xí)機(jī)制與自適應(yīng)貪婪策略引入FPA算法中，同時(shí)采用動(dòng)態(tài)轉(zhuǎn)換概率方法，使改進(jìn)算法在收斂速度與計(jì)算精度方面得到了較大改進(jìn)；孫朝東等[7]利用模擬退火算法改進(jìn)FPA算法，并運(yùn)用改進(jìn)算法對(duì)SVM參數(shù)進(jìn)行優(yōu)化，設(shè)計(jì)了一種新的對(duì)短時(shí)交通流量進(jìn)行預(yù)測(cè)的模型，實(shí)驗(yàn)結(jié)果表明，構(gòu)建的預(yù)測(cè)模型提高了交通流量預(yù)測(cè)準(zhǔn)確率。上述改進(jìn)策略在一定程度上提高了FPA算法的收斂能力，也擴(kuò)展了花授粉優(yōu)化算法的應(yīng)用領(lǐng)域，但目前針對(duì)該算法在移動(dòng)機(jī)器人路徑規(guī)劃中的相關(guān)研究仍鮮有報(bào)道。因此，本文針對(duì)花授粉優(yōu)化算法的局限性提出基于差分進(jìn)化策略的改進(jìn)花授粉算法，并研究群智能算法在移動(dòng)機(jī)器人路徑規(guī)劃中的應(yīng)用過(guò)程，將改進(jìn)的花授粉優(yōu)化算法用于求解移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題，并取得較好的優(yōu)化性能。

1 花授粉優(yōu)化算法

英國(guó)劍橋大學(xué)學(xué)者Xin-she Yang[8]于2012年提出一種新型元啟發(fā)式群智能優(yōu)化算法——花授粉算法(Flower Pollination Algorithm, FPA)，該算法由基于萊維飛行的隨機(jī)游動(dòng)、偏好隨機(jī)游動(dòng)及貪婪演化機(jī)制構(gòu)成，且算法勘探與開發(fā)之間的相互轉(zhuǎn)換，通過(guò)轉(zhuǎn)換概率參數(shù)p實(shí)現(xiàn)動(dòng)態(tài)控制，從而較好地解決了算法全局搜索與局部搜索的平衡問(wèn)題。由于FPA思想具有清晰、實(shí)現(xiàn)簡(jiǎn)單及全局收斂能力強(qiáng)等優(yōu)點(diǎn)，受到國(guó)內(nèi)外學(xué)者的廣泛關(guān)注，并對(duì)其進(jìn)行了大量理論及應(yīng)用研究。該算法模擬自然界中顯花植物的花朵傳粉過(guò)程，算法實(shí)現(xiàn)中假定每株顯花植物只開一朵花，且只有一個(gè)花粉配子，一個(gè)花粉配子對(duì)應(yīng)優(yōu)化問(wèn)題中的一個(gè)解，且還需假定以下幾個(gè)準(zhǔn)則[8]：

準(zhǔn)則1：生物異花授粉是指鳥、蜜蜂等傳播者攜帶其花粉通過(guò)Lévy進(jìn)行的全局授粉過(guò)程。

準(zhǔn)則2：非生物的自花授粉是通過(guò)其自身局部授粉加以實(shí)現(xiàn)。

準(zhǔn)則3：繁衍概率指花的常性，其值的大小與求解兩朵花的相似性成一定比例關(guān)系[9]。

準(zhǔn)則4：全局授粉與局部授粉之間的轉(zhuǎn)換受轉(zhuǎn)換概率p∈[0, 1]控制[10]，因花朵會(huì)受到物理位置上的近鄰性以及風(fēng)等其它自然因素影響，使授粉更偏重于自花授粉[11]。

因此，在FPA算法中，其全局搜索與局部搜索是個(gè)體演化的主體部分[12]，該算法的探測(cè)(全局授粉)部分是利用公式(1)實(shí)現(xiàn)的，開采(局部授粉)部分是運(yùn)用公式(3)實(shí)現(xiàn)的。

(1)

(2)

其中λ=3/2，Γ(λ)是標(biāo)準(zhǔn)的伽馬函數(shù)。

花朵個(gè)體通過(guò)公式(2)進(jìn)行局部搜索：

(3)

2 改進(jìn)花授粉優(yōu)化算法的移動(dòng)機(jī)器人路徑規(guī)劃

針對(duì)花授粉優(yōu)化算法存在的局限性，先對(duì)其進(jìn)行改進(jìn)，然后用于求解機(jī)器人路徑規(guī)劃問(wèn)題。因此，需要對(duì)機(jī)器人的工作環(huán)境進(jìn)行建模，根據(jù)路徑優(yōu)化目標(biāo)建立適應(yīng)度函數(shù)，最后對(duì)移動(dòng)機(jī)器人路徑進(jìn)行優(yōu)化。

2.1 基于差分進(jìn)化的花授粉優(yōu)化算法

差分進(jìn)化算法(Differential Evolution, DE)[15]是一種運(yùn)用種群在演化過(guò)程中個(gè)體之間的差異性進(jìn)行優(yōu)化的進(jìn)化算法，該算法的基本思路是利用進(jìn)化中種群個(gè)體間的矢量差組合獲得中間種群個(gè)體[16-17]，然后使用父代個(gè)體與中間個(gè)體進(jìn)行比較而得到后代種群。DE算法的變異機(jī)制使算法在進(jìn)化初期具有良好的探索能力，而到了演化后期，由于種群中個(gè)體之間的差異性越來(lái)越小，從而使DE算法具有較好的開采能力。DE算法的演化過(guò)程主要通過(guò)以下3種策略實(shí)現(xiàn)：

(1)變異操作。變異操作是DE算法的核心策略。

vij(t)=xa(t)+F(xb(t)-xc(t))

(4)

其中，xa(t)、xb(t)、xc(t)是進(jìn)化中隨機(jī)選取的3個(gè)種群個(gè)體，下標(biāo)a、b、c、i4個(gè)變量互不相等，且a、b、c是在1～N之間隨機(jī)選取的正整數(shù)。參數(shù)F是縮放因子[18]，且F∈[0，2]。

(2)交叉操作。DE算法的交叉操作可以有效增加種群個(gè)體間的差異性，該操作通過(guò)公式(5)對(duì)第t代進(jìn)化種群{xi(t)}與其經(jīng)過(guò)變異操作的種群{vi(t+1)}進(jìn)行交叉加以實(shí)現(xiàn)：

uij(t+1)=

(5)

其中，參數(shù)CR∈[0,1]是算法的交叉概率，rand(0，1)是0～1之間產(chǎn)生的隨機(jī)數(shù)，rand(1，n)是1～n之間產(chǎn)生的隨機(jī)正整數(shù)，j=1，2，…，d。通過(guò)該操作可以保證uij(t+1)中至少有一個(gè)分量來(lái)自vi(t)。

(3)選擇策略。利用公式(6)通過(guò)適應(yīng)度函數(shù)判斷個(gè)體uij(t+1)是否優(yōu)于xi(t)，以產(chǎn)生新一代個(gè)體xi(t+1)：

(6)

針對(duì)FPA算法易陷入局部極值、進(jìn)化后期收斂慢等不足，提出了DEFPA算法，即把差分進(jìn)化策略融入到FPA算法中，改進(jìn)算法對(duì)每代花朵個(gè)體進(jìn)行變異、交叉與選擇操作，因而在很大程度上提高了算法的尋優(yōu)性能。

改進(jìn)算法實(shí)現(xiàn)過(guò)程如下：

Step1：對(duì)種群數(shù)sizepop、最大進(jìn)化次數(shù)tmax、問(wèn)題維數(shù)D、DE算法中的交叉概率CR等參數(shù)進(jìn)行初始化。

Step2：計(jì)算當(dāng)前種群的適應(yīng)度值，記錄全局最優(yōu)值(適應(yīng)度最好值)及其對(duì)應(yīng)的最優(yōu)解。

Step3：算法進(jìn)入主循環(huán)體，若判斷條件p>rand成立，則利用公式(1)對(duì)個(gè)體位置進(jìn)行更新，并對(duì)其進(jìn)行越界處置，否則轉(zhuǎn)Step4。

Step4：倘若判斷條件p

Step5：利用公式(4)～(6)對(duì)花朵個(gè)體進(jìn)行差分優(yōu)化。

Step6：計(jì)算種群的最優(yōu)適應(yīng)度值及對(duì)應(yīng)的最優(yōu)解，若其較全局最優(yōu)值更優(yōu)，則更新全局最優(yōu)解與全局最優(yōu)值。

Step7：判斷結(jié)束條件，若滿足結(jié)束條件，退出程序并輸出最優(yōu)值及最優(yōu)解，否則，轉(zhuǎn)Step3。

2.2 環(huán)境建模

在二維空間建立移動(dòng)機(jī)器人路徑規(guī)劃的幾何模型，不考慮機(jī)器人與障礙物高度，同時(shí)將移動(dòng)機(jī)器人看作一個(gè)質(zhì)點(diǎn)，不考慮其大小及形狀。移動(dòng)機(jī)器人路徑規(guī)劃是指在一個(gè)已知障礙物的環(huán)境中[19]，機(jī)器人尋找一條從出發(fā)點(diǎn)S到終點(diǎn)T過(guò)程中與障礙物無(wú)碰撞且最短的路徑。機(jī)器人路徑規(guī)劃見(jiàn)圖1，在該圖的二維坐標(biāo)中，中間實(shí)心填充的區(qū)塊表示障礙物，左下角的實(shí)心小方塊表示機(jī)器人起始點(diǎn)S，右上角的實(shí)心五角星表示機(jī)器人目標(biāo)點(diǎn)T 。為了方便求解路徑規(guī)劃，環(huán)境中采用極坐標(biāo)與直角坐標(biāo)相結(jié)合的方法對(duì)移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題進(jìn)行求解。

圖1 移動(dòng)機(jī)器人路徑規(guī)劃

2.3 適應(yīng)度函數(shù)建立

適應(yīng)度函數(shù)是對(duì)移動(dòng)機(jī)器人路徑規(guī)劃優(yōu)劣程度的評(píng)估，適應(yīng)度函數(shù)的好壞直接影響著算法能否找到最優(yōu)路徑。在移動(dòng)機(jī)器人路徑規(guī)劃中，適應(yīng)度函數(shù)主要需要考慮路徑長(zhǎng)度性能指標(biāo)，其次還需考慮路徑安全性及光滑度等。因花授粉優(yōu)化算法多用于解決連續(xù)的優(yōu)化問(wèn)題，為此本文通過(guò)坐標(biāo)變換思想，采用直角坐標(biāo)與極坐標(biāo)相結(jié)合的方法求解移動(dòng)機(jī)器人路徑規(guī)劃。

本文建立適應(yīng)度函數(shù)如下：

fitness(path)=b1L1+b2L2

(7)

(8)

(9)

其中，b1、b2為加權(quán)函數(shù)，L1表示路徑長(zhǎng)度，xi、yi表示路徑初始點(diǎn)與終點(diǎn)，L2表示極坐標(biāo)路徑長(zhǎng)度，ρi為極坐標(biāo)長(zhǎng)度，α代表花朵個(gè)體角度。

2.4 實(shí)現(xiàn)步驟

利用DEFPA算法對(duì)移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題進(jìn)行求解，具體實(shí)現(xiàn)過(guò)程如下:

Step1：運(yùn)用柵格法構(gòu)建機(jī)器人實(shí)際工作環(huán)境[20]。

Step2：對(duì)DEFPA算法的種群數(shù)n等參數(shù)進(jìn)行初始化。

Step3：隨機(jī)初始化種群個(gè)體的初始位置,并利用2.3節(jié)的適應(yīng)度函數(shù)計(jì)算當(dāng)前種群個(gè)體的適應(yīng)度值。

Step4：進(jìn)入算法的主循環(huán)體，如果轉(zhuǎn)換概率p>rand條件成立，則進(jìn)行全局搜索，并對(duì)個(gè)體位置進(jìn)行越界處置，否則轉(zhuǎn)Step5。

Step5：進(jìn)行局部搜索，并對(duì)個(gè)體位置進(jìn)行越界處置。

Step6：采用差分思想(公式(4)～(6))對(duì)種群個(gè)體作進(jìn)一步優(yōu)化。

Step7：計(jì)算種群的最優(yōu)適應(yīng)度值及對(duì)應(yīng)的最優(yōu)解，若較全局最優(yōu)值更優(yōu)，則更新全局最優(yōu)解與全局最優(yōu)值。

Step8：判斷結(jié)束條件，若滿足，退出程序并輸出最優(yōu)路徑，否則，轉(zhuǎn)Step4。

3 仿真實(shí)驗(yàn)與分析

為了驗(yàn)證改進(jìn)花授粉算法在移動(dòng)機(jī)器人全局路徑規(guī)劃中的應(yīng)用，本文利用Matlab2014a環(huán)境對(duì)其進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yàn)空間大小設(shè)置為300m×300m，開始點(diǎn)坐標(biāo)設(shè)置為(0，0) ，目標(biāo)點(diǎn)坐標(biāo)設(shè)置為(300，300) ，實(shí)驗(yàn)空間中的黑色區(qū)塊表示障礙物。為了能更好地改進(jìn)花授粉算法在移動(dòng)機(jī)器人路徑規(guī)劃中的全局優(yōu)化能力，仿真實(shí)驗(yàn)中除將改進(jìn)的花授粉優(yōu)化算法與基本花授粉優(yōu)化算法進(jìn)行比較外，還與傳統(tǒng)粒子群算法的移動(dòng)機(jī)器人全局路徑規(guī)劃進(jìn)行了比較，實(shí)驗(yàn)結(jié)果如圖2-圖4所示。

圖2 利用FPA算法求解獲得的路徑

圖3 采用DEFPA算法求解獲得的路徑

圖4 運(yùn)用PSO算法求解獲得的路徑

從圖中可以看出，DEFPA算法得到的路徑較FPA算法與PSO算法得到的路徑更加光滑，轉(zhuǎn)折點(diǎn)也更少，尤其到了算法后期，路徑平滑度更要優(yōu)于FPA算法與PSO算法。因此，DEFPA算法在求解移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題中具有更優(yōu)的性能。

表1為FPA算法、DEFPA算法與PSO算法在仿真實(shí)驗(yàn)中得到的路徑長(zhǎng)度與運(yùn)行時(shí)間。從表中可以看出，改進(jìn)花授粉算法得到的從起始點(diǎn)到目標(biāo)點(diǎn)的路徑長(zhǎng)度最短，比FPA算法減少了3.127 2m，比PSO算法減少了5.133 3m。改進(jìn)的花授粉算法由于增加了差分策略計(jì)算，其尋找全局優(yōu)化路徑花費(fèi)的時(shí)間雖然比FPA算法多，但相差不太大，與FPA算法相比仍屬于同一時(shí)間復(fù)雜度級(jí)別，且比PSO算法尋找全局優(yōu)化路徑花費(fèi)的時(shí)間少。

表1 3種算法的路徑性能比較

4 結(jié)語(yǔ)

本文首先針對(duì)基本的花授粉算法存在收斂精度不高等不足，提出將差分進(jìn)化思想引入花授粉算法中，以提高花授粉算法的優(yōu)化能力，然后利用改進(jìn)算法對(duì)機(jī)器人路徑規(guī)劃問(wèn)題進(jìn)行求解，并取得了較好的實(shí)驗(yàn)效果。與對(duì)比算法FPA與PSO相比，本文提出的算法具有一定優(yōu)勢(shì)，驗(yàn)證了新算法的有效性。雖然FPA算法具有較強(qiáng)的優(yōu)化能力，并得到了廣泛應(yīng)用，但其具備良好性能的原因尚未得到理論證明。因此，如何利用數(shù)學(xué)工具與方法對(duì)算法的收斂率、魯棒性等進(jìn)行驗(yàn)證，是下一步需要研究的方向，以便為今后的算法改進(jìn)提供理論支撐。同時(shí)，本文利用改進(jìn)的FPA算法僅對(duì)靜態(tài)環(huán)境下的機(jī)器人路徑規(guī)劃問(wèn)題進(jìn)行了求解，但在實(shí)際工程中，動(dòng)態(tài)環(huán)境下的機(jī)器人路徑規(guī)劃問(wèn)題居多，如何利用改進(jìn)的FPA算法求解此類問(wèn)題，也是今后重要的研究課題。