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

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

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

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

0 引言

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

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

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

1 標(biāo)準(zhǔn)ABC算法

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

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

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

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

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

式中：φ為[1，-1]內(nèi)的隨機(jī)數(shù)。

跟隨蜂按照輪盤賭在引領(lǐng)蜂群中選擇概率pi較大的個體，然后在［0，1］內(nèi)產(chǎn)生一個隨機(jī)數(shù)，如果pi大于產(chǎn)生的隨機(jī)數(shù)，則按照式（4）選擇位置J：

式（4）中fit為蜜源適應(yīng)度值，按式（5）進(jìn)行更新。引領(lǐng)蜂和跟隨蜂產(chǎn)生新解后按照式（6）進(jìn)行貪婪選擇并保留新解。

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

2 IM-ABC算法

2.1 算法原理

在標(biāo)準(zhǔn)的ABC 算法中，引領(lǐng)蜂搜索實際可以理解成自身向其他個體學(xué)習(xí)的過程，在算法中引領(lǐng)蜂的更新是在自身位置周圍隨機(jī)選擇個體進(jìn)行交叉更新，這樣選擇的個體優(yōu)秀和較差的幾率對等。雖然這種方式在一定程度上擴(kuò)大了種群多樣性，但大大地降低了算法的收斂速度，也就是說這種方式探索能力強(qiáng)但開發(fā)能力差［16］。為了平衡算法的開發(fā)能力和探索能力，可以根據(jù)周圍個體適應(yīng)度值的優(yōu)劣調(diào)整進(jìn)化方向，這樣有利于提高種群總體的進(jìn)化速度和效果。

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

2.1.1 離子概念模型

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

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

2.1.2 離子交叉搜索規(guī)則

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

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

式中：Ai，j、Bi，j分別是引領(lǐng)蜂和跟隨蜂產(chǎn)生的新生個體；Abestj、Bbestj代表種群中最優(yōu)引領(lǐng)蜂與跟隨蜂。

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

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

2.1.3 自適應(yīng)花香濃度規(guī)則

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

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

2.2 算法流程

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

步驟1 設(shè)置初始化相關(guān)參數(shù)：種群數(shù)量SUM，最大迭代次數(shù)N，控制參數(shù)Limit。

步驟2 在可行空間內(nèi)產(chǎn)生初始種群，并設(shè)置迭代次數(shù)iter=0。

步驟3 利用離子運動規(guī)律產(chǎn)生新解，引領(lǐng)蜂和跟隨蜂按式（7）、（8）產(chǎn)生新解Ai，j、Bi，j。

步驟4 對產(chǎn)生的新解Ai，j、Bi，j按式（6）保留較優(yōu)的解。

步驟5 跳轉(zhuǎn)回步驟2 和步驟3 進(jìn)行反復(fù)迭代，若迭代次數(shù)iter＞N/2，則跳轉(zhuǎn)到步驟6。

步驟6 引領(lǐng)蜂按式（3）隨機(jī)產(chǎn)生新解vi，j，并按式（6）保留較優(yōu)的解。

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

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

步驟9 判斷是否達(dá)到最大迭代次數(shù)或目標(biāo)精度，若滿足，則輸出最優(yōu)解，否則跳轉(zhuǎn)至步驟5。

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

3 性能測試及路徑規(guī)劃仿真實驗

3.1 算法性能測試

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

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

表1 標(biāo)準(zhǔn)測試函數(shù)Tab.1 Benchmark functions

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

3.2 路徑規(guī)劃實驗

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

圖3 柵格模型工作環(huán)境Fig.3 Grid model working environment

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

表3 路徑規(guī)劃仿真實驗結(jié)果對比Tab.3 Comparison of path planning simulation experimental results

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

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

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

4 結(jié)語

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