基于Lévy飛行的人工蜂群算法

程憲寶

（廣州工商學(xué)院，廣東廣州510850）

基于Lévy飛行的人工蜂群算法

程憲寶

（廣州工商學(xué)院，廣東廣州510850）

針對(duì)人工蜂群算法在后期容易陷入局部最優(yōu)，且開(kāi)發(fā)能力不足的缺陷，提出了一種基于Lévy飛行的人工蜂群算法，在尋找蜜源過(guò)程中，引領(lǐng)蜂轉(zhuǎn)變成偵查蜂時(shí)，引入Lévy分布函數(shù)來(lái)調(diào)配原有的用0-1的隨機(jī)數(shù)參與的貪婪算法，有效增加了算法的合理性。最后用5個(gè)有效的測(cè)試函數(shù)對(duì)改進(jìn)的算法和原算法進(jìn)行比較，結(jié)果表明，基于Lévy分布的人工蜂群算法較原算法在收斂速度和優(yōu)化速度上都有顯著提高。

ABC;優(yōu)化；Lévy分布；仿真

人工蜂群算法[1](Artificial Bee Colony Algorithm,ABC)是一種以蜂群內(nèi)部自組織和群體智能為基礎(chǔ)的仿生學(xué)優(yōu)化算法。ABC算法原理簡(jiǎn)單，參數(shù)少，易于實(shí)現(xiàn)，有較強(qiáng)的全局尋優(yōu)能力，已經(jīng)快速成為優(yōu)化領(lǐng)域中強(qiáng)有力的全局優(yōu)化工具之一[2-6]。同時(shí)，和眾多的仿生學(xué)優(yōu)化算法類(lèi)似，ABC算法由于進(jìn)化方式和選擇策略的影響，該算法在接近全局最優(yōu)解時(shí)，也存在搜索速度變慢、種群多樣性減少、容易陷入局部最優(yōu)等缺點(diǎn),因此本文提出了一種基于Lévy（萊維）分布[7]的改進(jìn)人工蜂群算法，可以有效提高算法后期全局最優(yōu)的開(kāi)發(fā)，并且局部搜索能力上比原算法有顯著提高。

1 人工蜂群算法

1.1 ABC算法概述

ABC算法是模擬自然界中蜜蜂群體采蜜行為的一種智能算法。蜜蜂個(gè)體只能進(jìn)行簡(jiǎn)單的動(dòng)作，但是其群體卻表現(xiàn)出非常智能的行為，在尋找蜜源、采集蜂蜜、傳遞信息等方面精準(zhǔn)到位。在ABC算法中，將群體蜜蜂分為三種，引領(lǐng)蜂、跟隨蜂、和偵查蜂。引領(lǐng)蜂負(fù)責(zé)采集蜂蜜和招募蜜蜂，跟隨蜂根據(jù)引領(lǐng)蜂所傳遞的信息按一定的規(guī)則選擇引領(lǐng)蜂進(jìn)行跟隨，偵查蜂負(fù)責(zé)開(kāi)發(fā)新的蜜源。在尋優(yōu)問(wèn)題中，每個(gè)蜜源表示問(wèn)題的一個(gè)可能解，蜜源質(zhì)量的好壞用解的適應(yīng)度值來(lái)表示。適應(yīng)度值高的解所代表的食物源會(huì)優(yōu)先被引領(lǐng)蜂采集，跟隨蜂會(huì)在食物源的周?chē)M(jìn)行偵查，以期發(fā)現(xiàn)更優(yōu)的蜜源，每發(fā)現(xiàn)一個(gè)蜜源，就會(huì)與原蜜源進(jìn)行比較，如果新的蜜源的質(zhì)量比原蜜源更好，則淘汰原蜜源，并隨即在新的蜜源周?chē)^續(xù)重復(fù)原來(lái)的搜索。經(jīng)過(guò)這樣多次搜索就可以確定適應(yīng)度值最高的解，即問(wèn)題的最優(yōu)解。如果蜜蜂個(gè)體在一個(gè)蜜源附近經(jīng)過(guò)Limit次的搜索都沒(méi)有更新蜜源時(shí)，則放棄該食物源，并記錄其適應(yīng)度值，隨即變成偵查蜂去尋找新的食物源。

1.2 ABC算法步驟

(1)問(wèn)題的初始化

蜜蜂尋找食物源的過(guò)程就是尋優(yōu)問(wèn)題找最優(yōu)解的過(guò)程。首先算法隨機(jī)生成一個(gè)初始種群，這個(gè)初始種群中包含N個(gè)可行解，解的數(shù)量和引領(lǐng)蜂的數(shù)目相等。每個(gè)解xi(i=1,2,…N)用一個(gè)D維向量xi(xi1,xi2,…xiN)來(lái)表示。D指待解決問(wèn)題的參數(shù)的個(gè)數(shù)，即問(wèn)題的維數(shù)。初始解的生成引入一個(gè)隨機(jī)參數(shù)，按照式1生成。

式中d∈(1,2,…N)，xid.min和xid.max分別是xid的上限和下限：rand為隨機(jī)生成的在（0，1）之間均勻分布的隨機(jī)數(shù)。

利用下式計(jì)算各蜜源的質(zhì)量（適應(yīng)度值）：

式中fit(xi)表示第i個(gè)食物源xi的蜜源質(zhì)量，即第i個(gè)解的適應(yīng)度值，f(xi)表示該點(diǎn)對(duì)應(yīng)的目標(biāo)函數(shù)值。

(2)引領(lǐng)蜂搜索

引領(lǐng)蜂會(huì)在每個(gè)食物源周?chē)M(jìn)行搜索，按照“貪婪算法”的思想進(jìn)行優(yōu)勝劣汰，在搜索次數(shù)未達(dá)到預(yù)定的次數(shù)之前，一直循環(huán)進(jìn)行。ABC算法對(duì)食物源xi的鄰域進(jìn)行搜索，依據(jù)式（2）產(chǎn)生新的食物源vi(vi1,vi2,…viN)。

式中，q為[1,N]間的隨機(jī)整數(shù)，且q≠i，即根據(jù)上式生成新的蜜源xq=(xq1,xq2,…xqD)，且xq與xi不同，drand為[1,N]之間的隨機(jī)整數(shù)，rid∈[-1,1]是一個(gè)-1到1之間的隨機(jī)整數(shù)，用來(lái)控制引領(lǐng)蜂鄰域搜索范圍。

由式(2)可以看出，隨著xid和xqd的差值逐漸減小，新位置的產(chǎn)生的波動(dòng)也越來(lái)越小，隨著循環(huán)的進(jìn)行，搜索會(huì)漸漸接近最優(yōu)解，xid-xqd會(huì)自適應(yīng)的減少，因此算法具有自適應(yīng)的收斂性。

(3)跟隨蜂的搜索

當(dāng)引領(lǐng)蜂完成搜索后，會(huì)記下蜜源相關(guān)信息(質(zhì)量、方向、距離等)飛回蜂巢，在特定區(qū)域以“8”字舞或“搖擺”舞或其它方式向跟隨蜂傳遞蜜源信息。跟隨蜂以輪盤(pán)賭的方式選擇蜜源，質(zhì)量好且距離近的蜜源會(huì)招募到較多的跟隨蜂，蜜源i被跟隨蜂選中的概率p(xi)依據(jù)式（3）產(chǎn)生。

跟隨蜂根據(jù)引領(lǐng)蜂所傳達(dá)的信息到達(dá)所選擇的蜜源位置后，在蜜源周?chē)檬?2)進(jìn)行鄰域搜索，和引領(lǐng)蜂一樣利用“貪婪算法”優(yōu)勝劣汰進(jìn)行選擇。

(4)引領(lǐng)蜂和偵查蜂的轉(zhuǎn)換

引領(lǐng)蜂根據(jù)“貪婪算法”選擇后，如果經(jīng)過(guò)Limit次后都沒(méi)有更新蜜源，表明在當(dāng)前鄰域中所選擇的蜜源已經(jīng)是質(zhì)量最好的，即當(dāng)前解是局部最優(yōu)解，從算法的角度講，算法已陷入局部最優(yōu)，該蜜源應(yīng)該被放棄。此時(shí)，引領(lǐng)蜂轉(zhuǎn)換成偵查蜂，算法根據(jù)式(1)重新生成新的蜜源。找到蜜源后偵查蜂又重新變成引領(lǐng)蜂，重復(fù)算法搜索過(guò)程。

(5)結(jié)束

如果搜索達(dá)到預(yù)先設(shè)定好的循環(huán)最大次數(shù)，或是根據(jù)所求問(wèn)題精度需要，達(dá)到程序結(jié)束條件，則算法結(jié)束，完成搜索。

2 算法的改進(jìn)

ABC算法存在問(wèn)題的根本原因在于在后期無(wú)法保持群體的多樣性，偵查蜂在尋找新的密源時(shí)，是采用0～1之間的一個(gè)隨機(jī)數(shù)來(lái)調(diào)配“貪婪算法”，群體活動(dòng)趨于統(tǒng)一，并且在尋找到局部最優(yōu)解后無(wú)法快速向全局最優(yōu)解前進(jìn)，開(kāi)采能力不足，算法很容易陷入局部最優(yōu)。為此很多研究者采取了多種優(yōu)化方法，并取得了一定的成績(jī)。文獻(xiàn)[8]加入局部搜索算子，對(duì)當(dāng)前的最優(yōu)蜜源進(jìn)行局部搜索，以改進(jìn)算法易早熟的缺點(diǎn)。文獻(xiàn)[9]提出一種動(dòng)態(tài)調(diào)整子種群個(gè)體數(shù)目，以增強(qiáng)其局部搜索能力。文獻(xiàn)[10]在算法中引入一維正態(tài)云模型和新的概率選擇策略來(lái)提高算法的后期搜索能力。

本文在前人研究的基礎(chǔ)上，將符合自然界中飛行物種實(shí)際覓食習(xí)慣的Lévy飛行引入到算法中。研究表明很多動(dòng)物和昆蟲(chóng)的覓食行為具有萊維飛行的典型特征[11]，目前，這種行為己經(jīng)被運(yùn)用到優(yōu)化和優(yōu)化探索方面[12]。在引領(lǐng)蜂經(jīng)過(guò)Limit次搜索沒(méi)有發(fā)現(xiàn)比當(dāng)前蜜源質(zhì)量更好的蜜源時(shí)，便和偵查蜂轉(zhuǎn)換，此時(shí)采用Lévy（萊維）分布來(lái)代替隨機(jī)分布如式（4）所示。Lévy分布其實(shí)是隨機(jī)點(diǎn)分布的一種形式，在這種分布中，短距離的點(diǎn)分布與長(zhǎng)距離的運(yùn)動(dòng)線之間相互參雜，研究表明Lévy對(duì)群體協(xié)作又相互獨(dú)立的覓食者來(lái)說(shuō)，是最理想的尋找策略。Reynolds等人對(duì)蜜蜂和果蠅覓食軌跡進(jìn)行觀察，發(fā)現(xiàn)其飛行軌跡中也呈現(xiàn)出Lévy Flight特征[13-14]

改進(jìn)后算法的流程圖如圖1所示：

圖1 改進(jìn)算法的流程圖

3 實(shí)驗(yàn)仿真

3.1 測(cè)試函數(shù)

為了驗(yàn)證改進(jìn)的人工蜂群算法在實(shí)際的尋優(yōu)過(guò)程中的有效性，選取5個(gè)常用的測(cè)試函數(shù)進(jìn)行測(cè)試，并將改進(jìn)的蜂群算法(LABC)和原算法(ABC)進(jìn)行比較，這5個(gè)測(cè)試函數(shù)有兩個(gè)單蜂函數(shù)和3個(gè)多峰函數(shù)組成，可以有效測(cè)試算法的尋優(yōu)能力和抗干擾能力,見(jiàn)表1，仿真數(shù)據(jù)以最優(yōu)值，最劣值，平均值和收斂性表示，收斂性=(最劣值-最優(yōu)值)/平均值，可以反應(yīng)算法的收斂速度。

表1 測(cè)試函數(shù)

3.2 仿真結(jié)果與分析

表2為仿真的結(jié)果。圖2～6為改進(jìn)算法對(duì)5個(gè)測(cè)試函數(shù)的求解變化趨勢(shì)，其中，函數(shù)F1、F3為迭代次數(shù)為2000，D=60時(shí)的仿真效果，F(xiàn)2、F4、F5設(shè)置迭代次數(shù)為2000，D=30，每個(gè)函數(shù)的效果圖都是50次優(yōu)化平均得到的結(jié)果。

表2 兩種算法的性能比較

圖2 F1函數(shù)

圖3 F2函數(shù)

圖4 F3函數(shù)

圖5 F4函數(shù)

圖6 F5函數(shù)

從仿真的結(jié)果可以看出，基于Lévy分布的人工蜂群算法與ABC相比，在收斂速度和尋優(yōu)速度上都有所提高。

4 結(jié)束語(yǔ)

在當(dāng)今科學(xué)研究領(lǐng)域，多學(xué)科相互交叉，相互滲透是現(xiàn)代科學(xué)技術(shù)發(fā)展的顯著特點(diǎn)之一，各種仿生智能算法也越來(lái)越多的和其它理論結(jié)合起來(lái)以提高其優(yōu)化效果。人工蜂群算法由于算法簡(jiǎn)潔，參數(shù)較少而在近年來(lái)受到廣泛關(guān)注，但它和重多的仿生智能算法一樣，容易墜入局部最優(yōu)而放棄全局最優(yōu)值，后期開(kāi)采能力弱。本文將更符合昆蟲(chóng)覓食實(shí)際運(yùn)動(dòng)行為軌跡的Lévy分布加入到人工蜂群算法中，有效提高了算法的收斂速度、優(yōu)化速度和算法的運(yùn)行效率。

[1]KARABOGA D.An Idea Based On Honey Bee Swarm for Numerical Optimization[R].Turkey：Erciyes University,2005.

[2]PARK,J Y,HAN S Y.Swarm Intelligence Topology Optimization Based on Artificial Bee Colony Algorithm[J].International Journal of Precision Engineeringand Manufacturing,2013,14(1)：115-121.

[3]XU Y F,FAN P.A Simple and Efficient Artificial Bee Colony Algorithm[J].Mathematical Problems in Engineering,2013.

[4]BANSAL,J C,SHARMA H.Memetic search in artificial bee colony algorithm[J].Soft Computing,2013,17(10)：1911-1928.

[5]KASHAN M H,NAHAVANDI N.DisABC：A new artificial bee colony algorithm for binary optimization[J].Applied Soft Computing,2012,12(1)：342-352.

[6]KARABOGA N,CETINKAYA M B.A novel and efficient algorithm for adaptive filtering：Artificial bee colony algorithm[J].Turkish Journal of Electrical Engineering and Computer Sciences,2011,19(1)：175-190.

[7]SPRINGER X S,YANG.Firefly Algorithm,Levy Flights and Global Optimization[M].Research and Development in Intelligent Systems XXVI：Berlin,209-218.

[8]劉三陽(yáng),張平,朱明敏.基于局部搜索的人工蜂群算法[J].控制與決策，2014，15(1)：123-128.

[9]龍文,趙東泉,徐松金,等.子種群個(gè)體動(dòng)態(tài)調(diào)整的人工蜂群算法[J].蘭州理工大學(xué)學(xué)報(bào)，2015，41(6)：93-98.

[10]李仁興,丁力.基于云模型蜂群算法的無(wú)人機(jī)航跡規(guī)劃[J].計(jì)算機(jī)科學(xué)，2015，42(11A)：89-92.

[11]PAVLYUKEVICH.Levy flights,non-local search and simulated annealing[J].Journal of Computational Physics，2007，226：1830-1844.

[12]SHLESINGER M.Search research[J].Nature，2006，443：281-282．

[13]LIU C,YE C M.Bat algorithm with the characteristics of Levy flights[J].CAAI Transactions on Intelli gent Systems,2013,8(1)：240-246.

[14]XIE J,ZHOU Y Q,CHEN H.A bat algorithm based on Levy flights trajectory[J].Pattern Recognition and Artificial Intelligence,2013,26(9)：829-837.

〔責(zé)任編輯 高海〕

An Artificial Bee Colony Algorithm Based on Lévy Flight

CHENG Xian-bao
(Guangzhou Collage of Technology and Business,Guangzhou Guangdong,510850)

The artificial bee colony algorithm in the later is easy to fall into local optimum,and the lack of ability to develop This paper proposed a kind of artificial bee colony algorithm based on Lévy flight,in the process of finding nectar,leading bees turn into scout bees,the introduction of Lévy distribution function to allocate raw some 0-1 random number in the greedy algorithm,which effectively increased the rationality of the algorithm.Finally,the improved algorithm and the original algorithm are compared with 5 effective test functions,and the results show that the algorithm based on Lévy distribution has significantly improved the convergence speed and the optimization speed.

ABC;optimization;Lévy distribution;simulation

TP301.6

A

1674-0874(2016)03-0012-05

2016-03-09

程憲寶(1978-)，男，山東菏澤人，碩士，講師，研究方向：智能計(jì)算及計(jì)算機(jī)應(yīng)用。