基于交叉的全局人工蜂群算法的研究

張平華，李敬明，胡賢德，胡 俊

(1.安徽新華學(xué)院 信息工程學(xué)院，安徽 合肥 230088；2.合肥工業(yè)大學(xué) 管理學(xué)院，安徽 合肥 230009)

基于交叉的全局人工蜂群算法的研究

張平華1，李敬明2，胡賢德1，胡 俊1

(1.安徽新華學(xué)院 信息工程學(xué)院，安徽 合肥 230088；2.合肥工業(yè)大學(xué) 管理學(xué)院，安徽 合肥 230009)

人工蜂群(Artificial Bee Colony，ABC )算法在求解函數(shù)最優(yōu)值時(shí)，存在后期收斂速度慢、易于陷入局部最優(yōu)、疏于開發(fā)等問題.為了解決這些問題，對算法進(jìn)行了深入研究，結(jié)合其他仿生智能優(yōu)化算法的機(jī)制，提出了一種能有效提高收斂速度，增強(qiáng)算法開發(fā)性和全局尋優(yōu)能力，并能有效避免種群個(gè)體陷入局部最優(yōu)的算法——基于交叉的全局人工蜂群算法.選取7個(gè)標(biāo)準(zhǔn)測試函數(shù)進(jìn)行實(shí)驗(yàn)仿真，結(jié)果表明，與ABC算法、全局最優(yōu)人工蜂群算法(GABC)相比，基于交叉的全局人工蜂群算法(CGABC)的收斂速度及精度均有明顯提高.

智能算法；交叉；全局；人工蜂群算法

近年來，國內(nèi)外學(xué)者對基于智能優(yōu)化規(guī)則的啟發(fā)式算法做了大量的研究，各種先進(jìn)的、智能的仿生群智能算法不斷出現(xiàn)(如魚群算法、蛙跳算法、禁忌搜索算法、遺傳算法、蟻群算法、粒子群算法等)，并被逐步應(yīng)用到組合優(yōu)化和資源調(diào)度等各方面的問題求解中.仿生群智能是指眾多簡單的個(gè)體通過相互協(xié)同方式，表現(xiàn)出復(fù)雜的智能行為的過程和特性.群體智能算法主要有模擬螞蟻覓食行為的蟻群算法[1](Ant Colony Optimization，ACO)、源于鳥群覓食行為的粒子群算法[2](Particle Swarm Optimization，PSO)、模擬真實(shí)魚類覓食行為的人工魚群算法[3](Artificial Fish Swarm Algorithm，AFSA)、模擬自然界中螢火蟲成蟲發(fā)光的生物學(xué)特性的螢火蟲算法[4](Glowworm Swarm Optimization，GSO)以及模擬蜜蜂群體尋找優(yōu)良蜜源的人工蜂群算法[5](Artificial Bee Colony，ABC)等.

1 人工蜂群算法及計(jì)算框架

1.1 人工蜂群算法概述

在對蜜蜂群體采蜜行為進(jìn)行深入觀察和研究后，受蜜蜂行為的啟發(fā)，土耳其Erciyes大學(xué)的KARABOGA教授在一種虛擬蜜蜂(Virtual Bee Algorithm，簡稱VBA)算法的基礎(chǔ)上，于2005年在文獻(xiàn)[6]中系統(tǒng)地提出了一種新型群智能優(yōu)化算法——人工蜂群覓食優(yōu)化算法.

人工蜂群(簡稱ABC)算法在組合優(yōu)化方面已經(jīng)被證實(shí)比上述的智能算法具有更優(yōu)越的性能[7].但與其他群智能計(jì)算算法一樣，ABC算法也存在著缺乏全局最優(yōu)值的記錄和算法參與過程、后期收斂速度慢、易于陷入局部最優(yōu)、疏于開發(fā)等問題.ZHU等[8]優(yōu)化了蜜源產(chǎn)生位置的規(guī)則，在ABC算法中引入全局最優(yōu)，提高了算法的開發(fā)能力；王偉等[9]將遺傳算法的交叉算子引入了ABC算法中，提出了一種基于交叉算子的改進(jìn)人工蜂群算法(MABC)，提高了算法的局部搜索能力，加快了收斂速度；在DE算法的變異策略啟發(fā)下，GAO[10]等通過產(chǎn)生候選蜜源位置，改進(jìn)了蜂群對蜜源的搜索能力，提出了GABC算法；劉三陽[11]等引入局部搜索算子，利用隨機(jī)局部搜索算子對當(dāng)前最優(yōu)進(jìn)行局部搜索，加快了算法的收斂速度；AKAY[12]等通過控制擾動(dòng)頻率來加快算法的收斂速度.

本文針對以上不足，結(jié)合文獻(xiàn)[8]的優(yōu)點(diǎn)，在全局最優(yōu)的基礎(chǔ)上引入交叉系數(shù)，提高局部優(yōu)化能力，提出一種基于交叉的全局人工蜂群算法.

依據(jù)文獻(xiàn)[6]中的描述及搖擺舞(如圖1所示)和采蜜過程(如圖2所示)可知，ABC算法主要由4個(gè)基本組成元素：蜜源(食物源，F(xiàn)ood Sources)、引領(lǐng)蜂(又稱采蜜蜂或雇傭蜂，Employed Foragers，EF)、跟隨蜂(又稱觀察蜂Onlookers或非雇傭蜂，Unemployed Foragers，UF)、偵察蜂(Scouts).其中引領(lǐng)蜂和跟隨蜂用來開采蜜源, 即尋找最優(yōu)解, 而偵查蜂用來觀察是否陷入局部最優(yōu)[13]；兩種基本的智能行為模式為：(1)招募(Recruit)行為：采蜜蜂在蜂巢跳舞區(qū)傳遞蜜源信息，招募待工蜂(觀察蜂)；(2)放棄(Abandon)行為：某個(gè)食物源被持續(xù)開采極限(Limit)次后，采蜜蜂放棄該蜜源成為偵察蜂.

蜜源即待求解問題的可行解，在算法中用“適應(yīng)度”又稱“適應(yīng)值”來描述蜜源(可行解)質(zhì)量的好壞.

引領(lǐng)蜂也稱作雇傭蜂或采蜜蜂，在算法中其數(shù)量與已知的蜜源數(shù)量一致，占整個(gè)蜂群規(guī)模的一半.它具有記憶功能，存儲(chǔ)著蜜源的相關(guān)信息，它會(huì)將蜜源的相關(guān)信息在舞蹈區(qū)分享給觀察蜂(待工蜂)，并依據(jù)蜜源情況不斷更新自身位置選取更好的蜜源，提高了解的質(zhì)量.

圖1 搖擺舞

圖2 蜂群采蜜過程圖

偵察蜂主要在蜂巢周圍搜索潛在的食物源，一旦找到新的食物源，則變?yōu)楣蛡蚍浼床擅鄯?參考實(shí)驗(yàn)數(shù)據(jù)和文獻(xiàn)[6]，偵察蜂數(shù)量在算法中大約占蜂群數(shù)量的5%～20%；跟隨蜂占整個(gè)蜂群規(guī)模的一半，主要是在舞蹈區(qū)觀察引領(lǐng)蜂(雇傭蜂)的搖擺舞(如圖1所示)，按蜜源與適應(yīng)度值比例的概率，選擇自己認(rèn)為滿意的蜜蜂進(jìn)行跟隨.

招募行為：引領(lǐng)蜂在指定的區(qū)域內(nèi)隨機(jī)搜索新蜜源，并計(jì)算適應(yīng)度值大小，以此來判斷是否更新當(dāng)前的食物源，并存儲(chǔ)蜜源相關(guān)信息.引領(lǐng)蜂回到蜂巢跳舞區(qū)通過搖擺舞來傳遞蜜源信息給跟隨蜂，跟隨蜂采用貪婪算法并以一定的概率選擇一只引領(lǐng)蜂跟隨，成為引領(lǐng)蜂.

放棄(Abandon)行為：當(dāng)某個(gè)蜜源經(jīng)歷了Limit次迭代后仍沒有改進(jìn)時(shí)，則被強(qiáng)制放棄，其對應(yīng)的引領(lǐng)蜂轉(zhuǎn)變?yōu)閭刹榉?，重新隨機(jī)搜尋一個(gè)新的蜜源.

1.2 人工蜂群算法框架描述

根據(jù)求解組全優(yōu)化問題的分析，可以建立利用ABC算法求解智能優(yōu)化問題的數(shù)學(xué)模型，即

(1)

式中：D為優(yōu)化問題的維數(shù)；f(x)為優(yōu)化的目標(biāo)函數(shù)；G為可行解的解空間的(可以用上下界來表示，如[lb,ub]).

在ABC算法中，蜜源亦即優(yōu)化問題的解，通常用一個(gè)N維向量來表示；蜜源的優(yōu)劣用優(yōu)化函數(shù)的適應(yīng)度值來衡量.算法框架描述如下.

1.2.1 初始化階段

初始化人工蜂群的規(guī)模(SN)、最大迭代次數(shù)(maxCycle)、最大開采次數(shù)(limit)；初始化SN/2個(gè)D維的可行解xi(xi1,xi2,…,xiD)T(i=1,2,…，SN).

(2)

1.2.2 引領(lǐng)蜂階段

引領(lǐng)蜂依據(jù)(2)式進(jìn)行鄰域搜索，并采用貪婪算法或輪盤賭算法依據(jù)(3)式計(jì)算初始適應(yīng)度值(fitness(xi))，并按(4)式求出對蜜源選擇的概率.

(3)

式中：f(x)為待優(yōu)化的函數(shù)；fitness(xi)為函數(shù)的適應(yīng)度值.

f(x)通常是一個(gè)在實(shí)數(shù)域內(nèi)連續(xù)的函數(shù)，其值也是對應(yīng)于實(shí)數(shù)域中的適應(yīng)度值fitness(xi).從式(2)可以明顯看出，適應(yīng)度值fitness(xi)越大，對應(yīng)的目標(biāo)函數(shù)值就越小.因此，標(biāo)準(zhǔn)ABC算法中fitness(xi)的最大值，即對應(yīng)為求解式(1)的最小化問題.反之如果要求解優(yōu)化問題的最大值，只需求出適應(yīng)度值fitness(xi)的最小值.以上分析可用圖3所示的二維曲線圖[7]來描述.

圖3 目標(biāo)函數(shù)與適應(yīng)度轉(zhuǎn)化曲線圖

1.2.3 跟隨蜂階段

跟隨蜂依據(jù)(3)式計(jì)算跟隨概率Pi，搜索蜜源，并計(jì)算適應(yīng)度值，選擇相關(guān)蜜源.

(4)

1.2.4 偵察蜂階段

偵察蜂在其鄰域范圍內(nèi)隨機(jī)地搜索新的蜜源.當(dāng)蜜源經(jīng)過限定的最大開采次數(shù)(limit)后，如果仍然沒有改進(jìn)，則在此采蜜的引領(lǐng)蜂就放棄此蜜源，并變?yōu)閭刹榉?，從而重新?2)式隨機(jī)選取新的蜜源，產(chǎn)生新蜜源位置.

2 基于交叉的全局人工蜂群算法

2.1 交叉操作

在ABC算法中，算法的效率及收斂的關(guān)鍵是如何設(shè)計(jì)好適應(yīng)度函數(shù)、種群的更新過程和如何避免陷入局部最優(yōu).在ABC算法中，引領(lǐng)蜂從其阾域中隨機(jī)選取一個(gè)食物源進(jìn)行迭代更新，這種方式更新得到的新的食物源，在算法中不能保證它就是一個(gè)質(zhì)量較好的解，可能導(dǎo)致算法局部搜索能力的下降.為了更好地提高算法的全局和局部搜索能力，本文將遺傳算法中種群的交叉算子引入到GABC(全局最優(yōu)解引導(dǎo)的人工蜂群算法)算法中，提出一種基于交叉的全局人工蜂群算法(Crossover of the Global Artificial Bee Colony，CGABC).

交叉操作是將種群的父代個(gè)體基因中優(yōu)秀的基因遺傳給子代，通過配對方式進(jìn)行基因交換重組，重新結(jié)合成新個(gè)體，在一定程度上充分提高了蜂群的多樣性，提高了算法整體的優(yōu)化能力.

交叉操作常見的方式有指數(shù)交叉和二項(xiàng)交叉兩種[14].交叉操作是將選擇出的兩個(gè)個(gè)體作為父個(gè)體，將二者的部分碼值按位進(jìn)行交換.設(shè)有兩個(gè)8位個(gè)體P1和P2，如圖4所示.

圖4 P1，P2個(gè)體

現(xiàn)隨機(jī)產(chǎn)生一個(gè)在1到7之間的數(shù)c=3，則依據(jù)交叉原理可將P1和P2的低三位交換后，得到一個(gè)新的個(gè)體.其交換過程如圖5所示.

圖5 交叉操作示意圖

在交叉操作中，對于二項(xiàng)交叉，對每一個(gè)分量都隨機(jī)地產(chǎn)生一個(gè)0～l之間的隨機(jī)數(shù)rand，若rand

(5)

式中：交叉算子cr一般取值為0.3～0.6；β的取值在0～1.5.

為進(jìn)一步提高算法的探索和開發(fā)能力，在文獻(xiàn)[8]CABC算法思想啟發(fā)下，通過全局引導(dǎo)來加快算法的收斂速度和算法搜索能力，具體鄰域搜索公式改變?nèi)缦拢?/p>

k≠i

(6)

式中：β的取值在0～1.5；α∈[-1,1]之間的隨機(jī)值.

2.2 CGABC算法框架

基于交叉的全局人工蜂群算法(CGABC)借鑒了DE算法的基本思想和CABC算法的思想，在CABC的基礎(chǔ)上引入交叉算子[15]，提高了算法種群的多樣性和變異更新能力，達(dá)到了提高算法的開發(fā)能力和整體尋優(yōu)能力效果.算法流程圖如圖6所示.CGABC算法步驟如下：

S1:算法各種參數(shù)和種群的初始化；

S2: 引領(lǐng)蜂(采蜜蜂)依據(jù)(6)式進(jìn)行鄰域搜索，依據(jù)(3)式計(jì)算初始適應(yīng)度值(fitness(xi))并記錄全局最優(yōu)值(GlobalValue)和全局最優(yōu)解向量(GlobalMin)；

S3:進(jìn)入采蜜階段，引領(lǐng)蜂根據(jù)蜜源情況，采蜜蜂進(jìn)行鄰域搜索，依據(jù)(6)式更新食物源，產(chǎn)生新的候選位置，并進(jìn)行交叉操作.具體過程如下：

While(iter

采蜜蜂將鄰域搜索后的解與迭代產(chǎn)生的最優(yōu)解按(5)式進(jìn)行交叉操作，計(jì)算新的適應(yīng)度值，根據(jù)貪婪算法選擇更優(yōu)的蜜源.

按(4)式計(jì)算觀察蜂跟隨概率，并轉(zhuǎn)為采蜜蜂進(jìn)行鄰域搜索，然后按(5)式交叉操作，按照貪婪算法選擇新的蜜源，并保留全局最優(yōu)值；

偵察蜂隨機(jī)尋找新蜜源替換超過鄰域搜索限制次數(shù)的蜜源；

記錄全局最優(yōu)解；

End while

圖6 算法流程圖

3 數(shù)值實(shí)驗(yàn)仿真與分析

為了充分測試提出的基于交叉的全局人工蜂群(CGABC)算法的優(yōu)越性，在此選取了單模和多模函數(shù)共計(jì)7個(gè)(如表1所示)，分別進(jìn)行實(shí)驗(yàn)仿真，并與標(biāo)準(zhǔn)ABC算法和全局ABC算法的實(shí)驗(yàn)結(jié)果進(jìn)行比較.其中，只有Sphere 為單模態(tài)函數(shù)，其余都是多模態(tài)函數(shù)，它們的理論最優(yōu)值(最小值)都是0，在實(shí)驗(yàn)中，蜂群大小BN=50，采蜜蜂數(shù)量=觀察蜂的數(shù)量=BN/2=25，所有優(yōu)化函數(shù)維度D=30，最大迭代次數(shù)maxCycle=3 000，最大開采次數(shù)limit=300，交叉系數(shù)cr=0.3；實(shí)驗(yàn)針對每個(gè)測試函數(shù)在上述參數(shù)設(shè)置下獨(dú)立運(yùn)行10次，記錄其最優(yōu)值、平均值、最劣值和標(biāo)準(zhǔn)差.表2給出了CGABC算法、ABC算法和GABC算法對表1中的7個(gè)測試函數(shù)進(jìn)行仿真尋優(yōu)結(jié)果的比較.圖7～圖13為7個(gè)測試函數(shù)的優(yōu)化收斂比較圖.

表1 測試函數(shù)

編號(hào)函數(shù)名模式函數(shù)表達(dá)式取值范圍全局極小值F1Sphere單模fx()=∑Di=1x2i[-100,100]f0→()=0F2Rosenbrock多模fx()=∑D-1i=1100[(xi+1-x2i)2+(xi-1)2][-2.048,2.048]f1→()=0F3Schaffer多模fx()=0.5+sin2 ∑Di=1x2i()-0.5(1+0.001(∑Di=1x2i))2[-100,100]f0→()=0F4Schwefel多模fx()=D*418.9829-∑Di=1x2isin( xi)[-500,500]f420.96→()=0F5Ackley多模 fx()=-20e-0.2 1D∑Di=1x2i()-e1D∑Di=1cos2πxi()+20+e[-32,32]f0→()=0F6Rastrigin多模fx()=∑D-1i=1x2i[-10cos2πxi()+10][-5.12,5.12]f0→()=0F7Griewank多模fx()=14000∑Di=1x2i-∏Di=1cosxi i()+1[-600,600]f0→()=0

表2 測試函數(shù)優(yōu)化結(jié)果對比表

函數(shù)名算法全局極小值最劣值平均值標(biāo)準(zhǔn)差SphereABC4.55409×10-167.50686×10-165.72005×10-169.38136×10-17GABC2.63053×10-165.5108×10-165.0541×10-168.50722×10-17CGABC2.38339×10-163.28075×10-162.97085×10-162.65856×10-17RosenbrockABC0.1293804673.4995705431.2340769940.989323071GABC0.0029668641.7454077920.6157354010.613216816CGABC0.0585532680.4356478390.1964641660.109650872SchafferABC0.2276901410.3732906940.3404386050.045531083GABC0.1782223040.373290650.3036420660.051266344CGABC0.2727410960.3455094940.3097199320.032563777SchwefelABC0.0003818270.0003818270.0003818279.795557710-13GABC3.8182699×10-43.8182699×10-43.8182699×10-48.335656610-13CGABC3.8182699×10-43.8182699×10-43.8182699×10-40AckleyABC3.9968×10-144.35207×10-144.17444×10-141.77636×10-15GABC2.93099×10-144.35207×10-143.89022×10-144.21861×10-15CGABC2.930988×10-143.9968029×10-143.6415315×10-143.5527137×10-15RastriginABC05.68434×10-141.13687×10-142.27374×10-14GABC0000CGABC0000GriewankABC1.1102230×10-164.4408921×10-161.5543122×10-161.0175362×10-16GABC1.1102230×10-162.2204460×10-161.2212453×10-163.3306691×10-17CGABC1.1102230×10-161.1102230×10-161.1102230×10-160

圖7 Sphere函數(shù)收斂圖

圖 8 Rosenbrock函數(shù)收斂圖

圖9 Schaffer函數(shù)收斂圖

圖 10 Schwefel函數(shù)收斂圖

圖11 Ackley函數(shù)收斂圖

圖12 Rastrigin函數(shù)收斂圖

圖13 Griewank函數(shù)收斂圖

從表2和圖7～13的尋優(yōu)收斂曲線圖可以看出，不管是單模態(tài)還是多模態(tài)的函數(shù)，CGABC算法性能優(yōu)于標(biāo)準(zhǔn)ABC算法和GABC蜂群算法，它能更快速地收斂于最優(yōu)值點(diǎn)，效果有了明顯的提升.

4 結(jié)束語

人工蜂群算法是一種新型的群體智能優(yōu)化算法，因特有的勞動(dòng)分工、自組織、貪婪選擇和協(xié)作機(jī)制，算法靈活，不依賴于問題的梯度而具有廣泛的適用性.本文利用交叉算子對全局優(yōu)化算法進(jìn)行改進(jìn)，通過對函數(shù)的測試，表明該算法在求解多模態(tài)函數(shù)的全局優(yōu)化問題時(shí)，在收斂速度、優(yōu)化精度、收斂成功率和穩(wěn)定性等方面的性能更優(yōu)于標(biāo)準(zhǔn)人工蜂群算法.改進(jìn)后的算法可在多目標(biāo)優(yōu)化問題及相關(guān)工程領(lǐng)域廣泛應(yīng)用.

[1] COLORNI A, DORIGO M, MANIEZZO V. Distributed optimization by ant colonies[C]// Varela F J, Bourgine P. Proceedings of the First European Conference on Artificial Life. Second Printing Edition. Paris：Elsevier,1992:134-142.

[2] KENNEDY J. Particle Swarm Optimization[M]. New York: Spring US，2011:760-766.

[3] 李曉磊,邵之江,錢積新.一種基于動(dòng)物自治體的尋優(yōu)模式:魚群算法[J].系統(tǒng)工程理論與實(shí)踐，2002(11):32-38.

[4] KRISHNANAND K N, GHOSE D. Detection of multiple source locations using a glowworm metaphor with applications to collective robotics[C]// Symposium I S I .Proceedings 2005 IEEE Swarm Intelligence Symposium. Pasadena: IEEE,2005:84-91.

[5] KARABOGA D, BASTURK B. On the performance of artificial bee colony (ABC) algorithm[J]. Applied Soft Computing, 2008, 8(1): 687-697.

[6] KARABOGA D. An idea based on honey bee swarm for numerical optimization: Technical report-tr06[R].Kayseri: Erciyes University,2005.

[7]張偉. 人工蜂群混合優(yōu)化算法及應(yīng)用研究[D]. 杭州：浙江大學(xué), 2014.

[8]ZHU G, KWONG S. Gbest-guided artificial bee colony algorithm for numerical function optimization[J]. Applied Mathematics and Computation, 2010, 217(7): 3 166-3 173.

[9]王偉,龍文.基于交叉算子的改進(jìn)人工蜂群算法[J].蘭州理工大學(xué)學(xué)報(bào)，2015,41(1):101-106.

[10] GAO W, LIU S. A modified artificial bee colony algorithm[J]. Computers & Operations Research, 2012, 39(3): 687-697.

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

[12] AKAY B, KARABOGA D. A modified artificial bee colony algorithm for real-parameter optimization[J]. Information Sciences, 2012, 192: 120-142.

[13]寧愛平,張雪英.人工蜂群算法的收斂性分析[J].控制與決策，2013(10):1 554-1 558.

[14]喬艷霞,鄒書蓉,張洪偉.基于K-means的改進(jìn)差分進(jìn)化聚類算法[J].四川理工學(xué)院學(xué)報(bào)( 自然科學(xué)版)，2014,27(5):64-67.

[15] 邱劍鋒,謝娟,汪繼文.基于交叉突變算子的人工蜂群算法及其應(yīng)用[J].計(jì)算機(jī)應(yīng)用研究，2014(5):1 336-1 341.

(編輯：郝秀清)

Research on global artificial bee colony algorithm based on crossover

ZHANG Ping-hua1，LI Jing-ming2，HU Xian-de1，HU Jun1

(1.School of Information Engineering, Anhui Xinhua University, Hefei 230088, China;2.School of Management, Hefei University of Technology, Hefei 230009, China;)

The shortcomings of artificial bee colony algorithm include slow convergence speed，easily falling into local optimum value，neglect of development and other issues. In order to overcome these problems,referencing the mechanism of other bionic intelligent optimization algorithms, a new algorithm of global artificial bee colony algorithm based on crossover is proposed, which can effectively improve the convergence rate, enhance the development of the algorithm and the global optimization ability, and the algorithm can effectively avoid the local optimum. Finally,seven standard test functions are selected to carry out the experiment and simulation. The results show that the convergence speed and accuracy of the proposed algorithm (CGABC) are significantly improved compared with other algorithms such as ABC algorithm, GABC algorithm and so on.

intelligent algorithm; cross; global; artificial bee colony algorithm

2016-09-07

國家自然科學(xué)基金項(xiàng)目(71271071);安徽省自然科學(xué)基金項(xiàng)目(KJ2016A304，KJ2016A308)

張平華，男，zphpinganye@qq.com

1672-6197(2017)05-0006-06

TP301.6； TP18

A