趙旭芳 梁昔明 龍 文

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

0 引 言

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

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

對無約束連續(xù)優(yōu)化問題：

minf(X)X∈RD

(1)

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

1.1 ABC原理

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

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

1.1.1 初始化階段

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

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

(2)

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

(3)

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

1.1.2 引領(lǐng)蜂階段

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

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)中的一個隨機數(shù)。比較兩個食物源的適應(yīng)度函數(shù)值，若新食物源的適應(yīng)度值更大，則替換，同時計數(shù)器traili置0，否則保留舊食物源的位置且計數(shù)器加1。

1.1.3 跟隨蜂階段

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

(5)

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

1.1.4 偵查蜂階段

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

(6)

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

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

1.2 單純形法

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

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

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

Step4若f(Xn+3)

Step5若f(Xg)

Step6若f(Xb)

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

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

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

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

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

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

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

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

圖1 BABC算法流程圖

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

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

表1 五個典型的無約束優(yōu)化問題

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

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

表2 目標函數(shù)測試結(jié)果

續(xù)表2

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

圖2 目標函數(shù)f1平均值進化曲線

圖3 目標函數(shù)f2平均值進化曲線

圖4 目標函數(shù)f3平均值進化曲線

圖5 目標函數(shù)f4平均值進化曲線

圖6 目標函數(shù)f5平均值進化曲線

圖7 目標函數(shù)f6平均值進化曲線

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

3.2 指定精度下的迭代次數(shù)

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

表3 迭代次數(shù)的對比結(jié)果

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

3.3 改變參數(shù)的優(yōu)化結(jié)果

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

表4 不同參數(shù)下算法尋優(yōu)效果

續(xù)表4

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

3.4 與其他算法求解結(jié)果對比

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

表5 不同改進算法尋優(yōu)結(jié)果對比

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

4 改進算法在參數(shù)優(yōu)化問題中的應(yīng)用

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

傳統(tǒng)登革病毒傳播模型將所有人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代表人被雌蚊叮咬的概率，γ代表感染人群的恢復(fù)率。

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

利用Caputo分數(shù)階導(dǎo)數(shù)：

(12)

對傳統(tǒng)登革病毒傳播模型進行改進，得到在Caputo分數(shù)階導(dǎo)數(shù)定義下的分數(shù)階非線性登革病毒傳播模型[16]：

(13)

(14)

(15)

(16)

(17)

在Caputo分數(shù)階導(dǎo)數(shù)定義下的分數(shù)階非線性登革病毒傳播模型需要估計六個參數(shù)μh、μm、βh、βm、b、γ以及兩個Caputo分數(shù)階導(dǎo)數(shù)αh和αm，它們的搜索區(qū)間分別為: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。

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

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

當(dāng)參數(shù)為μh=1/71.365，μm=0.1，βh=0.36，βm=0.36，b=0.7，γ=1/3時，利用BABC算法對αh和αm進行優(yōu)化，求解結(jié)果為式(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。此時分數(shù)階非線性登革病毒傳播模型的輸出結(jié)果與實際數(shù)據(jù)的均方根誤差為323，利用BABC算法所得參數(shù)與文獻[16]中選取參數(shù)對應(yīng)的模型輸出與實際數(shù)據(jù)之間的擬合情況如圖8所示。

圖8 優(yōu)化所得參數(shù)對應(yīng)的模型輸出結(jié)果與實際數(shù)據(jù)的對比

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

5 結(jié) 語

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