蜂群優(yōu)化算法的機器人路徑規(guī)劃

張占義，朱金達

(1.河北交通職業(yè)技術(shù)學院 運輸管理系， 石家莊 050035； 2.河北科技大學 機械工程學院， 石家莊 050018)

adaptive

通過建立諸如軌跡長度最短、運動時間最少的優(yōu)化目標，找到復(fù)雜環(huán)境中起點和終點之間的最優(yōu)路徑，實現(xiàn)移動機器人的路徑規(guī)劃，是機器人自主導航的關(guān)鍵問題之一[1-3]。目前，以人工勢場法、視圖法、單元分解法為代表的傳統(tǒng)方法，在解決路徑規(guī)劃中存在執(zhí)行效率低和易陷入局部最優(yōu)的問題。因此，近年來以遺傳算法、粒子群算法、蟻群算法、人工蜂群算法為代表的啟發(fā)式智能優(yōu)化算法得到了越來越多學者的關(guān)注。

文獻[4]將人工神經(jīng)網(wǎng)絡(luò)、模糊神經(jīng)網(wǎng)絡(luò)引入機器人的路徑規(guī)劃中，借助神經(jīng)網(wǎng)絡(luò)的并行計算和出色的學習能力，提高了路徑規(guī)劃的效率和精度。文獻[5]采用蟻群算法對機器人進行路徑規(guī)劃，取得了較好的效果。文獻[6]對粒子群算法進行了改進，并將改進后的算法用于機器人的路徑規(guī)劃。此外，飛蛾優(yōu)化算法、人工蜂群算法等在機器人路徑規(guī)劃中同樣具有較高的應(yīng)用價值。

人工蜂群(Artificial Bee Colony，ABC)算法作為一種新的群智能優(yōu)化算法具有收斂速度快、精度高的優(yōu)點[7-8]，但同時，也存在早熟收斂等不足。文獻[9]提出了自適應(yīng)進化策略的人工蜂群優(yōu)化算法，使得算法的收斂速度更快、精度更高。文獻[10]結(jié)合粒子群算法提出了粒子蜂群算法，測試結(jié)果表明算法具有更快的收斂速度和更高的尋優(yōu)精度。因此，本文在對蜜源位置更新策略進行改進的基礎(chǔ)上，基于Bootstrap采樣策略，在蜂群位置更新公式中增加隨機搜索因子和自適應(yīng)位置更新系數(shù)的基礎(chǔ)上，提出了改進人工蜂群算法，并對所提算法進行了驗證。最后，將所提算法用于機器人的路徑規(guī)劃，取得了較好的效果。

1 Bst-ABC算法模型

1.1 ABC算法

ABC算法通過模擬蜜蜂采蜜過程，以實現(xiàn)尋優(yōu)的目的。ABC算法將蜂群分為三類：引領(lǐng)蜂、觀察蜂和偵查蜂。其中，引領(lǐng)蜂數(shù)量和觀察蜂數(shù)量相等，主要任務(wù)是開采蜜源，設(shè)置偵查蜂的目的是為了增加蜜源種類[7-8]。對目標優(yōu)化問題，蜜源的位置被看作是所求問題的解，花蜜數(shù)量被視為所求問題的函數(shù)值，問題求解的過程即為尋找最優(yōu)蜜源的過程。具體為：設(shè)優(yōu)化問題的解為D維，隨機產(chǎn)生2N個解為蜜源位置，即種群數(shù)量(引領(lǐng)蜂個數(shù)=觀察蜂個數(shù)=N)，選取N個作為蜜源位置。蜜蜂搜索蜜源的過程主要由三部分組成：1) 引領(lǐng)蜂對當前蜜源進行鄰域搜索，發(fā)現(xiàn)新蜜源，記錄蜜源的信息；2) 觀察蜂根據(jù)引領(lǐng)蜂提供的蜜源信息，選擇一個食物源，進行鄰域搜索；3) 一個蜜源被放棄，引領(lǐng)蜂變成偵查蜂，隨機尋找新的蜜源。

在搜索過程中按照式(1)隨機產(chǎn)生蜜源，即：

xij=r1(ub-lb)+lb

(1)

式(1)中：r1為[0,1]之間的隨機數(shù)；ub，lb分別為變量x的上、下限。

引領(lǐng)蜂和觀察蜂按式(2)對蜜源進行鄰域搜索，即：

vij=xij+r(xij-xkj)

(2)

式(2)中：vij為新蜜源位置；r∈[-1,1]是一個隨機數(shù)；k∈1,2，…，N且k≠i，為隨機產(chǎn)生的整數(shù)；j為第i個蜜源中第j維的位置，j∈1,2，…，D。

觀察蜂按照式(3)選擇蜜源，即:

(3)

式(3)中，fi為花蜜適應(yīng)度。按式(4)進行計算，即：

(4)

式(4)中，f(i)為第i個解的目標函數(shù)值。在一定循環(huán)次數(shù)之后若蜜源質(zhì)量沒有提高，則該蜜源被放棄，同時，相應(yīng)的引領(lǐng)蜂轉(zhuǎn)變?yōu)閭刹榉?，按?5)隨機產(chǎn)生新蜜源，即：

xij=r2(0,1)(uj-lj)+lj

(5)

式(5)中：r2為[0,1]之間的隨機數(shù)；uj,、lj分別為當前循環(huán)內(nèi)得到的解的第j維最大值和最小值。

1.2 蜜源位置公式的改進

梯度下降算法為了實現(xiàn)優(yōu)化的目的，使得變量沿負梯度方向更新。其自變量迭代量Δxt的形式為：

(6)

為避免算法早熟，提高算法優(yōu)化性能，將式(6)和式(2)相結(jié)合，取出式(6)中分母表示前后兩次迭代的函數(shù)值差，提出如式(7)改進的蜜源位置更新公式。同時，考慮到引領(lǐng)蜂和觀察蜂進行鄰域搜索的早期，蜜源位置隨機性較大，此時，為了快速獲得最優(yōu)解，蜜源位置更新時應(yīng)該具有較大的迭代步長。在搜索后期，蜜源的位置逐漸接近最優(yōu)位置，此時，解的搜索范圍逐漸縮小，引領(lǐng)蜂和觀察蜂進行鄰域搜索的過程中應(yīng)該具有更小的搜索迭代步長。鑒于以上思路，對式(2)進行了改進，如式(7)所示。式(7)中主要增加了基于sigmoid函數(shù)的自適應(yīng)調(diào)整系數(shù)w和隨機搜索因子c∈[0,1],以實現(xiàn)隨機搜索的目的。

vij=wcxij+r(fbest-fi)(xij-xkj)

(7)

式(7)中：t為迭代次數(shù)；fbest為當前最優(yōu)蜜源的適應(yīng)度值；fi為第i個蜜源的適應(yīng)度值。其中，(fbest-fi)代表當前最優(yōu)適應(yīng)度值與當前適應(yīng)度值的差值，r和梯度下降算法中的(xi+1-xi)具有相同的作用，此處取為[-1,1]的一個隨機數(shù)。式(7)的改進與梯度下降算法的思想一致。

1.3 改進人工蜂群算法(Bst-ABC)

Bootstrap是對已有樣本進行有放回的隨機抽樣，使得數(shù)據(jù)集中出現(xiàn)概率大的樣本被抽取到的次數(shù)較多。該方法對包含有n個樣本的數(shù)據(jù)集進行n次抽樣，從而形成新的樣本數(shù)據(jù)集。在ABC算法中，引領(lǐng)蜂和觀察蜂在搜索的過程中依據(jù)隨機選擇的方法進行鄰域搜索，這就使得當前較優(yōu)蜜源不能很好的被利用，降低了算法搜索效率，無法充分開發(fā)當前最優(yōu)解。同時，算法在計算適應(yīng)度時也未能優(yōu)先考慮當前最優(yōu)解，使得最優(yōu)解的利用效率降低。鑒于上述思想我們引入Bootstrap采樣策略，使得算法在每次迭代時能夠充分利用當前最優(yōu)解，從而加快算法收斂速度，提高算法精度。Bst-ABC具體算法步驟如下：

步驟1初始化參數(shù)，根據(jù)式(1)隨機產(chǎn)生初始種群M，種群規(guī)模為2N，找到初始蜜源;

步驟2根據(jù)Bootstrap對蜜源進行采樣，選擇要進行鄰域搜索的蜜源位置。引領(lǐng)蜂根據(jù)式(7)對蜜源進行鄰域搜索，形成新的種群M1;

步驟3根據(jù)Bootstrap對種群M1進行采樣形成新的種群M2;

步驟4計算種群M2中個體適應(yīng)度(函數(shù)值)；

步驟5觀察蜂根據(jù)式(3)選擇蜜源；

步驟6觀察蜂根據(jù)式(7)對蜜源進行鄰域搜索，形成新的種群M3；

步驟7根據(jù)Bootstrap對種群M3進行采樣形成新的種群M4;

步驟8觀察蜂計算種群M4中個體適應(yīng)度(函數(shù)值)，用式(3)選擇較好的蜜源；

步驟9判斷有無蜜源需要拋棄，如果有偵查蜂根據(jù)式(5)發(fā)現(xiàn)新的蜜源；

步驟10記錄迄今為止最好的蜜源，判斷是否滿足終止條件，如果是，輸出最優(yōu)解，否轉(zhuǎn)至步驟7。

Bst-ABC算法流程如圖1所示。

圖1 Bst-ABC算法流程框圖

為了驗證Bst-ABC算法的有效性，對所提算法在以下標準測試函數(shù)[11](選用研究者普遍使用的幾個測試函數(shù))上進行了測試，并和傳統(tǒng)ABC算法及目前改進效果較好的LRABC[11]、FSABC[12]、ABCP[13]算法進行了比較。結(jié)果顯示，無論是在迭代次數(shù)還是精度方面Bst-ABC算法都要優(yōu)于其他幾種算法。由此可見，本文算法具有良好的搜索能力。因此，所提Bst-ABC算法可以用來優(yōu)化SVM的懲罰因子和核函數(shù)參數(shù)。算法具體測試參數(shù)為引領(lǐng)蜂、觀察蜂、蜜源的數(shù)量為50；蜜源循環(huán)次數(shù)limit為50；迭代次數(shù)cycles為 1 000。為了測試算法的有效性，算法隨機運行50，取測試結(jié)果的平均值、最優(yōu)值、最差值、方差來衡量所提算法的性能。測試函數(shù)信息見表1，測試結(jié)果見表2，為了更加直觀的對比幾種算法的優(yōu)劣性，圖2(橫坐標為進化次數(shù)，縱坐標為適應(yīng)度的對數(shù)值)給出了幾個測試函數(shù)具有最優(yōu)測試結(jié)果時的進化過程曲線。

表1 測試函數(shù)信息

表2 Bst-ABC算法測試結(jié)果

圖2 5種算法的進化過程比較

由表2中的結(jié)果數(shù)據(jù)可以看出，所提Bst-ABC算法在解的精度和魯棒性方面要明顯優(yōu)于其他四種算法。圖2直觀的反映了Bst-ABC在迭代初期收斂速度就高于其他幾種ABC算法，而且相比其他ABC算法Bst-ABC能收斂速度更快，且能收斂到更高精度解。

2 路徑規(guī)劃

將本文所提蜂群算法用于機器人的路徑規(guī)劃，檢驗算法的實際應(yīng)用效果。

2.1 參數(shù)選擇

采用如圖3所示的環(huán)境模型，其中起點和終點坐標分別為(0,0)和(100,100)。圖3中以綠色圓代表障礙物，其位置表達式為：

圖3 基本環(huán)境模型示意圖

r2=(x-a)2+(y-b)2

(8)

式(8)中：(a,b)為障礙物的圓心；r為半徑。

以圖3中起點(0,0)、目標點(100,100)，構(gòu)建一條不經(jīng)過障礙物的平滑路徑，使得該條路徑長度最短。建立如下目標函數(shù)[6]：

(9)

式(9)中：l(k)為避障約束函數(shù)；R(k)為第k個障礙物的半徑；K為障礙物個數(shù)；ε為權(quán)重系數(shù),設(shè)為100。

2.2 路徑規(guī)劃仿真

將本文所提Bst-ABC算法和對比結(jié)果較優(yōu)的FSABC算法用于路徑規(guī)劃仿真實驗。設(shè)置兩種算法具有相同的參數(shù)，分別為：引領(lǐng)蜂、觀察蜂、蜜源的數(shù)量分別為50；蜜源循環(huán)次數(shù)limit為50；迭代次數(shù)cycles為1 000。實驗環(huán)境為 Matlab 2015a，分別將兩種算法進行30次實驗,獲得每次算法路徑規(guī)劃結(jié)果，如圖4所示。圖4中橫坐標為算法的實驗次數(shù)，縱坐標為每次規(guī)劃的路徑長度。結(jié)果顯示，相較FSABC算法的規(guī)劃結(jié)果，本文所提算法30次實驗的最終規(guī)劃曲線波動較小，說明該算法穩(wěn)定性高。而FSABC算法的結(jié)果曲線相對波動較大，算法穩(wěn)定性較差。圖5為本文所提算法在目標環(huán)境中的規(guī)劃結(jié)果。圖5中信息顯示，算法的路徑規(guī)劃結(jié)果更加平穩(wěn)、距離更短，30次規(guī)劃結(jié)果都能很好的避開障礙物，具有較高的成功率。而圖6所示的FSABC算法規(guī)劃結(jié)果效果更差，規(guī)劃成功的概率更低。兩種規(guī)劃結(jié)果也能直觀反映出，本文改進算法具有更高的路徑規(guī)劃精度和魯棒性。

圖4 兩種算法規(guī)劃結(jié)果曲線

圖5 Bst-ABC算法規(guī)劃結(jié)果

圖6 FSABC算法規(guī)劃結(jié)果

3 結(jié)論

在增加隨機搜索因子和基于sigmoid函數(shù)的自適應(yīng)位置更新系數(shù)的基礎(chǔ)上，將Bootstrap采樣理論引入ABC算法，提出了基于Bootstrap采樣策略的改進ABC算法(Bst-ABC)，以解決ABC算法早熟及優(yōu)化精度不高的問題。在部分研究者普遍采用的優(yōu)化函數(shù)上的測試結(jié)果表明了所提算法相較其他的改進較優(yōu)的算法具有更高的優(yōu)化精度。最后將所提算法用于機器人的路徑規(guī)劃，表明算法具有應(yīng)用價值。