王金金　丁茹茹　鄭耿輝

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

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

1 引言

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

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

算法與ABC算法和EABC算法進(jìn)行三維點(diǎn)云配準(zhǔn)實(shí)驗(yàn)，結(jié)果表明本文提出的新改進(jìn)人工蜂群算法效果更佳。

2三維點(diǎn)云配準(zhǔn)

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

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

3 人工蜂群算法

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

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

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

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

4 EABC算法

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

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

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

6實(shí)驗(yàn)結(jié)果以及分析

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

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

在實(shí)驗(yàn)中分別采用ABC算法、EABC算法以及本文所提出的EFABC算法對(duì)Bird、Tele、Frog以及Bunny等四種點(diǎn)云模型進(jìn)行配準(zhǔn)。配準(zhǔn)完成后，各算法取得的誤差中值最小值、平均值以及標(biāo)準(zhǔn)差如表2所示：

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

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

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

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

7結(jié)束語

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

參考文獻(xiàn)：

[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]暴勵(lì)， 曾建潮. 自適應(yīng)搜索空間的混沌蜂群算法[J]. 計(jì)算機(jī)應(yīng)用研究， 2010， 27（4）：1331-1335.

[6]羅鈞， 樊鵬程. 基于遺傳交叉因子的改進(jìn)蜂群優(yōu)化算法[J]. 計(jì)算機(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]. 計(jì)算機(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]于曉東， 廉蓮. 人工蜂群算法在單時(shí)間窗車輛路徑問題中的應(yīng)用[J]. 科技創(chuàng)新與應(yīng)用， 2016（19）：64-64.

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

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

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

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

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

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

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

[18] 臧明相， 馬軒， 段奕明. 一種改進(jìn)的人工蜂群算法[J]. 西安電子科技大學(xué)學(xué)報(bào)， 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.

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