蜂群優化算法的機器人路徑規劃

張占義，朱金達

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

adaptive

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

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

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

1 Bst-ABC算法模型

1.1 ABC算法

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

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

xij=r1(ub-lb)+lb

(1)

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

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

vij=xij+r(xij-xkj)

(2)

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

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

(3)

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

(4)

式(4)中，f(i)為第i個解的目標函數值。在一定循環次數之后若蜜源質量沒有提高，則該蜜源被放棄，同時，相應的引領蜂轉變為偵查蜂，按式(5)隨機產生新蜜源，即：

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

(5)

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

1.2 蜜源位置公式的改進

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

(6)

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

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

(7)

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

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

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

步驟1初始化參數，根據式(1)隨機產生初始種群M，種群規模為2N，找到初始蜜源;

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

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

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

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

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

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

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

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

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

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

圖1 Bst-ABC算法流程框圖

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

表1 測試函數信息

表2 Bst-ABC算法測試結果

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

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

2 路徑規劃

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

2.1 參數選擇

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

圖3 基本環境模型示意圖

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

(8)

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

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

(9)

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

2.2 路徑規劃仿真

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

圖4 兩種算法規劃結果曲線

圖5 Bst-ABC算法規劃結果

圖6 FSABC算法規劃結果

3 結論

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