移動機器人路徑規(guī)劃中的改進花授粉算法應(yīng)用

王志俊

（山西建筑職業(yè)技術(shù)學(xué)院 山西省太原市 030006）

人工智能、語言交互、機器學(xué)習(xí)這些飛速發(fā)展的技術(shù)，使得全世界的服務(wù)機器人產(chǎn)業(yè)飛快發(fā)展。由于市場規(guī)模的開啟和行業(yè)空間的增大，越來越多的企業(yè)走進服務(wù)機器人的市場。移動機器人是人工智能背景下的產(chǎn)物，是為了適應(yīng)智能化社會而應(yīng)運而生的產(chǎn)物。移動機器人局部路徑及全局路徑規(guī)劃研究成為目前機器人研究的熱點，前者主要利用的是傳感器信息，后者則是基于環(huán)境模型[1]。作為一種新型群智能優(yōu)化算法，花授粉優(yōu)化算法強調(diào)提升花授粉全局優(yōu)化能力，其通過采用動態(tài)轉(zhuǎn)換概率方法，促進了收斂速度及計算精度的提升。以往學(xué)者在研究中采用改進花授粉算法優(yōu)化SVM 參數(shù)，建立了交通流量預(yù)測模型，證實了花授粉優(yōu)化算法對FPA 收斂能力的提升[2]?；诨ㄊ诜蹆?yōu)化算法角度下的移動機器人路徑規(guī)劃研究尚未見報道。本文將差分化進化策略融入改進花授粉算法，對其在移動機器人路徑規(guī)劃中的作用進行探討，實踐證明其能夠獲得良好的優(yōu)化性能。

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

英國劍橋大學(xué)學(xué)者是花授粉算法最早提出者，其構(gòu)成機制包括萊維飛行及偏好隨機游動、貪婪演化，能夠完成算法勘探與開發(fā)的有機轉(zhuǎn)換[3]，在轉(zhuǎn)換概率參數(shù)P 作用下實現(xiàn)動態(tài)控制，能夠為全局搜索及局部搜索相關(guān)問題的解決提供可靠的依據(jù)。另外花授粉算法提出了清晰的思路，不僅執(zhí)行起來簡單，而且具有極強的全局收斂功能，是人工智能移動機器人研究的重點。該算法靈感來源于自然界顯花植物花朵傳粉，通過對流程的模擬，做出假設(shè)，假如只開一朵花，且僅擁有一個花粉配子，且優(yōu)化問題對應(yīng)每個花粉配子需要一個解，那么需要符合以下準(zhǔn)則：

（1）鳥、蜜蜂對花粉是傳播作用，其攜帶的花粉在Levy 作用下完成全局授粉，這一過程屬于生物異花授粉；

（2）利用自身局部授粉實現(xiàn)屬于非生物自花授粉；

（3）在評估繁衍概率時主要利用的是花的常性指標(biāo)，該值能夠反映出兩朵花的相似性，具有比例關(guān)系[4]；

（4）全局及局部授粉會受到轉(zhuǎn)換概率的影響，而花朵在自然環(huán)境中生存難免會受到其周圍環(huán)境諸如地理位置、風(fēng)等的影響，從這個角度看授粉近似于自花授粉。

作為一個個體演化過程，全局及局部搜索花授粉算法都可以采用公式能夠?qū)崿F(xiàn)算法探測，開采部分主要通過公式實現(xiàn)。其中xit+1表示的是算法進化t+1代的值，表示第t 代的值，全局最優(yōu)解用g 表示，控制步長縮放因子采用γ 表示，花朵個體萊維飛行為宜采用L（λ）表示。0 與1范圍間正態(tài)分布采用隨機數(shù)ε 表示。另外同一種植物，若花朵種類不同，其花粉也具有一定的不同，分別表示為、。

2 移動機器人路徑規(guī)劃中的改進花授粉算法應(yīng)用

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

圖2：花授粉算法最優(yōu)路徑

圖3：改進花授粉算法路徑

圖4：粒子群算法路徑

傳統(tǒng)花授粉優(yōu)化算法具有一定的局限性，針對這一問題，在對花授粉算法進行改進時首先需要結(jié)合機器人工作環(huán)境建立一個模型，然后制定可行性的路徑優(yōu)化目標(biāo)，并打造適應(yīng)度函數(shù)，最后優(yōu)化移動機器人路徑。

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

作為一種進化算法，差分進化算法主要指的是在演化期間采用種群的方式優(yōu)化個體間差異性的過程。通常，進化中種群個體會產(chǎn)生一定的矢量差，利用該矢量差對其進行組合能夠得到中間種群個體[5]。比較父代與中間個體進而獲得后代種群?；诓罘诌M化算法變異性特征，其探索能力往往在進化初期能夠達到最早。隨著演化過程的推進，會降低種群個體差異，與此同時伴隨差分進化算法開采能力提高。本研究將差分進化算法在演化期間的實現(xiàn)策略分為三個方面，具體如下：

（2）交叉操作。為提升種群個體差異性，可以采用交叉操作，其首先需要對第t 代進化種群及經(jīng)過變異的種群進行交叉獲得，公式為：

算法交叉概率參數(shù)CR 范圍為[0,1]，rand 是0～1 之間選擇的隨中至少存在一個分量來源于vi(t)。

表1：不同算法路徑性能比較

（3）選擇策略。在適應(yīng)度函數(shù)作用下對個體vi(t+1)做出判斷，觀察期與xi（t）的差異，使得順利產(chǎn)生新的個體xi（t+1）。

進入進化后期后，花授粉算法收斂速度會呈現(xiàn)出降低趨勢，且局部極值問題也得以暴露，針對這一問題，需要對傳統(tǒng)花授粉算法予以改進，并在此基礎(chǔ)上引入差分進化策略，使得每朵花完成個體變異及交叉，促進了算法尋優(yōu)性能的提升。其實現(xiàn)過程如下：

（1）完成種群數(shù)sizepop、問題維數(shù)D 等各項參數(shù)的初始化，對種群適應(yīng)度值進行計算，獲得全局最優(yōu)值后計算最優(yōu)解。

（2）進入主循環(huán)體后，更新個體位置，當(dāng)p>rand，需要及時處置越界問題[6]；若P

（3）差分優(yōu)化花朵個體，首先需要計算種群最優(yōu)適應(yīng)度值，若該值與全局最優(yōu)值相比更好，要更新最優(yōu)解及最優(yōu)值。

（4）若滿足結(jié)束條件，那么將程序退出，并按照流程輸出最優(yōu)值及最優(yōu)解[7]。

2.2 環(huán)境建模

首先建立一個二維空間，通過全面分析及影響控制避免機器人障礙物高度、大小等對結(jié)果的影響，在此基礎(chǔ)上實施移動機器人路徑規(guī)劃?？梢詫⑵渥鳛橐粋€質(zhì)點，將其路徑規(guī)劃置于一個已知障礙物環(huán)境，自出發(fā)點S 到終點T 全程尋找不會與障礙物接觸且距離最短的路徑，如圖1所示，不同形狀填充黑塊為障礙物，S 點表示的是起始位置，五角星標(biāo)識位置為目標(biāo)點[8]。在路徑規(guī)劃中，為獲得最優(yōu)解，采用直角坐標(biāo)與極坐標(biāo)相結(jié)合的建模方法。

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

適應(yīng)度函數(shù)主要用于對移動機器人路徑規(guī)劃優(yōu)劣的評估，其會影響到最優(yōu)路徑的實施與實現(xiàn)。路徑長度性能指標(biāo)是路徑規(guī)劃的首要考慮因素，需要在確保路徑安全的前提下，確保光滑[9]。通常連續(xù)優(yōu)化問題多采用的是花授粉優(yōu)化算法。針對這一研究結(jié)論，在構(gòu)建最優(yōu)路徑時，采用了坐標(biāo)變換思想，極坐標(biāo)結(jié)合直角坐標(biāo)系條件下對機器人路徑進行規(guī)劃，適應(yīng)度函數(shù)如公式所示：機數(shù)，j 表示1,2，……，d，其能夠確保

其中加權(quán)函數(shù)包括b1、b2，路徑長度采用L1 表示，路徑初始點及終點分別采用xi、yi表示，a 表示的是花朵個體角度。

2.4 實現(xiàn)步驟

基于改進的花授粉算法在移動機器人路徑規(guī)劃問題求解中的應(yīng)用主要通過以下幾個流程實現(xiàn)：

（1）采用柵格法營造一個真實的機器人工作環(huán)境，經(jīng)過初始化處理，完成種群數(shù)N 參數(shù)的優(yōu)化[10]。

（2）隨機選擇種群個體實施初始化處理，選擇適應(yīng)度函數(shù)通過計算獲得種群個體適應(yīng)度值。在主循環(huán)體緩解，當(dāng)轉(zhuǎn)換概率p 較rand 大時，需要實施全局搜索，并采用越界處置方法對個體位置進行處理。種群個體的深度優(yōu)化采用的是差分思想。

（3）對種群最優(yōu)適應(yīng)度值及最優(yōu)解進行計算，并對最優(yōu)值及最優(yōu)解進行更新[11～12]。

（4）滿足結(jié)束條件后，將程序退出，獲得最優(yōu)路徑。

3 仿真實驗及分析

研究構(gòu)建了一個Matlab2014a 環(huán)境，模擬了移動機器人全局路徑，在防真試驗過程中，建立一個300m×300m 的實驗空間，開始點與目標(biāo)點坐標(biāo)分別為（0,0），（300,300），黑色區(qū)塊代表的是障礙物。通過對比可以發(fā)現(xiàn)，與傳統(tǒng)花授粉優(yōu)化算法、粒子群算法相比，改進花授粉算法擁有更強的全局優(yōu)化能力，結(jié)果如圖2～圖4所示。

由上述可知，與花授粉算法及粒子群算法相比，改進花授粉算法獲得路徑最為光滑，不僅轉(zhuǎn)折點少，而且在算法后期，路徑平滑度好，提示移動機器人路徑規(guī)劃可以采用改進花授粉算法以獲得更加的性能。不同算法仿真試驗數(shù)據(jù)如表1所示，可以發(fā)現(xiàn)，改進花授粉算法起始到目標(biāo)位置路徑較另外兩種算法短，經(jīng)過差分策略的干預(yù)，其花費的時間較傳統(tǒng)花授粉算法略多，但整體差異較小，且在路徑長度方面優(yōu)勢更為明顯。

4 結(jié)束語

研究為獲得移動機器人最優(yōu)規(guī)劃路徑，將差分進化思想引入花授粉算法，經(jīng)過仿真實驗證實該算法性能佳，優(yōu)勢明顯。在后續(xù)研究中應(yīng)進一步探究該算法收斂率及魯棒性等問題，為算法改進提供參考。