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

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

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

1 相關(guān)工作

1.1 基本人工蜂群算法

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

(1)

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

(1)雇傭蜂階段。每只雇傭蜂在對應(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]之間的隨機數(shù)；k是隨機選擇的一個食物源，且k≠i;j是隨機選擇的維數(shù)。

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

(3)

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

這里fi是第i個解的目標函數(shù)值。

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

1.2 改進的人工蜂群算法

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

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

(4)

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

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

(5)

式中，r1≠r2,r1與r2是{1,2,…,N}中隨機選擇的食物源序號。由于式(5)只有一個引導(dǎo)項φi,j(xr1,j-xr2,j)，因此避免了式(4)中的震蕩問題。同時，式(5)去掉了Xbest的引導(dǎo)，不易早熟。文獻[7]認為式(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個個體中隨機選擇的精英解, 0

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

(8)

式中，0

2 筆者提出的算法

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

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

(9)

(10)

(11)

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

)

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

3 實驗與分析

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

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

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

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

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

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

4 結(jié) 論

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