基于差分變異算子的改進(jìn)人工蜂群算法

張怡森

摘? ?要：文章針對傳統(tǒng)人工蜂群算法收斂速度慢、精度不高的問題，基于差分進(jìn)化算法中的變異算子，對人工蜂群算法搜索方程進(jìn)行改進(jìn)，在種群更新過程中引入當(dāng)前種群最優(yōu)個(gè)體信息，以提升算法的收斂速度和局部優(yōu)化能力。

關(guān)鍵詞：人工蜂群算法;搜索方程;變異算子

人工蜂群算法（Artificial Bee Colony，ABC）是由Karaboga基于蜂群搜索蜜源行為提出的一種群體智能優(yōu)化算法，該算法在搜索過程中同時(shí)兼顧局部搜索和全局搜索，控制參數(shù)少、易于實(shí)現(xiàn)、全局收斂性能好、具有良好的魯棒性，并且其優(yōu)化性能優(yōu)于其他一些傳統(tǒng)智能優(yōu)化算法[1]，如遺傳算法、粒子群算法、差分進(jìn)化算法等，特別是在非線性函數(shù)優(yōu)化求解方面具有良好的性能。關(guān)于ABC算法的研究主要是對其選擇機(jī)制和搜索方程進(jìn)行改進(jìn)，以提升算法性能。丁海軍等[2]將boltzmann選擇策略引入ABC算法，對其收斂速度和種群多樣性進(jìn)行平衡;畢曉君等[3]采用自由搜索算法中的信息素模型代替輪盤賭選擇策略，提高了算法的全局搜索能力。在上述研究中由于沒有對算法搜索方程進(jìn)行改進(jìn)，導(dǎo)致在處理復(fù)雜優(yōu)化問題時(shí)收斂速度和尋優(yōu)精度較低。因此，本文在對傳統(tǒng)ABC算法分析基礎(chǔ)上，考慮當(dāng)前種群最優(yōu)個(gè)體對種群更新的影響，對算法搜索方程進(jìn)行改進(jìn)，在數(shù)值實(shí)驗(yàn)中選用標(biāo)準(zhǔn)測試函數(shù)對算法性能進(jìn)行驗(yàn)證。

1? ? 人工蜂群算法

在ABC算法模型中，主要包含兩部分：蜜源和人工蜂群。其中，蜜源位置代表優(yōu)化問題的可行解，蜜源的花蜜量代表對應(yīng)解的質(zhì)量或適應(yīng)度值。根據(jù)蜜蜂在搜索過程中的職能不同可將人工蜂群分為3類：采蜜蜂、觀察蜂和偵查蜂。采蜜蜂和觀察蜂數(shù)量各占蜂群一半，且等于蜜源數(shù)量，當(dāng)采蜜蜂放棄對應(yīng)蜜源后即成為偵查蜂。在ABC算法中，3類蜜蜂按以下順序進(jìn)行搜索：

（1）采蜜蜂對蜜源進(jìn)行開采，評估花蜜量。在該過程中，采蜜蜂在蜜源附近搜索，并采用貪婪選擇機(jī)制選擇新蜜源位置以發(fā)現(xiàn)局部最優(yōu)解。

（2）觀察蜂對蜜源進(jìn)行開采。根據(jù)采蜜蜂傳遞的蜜源信息，按照與花蜜量正相關(guān)的概率選擇蜜源位置進(jìn)行開采，同樣地，采用貪婪選擇機(jī)制選擇新蜜源位置以發(fā)現(xiàn)局部最優(yōu)解。

（3）確定偵查蜂。如果蜜源在經(jīng)過一定次數(shù)后仍沒有更新，說明該位置陷入局部最優(yōu)。此時(shí)，采蜜蜂放棄該蜜源位置，相應(yīng)的采蜜蜂變?yōu)閭刹榉?。偵查蜂隨機(jī)搜索新蜜源代替被放棄的蜜源。

在初始化蜜源位置基礎(chǔ)上，ABC算法通過不斷重復(fù)以上3種蜜蜂的活動(dòng)搜索全局最優(yōu)解。在上述ABC算法中，存在3個(gè)控制參數(shù)，描述如下。

（1）SN：種群數(shù)量。即種群中采蜜蜂和觀察蜂的數(shù)量，且與蜜源數(shù)量相等。

（2）Limit：蜜源為更新次數(shù)。當(dāng)蜜源循環(huán)次數(shù)超過Limit后仍沒有改進(jìn)，該蜜源位置被放棄，對應(yīng)的采蜜蜂變?yōu)閭刹榉洹?/p>

（3）Maxcycle：最大迭代次數(shù)。算法迭代次數(shù)大于Maxcycle時(shí)結(jié)束運(yùn)行并輸出最優(yōu)個(gè)體。

在ABC算法優(yōu)化過程中，首先隨機(jī)產(chǎn)生SN個(gè)初始解，假設(shè)優(yōu)化問題的每個(gè)解Xi，i=1，2，…SN，D為向量，D是優(yōu)化變量個(gè)數(shù)。在此基礎(chǔ)上，采蜜蜂和觀察蜂通過以下搜索方程產(chǎn)生新蜜源（即新的可行解）：

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

基于上述分析可知，ABC算法的優(yōu)化性能主要受搜索方程影響。在搜索方程式（1）中，Xk為隨機(jī)選擇的個(gè)體，新的可行解是通過當(dāng)前個(gè)體向另一個(gè)隨機(jī)個(gè)體的偏移得到。這種方法產(chǎn)生的可行解質(zhì)量不能保證，對當(dāng)前解的更新效率較低，而且在搜索過程中沒有充分利用種群最優(yōu)個(gè)體信息。因此，ABC算法局部優(yōu)化能力較差，導(dǎo)致算法的收斂速度較慢。

針對上述問題，本研究借鑒差分進(jìn)化算法（Differential Evolution， DE）的變異算子對ABC算法搜索方程進(jìn)行改進(jìn)，以提高算法收斂速度。DE算法的變異算子充分利用了種群中最優(yōu)個(gè)體的信息，可以使種群快速向最優(yōu)個(gè)體聚攏，具有較強(qiáng)的局部優(yōu)化能力?；诓罘肿儺愃阕?，新搜索方程為：

由上式可以看出，新的可行解只在最優(yōu)個(gè)體附近產(chǎn)生，因此可以有效提高算法收斂速度。但采用該搜索方程也會(huì)在一定程度上降低種群的多樣性，可能使得算法過早收斂，降低全局搜索能力。因此，為平衡算法的全局搜索和局部搜索能力，在采蜜蜂階段采用式（1）產(chǎn)生新的可行解，盡可能擴(kuò)展搜索區(qū)域，保證種群的多樣性;由于觀察蜂可以綜合所有采蜜蜂得到的信息，進(jìn)而判斷出當(dāng)前種群中最優(yōu)個(gè)體位置，所以在觀察蜂階段，采用式（2）產(chǎn)生新的可行解，增強(qiáng)種群更新的趨勢性。

3? ? 數(shù)值實(shí)驗(yàn)

部分學(xué)者已對ABC算法與遺傳算法、蟻群算法、粒子群算法等智能優(yōu)化算法進(jìn)行了較為詳細(xì)的比較分析，因此這里只將本文提出的改進(jìn)ABC算法（MABC）和原始ABC算法進(jìn)行比較，驗(yàn)證MABC算法的性能和優(yōu)越性。

為驗(yàn)證本文所提MABC算法的性能，選取3個(gè)不同類型的優(yōu)化算法標(biāo)準(zhǔn)測試函數(shù)Sphere、Griewank和Rosebrock進(jìn)行數(shù)值實(shí)驗(yàn)。表1給出了選用函數(shù)的函數(shù)名、表達(dá)式及搜索空間。Sphere為單峰高維函數(shù)，理論最優(yōu)值為f（0，…，0）=0，設(shè)置維數(shù)為100，搜索空間為[-100，100]D;Griewank為多峰多極值的高維函數(shù)，理論最優(yōu)值為f（0，…，0）=0，設(shè)置維數(shù)為100，搜索空間為[-600，600]D;Rosebrock為多峰少極值的低維函數(shù)，理論最優(yōu)值為f（1，…，1）=0，設(shè)置維數(shù)為5，搜索空間為[-100，100]D。

ABC算法和MABC算法控制參數(shù)設(shè)置相同，如下所示：SN=50，Limit=50，Maxcycle=1 000。為測試算法性能，在以上參數(shù)設(shè)置下對每個(gè)測試函數(shù)獨(dú)立運(yùn)行算法30次，計(jì)算優(yōu)化結(jié)果的平均值和標(biāo)準(zhǔn)差。在此基礎(chǔ)上比較算法的魯棒性和尋優(yōu)精度，并通過優(yōu)化過程對算法收斂速度進(jìn)行分析。不同函數(shù)優(yōu)化結(jié)果的平均值和方差如表1所示。

由表1可以看出，針對實(shí)驗(yàn)中的3個(gè)測試函數(shù)，本文提出的MABC算法所得優(yōu)化結(jié)果平均值和標(biāo)準(zhǔn)差均優(yōu)于原始ABC算法。特別是在多峰函數(shù)Griewank和Rosebrock中，ABC算法優(yōu)化結(jié)果精度較差，難以得到滿意解。因此，本文提出的MABC算法能夠有效提高尋優(yōu)精度及結(jié)果的魯棒性，具有良好的全局搜索能力。

為直觀對比兩種算法的收斂性能，下面對以上3個(gè)測試函數(shù)在ABC和MABC算法下的優(yōu)化過程進(jìn)行分析。對Sphere函數(shù)來說，MABC算法在迭代600次后趨于收斂，ABC算法在迭代800次后趨于收斂;對Griewank函數(shù)來說，MABC算法在迭代700次后趨于收斂，ABC算法在迭代900次后趨于收斂;而對于Rosebrock函數(shù)，MABC算法在迭代500次后趨于收斂，ABC算法在迭代700次后趨于收斂;可以看出，MABC算法的收斂速度明顯更快。由此可得，與傳統(tǒng)ABC算法相比，MABC算法能夠有效提高種群更新效率和收斂速度，具有良好的函數(shù)優(yōu)化性能。

4? ? 結(jié)語

本文在ABC算法機(jī)理分析基礎(chǔ)上，結(jié)合DE算法的變異算子，將每代種群中最優(yōu)個(gè)體信息引入搜索方程，在一定程度上提高了種群更新效率，平衡了算法全局優(yōu)化和局部優(yōu)化能力。數(shù)值實(shí)驗(yàn)結(jié)果表明，本文所提的改進(jìn)方法能夠有效提高ABC算法收斂速度和優(yōu)化結(jié)果精度。

[參考文獻(xiàn)]

[1]KARABOGA D，AKAY B.A comparative study of artificial bee colony algorithm[J].Applied Mathematics and Computation，2009（1）：108-132.

[2]丁海軍，馮慶嫻.基于boltzmann選擇策略的人工蜂群算法[J].計(jì)算機(jī)工程與應(yīng)用，2009（31）：53-55.

[3]畢曉君，王艷嬌.改進(jìn)人工蜂群算法[J].哈爾濱工程大學(xué)學(xué)報(bào)，2012（1）：117-123.