精英協(xié)作引導(dǎo)花授粉算法及機(jī)器人導(dǎo)航路徑規(guī)劃

朱旭東

（無錫工藝職業(yè)技術(shù)學(xué)院，江蘇 宜興214200）

1 引言

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

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

這里研究了花授粉算法的改進(jìn)問題，通過在花授粉算法中添加對立點(diǎn)初始化策略、精英協(xié)作引導(dǎo)策略和動態(tài)轉(zhuǎn)換概率策略等，達(dá)到提高算法尋優(yōu)精度和穩(wěn)定性的目的。并將此算法應(yīng)用于機(jī)器人路徑規(guī)劃，達(dá)到了提高路徑質(zhì)量和規(guī)劃穩(wěn)定性的目的。

2 花授粉算法

2.1 花授粉算法的仿生學(xué)原理分析

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

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

2.2 花授粉算法簡介

花授粉算法核心思想為：設(shè)置一個(gè)轉(zhuǎn)換概率p和隨機(jī)數(shù)rand∈(0,1)，當(dāng)rand＜p則進(jìn)行全局搜索，若rand≥p則進(jìn)行局部搜索。算法實(shí)現(xiàn)主要包括初始化、全局搜索與局部搜索機(jī)制、花粉選擇等關(guān)鍵步驟。

（1）花粉位置初始化。花粉位置使用隨機(jī)方式進(jìn)行初始化，為：

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

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

式中：λ=1.5，Γ(λ)-標(biāo)準(zhǔn)gamma函數(shù)；s-利用Mantegna算法產(chǎn)生的步長，即：

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

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

（4）適者生存。花粉每更新一步，則判斷更新前后位置優(yōu)劣，并根據(jù)適者生存原則進(jìn)行選擇［9］。記f()為目標(biāo)函數(shù)，目標(biāo)函數(shù)越小則花粉位置越優(yōu)。當(dāng)時(shí)進(jìn)行位置更新，否則不進(jìn)行位置更新。花粉位置更新后進(jìn)行全局最優(yōu)判斷，若則更新全局最優(yōu)，否則不更新。

（5）算法結(jié)束條件。當(dāng)所有花粉完成一次迭代時(shí)才進(jìn)入下一輪迭代，當(dāng)?shù)螖?shù)達(dá)到最大迭代次數(shù)Tmax時(shí)算法停止，輸出全局最優(yōu)即為花粉最優(yōu)位置。

3 精英協(xié)作引導(dǎo)花授粉算法

3.1 算法缺陷分析

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

3.2 改進(jìn)策略

（1）對立點(diǎn)初始化方法。

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

圖1 對稱點(diǎn)示意圖Fig.1 Opposing Point Sketch

經(jīng)分析可知，取值范圍內(nèi)的任意一點(diǎn)其對稱點(diǎn)是唯一存在的，計(jì)算方法為：

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

（2）精英協(xié)作引導(dǎo)方法。

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

圖2 精英協(xié)作方式Fig.2 Elite Collaboration Manner

為了體現(xiàn)不同精英花粉在協(xié)作與協(xié)商過程中的話語權(quán)，依據(jù)花粉的目標(biāo)函數(shù)值為其賦不同的權(quán)值。以目標(biāo)函數(shù)f()越小越優(yōu)為例，精英花粉權(quán)值賦值方法為：

式中：wgb1、wgb2、wgb3-不同精英的權(quán)值。則精英的協(xié)作位置為：

式中：Xlead-精英花粉協(xié)作位置，使用Xlead代替式（2）中的全局最優(yōu)就實(shí)現(xiàn)了精英協(xié)作策略對全局搜索的引導(dǎo)。

（3）動態(tài)自適應(yīng)轉(zhuǎn)換概率。

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

式中：pdy-動態(tài)轉(zhuǎn)換概率；pmax、pmin-最大最小轉(zhuǎn)換概率；tmax-最大迭代次數(shù)；t-當(dāng)前迭代次數(shù)。

3.3 精英協(xié)作引導(dǎo)花授粉算法流程

以傳統(tǒng)花授粉算法流程為基礎(chǔ)，將對立點(diǎn)初始化方法、精英協(xié)作引導(dǎo)策略、動態(tài)轉(zhuǎn)換概率融入其中，得到精英協(xié)作引導(dǎo)花授粉算法流程如下：

Step1：初始化算法參數(shù)，包括種群規(guī)模N，算法最大迭代次數(shù)tmax，最大最小轉(zhuǎn)換概率pmax、pmin；

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

Step3：對轉(zhuǎn)化概率進(jìn)行動態(tài)更新，當(dāng)rand＜pdy時(shí)執(zhí)行精英協(xié)作的全局搜索策略，當(dāng)rand≥pdy時(shí)執(zhí)行局部搜索策略；

Step4：計(jì)算花粉位置更新前后的目標(biāo)函數(shù)值，依據(jù)適者生存的原則選擇目標(biāo)函數(shù)值小的花粉進(jìn)入下一輪迭代；

Step5：判斷是否達(dá)到最大迭代次數(shù)，若否則轉(zhuǎn)至Step3；若是則輸出全局最優(yōu)位置，算法結(jié)束。

4 改進(jìn)花授粉算法性能測試

4.1 測試環(huán)境及測試函數(shù)

使用Matlab（R2010b）軟件對算法性能進(jìn)行測試，使用的測試函數(shù)從非固定維數(shù)單模態(tài)標(biāo)準(zhǔn)函數(shù)和非固定維數(shù)多模態(tài)標(biāo)準(zhǔn)函數(shù)中隨機(jī)選取，如表1所示。

表1 測試函數(shù)Tab.1 Testing Function

4.2 測試結(jié)果分析

為了驗(yàn)證三種改進(jìn)措施之間的關(guān)聯(lián)性和耦合性，記傳統(tǒng)花授粉算法為FPA，融入對立點(diǎn)初始化的花授粉算法記為IFPA1，融入精英協(xié)作引導(dǎo)策略的花授粉算法記為IFPA2，融入動態(tài)自適應(yīng)轉(zhuǎn)換概率的花授粉算法記為IPFA3，融入全部改進(jìn)策略的花授粉算法記為IPFA。

為了保證公平公正，算法共有的參數(shù)設(shè)置為相同值，種群規(guī)模N=30，最大迭代次數(shù)tamx=500，固定轉(zhuǎn)換概率p=0.8，轉(zhuǎn)換概率最大值最小值分別為pmax=0.9、pmin=0.7。測試函數(shù)維度統(tǒng)一設(shè)置為50。為了防止偶然性因素影響，每種算法各自獨(dú)立運(yùn)行10次，統(tǒng)計(jì)每次最優(yōu)結(jié)果的平均值和標(biāo)準(zhǔn)差，如表2所示。

表2 測試結(jié)果Tab.2 Testing Result

分析表2中的測試數(shù)據(jù)可以得出以下結(jié)論：（1）融合任意一個(gè)改進(jìn)措施的花授粉算法尋優(yōu)精度和尋優(yōu)穩(wěn)定性都優(yōu)于傳統(tǒng)算法，說明三項(xiàng)改進(jìn)措施都是有效且必要的；（2）融合三項(xiàng)改進(jìn)措施的精英協(xié)作花授粉算法具有最佳的尋優(yōu)精度和尋優(yōu)穩(wěn)定性，說明三向改進(jìn)措施之間沒有發(fā)生有害性耦合與關(guān)聯(lián)。綜上所述，精英協(xié)作引導(dǎo)花授粉算法具有最佳的尋優(yōu)精度和尋優(yōu)穩(wěn)定性。

5 機(jī)器人路徑規(guī)劃應(yīng)用

5.1 機(jī)器人路徑規(guī)劃建模

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

圖3 路徑規(guī)劃思路Fig.3 Path Planning Thought

這里的路徑規(guī)劃目標(biāo)為：在避障的前提下規(guī)劃出全局最短路徑［10］，根據(jù)這一規(guī)劃目標(biāo)，目標(biāo)函數(shù)構(gòu)造為：

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

為了方便進(jìn)行碰撞判斷，將所有障礙物膨脹為圓形，碰撞標(biāo)志變量P計(jì)算方法為：

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

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

根據(jù)以上機(jī)器人路徑規(guī)劃模型，花粉位置使用十進(jìn)制編碼方式，花粉維度設(shè)置為D-1維，編碼方法為

5.2 機(jī)器人路徑規(guī)劃性能驗(yàn)證

如圖4所示環(huán)境為機(jī)器人工作環(huán)境，圖中藍(lán)色圓圈為障礙物區(qū)域。同時(shí)使用傳統(tǒng)花授粉算法與精英協(xié)商引導(dǎo)花授粉算法進(jìn)行路徑規(guī)劃，算法的參數(shù)設(shè)置與4.2節(jié)一致，每種算法各自獨(dú)立規(guī)劃10次，統(tǒng)計(jì)10次最優(yōu)路徑長度，結(jié)果如圖5、表3所示。

圖4 機(jī)器人工作環(huán)境Fig.4 Robot Working Environment

表3 路徑規(guī)劃統(tǒng)計(jì)值Tab.3 Path Planning Statistics

圖5 路徑規(guī)劃結(jié)果Fig.5 Path Planning Result

由圖5和表3可以明顯看出，精英協(xié)作引導(dǎo)花授粉算法規(guī)劃路徑均值比傳統(tǒng)算法減少了4.01%，標(biāo)準(zhǔn)差減少了一個(gè)數(shù)量級以上。說明精英協(xié)作引導(dǎo)花授粉算法的路徑規(guī)劃穩(wěn)定性遠(yuǎn)遠(yuǎn)優(yōu)于傳統(tǒng)花授粉算法，規(guī)劃的路徑質(zhì)量也優(yōu)于傳統(tǒng)算法。這意味著，精英協(xié)作引導(dǎo)花授粉算法不僅尋優(yōu)精度極佳，而且穩(wěn)定性很好，每次都能夠搜索到極佳路徑。這是因?yàn)閷αⅫc(diǎn)初始化方法提高了初始種群質(zhì)量，精英協(xié)作引導(dǎo)全局搜索的方式提高了算法搜索效率和質(zhì)量，動態(tài)轉(zhuǎn)換概率策略有效平衡了全局搜索與局部搜索，使算法尋優(yōu)精度和穩(wěn)定性明顯優(yōu)于傳統(tǒng)算法。精英協(xié)作引導(dǎo)花授粉算法與傳統(tǒng)算法規(guī)劃的最優(yōu)路徑，如圖6所示。

圖6 兩種算法的規(guī)劃結(jié)果Fig.6 Path Planning Result by the Two Algorithms

從圖6中可以看出，兩種算法規(guī)劃的路徑均安全且平滑，能夠滿足機(jī)器人行駛的動力學(xué)要求。結(jié)合圖5與表3，精英協(xié)作引導(dǎo)花授粉算法在機(jī)器人路徑規(guī)劃中尋優(yōu)精度高且穩(wěn)定性極好。

6 結(jié)論

這里研究了花授粉算法的改進(jìn)問題，給出了對立點(diǎn)初始化、精英協(xié)作引導(dǎo)全局搜索、動態(tài)轉(zhuǎn)換概率等改進(jìn)策略，從而提出了精英協(xié)作引導(dǎo)花授粉算法，經(jīng)測試得出了以下結(jié)論：（1）每種改進(jìn)策略都能夠提高算法性能，且彼此間不存在抵消性耦合；（2）精英協(xié)作引導(dǎo)花授粉算法在機(jī)器人路徑規(guī)劃中尋優(yōu)精度高、穩(wěn)定性能好。