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

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

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

0 引言

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

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

1 標準ABC算法

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

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

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

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

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

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

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

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

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

2 IM-ABC算法

2.1 算法原理

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

考慮到跟隨蜂依據(jù)輪盤賭選擇策略來更新種群是一種相對貪婪的方式，在算法的整個過程中會快速地降低種群多樣性，容易導(dǎo)致過早收斂和局部最優(yōu)，為了在保證收斂速度的前提下，避免局部最優(yōu)，需要引入一個自適應(yīng)因子進行調(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)提高算法進化速度、促進種群快速收斂。

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

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

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

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

在全局更新階段，由于偵察蜂位置更新方式隨機性較大，屬于放回型采樣，會對較差的蜜源做多次無用更新計算，和實際意義不貼切，可以加入自適應(yīng)花香濃度信息策略，根據(jù)加入自適應(yīng)因子的花香濃度進行更新。自適應(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 進行反復(fù)迭代，若迭代次數(shù)iter＞N/2，則跳轉(zhuǎn)到步驟6。

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

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

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

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

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

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

3.1 算法性能測試

為了驗證IM-ABC 算法的有效性，本文選擇研究人員普遍使用的四個標準測試函數(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）算法進行測試比較。FSABC 算法采用局部搜索算子在求解精度上有顯著提升［17］，LRABC 算法在收斂速度上有較大提升［18］，但兩個算法在開發(fā)能力上仍具有一定的缺陷。

在實驗中對四種算法的參數(shù)進行設(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改進算法，具有良好的搜索能力。

表1 標準測試函數(shù)Tab.1 Benchmark functions

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

3.2 路徑規(guī)劃實驗

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

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

實驗利用Matlab 2016a 軟件進行仿真，通過測試ABC 算法、FSABC 算法、LRABC、IM-ABC 算法在柵格地圖上尋找由起始點到目標點中心連線的最短路徑來模擬實際環(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算法而言，改進后的算法尋優(yōu)性能上提升了12.6%，迭代次數(shù)減少了58.3%，主要原因是傳統(tǒng)的ABC 算法在搜索階段盲目性較大，導(dǎo)致整個搜索過程步長較短，收斂速度慢，同時在全局更新階段由于隨機更新，進一步降低了收斂速度；而改進算法在避免局部最優(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)性更新，提升算法的效率。該算法在不同的標準測試函數(shù)下驗證極值求解能力并表現(xiàn)出較大的優(yōu)勢，通過求解機器人路徑規(guī)劃問題驗證了算法的實際應(yīng)用效果。下一步的工作是探究算法參數(shù)對算法的影響，更進一步研究多機器人蜂群算法模型及性能。