基于改進花授粉算法的移動機器人路徑規(guī)劃研究

肖輝輝，段艷明

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

0 引言

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

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

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

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

準則1：生物異花授粉是指鳥、蜜蜂等傳播者攜帶其花粉通過Lévy進行的全局授粉過程。

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

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

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

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

(1)

(2)

其中λ=3/2，Γ(λ)是標準的伽馬函數(shù)。

花朵個體通過公式(2)進行局部搜索：

(3)

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

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

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

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

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

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

(4)

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

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

uij(t+1)=

(5)

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

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

(6)

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

改進算法實現(xiàn)過程如下：

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

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

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

Step4：倘若判斷條件p

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

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

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

2.2 環(huán)境建模

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

圖1 移動機器人路徑規(guī)劃

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

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

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

fitness(path)=b1L1+b2L2

(7)

(8)

(9)

其中，b1、b2為加權函數(shù)，L1表示路徑長度，xi、yi表示路徑初始點與終點，L2表示極坐標路徑長度，ρi為極坐標長度，α代表花朵個體角度。

2.4 實現(xiàn)步驟

利用DEFPA算法對移動機器人路徑規(guī)劃問題進行求解，具體實現(xiàn)過程如下:

Step1：運用柵格法構建機器人實際工作環(huán)境[20]。

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

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

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

Step5：進行局部搜索，并對個體位置進行越界處置。

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

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

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

3 仿真實驗與分析

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

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

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

圖4 運用PSO算法求解獲得的路徑

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

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

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

4 結語

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