基于參數(shù)優(yōu)化的改進(jìn)人工蜂群算法及其應(yīng)用
發(fā)布時(shí)間:2018-07-01 來源: 歷史回眸 點(diǎn)擊:
摘要:針對基本人工蜂群算法(ABC)收斂速度較慢、容易陷入局部極值等不足,本文通過引入一個自適應(yīng)控制參數(shù),將基本ABC算法和一種改進(jìn)的人工蜂群算法(EABC)進(jìn)行混合,從而得出一種性能更加優(yōu)良的改進(jìn)人工蜂群算法——EFABC。將本文所提算法與混合前的兩種算法應(yīng)用于三維點(diǎn)云配準(zhǔn)實(shí)驗(yàn)中,通過對點(diǎn)云庫中的多個模型進(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)化算法,該算法通過模擬蜜蜂采蜜的行為對問題進(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]。人工蜂群算法能夠在不需要知道問題的特殊信息情況下,對問題進(jìn)行優(yōu)劣的比較,通過蜜蜂個體的尋優(yōu)行為,在整個群體中體現(xiàn)出全局的最優(yōu)值,故該算法一經(jīng)提出就受到了極大的關(guān)注。近年來吸引了國內(nèi)外眾多學(xué)者對其進(jìn)行了研究、改進(jìn)[5-8]以及應(yīng)用,主要在于函數(shù)優(yōu)化問題[9]、車輛路徑問題[10]、經(jīng)濟(jì)負(fù)荷分配[11]、無線傳感器網(wǎng)絡(luò)動態(tài)部署[12]及人工神經(jīng)網(wǎng)絡(luò)[13]等領(lǐng)域。
但不可避免的是,人工蜂群算法在其具有較多優(yōu)點(diǎn)的同時(shí),也存在著一定的缺陷。它所具有的優(yōu)良全局搜索能力,也導(dǎo)致了算法在尋優(yōu)過程中開發(fā)能力較差,耗時(shí)較長等。為此,許多學(xué)者提出了一些相關(guān)的改進(jìn)措施[14-18],也取得了較好的效果。但由于多數(shù)學(xué)者過多的注重開發(fā)能力,致使改進(jìn)后的人工蜂群算法容易陷入局部極值。為此,本文提出了一種新的改進(jìn)措施,用一個自適應(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)云間的歐式變換矩陣 ,以此來解決多個傳感器掃描得到的不同視角點(diǎn)云的配準(zhǔn)問題。該變換矩陣包含6個待定參數(shù),分別為沿三個坐標(biāo)軸的平移量 以及繞三個坐標(biāo)軸的旋轉(zhuǎn)角 。在不考慮模型尺度伸縮的情況下,變換矩陣 的表達(dá)式為: 其中,
解決配準(zhǔn)問題便可利用人工蜂群算法對該目標(biāo)函數(shù)進(jìn)行優(yōu)化求解,從而得出歐式變換矩陣 ,完成配準(zhǔn)。
3 人工蜂群算法
人工蜂群算法主要是模擬蜂群的智能采蜜行為。在ABC算法的模型中,主要包含三個基本的組成要素:食物源、被雇傭的蜜蜂以及未被雇傭的蜜蜂[19]。利用ABC算法求解優(yōu)化問題時(shí),食物源的位置被抽象成解空間中的點(diǎn),蜜蜂采蜜的過程就是搜尋最優(yōu)解的過程。被雇傭的蜜蜂也稱采蜜蜂,采蜜蜂即已經(jīng)發(fā)現(xiàn)食物源的蜜蜂,與其所發(fā)現(xiàn)的食物源一一對應(yīng),并儲存著某一食物源的相關(guān)信息,例如相對于蜂巢的方向、距離以及食物源中花蜜的數(shù)量等,隨后將這些信息以一定的概率與其他蜜蜂分享。未被雇傭的蜜蜂包括跟隨蜂和偵察蜂。采蜜蜂完成工作后,跟隨蜂會根據(jù)采蜜蜂傳達(dá)回來的信息,通過一定的概率選擇適應(yīng)度值較高的食物源,提高算法的收斂速度。偵察蜂則是負(fù)責(zé)隨機(jī)搜索蜂巢附近的食物源,增強(qiáng)算法跳出局部極值的能力。在采蜜的過程中,若采蜜蜂經(jīng)過一定次數(shù)地循環(huán)搜索食物源后,食物源的質(zhì)量仍然沒有改善時(shí),該食物源會被采蜜蜂所拋棄,然后該采蜜蜂變?yōu)閭刹旆,開始尋找新的食物源。
人工蜂群算法中,蜂群采蜜的過程其實(shí)就是尋找優(yōu)化問題中最優(yōu)解的過程。食物源的位置則對應(yīng)著優(yōu)化問題中的可行解,每個食物源的花蜜量則代表相關(guān)解的質(zhì)量(適應(yīng)度fit),采蜜蜂的數(shù)量就等于食物源的數(shù)量。在初始化階段,人工蜂群算法首先生成一個隨機(jī)分布的初始種群(食物源位置),其中 表示食物源的數(shù)量。利用公式(3-1)隨機(jī)生成食物源:
其中, 為食物源位置 的適應(yīng)度值。適應(yīng)度值越優(yōu)的食物源被選擇的概率越大。
當(dāng)采蜜蜂在某個食物源的位置處搜索超過一定的次數(shù)后,該食物源沒有得到改善時(shí),采蜜蜂會變成偵察蜂,通過公式(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í)較長。而大部分改進(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ǔ)上,引入了一個能夠隨著迭代次數(shù)改變的自適應(yīng)參數(shù) ,使算法既具有良好的探索性能又同時(shí)具備較好的開發(fā)能力。在解決最優(yōu)化問題時(shí),首先進(jìn)行全局搜索,在找到較多的疑似最優(yōu)解的位置后再對其進(jìn)行開發(fā),通過這樣的搜索過程會取得更佳的結(jié)果。引入本文所提自適應(yīng)參數(shù) 后改進(jìn)的搜索方程,如公式(5-1)、(5-2)所示。
相關(guān)熱詞搜索:蜂群 算法 及其應(yīng)用 改進(jìn) 優(yōu)化
熱點(diǎn)文章閱讀