李文霞，劉林忠，代存杰，李玉

（蘭州交通大學交通運輸學院，蘭州 730070）

0 引言

近年來，隨著群智能優(yōu)化算法的高效發(fā)展，其在解決復雜優(yōu)化問題時體現(xiàn)出良好的求解性能，受到學者們的廣泛關注，群智能優(yōu)化算法源于對自然界中生物群體行為的模擬，主要包括遺傳算法［1］、蟻群算法［2］、粒子群算法［3］、人工蜂群（Artificial Bee Colony，ABC）算法［4］等。遺傳算法對自然界中生物的自然淘汰進化過程進行模擬，主要通過交叉、變異、選擇算子來實現(xiàn)，該算法的改進方向包括自適應算子的引入［5］、多種群方式的改進［6］、編碼技術的改進［7］及混沌理論的加入［8］等角度；蟻群算法模擬螞蟻覓食行為，通過信息素的正反饋機制尋找自蟻巢到食物源的最短路徑，近年來蟻群算法的改進主要集中在信息素的更新策略［9］及路徑選擇策略［10］兩個方面；粒子群算法對生物界鳥類覓食行為進行模擬，通過對全局極值的對比，及時調(diào)整粒子的搜索速度與方向，相關學者從粒子群多樣性的控制［11］、算法中參數(shù)的改進［12］、初始化過程中粒子拓撲結(jié)構的優(yōu)化［13］等方面出發(fā)對算法進行改進。上述群體智能算法的優(yōu)化改進逐漸趨于成熟，一些新型群體智能算法的提出受到了國內(nèi)外學者的廣泛關注。

受蜜蜂群體覓食行為啟發(fā)，Karaboga［4］于2005 年提出了人工蜂群（ABC）算法。相較于其他群體智能算法，人工蜂群算法中的勞動分工和協(xié)作機制有效提高了算法的全局搜索能力，同時正反饋的尋優(yōu)策略加快了全局尋優(yōu)過程，求解效率更高，并且在求解連續(xù)優(yōu)化問題和組合優(yōu)化問題時均表現(xiàn)出優(yōu)越的性能，具有廣泛的適用性，已在神經(jīng)網(wǎng)絡訓練［14］、系統(tǒng)工程設計［15］、聚類分析［16］和圖像信號處理［17］等眾多領域得到了廣泛應用。

ABC 性能主要取決于搜索方程和個體選擇策略，基本ABC 的搜索方程包含隨機個體信息較強，相較于一般群體智能優(yōu)化算法，表現(xiàn)出良好的全局搜索優(yōu)勢，但同時存在收斂速度慢、求解精度低、易陷入局部最優(yōu)等問題。算法的全局搜索和局部開發(fā)在求解過程中表現(xiàn)出互補性，但在操作上又具有矛盾性，為更好地平衡二者，同時滿足求解效率和求解精度要求，相關學者從搜索機制改進和融合算法等方面進行了有效研究。向萬里等［18］將最優(yōu)個體指導信息引入雇傭蜂階段，利用個體信息對跟隨蜂的擾動，進一步平衡探索能力和開發(fā)能力。Kiran等［19］考慮算法的下降梯度，對較強地位的維度進行搜索，以提高算法的搜索深度。孟紅云等［20］利用精英信息、隨機信息及鄰域信息指導雇傭蜂階段搜索，同時在觀察蜂階段提出全局精英信息和當代最優(yōu)信息指導搜索，使算法的尋優(yōu)能力得到顯著提高。Jadon 等［21］受差分進化（Differential Evolution，DE）思想的啟發(fā)，提出具有差異進化的混合人工蜂群（Hybrid Artificial Bee Colony with Differential Evolution，HABCDE）算法，將DE 和ABC 融合，以提供良好的搜索平臺，在提高搜索的深度的同時不影響探索的廣度。魏鋒濤等［22］為提高種群多樣性，構建了混沌反向解初始化機制，并構建跟隨蜂量子更新搜索策略，進一步地提高蜜源鄰域內(nèi)的尋優(yōu)質(zhì)量。

上述算法改進在不同程度上提高了ABC 的尋優(yōu)能力，但仍有較大改進空間，如何進一步提高算法的應用范圍、收斂速度及收斂精度，仍需深入研究，因此本文提出了一種基于多種群組合策略的人工蜂群（Artificial Bee Colony based on Multipopulation Combination strategy，MCABC）算法。為提高算法搜索效率，針對雇傭蜂和跟隨蜂分別設計不同的組合策略，在跟隨蜂階段劃分了自由種群和非自由種群，針對不同屬性的個體采用對應的子策略；同時在搜索方程中改進了維度信息更新機制，進一步提高了算法在高維復雜函數(shù)的求解性能。為驗證本文提出算法的有效性，采用15 個標準測試函數(shù)，將MCABC與多個具有代表性的改進ABC算法進行對比，進一步驗證了算法的尋優(yōu)性能。

1 標準人工蜂群算法

人工蜂群算法思想來源于仿生學中蜜蜂群體覓食行為，蜂群個體分為雇傭蜂、跟隨蜂和偵查蜂3 種類型，雇傭蜂和跟隨蜂數(shù)量各占蜂群總數(shù)一半，偵查蜂數(shù)量與雇傭蜂相同，雇傭蜂負責勘察并將蜜源信息分享給跟隨蜂，跟隨蜂依據(jù)蜜源質(zhì)量通過輪盤賭方式選擇，并在附近尋找更好的蜜源，當某一蜜源被舍棄時，雇傭蜂轉(zhuǎn)化為偵查蜂尋找新蜜源，三種蜂群發(fā)揮各自效用，準確有效完成蜜源的搜索和采集任務。

1.1 初始化

在標準ABC 中，當前解空間通過式（1）初始化種群，一個蜜源位置代表問題的一個可行解，蜜源的位置用D維向量表示Xi=[xi1，xi2，…，xiD]，其中：

其中：i=1，2，…，SN，SN是解（蜜源）的數(shù)量，j=1，2，…，D，D是解的維數(shù)；xi，j是第i個解的第j維；?i，j是［0，1］的隨機數(shù)；、是j維的上、下界。

1.2 雇傭蜂

雇傭蜂通過式（2）在初始解附近搜索新解，進行局部搜索，并對每個蜜源的適應度進行計算，進而評價食物源的優(yōu)劣，若新解優(yōu)于初始解，則保留新解，迭代重復值Counter（i）加1；否則保留初始解，迭代重復值Counter（i）不變，即通過貪婪選擇更新解同時記錄蜜源開采情況。

其中：vi，j是更新后的解；xk，j是在種群中隨機選擇與xi，j不相同的解；φi，j是［-1，1］的均勻隨機數(shù)。

1.3 跟隨蜂

跟隨蜂依據(jù)雇傭蜂傳遞的蜜源信息，通過式（3）輪盤賭概率選擇某一蜜源，蜜源的適應度值越高，可行解的質(zhì)量越好，被選擇的概率越大。隨后跟隨蜂采用式（2）進行鄰域搜索，并采用貪婪選擇更新解，在保留優(yōu)勢個體的同時兼顧蜜源的探索能力。

其中：pi是解i的選擇概率；fiti是解i的適應度值。

其中：fi是目標函數(shù)值。

1.4 偵查蜂

當某一蜜源長期未更新時，當前蜜源將被遺棄，雇傭蜂轉(zhuǎn)變?yōu)閭刹榉洌ㄟ^式（1）隨機產(chǎn)生新蜜源，算法進入雇傭蜂階段。偵查蜂的操作有效避免了算法過早陷入局部最優(yōu)，提高了算法的全局探索能力。

2 基于多種群組合策略的人工蜂群算法

2.1 研究思路

標準ABC 受制于搜索策略的單一和搜索方程的信息匱乏，算法的搜索導向性和多源信息的融合性較弱，表現(xiàn)為一種隨機的無向搜索，這種無向搜索雖然一定程度上增強了全局探索能力，但同時也降低了收斂速度和求解精度，且迭代過程中只更新D維中隨機選擇的一個維度，使其在求解高維函數(shù)時尋優(yōu)能力下降。鑒于此，本文針對雇傭蜂和跟隨蜂分別設計組合策略CS1和CS2。在雇傭蜂階段采用CS1策略，以提高初始種群的深度與廣度；在跟隨蜂階段，為進一步明確跟隨蜂個體的任務重點，針對自由子集和非自由子集，采用CS2 策略，其中，自由個體增強探索能力，非自由個體側(cè)重開發(fā)能力；最后，在搜索方程中融入異維單點更新和多維匹配更新機制，以提高算法在高維問題中的優(yōu)化效率。

2.2 維度更新機制

ABC中固有的同維單點更新機制能夠有效勝任低維問題的求解，而這種單一的更新模式在面對高維問題時求解效率顯著下降，既有研究證明，異維搜索避免了ABC 單一搜索模式的局限性，增強了算法的全局搜索能力，有利于算法擺脫局部最優(yōu)［23-24］。為此，本文將多維匹配更新機制和異維單點更新機制引入搜索方程，有效利用多維信息的并行優(yōu)化和異維信息的協(xié)同交互，提高算法在求解高維問題時的精度。多維匹配更新示意如圖1所示，異維單點更新示意如圖2所示。

圖1 多維匹配更新示意圖Fig.1 Schematic diagram of multi-dimensional matching update

圖2 異維單點更新示意圖Fig.2 Schematic diagram of different-dimensional single point update

2.3 雇傭蜂組合策略CS1

對于標準ABC 算法，雇傭蜂主要借助式（2）在當前解i的鄰域內(nèi)進行一次擾動，主要包括三個隨機項j、k、φi，j，隨機項j確定某一具體更新維度，隨機項k確定用于更新的另一個解，這種更新模式使初始解僅在對應的同一維度內(nèi)更新鄰域，雖然表現(xiàn)出一定的全局探索性，但局部開發(fā)性較弱。因此，為達到立體式搜索效果，采用一種組合策略CS1 來平衡算法的探索和開發(fā)能力。

CS1-1 搜索方程中包含了四個隨機項M、k、h、φi，j，加強廣度探索：

其中：M是多維匹配更新的維度數(shù)；k≠h≠i且k，h∈{1，2，…，SN} 是隨機選擇的個體下標。M個維度的多維匹配更新在最大限度上保留了初始解的有效信息，同時在一定程度上保證了鄰域搜索的均衡性，而隨機項k、h提高了解在鄰域內(nèi)的探索能力，擴大了搜索空間，即CS1-1策略兼顧了雇傭蜂鄰域搜索的廣度與深度。

CS1-2側(cè)重于深度開發(fā)，與文獻［20］中式（3）“vi，j=xbest，j+φi，j(xbest，j-xi，j)”不同，式（5）避免了xbest，j與xi，j差距過大時導致的擾動過大，最大限度保留了精英個體的有益信息，提高了搜索效率。

其中：xbest是每一代中適應值最高的精英個體。

雇傭蜂隨機選擇CS1-1 和CS1-2，在全局探索的同時兼顧對最優(yōu)個體的開發(fā)。

2.4 跟隨蜂種群劃分

在跟隨蜂階段，將種群劃分為自由子集和非自由子集，如圖3 所示。為兩類個體賦予特定的職能，其中自由個體適應值與精英個體適應值相差較大，潛在的開發(fā)效益較差，可以加強其探索能力來搜索額外的解空間；非自由個體的適應值與精英個體的適應值的差異較小，有更好的挖掘潛能，可以賦予其在非自由子集范圍內(nèi)的開發(fā)能力，以加強算法在優(yōu)勢個體的深度搜索。跟隨蜂中非自由個體搜索通常情況下比自由個體搜索跨度要小，兩種策略的結(jié)合在深度和廣度上加強了算法的搜索能力。

圖3 種群劃分Fig.3 Population division

平均差異度dt作為劃分種群的依據(jù)：

其中：dt是第t代循環(huán)適應值的平均差異度；fitbest和fiti分別是精英個體和第i個體的適應值。

計算當前個體適應度fiti與最佳個體適應度fitbest的差值，比較差值與平均差異度dt的大小，若差值大于平均差異度，即超出以平均差異度為半徑的范圍，則當前個體視為自由個體；反之，當前個體視為非自由個體，以此來進行種群劃分。

2.5 跟隨蜂組合策略CS2

在跟隨蜂階段，經(jīng)過輪盤賭選擇后，當跟隨蜂選擇的是自由個體，通過兩個隨機個體和當前個體構建探索的子策略CS2-1，包括M、p、q、φi，j四個隨機項，使其在整個解空間內(nèi)進行隨機搜索：

其中：p≠q≠i且p，q∈{1，2，…，SN} 。

非自由個體具有成為下一精英個體的潛在優(yōu)勢，而多源信息交互是改善搜索性能的有效手段，因此，當跟隨蜂選擇的是非自由個體，則通過當前個體、精英個體和非自由子集中的隨機個體構建CS2-2 子策略，在非自由子集范圍跨越維度深度開發(fā)，以期發(fā)現(xiàn)未知的優(yōu)勢個體：

其中：xe是非自由子集中的隨機個體；r1≠r2≠r3且r1，r2，r3∈{1，2，…，D} 。

式（8）與文獻［20］中式（12）在方程結(jié)構上很相似，需要注意的是，在文獻［20］中式（12）是利用精英解的有益信息和同維單點更新機制，相應的，式（8）采用的是非自由子集中隨機個體的有益信息和異維單點更新機制，在擴大有益解空間的同時有效利用了異維信息的協(xié)同優(yōu)化。

2.6 MCABC流程

算法迭代過程中，雇傭蜂隨機選擇子策略CS1-1 或CS1-2更新初始化種群個體，通過與初始化種群貪婪選擇保留當前優(yōu)勢個體；以個體適應值和最佳適應值的平均差異度比較作為種群劃分標準對當前優(yōu)勢個體進行種群劃分，為跟隨蜂階段作準備；通過輪盤賭方式對跟隨蜂進行選擇，針對自由子集跟隨蜂采取CS2-1子策略，非自由子集跟隨蜂采取CS2-2子策略，在進行貪婪選擇后更新自由子集和非自由子集；對于達到未更新次數(shù)的個體進行初始化。不斷循環(huán)上述過程，直到滿足算法停止條件，算法流程如圖4所示。

圖4 MCABC算法流程Fig.4 Flow chart of MCABC algorithm

2.7 MCABC偽代碼

MCABC偽代碼如下：

2.8 算法復雜度分析

MCABC 算法在雇傭蜂階段和跟隨蜂階段分別引入了兩種不同的種群更新策略。在雇傭蜂階段，種群個體通過隨機方式選擇策略CS1-1和策略CS1-2進行更新，該過程不增加算法的時間復雜度。在跟隨蜂階段，涉及循環(huán)前的種群整體劃分和循環(huán)中的種群動態(tài)劃分，在循環(huán)前，需依據(jù)種群個體適應值和精英個體適應值的平均差異度作為種群劃分的標準，首先依據(jù)適應度值對整個種群進行排序操作（對總體排序）選擇出精英個體，其時間復雜度為O（SN·log（SN）），然后通過式（7）計算種群平均差異度，以此標準對種群整體進行劃分；在循環(huán)過程中，每次循環(huán)后需判斷當前更新個體是否為精英個體，更新當前個體后通過式（7）計算種群適應值的平均差異度來動態(tài)劃分種群，該過程不涉及排序操作，不額外增加算法的時間復雜度。

因此，與ABC 算法相比，MCABC 算法在雇傭蜂階段開始前劃分種群過程時引入了額外的計算，由于ABC 算法的時間復雜度為O（SN·D），因此，MCABC算法時間復雜度為O（SN·D+SN·log（SN）），由于D遠大于log（SN），MCABC 算法的時間復雜度可以簡化為O（SN·D），可見相較于經(jīng)典ABC 算法，MCABC算法具有相同的計算時間復雜度。

3 實驗仿真與結(jié)果分析

3.1 測試函數(shù)實驗結(jié)果

為了測試本文提出MCABC 算法的性能，采用15 個標準測試函數(shù)，將MCABC與文獻［4］提出的ABC、文獻［25］提出的GABC（Gbest-guided Artificial Bee Colony）、文獻［26］提出的qABC（quick Artificial Bee Colony）、文獻［27］提出的CABC 四種算法進行比較，仿真基于Matlab 2016a 軟件平臺實現(xiàn)。測試函數(shù)信息如表1所示。

表1 標準測試函數(shù)Tab.1 Benchmark functions

仿真在一臺搭載1.6 GHz 的Intel Core i5 處理器和4 GB內(nèi)存的PC 平臺上實現(xiàn)?？紤]對算法性能進行較為全面的測試，采用的15 個測試函數(shù)包括了各種類型的特征函數(shù)，f1、f2、f4、f6～f8、f12為連續(xù)單峰函數(shù)，在解空間中僅有一個極值點；f3在特定的間隔產(chǎn)生階躍現(xiàn)象，是一種不連續(xù)的階躍函數(shù)；f5的特征與問題的維數(shù)有關，當D≤3 時，f5為單峰函數(shù)，當D>3時，f5為多峰函數(shù)；f9～f11、f13～f15為連續(xù)多峰函數(shù)，在解空間中存在大量的局部極小值點，該類函數(shù)在求解時易陷入局部最優(yōu)。算法實驗參數(shù)設置如下：蜂群規(guī)模NP=60，算法最大迭代次數(shù)MCF=5000，未更新限制次數(shù)Limit=3000，為了測試算法在低維和高維條件下求解性能的差異，分別在函數(shù)為50維和100 維時進行測試。比較算法的特定參數(shù)均參照原文設定［2-3］：qABC 中r=1.5，GABC 中C=1.5。對每個測試函數(shù)運行20次，得到最優(yōu)值（Best）、平均值（Mean）、方差（Std）及達到可接受值的平均迭代次數(shù)（Minc），50 維和100 維仿真結(jié)果如表2～3所示

表2 低維函數(shù)下5種算法的仿真結(jié)果（D=50）Tab.2 Simulation results of five algorithms under low-dimensional functions（D=50）

本文采用4 個評價指標對各算法的性能進行對比，Best（Mean）表示20 次獨立測試中的最佳目標值（平均目標值），Std（Minc）記錄了20次獨立實驗測試結(jié)果的標準差（達到可接受值的平均迭代次數(shù)）。表2 記錄了D=50 的測試結(jié)果。與標準ABC 相比，對于除f3、f10以外的所有函數(shù)，MCABC 在收斂速度、求解精度、穩(wěn)定性上均優(yōu)于ABC，由于f3全局最優(yōu)是一個區(qū)域，f10全局最優(yōu)不是一個點，因此這兩個函數(shù)更容易搜索到最優(yōu)值，所以MCABC 與ABC 都能夠求得最優(yōu)值，但MCABC 在收斂性和穩(wěn)定性上顯著優(yōu)于ABC。此外，在函數(shù)f8、f9、f12、f15的求解中，MCABC的求解性能遠優(yōu)于ABC。MCABC 與其他改進ABC 相比，在求解精度上，對于函數(shù)f3、f10、f11、f15，MCABC 與其他改進ABC 均能達到最優(yōu)值，在除f3、f10、f11、f15以外的其他函數(shù)上，MCABC 在求解精度上均不同程度優(yōu)于其他改進ABC。在算法穩(wěn)定性上，qABC 在f5上優(yōu)于MCABC，特別對于函數(shù)f10，GABC、CABC 與MCABC 均具有最強的穩(wěn)定性，在函數(shù)f11的求解中，GABC 和MCABC 也具有相同的強穩(wěn)定性，在除f5、f10、f11外的其他函數(shù)上，MCABC 均優(yōu)于其他改進ABC。在算法收斂性上，qABC 在f5、f12、f14略優(yōu)于MCABC，CABC 在f9優(yōu)于MCABC，在除f5、f12、f14、f9外的其他函數(shù)上，MCABC 均遠優(yōu)于其他改進ABC。綜上，在50 維函數(shù)測試條件下，MCABC的綜合尋優(yōu)能力優(yōu)于已有的改進ABC。

為進一步驗證本文改進算法在高位函數(shù)中的有效性，選擇文獻中常用的4 個具有代表性的測試函數(shù)在100 維條件下進行仿真，結(jié)果如表3所示。

表3 高維函數(shù)下5種算法的仿真結(jié)果（D=100）Tab.3 Simulation results of 5 algorithms under high-dimensional functions（D=100）

由于MCABC采用多維匹配和異維協(xié)同的更新機制，因此MCABC 在收斂精度上均超過其他算法，尤其是對于函數(shù)f10、f15，MCABC 盡管在穩(wěn)定性上不如低維條件下好，但是依舊能收斂到理論最優(yōu)。100 維測試下MCABC 相較于ABC 及其他改進算法在收斂速度上具有顯著優(yōu)勢，并且在穩(wěn)定性上均優(yōu)于其他算法。為更加可視化展示MCABC的求解性能，選取不同類型的四個函數(shù)f1、f7、f10、f15，分別在50 維和100 維條件下對5個算法進行對比，如圖5～6所示，其中，收斂函數(shù)圖是本次獨立實驗的收斂函數(shù)曲線。

由圖5～6 可以看出，得益于搜索方程更新模式的多樣性，無論在低維還是高維測試中，MCABC 收斂速度均明顯快于其他算法，且收斂精度最高，均保持良好的下降趨勢。在50 維測試條件下，改進4 種ABC 算法能夠有效發(fā)揮各自不同的優(yōu)勢，下降速度和趨勢差異較為明顯；在100 維測試條件下，由于維度的顯著增加，受限于搜索方程更新模式的單一性，削弱了改進ABC 算法各自的優(yōu)勢，各改進ABC 算法的下降趨勢和收斂速度相對接近，收斂曲線差異性減小，但MCABC 仍舊保持相較于其他算法的顯著優(yōu)勢。

圖5 四個標準測試函數(shù)的50維收斂圖Fig.5 Fifty-dimensional convergence graph of 4 benchmark functions

圖6 四個標準測試函數(shù)的100維收斂圖Fig.6 One hundred-dimensional convergence graph of 4 benchmark functions

3.2 算法的運行時間

為了檢驗MCABC 的時間復雜度，在相同的運行環(huán)境下，計算各算法的運行時間，計算得到15個算法在D=50條件下的平均運行時間如表4 所示。由表4 可以看出，由于MCABC與ABC 的時間復雜度相差不大，故在運行時間上略有增加，而MCABC相較于其他三種比較算法在運行時間上均有降低。因此，本文提出的尋優(yōu)方法在可接受的計算時間內(nèi)能夠有效提高算法的求解質(zhì)量。

表4 不同算法運行時間對比 單位：sTab.4 Running time comparison of different algorithms unit：s

4 結(jié)語

本文提出了一種基于多種群組合策略的人工蜂群算法，通過將多維匹配和異維協(xié)同兩種更新機制引入搜索方程，提高了算法更新模式的多樣性；同時，分別針對雇傭蜂和觀察蜂提出了兩個組合策略，以平衡算法的廣度探索和深度搜索，并在雇傭蜂階段劃分自由子集和非自由子集，以明確個體的搜索重點。通過對標準測試函數(shù)進行仿真實驗，進一步驗證了本文所提出的MCABC算法具有良好的尋優(yōu)性能。