杜振鑫，劉廣鐘，趙學(xué)華

(1.韓山師范學(xué)院 計(jì)算機(jī)與信息工程學(xué)院，廣東 潮州 521041；2.上海海事大學(xué) 信息工程學(xué)院，上海 201306；3.深圳信息職業(yè)技術(shù)學(xué)院 數(shù)字媒體學(xué)院，廣東 深圳 518172)

進(jìn)化算法在解決復(fù)雜優(yōu)化問題方面具有較大優(yōu)勢(shì)，因此受到越來越多的關(guān)注。主要的進(jìn)化算法包括粒子群算法(Particle Swarm Optimization, PSO)[1]、差分進(jìn)化算法(Differential Evolution, DE)[2]、人工蜂群算法(Artificial Bee Colony, ABC)[3]等。人工蜂群算法結(jié)構(gòu)簡單，參數(shù)較少，相比其他進(jìn)化算法具有一定優(yōu)勢(shì)[3-8]，受到了大量的關(guān)注。但是，人工蜂群算法也存在一定的缺點(diǎn)。許多研究表明[4-8]，人工蜂群算法由于搜索公式中的鄰居選擇機(jī)制隨機(jī)性太強(qiáng)，導(dǎo)致人工蜂群算法擅長勘探而不擅長開采[5]。目前，多數(shù)算法采用全局最優(yōu)解來增強(qiáng)人工蜂群算法的開采能力，但是如果全局最優(yōu)解位于一個(gè)錯(cuò)誤的位置，將帶領(lǐng)整個(gè)種群陷入局部最優(yōu)解。另外，全局最優(yōu)解雖然是總體表現(xiàn)最好的解，卻未必在每個(gè)維度上都處于最好位置，而不同維度上的最好位置往往分散在不同的解中。因此，如何集成已有的種群信息，更準(zhǔn)確地估計(jì)理論最優(yōu)解的位置，從多個(gè)維度上快速接近理論最優(yōu)解，從而避免算法陷入局部最優(yōu)解，是一個(gè)值得研究的問題。筆者通過集成多個(gè)較好解的信息來構(gòu)造一個(gè)更加“正確”的集成最優(yōu)解，代替全局最優(yōu)解引導(dǎo)算法進(jìn)化，顯著地提高了算法的性能。

1 相關(guān)工作

1.1 基本人工蜂群算法

人工蜂群[5]包含雇傭蜂、觀察蜂和偵察蜂3類。假設(shè)在D維空間中，種群規(guī)模為2×N(雇傭蜂個(gè)數(shù)=觀察蜂個(gè)數(shù)=N)，蜜源與雇傭蜂一一對(duì)應(yīng)。第i個(gè)蜜源的位置記為Xi=(Xi,1,Xi,2,…,Xi,D),代表搜索空間中的一個(gè)候選解，i=1,…,N，D是待優(yōu)化問題的維數(shù)。按照下式生成N個(gè)初始解：

(1)

人工蜂群算法可分3個(gè)階段循環(huán)搜索：

(1)雇傭蜂階段。每只雇傭蜂在對(duì)應(yīng)的食物源Xi處根據(jù)式(2)生成候選解Vi=(Vi,1,Vi,2,…,Vi,D)。若f(Vi)

Vi,j=Xi,j+φi,j(Xi,j-Xk,j) ，

(2)

式中，φi,j是[-1,1]之間的隨機(jī)數(shù)；k是隨機(jī)選擇的一個(gè)食物源，且k≠i;j是隨機(jī)選擇的維數(shù)。

(2)觀察蜂階段。雇傭蜂完成勘探之后，觀察蜂按照下面的概率隨機(jī)選擇一個(gè)食物源i進(jìn)一步開采：

(3)

式中，F(xiàn)i是食物源Xi的適應(yīng)度值。根據(jù)式(3)，食物源的適應(yīng)值越大，被觀察蜂選中的概率越高。式(3)中，

這里fi是第i個(gè)解的目標(biāo)函數(shù)值。

(3)偵察蜂階段。對(duì)每輪循環(huán)選擇搜索失敗次數(shù)最大且超過l次的食物源Xi，用式(1)隨機(jī)初始化。

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

Zhu[4]受到粒子群算法的啟發(fā)，通過引入全局最優(yōu)解Xbest項(xiàng)，提出一種改進(jìn)公式：

Vi,j=Xi,j+φi,j·(Xi,j-Xk,j)+ψi,j·(Xbest,j-Xi,j) ,

(4)

式中，ψi,j是[0,1.5]之間的隨機(jī)數(shù)，Xbest是全局最優(yōu)解。 文獻(xiàn)[6]指出：式(4)右邊兩項(xiàng)可能位于相反的方向，容易導(dǎo)致算法震蕩。因此，提出改進(jìn)公式：

Vi,j=Xr1,j+φi,j·(Xr1,j-Xr2,j) ,

(5)

式中，r1≠r2,r1與r2是{1,2,…,N}中隨機(jī)選擇的食物源序號(hào)。由于式(5)只有一個(gè)引導(dǎo)項(xiàng)φi,j(xr1,j-xr2,j)，因此避免了式(4)中的震蕩問題。同時(shí)，式(5)去掉了Xbest的引導(dǎo)，不易早熟。文獻(xiàn)[7]認(rèn)為式(5)中全局最優(yōu)解未得到利用，提出一種精英人工蜂群算法 (Depth FirSt and elite-guided ABC, DFSABC_elite),重新引入全局最優(yōu)解Xbest，并通過精英解平衡全局最優(yōu)解的引導(dǎo)作用：

Vi,j=Xe,j+φi,j·(Xe,j-Xk,j) ,

(6)

(7)

式(6)用于雇傭蜂階段，式(7)用于觀察蜂階段。Xe是從種群最好的p×N個(gè)個(gè)體中隨機(jī)選擇的精英解, 0

文獻(xiàn)[8]提出一種改進(jìn)的算法 (Modified GABC, MGABC)：

(8)

式中，0

2 筆者提出的算法

全局最優(yōu)解的使用，是增強(qiáng)進(jìn)化算法開采能力、加速收斂最重要的途徑之一[5]。但由于全局最優(yōu)解僅是算法當(dāng)前發(fā)現(xiàn)的最優(yōu)解，如果全局最優(yōu)解本身處于一個(gè)錯(cuò)誤位置，容易帶領(lǐng)整個(gè)算法陷入局部最優(yōu)解，因此僅使用全局最優(yōu)解的單一引導(dǎo)，容易導(dǎo)致算法早熟。為此，人們提出了大量改進(jìn)算法。在粒子群算法領(lǐng)域，2016年提出的動(dòng)態(tài)指導(dǎo)粒子群[1]按照一定概率向全局最優(yōu)解學(xué)習(xí)，既利用了全局最優(yōu)解的信息，也抑制了早熟問題。2017年提出的改進(jìn)粒子群[9]對(duì)全局最優(yōu)解施加擾動(dòng)以免早熟。2017年，文獻(xiàn)[10]在差分算法中引入全局最優(yōu)解，通過提取多個(gè)解的信息抑制早熟。在人工蜂群算法領(lǐng)域，式(4)最早采用全局最優(yōu)解來增強(qiáng)算法的開采能力[4]；式(5)去掉了全局最優(yōu)解引導(dǎo)，抑制了早熟問題。DFSABC_elite[7]通過精英解弱化全局最優(yōu)解的引導(dǎo)，而MGABC[8]則按一定概率使用全局最優(yōu)解抑制早熟。

受到文獻(xiàn)[10]的啟發(fā)，假設(shè)待優(yōu)化問題是求最小值。對(duì)于當(dāng)前種群中待更新的第i個(gè)個(gè)體Xi，首先對(duì)當(dāng)前種群X按照函數(shù)值從好到壞排序[10]，排序后的種群稱為R.按式(9)求得種群X中待更新個(gè)體i在搜索公式中使用的集成最優(yōu)解(ensemble best, ebest),用集成最優(yōu)解Xebest代替原來搜索公式中的全局最優(yōu)解Xbest。

(9)

(10)

(11)

圖1 集成學(xué)習(xí)原理(種群規(guī)模N=5，待更新個(gè)體i=5)

)

對(duì)于嵌入集成學(xué)習(xí)框架的MGABC_EL，需要增加一個(gè)額外的排序操作，增加的排序操作的復(fù)雜度是O(N·log(N))。 由于MGABC的計(jì)算復(fù)雜度為O(D·N)[8],則MGABC_EL的復(fù)雜度是O(N·log(N)+D·N)。因?yàn)镈一般遠(yuǎn)大于log(N),所以O(shè)(N·log(N)+D·N)可以簡化為O(D·N)。因此，MGABC_EL與MGABC復(fù)雜度相同?？梢娂尤爰蓪W(xué)習(xí)框架不會(huì)改變?cè)妓惴ǖ膹?fù)雜度。

3 實(shí)驗(yàn)與分析

為了測試集成學(xué)習(xí)框架的有效性，限于篇幅，在MGABC[8], DFSABC_elite[7], MGBDE[2]與SRPSO[11]這4種性能較高且較新的算法上進(jìn)行了測試。4種進(jìn)化算法都采用全局最優(yōu)解引導(dǎo)算法進(jìn)化，其中SRPSO是最近提出的改進(jìn)粒子群算法；MGBDE是著名的高斯骨干差分進(jìn)化算法，具有無參數(shù)特性及較高的性能。嵌入集成學(xué)習(xí)框架的4種算法分別稱為MGABC_EL, DFSABC_elite_EL， MGBDE_EL， SRPSO_EL。測試函數(shù)的定義、函數(shù)名稱、搜索范圍及理論最優(yōu)解見文獻(xiàn)[7]。其中，函數(shù)f1～f8是單峰函數(shù)；f9是帶噪聲的函數(shù)；f10是Rosenbrock函數(shù)，當(dāng)測試維數(shù)D>2時(shí)，是多峰函數(shù)[7]；f11～f22是多峰函數(shù)。表1用于測試集成學(xué)習(xí)框架是否可以增強(qiáng)人工蜂群算法的性能，測試函數(shù)的維數(shù)D=50，所有人工蜂群算法的種群規(guī)模按照文獻(xiàn)[7]設(shè)置，即種群規(guī)模N=50。按照文獻(xiàn)[7]的建議，算法最大評(píng)價(jià)次數(shù)M=5 000·D。其余參數(shù)設(shè)置均參照相應(yīng)算法的原始文獻(xiàn)設(shè)置。表2用于測試集成學(xué)習(xí)框架是否可以增強(qiáng)差分、粒子群算法的性能，種群規(guī)模同樣取50，其余參數(shù)均按照原始文獻(xiàn)設(shè)置。測試在同樣條件下重復(fù)30次。 其中，Mean表示平均結(jié)果，反映了算法在給定最大評(píng)價(jià)次數(shù)時(shí)的求解精度；std表示標(biāo)準(zhǔn)差，反映了算法的穩(wěn)定性。 表1與表2給出了非參數(shù)統(tǒng)計(jì)[12]的結(jié)果，顯著性水平為0.05。表中的符號(hào)“+”“=”“-”分別表示嵌入集成學(xué)習(xí)框架的算法好于、等于、差于相應(yīng)的原始算法。

表1 利用集成學(xué)習(xí)框架增強(qiáng)其他人工蜂群算法變種的實(shí)驗(yàn)結(jié)果(D=50,N=50)

根據(jù)表1，嵌入集成學(xué)習(xí)框架的MGABC_EL在除f14之外的21個(gè)函數(shù)上明顯好于MGABC。同樣，嵌入集成學(xué)習(xí)框架的DFSABC_elite_EL在除了f22之外的所有其他函數(shù)上都好于DFSABC_elite。實(shí)驗(yàn)結(jié)果表明，由于集成框架采用集成最優(yōu)解帶領(lǐng)算法進(jìn)化，集成了多個(gè)較好解的信息，弱化了全局最優(yōu)解的引導(dǎo)作用，從而抑制了早熟收斂，因此集成最優(yōu)解能夠帶領(lǐng)整個(gè)種群搜索更有希望的方向，明顯提高算法的性能。另外，集成學(xué)習(xí)框架對(duì)不同算法的提高幅度是不同的，例如在表1的實(shí)驗(yàn)結(jié)果中，MGABC_EL大幅度提高了MGABC的性能，而DFSABC_elite_EL對(duì)DFSABC_elite的提高幅度小一些。這主要是由于在MGABC中，在雇傭蜂階段與觀察蜂階段都使用全局最優(yōu)解引導(dǎo)，全局最優(yōu)解的作用較大，因此集成學(xué)習(xí)框架可以很好地幫助MGABC抑制早熟收斂。而DFSABC_elite僅在觀察蜂階段使用全局最優(yōu)解引導(dǎo)，全局最優(yōu)解的作用小一些，且DFSABC_elite本身已經(jīng)好于大量優(yōu)秀算法[7],進(jìn)一步提高性能的難度較大。但總體而言，集成學(xué)習(xí)框架仍能明顯提高DFSABC_elite的性能。表1的最后一列給出了最新提出的高性能的改進(jìn)算法ABCLGII[13]的實(shí)驗(yàn)結(jié)果。可以看出，嵌入集成學(xué)習(xí)框架的DFSABC_elite_EL雖然稍差于ABCLGII(兩者分別有6個(gè)、7個(gè)函數(shù)好于對(duì)方)，但是集成學(xué)習(xí)框架具有更好的推廣能力。表2給出了利用集成學(xué)習(xí)框架增強(qiáng)新提出的MGBDE[2]、SRPSO[11]算法性能的實(shí)驗(yàn)結(jié)果，可以看出，集成學(xué)習(xí)框架可以有效地提高全局最優(yōu)解引導(dǎo)的差分進(jìn)化算法與粒子群算法的性能。

表2 D=30時(shí)，利用集成學(xué)習(xí)框架增強(qiáng)差分、粒子群算法的實(shí)驗(yàn)結(jié)果

根據(jù)式(9)，個(gè)體i的集成最優(yōu)解由i在排序種群R中的排序序號(hào)si與好于i的解在排序種群中的序號(hào)k決定。當(dāng)種群規(guī)模N變大時(shí)，由于較差解的排序序號(hào)si較大，因此好于i的較好解較多，會(huì)造成較好解在集成最優(yōu)解中的權(quán)重下降。為了考查這一影響，表3給出了當(dāng)種群規(guī)模N=100時(shí)的實(shí)驗(yàn)結(jié)果，其余參數(shù)與表1相同。對(duì)比表3與表1可以發(fā)現(xiàn)，在表3中嵌入集成學(xué)習(xí)框架的改進(jìn)算法MGABC_EL與DFSABC_elite_EL相對(duì)于MGABC、DFSABC_elite的優(yōu)勢(shì)不如表1大。造成優(yōu)勢(shì)下降的主要原因是當(dāng)種群規(guī)模N增大時(shí)，函數(shù)值靠后的個(gè)體使用的集成最優(yōu)解中全局最優(yōu)解等好解的權(quán)重下降，因此算法收斂速度受到影響。但是根據(jù)表3，集成學(xué)習(xí)框架仍能明顯增強(qiáng)MGABC與DFSABC_elite的性能。

表3 利用集成學(xué)習(xí)框架增強(qiáng)其他人工蜂群算法變種的實(shí)驗(yàn)結(jié)果(D=50,N=100)

4 結(jié) 論

為了抑制傳統(tǒng)人工蜂群算法中全局最優(yōu)解引導(dǎo)導(dǎo)致的早熟問題，提出一種集成學(xué)習(xí)框架。該框架通過集成多個(gè)較好解的信息抑制早熟收斂，且容易實(shí)施，可以嵌入其他全局最優(yōu)解引導(dǎo)的人工蜂群、差分及粒子群算法，顯著增強(qiáng)這些算法的性能，而沒有增加這些算法的計(jì)算復(fù)雜度。