優(yōu)化高維復(fù)雜函數(shù)的改進人工蜂群算法

王志剛，王明剛

(南京師范大學(xué)泰州學(xué)院數(shù)學(xué)科學(xué)與應(yīng)用學(xué)院，江蘇 泰州 225300)

優(yōu)化高維復(fù)雜函數(shù)的改進人工蜂群算法

王志剛，王明剛

(南京師范大學(xué)泰州學(xué)院數(shù)學(xué)科學(xué)與應(yīng)用學(xué)院，江蘇 泰州 225300)

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

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

0引言

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

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

1人工蜂群算法

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

引領(lǐng)蜂和跟隨蜂根據(jù)

vij=xij+φij(xij-xkj)

(1)

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

跟隨蜂通過

(2)

概率來選擇食物源.式中fiti為第i個食物源的適應(yīng)值.在最小化問題中，fiti與優(yōu)化問題目標(biāo)函數(shù)值fi的對應(yīng)關(guān)系為

(3)

在ABC算法中，如果連續(xù)經(jīng)過limit次循環(huán)之后食物源仍然沒有得到更新，則引領(lǐng)蜂就放棄食物源，轉(zhuǎn)變?yōu)閭刹旆洌?/p>

(4)

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

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

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

2.2新的搜索策略

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

2.2.1引領(lǐng)蜂的搜索策略

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

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

(5)

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

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

2.2.2跟隨蜂的搜索策略

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

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

(6)

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

2.3基于目標(biāo)函數(shù)值的選擇尋優(yōu)

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

2.4IABC算法的步驟

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

步驟1設(shè)置算法的各個參數(shù)，初始化種群，計算每個引領(lǐng)蜂對應(yīng)的食物源的目標(biāo)函數(shù)值并記錄全局最優(yōu)值；

步驟2對每個引領(lǐng)蜂，根據(jù)(5)式對食物源進行更新并計算其目標(biāo)函數(shù)值，通過貪婪選擇較優(yōu)的食物源；

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

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

步驟5若引領(lǐng)蜂對應(yīng)的食物源連續(xù)limit次沒有得到更新，則對應(yīng)的引領(lǐng)蜂變?yōu)閭刹旆洌鶕?jù)(4)式產(chǎn)生新食物源；

步驟6記錄下全局最優(yōu)值，并跳轉(zhuǎn)至步驟2，直至滿足算法結(jié)束條件.

3仿真實驗

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

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

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

表2　ABC、GABC和IABC在函數(shù)維數(shù)為30時的測試結(jié)果

表3　ABC、GABC和IABC在函數(shù)維數(shù)為100時的測試結(jié)果

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

圖1　Schwefel 2.22函數(shù)收斂曲線

圖2　Schwefel 2.21函數(shù)收斂曲線

圖3　Quartic函數(shù)收斂曲線

圖4　Griewank函數(shù)收斂曲線

圖5　Ackley函數(shù)收斂曲線

圖6　Schaffer函數(shù)收斂曲線

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

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

表4　5種算法在函數(shù)維數(shù)為30時的測試結(jié)果

表5　5種算法在函數(shù)維數(shù)為100時的測試結(jié)果

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

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

4結(jié)論與展望

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

當(dāng)然，新算法也存在著一些不足，對于Rosenbrock函數(shù)，IABC算法的求解效果并不是很好.如何使算法能夠在更多復(fù)雜函數(shù)上表現(xiàn)更好的性能將是下一步的研究方向.同時，將所提出的算法應(yīng)用到約束優(yōu)化、多目標(biāo)優(yōu)化以及非線性系統(tǒng)優(yōu)化等領(lǐng)域也是值得進一步研究的任務(wù).

[參考文獻]

[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]趙輝，李牧東，翁興偉.具有自適應(yīng)全局最優(yōu)引導(dǎo)快速搜索策略的人工蜂群算法[J].控制與決策，2014，29(11)：2041-2047.

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

[14]劉金洋，郭茂祖，鄧超.基于雁群啟示的粒子群優(yōu)化算法[J].計算機科學(xué)，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.

(責(zé)任編輯：石紹慶)

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

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

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

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

[文獻標(biāo)志碼]A

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