王金金　丁茹茹　鄭耿輝

摘要：針對基本人工蜂群算法（ABC）收斂速度較慢、容易陷入局部極值等不足，本文通過引入一個自適應(yīng)控制參數(shù)，將基本ABC算法和一種改進的人工蜂群算法（EABC）進行混合，從而得出一種性能更加優(yōu)良的改進人工蜂群算法——EFABC。將本文所提算法與混合前的兩種算法應(yīng)用于三維點云配準實驗中，通過對點云庫中的多個模型進行配準，結(jié)果表明本文所提算法不僅能提高收斂速度和精度，也可在一定程度上提高算法跳脫局部極值的性能。

關(guān)鍵詞：群智能優(yōu)化；人工蜂群算法；自適應(yīng)控制參數(shù)；三維點云配準

1 引言

人工蜂群算法（Artificial bee colony algorithm， ABC）[1]是由Karaboga、Basturk等，于2005年提出的一種群體智能優(yōu)化算法，該算法通過模擬蜜蜂采蜜的行為對問題進行優(yōu)化求解，具有參數(shù)較少、優(yōu)化精度高等優(yōu)點。其與粒子群算法（Particle swarm optimization， PSO）[2]、差分進化算法（Differential evolution， DE）[3]等相比具有更好的優(yōu)化求解性能[4]。人工蜂群算法能夠在不需要知道問題的特殊信息情況下，對問題進行優(yōu)劣的比較，通過蜜蜂個體的尋優(yōu)行為，在整個群體中體現(xiàn)出全局的最優(yōu)值，故該算法一經(jīng)提出就受到了極大的關(guān)注。近年來吸引了國內(nèi)外眾多學(xué)者對其進行了研究、改進[5-8]以及應(yīng)用，主要在于函數(shù)優(yōu)化問題[9]、車輛路徑問題[10]、經(jīng)濟負荷分配[11]、無線傳感器網(wǎng)絡(luò)動態(tài)部署[12]及人工神經(jīng)網(wǎng)絡(luò)[13]等領(lǐng)域。

但不可避免的是，人工蜂群算法在其具有較多優(yōu)點的同時，也存在著一定的缺陷。它所具有的優(yōu)良全局搜索能力，也導(dǎo)致了算法在尋優(yōu)過程中開發(fā)能力較差，耗時較長等。為此，許多學(xué)者提出了一些相關(guān)的改進措施[14-18]，也取得了較好的效果。但由于多數(shù)學(xué)者過多的注重開發(fā)能力，致使改進后的人工蜂群算法容易陷入局部極值。為此，本文提出了一種新的改進措施，用一個自適應(yīng)參數(shù)將基本人工蜂群算法和一種改進后的人工蜂群算法所分別具有的優(yōu)異全局搜索能力和開發(fā)能力相結(jié)合，從而減少算法陷入局部極值的概率并降低求解時間。通過將本文

算法與ABC算法和EABC算法進行三維點云配準實驗，結(jié)果表明本文提出的新改進人工蜂群算法效果更佳。

2三維點云配準

給定兩片點云，一片為待配準點云 ，另外一片為目標點云 ，三維點云配準的目的是要獲取這兩片點云間的歐式變換矩陣 ，以此來解決多個傳感器掃描得到的不同視角點云的配準問題。該變換矩陣包含6個待定參數(shù)，分別為沿三個坐標軸的平移量 以及繞三個坐標軸的旋轉(zhuǎn)角 。在不考慮模型尺度伸縮的情況下，變換矩陣 的表達式為： 其中，

解決配準問題便可利用人工蜂群算法對該目標函數(shù)進行優(yōu)化求解，從而得出歐式變換矩陣 ，完成配準。

3 人工蜂群算法

人工蜂群算法主要是模擬蜂群的智能采蜜行為。在ABC算法的模型中，主要包含三個基本的組成要素：食物源、被雇傭的蜜蜂以及未被雇傭的蜜蜂[19]。利用ABC算法求解優(yōu)化問題時，食物源的位置被抽象成解空間中的點，蜜蜂采蜜的過程就是搜尋最優(yōu)解的過程。被雇傭的蜜蜂也稱采蜜蜂，采蜜蜂即已經(jīng)發(fā)現(xiàn)食物源的蜜蜂，與其所發(fā)現(xiàn)的食物源一一對應(yīng)，并儲存著某一食物源的相關(guān)信息，例如相對于蜂巢的方向、距離以及食物源中花蜜的數(shù)量等，隨后將這些信息以一定的概率與其他蜜蜂分享。未被雇傭的蜜蜂包括跟隨蜂和偵察蜂。采蜜蜂完成工作后，跟隨蜂會根據(jù)采蜜蜂傳達回來的信息，通過一定的概率選擇適應(yīng)度值較高的食物源，提高算法的收斂速度。偵察蜂則是負責(zé)隨機搜索蜂巢附近的食物源，增強算法跳出局部極值的能力。在采蜜的過程中，若采蜜蜂經(jīng)過一定次數(shù)地循環(huán)搜索食物源后，食物源的質(zhì)量仍然沒有改善時，該食物源會被采蜜蜂所拋棄，然后該采蜜蜂變?yōu)閭刹旆?，開始尋找新的食物源。

人工蜂群算法中，蜂群采蜜的過程其實就是尋找優(yōu)化問題中最優(yōu)解的過程。食物源的位置則對應(yīng)著優(yōu)化問題中的可行解，每個食物源的花蜜量則代表相關(guān)解的質(zhì)量（適應(yīng)度fit），采蜜蜂的數(shù)量就等于食物源的數(shù)量。在初始化階段，人工蜂群算法首先生成一個隨機分布的初始種群（食物源位置），其中 表示食物源的數(shù)量。利用公式（3-1）隨機生成食物源：

其中， 為食物源位置 的適應(yīng)度值。適應(yīng)度值越優(yōu)的食物源被選擇的概率越大。

當(dāng)采蜜蜂在某個食物源的位置處搜索超過一定的次數(shù)后，該食物源沒有得到改善時，采蜜蜂會變成偵察蜂，通過公式（3-1）產(chǎn)生新的食物源。

4 EABC算法

人工蜂群算法一經(jīng)提出，就有大批學(xué)者進行研究和改進。提高人工蜂群算法性能的關(guān)鍵，就在于平衡和提高該算法的探索性能和開發(fā)性能。探索性能通常表現(xiàn)為優(yōu)化過程中算法跳脫局部極值的能力，而開發(fā)性能則體現(xiàn)為算法的收斂精度和速度。在原始的人工蜂群算法中，采蜜蜂和跟隨蜂的位置更新搜索方程完全一致，較不利于算法性能的平衡和提高。高衛(wèi)峰等[20]于2014年，研究并提出了一種改進的人工蜂群算法（Enhancing artificial bee colony algorithm， EABC），該算法在采蜜蜂和跟隨蜂階段引入了不同的搜索方程，該改進后的算法性能優(yōu)良。其在采蜜蜂階段引入的搜索方程如公式（4-1）：

5 使用自適應(yīng)參數(shù)控制的改進人工蜂群算法——EFABC

人工蜂群算法的優(yōu)化效果較好，但由于初始的人工蜂群算法的搜索方程更加偏向于探索，故其在處理復(fù)雜的優(yōu)化問題時往往收斂速度較慢，耗時較長。而大部分改進的人工蜂群算法則直接將算法偏向于開發(fā)性能，提高算法的收斂速度，但在節(jié)約了較多時間的同時也使得算法較為容易陷入局部極值。改進的EABC算法較于基本ABC算法性能優(yōu)異，提高了開發(fā)能力，收斂速度較快，但是該算法同樣容易陷入局部極值。因此，為了更好地提高算法的求解性能，本文提出了另一種改進的人工蜂群算法：EFABC（Enhancing faster artificial bee colony algorithm）。該算法在基本ABC算法和EABC算法的基礎(chǔ)上，引入了一個能夠隨著迭代次數(shù)改變的自適應(yīng)參數(shù) ，使算法既具有良好的探索性能又同時具備較好的開發(fā)能力。在解決最優(yōu)化問題時，首先進行全局搜索，在找到較多的疑似最優(yōu)解的位置后再對其進行開發(fā)，通過這樣的搜索過程會取得更佳的結(jié)果。引入本文所提自適應(yīng)參數(shù) 后改進的搜索方程，如公式（5-1）、（5-2）所示。

6實驗結(jié)果以及分析

為了驗證提出的改進算法的性能，本文選取了被廣泛認可的點云配準實驗?zāi)Ｐ?，包括SAMPL點云庫的Bird、Tele、Frog模型和斯坦福實驗室的Bunny模型進行配準實驗。為了體現(xiàn)本文提出改進算法的優(yōu)良性能，本文將EFABC算法與ABC算法、EABC算法進行了對比實驗。仿真環(huán)境為Windows 7操作系統(tǒng)，Intel i5處理器，2.20GHz，4G內(nèi)存。仿真軟件為MATLAB R2014a。為保證實驗結(jié)果數(shù)據(jù)的可靠性，我們對每個模型均進行了20次獨立配準實驗取平均值。在配準完成后，根據(jù)由式（2-5）得出的目標函數(shù)值評價各算法的優(yōu)劣。在實驗中Bird、Tele、Frog點云模型采用的是0度視角和40度視角的兩片點云，同時為了凸顯算法對于不同模型的適用性，對Bunny點云模型采用的是0度視角和45度視角的兩片點云。在所有的配準實驗中，均以0度視角的點云為靜態(tài)點云，另一片點云作為動態(tài)點云進行配準。

實驗配準完成的標準是以最后得出的兩片點云間對應(yīng)點歐式距離的中值（誤差中值）進行核定的。在經(jīng)過大量論文查詢和實驗的觀察比較后，確定了適用于本文實驗中的四種模型的誤差中值的標準精度。具體精度數(shù)值如表1所示：

在實驗中分別采用ABC算法、EABC算法以及本文所提出的EFABC算法對Bird、Tele、Frog以及Bunny等四種點云模型進行配準。配準完成后，各算法取得的誤差中值最小值、平均值以及標準差如表2所示：

由表2中可明顯看出，本文改進后的算法EFABC在對四個不同點云模型的配準實驗中，均取得了最小的配準誤差平均值和標準差，明顯優(yōu)于ABC算法和EABC算法。特別的，對于配準誤差最小值，僅在對Bird模型進行配準得出的實驗結(jié)果中，較EABC算法大，但差異極小。特別要說明的是對于Bunny點云模型，由于其點云密度比另外三個點云模型大得多，因此其數(shù)據(jù)精度對比其他模型要高。

此外，本文在設(shè)定運行次數(shù)和進化代數(shù)后，對不同算法用于各模型配準完成后的成功率及所用時間進行了記錄整理及對比分析。實驗結(jié)果如表3所示：

由表3可以看出，本文新提出的改進EFABC算法與EABC算法較原始的ABC算法相比，在時間和成功率上都有較大的提升。但在Bunny點云模型的實驗中，對EABC和ABC算法數(shù)據(jù)進行對比分析后，雖然EABC的運行時間比ABC算法短，但是成功率卻低于ABC算法，這是因為EABC算法比ABC算法雖提高了開發(fā)能力，但相應(yīng)的探索能力較弱，更加容易陷入局部極值，節(jié)約運行時間的同時降低了配準的精度與成功率。而本文改進的EFABC算法在減少了時間成本的情況下依然保證了較高的配準精度。在Bird、Frog、Tele這三個點云模型中，EFABC算法在節(jié)省時間成本和提高精度方面明顯優(yōu)于ABC算法和EABC算法。

綜上所述，本文引入自適應(yīng)控制參數(shù)優(yōu)化搜索方程后的改進人工蜂群EFABC算法，在三維點云配準的誤差精度和成功率方面都有了明顯的突破與提高，同時降低了運行時間。

7結(jié)束語

本文針對人工蜂群算法收斂速度較慢、容易陷入局部極值的缺陷，結(jié)合一種改進的人工蜂群算法，引入一個自適應(yīng)控制參數(shù)優(yōu)化其搜索方程，從而得到了一種新的改進人工蜂群算法——EFABC。本文所提改進算法兼顧了全局搜索和開發(fā)能力，提高了算法的性能。通過將本文EFABC算法與ABC算法、EABC算法應(yīng)用于三維點云配準實驗，可以發(fā)現(xiàn)，本文EFABC算法不僅提高了配準的精度，而且大大縮短了配準完成所用的時間。由此可見，EFABC算法是一種性能優(yōu)良的改進算法。

參考文獻：

[1]Karaboga D， Basturk B. A powerful and efficient algorithm for numerical function optimization： artificial bee colony （ABC） algorithm [J]. Journal of Global Optimization， 2007， 39（3）：459-471.

[2]He L H， Yao N， Wu J H， et al. Application of modified PSO in the optimization of reactive power[C]. Proc. Of the Chinese Control and Decision Conference， 2009：3493-3496.

[3] Storn R P K. Differential evolution a simple and efficient heuristic for global optimization over continuous spaces [J]. Journal of Global Optimization， 1997， 11（4）：341-359.

[4]Karaboga D， Basturk B. On the performance of artificial bee colony （ABC） algorithm [J]. Applied Soft Computing， 2008， 8（1）：687-697.

[5]暴勵， 曾建潮. 自適應(yīng)搜索空間的混沌蜂群算法[J]. 計算機應(yīng)用研究， 2010， 27（4）：1331-1335.

[6]羅鈞， 樊鵬程. 基于遺傳交叉因子的改進蜂群優(yōu)化算法[J]. 計算機應(yīng)用研究， 2009， 26（10）：3751-3753.

[7]Alatas B. Chaotic bee colony algorithms for global numerical optimization [J]. Expert Systems with Applications， 2010， 37（8）：5682-5687.

[8] 丁海軍， 馮慶嫻. 基于Boltzmann選擇策略的人工蜂群算法[J]. 計算機工程與應(yīng)用， 2009， 45（31）：53-55.

[9] Karaboga D， Basturk B. A comparative study of artificial bee colony algorithm [J]. Applied Mathematics and Computation， 2009， 214（1）108-132.

[10]于曉東， 廉蓮. 人工蜂群算法在單時間窗車輛路徑問題中的應(yīng)用[J]. 科技創(chuàng)新與應(yīng)用， 2016（19）：64-64.

[11]胡欣. 改進的人工蜂群算法及其在經(jīng)濟負荷分配中的應(yīng)用[D]. 武漢理工大學(xué)， 2015.

[12]賀培玉. 人工蜂群算法及其在無線傳感器網(wǎng)絡(luò)動態(tài)部署中的應(yīng)用[D]. 山東大學(xué)， 2014.

[13] 冷昕，張樹群， 雷兆宜. 改進的人工蜂群算法在神經(jīng)網(wǎng)絡(luò)中的應(yīng)用[J]. 計算機工程與應(yīng)用， 2016， 52（11）：7-10.

[14]李彥蒼， 彭揚. 基于信息熵的改進人工蜂群算法[J]. 控制與決策， 2015， 30（06）：1121-1125.

[15]畢曉君， 王艷嬌. 改進人工蜂群算法[J]. 哈爾濱工程大學(xué)學(xué)報， 2012， 33（01）：117-123.

[16]王冰. 基于局部最優(yōu)解的改進人工蜂群算法[J]. 計算機應(yīng)用研究， 2014， 31（04）：1023-1026.

[17]王生生， 楊娟娟， 柴勝. 基于混沌鯰魚效應(yīng)的人工蜂群算法及應(yīng)用[J]. 電子學(xué)報， 2014， 42（09）：1731-1737.

[18] 臧明相， 馬軒， 段奕明. 一種改進的人工蜂群算法[J]. 西安電子科技大學(xué)學(xué)報， 2015， 42（2）：65-70.

[19]Nurhan K. A new design method based on artificial bee colony algorithm for digital IIR filters[J]. Journal of the Franklin Institute， 2009， 346（4）：328-348.

[20]Gao W F， Liu S Y， Huang L L. Enhancing artificial bee colony algorithm using more information-based search equations[J]. Information Sciences， 2014， 270（1）： 112-133.

基金項目：2016年國家級大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計劃項目“基于群智能計算的紋理圖像拼接技術(shù)研究”（201610069021）