基于非線性遞減選擇策略的人工蜂群算法*

劉文英 陳振文 蘇兆鑫 李克文

（中國石油大學(xué)（華東）計(jì)算機(jī)與通信工程學(xué)院 青島 266580）

1 引言

人工蜂群算法（Artificial Bee Colony，ABC）是群體智能優(yōu)化算法中的一種，由Karaboga于2005年提出［1］。它仿真了真實(shí)蜂群的兩種群體行為：第一種是在蜂巢周圍搜索花蜜；第二種是分享蜂巢周圍食物來源的位置信息。因其概念簡單，控制參數(shù)較少，易于實(shí)現(xiàn)等優(yōu)點(diǎn)而被廣大的研究人員所關(guān)注，許多人工蜂群算法的改進(jìn)算法也因此被提出，例如周等人將全局領(lǐng)域搜索算子引入到MABC中，從而提出了一種新的算法MABC-NS，改善了算法的性能［2］。Babaoglu I為了改善種群的停滯行為而提出了一種基于分布的更新規(guī)則，該更新規(guī)則利用本解和其鄰域解得到兩個解的均值和標(biāo)準(zhǔn)差，然后通過正態(tài)分布來產(chǎn)生新的候選解［3］。Banharnsakun A等在解搜索方程中結(jié)合了最優(yōu)選擇方法和可調(diào)搜索半徑提出了一種ABC變體以提高算法的收斂能力［4］。周等人將PSO更新機(jī)制引入ABC算法以提高算法的開發(fā)能力［5］。Karaboga D提出了qABC變體，其在跟隨蜂階段利用鄰居間的最優(yōu)解來構(gòu)造搜索方程［6］。高等人在算法中引入正交學(xué)習(xí)策略以提出了一種新的ABC更新規(guī)則［7］。K?ran M S等提出了一種利用方向信息以加快ABC收斂速度的DABC算法［8］。文獻(xiàn)［9］為探索最佳解附近的區(qū)域而提出了一種自適應(yīng)局部搜索策略，以此增加了算法的局部收斂能力。文獻(xiàn)［10］混合了粒子群算法和煙花算法并將其用在了全局優(yōu)化上。文獻(xiàn)［11~12］分別結(jié)合了粒子群優(yōu)化算法和螢火蟲算法，以形成一個綜合尋優(yōu)性能超過單個算法的混合算法。另外還有人工蜂群算法和其他算法的結(jié)合，例如文獻(xiàn)［13］將遺傳算法和ABC算法結(jié)合。

但這些人工蜂群算法大多數(shù)在雇傭蜂搜索階段采用的是完全貪婪的選擇策略且搜索無方向指引，因此存在種群多樣性降低較快，收斂速度緩慢等問題。優(yōu)化算法擁有一定的種群多樣性是大概率找到全局最優(yōu)解的基礎(chǔ)，為了在維持較高種群多樣性的情況下提高算法的局部開發(fā)能力，加快算法的收斂速度；本文提出了一種基于非線性遞減選擇策略的人工蜂群算法（Artificial Bee Colony Algorithm Based on Nonlinear Decreasing Selection Strategy，ndssABC），分別從雇傭蜂接受新解方式、跟隨蜂搜索新解方式和偵察蜂產(chǎn)生新解的方式上進(jìn)行了改進(jìn)。

2 人工蜂群算法的個體分類

在人工蜂群算法初始化之后，主要有三個階段依次迭代運(yùn)行，這三個階段分別為雇傭蜂搜索階段、跟隨蜂搜索階段和偵察蜂搜索節(jié)段。尋優(yōu)個體也被對應(yīng)的分為三種：雇傭蜂、跟隨蜂和偵察蜂。三種蜜蜂各司其職，分工完成群體的進(jìn)化活動。

1）雇傭蜂

雇傭蜂的鄰域搜索和貪婪選擇出現(xiàn)在雇傭蜂階段。在人工蜂群算法中，有一半數(shù)目的蜂種為雇傭蜂，雇傭蜂的數(shù)量又等于花蜜源的數(shù)量，表示優(yōu)化問題中的可行解，且每只雇傭蜂都唯一對應(yīng)著一個花蜜源，雇傭蜂在進(jìn)行鄰域搜索和貪婪選擇時也只在其對應(yīng)的花蜜源上進(jìn)行。單只雇傭蜂在雇傭蜂階段的尋優(yōu)并沒有同其它雇傭蜂進(jìn)行信息交互，它們的鄰域搜索和貪婪選擇都是獨(dú)立完成的。

2）跟隨蜂

跟隨蜂鄰域搜索和貪婪選擇的執(zhí)行出現(xiàn)在跟隨蜂階段。在蜂群算法中，跟隨蜂占據(jù)種群數(shù)目的另一半。跟隨蜂不唯一對應(yīng)著指定的花蜜源，在進(jìn)行鄰域搜索和貪婪選擇時是基于雇傭蜂傳遞的花蜜源質(zhì)量信息依據(jù)概率選擇要去采蜜的花蜜源。質(zhì)量較優(yōu)的花蜜源會大概率吸引多只跟隨蜂前來采蜜。

3）偵察蜂

當(dāng)有花蜜源被開采殆盡時，與其對應(yīng)的雇傭蜂遺棄該蜜源，同時其角色轉(zhuǎn)變?yōu)橐恢粋刹旆?。偵察蜂出現(xiàn)在偵察蜂階段，同雇傭蜂和跟隨蜂不同，偵察蜂并不進(jìn)行鄰域搜索和貪婪選擇，而是負(fù)責(zé)搜尋新的蜜源來替代被放棄的蜜源，待偵察蜂搜尋到新的蜜源后，其角色再變?yōu)楣蛡蚍?，并與該新蜜源唯一對應(yīng)。

在每一代的進(jìn)化中，雇傭蜂搜索階段和跟隨蜂搜索階段是必定出現(xiàn)的階段，雇傭蜂階段在前，跟隨蜂階段在后。而偵察蜂只有當(dāng)算法進(jìn)化到一定的時期、花蜜源未被改善的次數(shù)達(dá)到最大停滯次數(shù)limit時才會出現(xiàn)。

3 算法改進(jìn)策略

3.1 雇傭蜂的非線性遞減選擇策略

基本人工蜂群算法在雇傭蜂階段進(jìn)行鄰域搜索后采用的是完全貪婪策略：即只有當(dāng)雇傭蜂搜索到的候選解Vi的質(zhì)量優(yōu)于舊解Xi時才更新花蜜源位置，否則完全放棄新解Vi。新解計(jì)算公式如式（1）：

這種完全貪婪的選擇策略雖然加快了算法的收斂速度，但會導(dǎo)致種群多樣性急速下降。種群多樣性的過早喪失，使算法非常容易陷入局部最優(yōu)區(qū)域?；诖?，本文提出了一種雇傭蜂的非線性遞減選擇策略的解更新方式：若利用式（1）產(chǎn)生的候選解Vi的質(zhì)量優(yōu)于舊解Xi時，則更新花蜜源的位置并將計(jì)數(shù)器置0；否則依據(jù)式（2）和式（3）產(chǎn)生的概率PIter接受差解Vi。

其中IterMax為最大終止代數(shù)，Iter為當(dāng)前的代數(shù)。

其中pMax為雇傭蜂接受差解的最大概率，在算法初始化時設(shè)置，pMax設(shè)置較大則種群在進(jìn)化過程中能夠保持較大的種群多樣性，此時算法擁有相對較大的全局探索能力；反之pMax設(shè)置較小，則種群在進(jìn)化過程中的種群多樣性較小，算法的局部開發(fā)能力較強(qiáng)，為了平衡算法的全局勘探能力和局部開發(fā)能力，pMax通常的設(shè)置范圍為［0.3，0.8］。當(dāng)pMax設(shè)置為0時，即種群始終以0的概率接受差解，這種搜索方式相當(dāng)于完全貪婪選擇策略，也可以把完全貪婪選擇策略當(dāng)成是一種pMax為0時的特殊情況。

由式（3）可知，隨著算法迭代次數(shù)的增加，PIter從接受差解的最大概率pMax非線性遞減到0。其和線性遞減相比，該非線性遞減的方式能夠保證在種群進(jìn)化前期以高于線性遞減方式的概率接受差解，以此更大化地維持種群的多樣性，提高種群的全局勘探能力；而在種群進(jìn)化后期能以低于線性遞減方式的概率接受差解，以加速種群的收斂，提高種群的局部深挖能力。假設(shè)pMax為1、迭代次數(shù)為100代，本文提出的非線性遞減和線性遞減的具體對比如圖1所示。

圖1 線性遞減和非線性遞減對比圖

本文希望種群在進(jìn)化前期能夠維持比較大的種群多樣性，以保證算法的全局勘探能力，增加算法找到全局最優(yōu)解的概率；而在進(jìn)化后期種群多樣性迅速降低，可以使得算法快速收斂并在最優(yōu)解周圍做精細(xì)化搜索。讓算法在進(jìn)化前期擁有較大的種群多樣性而在進(jìn)化后期擁有較小的種群多樣性，非線性遞減選擇策略能比線性遞減選擇策略更適合這種需求。雇傭蜂的非線性遞減選擇策略如式（4）所示。

其中fit（Vi）和fit（Xi）分別表示新解和舊解的適應(yīng)度函數(shù)值，由目標(biāo)函數(shù)構(gòu)造而成，適應(yīng)度函數(shù)值與花蜜源解的質(zhì)量呈正相關(guān)，即適應(yīng)度函數(shù)值越大，可行解的質(zhì)量越好。由式（4）可知，當(dāng)候選解Vi的質(zhì)量優(yōu)于舊解Xi時，個體無條件接受候選解Vi；當(dāng)候選解Vi的質(zhì)量差于舊解Xi時，以一定的概率接受差解，該概率由式（3）產(chǎn)生，與進(jìn)化代數(shù)有關(guān)。

3.2 跟隨蜂的全局最優(yōu)解引導(dǎo)方式

生成新解的方程是算法的核心操作，由于基本人工蜂群算法搜索方程的無定向性，現(xiàn)有種群找到的花蜜源信息沒有被充分利用，因而種群的局部開發(fā)能力較弱［14］。為了彌補(bǔ)這種不足，本文充分利用群體的有益信息來建立新的花蜜源搜索方式以引導(dǎo)種群的進(jìn)化，進(jìn)而提高算法的尋優(yōu)性能。具體如式（5）、（6）所示。

其中rand為［0，1］之間的隨機(jī)值，IterMax為最大迭代次數(shù)，Iter為當(dāng)前迭代次數(shù)，ω為產(chǎn)生的權(quán)重值。

跟隨蜂搜索到的候選解由其跟隨的花蜜源、鄰居蜜源和目前群體找到的種群最優(yōu)解共同決定，隨著迭代的進(jìn)行搜索到的候選解有逐漸靠近種群最優(yōu)解的趨勢，增加了蜂群在種群最優(yōu)解附近的搜索機(jī)會。同時為了加快種群的進(jìn)化速度，跟隨蜂采用完全貪婪的選擇策略來決定是否要接受候選解，即當(dāng)產(chǎn)生的候選解優(yōu)于舊解時就會替換掉舊解；當(dāng)候選解差于舊解時，就保持舊解不變，不再有其他額外的判斷條件。

3.3 偵察蜂的貼近最優(yōu)解策略

隨著種群的進(jìn)化，當(dāng)有花蜜源未被改善的次數(shù)達(dá)到最大停滯次數(shù)limit時，偵察蜂出現(xiàn)，并由其尋找一個新的花蜜源來代替被遺棄的花蜜源?；救斯し淙核惴ㄖ行禄墼床捎秒S機(jī)的方式生成，以這種方式生成的蜜源往往因其質(zhì)量不高而在以后的迭代中很快被再次遺棄；因此本文利用式（7）和式（8）在原有生成新解的基礎(chǔ)上采用貼近最優(yōu)解策略來生成蜜源，以此提高生成新解的質(zhì)量。

其中j=1，2，…，D，i表示被遺棄花蜜源的坐標(biāo)，gBestj為目前群體找到的種群最優(yōu)解gBest的第j維。

采用貼近最優(yōu)解策略生成新解的方式改善了生成新解的質(zhì)量，間接地加快了種群的進(jìn)化速度。

綜上所述，在改進(jìn)的人工蜂群算法中，雇傭蜂采用非線性遞減選擇策略的方式來決定是否接受差解，增加了種群的全局勘探能力。同時為了增加種群的局部深挖能力，跟隨蜂產(chǎn)生新解的方式由全局最優(yōu)解來引導(dǎo)進(jìn)化，并保持完全貪婪的選擇策略不變。另外，為了加快種群的進(jìn)化速度，偵察蜂采用貼近最優(yōu)解的策略來生成新解，提高了生成新解的質(zhì)量。

4 ndssABC算法的主要步驟和流程

改進(jìn)后的算法主要包括四個階段：

1）初始化階段：初始化各種參數(shù)，如種群的最大迭代次數(shù)IterMax，花蜜源的最大停滯次數(shù)limit，雇傭蜂接受差解的最大概率pMax等；在D維空間內(nèi)隨機(jī)生成SN個解，表示D維空間中的第i個解；為每個蜜源設(shè)置一個計(jì)數(shù)器并置零，記錄花蜜源未被改善的次數(shù)。

2）雇傭蜂階段：每個雇傭蜂在各自對應(yīng)的花蜜源上進(jìn)行一次鄰域搜索，計(jì)算解的適應(yīng)度值。Vi為新產(chǎn)生的候選解，由舊解Xi和隨機(jī)選擇的鄰居解Xk一起產(chǎn)生，若Vi的質(zhì)量優(yōu)于原來的舊解Xi，則Xi被Vi替代，并將計(jì)數(shù)器置零；否則依據(jù)式（3）計(jì)算的接受差解的概率PIter來接受新解，且計(jì)數(shù)器加1，具體解的更新方式如式（4）所示。

3）跟隨蜂階段：每只跟隨蜂在得到雇傭蜂傳達(dá)的花蜜源豐富度信息后，計(jì)算出來的選擇概率利用輪盤賭機(jī)制選擇要去跟隨的雇傭蜂，之后跟隨蜂利用式（6）進(jìn)行鄰域搜索然后貪婪選擇，同時同雇傭蜂搜索階段一樣改變蜜源的計(jì)數(shù)器。較優(yōu)質(zhì)量花蜜源所對應(yīng)的雇傭蜂很可能會吸引較多的跟隨蜂前來采蜜。

4）偵察蜂階段：當(dāng)一個花蜜源在通過limit次鄰域搜索后，若解的質(zhì)量仍然沒有得到改善，則此蜜源被消耗殆盡；雇傭蜂放棄此蜜源并變?yōu)閭刹旆洌齻刹旆淅檬剑?）和式（8）隨機(jī)尋找到一個新的蜜源后重新變?yōu)楣蛡蚍?，并將記錄花蜜源未被改善次?shù)的計(jì)數(shù)器置零。

基于非線性遞減選擇策略的人工蜂群算法的流程圖如圖2所示。

圖2 算法流程圖

雇傭蜂階段是全局搜索，其對每個花蜜源都進(jìn)行一次鄰域搜索，然后對產(chǎn)生的新解進(jìn)行非完全貪婪式選擇；而跟隨蜂是一種不平衡的局部搜索，每只跟隨蜂依據(jù)概率選擇花蜜源進(jìn)行鄰域搜索然后再進(jìn)行完全貪婪式選擇，質(zhì)量較優(yōu)的花蜜源有可能會招募多只跟隨蜂前來采蜜；為了改善在尋優(yōu)過程中種群多樣性的過早喪失、算法停滯以及易陷入局部最優(yōu)值的問題，當(dāng)花蜜源未被改善的次數(shù)達(dá)到limit次時，偵察蜂出現(xiàn)并采用貼近最優(yōu)解的策略隨機(jī)搜索一個新的花蜜源去替換掉原來的舊蜜源。另外，通常有花蜜源的數(shù)量=雇傭蜂的數(shù)量=跟隨蜂的數(shù)量=SN；雇傭蜂和跟隨蜂的鄰域搜索只改變可行解中的某一維；每代若出現(xiàn)則最多出現(xiàn)一只偵察蜂。

5 仿真實(shí)驗(yàn)分析

為了檢驗(yàn)基于非線性遞減選擇策略的人工蜂群算法的性能，如表1所示，本文選取了8個經(jīng)典基準(zhǔn)函數(shù)來驗(yàn)證算法的收斂精度、穩(wěn)定性等性能。其中，sphere函數(shù)、rosenbrock函數(shù)、sumSquares函數(shù)、sumPower函數(shù)為單峰函數(shù)；schwefel2.26函數(shù)、rastrigin函數(shù)、ackley函數(shù)、griewank函數(shù)為多峰函數(shù)。

表1 基準(zhǔn)函數(shù)

為了對比實(shí)驗(yàn)本文選取了基本人工蜂群算法ABC和基于分布更新規(guī)則的人工蜂群算法distABC［3］做為對比算法。其中distABC算法采用原解和其鄰居解得到的均值和方差利用正態(tài)分布來產(chǎn)生新解，是近年來經(jīng)常被用來比較的優(yōu)秀算法?；墼碨N的數(shù)量設(shè)置為20；limit的數(shù)量由式（9）確定；最大迭代次數(shù)IterMax由式（10）確定。

其中NP表示種群的數(shù)量，等于2×SN，D表示求解問題的維數(shù)。除了上述參數(shù)外，本文算法中的pMax設(shè)置為0.4；distABC算法中的TSD按照其原文設(shè)置為1×10-4。

5.1 算法的收斂精度和穩(wěn)定性分析

本文所用的目標(biāo)測試函數(shù)都是求最小值的函數(shù)，可行解的目標(biāo)函數(shù)值越小，表明解的質(zhì)量越好。算法的收斂精度由多次尋優(yōu)結(jié)果的均值來驗(yàn)證，由于是求最小值，所以均值越小，算法的收斂精度越好；算法的穩(wěn)定性由多次尋優(yōu)結(jié)果的標(biāo)準(zhǔn)差來驗(yàn)證，標(biāo)準(zhǔn)差越小的算法表明其尋優(yōu)性能越穩(wěn)定。

為了減少算法的不確定性影響，每個算法在每個測試函數(shù)的30維上單獨(dú)運(yùn)行30次，然后求其平均值和標(biāo)準(zhǔn)差來分別驗(yàn)證算法的收斂精度和穩(wěn)定性。實(shí)驗(yàn)結(jié)果如表2所示，其中ndssABC表示本節(jié)提出的算法，最佳結(jié)果加粗顯示。

表2 D=30維時的測試結(jié)果

由表2可知，distABC算法在函數(shù)f2、f5上的尋優(yōu)結(jié)果差于ABC算法，在其余函數(shù)上都優(yōu)于ABC法。本節(jié)提出的算法ndssABC在函數(shù)f5上的尋優(yōu)結(jié)果略微差于其他兩個算法。在函數(shù)f1中，ndss-ABC的尋優(yōu)結(jié)果略微差于distABC算法但依舊明顯優(yōu)于ABC算法。在函數(shù)f4上，ndssABC取得了和其他算法相等的尋優(yōu)結(jié)果。在函數(shù)f3上，ABC的尋優(yōu)結(jié)果最差，ndssABC取得了和distABC相同的尋優(yōu)結(jié)果，但ndssABC的標(biāo)準(zhǔn)差最小，表明了ndss-ABC尋優(yōu)性能的穩(wěn)定性。除此之外，ndssABC在函數(shù)f2、f6、f7、f8上都取得了明顯的最優(yōu)結(jié)果。

通過對比實(shí)驗(yàn)分析，本節(jié)所提出的改進(jìn)算法在大多數(shù)測試函數(shù)中能取得較好的尋優(yōu)結(jié)果且穩(wěn)定性較好，尤其在一些多峰函數(shù)中；這是因?yàn)樵诒竟?jié)提出的算法中，雇傭蜂在進(jìn)化前期以較大的概率接受差解以保持種群的多樣性，進(jìn)而盡可能地抑制了種群出現(xiàn)早熟現(xiàn)象，增加了種群的全局尋優(yōu)能力；而在進(jìn)化后期，雇傭蜂以較小的概率接受差解和跟隨蜂的全局最優(yōu)引導(dǎo)方式都提高了種群的進(jìn)化速度，加速了種群的收斂。綜合來看，本文算法具有相對較優(yōu)異的優(yōu)化性能。

5.2 種群多樣性的分析

種群多樣性是評價算法優(yōu)劣性的一個重要指標(biāo)，若種群在進(jìn)化中能擁有良好的種群多樣性則表明其有較強(qiáng)的避免早熟收斂，跳出局部最優(yōu)解的能力。本文借鑒彭等提出的多樣性評估方法［15］，提出本文所用的種群多樣性測試方法如式（11）所示。

其中，SN代表花蜜源的數(shù)量；L代表搜索域的最大對角線長度；D代表問題的維數(shù)；表示第i個蜜源第j維的值；表示第j維的平均值。采用式（11）測得的種群多樣性范圍屬于［0，1］。

其中測試維度D為30維，最大迭代次數(shù)Iter?Max為3500次，為了不影響算法的搜索速度，種群多樣性測驗(yàn)每隔500代計(jì)算一次。為了減少算法不確定性的影響，每個算法獨(dú)立運(yùn)行30次，然后取其平均值，測試結(jié)果如表3所示。其中ABC表示基本人工蜂群算法，ndssABC表示本節(jié)提出的基于非線性遞減選擇策略的人工蜂群算法。

表3 種群多樣性測試結(jié)果

通過表3可知，由于算法在開始時都是采用隨機(jī)初始化的方式，故在第0代時的種群多樣性大小相似。在大部分函數(shù)中，基本ABC算法在進(jìn)化至500代時種群多樣性就迅速衰減，這是由于基本ABC算法無論是雇傭蜂階段還是跟隨蜂階段都是采用完全貪婪的選擇策略；而本文算法由于在雇傭蜂階段采用的是非線性遞減的選擇策略，在種群進(jìn)化前期雇傭蜂以較大的概率接受差解，因此種群多樣性下降緩慢。在進(jìn)化中期算法在部分函數(shù)上的種群多樣性有輕微上升的趨勢，這是因?yàn)槠渲杏胁糠只墼吹挠?jì)數(shù)器已達(dá)到limit次，標(biāo)志著該蜜源已被開采殆盡，因而被遺棄，此時，偵察蜂搜索新蜜源來代替被遺棄的舊蜜源，種群多樣性因此得到略微的提高。本文算法在進(jìn)化后期種群多樣性較低，這是因?yàn)榇藭r雇傭蜂以較小的概率來接受差解；另外，跟隨蜂由全局最優(yōu)解來引導(dǎo)進(jìn)化也加速了種群的收斂，提高了算法在全局最優(yōu)解附近的深挖能力。

從一個進(jìn)化周期來看，在進(jìn)化前期由于雇傭蜂采用非線性遞減的選擇策略以較大概率接受差解因而能夠很好地維持種群多樣性，提高了算法的全局勘探能力；在進(jìn)化后期雇傭蜂接受差解的概率降低、跟隨蜂采用全局最優(yōu)解來引導(dǎo)進(jìn)化，因此算法有很好的局部開發(fā)能力，較優(yōu)的收斂精度?？傊蛡蚍潆A段的非線性遞減選擇策略，跟隨蜂的全局最優(yōu)解引導(dǎo)方式和偵察蜂的貼近最優(yōu)解策略很好地平衡了算法的全局勘探能力和局部開發(fā)能力，使改善后的算法擁有相對較優(yōu)異的優(yōu)化性能。

6 結(jié)語

針對基本人工蜂群算法種群多樣性下降較快導(dǎo)致全局勘探能力較弱、易陷入局部最優(yōu)等不足，本節(jié)提出了一種基于非線性遞減選擇策略的人工蜂群算法。在該算法中，雇傭蜂采用非線性遞減選擇策略以一定的概率來接受差解，以此改善種群多樣性喪失較快的問題，使得種群的搜索領(lǐng)域變廣，增加了算法的全局勘探能力；跟隨蜂采用鄰居解和種群最優(yōu)解共同引導(dǎo)個體進(jìn)化的方式，充分利用了種群到目前為止找到的有益信息，加速了種群進(jìn)化，提高了種群的局部開發(fā)能力；當(dāng)有蜜源未被改善的次數(shù)達(dá)到最大停滯次數(shù)limit時，為了盡可能地防止隨機(jī)初始化后的新解因其質(zhì)量不高而很快地被再次淘汰掉，對種群的進(jìn)化沒有起到實(shí)質(zhì)性的促進(jìn)作用，偵察蜂采用貼近最優(yōu)解的策略以提高產(chǎn)生新解的質(zhì)量。三者共同進(jìn)化使得算法能夠很好地平衡種群的全局勘探能力和局部開發(fā)能力。最后在4個單峰函數(shù)和4個多峰函數(shù)上的測優(yōu)結(jié)果表明了本文算法的優(yōu)越性。