王曉娟

(西安電子科技大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院，陜西西安 710071)

近年來，人工蜂群算法［1］由于其良好的搜索能力和強(qiáng)大的實際應(yīng)用背景，得到了快速的發(fā)展，人工蜂群算法的改進(jìn)體也相繼而出。但該算法仍面臨著諸多難題。隨著越來越多的研究，其收斂速度慢，在解決高維多峰問題時易陷入局部最優(yōu)等缺點給學(xué)者帶來了困難和挑戰(zhàn)。在文獻(xiàn)［2］中作者用排序選擇代替了貪婪選擇，維持種群的多樣性，又加入了隨機(jī)動態(tài)搜索算子用來進(jìn)行局部搜索，加快了算法的收斂速度;在文獻(xiàn)［3］中，由于人工蜂群算法的變異方程存在著全局搜索能力強(qiáng)而局部搜索能力弱的缺陷，受改進(jìn)的差分進(jìn)化算法的影響，提出了一種新的變異方程，該變異方程在最優(yōu)解附近進(jìn)行搜索，提高了算法的局部搜索能力;文獻(xiàn)［4］提出了基于ABC改進(jìn)的優(yōu)秀種群引導(dǎo)的人工蜂群算法(Gbest－guided Artificial Bee Colony Algorithm，GABC)等?；趩尉S搜索的雇傭蜂由于改變量小，而使得ABC算法收斂速度較慢;本文借鑒了回溯搜索優(yōu)化算法(Backtracking Search Optimization Algorithm，BSA)［5］的搜索方式，BSA在變異擾動方程中，基向量無旋轉(zhuǎn)，這與ABC的變異方式相似。故本文結(jié)合蜂群算法的特點，使BSA的搜索方式與雇傭蜂結(jié)合，得到了一種基于多維和一維混合搜索策略的改進(jìn)雇傭蜂，使得搜索策略更加快速高效，并改進(jìn)了跟隨蜂的蜜源選擇策略，增加了種群多樣性。

1 人工蜂群算法

人工蜂群算法可分為4部分:初始化食物源、雇傭蜂開采、跟隨蜂開采和觀察蜂替換食物源。初始化食物源方式為

食物源表示問題的可行解，xi，j表示第i個食物源xi的第 j維元素，其中 i=1，2，…，ps，j=1，2，…，D，D 為問題的維數(shù)，ps為種群規(guī)模，［aj，bj］表示問題第 j維元素的區(qū)間。隨機(jī)生成ps個食物源后，交給雇傭蜂進(jìn)行開采，開采方程如下

vi，j是變異后第i個個體vi的第j維元素，vi是雇傭蜂隨機(jī)選取一個不同于xi的食物源，j是隨機(jī)選擇的一個位置索引，r是［－1，1］之間的一個隨機(jī)數(shù)。當(dāng)產(chǎn)生新的食物源后，雇傭蜂會根據(jù)食物源的適應(yīng)度值，并在vi和xi之間作貪心法選擇。第i個個體適應(yīng)度值fitnessi的計算公式為

雇傭蜂開采完后交給跟隨蜂開采，跟隨蜂不同于雇傭蜂，其會選擇性開采食物源，每個食物源的被選擇概率probi計算公式為

跟隨蜂先根據(jù)輪盤賭選擇出新食物源xi，然后對新食物源進(jìn)行如雇傭蜂一致的開采并進(jìn)行貪心選擇。觀察蜂觀察食物源的替換情況，若某食物源在規(guī)定的limit次開采后均未被替換，蜂群將放棄這一食物源，并由觀察蜂重新隨機(jī)生成一個食物源來替代。最終算法將循環(huán)執(zhí)行雇傭蜂、跟隨蜂和觀察蜂的操作，直至滿足停止條件。

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

人工蜂群算法自提出以來，并用嚴(yán)格的理論來證明其搜索維數(shù)的多少，及其擾動尺度;根據(jù)經(jīng)驗性的研究，已確定單一的一維搜索方式使得蜂群的搜索步長較短，從而會造成其在某些問題上的收斂速度緩慢，但一維搜索方式對個體的改變量較小，使得算法對個體有更強(qiáng)的微調(diào)處理能力，因此人工蜂群算法收斂精度明顯高于其他進(jìn)化算法;本文在雇傭蜂階段中引入一種聯(lián)合搜索機(jī)制，使蜂群隨機(jī)進(jìn)行一維或多維搜索來克服搜索步長短的限制，同時也保留人工蜂群算法的高收斂精度;另外，針對不同的搜索維數(shù)，文中制定了不同的擾動尺度系數(shù)來配合，從而產(chǎn)生了兩種不同的搜索方程。在跟隨蜂階段，選用一種新的選擇策略，來增強(qiáng)種群的多樣性，防止算法陷入局部最優(yōu)。仿真實驗表明，該策略能取得更好的收斂效果，并加快人工蜂群算法的收斂速度。

2.1 歷史種群與種群初始化

標(biāo)準(zhǔn)人工蜂群算法中，種群的引導(dǎo)是當(dāng)代種群內(nèi)不同個體間的引導(dǎo)，為進(jìn)一步增強(qiáng)種群多樣性，利用與當(dāng)代種群有更大區(qū)別的歷史種群進(jìn)行引導(dǎo)，歷史種群是當(dāng)代種群或以前的某一代種群，其選擇是一馬爾科夫鏈過程，每代歷史種群更新情況如下

其中，歷史種群記作old P，初始種群記作P，即old P可選擇成為上代種群P或保持不變，選擇后對old P的個體做隨機(jī)排序。

改進(jìn)算法的初始化包括種群初始化和歷史種群初始化，初始化方程如下

其中，Pi，j，old Pi，j分別表示種群和歷史種群第 i個個體的第j維元素;lowj，upj分別表示第j維分量的下界和上界;rand表示(0，1)中的隨機(jī)數(shù)，兩初始化過程相互獨立。對歷史種群的初始化是為了防止第一次搜索時，歷史種群為空。

2.2 雇傭蜂的改進(jìn)

2.2.1 新的搜索方式

本文引入以下搜索方式，該搜索方式既可進(jìn)行多維搜索也可進(jìn)行一維搜索，兩者等概率隨機(jī)調(diào)用，新的搜索方程如下

map是一索引矩陣，·表示矩陣點乘運算，mapi，j為0或1，當(dāng)為1時，代表第i個個體的第j維為搜索維;當(dāng)為0時，表示其不為搜索維。F是擾動系數(shù)，offsprings是生成的實驗種群，若offsprings的第i個體適應(yīng)度值大于種群P的第i個體函數(shù)值，則將用來替換種群P的第i個體。其中，old P和map在每一代均會更新，map矩陣用來控制一維搜索和多維搜索的選擇，其更新方式如下

2.2.2 雇傭蜂搜索方式的改進(jìn)

對于每一代雇傭蜂，進(jìn)行以下開采搜索，且對于不同的搜索維數(shù)賦予不同的擾動系數(shù)。

(1)多維搜索方式時，擾動系數(shù)F的生成方程如下

epk是當(dāng)前代數(shù)，epoch是最大進(jìn)化代數(shù)，CH3是一服從自由度為3的卡方分布隨機(jī)數(shù)，新擾動系數(shù)即可產(chǎn)生規(guī)模較小的量，有利于局部搜索，也可產(chǎn)生規(guī)模較大的量，有利于全局搜索。改進(jìn)的擾動系數(shù)比原擾動系數(shù)更能平衡局部搜索和全局搜索。另外，改進(jìn)擾動系數(shù)的設(shè)計參考了差分進(jìn)化算法的擾動方程，將產(chǎn)生擾動系數(shù)的分布中心改為0.5而不是0。大量數(shù)值實驗表明，分布中心改為0.5有更好的收斂效果。

(2)一維搜索方式時，擾動系數(shù)F的方程如下

此時搜索過程等價于標(biāo)準(zhǔn)人工蜂群算法的搜索過程。

2.3 跟隨蜂階段的改進(jìn)

在新的跟隨蜂階段，在保證跟隨蜂作用前提下改變了跟隨蜂選擇食物源的方式。首先計算適應(yīng)度值，方程如下

為每個食物源賦予以下選擇概率

生成［0，1］間的隨機(jī)數(shù)rand與probi比較大小，若有rand＜probi，對食物源i進(jìn)行同雇傭蜂相同的搜索，否則不對其進(jìn)行搜索;在蜜源中循環(huán)進(jìn)行該操作，直到進(jìn)行次ps搜索，跟隨蜂階段結(jié)束。

新的選擇概率保持了具有大適應(yīng)度值的可行解，有較高的選擇可能性，同時隨著進(jìn)化代數(shù)的增加，不斷提高了小適應(yīng)度值可行解被選擇的幾率，有利于保持種群的多樣性。

3 實驗設(shè)計

實驗設(shè)計從文獻(xiàn)［7～8］中選取了12個多維測試函數(shù)，在相同的搜索次數(shù)下，將改進(jìn)蜂群算法與標(biāo)準(zhǔn)蜂群算法的收斂時間和收斂結(jié)果進(jìn)行比較，12個測試函數(shù)如表1所示。

表1 Benchmark測試函數(shù)

表2 測試實驗參數(shù)取值

實驗均在相同配置的計算機(jī)上，用Matlab 2013a進(jìn)行編程測試。為了說明改進(jìn)人工蜂群算法的收斂性能，給出5個高維函數(shù) F1、F2、F3、F7和F8的收斂曲線，如圖1所示。

圖1 收斂曲線圖

改進(jìn)蜂群算法、標(biāo)準(zhǔn)蜂群算法和回溯搜索算法的 收斂時間與收斂結(jié)果比較，如表3所示。

表3 改進(jìn)蜂群算法與標(biāo)準(zhǔn)蜂群算法的收斂時間和收斂結(jié)果比較

從12個測試函數(shù)的結(jié)果可看出，F(xiàn)ABC的收斂效果均優(yōu)于ABC及BSA，這說明基于多維和一維混合搜索策略的改進(jìn)雇傭蜂階段，能克服單維搜索雇傭蜂收斂速度慢的缺點，縮短搜索時間，有效加快了收斂速度;即使在解決griewank等高維問題時，F(xiàn)ABC的搜索效率也比ABC及BSA高，這一方面歸功于雇傭蜂階段更具開發(fā)性的搜索策略;另一方面得益于跟隨蜂階段有效的選擇策略，充分保證了種群的多樣性，使算法在加快了收斂速度時不易陷入局部最優(yōu)。新的搜索策略和選擇策略在加快了收斂速度的同時，也確保了算法具有較高的穩(wěn)定性。

4 結(jié)束語

人工蜂群算法搜索步長過短，對某些問題存在收斂速度慢的缺點，且易陷入局部最優(yōu)，回溯搜索優(yōu)化算法有較強(qiáng)的搜索能力，其變異方程能進(jìn)行長距離的擾動，且在基變量無旋轉(zhuǎn)的基礎(chǔ)上擾動，與雇傭蜂的搜索方式相似。本文借鑒BSA算法的思想對人工蜂群算法的雇傭蜂進(jìn)行改進(jìn)，較好地改進(jìn)了單一一維搜索下的缺點，并設(shè)計了自適應(yīng)的跟隨蜂的選擇策略，以增強(qiáng)算法的全局搜索能力。仿真實驗表明，改進(jìn)算法有更快的收斂速度和精度。

［1］Karaboga D，Basturk B.A powerful and efficient algorithm for numerical function optimization:artificial bee colony(ABC)algorithm［J］.Journal of Global Optimization，2007，39(3):459－471.

［2］暴勵，曾建潮.自適應(yīng)搜索空間的混沌蜂群算法［J］.計算機(jī)應(yīng)用研究，2010，27(4):1331 －1335.

［3］丁海軍，馮慶嫻.基于Boltzmann選擇策略的人工蜂群算法［J］.計算機(jī)工程與應(yīng)用，2009，45(31):53 －55.

［4］Zhu G，Kwong S.Gbest－ guided artificial bee colony algorithm for numerical function optimization［J］.Applied Mathematics and Computation，2010，217(7):3166 －3173.

［5］Civicioglu P.Backtracking search optimization algorithm for numerical optimization problems［J］.Applied Mathematics and Computation，2013，219(15):8121 －8144.

［6］Storn R，Price K.Differential evolution－a simple and efficient heuristic for global optimization over continuous spaces［J］.Journal of Global Optimization，1997，11(4):341 －359.

［7］Karaboga D，Akay B.A comparative study of artificial bee colony algorithm ［J］.Applied Mathematics and Computation，2009，214(1):108 －132.

［8］Molga M，Smutnicki C.Test functions for optimization needs［J］.Journal of Global Optimization，2009，23(3):281 －287.