陳 皓,張 潔,楊清萍,董婭婭,肖利雪,冀敏杰

(西安郵電大學(xué) 計(jì)算機(jī)學(xué)院,西安 710121) (*通信作者電子郵箱chenhao@xupt.edu.cn)

基于混合搜索的多種群人工蜂群算法

陳 皓*,張 潔,楊清萍,董婭婭,肖利雪,冀敏杰

(西安郵電大學(xué) 計(jì)算機(jī)學(xué)院,西安 710121) (*通信作者電子郵箱chenhao@xupt.edu.cn)

針對(duì)經(jīng)典人工蜂群(ABC)算法搜索策略存在搜索機(jī)制單一、群體全局搜索與局部搜索運(yùn)算耦合性較高的問(wèn)題，提出一種基于混合搜索的多種群人工蜂群(MPABC) 算法。首先，將種群按照適應(yīng)度值進(jìn)行排序，得到一個(gè)有序隊(duì)列，進(jìn)而將其劃分為隨機(jī)子群、核心子群和平衡子群三類有序子群；其次，針對(duì)不同子群結(jié)合相應(yīng)的個(gè)體選擇機(jī)制與搜索策略，構(gòu)建出不同的差異向量；最后，在群體的搜索過(guò)程中，通過(guò)三類子群實(shí)現(xiàn)對(duì)具有不同適應(yīng)度函數(shù)值個(gè)體的有效控制，來(lái)增強(qiáng)群體全局搜索和局部搜索的平衡能力。通過(guò)對(duì)16個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行仿真實(shí)驗(yàn)并與具有可變搜索策略的人工蜂群(ABCVSS)算法、基于選擇概率的改進(jìn)人工蜂群(MABC)算法、基于粒子群策略的多精英人工蜂群(PS-MEABC)算法、基于符號(hào)函數(shù)的多搜索策略人工蜂群(MSSABC)算法和優(yōu)化高維復(fù)雜函數(shù)的改進(jìn)人工蜂群(IABC)算法共五種典型的蜂群算法進(jìn)行了對(duì)比，實(shí)驗(yàn)結(jié)果顯示MPABC具有較好的優(yōu)化效果；與ABC算法相比，MPABC在求解高維(100維)復(fù)雜問(wèn)題上的收斂速度提高了約23%，且求解精度更優(yōu)。

人工蜂群算法；個(gè)體選擇機(jī)制；差分搜索；群體分類控制策略

0 引言

人工蜂群(Artificial Bee Colony, ABC)算法[1]具有結(jié)構(gòu)簡(jiǎn)單、控制參數(shù)少、性能優(yōu)良等特點(diǎn),目前已被應(yīng)用于解決多種不同的實(shí)際優(yōu)化問(wèn)題[2-5],并取得了較好的實(shí)驗(yàn)結(jié)果。但在ABC中,雇傭蜂和觀察蜂所采取的搜索策略在求解復(fù)雜函數(shù)時(shí)存在著過(guò)早收斂、容易陷入局部最優(yōu)、求解精度不高等缺點(diǎn)。為此,研究者提出了許多不同的搜索策略來(lái)改善算法性能,其中的代表性研究工作是關(guān)于如何改進(jìn)解搜索方程或提出新的解搜索方程[6]。Zhu等[7]受粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法啟發(fā),提出在解搜索方程中加入全局最優(yōu)解gbest信息引導(dǎo)ABC算法。另一研究趨勢(shì)是探索如何與其他搜索算子相結(jié)合來(lái)提高算法搜索性能。比如,Gao等[8]通過(guò)將ABC與局部搜索Powell方法相結(jié)合,有效地提高了ABC的性能。

上述通過(guò)直接修改進(jìn)化操作算子的方法雖一定程度上提高了算法性能,但其都是在具體操作層面上的改進(jìn),并沒(méi)有充分考慮種群全局結(jié)構(gòu)和局部算子的個(gè)體能力問(wèn)題[9],沒(méi)有從根本上解決在提高算法收斂性的同時(shí)該如何增加種群的多樣性、避免陷入局部最優(yōu)的問(wèn)題,其根本原因在于搜索策略的調(diào)節(jié)仍是被動(dòng)適應(yīng)[10]。因而,為有效解決蜂群間通信方式單一、協(xié)作不足所引發(fā)的種群在全局探索與局部尋優(yōu)不平衡的問(wèn)題，本文通過(guò)研究個(gè)體選擇方式與搜索運(yùn)算的性能特點(diǎn)間的聯(lián)系,提出了一種基于混合搜索的多種群人工蜂群(Multi-Population ABC, MPABC)算法,該算法利用個(gè)體選擇機(jī)制提升其在進(jìn)化過(guò)程中的自我調(diào)節(jié)能力,并通過(guò)融合多種進(jìn)化策略改進(jìn)種群的搜索效率與抗早熟能力。

1 ABC算法的基本計(jì)算機(jī)制

(1)

2)觀察蜂階段。雇傭蜂完成勘探后,觀察蜂根據(jù)雇傭蜂分享的信息,以輪盤賭方式選擇一個(gè)食物源進(jìn)一步開采,則食物源被選中的概率為:

(2)

其中:fiti為第i個(gè)食物源的適應(yīng)度函數(shù)值。對(duì)于最小化問(wèn)題,fiti與問(wèn)題空間S的目標(biāo)函數(shù)值trueFiti對(duì)應(yīng)關(guān)系為:

(3)

3)偵察蜂階段。當(dāng)雇傭蜂對(duì)應(yīng)食物源的適應(yīng)值連續(xù)limit次未更新,表明該食物源已被開采盡,則對(duì)應(yīng)雇傭蜂就放棄該食物源并變成偵察蜂,同時(shí)隨機(jī)產(chǎn)生一新食物源:

(4)

為進(jìn)一步研究ABC算法的計(jì)算機(jī)制,圖1～2給出了單峰函數(shù)F06(Step)與多峰函數(shù)F09(Rastrigin)利用ABC在搜索最優(yōu)解過(guò)程中函數(shù)收斂曲線與群體多樣性曲線。參數(shù)設(shè)置為:迭代次數(shù)Max.FE=1 000次；控制參數(shù)limit=10,80次;收斂精度為10-5。其中，收斂精度取對(duì)數(shù)后，所得函數(shù)值為-5，則收斂精度曲線與橫坐標(biāo)相互重合。

為了便于對(duì)ABC性能的分析,首先給出一些基本定義:

定義1 個(gè)體xi和xj之間的相似性可通過(guò)歐氏距離比Disij來(lái)度量:

Disij=Dis(xi,xj)=‖xi-xj‖/‖xub-xlb‖

(5)

其中:‖xi-xj‖表示兩個(gè)實(shí)數(shù)向量的歐幾里得范數(shù)。顯然Disij在區(qū)間[0,1]內(nèi),Disij愈趨近0,個(gè)體差異性越小;反之則相反。

定義2 群體的平均間距meanDis為:

(6)

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

圖2 函數(shù)多樣性曲線

limit作為ABC算法中衡量全局搜索代價(jià)的重要參數(shù),直接關(guān)系到算法的計(jì)算性能與收斂速度。如圖1～2所示,當(dāng)函數(shù)F06與F09的limit值較小時(shí),算法雖然具有較強(qiáng)的隨機(jī)性能與全局搜索性能,但其收斂速度非常緩慢且精度遠(yuǎn)沒(méi)有達(dá)到實(shí)驗(yàn)要求；當(dāng)limit較大時(shí),算法雖然增強(qiáng)了局部搜索能力,提升了收斂速度,但卻因受到局部最優(yōu)解的束縛而陷入早熟收斂。以上分析說(shuō)明limit的取值差異使式(1)參數(shù)傾向于不同搜索策略,偏向全局搜索的參數(shù)使曲線表現(xiàn)出過(guò)度的全局搜索趨勢(shì),偏向局部搜索的參數(shù)使曲線表現(xiàn)出過(guò)度的局部搜索趨勢(shì),其根本原因在于ABC單一搜索模式具有的較高的耦合性,難以實(shí)現(xiàn)全局搜索和局部搜索間的有效協(xié)調(diào)。

2 基于子群與多進(jìn)化策略的改進(jìn)機(jī)制

2.1 子群的構(gòu)造機(jī)制

針對(duì)上述研究中的不足,通過(guò)對(duì)個(gè)體間編碼差異及其問(wèn)題空間的分布與其所參與搜索運(yùn)算的性能特點(diǎn)間存在的聯(lián)系[11]進(jìn)行研究,發(fā)現(xiàn)其主要表現(xiàn)為個(gè)體編碼差異對(duì)搜索運(yùn)算的控制,或是個(gè)體空間分布形態(tài)所形成的結(jié)構(gòu)對(duì)系統(tǒng)整體計(jì)算的調(diào)節(jié),但這種隱式的結(jié)構(gòu)關(guān)系并不利于其對(duì)計(jì)算過(guò)程的主動(dòng)控制。因此,就需要設(shè)計(jì)出一種更為明顯的種群關(guān)系。

隊(duì)列作為實(shí)際生活中一種常見的有序群體,其特點(diǎn)是隊(duì)頭與隊(duì)尾個(gè)體差異較大,中間個(gè)體差異較小且數(shù)目眾多,這說(shuō)明有序隊(duì)列不同位置中的個(gè)體之間具有一定間距關(guān)系。基于以上分析,本文提出一種新思路,將種群先按適應(yīng)值大小進(jìn)行排序,分為三類有序子群;再通過(guò)子群控制個(gè)體的選擇范圍,以構(gòu)建出不同的差異向量進(jìn)行群體搜索。

(7)

其中:Rg、Cg和Bg分別表示隨機(jī)子群、核心子群和平衡子群;Nrand表示隨機(jī)子群的個(gè)體總數(shù);Nother=SN-Nrand表示Cg和Bg的個(gè)體總數(shù);μ是群體劃分比例,實(shí)驗(yàn)取值為0.3。

圖3是由式(7)得到的種群類結(jié)構(gòu)圖,子群內(nèi)個(gè)體相似性最大,而子群間差異性最大。因而,本文利用這三類子群實(shí)現(xiàn)對(duì)具有不同適應(yīng)度函數(shù)值個(gè)體的有效控制,以達(dá)到調(diào)節(jié)全局和局部搜索的目的。

圖3 基于適應(yīng)值排序的種群類結(jié)構(gòu)

2.2 分類機(jī)制對(duì)群體搜索狀態(tài)的影響分析

2.2.1 利用分類結(jié)構(gòu)調(diào)節(jié)全局和局部搜索過(guò)程

本節(jié)從兩方面分析算法是如何利用三類子群實(shí)現(xiàn)對(duì)群體搜索過(guò)程的調(diào)節(jié)：一是通過(guò)對(duì)三類子群的平均間距進(jìn)行分析,說(shuō)明其可調(diào)節(jié)全局與局部搜索的原因；二是利用個(gè)體選擇機(jī)制實(shí)現(xiàn)其對(duì)搜索過(guò)程的調(diào)節(jié)。圖4和圖5分別表示函數(shù)F03(SumPower)運(yùn)用MPABC算法在搜索最優(yōu)解過(guò)程中子群的平均間距meanDis與個(gè)體數(shù)目number的變化曲線,實(shí)驗(yàn)結(jié)果為20次獨(dú)立實(shí)驗(yàn)(參數(shù)為D=30,Max.FE=1 000)的平均值。

圖4 三類子群平均間距在進(jìn)化過(guò)程中的變化曲線

另外,根據(jù)三類子群間獨(dú)立又彼此聯(lián)系的結(jié)構(gòu),可以方便地將具有不同計(jì)算結(jié)構(gòu)和運(yùn)算特性的搜索方法有效結(jié)合在一起,通過(guò)個(gè)體選擇機(jī)制實(shí)現(xiàn)對(duì)群體全局和局部搜索的動(dòng)態(tài)調(diào)節(jié)。如圖5所示,進(jìn)化過(guò)程分為三個(gè)階段,其中,Cg與Bg的個(gè)體數(shù)目不斷增大,Rg數(shù)目卻逐漸減小,這種變化使看起來(lái)獨(dú)立的各類子群之間又彼此關(guān)聯(lián)。

圖5 進(jìn)化過(guò)程Cg、Bg和Rg的個(gè)體數(shù)目變化曲線

基于以上分析,針對(duì)不同的搜索水平設(shè)計(jì)出一種新型的個(gè)體選擇機(jī)制:

Cg的局部搜索:

{ci|ci∈Cg,i=p1,p2}

(8)

Bg的全局到局部的過(guò)渡搜索:

{bi|bi∈Bg,i=p1,p2}

(9)

Rg的全局搜索:

{ri|ri∈Cg∪Bg∪Rg,i=p1,p2,…,p5}

(10)

其中:ci表示在Cg中隨機(jī)選出2個(gè)個(gè)體,記為cp1和cp2;同理bi與ri分別表示在Bg與Rg中選出的個(gè)體。

進(jìn)化搜索中三類子群的搜索頻率由個(gè)體數(shù)目決定,故其取值大小將直接影響每代進(jìn)行全局及局部搜索的比例。進(jìn)化前期,Rg在群體中number值比重最大且Bg與Cg比重較小,形成以“全局搜索方式為主與其他搜索方式為輔”的計(jì)算機(jī)制,有效地豐富了群體多樣性并降低了算法早熟收斂的可能;進(jìn)化中期,三類子群number值均處于一種相對(duì)穩(wěn)定的狀態(tài),形成了一種“過(guò)渡搜索+全局搜索+局部搜索”的搜索組合;而隨著Cg中number逐漸增大,其他子群值的不斷減小,使得進(jìn)化后期形成了以“局部搜索和過(guò)渡搜索為主與全局搜索方式為輔”的計(jì)算機(jī)制,從而提高了算法尋找最優(yōu)解的速度。

2.2.2 基于分類調(diào)節(jié)的新型差分進(jìn)化算法計(jì)算機(jī)制的性能分析

為有效降低ABC算法搜索機(jī)制因單一盲目性所帶來(lái)的負(fù)面影響,在分類調(diào)節(jié)機(jī)制的基礎(chǔ)上通過(guò)進(jìn)一步引入差分進(jìn)化(Differential Evolution, DE)算法的多種搜索方式,有效地提高了系統(tǒng)的計(jì)算效率。為了便于研究,將DE的五種進(jìn)化模式分為三類[12],其特點(diǎn)是:第一類模式中個(gè)體自由探索性突出,全局收斂較強(qiáng),不易陷入局部最優(yōu),但收斂速度較慢；第二類模式的個(gè)體在該區(qū)域的自由探索性相對(duì)較弱,局部收斂性和繼承性較強(qiáng),收斂速度較快,但易陷入局部最優(yōu)；第三類模式特點(diǎn)是群體自由探索性和繼承性相對(duì)保持均衡,具有良好的適應(yīng)性。

通過(guò)以上分析,為有效提升算法的搜索性能，本文按照子群平均間距值對(duì)種群的搜索水平進(jìn)行類別劃分,則三類子群的搜索機(jī)制如下:

Cg搜索策略:

(11)

Bg搜索策略:

(12)

Rg搜索策略:

(13)

根據(jù)每個(gè)個(gè)體在搜索過(guò)程中的不同表現(xiàn),對(duì)于不同子群的個(gè)體,在尋優(yōu)過(guò)程中它需要加強(qiáng)該子群所需要的能力。即,在Cg中加強(qiáng)局部尋優(yōu)來(lái)搜索極值點(diǎn),Rg中通過(guò)全局搜索來(lái)增強(qiáng)算法的勘探能力,而Bg主要是對(duì)算法全局搜索能力和局部搜索能力的協(xié)調(diào)。

2.3 基于多進(jìn)化模式協(xié)作的人工蜂群算法

在前述基礎(chǔ)上提出了一種新算法MPABC,即在分類調(diào)節(jié)機(jī)制的基礎(chǔ)上進(jìn)一步引入DE計(jì)算機(jī)制來(lái)改進(jìn)全局與局部的計(jì)算效果。圖6為MPABC的架構(gòu)。

圖6 MPABC的架構(gòu)

如圖6所示, MPABC計(jì)算模式分為三大模塊:模塊一是系統(tǒng)初始化,包括種群初始化與子群的構(gòu)建,最后得到三類有序子群體;模塊二針對(duì)不同子群設(shè)計(jì)出一種更具針對(duì)性且協(xié)調(diào)性更佳的搜索機(jī)制組合,實(shí)現(xiàn)對(duì)搜索過(guò)程的調(diào)節(jié);模塊三是利用觀察蜂進(jìn)行局部尋優(yōu)來(lái)找出最優(yōu)解。先通過(guò)式(8)～(9)計(jì)算出觀察蜂的搜索區(qū)間,再利用式(11)進(jìn)行局部搜索,進(jìn)一步提升算法的尋優(yōu)能力。

3 仿真實(shí)驗(yàn)及結(jié)果分析

為驗(yàn)證MPABC的求解性能,采用16個(gè)典型的Benchmark[13]146函數(shù)(F01～F16)用于仿真實(shí)驗(yàn)。其中：F01～F08是單峰函數(shù)；F06是非連續(xù)函數(shù)；F07是帶噪聲函數(shù),在維度大于3時(shí)為多峰函數(shù);F09～F16是多峰函數(shù)。通常單峰函數(shù)用于測(cè)試算法的尋優(yōu)精度以及考察算法的執(zhí)行性能。而多峰函數(shù)中的局部最優(yōu)點(diǎn)會(huì)伴隨維數(shù)的增加而指數(shù)增長(zhǎng),常用于檢驗(yàn)算法跳出局部最優(yōu)的能力。

整個(gè)實(shí)驗(yàn)分為兩部分：第一部分是對(duì)ABC和MPABC的優(yōu)化性能與測(cè)試結(jié)果進(jìn)行比較；第二部分是將其與近年的ABC變種算法進(jìn)行比較分析,包括具有可變搜索策略的人工蜂群算法(ABC algorithm with Variable Search Strategy, ABCVSS)[13]148-151、基于選擇概率的改進(jìn)人工蜂群算法(Modified ABC algorithm based on selection probability, MABC)[13]152、基于粒子群策略的多精英人工蜂群(Particle Swarm-inspired Multi-Elitist ABC, PS-MEABC)算法[14]、基于符號(hào)函數(shù)的多搜索策略人工蜂群(Multi-Search Strategy of the ABC, MSSABC)算法[15]和優(yōu)化高維復(fù)雜函數(shù)的改進(jìn)人工蜂群算法(Improved ABC algorithm for optimizing high-dimensional complex functions, IABC)[16]。

3.1 MPABC和ABC的收斂性比較

為驗(yàn)證MPABC的尋優(yōu)能力在復(fù)雜高維函數(shù)的有效性。將MPABC與ABC從結(jié)果精度、收斂速度和維度擴(kuò)展性三個(gè)方面進(jìn)行比較分析。實(shí)驗(yàn)參數(shù)設(shè)置為:NP=40;limit=200;D=30,60,100;Max.FE=5 000;收斂精度為10-5。表1給出了當(dāng)D=30,60,100時(shí)算法的測(cè)試結(jié)果(每個(gè)函數(shù)獨(dú)立運(yùn)行20次)。其中：最優(yōu)值和最差值反映了解的質(zhì)量,平均值反映了在給定最大評(píng)價(jià)次數(shù)時(shí)算法的求解精度,標(biāo)準(zhǔn)差則反映了算法的穩(wěn)定性和魯棒性。

由表1計(jì)算結(jié)果可以看出：在30維情況下,MPABC在大部分函數(shù)上的性能要顯著優(yōu)于ABC。對(duì)部分函數(shù)(如F05、F07、F08、F12和F14),兩者性能相當(dāng);尤其是在函數(shù)F06、F09～F11上,ABC與MPABC均能取得理論最優(yōu)值0。而對(duì)于其他函數(shù)(F01～F04),MPABC的收斂精度比ABC則有了大幅度提升。并且隨著維度的增長(zhǎng),MPABC的求解結(jié)果仍要優(yōu)于或同ABC一樣得到理論最優(yōu)值0(如函數(shù)F06、F11)。

函數(shù)無(wú)論是在30、60還是100維上,MPABC算法的最優(yōu)值和最差值的精度與ABC相比得到明顯提高,并且對(duì)各測(cè)試函數(shù)均具有較高的尋優(yōu)精度,尤其在函數(shù)F01～F04、F10、F11上。其次,在相同迭代次數(shù)下,針對(duì)絕大部分函數(shù)(F01、F03、F6～F11、F13～F14),MPABC算法尋優(yōu)速度更快。其中一部分原因是系統(tǒng)利用種群分類結(jié)構(gòu)直接控制群體的搜索過(guò)程,實(shí)現(xiàn)對(duì)全局和局部搜索過(guò)程的調(diào)節(jié);另一部分是因?yàn)樵诜诸愓{(diào)節(jié)機(jī)制的基礎(chǔ)上進(jìn)一步引入DE計(jì)算機(jī)制來(lái)改進(jìn)全局與局部的計(jì)算效果,使MPABC在計(jì)算的不同階段形成更具針對(duì)性且協(xié)調(diào)性更佳的搜索機(jī)制組合,實(shí)現(xiàn)了在不同復(fù)雜結(jié)構(gòu)的問(wèn)題空間中更高效、穩(wěn)定的搜索。

表1 ABC與MPABC算法的測(cè)試結(jié)果

為了直觀反映MPABC的收斂性能,圖7～8給出了兩種算法對(duì)于部分測(cè)試函數(shù)在D=30,Max.FE=200時(shí)的收斂曲線與群體多樣性圖。從圖7～8可以看出,MPABC雖然在迭代初期的性能略差,但隨著迭代次數(shù)的增加,函數(shù)收斂曲線和群體多樣性曲線的下降速度明顯高于ABC算法,有利于群體在后期快速收斂到較高精度的解。

由圖7的收斂曲線可以看出:MPABC算法不但在函數(shù)F06上找到理論最優(yōu)值0,而且其收斂速度明顯高于ABC;在復(fù)雜非線性函數(shù)F08和多模態(tài)函數(shù)F15上,MPABC的性能僅略優(yōu)于ABC;而對(duì)多模態(tài)函數(shù)F13和F14,MPABC的收斂精度和速度均顯著高于ABC。由圖8的多樣性曲線可以看出,MPABC的群體多樣性值在前期僅略高于ABC,能夠較好地減緩算法在前期的收斂速度;隨后MPABC算法的群體多樣性迅速降低并逐漸趨于0,其多樣性明顯低于ABC算法。此時(shí)群體差異性最小,促使其加速收斂到最優(yōu)值。綜上,說(shuō)明改進(jìn)后的MPABC算法性能優(yōu)于ABC。

圖7 函數(shù)的收斂曲線

圖8 函數(shù)的多樣性曲線

3.2 MPABC和其他改進(jìn)算法的比較

將MPABC與近幾年所提出的改進(jìn)算法ABCVSS、MABC、PS-MEABC、MSSABC、IABC在D=30時(shí)進(jìn)行比較。為了比較的公平性,MPABC參數(shù)設(shè)置為Max.FE=5 000,limit=200;另外5種算法參數(shù)均為Max.FE=5 000×D,limit=SN×D,其余參數(shù)保持不變,實(shí)驗(yàn)數(shù)據(jù)直接取自各文獻(xiàn)。

由表2可以看出,在16個(gè)基準(zhǔn)測(cè)試函數(shù)中,6種算法在函數(shù)F06、F09～F11上都能求得理論最優(yōu)值;對(duì)于其他函數(shù),MPABC在解的精度和穩(wěn)定性上明顯優(yōu)于ABCVSS、MABC、PS-MEABC、MSSABC,在絕大部分函數(shù)上則優(yōu)于IABC。

從上述實(shí)驗(yàn)結(jié)果可以看出,MPABC算法可以在較小的評(píng)價(jià)次數(shù)下達(dá)到相同甚至更高的精度。不僅具有較強(qiáng)的全局搜索能力,而且具有較強(qiáng)的局部搜索能力,能有效克服ABC算法收斂速度慢和易陷入局部最優(yōu)的缺陷,并隨著函數(shù)維度的增加,仍能保持較好的有效性和魯棒性。

4 結(jié)語(yǔ)

本文提出在種群分類調(diào)節(jié)機(jī)制的基礎(chǔ)上進(jìn)一步引入DE計(jì)算機(jī)制來(lái)改進(jìn)種群全局與局部的計(jì)算效果,形成了一種新型的進(jìn)化搜索算法,基于混合搜索的多種群人工蜂群算法。對(duì)16個(gè)基準(zhǔn)測(cè)試函數(shù)的仿真實(shí)驗(yàn)結(jié)果表明,算法有效克服了ABC演化過(guò)程中局部停滯的問(wèn)題,能有效處理高維函數(shù)優(yōu)化問(wèn)題并獲得較高的尋優(yōu)精度。但其也存在局限性,例如對(duì)Schwefel 2.26(F12)函數(shù)的求解效果并不理想。因而,如何使算法能夠在函數(shù)上表現(xiàn)出更好的性能以及將本文算法應(yīng)用到多目標(biāo)優(yōu)化、約束優(yōu)化等領(lǐng)域?qū)⑹窍乱徊降难芯抗ぷ鳌?/p>

表2 ABCVSS、MABC、PS-MEABC、MSSABC、IABC和MPABC算法結(jié)果對(duì)比

References)

[1] KARABOGA D. An idea based on honey bee swarm for numerical optimization: TR06[R]. Kayseri: Erciyes University, Engineering Faculty, 2005: 10.

[2] 冀俊忠, 魏紅凱, 劉椿年, 等. 基于引導(dǎo)素更新和擴(kuò)散機(jī)制的人工蜂群算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2013, 50(9): 2005-2014. (JI J Z, WEI H K, LIU C N, et al. Artificial colony algorithm based on introductory updating and diffusion mechanism[J]. Journal of Computer Research and Development, 2013, 50(9): 2005-2014.)

[3] EBRAHIMNEJAD A, TAVANA M, ALREZAAMIRI H. A novel artificial bee colony algorithm for shortest path problems with fuzzy arc weights[J]. Measurement, 2016, 93: 48-56.

[4] YIN P Y, CHUANG Y L. Adaptive memory artificial bee colony algorithm for green vehicle routing with cross-docking[J]. Applied Mathematical Modelling, 2016, 40(21/22): 9302-9315.

[5] NSEEF S K, ABDULLAH S, TURKY A, et al. An adaptive multi-population artificial bee colony algorithm for dynamic optimization problems[J]. Knowledge-Based Systems, 2016, 104: 14-23.

[6] 周新宇, 吳志健, 王明文. 基于正交實(shí)驗(yàn)設(shè)計(jì)的人工蜂群算法[J]. 軟件學(xué)報(bào), 2015, 26(9): 2167-2190. (ZHOU X Y, WU Z J, WANG M W. Artificial colony algorithm based on orthogonal experiment design [J]. Journal of Software, 2015, 26(9): 2167-2190.)

[7] ZHU G, KWONG S. Gbest-guided artificial bee colony algorithm for numerical function optimization[J]. Applied Mathematics amp; Computation, 2010, 217(7): 3166-3173.

[8] GAO W F, LIU S Y, HUANG L L. A novel artificial bee colony algorithm with Powell’s method[J]. Applied Soft Computing, 2013, 13(9): 3763-3775.

[9] 李文鋒, 梁曉磊, 張煜. 具有異構(gòu)分簇的粒子群優(yōu)化算法研究[J]. 電子學(xué)報(bào), 2012, 40(11): 2194-2199. (LI W F, LIANG X L, ZHANG Y. Research on particle swarm optimization algorithm with heterogeneous clustering [J]. Acta Electronica Sinica, 2012, 40(11): 2194-2199.)[10] 周傳華, 謝安世. 一種基于動(dòng)態(tài)小生境的自組織學(xué)習(xí)算法[J]. 軟件學(xué)報(bào), 2011, 22(8): 1738-1748. (ZHOU C H, XIE A S. A self-organizing learning algorithm based on dynamic niche [J]. Journal of Software, 2011, 22(8): 1738-1748.)

[11] 陳皓, 潘曉英. 類搜索算法[J]. 軟件學(xué)報(bào), 2015, 26(7): 1557-1573. (CHEN H, PAN X Y. Clustering search algorithm[J]. Journal of Software, 2015, 26(7): 1557-1573.)

[12] 賀毅朝, 王熙照, 劉坤起, 等.差分演化的收斂性分析與算法改進(jìn)[J]. 軟件學(xué)報(bào), 2010, 21(5): 875-885. (HE Y Z, WANG X Z, LIU K Q, et al. Convergence analysis and algorithm improvement of differential evolution[J]. Journal of Software, 2010, 21(5): 875-885.)

[13] 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(1): 140-157.

[14] MA W, SUN Z, LI J, et al. An improved artificial bee colony algorithm based on the strategy of global reconnaissance[J]. Soft Computing, 2015, 20(12): 4825-4857.

[15] 王志剛, 王明剛. 基于符號(hào)函數(shù)的多搜索策略人工蜂群算法[J]. 控制與決策, 2016, 31(11): 2038-2044. (WANG Z G, WANG M G. Multi-search strategy based on symbolic function artificial bee colony algorithm [J]. Control and Decision, 2016, 31(11) : 2038-2044.)

[16] 王志剛, 王明剛. 優(yōu)化高維復(fù)雜函數(shù)的改進(jìn)人工蜂群算法[J]. 東北師大學(xué)報(bào) (自然科學(xué)版), 2016, 48(2): 56-64. (WANG Z G, WANG M G. An improved artificial bee colony algorithm for optimizing high dimensional complex functions[J]. Journal of Northeast Normal University (Natural Science Edition), 2016, 48(2): 56-64.)

Multi-populationartificialbeecolonyalgorithmbasedonhybridsearch

CHEN Hao*, ZHANG Jie, YANG Qingping, DONG Yaya, XIAO Lixue, JI Minjie

(SchoolofComputerScienceandTechnology,Xi’anUniversityofPostsamp;Telecommunications,Xi’anShaanxi710121,China)

Aiming at the problems of Artificial Bee Colony (ABC) algorithm, which are the single search mechanism and the high coupling between global search and local search, a Multi-Population ABC (MPABC) algorithm based on hybrid search was proposed. Firstly, the population was sorted according to the fitness value to get an ordered queue, which was divided into three sorted subgroups including random subgroup, core subgroup and balanced subgroup. Secondly, different difference vectors were constructed according to the corresponding individual selection mechanism and search strategy to different subgroups. Finally, in the process of group search, the effective control of individuals with different fitness functions was realized through three subgroups, thus improving the balance ability of global search and local search. The simulation results based on 16 benchmark functions show that compared with ABC algorithm with Variable Search Strategy (ABCVSS), Modified ABC algorithm based on selection probability (MABC), Particle Swarm-inspired Multi-Elitist ABC (PS-MEABC) algorithm, Multi-Search Strategy of the ABC (MSSABC) and Improved ABC algorithm for optimizing high-dimensional complex functions (IABC), MPABC achieves a better optimization effect; and on the solution of high dimensional (100 dimensions) problems, compared with ABC, MPABC has higher convergence speed which is increased by about 23% and better search accuracy.

Artificial Bee Colony (ABC) algorithm; individual selection mechanism; differential search; group classification control strategy

2017- 05- 02;

2017- 07- 19。

國(guó)家自然科學(xué)基金資助項(xiàng)目(61203311,61105064);西安郵電大學(xué)創(chuàng)新基金資助項(xiàng)目(114- 602080126)。

陳皓(1978—),男,河北安新人,副教授,博士,CCF會(huì)員,主要研究方向:進(jìn)化計(jì)算、工程優(yōu)化; 張潔(1992—),女,陜西咸陽(yáng)人,碩士研究生,主要研究方向:計(jì)算智能、數(shù)據(jù)挖掘; 楊清萍(1992—),女,湖北襄陽(yáng)人,碩士研究生,主要研究方向:機(jī)器學(xué)習(xí); 董婭婭(1991—),女,陜西韓城人,碩士研究生,主要研究方向:自然語(yǔ)言處理、數(shù)據(jù)挖掘; 肖利雪(1992—),女,內(nèi)蒙赤峰人,碩士研究生,主要研究方向:計(jì)算智能、數(shù)據(jù)挖掘; 冀敏杰(1990—),男,陜西渭南人,碩士研究生,主要研究方向:計(jì)算智能、數(shù)據(jù)挖掘。

1001- 9081(2017)10- 2773- 07

10.11772/j.issn.1001- 9081.2017.10.2773

TP301.6

A

This work is partially supported by the National Natural Science Foundation of China (61203311, 61105064), the Innovation Foundation of Xi’an University of Posts amp; Telecommunications (114-602080126).

CHENHao, born in 1978, Ph. D., associate professor. His research interests include evolutionary computing, engineering optimization.

ZHANGJie, born in 1992, M. S. candidate. Her research interests include computational intelligence, data mining.

YANGQingping, born in 1992, M. S. candidate. Her research interests include machine learning.

DONGYaya, born in 1991, M. S. candidate. Her research interests include natural language processing, data mining.

XIAOLixue, born in 1992, M. S. candidate. Her research interests include computational intelligence, data mining.

JIMinjie, born in 1990, M. S. candidate. His research interests include computational intelligence, data mining.