優化高維復雜函數的改進人工蜂群算法

王志剛，王明剛

(南京師范大學泰州學院數學科學與應用學院，江蘇 泰州 225300)

優化高維復雜函數的改進人工蜂群算法

王志剛，王明剛

(南京師范大學泰州學院數學科學與應用學院，江蘇 泰州 225300)

[摘要]針對人工蜂群算法傳統搜索策略在求解高維復雜函數時收斂速度較慢、容易陷入局部最優的缺陷，提出了一種改進的人工蜂群算法(IABC).該算法在引領蜂的搜索策略中借鑒了差分進化算法DE/best/1變異操作模式；在跟隨蜂的搜索策略中借鑒了生物界中雁群的飛行特征，同時基于目標函數值進行選擇尋優，能較好地平衡局部搜索能力和全局搜索能力.通過對15個基準函數的仿真實驗及與其他改進算法進行比較，發現該算法具有較快的收斂速度和較高的求解精度.

[關鍵詞]人工蜂群算法；差分進化算法；雁群飛行；搜索策略

0引言

人工蜂群[1](Artificial Bee Colony，ABC)算法是由Karaboga在2005年提出的一種比較新穎的群體智能優化算法.目前，該算法已在眾多領域得到了廣泛的應用[2-5]，并取得了較好的實驗結果.但在ABC算法中，引領蜂和跟隨蜂所采用的搜索策略在求解高維復雜函數時存在著過早收斂、容易陷入局部最優、求解精度不高等缺點.針對這些問題，許多專家們提出了不同的搜索策略來改善算法的性能[6-13].例如：文獻[6]通過引入Rosenbrock旋轉方向的辦法對引領蜂的搜索策略進行改進，提高了算法的收斂速度；文獻[7]受粒子群算法的啟發，在原有搜索策略的基礎上融入全局最優解的信息來提高算法的局部搜索能力；文獻[8]采用混沌映射和反向學習理論初始化種群，然后引入差分變異和一個平衡選擇2種搜索機制的概率以提高算法的全局進化性能；文獻[9]在ABC算法的搜索策略中通過引入一個擾動概率參數和自適應尺度因子來對ABC算法進行改進；文獻[10]在差分進化思想的啟發下，提出了ABC/best算法；文獻[11]中引領蜂和跟隨蜂在執行搜索策略時按照一定的選擇概率從5種不同的搜索策略中選取其中一種策略進行搜索；文獻[12]提出了一種具有自適應全局最優引導快速搜索策略的人工蜂群算法；文獻[13]受分治策略的啟發，提出一種基于分治策略的改進人工蜂群算法.

本文提出一種改進的人工蜂群算法，該算法對ABC算法原有搜索策略做了相應改進：在引領蜂的搜索策略中借鑒差分進化算法中DE/best/1變異操作模式；在跟隨蜂的搜索策略中借鑒自然界中雁群的飛行特征，同時利用目標函數值進行選擇操作.新的搜索策略能夠平衡算法的局部搜索能力和全局搜索能力，加快算法的收斂速度，提高尋優精度.為驗證本文算法的性能，在15個典型的benchmark函數上進行了仿真實驗，并與ABC算法和5種不同類型的改進算法進行了對比.實驗結果表明，新算法不僅具有較強的全局搜索能力，而且具有較強的局部搜索能力，在收斂速度和解的精度上均有較大優勢.

1人工蜂群算法

在ABC算法中，人工蜂群包含引領蜂、跟隨蜂和偵察蜂3種.ABC算法在求解優化問題時，食物源代表優化問題的一個可能解，蜂群采蜜(食物源)的過程也就是搜尋優化問題最優解的過程.食物源的優劣取決于優化問題的適應值，適應值高的食物源較優.ABC算法中解的個數(SN)等于引領蜂或跟隨蜂的個數.用xi=(xi1，xi2，…，xiD)表示第i個食物源(i=1，2，…，SN，D為搜索空間的維數).人工蜂群搜索食物源的過程：(1)引領蜂對當前食物源進行鄰域搜索，產生候選食物源，并通過貪婪選擇較優的食物源；(2)跟隨蜂根據引領蜂分享的信息選擇一個食物源，進行鄰域搜索產生候選食物源，并通過貪婪選擇較優的食物源；(3)引領蜂放棄食物源，變為偵察蜂，并隨機搜索新的食物源.

引領蜂和跟隨蜂根據

vij=xij+φij(xij-xkj)

(1)

在食物源的鄰域生成一個候選食物源.式中：vij是生成的候選食物源，k∈{1，2，…，SN}，j∈{1，2，…，D}，k和j這2個數都是隨機選取的，但k≠i，φij是[-1，1]上均勻分布的隨機數.(1)式稱為ABC算法的搜索策略.

跟隨蜂通過

(2)

概率來選擇食物源.式中fiti為第i個食物源的適應值.在最小化問題中，fiti與優化問題目標函數值fi的對應關系為

(3)

在ABC算法中，如果連續經過limit次循環之后食物源仍然沒有得到更新，則引領蜂就放棄食物源，轉變為偵察蜂，并按

(4)

2改進的人工蜂群算法(IABC)

2.1ABC算法中搜索策略的不足

在ABC算法的搜索策略中主要存在2個問題：(1)搜索策略(1)式中含有j，k和φij3個隨機項，這使得算法在搜索過程中有更多的不確定性，雖然具有較好的全局搜索能力，但局部搜索能力不足，導致算法存在著收斂速度慢、求解精度低的問題[7]；(2)在ABC算法中，引領蜂負責在特定的范圍內搜索食物源，并將搜索到的信息共享給跟隨蜂，跟隨蜂選擇較好的食物源做進一步的搜索，以便找到更好的食物源，而引領蜂和跟隨蜂使用相同的搜索策略與算法模擬蜂群采蜜的過程相矛盾[12].

2.2新的搜索策略

針對ABC算法搜索策略存在的不足，我們對ABC算法中引領蜂和跟隨蜂的搜索策略做相應改進.

2.2.1引領蜂的搜索策略

為提高算法的局部搜索能力，加快收斂速度，借鑒差分進化算法中DE/best/1的變異操作模式[8]，將式(1)變為

vij=xbest，j+φij(xrj-xkj).

(5)

其中：xbest，j為種群的全局最優解；r，k∈{1，2，…，SN}，j∈{1，2，…，D}，且r≠k≠i.

(5)式在種群的全局最優解附近產生候選食物源，通過種群的全局最優解來引導種群的搜索軌跡，加快算法的收斂速度，以增強算法的局部搜索能力.因此，把(5)式作為新算法中引領蜂的搜索策略.

2.2.2跟隨蜂的搜索策略

雁群在飛行時常常呈現“人”字形或“一”字形，其中頭雁扇動雙翼產生尾渦，后面尾隨的大雁借力飛行，雁群中最強壯的大雁往往作為頭雁，其他大雁依次往后排[14].借鑒雁群的這種飛行特征，可以把大雁的強壯程度視為食物源的優劣，將食物源按照適應值的優劣進行排序，把最優的食物源作為頭雁，剩余的依次往后排，跟隨蜂在食物源xi附近按照

vij=xi-1，j+φij(xi-1，j-xkj)

(6)

產生候選食物源.其中xi-1為按照食物源的適應值優劣排在xi前的食物源.(6)式在產生候選食物源時可以充分利用整個種群的信息，避免了所有候選食物源都在種群的全局最優解附近產生，這有利于在搜索過程中找到更優秀的個體，增強了算法跳出局部最優的可能.

2.3基于目標函數值的選擇尋優

在ABC算法中，引領蜂、跟隨蜂和偵察蜂在對食物源的選擇過程中都是基于適應值fiti，如果候選食物源的適應值優于之前食物源，則取而代之.但從(3)式可以看出，對于函數優化問題的目標函數值大于0且無限接近0時，對應的適應值fiti就不具有區分度.為解決這個問題，本文算法在引領蜂、跟隨蜂和偵察蜂對食物源的選擇過程中直接采用目標函數值來代替適應值[15].

2.4IABC算法的步驟

改進算法的具體步驟如下：

步驟1設置算法的各個參數，初始化種群，計算每個引領蜂對應的食物源的目標函數值并記錄全局最優值；

步驟2對每個引領蜂，根據(5)式對食物源進行更新并計算其目標函數值，通過貪婪選擇較優的食物源；

步驟3計算更新后食物源的目標函數值，并按(2)式計算選擇概率Pi；

步驟4跟隨蜂依據概率Pi選擇食物源，根據(6)式對食物源進行更新并計算其目標函數值，通過貪婪選擇較優的食物源；

步驟5若引領蜂對應的食物源連續limit次沒有得到更新，則對應的引領蜂變為偵察蜂，根據(4)式產生新食物源；

步驟6記錄下全局最優值，并跳轉至步驟2，直至滿足算法結束條件.

3仿真實驗

為了驗證本文提出的IABC算法的性能，選取了15個基準測試函數用于仿真實驗，并與ABC算法、文獻[7]提出的算法(記為GABC)的測試結果進行比較.實驗時，種群規模SN=20，limit=SN×D，最大評價次數MaxFEs=5 000×D.在實驗中，3種算法在每個函數上獨立運行10次，記錄結果的最優值(Best)、最差值(Worst)、平均值(Mean)和標準差(Std).其中：Best和Worst反映了解的質量；Mean反映了算法在給定的最大評價次數下所能達到的精度；Std反映了算法的穩定性和魯棒性.

表1給出了15個基準測試函數的表達式、搜索范圍和理論最優值，其中，f1(x)-f8(x)為單峰函數，f9(x)-f15(x)為多峰函數.表2和3分別給出了ABC、GABC和IABC在D=30和D=100時的測試結果.

表1　基準測試函數

表2　ABC、GABC和IABC在函數維數為30時的測試結果

表3　ABC、GABC和IABC在函數維數為100時的測試結果

從表2可以看出，在單峰函數的測試中，除了f8(x)外，IABC算法在解的精度和穩定性兩方面都優于ABC算法和GABC算法.在多峰函數的測試中，對于f9(x)和f10(x)，3種算法都能得到理論最優值.對于其他的復雜多峰函數，IABC算法的求解結果明顯優于ABC算法和GABC算法.為了直觀地反映IABC算法的收斂性能，圖1—6給出了3種算法對于部分測試函數在30維數時的收斂曲線.從圖1—6中可以看出，IABC算法在迭代初期就有良好的性能，測試函數的收斂曲線下降速度很快，能夠收斂到較高精度的解.

圖1　Schwefel 2.22函數收斂曲線

圖2　Schwefel 2.21函數收斂曲線

圖3　Quartic函數收斂曲線

圖4　Griewank函數收斂曲線

圖5　Ackley函數收斂曲線

圖6　Schaffer函數收斂曲線

從表3可以看出，對于D=100，IABC算法也取得了與D=30時一樣好的優化結果，即對于15個測試函數，除f8(x)外，IABC算法的結果都優于ABC算法和GABC算法.

為進一步測試IABC算法的性能，將其與MABC[8]、ABCBest1[10]、ABCBest2[10]、ABCVSS[11]等較新的改進算法在D=30和D=100時進行了比較，所有算法的最大評價次數MaxFEs=5 000×D.表4—5給出了5種算法的測試結果.

表4　5種算法在函數維數為30時的測試結果

表5　5種算法在函數維數為100時的測試結果

由表4和5可以看出，在15個基準測試函數中，對于f6(x)，f9(x)和f10(x)，5種算法都能求得理論最優值，對于其他函數，IABC算法在解的精度和穩定性兩方面明顯優于MABC、ABCBest1、ABCBest2，在絕大部分函數上優于ABCVSS.

從上述實驗結果可以看出，IABC算法在計算精度上有了明顯提高，不僅具有較強的全局搜索能力，而且具有較強的局部搜索能力，能有效克服ABC算法收斂速度慢和易陷入局部最優的缺陷，并且隨著目標函數維數的增加，仍能保持較好的有效性和魯棒性.

4結論與展望

針對人工蜂群算法傳統搜索策略容易導致算法陷入早熟、搜索效率較低的缺點，提出了一種改進的人工蜂群算法，新算法提高了搜索效率.借鑒差分進化算法中的變異操作和生物界中雁群的飛行特征分別對人工蜂群算法中引領蜂和跟隨蜂的搜索策略進行改進，并直接基于目標函數值選擇尋優.對15個基準測試函數進行仿真實驗.結果表明，新算法在優化性能和魯棒性等方面較基本人工蜂群算法及一些改進的人工蜂群算法有了較大的改善.

當然，新算法也存在著一些不足，對于Rosenbrock函數，IABC算法的求解效果并不是很好.如何使算法能夠在更多復雜函數上表現更好的性能將是下一步的研究方向.同時，將所提出的算法應用到約束優化、多目標優化以及非線性系統優化等領域也是值得進一步研究的任務.

[參考文獻]

[1]KARABOGA D.An idea based on honey bee swarm for numerical optimization[R].Kayseri：Erciyes University，2005.

[2]KARABOGA N.A new design method based on artificial bee colony algorithm for digital IIR filters[J].Journal of the Franklin Institute，2009，346(4)：328-348.

[3]SINGH A.An artificial bee colony algorithm for the leaf-constrained minimum spanning tree problem[J].Applied Soft Computing，2009，9(2)：625-631.

[4]TASGETIREN M F，PAN Q K，SUGANTHAN P N，et al.A discrete artificial bee colony algorithm for the total flowtime minimization in permutation flow shops [J].Information Sciences，2011，181(16)：3459-3475.

[5]SZETO W，WU Y，HO S C.An artificial bee colony algorithms for the capacitated vehicle routing problem[J].European Journal of Operational Research，2011，215(1)：126-135.

[6]KANG F，LI J L，MA Z Y.Rosenbrock artificial bee colony algorithm for accurate global optimization of numerical functions[J].Information Sciences，2011，181(16)：3508-3531.

[7]ZHU G P，KWONG S.Gbest-guided artificial bee colony algorithm for numerical function optimization[J].Applied Mathematics and Computation，2010，217(7)：3166-3173.

[8]GAO W F，LIU S Y.A modified artificial bee colony algorithm[J].Computer & Operations Research，2012，39(3):687-697.

[9]AKAY B，KARABOGA D.A modified artificial bee colony algorithm for real-parameter optimization[J].Information Sciences，2012，192(1)：120-142.

[10]GAO W F，LIU S Y，HUANG L L.A global best artificial bee colony algorithm for global optimization[J].Journal of Computational and Applied Mathematics，2012，236(11)：2741-2753.

[11]KIRAN M S，HAKLI H，GUNDUZ M，et al.Artificial bee colony algorithm with variable search strategy for continuous optimization[J].Information Sciences，2015，300(8)：140-157.

[12]趙輝，李牧東，翁興偉.具有自適應全局最優引導快速搜索策略的人工蜂群算法[J].控制與決策，2014，29(11)：2041-2047.

[13]李田來，劉方愛，王新華.基于分治策略的改進人工蜂群算法[J].控制與決策，2015，30(2)：316-320.

[14]劉金洋，郭茂祖，鄧超.基于雁群啟示的粒子群優化算法[J].計算機科學，2006，33(11)：166-168.

[15]BANHARNSAKUN A，ACHALAKUL T，SIRINAOVAKUL B.The best-so-far selection in artificial bee colony algorithm[J].Applied Soft Computing，2011，11(2)：2888-2901.

(責任編輯：石紹慶)

Improved artificial bee colony algorithm for solving complex functions with high dimensions

WANG Zhi-gang，WANG Ming-gang

(School of Mathematics and Apply，Nanjing Normal University Taizhou College，Taizhou 225300，China)

Abstract:The traditional search strategy of artificial bee colony algorithm exists some disadvantages when solving complex functions with high dimensions，such as the convergence speed is not fast enough，easy to fall into local optimum.In order to solve these issues，an improved artificial bee colony algorithm is presented.In this algorithm，the search strategy of employed bees uses the DE/best/1 mutation operation of the differential evolution for reference，the search strategy of onlookers uses the characteristics of the flight of geese for reference，and select the best solution based on the objective function value.The new algorithm can balance the ability of local and global search.Experiments are conducted on a set of 15 benchmark functions，and the results demonstrate that the new algorithm has fast convergence and high accuracy than several other ABC-based algorithms.

Keywords:artificial bee colony algorithm；differential evolution；flight of geese；search strategy

[文章編號]1000-1832(2016)02-0056-09

[收稿日期]2015-09-06

[基金項目]國家自然科學基金資助項目(71503132)；江蘇省高校自然科學研究項目(14KJD110005，14KJB110017)；南京師范大學泰州學院數學建模精品課程項目.

[作者簡介]王志剛(1978—)，男，講師，主要從事組合優化與智能優化算法研究；王明剛(1982—)，男，副教授，主要從事智能優化算法、復雜系統建模與控制研究.

[中圖分類號]TP 301.6[學科代碼]520·30

[文獻標志碼]A

[DOI]10.16163/j.cnki.22-1123/n.2016.02.014