維適應人工蜂群算法的研究

趙 明,焦劍如,宋曉宇,高怡臣

1(沈陽建筑大學 計算機科學與工程學院,沈陽 110168)

2(沈陽燃氣有限公司 技術信息部,沈陽 110005)

0 引 言

群體智能優化算法,通過智能體之間簡單的相互作用所產生的智能全局行為使得群體具有求解復雜問題的能力[1],由于其在各種優化問題中比確定性算法性能好、速度快,從而在許多應用學科中非常流行,學者研究出了各種群體智能優化算法[2].其中,人工蜂群(Artificial Bee Colony,ABC)算法是一種建立在蜜蜂自組織型和群體智能基礎上的優化算法,是Karaboga受蜜蜂智能采蜜行為的啟發于2005年提出的[3],由于其參數簡單、易于求解和性能優異等特點[4],在解決諸多實際優化問題中被成功應用,如生產調度、圖像分割、路徑規劃、組合優化、參數選擇和連續優化等領域[5-10].

與其他優化算法一樣,基本ABC算法也有不足之處,由于其擅長探索而不擅長開發,因此往往收斂速度較慢[11].相關學者從改進維數方面對基本ABC算法進行了研究,例如:Chu等人提出每次對解的所有維進行改進,通過對鄰域的全方位探索提高了搜索效率[12];Gao等人發現改進維數直接影響著不同問題的優化效果,并引入參數對不同優化問題的改進維數進行控制,但需要事先基于實驗進行測定然后才能進行設置[13];Li等人受差分進化算法的啟發,在跟隨蜂階段基于食物源搜索失敗的次數設置改進維數,次數越多維數越少,以此增強局部開發能力,對改進維的選擇采用隨機方式進行,沒有采用當前種群進化信息進行指導[14].

以上研究及其成果表明,對不同的問題進行優化時,適用的改進維數會存在差異,而且對改進維的選擇也直接影響著算法的性能.因此,為了使ABC算法能夠根據不同優化問題以及不同優化階段,適應地確定需要改進的維數,基于以上啟發,本文首先提出一種基于改進維數成功歷史檔案的適應機制,不再單一的選擇幾維或者全維進行搜索,而是基于構建的改進維數成功歷史檔案動態設置,使得算法能夠隨著具體問題的優化過程適應到適合的改進維數,從而提高解的改進成功率;在此基礎上,以一定比例引入到當前最優解的歐式距離信息智能指導跟隨蜂對要改進維的選擇,使得算法能夠根據不同優化問題的不同搜索過程自動適應到有潛能的維進行搜索,從而提升算法性能以加快收斂速度.最后,采用CEC2014基準測試函數集對提出算法的有效性和優越性進行驗證分析.

1 基本ABC算法

基本ABC算法是由食物源、雇傭蜂和非雇傭蜂(包括跟隨蜂和偵查蜂)3部分組成.一只雇傭蜂對應一個食物源,即二者數量相等,且為種群規模NP的一半,種群的另一半為跟隨蜂.雇傭蜂的任務是發現食物源信息并與跟隨蜂分享,跟隨蜂獲取信息后采用輪盤賭選擇食物源并對其進行開發.如果某食物源在限定次數后仍未被更新,相應的雇傭蜂變成偵查蜂在蜂巢附近搜索新的食物源代替原來的食物源.整個蜂群的目標就是找到花蜜量最大的食物源.

在初始化階段,ABC算法使用公式(1)隨機對食物源進行初始化.初始化食物源就相當于初始化問題的一個解.食物源數量(也是雇傭蜂數量和跟隨蜂數量)用SN表示(SN=NP/2),種群的第i個食物源用Xi表示.Triali代表嘗試被搜索改進的次數,limit代表預先設置的食物源嘗試被改進的最大次數.

(1)

然后,基于最小優化問題采用公式(2)計算食物源的適應度值.Xi的適應度值用fiti表示,f(Xi)代表優化問題中食物源Xi的目標函數值(根據具體優化問題的優化目標進行計算).

(2)

在雇傭蜂搜索階段,每個食物源的雇傭蜂均采用公式(3)在其附近進行搜索.

(3)

其中,Vi表示搜索到的新食物源,G表示代數,j表示隨機選取的改進維度,Xk表示從種群中隨機選取且與Xi不同的食物源,φij是范圍為[-1,1]隨機實數.

雇傭蜂搜索結束后對原食物源和新食物源進行比較,從中選擇更優質的保留并與跟隨蜂分享.此時,若食物源Xi更新成功,則Triali值設置為0,否則增1.

在跟隨蜂搜索階段,每個跟隨蜂利用輪盤賭選擇一個食物源,食物源被選擇的概率根據公式(4)計算出來:

(4)

其中,Pi為Xi被選擇的概率,與該食物源的適應度值成正相關,食物源越好被選擇的概率越大.

跟隨蜂選擇食物源后,采用公式(3)對其進行改進搜索,并于搜索后在原食物源和新食物源之間進行貪婪選擇,同時設置相應食物源的Triali值.

最后是偵查蜂搜索階段,將食物源中最大的Triali值與limit進行比較,如果達到則表明此食物源在設定的搜索次數內沒有變得更好,那么這個食物源會被放棄,其雇傭蜂變成偵查蜂并根據公式(1)隨機生成一個新的食物源.

基本ABC算法的終止條件有兩個:找到可接受解或達到最大函數評價次(maxFEs).

2 維適應的人工蜂群算法

2.1 搜索方程設計

雇傭蜂階段采用的搜索方程如公式(5)所示:

(5)

其中,Xr1、Xr2、Xr3從種群中隨機選取的3個不同食物源,且均與Xi不同,φij是范圍為[-1,1]隨機實數.

從公式(5)可以看出,雇傭蜂是圍繞隨機選擇的且與當前食物源不同的食物源進行改進搜索,并基于另外兩個隨機選擇的不同食物源與其的差向量進行引導.由于式中采用了3個不同的食物源組合進行搜索,可以充分利用當前種群的多樣性信息,使其具有更好的搜索能力.

跟隨蜂階段采用的搜索方程如公式(6)所示:

(6)

其中,Xk是通過輪盤賭選取的食物源,所以選中好解的概率大,Xr1、Xr2是隨機選取的兩個不同食物源,且均Xk與不同,φij是范圍為[-1,1]隨機實數.

從公式(6)可以看出,跟隨蜂圍繞著輪盤賭選取的食物源進行搜索,利用兩個隨機選擇且不同的食物源的差向量進行擾動.算法迭代搜索初期,Xr1和Xr2的差異較大,此時搜索步長(搜索步長由第2項的差值決定)也較大,側重于探索;到了算法迭代搜索后期,兩者之間的差異很小,此時搜索步長也很小,側重于開發.因此,跟隨蜂可以利用搜索步長的動態變換實現求解過程逐步由探索轉為開發.

2.2 改進維數的適應機制

相關研究發現,不同的優化問題適用的改進維數有所不同,而且,隨著算法搜索過程的進行,其搜索重點應由探索轉向開發,因而不同的搜索階段適用的改進維數也會發生變化.因此,引入了基于成功歷史檔案的維數適應機制,通過建立改進維數的成功歷史檔案,記錄當前優化過程中成功對食物源進行改進的維數信息,在此基礎上利用高斯分布設置下一代人工蜂搜索時改進的維數,保證改進維數對不同問題的適應性,同時保持適度隨機性.

成功歷史檔案的應用過程如下:在算法初始化階段,創建維數成功歷史檔案succ_arch,其規模為H,用于存儲人工蜂每代更新食物源時使用的維數比例DNR的加權均值,檔案中每個項目的初值均設置為0.5.每代人工蜂搜索時,累計本代成功更新食物源的次數success,并采用success_DNR記錄本代每次成功更新食物源時的所有維數比例.當下一代人工蜂對食物源進行改進時,隨機在成功歷史檔案里選擇一個值,并基于該值利用高斯分布生成本次更新使用的維數比例DNRi,此外,若本次成功更新,將DNRi保存到本代的success_DNR中,并將本次食物源改進的程度記錄到sigma_fi中.每代人工蜂搜索結束后,采用公式(7)計算本代成功改進時的維數比例加權均值DNRG,并用其替代成功歷史檔案中index位置的值,初始時index=0,以后index=(index+1)modH,從而實現檔案項目的實時依次更新.

(7)

從公式(7)可以看出,使用食物源改進程度作為權值進行均值計算,能夠突出改進程度大的食物源更新時使用的維數信息,因而可以達到更好的指導作用.

同時,在利用成功改進維數歷史信息的基礎上,確保具有一定隨機性和適應性,人工蜂在確定改進維數時首先從成功歷史檔案的H個值中隨機選取一個記作muDNR,然后利用如公式(8)所示的高斯分布產生本次搜索的維數比例值DNRi.

DNRi=gaussrand(muDNR,0.2)

(8)

公式(8)中,高斯分布參數設置為0.2,目的是使得產生的值較為集中的分布在muDNR附近,以充分利用成功信息保證改進解的成功率.

2.3 維選擇的適度指導機制

在確定改進維數比例的基礎上,雇傭蜂階段對于改進維的選擇全部隨機進行,來保證算法的探索能力.同時,為了提高開發能力以便加快收斂速度,跟隨蜂階段將改進的維分為兩個相等的部分,一半隨機進行維的選擇,另一半則按所選個體與當前最優解的歐式距離進行選擇,即利用當前最優解的信息對維選擇進行指導.

跟隨蜂選中的食物源Xk在j維距離當前最優解Xbest的歐式距離如公式(9)所示:

Edj(Xk)=|Xkj-Xbest j|

(9)

跟隨蜂根據基于成功歷史檔案和高斯分布生成的本次改進維數比例DNRi確定改進的維數為DNRi×D,然后根據公式(9)計算其選中食物源Xk每一維與當前最優解Xbest的距離,并依據計算結果從大到小的原則選擇一半數量的維,另一半從剩下的維中隨機選取.

2.4 算法流程和步驟

步驟1.初始化算法參數,包括NP、D、limit、maxFEs和H,采用公式(1)初始化種群X,初始化成功歷史存儲succ_arch.

步驟2.采用公式(2)計算初始種群中食物源的適應度值.

步驟3.雇傭蜂搜索階段.每個雇傭蜂根據成功歷史檔案和公式(8)高斯分布確定改進的維數,并隨機選擇改進的維,采用公式(5)搜索新食物源,計算新食物源的適應度值,依據貪婪選擇策略保留食物源,并設置相應的Trial值.若食物源更新成功,記錄改進維數比例以及解改進程度信息.

步驟4.跟隨蜂搜索階段.采用公式(4)計算每個食物源的選擇概率,每個跟隨蜂采用輪盤賭選擇要改進的食物源,根據成功歷史檔案和公式(8)高斯分布確定改進的維數,其中,一半數量的維根據公式(9)計算每一維到當前最優解的歐式距離從大到小確定,另一半隨機選取.然后,跟隨蜂采用公式(6)搜索新食物源,計算新食物源的適應度值,依據貪婪選擇策略保留食物源,并設置相應的Trial值.若食物源更新成功,記錄改進維數比例以及解改進程度信息.

步驟5.成功歷史檔案更新.采用公式(7)計算本代成功更新解時的加權平均維數比例并更新歷史檔案.

步驟6.偵查蜂搜索階段.若某食物源經過限定次數后仍舊未被更新,則該食物源被放棄,該食物源的雇傭蜂變成偵查蜂,采用公式(1)隨機初始化一個新的食物源代替該食物源.

步驟7.判斷是否滿足結束條件,若滿足,算法結束;否則重復步驟2～步驟6.

步驟8.輸出最優解.

維適應人工蜂群(Dimension-Adaption Artificial Bee Colony,DAABC)算法流程如圖1所示.

圖1 DAABC算法的流程圖Fig.1 Flow chart of DAABC algorithm

2.5 時間復雜度分析

初始化階段:對種群的初始化,DAABC與基本ABC相同,時間復雜度為O(NP×D);DAABC需要對成功歷史檔案進行初始化,時間復雜度為O(H),根據本文實驗參數設置部分的討論H設置為D,因此時間復雜度為O(D);對食物源的適應度值的計算,DAABC與基本ABC相同,時間復雜度為O(NP×D).

雇傭蜂搜索階段:DAABC根據成功歷史檔案利用高斯分布確定改進的維數,最大改進的維數為D,因此時間復雜度為O(D);利用搜索方程對食物源進行改進搜索時,DAABC一般進行多維搜索,由于最大維數為D,因而時間復雜度為O(NP×D);DAABC需在食物源更新成功時記錄改進相關信息,時間復雜度為O(NP).

跟隨蜂搜索階段:對食物源的選擇概率進行計算,DAABC與基本ABC相同,時間復雜度為O(NP);DAABC根據成功歷史檔案確定改進的維數,最大改進維數為D,時間復雜度為O(D);DAABC跟據改進維數對維進行選取時,首先計算各維距離當前最優解的距離并排序,時間復雜度為O(D×log(D)),對要改進的維進行選取時,時間復雜度為O(D);利用搜索方程對食物源進行改進搜索時,DAABC一般進行多維搜索,由于最大維數為D,因而時間復雜度為O(NP×D);DAABC需在食物源更新成功時記錄改進相關信息,時間復雜度為O(NP).

偵查蜂搜索階段:DAABC與基本ABC相同,時間復雜度為O(NP).

通過以上分析可以看出,DAABC與基本ABC相比較,整個算法在各階段額外增加的時間復雜度量級分別為O(D)、O(NP)、O(D×log(D))和O(NP×D),D通常小于NP,因而整個算法的時間復雜度最大量級仍為O(NP×D),與基本ABC相同.

3 實驗結果與分析

3.1 測試函數集以及參數設置

本文采用的CEC2014測試函數集包含30個基準測試函數,搜索空間為[-100,100],其中f1～f3是單峰函數、f4～f16是簡單的多峰函數、f17～f22是混合函數、f23～f30是復合函數.表1中列出了每個函數的序號、名稱以及取值范圍[15].

表1 測試函數集Table 1 Benchmark function set

本文選取了當前國內外ABC改進算法研究中性能先進的算法與提出算法進行對比,包括APABC[16]、DFSABC_elite[17]、ABCLGII[18]、ECABC[19]和ARABC[20].參數設置如表2所示.需要特別說明的是,對比算法的參數設置均為其提出文獻的設置,算法公共參數maxFEs均設置為10000×D.

表2 所有ABC算法的參數表Table 2 Parameter table of all ABC algorithms

3.2 實驗結果及對比分析

3.2.1 均值與標準差

D=30時,每個算法分別獨立運行30次,統計求解獲得的最優值的均值和標準差,其結果如表3所示.表3中對每個函數在所有算法中最好的結果進行加粗突出顯示.

表3 30維均值和方差實驗結果列表Table 3 Experimental results of mean and standard deviation with D=30

從表3中可以看出,與其它5個改進的ABC算法相比,DAABC在30個基準函數測試結果中有15個表現最好,APABC、DFSABC_elite、ABCLGII、ECABC和ARABC分別有3個、6個、5個、4個和1個,從數量上DABC顯著高于其他對比算法.另外,對于f1、f4、f5、f9、f10、f11、f12、f13、f14、f16、f24、f25、f27、f28,DAABC雖然略低于其它5個算法中最優均值,但是求解結果具有相同的數量級,說明算法的性能相差不大,只有f2效果稍差.綜合來看,DAABC在求解精度和魯棒性上明顯優于其它改進算法.

為了進一步驗證DAABC的優越性,對表3中算法求解優化函數的均值數據采用SPSS進行非參數檢驗,包括Wilcoxon檢驗和Friedman檢驗,檢驗結果如表3后兩行所示.利用Wilcoxon檢驗把5個對比算法與DAABC兩兩進行非參數檢驗,檢驗結果p值均小于0.05,說明它們與DAABC存在顯著性差異,即DAABC顯著優于這5個算法.利用Friedman對6個算法進行非參數檢驗,秩排名ARABC>APABC>ECABC>ABCLGII>DFSABC_elite>DAABC,說明DAABC表現最好,并且p值遠遠小于0.05,說明DAABC與5個對比算法存在顯著差異,即DAABC顯著優于其它改進算法.

3.2.2 收斂能力

為了進一步檢驗算法的收斂能力,從DAABC算法并非表現最優的函數中選取12個繪制收斂圖,如圖2所示,其中橫軸表示函數評價次數,縱軸表示最優解以10為底的對數值.

圖2 30維時部分函數的收斂圖Fig.2 Convergence diagrams of partial functions with D=30

從圖2可以看出,即使與其他5個算法相比,DAABC算法在這些函數上并非表現最好,但收斂速度更快或相似,尤其可以看出,在算法搜索最初,DAABC由于沒有適應到適合的維數及維,收斂不是最快,但隨著搜索的繼續,其一直保持著向最優解收斂的能力,不易陷入局部最優.

3.3 參數討論

本文提出算法在設立成功歷史檔案時新引入了參數H,因而,為了分析H對性能的影響,為DAABC設置不同大小的H值并分別獨立運行30次,均值和標準差的結果如表4所示.

表4 不同大小H的實驗結果Table 4 Experimental results of H with different sizes

從表4可以看出,對于7種H參數從D/2～3D范圍內的設置,在30個優化函數中除了f6、f8、f10、f11和f29這5個函數外的25個函數上,均值都在相同數量級,說明差異不大.在f6上,只有H=D/2和25表現比其他設置差;在f8、f10和f11上,只有H=3D比其他設置差;在f29上,H=D和H=3D/2比其他設置好.由此可以看出,雖然H=3D在12個函數上獲得了最好均值,但與其他設置在相同數量級差距不大,于此同時,其在3個函數上表現明顯低于其他設置,說明當H較大時會由于成功歷史檔案更新不及時而導致性能的不穩定.此外,H較小為D/2或25時,有1個函數因為成功歷史檔案更新過快表現較差.而在H在D～5D/2范圍內時,差距不大,因此綜合考慮節省程序使用輔助空間因素,建議H的設置為D.

4 結 論

為了解決基本ABC算法后期精度不高、收斂速度慢的問題,本文提出了一種維適應的人工蜂群算法,通過建立維數成功歷史檔案使得算法能夠隨著收斂過程自動適應到合適的改進維數,提高了解改進的成功率,同時在改進維選擇中適度采用當前最優解進行指導,使得算法能夠自動適應到更有潛能的維進行搜索,增強了收斂能力.在CEC2014基準測試集的實驗結果以及相應的Wilcoxon和Friedman統計檢驗表明,本文提出的算法與當前5個先進的改進ABC算法相比,具有顯著優越的求解精度、魯棒性和收斂能力.下一步研究主要考慮將本文提出的算法應用到實際工程問題中,進一步驗證其在處理實際問題的優越性.