精英協作引導花授粉算法及機器人導航路徑規劃

朱旭東

（無錫工藝職業技術學院，江蘇 宜興214200）

1 引言

花授粉算法模擬自然界中自花授粉和異花授粉而提出，具有參數少、原理簡單、尋優性能佳等諸多優點［1］。與其它啟發式算法一致，花授粉算法也存在探索（全局搜索）與開采（局部搜索）之間的矛盾與平衡問題，使算法的收斂與尋優能力存在矛盾。因此，對算法進行改進而尋找探索與開采之間的平衡，對提高算法的尋優性能具有明顯作用。

花授粉算法尋優性能的缺陷主要體現在兩個方面：一是算法運行過程中過慢的收斂速度；二是隨著算法迭代，較差的進化能力使算法過早停滯在局部最優。改進思路也從兩個方面入手：一是將花授粉算法與其他算法融合，實現優勢互補；二是改進算法的局部搜索和全局搜索過程，尋找兩者更加的平衡點。文獻［2］將和聲搜索算法融入到花授粉算法中，提高了算法的收斂速度，同時使用折射原理提高了算法的搜索精度；文獻［3］將模擬退火算法降溫操作融入到花授粉算法中，增加了種群多樣性，同時提高了算法的整體尋優性能；文獻［4］使用邏輯自映射函數對花粉進行混沌擾動，改善了花授粉算法缺乏變異機制的問題，解決了算法后期趨同問題；文獻［5］針對全局搜索過程引入全局平均最優花粉位置和動態權重遞減因子，牽引花粉朝正確方向搜索，同時使用Cauchy變異增加種群多樣性，提升了算法的尋優精度和速度。針對不同的問題，啟發式算法具有不同的改進方法和優化方式。另外，群智能算法的兩個平衡點研究難以解決，分別是收斂性與尋優精度的平衡研究、全局搜索與局部搜索的平衡研究。

這里研究了花授粉算法的改進問題，通過在花授粉算法中添加對立點初始化策略、精英協作引導策略和動態轉換概率策略等，達到提高算法尋優精度和穩定性的目的。并將此算法應用于機器人路徑規劃，達到了提高路徑質量和規劃穩定性的目的。

2 花授粉算法

2.1 花授粉算法的仿生學原理分析

花授粉算法是模擬自然界中的自花授粉和異花授粉現象而提出的。自花授粉的傳播距離較近，是一種局部搜索方式。異花授粉依賴蜜蜂、蝴蝶等昆蟲以Levy飛行的方式傳播，花粉的傳播距離較遠，是一種全局搜索方式［6］。

在算法中為了實現全局搜索和局部搜索的切換，設置了一個轉換概率p。轉換概率的設置至關重要，用于平衡與協調局部搜索和全局搜索。花粉位置改變前后的優劣程度使用適應度函數表征，并使用適者生存原則進行選擇。總的來講，花粉傳播現象與花授粉算法的對應關系如下：（1）通過對花粉進行合理編碼，將花粉位置與待搜索空間的點一一對應；（2）自花授粉對應局部搜索過程，異花授粉對應全局搜索過程；（3）花粉所處位置的優劣與待優化問題的適應度函數值一一對應；（4）花粉傳播前后的選擇使用適者生存原則進行選擇。

2.2 花授粉算法簡介

花授粉算法核心思想為：設置一個轉換概率p和隨機數rand∈(0,1)，當rand＜p則進行全局搜索，若rand≥p則進行局部搜索。算法實現主要包括初始化、全局搜索與局部搜索機制、花粉選擇等關鍵步驟。

（1）花粉位置初始化。花粉位置使用隨機方式進行初始化，為：

式中：Xi-花粉第i維位置；ri-［0，1］間隨機數花粉第i維位置的最小值和最大值。

（2）全局搜索。全局搜索模擬Levy飛行方式進行位置更新［7］，方法為：

式中：λ=1.5，Γ(λ)-標準gamma函數；s-利用Mantegna算法產生的步長，即：

式中：v～N(0,1)，μ～N(0,σ2)，方差σ2的計算方法為：

（3）局部搜索。局部搜索以異于自身的兩個花粉差分為牽引［8］，即

（4）適者生存。花粉每更新一步，則判斷更新前后位置優劣，并根據適者生存原則進行選擇［9］。記f()為目標函數，目標函數越小則花粉位置越優。當時進行位置更新，否則不進行位置更新。花粉位置更新后進行全局最優判斷，若則更新全局最優，否則不更新。

（5）算法結束條件。當所有花粉完成一次迭代時才進入下一輪迭代，當迭代次數達到最大迭代次數Tmax時算法停止，輸出全局最優即為花粉最優位置。

3 精英協作引導花授粉算法

3.1 算法缺陷分析

對花授粉算法原理及實現方式進行深入分析，可以看出算法的如下缺陷：（1）使用完全隨機的方式進行位置初始化，花粉可能在某區域較為集中，而不夠分散；（2）隨著算法的迭代，在全局最優g*的牽引作用下，花粉聚集在全局最優附近，使得g*-Xt i較小或約為0，此時式（2）給出的全局搜索方式幾乎沒有進化能力，使算法停滯在某一局部最優處；（3）轉換概率用于平衡與調節全局搜索和局部搜索，但是固定的轉換概率難以較好適應算法全過程。本節針對以上分析出的幾點缺陷提出改進方法，分別提出了對立點初始化方法、精英協作引導方法、動態自適應轉換概率等。

3.2 改進策略

（1）對立點初始化方法。

以花粉第i維為例，對立點定義方式，如圖1所示。

圖1 對稱點示意圖Fig.1 Opposing Point Sketch

經分析可知，取值范圍內的任意一點其對稱點是唯一存在的，計算方法為：

對立點初始化方法為：對于種群規模為N的初始化問題，首先使用隨機方式進行生成N個初始位置，而后計算每個花粉對立點，將原始位置與對立點位置共2N個進行適應度排序，選擇前N個個體作為種群初始位置。

（2）精英協作引導方法。

隨著算法的迭代，花粉聚集在全局最優g*附近，使得g*-按照全局搜索方式有，這意味著算法幾乎失去了進化能力，極易陷入當前最優。深入進行機理分析可知，單獨的種群最優進行引導過于單調，沒有充分發揮種群智慧。為了解決這一問題，這里選擇種群中適應度前三的花粉（即精英花粉），精英花粉進行協作組成新的花粉位置對全局搜索進行引導。精英協作如圖2所示。

圖2 精英協作方式Fig.2 Elite Collaboration Manner

為了體現不同精英花粉在協作與協商過程中的話語權，依據花粉的目標函數值為其賦不同的權值。以目標函數f()越小越優為例，精英花粉權值賦值方法為：

式中：wgb1、wgb2、wgb3-不同精英的權值。則精英的協作位置為：

式中：Xlead-精英花粉協作位置，使用Xlead代替式（2）中的全局最優就實現了精英協作策略對全局搜索的引導。

（3）動態自適應轉換概率。

前文中講到，轉換概率用于平衡全局搜索與局部搜索，對算法的尋優性能至關重要。算法初期，算法應更大概率進行全局搜索，在全局范圍內找到最優解鄰域；算法后期，算法應更加傾向于進行局部搜索，在小范圍內提高尋優精度，同時促進算法收斂。基于這一思考，這里使用動態自適應轉換概率代替固定轉換概率。方法為：

式中：pdy-動態轉換概率；pmax、pmin-最大最小轉換概率；tmax-最大迭代次數；t-當前迭代次數。

3.3 精英協作引導花授粉算法流程

以傳統花授粉算法流程為基礎，將對立點初始化方法、精英協作引導策略、動態轉換概率融入其中，得到精英協作引導花授粉算法流程如下：

Step1：初始化算法參數，包括種群規模N，算法最大迭代次數tmax，最大最小轉換概率pmax、pmin；

Step2：使用對立點初始化方法生成并選擇初始種群；

Step3：對轉化概率進行動態更新，當rand＜pdy時執行精英協作的全局搜索策略，當rand≥pdy時執行局部搜索策略；

Step4：計算花粉位置更新前后的目標函數值，依據適者生存的原則選擇目標函數值小的花粉進入下一輪迭代；

Step5：判斷是否達到最大迭代次數，若否則轉至Step3；若是則輸出全局最優位置，算法結束。

4 改進花授粉算法性能測試

4.1 測試環境及測試函數

使用Matlab（R2010b）軟件對算法性能進行測試，使用的測試函數從非固定維數單模態標準函數和非固定維數多模態標準函數中隨機選取，如表1所示。

表1 測試函數Tab.1 Testing Function

4.2 測試結果分析

為了驗證三種改進措施之間的關聯性和耦合性，記傳統花授粉算法為FPA，融入對立點初始化的花授粉算法記為IFPA1，融入精英協作引導策略的花授粉算法記為IFPA2，融入動態自適應轉換概率的花授粉算法記為IPFA3，融入全部改進策略的花授粉算法記為IPFA。

為了保證公平公正，算法共有的參數設置為相同值，種群規模N=30，最大迭代次數tamx=500，固定轉換概率p=0.8，轉換概率最大值最小值分別為pmax=0.9、pmin=0.7。測試函數維度統一設置為50。為了防止偶然性因素影響，每種算法各自獨立運行10次，統計每次最優結果的平均值和標準差，如表2所示。

表2 測試結果Tab.2 Testing Result

分析表2中的測試數據可以得出以下結論：（1）融合任意一個改進措施的花授粉算法尋優精度和尋優穩定性都優于傳統算法，說明三項改進措施都是有效且必要的；（2）融合三項改進措施的精英協作花授粉算法具有最佳的尋優精度和尋優穩定性，說明三向改進措施之間沒有發生有害性耦合與關聯。綜上所述，精英協作引導花授粉算法具有最佳的尋優精度和尋優穩定性。

5 機器人路徑規劃應用

5.1 機器人路徑規劃建模

機器人路徑規劃思路如圖3所示，在原坐標系XOY中確定出機器人起始點和目標點，而后將起點至終點使用直線連接，連接線與X軸夾角記為θ。以起點至終點接線為X’軸建立新坐標系X’SY’，在起點S與終點T之間使用D-1條平行線將線段ST等分為D段。那么，只要規劃出每條平行線Li的縱坐標值，將其進行平滑連接就得到了機器人路徑。經過以上分析過程，這里將路徑規劃問題轉化為平行線上Li的縱坐標規劃問題。

圖3 路徑規劃思路Fig.3 Path Planning Thought

這里的路徑規劃目標為：在避障的前提下規劃出全局最短路徑［10］，根據這一規劃目標，目標函數構造為：

式中：Leng-路徑長度；P-機器人碰撞標志變量；β-足夠大的系數，用于排除發生碰撞的路徑，在此取β=100。路徑長度Leng為：

為了方便進行碰撞判斷，將所有障礙物膨脹為圓形，碰撞標志變量P計算方法為：

式中：(xobsk,yobsk)-第k個障礙物圓心；(xi,yi)-插值點坐標；dk-插值點與第k個障礙物的距離最小值；robsk-第k個障礙物的半徑；θk-軌跡與第k個障礙物的碰撞標志值；nobs-所有障礙物數量。

分析式（12）可知，當存在某一插入點與障礙物中心距離小于障礙物半徑時，此時機器人與障礙物發生碰撞，同時θk＞0，則P＞0，結合式（10）在系數β的放大作用下，有z=L(1+βP)?L，此時z值較大，不會成為最優路徑。當所有插入點與障礙物不發生碰撞時，θk=0，P=0，1+βP=1，此時z=L，長度最短的無碰路徑即為最優路徑。

根據以上機器人路徑規劃模型，花粉位置使用十進制編碼方式，花粉維度設置為D-1維，編碼方法為

5.2 機器人路徑規劃性能驗證

如圖4所示環境為機器人工作環境，圖中藍色圓圈為障礙物區域。同時使用傳統花授粉算法與精英協商引導花授粉算法進行路徑規劃，算法的參數設置與4.2節一致，每種算法各自獨立規劃10次，統計10次最優路徑長度，結果如圖5、表3所示。

圖4 機器人工作環境Fig.4 Robot Working Environment

表3 路徑規劃統計值Tab.3 Path Planning Statistics

圖5 路徑規劃結果Fig.5 Path Planning Result

由圖5和表3可以明顯看出，精英協作引導花授粉算法規劃路徑均值比傳統算法減少了4.01%，標準差減少了一個數量級以上。說明精英協作引導花授粉算法的路徑規劃穩定性遠遠優于傳統花授粉算法，規劃的路徑質量也優于傳統算法。這意味著，精英協作引導花授粉算法不僅尋優精度極佳，而且穩定性很好，每次都能夠搜索到極佳路徑。這是因為對立點初始化方法提高了初始種群質量，精英協作引導全局搜索的方式提高了算法搜索效率和質量，動態轉換概率策略有效平衡了全局搜索與局部搜索，使算法尋優精度和穩定性明顯優于傳統算法。精英協作引導花授粉算法與傳統算法規劃的最優路徑，如圖6所示。

圖6 兩種算法的規劃結果Fig.6 Path Planning Result by the Two Algorithms

從圖6中可以看出，兩種算法規劃的路徑均安全且平滑，能夠滿足機器人行駛的動力學要求。結合圖5與表3，精英協作引導花授粉算法在機器人路徑規劃中尋優精度高且穩定性極好。

6 結論

這里研究了花授粉算法的改進問題，給出了對立點初始化、精英協作引導全局搜索、動態轉換概率等改進策略，從而提出了精英協作引導花授粉算法，經測試得出了以下結論：（1）每種改進策略都能夠提高算法性能，且彼此間不存在抵消性耦合；（2）精英協作引導花授粉算法在機器人路徑規劃中尋優精度高、穩定性能好。