基于一致分布佳點(diǎn)集改進(jìn)的交叉人工蜂群算法

張平華,賈萬祥,程曉蕾

(1.合肥職業(yè)技術(shù)學(xué)院，安徽 合肥 230000；2.萬博科技職業(yè)學(xué)院，安徽 合肥 230000)

近年來，國內(nèi)外的研究學(xué)者對基于智能優(yōu)化規(guī)則的啟發(fā)式算法做了大量的研究，各種不同的先進(jìn)智能的仿生群智能算法不斷出現(xiàn)(如魚群算法、蛙跳算法、禁忌搜索算法、遺傳算法、蟻群算法、粒子群算法等)，并被逐步應(yīng)用到組合優(yōu)化和資源高度等各方面的問題求解中。仿生群智能是指眾多簡單的個體通過相互協(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)良蜜源的人工蜂群算法(artificial bee colony，ABC)[5]等。

人工蜂群算法[6]是由土耳其Erciyes大學(xué)的Karaboga教授在美國Virginia Tech大學(xué)的Teodorovic的蜂群優(yōu)化(bee colony optimization,BCO)和英國Cambridge大學(xué)的Yang等的一種虛擬蜜蜂(virtual bee algorithm，VBA)算法的研究基礎(chǔ)上，于2005年在一份內(nèi)部技術(shù)報(bào)告中系統(tǒng)地提出的一種新型群智能優(yōu)化算法。在組合優(yōu)化方面已經(jīng)被證實(shí)比上述的智能算法具有更優(yōu)越的性能[7]。G.Zhu和S.Kwong[8]優(yōu)化了蜜源產(chǎn)生位置的規(guī)則，在ABC算法中引入全局最優(yōu)，提高了算法的開發(fā)能力；王偉[9]將遺傳算法的交叉算子引入了ABC算法中，提出了一種基于交叉算子的改進(jìn)人工蜂群算法(MABC)，提高了算法的局部搜索能力，加快了收斂速度；在DE算法的變異策略啟發(fā)下，W.Gao[10]等通過產(chǎn)生候選蜜源位置，改進(jìn)了蜂群對蜜源的搜索能力，提出了CABC算法；劉三陽[11]等引入局部搜索算子，利用隨機(jī)局部搜索算子對當(dāng)前最優(yōu)進(jìn)行局部搜索，以加快算法的收斂速度；B.Akay[12]等通過控制擾動頻率來加快算法的收斂速度。

針對算法后期收斂速度慢、易于陷入局部極值的問題，結(jié)合數(shù)論和交叉方法提出了一種基于一致分布佳點(diǎn)集改進(jìn)的交叉人工蜂群算法。通過一致分布佳點(diǎn)集對算法種群的初始化進(jìn)行改進(jìn)，以維持種群的均勻分布和多樣性，提高了收斂速度及精度；在全局最優(yōu)的基礎(chǔ)上引入交叉系數(shù)，通過交叉方式進(jìn)行迭代更新位置，增強(qiáng)全局尋優(yōu)能力，有效地避免算法陷入局部最優(yōu)，提高優(yōu)化能力。

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

1.1 人工蜂群算法概述

依據(jù)文獻(xiàn)[6]中的描述，ABC算法主要由4個基本組成元素：食物源(蜜源，food source)、引領(lǐng)蜂(又稱采蜜蜂或雇傭蜂，employed forager，EF)、跟隨蜂(又稱觀察蜂onlooker，或非雇傭蜂unemployed forager，UF)、偵察蜂(scout)。其中引領(lǐng)蜂和跟隨蜂用來開采蜜源,即尋找最優(yōu)解,而偵查蜂用來觀察是否陷入局部最優(yōu)[13]；兩種基本的智能行為模式：(1)招募行為(recruit)：采蜜蜂在蜂巢跳舞區(qū)傳遞蜜源信息，招募待工蜂(觀察蜂)；(2)放棄(abandon)行為：某個食物源被持續(xù)開采極限(limit)次后，采蜜蜂放棄該蜜源成為偵察蜂。

1.2 ABC算法框架描述

根據(jù)求解組合優(yōu)化問題的分析，可以建立ABC算法的進(jìn)行求解智能優(yōu)化問題的數(shù)學(xué)模型：

minf(x);x=(x1,x2,…,xD)∈G

(1)

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

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

1.2.1 初始化(initialization)階段

初始化人工蜂群的規(guī)模(SN)、最大迭代次數(shù)(maxCycle)、最大開采次數(shù)(limit)；初始化SN/2個D維的可行解Xi=(Xi1,Xi2,…,XiD)T(i=1,2,…,SN):

(2)

1.2.2 引領(lǐng)蜂階段

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

(3)

其中，f(xi)為待優(yōu)化的函數(shù)，fitness(xi)為函數(shù)的適應(yīng)度值。

1.2.3 跟隨蜂階段

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

(4)

1.2.4 偵察蜂階段

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

2 改進(jìn)的人工蜂群算法

人工蜂群算法求解問題時，主要利用種群的智能迭代搜索解空間，對食物源初始化采用隨機(jī)分布方式，這可能導(dǎo)致部分初始解過于集中或重合，經(jīng)多次實(shí)驗(yàn)證明種群的初始化的程序影響著算法的收斂速度和解的質(zhì)量。隨機(jī)點(diǎn)分布如圖1所示。

圖1 二維隨機(jī)點(diǎn)分布 圖2 一致均勻佳點(diǎn)分布

2.1 基于佳點(diǎn)集的種群初始化

對一個未知的分布，采用隨機(jī)方法(RAND)取點(diǎn)法時，偏差一般是O(n(1-/2))，由華羅庚等在文獻(xiàn)[14]中提出的具有“最佳一致分布的佳點(diǎn)集”的方法取點(diǎn)時，其偏差僅為O(n(-1+ε))，兩者相差102倍。由此可見，用佳點(diǎn)集方法比隨機(jī)方法偏差要小得多。即在相同取點(diǎn)個數(shù)的條件下，一致分布的佳點(diǎn)集序列要比隨機(jī)方法方式選取的點(diǎn)序列更均勻。若將S維歐式空間中的單位立方體GS上的佳點(diǎn)映射到求解空間，可以構(gòu)造出一個均勻取點(diǎn)方法，如圖2所示。

張鈴教授利用佳點(diǎn)集法選擇點(diǎn)比隨機(jī)選取點(diǎn)的偏差要小得多等理論對遺傳算法進(jìn)行了改進(jìn)，在算法的收斂性和解的精度方面均取得了非常優(yōu)越的效果。佳點(diǎn)的分布，不管取多少點(diǎn)多少次，其分布情況每次都是一致均勻的，而其他分布形式則不能達(dá)到這樣的效果。同時，傳統(tǒng)的蜂群算法在進(jìn)行算法優(yōu)化搜索過程中易陷入局部極值，在引入一致分布的佳點(diǎn)集理論進(jìn)行算法初始化后，使種群分布均勻，可有效避免陷入局部極值。

2.2 佳點(diǎn)集

設(shè)GS是S維歐式空間中的單位立方體，即〈x〉∈Gs，〈x〉=(x1,x2,…,xs)，其中0≤xi≤1,(i=1,2,…,s)。令γ∈GS，若點(diǎn)集

Pn(k)=({r1(k),r2(k),…,rs(k)}),k=1,2,…,n

(5)

有偏差

φ(n)=C(γ,ε)n(-1+ε)

(6)

(7)

rk={ek},1≤k≤s

(8)

則稱γ是佳點(diǎn)。其中，{an}表示an的小數(shù)部分。

2.3 一致分布

一致分布，又叫等分布，即數(shù)列{x(n)}在[0，1]上“等可能”分布，主要是為了研究小數(shù)的數(shù)字規(guī)律。其理論最早于1916年由H.Weyl在文獻(xiàn)[15]提出，具體定義如下：

(9)

則稱點(diǎn)集{Pn(k)}(0≤k≤n)存在φ(n)的偏差。

由華羅庚等在“數(shù)論在近似分析中的應(yīng)用”對鐘開萊、Kiefer定理的證明和文中的算法收斂性分析證明可知，一致分布的佳點(diǎn)集能夠加快算法收斂速度。本文利用式(8)構(gòu)造佳點(diǎn)集對人工蜂群算法進(jìn)行種群初始化的改進(jìn)，同時為了更好地提高算法的全局和局部搜索能力和種群的多樣性和變異更新能力，本文將遺傳算法中種群的交叉算子引入到全局最優(yōu)解引導(dǎo)的人工蜂群算法(global artificial bee colony,GABC)中，提出一種基于一致分布佳點(diǎn)集改進(jìn)的交叉人工蜂群算法(crossover of the global artificial bee colony,CGABC)。

2.4 交叉操作

在ABC算法中，算法的效率及收斂的關(guān)鍵是如何設(shè)計(jì)好適應(yīng)度函數(shù)、種群的更新過程和如何避免陷入局部最優(yōu)。在ABC算法中，引領(lǐng)蜂是在其領(lǐng)域中隨機(jī)選取一個食物源進(jìn)行迭代更新，這種方式更新得到的新食物源，在算法中不能保證它就是一個質(zhì)量較好的解，可能導(dǎo)致算法局部搜索能力的下降。

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

交叉操作常見方式有指數(shù)交叉和二項(xiàng)交叉兩種[17]。交叉操作是將選擇出的兩個個體作為父個體，將二者的部分碼值按位進(jìn)行交換。在交叉操作中，對于二項(xiàng)交叉，對每一個分量都隨機(jī)地產(chǎn)生一個0～1之間的隨機(jī)數(shù)rand，若rand

(10)

其中，交叉算子CR一般取值為0.3～0.6，β的取值在0～1.5。

為進(jìn)一步提高算法的探索和開發(fā)能力，在G.P.Zhu和S.Kwong等提出的CABC算法思想啟發(fā)下，通過全局引導(dǎo)來加快算法的收斂速度和算法搜索能力，具體領(lǐng)域搜索公式改變?nèi)缦拢?/p>

(11)

其中，β的取值在0～1.5；α∈[-1,1]的隨機(jī)值。

3 CGABC算法框架

基于一致均勻佳點(diǎn)集的全局交叉人工蜂群算法(GCABC)借鑒了DE算法的基本思想和Zhu Guopu和Kwong Sam等提出的CABC算法思想，在CABC的基礎(chǔ)上引入交叉算子，提高算法的種群多樣性和變異更新能力，達(dá)到提高算法的開發(fā)能力和整體尋優(yōu)能力效果。

CGABC算法步驟如下：

S1:算法各種參數(shù)和基于佳點(diǎn)集的種群初始化。

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

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

While(iter

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

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

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

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

End while

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

為進(jìn)一步驗(yàn)證算法的合理與先進(jìn)性，利用MATLAB 2013對下面的相關(guān)函數(shù)和工程設(shè)計(jì)問題進(jìn)行了模擬仿真。具體仿真設(shè)計(jì)中采用參數(shù)設(shè)置如下：蜂群大小BN=50，采蜜蜂數(shù)量=觀察蜂的數(shù)量=BN/2=25，所有優(yōu)化函數(shù)維度D=30，最大迭代次數(shù)maxCycle=3 000，最大開采次數(shù)limit=1 500，交叉系數(shù)CR=0.4。實(shí)驗(yàn)針對每個測試函數(shù)在上述參數(shù)設(shè)置下獨(dú)立運(yùn)行10次，記錄其最優(yōu)值、平均值、最劣值和標(biāo)準(zhǔn)差。

4.1 函數(shù)優(yōu)化仿真結(jié)果分析

為了充分測試CGABC的優(yōu)越性，對文獻(xiàn)[19]中的7個標(biāo)準(zhǔn)函數(shù)分別進(jìn)行實(shí)驗(yàn)仿真，并與標(biāo)準(zhǔn)ABC算法和全局ABC算法的實(shí)驗(yàn)結(jié)果進(jìn)行比較。7個標(biāo)準(zhǔn)測試函數(shù)如表1所示。

表1 測試函數(shù)

從表2中和圖3～9的尋優(yōu)收斂曲線圖可以直觀看出，不管是單模態(tài)還是多模態(tài)的函數(shù)，CGABC算法性能優(yōu)于標(biāo)準(zhǔn)ABC算法和GABC蜂群算法，它能更快速地收斂于最優(yōu)值點(diǎn)，效果有了明顯提升。標(biāo)準(zhǔn)ABC蜂群算法和GABC蜂群算法所得出的結(jié)果與CGABC算法計(jì)算的結(jié)果比較，無論在精度還是在方差上都比CGABC算法差，且有時候會陷入早熟收斂問題。而改進(jìn)后的蜂群算法有效地克服了標(biāo)準(zhǔn)蜂群算法的這些缺點(diǎn)。

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

圖3 Sphere函數(shù)收斂 圖4 Rosenbrock函數(shù)收斂 圖5 Schaffer函數(shù)收斂

圖6 Schwefel函數(shù)收斂 圖7 Ackley函數(shù)收斂 圖8 Rastrigin函數(shù)收斂

圖9 Griewank函數(shù)收斂

4.2 工程設(shè)計(jì)問題

為進(jìn)一步驗(yàn)證算法的可用性和正確性，選用了文獻(xiàn)[20]中的焊接梁設(shè)計(jì)(welded beam)，壓力容器設(shè)計(jì)(pressure vessel)，拉伸/壓縮彈簧設(shè)計(jì)(tension/compression spring)和減速器設(shè)計(jì)(speed reducer)4個工程問題(具體的工程細(xì)節(jié)描述和數(shù)學(xué)模型見參考文獻(xiàn)[20])。

表3中詳細(xì)列出了焊接梁設(shè)計(jì)、壓力容器設(shè)計(jì)、拉伸/壓縮彈簧設(shè)計(jì)和減速器設(shè)計(jì)4個工程問題的線性和非線性約束。表4可以明顯看出3種不同算法之間的區(qū)別，無論是在最優(yōu)值還是標(biāo)準(zhǔn)差方面本文的算法結(jié)果都比其他兩種改進(jìn)算法的結(jié)果更優(yōu)。

表3 各種問題的線性和非線性不等式約束數(shù)

表4 CGABC與GABC算法、ABC算法優(yōu)化4個標(biāo)準(zhǔn)工程問題的比較結(jié)果

5 結(jié) 論

人工蜂群算法是一種新型的群體智能優(yōu)化算法，其具有特定的優(yōu)化分工，采用貪婪選擇和協(xié)作機(jī)制，算法靈活，不依賴于問題的梯度，具有廣泛的適用性。本文對種群的初始化運(yùn)用一致均勻的設(shè)計(jì)方法，并在優(yōu)化過程中引入交叉算子對全局優(yōu)化算法進(jìn)行改進(jìn)。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的CGABC算法在優(yōu)化單模和多模問題時均有較好的表現(xiàn)，均能提前全局收斂于函數(shù)的最優(yōu)值，有效地平衡了算法的“局部開采”與“全局探測”能力，在一定程度上提高了算法的優(yōu)化能力。