基于離子運動-人工蜂群算法的移動機器人路徑規劃

魏 博，楊 茸，舒思豪，萬 勇，苗建國

（1.重慶郵電大學先進制造工程學院，重慶 400064；2.四川大學空天科學與工程學院，成都 610065）

（*通信作者電子郵箱jianguomiao1992@163.com）

0 引言

路徑規劃是輪式移動機器人導航的核心技術之一，是指在具有障礙物環境下給定機器人起始點與目標點后，按照特定的評價標準為機器人提供一條安全、高效的運動路徑，其評價標準通常有：最短行程、最短時間、最少能量等［1］，而傳統的路徑規劃方法有人工勢場法、圖搜索法、柵格解耦法等［2-3］。近些年國內外學者對路徑規劃方法做了大量的研究，提出了眾多優秀的群智能算法：如粒子群優化（Partical Swarm Optimization，PSO）算法、蟻群優化（Ant Colony Optimization，ACO）算法、煙花-蟻群融合算法（Fireworks-Ant Colony Algorithm，FA-ACA）等［4-7］，這些方法極大地提高了路徑規劃性能，但同時也有一定的局限性，比如易陷入局部最優、運算時間長、求解復雜等。

人工蜂群（Artificial Bee Colony，ABC）算法是Karaboga［8］受蜜蜂覓食啟發提出的群體智能進化算法，該算法模擬了蜜蜂采蜜相互協作轉換來指引搜索。標準的ABC 算法具有收斂速度快、尋優能力強、實現簡單等優點，但同時也存在后期收斂速度過快導致局部最優、平衡能力差、精度相對較低等缺點。為了加快算法收斂，文獻［9］中在ABC 算法初始化階段引入了隨機因子，并應用于多機器人路徑規劃；文獻［10］中在機器人路徑規劃中應用了一種改進的ABC 算法，該改進算法在引領蜂搜索階段引入了一組隨機向量并添加了當前最優值，再進一步利用Bezier 曲線把路徑規劃問題轉化成求極值點問題；文獻［11］中對ABC 算法的偵察蜂搜索階段進行改進，應用反向學習策略解決了種群多樣性差和收斂速度慢等問題；文獻［12］中將混沌優化方法引入ABC 算法，不僅縮小了算法的搜索空間，還提高了算法收斂速度和精度；文獻［13］通過與PSO 算法結合來改進ABC 算法，在一定程度上平衡了ABC算法的開發能力和探索能力，避免了局部最優。

針對算法收斂速度慢和易陷入局部最優等問題，本文提出了一種基于離子運動的人工蜂群（Ion Motion-Artificial Bee Colony，IM-ABC）算法，為避免傳統的ABC 算法平衡能力差、易陷入局部最優等缺點，該算法在搜索階段的前后期采用不同策略。在算法前期提出了離子交叉搜索規則，以提升種群開發能力；后期采用反輪盤賭來擴大種群多樣性，避免陷入局部最優。全局更新階段則提出了自適應花香濃度規則，改善了抽樣方式，引導種群更新的方向。與其他群智能算法相比，該算法在路徑規劃中能更有效地平衡算法的開發和探索能力，在能避免局部最優的前提下，極大地提升了算法的收斂速度與精度。

1 標準ABC算法

ABC 算法是一種新興的群體啟發智能進化算法，由于算法在尋優過程中設置參數較少、收斂速度快，在一定概率上能跳出局部最優獲得較理想的全局最優解，因而受到了各國學者的重視［14］。

ABC 算法是模擬蜜蜂采蜜過程所提出的，其中蜂群主要分為三類：領蜂、跟隨蜂和偵察蜂［15］。三種蜜蜂在采蜜過程中進行協作和信息共享，跟隨蜂得到引領蜂信息后進行評價，根據優劣選擇合適的花源進行采蜜；偵察蜂在蜜源枯竭時更新較差蜜源，每一個蜜源代表路徑規劃的一條可行解。ABC 算法尋優步驟如下：

1）初始化階段。首先設定蜂群數量SUM、最大迭代次數N和控制參數Limit，在S維空間隨機生成M個初始位置Xi=(xi1，xi2，…，xiS)，Xi按式（1）進行生成：

其中：Wi，j和Ui，j分別為S維空間取值的上下界，i=1，2，…，M，j=1，2，…，S；M代表解的個數，一般取值為SUM/2。

2）搜索階段。種群中適應度值較小的一半為引領蜂，另一半為跟隨蜂，跟隨蜂隨機選擇個體q1∈(1，2，…，M/2)逐維進行搜索產生新個體V，如式（3）。

式中：φ為[1，-1]內的隨機數。

跟隨蜂按照輪盤賭在引領蜂群中選擇概率pi較大的個體，然后在［0，1］內產生一個隨機數，如果pi大于產生的隨機數，則按照式（4）選擇位置J：

式（4）中fit為蜜源適應度值，按式（5）進行更新。引領蜂和跟隨蜂產生新解后按照式（6）進行貪婪選擇并保留新解。

3）全局更新階段。經過引領蜂和跟隨蜂種群的搜索完成后，為了避免種群多樣性喪失，若i位置連續Limit代不變，那么就根據式（1）隨機生成一個替代解，接下來返回雇傭蜂和跟隨蜂搜索過程，重復地循環直至找到最優解。

2 IM-ABC算法

2.1 算法原理

在標準的ABC 算法中，引領蜂搜索實際可以理解成自身向其他個體學習的過程，在算法中引領蜂的更新是在自身位置周圍隨機選擇個體進行交叉更新，這樣選擇的個體優秀和較差的幾率對等。雖然這種方式在一定程度上擴大了種群多樣性，但大大地降低了算法的收斂速度，也就是說這種方式探索能力強但開發能力差［16］。為了平衡算法的開發能力和探索能力，可以根據周圍個體適應度值的優劣調整進化方向，這樣有利于提高種群總體的進化速度和效果。

考慮到跟隨蜂依據輪盤賭選擇策略來更新種群是一種相對貪婪的方式，在算法的整個過程中會快速地降低種群多樣性，容易導致過早收斂和局部最優，為了在保證收斂速度的前提下，避免局部最優，需要引入一個自適應因子進行調節。為了使算法得到更好的效果，把算法搜索階段分為前后兩期。

2.1.1 離子概念模型

在自然界中，具有相似電荷的離子往往會排斥，而具有相反電荷的離子相互吸引。吸引力和排斥力與陰離子和陽離子之間的關系如圖1 所示，實線箭頭代表引力，虛線箭頭代表離子在吸引力/排斥力作用下陰離子向最好的陽離子靠攏，而陽離子向最好的陰離子移動。

圖1 陰陽離子運動模型圖Fig.1 Anion and cation motion model

2.1.2 離子交叉搜索規則

為了平衡算法的開發和探索能力，把算法搜索階段分為前后兩期，并引入離子交叉搜索規則：

1）搜索階段前期，在ABC 算法中引入離子運動交叉搜索方程，假設引領蜂為陽離子，跟隨蜂為陰離子，蜜蜂之間傳遞的信息比作離子間引力，則引領蜂和跟隨蜂交叉更新如式（7）、（8）所示。引領蜂和跟隨蜂選擇適應度值最優的個體交叉學習，并引入引力因子AFi，j、BFi，j自適應調節增大搜索步長，這種方法可以自適應提高算法進化速度、促進種群快速收斂。

式中：Ai，j、Bi，j分別是引領蜂和跟隨蜂產生的新生個體；Abestj、Bbestj代表種群中最優引領蜂與跟隨蜂。

2）搜索階段后期，種群個體大都處于較優狀態，優秀個體的進化信息不再起主導作用，這時需要平衡前期的開發能力，增大蜂群的局部探索能力，使蜂群能夠在自身鄰域附近進行精細化搜索，不需要如前期那樣較大的搜索步長，避免因搜索步長較大導致局部最優，降低尋找到全局最優解的概率。

在后期中引領蜂按照式（3）進行搜索，產生的新解按照式（6）進行選擇替換；跟隨蜂則引入反向輪盤賭選擇機制如式（11），適應度值倒數較大的個體被選中的可能性變大，能有效地跳出局部最優。

2.1.3 自適應花香濃度規則

在全局更新階段，由于偵察蜂位置更新方式隨機性較大，屬于放回型采樣，會對較差的蜜源做多次無用更新計算，和實際意義不貼切，可以加入自適應花香濃度信息策略，根據加入自適應因子的花香濃度進行更新。自適應因子可以調節每次循環中的花香濃度，當偵察蜂發現某個方向蜜源較差時，就不會第二次更新該方向，偵察蜂根據式（12）計算位置更新概率。

式中：KTi為每維度的花香濃度，?(t)是自適應參數，Max_Cycle是算法的最大迭代次數。初始時每個維度花香濃度都相等，當排除后的維度花香濃度KTi設為零，這樣就避免了同一個方向二次更新，同時自適應地為偵察蜂更新提供方向性，一定程度上加速了算法收斂，且不會導致局部最優。

2.2 算法流程

IM-ABC算法流程如圖2所示。具體步驟如下：

步驟1 設置初始化相關參數：種群數量SUM，最大迭代次數N，控制參數Limit。

步驟2 在可行空間內產生初始種群，并設置迭代次數iter=0。

步驟3 利用離子運動規律產生新解，引領蜂和跟隨蜂按式（7）、（8）產生新解Ai，j、Bi，j。

步驟4 對產生的新解Ai，j、Bi，j按式（6）保留較優的解。

步驟5 跳轉回步驟2 和步驟3 進行反復迭代，若迭代次數iter＞N/2，則跳轉到步驟6。

步驟6 引領蜂按式（3）隨機產生新解vi，j，并按式（6）保留較優的解。

步驟7 跟隨蜂按照式（11）的反輪盤賭的機制選擇個體，并按式（3）產生新個體vi，j，并按式（6）保留較優的解。

步驟8 跳轉回步驟2 和步驟3 進行反復迭代，若位置i連續Limit代未更新，則放棄該位置，偵察蜂根據式（12）的花香因子選擇個體，并更新種群。

步驟9 判斷是否達到最大迭代次數或目標精度，若滿足，則輸出最優解，否則跳轉至步驟5。

圖2 IM-ABC算法流程Fig.2 Flowchart of IM-ABC algorithm

3 性能測試及路徑規劃仿真實驗

3.1 算法性能測試

為了驗證IM-ABC 算法的有效性，本文選擇研究人員普遍使用的四個標準測試函數：Sphere、Rosenbrock、Rastrigin 和Griwank，對傳統的ABC算法和目前性能較為優秀的快速搜索人工蜂群（Fast Search Artificial Bee Colony，FSABC）算法、局部路徑人工蜂群算法（Local Route Artificial Bee Colony，LRABC）算法進行測試比較。FSABC 算法采用局部搜索算子在求解精度上有顯著提升［17］，LRABC 算法在收斂速度上有較大提升［18］，但兩個算法在開發能力上仍具有一定的缺陷。

在實驗中對四種算法的參數進行設置，算法中總群數量SUM設為100，引領蜂和跟隨蜂的數量分別設為50，Limit值設置為750，測試函數的維度均為30，且最大迭代次數N設置為2 000，通過對實驗數據的最優值、最差值、平均值和方差來衡量算法性能。測試函數信息見表1，測試結果數據見表2，實驗結果顯示本文所提的IM-ABC 算法的精度要優于傳統的ABC算法和其余兩個ABC改進算法，具有良好的搜索能力。

表1 標準測試函數Tab.1 Benchmark functions

表2 算法仿真結果比較Tab.2 Comparison of algorithm simulation results

3.2 路徑規劃實驗

本文算法主要用于求解機器人路徑規劃問題，為了驗證算法的實際應用效果，通過建立柵格模型來模擬現實中復雜多變的倉儲環境。如圖3 所示，以20 m×20 m 的柵格環境為例，在柵格地圖中，工作環境被劃分成兩種柵格，黑色柵格表示障礙物，白色柵格表示無障礙物，在系統仿真程序中分別用1和0表示，柵格圖的尺寸和大小可根據實際環境進行調整。

圖3 柵格模型工作環境Fig.3 Grid model working environment

實驗利用Matlab 2016a 軟件進行仿真，通過測試ABC 算法、FSABC 算法、LRABC、IM-ABC 算法在柵格地圖上尋找由起始點到目標點中心連線的最短路徑來模擬實際環境中的最短路徑。在20 m×20 m 大小的柵格地圖環境中，將蜂群規模SUM設置為100，最大迭代次數N為200，Limit值設置為10。實驗結果如圖4、5和表3所示。

表3 路徑規劃仿真實驗結果對比Tab.3 Comparison of path planning simulation experimental results

由圖4及表3可知，IM-ABC算法收斂速度較快，相較傳統ABC算法而言，改進后的算法尋優性能上提升了12.6%，迭代次數減少了58.3%，主要原因是傳統的ABC 算法在搜索階段盲目性較大，導致整個搜索過程步長較短，收斂速度慢，同時在全局更新階段由于隨機更新，進一步降低了收斂速度；而改進算法在避免局部最優的前提下，提出離子搜索方式和花香濃度策略，提高了算法的收斂速度。因此本文所提算法具有更短最優路徑和更快的收斂速度。

圖4 四種算法搜索的最優路徑Fig.4 Optimal paths searched by four algorithms

圖5 四種算法的收斂圖Fig.5 Convergence graphs of four algorithms

4 結語

本文提出了一種基于離子運動的人工蜂群（IM-ABC）算法，主要用于解決倉儲環境下路徑規劃問題。針對傳統ABC算法存在的不足與缺陷，引入自然界離子間相互作用力來改善蜂群算法搜索階段，并把搜索階段分成前、后期來平衡算法的開發和探索能力，在保證不陷入局部最優的前提下，加大搜索步長，并在全局更新階段加入自適應性花香濃度，根據花香濃度指引變異自適應性更新，提升算法的效率。該算法在不同的標準測試函數下驗證極值求解能力并表現出較大的優勢，通過求解機器人路徑規劃問題驗證了算法的實際應用效果。下一步的工作是探究算法參數對算法的影響，更進一步研究多機器人蜂群算法模型及性能。