基于最優個體指導單純形法改進的人工蜂群算法及應用

趙旭芳 梁昔明 龍 文

1(北京建筑大學理學院 北京102600)2(貴州財經大學經濟系統仿真貴州省重點實驗室 貴州 貴陽 550025)

0 引 言

在過去的二十年來，全局優化算法發展迅速，為解決高度復雜的優化問題，眾多受生物行為啟發的優化算法相繼被提出，這些方法通常簡單且易于實現，例如：遺傳算法、粒子群算法、蛙跳算法、人工魚群算法、人工蜂群算法等。這些算法對優化問題研究結果表明群智能優化算法對解決復雜優化問題具有巨大的潛力和優勢。人工蜂群算法ABC(Artificial bee colony algorithm)是由Karabogo在2005年提出的一種新型群體智能優化算法，全局探索能力強，能夠有效解決復雜的高維度全局優化問題[1-2]。自提出以來，由于良好的全局優化能力且控制參數少、易于實現等優點，受到研究者的關注，并且適用于許多應用領域。然而，基本人工蜂群算法同樣存在局部搜索緩慢和收斂精度低的缺點，且易陷入局部最優。為解決這些不足，研究人員提出一些改進算法，這些算法都有自己的特點和優勢，并取得優異的結果。文獻[3]利用微分算子的優勢彌補基本人工蜂群算法的局限性，從而提高算法的收斂精度和加快其收斂速度；文獻[4]受重力模型啟發，提出一種基于對立學習的多節搜索方程和一種多方偵查的搜索策略來提高算法的性能；文獻[5]提出在全局最優的指導下進行鄰域搜索且采用精英蜜蜂隨機選擇的方法代替跟隨蜂的概率選擇方法，提高收斂精度和收斂速度；文獻[6]提出基于混沌算子和相鄰選擇策略的改進算法，以平衡基本ABC算法的全局搜索和局部尋優能力；文獻[7]提出一種全球偵查方案，通過對偵查蜂的搜索策略進行預測和選擇來提高算法求解精度；文獻[8]提出在全局最優和子集合最優共同指導下的搜索策略和獨立的遺傳搜索策略，用于提高算法的全局搜索能力。目前人工蜂群算法已在多方面得到應用，文獻[9]將人工蜂群算法應用于應急調度優化問題中，使得所求出的非支配前沿解集更加多樣性；文獻[10]利用人工蜂群算法解決車輛路徑規劃問題，以減少總體的旅行距離或旅行時間，滿足綠色物流的新要求；文獻[11]對于雙級交通網絡設計問題，提出依靠人工蜂群算法來設計路線結構和下降的搜索方向，以確定給定路線結構的最佳頻率設置。本文提出一種基于當前最優個體指導的人工蜂群算法，有效結合單純形法精確的局部尋優能力和人工蜂群算法較強的全局搜索能力。經數值試驗結果表明，所得改進后的人工蜂群算法具有更快的收斂速度和更高的收斂精度。

1 基本人工蜂群算法和單純形法

對無約束連續優化問題：

minf(X)X∈RD

(1)

若X*∈RD滿足f(X*)≤f(X),?X∈RD，稱X*為f(X)在全空間RD上的全局極小點或整體極小點。

1.1 ABC原理

人工蜂群算法是模擬蜜蜂采蜜行為提出的群智能優化算法，整個搜索過程可分為：引領蜂階段、跟隨蜂階段和偵查蜂階段。開始時所有的引領蜂在對應的食物源鄰域隨機搜索新的食物源，跟隨蜂根據食物源的豐富程度進一步進行隨機搜索。在搜索過程中，貪婪的選擇機制被用于新舊食物源的選取，若經過給定迭代次數后食物源沒有得到更新，那么引領蜂將轉變為偵查蜂在搜索空間隨機搜索替換。在搜索過程中，引領蜂、跟隨蜂和偵查蜂都是重復迭代進行同樣的工作，直到達到終止條件(最大迭代次數或給定的求解精度)。

ABC算法在求解優化問題時，NP表示食物源的數量，引領蜂和跟隨蜂的個數等于食物源的數量；fiti是適應度函數值，表示食物源的豐富程度；limit是開采極限，引入計數traili。

1.1.1 初始化階段

食物源的初始種群Xi=(xi1,xi2,…,xiD)(i=1,2,…,NP)按下式在搜索空間隨機產生：

xi.j=Lmin,j+ψ(Umax,j-Lmin,j)

(2)

式中：j∈(1,2,…,D)，Umax,j和Umin,j分別表示第j維的上界和下界，ψ是(0,1)中的一個隨機數。每個食物源的適應度函數值由下式計算：

(3)

式中：fi=f(Xi)。同時設置計數器traili(i=1,2,…,NP)為0。

1.1.2 引領蜂階段

每一個引領蜂對應一個食物源，并在其周圍按下式搜索得到一個新的食物源Vi，并計算其適應度值:

vi,j=xi.j+φ(xi,j-xk,j)

(4)

式中：i=1,2,…,NP，k是隨機選擇的一只人工蜂，k∈(1,2,…,NP)且k≠i，j∈[1,2,…,D]且是隨機選擇的一維，其余所有變量都將從舊食物源中繼承，φ是(-1,1)中的一個隨機數。比較兩個食物源的適應度函數值，若新食物源的適應度值更大，則替換，同時計數器traili置0，否則保留舊食物源的位置且計數器加1。

1.1.3 跟隨蜂階段

跟隨蜂根據引領蜂提供的信息，采用輪盤賭的選擇機制選取需要更新的食物源，對每個食物源被選擇的概率按下式計算：

(5)

r是選取的[0,1]中隨機選取一個均勻分布的數，如果pi>r，那么跟隨蜂在其對應的食物源周圍按式(4)進行隨機搜索產生新的食物源。貪婪選擇機制被用于確定新舊食物源的去留，即新食物源的適應度值更大，則替換，同時計數器traili置0，否則保留舊食物源的位置且計數器加1。

1.1.4 偵查蜂階段

在所有的引領蜂和偵查蜂完成搜索后，需要檢查算法的計數器中是否有大于給定開采極限limit的值，若存在，則與之食物源對應的引領蜂就要轉化為偵查蜂，在搜索空間按式(2)隨機產生新的食物源Vi取代原有的，即：

(6)

式中：i=1,2,…,NP，j=1,2,…,D。

引領蜂、跟隨蜂和偵查蜂階段的搜索過程重復迭代直到達到給定的終止條件。通過以上過程可以看出，在基本ABC算法中，引領蜂分享信息的能力增強了蜂群之間的合作能力，跟隨蜂選擇適應度值大的食物源進行搜索可以提高算法的收斂速度，偵查蜂用于跳出局部最優解。但三種蜜蜂的搜索方案都是隨機生成的，這樣提高了搜索方案的多樣性和全局探索的能力，但也弱化了算法的局部搜索能力。而且對于跟隨蜂的搜索只是改變食物源其中的一維向量，探測能力有限，故本文針對這一現象對基本人工蜂群算法進行改進，在跟隨蜂階段引入單純形法，且以當前最好的食物源作為指導。

1.2 單純形法

單純形法是由Hest和Himsworth于1962年提出的，是一種用于直接求解無約束優化問題的算法，具有良好的局部搜索能力。算法過程簡單易于實現，通過對單純體頂點目標函數值的比較，改良單純體較劣頂點以逼近最優值。過程主要包括反射過程、擴張過程和收縮過程。以三個點為例，對函數值最小的頂點通過反射、擴張和收縮三種運算進行更新，得到更優的點。其求解流程如下：

Step1設置反射系數、擴張系數和收縮系數α、β、γ和ε，隨機生成3個頂點X1、X2、X3。

Step2計算每個頂點的目標函數值，找到目標函數值最好的、第二差的和最差的分別為Xg、Xb、…、Xw。

Step4若f(Xn+3)

Step5若f(Xg)

Step6若f(Xb)

2 改進人工蜂群算法和單純形法

基本ABC算法中，依靠蜂群之間信息分享共同完成搜索新食物源的任務，但由于引領蜂和偵查蜂的隨機搜索機制導致算法隨機性大，故算法有強的全局探索能力，但局部探索性能差。因此針對此缺陷，提出一種基于最優個體指導單純形法改進的人工蜂群算法(BABC),在跟隨蜂的局部搜索引入以當前最優個體作為指導的單純性法且在偵查蜂階段加入保優策略。基本ABC算法中的局部搜索每次只改變一維的變量，而單純形法同時可以改變多個變量，便于加大搜索范圍，更快地找到最優值。具體更新規則為：在跟隨蜂階段選取當前最優個體Xg，次優個體Xb和需要更新個體Xw作為初始頂點代入單純形法，且令α=1.4，β=0.5，γ=0.4，用單純形算法求得的Xi取代Xw。接著進行偵查蜂階段的保最優個體策略，即首先判斷達到開采極限的是否為當前最優個體，若是，則保留；若不是，按基本ABC算法的搜索機制進行，最后判斷是否達到終止條件，若達到，輸出當前最優個體。在偵查蜂階段加入的選取機制，能夠有效避免偵查蜂跳出最優值，增強算法的收斂速度和精度。改進后的人工蜂群算法流程如下：

(1) 初始階段，隨機初始化NP個食物源，分別設置參數最大迭代次數max、食物源開采極限limit和精度tol；

(2) 計算適應度函數值，執行引領蜂階段，即引領蜂在各自的食物源周圍進行隨機搜索，記錄新食物源的適應度函數值且與舊食物源的進行比較，保留豐富的食物源(適應度函數值大的)；

(3) 執行跟隨蜂階段，即根據引領蜂分享食物源豐富程度的信息(適應度函數值的大小)，跟隨蜂以輪盤賭的方式選擇搜索的食物源，然后通過以最優個體指導的單純形法進行搜索，并記錄新食物源的適應度值，采用貪婪選擇機制確定留下的食物源；

(4) 執行偵查蜂階段，即所有的引領蜂和跟隨蜂完成搜索任務后，檢測計算器traili(1,2,…,NP)中是否有大于開采極限limit，若大于開采極限則需再次判斷是否為當前最優個體，若是，則保留，反之引領蜂轉化為偵查蜂，在空間隨機搜索食物源取代；

(5) 所有的蜜蜂完成搜索任務后，判斷是否達到終止條件(終止條件是達到最大迭代次數或達到目標精度)，如果滿足終止條件，則輸出最優解，算法終止，否則轉步驟(2)。

BABC算法流程圖如圖1所示。

圖1 BABC算法流程圖

3 實驗結果與分析

為了驗證所提出的改進人工蜂群算法的性能，使用以下五個典型的無約束極小化問題進行數值試驗，具體如表1所示。

表1 五個典型的無約束優化問題

3.1 ABC算法、GABC算法和BABC算法的比較

對目標函數f1～f5，將BABC算法與基本ABC算法及文獻[12]中GABC算法在固定迭代次數下進行比較分析。GABC算法以當前最好的食物源位置作為引領蜂搜索方式的指導，以提高搜索精度。試驗中，具體參數設置如下：食物源NP取30，測試目標函數設置維數D為100，最大迭代次數2 000次，開采極限limit=300。采用MatlabR2014a實驗平臺進行數值試驗，為減少偶然性的影響，每個算法對每個測試問題進行30次獨立試驗，取試驗所得目標函數值的平均值、標準差、最大值和最小值進行對比。試驗結果統計如表2所示，且圖2-圖7分別是三種算法對不同目標函數的平均最優值進化曲線。

表2 目標函數測試結果

續表2

從表2可以看出，與ABC算法和GABC算法相比，BABC算法無論在穩定性還是所得目標函數值的精度上都有較大的提升。對目標函數f1～f6，ABC算法和GABC算法均得不到最優目標函數值，且其求解精度也不高。而BABC算法對目標函數f1、f2、f5和f6，都有較高的求解精度，且目標函數值平均值、最小值和最大值相差不是很大，說明算法穩定性很好。對目標函數f3，BABC算法求得理論最優目標函數值0；對目標函數f4，雖求得的目標函數值精度提升不大，但求的最小值達2.45e-12。

圖2 目標函數f1平均值進化曲線

圖3 目標函數f2平均值進化曲線

圖4 目標函數f3平均值進化曲線

圖5 目標函數f4平均值進化曲線

圖6 目標函數f5平均值進化曲線

圖7 目標函數f6平均值進化曲線

從圖2、圖3和圖6可以看出，BABC算法在大約1 200次迭代后趨于平緩且解達到較高精度，而ABC算法和GABC算法在迭代2 000次仍只得到精度較低的解；從圖4可以看出，BABC算法很快達到理論最優值，圖上基本顯示不出它的變化曲線，而ABC算法和GABC算法在迭代500次趨于平緩且求解精度很低；從圖5和圖7可以看出，BABC算法在迭代2 000次達到較高精度且仍在向最優解靠近。

3.2 指定精度下的迭代次數

為了進一步比較三種算法的性能，在給定精度tol=10-6下每個算法對每個測試問題進行30次獨立試驗，統計每個算法的成功率、平均迭代次數、最小迭代次數和最大迭代次數，其中成功率表示算法在30次獨立試驗中達到給定精度的次數和30的比值，維數D=100。表3為迭代次數的對比結果。

表3 迭代次數的對比結果

從表3中可以看出，在給定精度的情況下，ABC算法和GABC算法對目標函數f1～f6，迭代2 000次均沒有得到指定精度的解，成功率為0，而BABC算法除目標函數f4外，成功率為1。且所用迭代次數更少，尤其對復雜目標函數f3，平均迭代次數只需3次便得到給定精度的解，對于其他目標函數，其最小迭代次數均是兩位數，平均迭代次數均為三位數。以上結果說明，在給定精度下，BABC算法不論是成功率、穩定性還是計算效率均比其他兩種算法有很大的提升。

3.3 改變參數的優化結果

種群數目、迭代次數和開采極限是影響算法性能的主要參數，對參數的取值不同，算法的尋優效率也會有變化。為了能夠進一步了解算法的性能，設置了在不同開采極限下不同種群數在不同維度和不同最大迭代次數下的試驗。取種群數分別為20、40、60、80、100和150，開采極限為100、200和300，分別對應最大迭代次數1 000、2 000和3 000，維數取30和50，對六個測試問題進行30次獨立試驗求取目標函數的平均值，測試結果如表4所示。

表4 不同參數下算法尋優效果

續表4

從表4中可以看出，當最大迭代次數增加和開采極限改變時，BABC算法對目標函數的求解精度有所提高，當NP≥40時，BABC算法優化結果相對穩定且收斂精度較高。計算中增加迭代次數和加大群體規模更有助于算法的尋優效果，但計算量也隨之增加。因此，對一些優化問題的求解過程中，太多的迭代次數和太大的群體規模是不必要的，要選取適量的迭代次數和群體規模，在取得精度較高解的同時減少計算量，從而減少運算時間。

3.4 與其他算法求解結果對比

對六個目標函數，BABC算法與GABC算法、COABC算法[13]、ABC-best-1算法[14]、ABC-best-2算法[15]進行比較,維數取30，其他參數設置與文獻[8]一致且表中數據除BABC算法均來自文獻[16]。COABC算法通過應用前一個最佳方案來指導新的候選方案，從而提高算法的性能；ABC-best-1算法為提高算法的收斂精度生成初始種群時采用了混沌系統和基于隊里的學習方法；ABC-best-2算法在搜索中引入選擇性機制來提高算法的全局尋優速度。表5為不同改進算法尋優結果對比。

表5 不同改進算法尋優結果對比

從表5中可以看出，BABC算法對目標函數f1雖然沒有得到最優值0，但其精度很高；對目標函數f2，其目標函數值精度較ABC-best-1算法和ABC-best-2算法有很大的提升；對目標函數f3，只有BABC算法取得理論最優值0，而且其他算法求解精度均不是很高；對目標函數f4，除ABC-best-1算法外，其他四種算法均求得理論最優值；對目標函數f5，其他四種算法求解精度均很低，只有BABC算法得到精度較高的解；對目標函數f6，五種算法均得到理論最優值0。

4 改進算法在參數優化問題中的應用

近年來，智能優化算法求解模型參數優化問題越來越受到人們的關注，本文選用登革病毒傳播模型，利用BABC算法對模型參數進行優化，并與文獻[16]中選取的參數得到的模型輸出結果進行對比，結果表明BABC算法求解的參數使模型輸出和實際觀測數據之間擬合效果更好, 均方根誤差更小。

傳統登革病毒傳播模型將所有人Nh分為三部分：易感人群Sm(t)，感染人群Ih(t)，擁有抗體人群Rh(t)。所有的雌蚊Nm被分為兩部分：易感染雌蚊Sm(t)和已感染雌蚊Im(t)。模型由如下五個方程描述，考慮五個獨立變量Sh、Ih、Rh、Sm、Im：

(7)

(8)

(9)

(10)

(11)

式中：μh代表人患病后的平均死亡率，μm代表雌蚊患病后的平均死亡率，βh代表易感人群被已感染雌蚊叮咬后被傳染的概率，βm代表易感染雌蚊叮咬感染人群后被傳染的概率，b代表人被雌蚊叮咬的概率，γ代表感染人群的恢復率。

登革病毒傳播模型需要顧及六個參數μh、μm、βh、βm、b、γ，各個參數的搜索區間分別為：1e-5≤μh≤1e-4，0≤μm≤0.5，0≤βh≤1，0≤βm≤1，0≤b≤1，0≤γ≤1。

利用Caputo分數階導數：

(12)

對傳統登革病毒傳播模型進行改進，得到在Caputo分數階導數定義下的分數階非線性登革病毒傳播模型[16]：

(13)

(14)

(15)

(16)

(17)

在Caputo分數階導數定義下的分數階非線性登革病毒傳播模型需要估計六個參數μh、μm、βh、βm、b、γ以及兩個Caputo分數階導數αh和αm，它們的搜索區間分別為:1e-5≤μh≤1e-4，0≤μm≤0.5，0≤βh≤1，0≤βm≤1，0≤b≤1，0≤γ≤1，0≤αh≤1，0≤αm≤1。

為了估計登革病毒傳播模型中的參數，我們利用佛得角島上2009年登革熱疫情的實際數據作為已知數據，初始條件為：Sh(0)=55 784，Ih(0)=216，Rh(0)=0，Sm(0)=168 000，Im(0)=0，時間t=90天。

文獻[16]選取參數為μh=1/71.365，μm=0.1，βh=0.36，βm=0.36，b=0.7，γ=1/3，αh=1，αm=0.77，此時分數階非線性登革病毒傳播模型輸出結果與實際數據的均方根誤差為581。

當參數為μh=1/71.365，μm=0.1，βh=0.36，βm=0.36，b=0.7，γ=1/3時，利用BABC算法對αh和αm進行優化，求解結果為式(13)中αh= 0.999 1，式(14)中αh= 0.726 8，式(15)中αh= 0.752 4，式(16)中αm= 0.979 8，式(17)中αm= 0.915 4。此時分數階非線性登革病毒傳播模型的輸出結果與實際數據的均方根誤差為323，利用BABC算法所得參數與文獻[16]中選取參數對應的模型輸出與實際數據之間的擬合情況如圖8所示。

圖8 優化所得參數對應的模型輸出結果與實際數據的對比

BABC算法求解在Caputo分數階導數定義下的分數階非線性登革病毒傳播模型中的參數，所得參數對應的模型輸出比文獻[16]選取的模型輸出與實際數據的均方根誤差都小。

5 結 語

本文提出了一種基于最優個體指導單純形法改進的人工蜂群算法(BABC)，應用于跟隨蜂階段，以平衡算法的開發和探測能力，并且在偵查蜂階段加入一個保優策略，避免跳出全局最優，以加快收斂速度。經過6個目標測試函數的實驗數據表明，所提出的改進算法是有效的，能夠增強基本ABC算法的局部搜索能力，使得算法具有更高的求解精度。利用改進后的算法對參數進行優化，所得模型參數對應的模型輸出與實際數據擬合很好，結果表明BABC算法對這類模型參數優化問題求解的有效性。