王志剛，王明剛

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

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

王志剛，王明剛

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

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

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

0引言

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

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

1人工蜂群算法

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

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

vij=xij+φij(xij-xkj)

(1)

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

跟隨蜂通過(guò)

(2)

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

(3)

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

(4)

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

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

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

2.2新的搜索策略

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

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

為提高算法的局部搜索能力，加快收斂速度，借鑒差分進(jìn)化算法中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)生候選食物源，通過(guò)種群的全局最優(yōu)解來(lái)引導(dǎo)種群的搜索軌跡，加快算法的收斂速度，以增強(qiáng)算法的局部搜索能力.因此，把(5)式作為新算法中引領(lǐng)蜂的搜索策略.

2.2.2跟隨蜂的搜索策略

雁群在飛行時(shí)常常呈現(xiàn)“人”字形或“一”字形，其中頭雁扇動(dòng)雙翼產(chǎn)生尾渦，后面尾隨的大雁借力飛行，雁群中最強(qiáng)壯的大雁往往作為頭雁，其他大雁依次往后排[14].借鑒雁群的這種飛行特征，可以把大雁的強(qiáng)壯程度視為食物源的優(yōu)劣，將食物源按照適應(yīng)值的優(yōu)劣進(jìn)行排序，把最優(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)生候選食物源時(shí)可以充分利用整個(gè)種群的信息，避免了所有候選食物源都在種群的全局最優(yōu)解附近產(chǎn)生，這有利于在搜索過(guò)程中找到更優(yōu)秀的個(gè)體，增強(qiáng)了算法跳出局部最優(yōu)的可能.

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

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

2.4IABC算法的步驟

改進(jìn)算法的具體步驟如下：

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

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

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

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

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

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

3仿真實(shí)驗(yàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4結(jié)論與展望

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

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

[參考文獻(xiàn)]

[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]李田來(lái)，劉方愛(ài)，王新華.基于分治策略的改進(jìn)人工蜂群算法[J].控制與決策，2015，30(2)：316-320.

[14]劉金洋，郭茂祖，鄧超.基于雁群?jiǎn)⑹镜牧Ｗ尤簝?yōu)化算法[J].計(jì)算機(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

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

[收稿日期]2015-09-06

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

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

[中圖分類(lèi)號(hào)]TP 301.6[學(xué)科代碼]520·30

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

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