趙玉霞，徐曉鐘，黃 維，馬 燕

(上海師范大學(xué) 信息與機(jī)電工程學(xué)院，上海 200234)

0 引 言

人工蜂群算法[1](artificial bee colony，ABC)是受蜂群采蜜過(guò)程啟發(fā)的一種群智能算法，具有控制參數(shù)少、搜索能力強(qiáng)等優(yōu)點(diǎn)[2]，已被用于連續(xù)空間優(yōu)化[3]、數(shù)據(jù)挖掘[4]和神經(jīng)網(wǎng)絡(luò)優(yōu)化[5]等多個(gè)方面。但ABC算法仍存在易“早熟”收斂和進(jìn)化后期搜索能力較差的缺點(diǎn)，大量學(xué)者對(duì)此提出了多種改進(jìn)方法，包括食物源初始化改進(jìn)、觀察蜂選擇策略改進(jìn)、解更新策略改進(jìn)、與其他算法結(jié)合等等。

在食物源初始化改進(jìn)方面，羅鈞等[6]提出應(yīng)用混沌序列初始化解，通過(guò)混沌的隨機(jī)性、遍歷性，提高解的多樣性和搜索的遍歷性。在觀察蜂選擇策略的改進(jìn)方面，Bao等[7]提出三種新的選擇機(jī)制：裂變選擇、排序選擇和競(jìng)標(biāo)賽選擇，并證明了新選擇機(jī)制的有效性。在解更新策略的改進(jìn)方面，Zhu等[8]在粒子群算法的啟發(fā)下，提出基于最優(yōu)解引導(dǎo)的解更新策略，提高了算法開采能力。Kiran等[9]在解更新策略中引入方向信息，降低了更新方向的盲目性，提高了算法速度。郝繼升等[10]引入受差分進(jìn)化算法啟發(fā)的搜索方程，提高算法的搜索能力。在與其他算法結(jié)合方面，Ozturk等[11]將遺傳算法與人工蜂群算法相結(jié)合，利用交叉和交換機(jī)制對(duì)食物源更新公式進(jìn)行改進(jìn)，使其跳出局部最優(yōu)解。

以上改進(jìn)從不同方面提升了算法優(yōu)化能力，但是在提高算法收斂性的同時(shí)避免陷入局部最優(yōu)方面仍舊有進(jìn)一步的改進(jìn)空間，因而文中提出基于貓群思想的混合人工蜂群算法，以通過(guò)新的搜索策略和搜索過(guò)程，以提高算法優(yōu)化性能。

1 混合人工蜂群算法

1.1 基于隨機(jī)新解引導(dǎo)的自適應(yīng)搜索策略

基本人工蜂群算法根據(jù)式1建立初始種群，在雇傭蜂和觀察蜂階段根據(jù)式2進(jìn)行鄰域搜索，在偵查蜂階段丟棄經(jīng)過(guò)limit次搜索后未進(jìn)行更新的食物源，再根據(jù)式1得到新的食物源。

xi,j=xmin,j+rand×(xmax,j-xmin,j)

(1)

vi,j=xi,j+ri,j×(xi,j-xk,j)

(2)

其中，xmin,j,xmax,j分別為食物源第j(j∈{1,2,…,D})維分量的下限和上限，rand為(0,1)之間的隨機(jī)數(shù)；k∈{1,2,…,SN}且k≠i，ri,j是[-1,1]之間的隨機(jī)數(shù)。

通過(guò)對(duì)函數(shù)尋優(yōu)發(fā)現(xiàn)，基本ABC算法存在易陷入局部極值、易早熟收斂的問(wèn)題。胡珂等[12]提到，迭代后期食物源位置相似度高，導(dǎo)致位置更新速度變慢。文中認(rèn)為，迭代后期，現(xiàn)有搜索方程中的鄰居從當(dāng)前種群中選取，雖然偵查蜂階段會(huì)對(duì)枯竭的食物源進(jìn)行初始化，但依然有很大概率會(huì)選中當(dāng)前食物源的相似食物源，二者差異較小，導(dǎo)致搜索能力下降，不利于跳出局部最優(yōu)，從而導(dǎo)致算法早熟收斂。

Gao等[13]提出取消搜索方程中當(dāng)前食物源的作用，新解完全由種群中隨機(jī)選擇的解生成，能利用更多信息進(jìn)行搜索。但由于依舊是從當(dāng)前種群中選擇，選中相似食物源的概率依舊很大。因此，基于上述分析與啟發(fā)，文中提出采用重新初始化生成的新解引導(dǎo)搜索，由于新解與當(dāng)前食物源的相似度最低，有利于增強(qiáng)算法搜索能力。

新的搜索方程如下：

vi,j=xi,j+ri,j×(xi,j-Vr,j)

(3)

其中，Vr,j為根據(jù)式1生成的隨機(jī)新解Vr的第j維值，其他參數(shù)含義同式2。該式具有較強(qiáng)的探索能力和隨機(jī)性，利于算法跳出局部最優(yōu)解，適合即將枯竭的食物源，但不適合搜索勢(shì)頭良好的食物源，因此為了保持算法穩(wěn)定，在上式中加入種群中相鄰食物源的引導(dǎo)作用，同時(shí)在文獻(xiàn)[14]的啟發(fā)下，提出基于當(dāng)前食物源搜索現(xiàn)狀的自適應(yīng)搜索策略，以平衡兩方面的引導(dǎo)力度。新的搜索方程如下：

vi,j=xi,j+μ×ri,j×(xi,j-xk,j)+(1-μ)×φi,j×(xi,j-Vr,j)

(4)

其中，φi,j為[-1,1]之間的隨機(jī)數(shù)；μ為調(diào)節(jié)相鄰食物源引導(dǎo)力度與隨機(jī)新解引導(dǎo)力度的平衡因子，自適應(yīng)過(guò)程如下：

μ=1-trial(xi)/limit

(5)

其中，trial(xi)為食物源xi的連續(xù)開采失敗次數(shù)；limit為算法參數(shù)，一定程度上代表trial(xi)能達(dá)到的最大值。當(dāng)搜索到更優(yōu)解時(shí)，trial(xi)被重置為0，此時(shí)應(yīng)側(cè)重于相鄰食物源引導(dǎo)，以進(jìn)行平穩(wěn)搜索；隨著對(duì)食物源的開采接近枯竭，trial(xi)值增大，此時(shí)應(yīng)加大隨機(jī)新解的引導(dǎo)力度，引導(dǎo)算法向更有利區(qū)域進(jìn)行搜索，以跳出局部極值。另外，當(dāng)偵查蜂階段判定某食物源枯竭時(shí)，將對(duì)其進(jìn)行重新初始化，對(duì)應(yīng)trial(xi)被重置為0，雖然根據(jù)式4將側(cè)重于在相鄰食物源的引導(dǎo)下搜索新解，但由于當(dāng)前食物源本身是初始化后的新解，因而兩方面的引導(dǎo)相統(tǒng)一，此時(shí)式4滿足算法搜索需求。

1.2 多次高斯搜索機(jī)制

(6)

基于隨機(jī)新解引導(dǎo)的自適應(yīng)搜索策略的目的在于加大解的隨機(jī)性，提高種群多樣性，避免陷入局部最優(yōu)，因此新解會(huì)攜帶較多的隨機(jī)信息，但質(zhì)量不一定比舊解更好。而基本ABC算法的貪婪選擇策略更偏向于解質(zhì)量的提高，因此搜索到的新解有很大的概率會(huì)被丟棄，則新的搜索策略難以發(fā)揮作用。因而引入多次高斯搜索機(jī)制，在新解被丟棄前，以新解為中心，進(jìn)行多次高斯搜索，并保留搜索過(guò)程中得到的最優(yōu)解，再與舊解進(jìn)行貪婪選擇，達(dá)到保證解的質(zhì)量和跳出局部最優(yōu)之間的平衡。

綜上，改進(jìn)雇傭蜂階段流程如圖1所示。

圖1 改進(jìn)雇傭蜂階段流程

1.3 基于貓群思想的搜索過(guò)程

由于ABC算法原始搜索策略隨機(jī)選擇鄰居食物源和步長(zhǎng)進(jìn)行搜索，具有較好的探索能力。雖然算法早期需要較強(qiáng)的探索能力來(lái)搜索盡可能多的最優(yōu)解，但若能同時(shí)配合較強(qiáng)的開采能力，則能有效加快算法收斂速度，后期收斂精度也更高。因此眾多學(xué)者從提高開采能力的角度提出了不同的搜索策略。

文中從混合算法角度出發(fā)，提出基于貓群思想的搜索過(guò)程，一方面蜂群算法與貓群算法的混合研究較少，另一方面，對(duì)貓群算法研究后發(fā)現(xiàn)，通過(guò)有效結(jié)合，其局部搜索方式和全局搜索方式能更有針對(duì)性地提高ABC算法的局部開采能力和全局搜索能力，進(jìn)而提高算法性能。

1.3.1 貓群算法分析

貓群算法[15](cat swarm optimization，CSO)將貓的行為模式分為搜尋模式和跟蹤模式。搜尋模式下，通過(guò)對(duì)個(gè)體進(jìn)行多次擾動(dòng)，完成每個(gè)個(gè)體向局部最優(yōu)靠近的過(guò)程，即搜尋模式主要承擔(dān)局部搜索工作。跟蹤模式下，貓以一定速度對(duì)目標(biāo)獵物進(jìn)行跟蹤，通過(guò)與群體最優(yōu)位置進(jìn)行比較來(lái)更新個(gè)體位置。跟蹤模式本質(zhì)上是向全局最優(yōu)靠近的過(guò)程，這種“社會(huì)性”利于算法進(jìn)行全局搜索。

1.3.2 跟蹤模式優(yōu)化

跟蹤模式類似于粒子群算法，利用全局最優(yōu)位置不斷更新貓的當(dāng)前位置，使得當(dāng)前解不斷向最優(yōu)解逼近，最終達(dá)到全局最優(yōu)解。該模式下貓的速度與位置更新公式如下：

vi(t+1)=vi(t)+c1×rand×(x*-xi(t))

(7)

xi(t+1)=xi(t)+vi(t+1)

(8)

其中，x*表示貓群目前最好的位置；c1為加速系數(shù)；rand為[0,1]區(qū)間內(nèi)的隨機(jī)數(shù)；vi(t)和vi(t+1)分別表示第t次和第t+1次迭代時(shí)貓的速度；xi(t)和xi(t+1)分別表示第t次和第t+1次迭代時(shí)貓的位置。

該模式采用“速度-位移”模型，效果較好，但速度參數(shù)只應(yīng)用在跟蹤模式下，在搜尋模式中未應(yīng)用，利用率不高；考慮到要和采用“位移”模型的ABC算法結(jié)合，因此從簡(jiǎn)化算法和便于算法結(jié)合的角度出發(fā)，提出去掉速度參數(shù)，采用位置跟蹤方式，根據(jù)下式進(jìn)行解更新：

xi(t+1)=xi(t)+φi×(x*-xi(t))

(9)

其中，φi在[0,1]區(qū)間隨機(jī)取值，其他參數(shù)含義同式7?？芍?，該式同樣實(shí)現(xiàn)了跟蹤全局最優(yōu)解的功能，且更加簡(jiǎn)潔。

1.3.3 基于貓群思想的搜索過(guò)程

由上文可知，貓群算法的搜尋模式和跟蹤模式分別具有較強(qiáng)的局部搜索能力和全局搜索能力，而ABC算法具有易“早熟”收斂和后期開采能力較差的缺陷，因而提出將貓群思想引入到基本ABC算法中，在觀察蜂階段之后，加入基于貓群思想的搜索過(guò)程，同時(shí)采用順序模式分配方式，實(shí)現(xiàn)算法結(jié)合。

順序模式分配是相對(duì)于貓群算法隨機(jī)分配方式而言的。隨機(jī)分配方式是指在確定執(zhí)行跟蹤模式個(gè)體的數(shù)量后，隨機(jī)選擇對(duì)應(yīng)數(shù)量的個(gè)體執(zhí)行跟蹤模式，而順序模式分配方式是先對(duì)個(gè)體依據(jù)適應(yīng)度值進(jìn)行升序排序，再順序依次分配模式的方式。具體地，根據(jù)適應(yīng)度值和MR參數(shù)，將食物源分為較優(yōu)食物源和較差食物源，對(duì)較優(yōu)食物源執(zhí)行搜尋模式，對(duì)較差食物源執(zhí)行跟蹤模式。

通過(guò)對(duì)兩種模式的分析，可知順序模式分配的好處在于搜尋模式能對(duì)優(yōu)質(zhì)食物源進(jìn)行充分精細(xì)的局部搜索，有針對(duì)性地提高算法的局部搜索能力；而跟蹤模式能引導(dǎo)較差食物源向全局最優(yōu)靠近，減少對(duì)該食物源的無(wú)效搜索次數(shù)，提升算法效率；從而通過(guò)兩種模式的配合，提高算法整體搜索能力。

1.4 混合人工蜂群算法

綜上，在基本ABC算法的雇傭蜂階段引入基于隨機(jī)新解引導(dǎo)的自適應(yīng)搜索策略作為原始搜索策略的補(bǔ)充，同時(shí)結(jié)合多次高斯搜索機(jī)制，完成雇傭蜂階段尋優(yōu)任務(wù)；在觀察蜂階段之后，引入基于貓群思想的搜索過(guò)程，采用順序模式分配方式，對(duì)較優(yōu)解執(zhí)行搜尋模式，對(duì)較差解執(zhí)行優(yōu)化后的跟蹤模式；在搜索過(guò)程結(jié)束后進(jìn)入偵查蜂階段，完成接下來(lái)的尋優(yōu)任務(wù)，得到混合人工蜂群算法(hybrid ABC，HABC)。算法流程如圖2所示。

圖2 混合人工蜂群算法流程

2 實(shí)驗(yàn)驗(yàn)證

2.1 參數(shù)設(shè)置與測(cè)試函數(shù)

為驗(yàn)證文中改進(jìn)策略的有效性，將僅引入基于隨機(jī)新解引導(dǎo)的自適應(yīng)搜索策略和多次高斯搜索機(jī)制的改進(jìn)人工蜂群算法命名為MABC，將僅采用優(yōu)化跟蹤模式的改進(jìn)貓群算法命名為MCSO，HABC算法則是在MABC的基礎(chǔ)上引入基于貓群思想的搜索過(guò)程，該搜索過(guò)程采用優(yōu)化后的跟蹤模式。選取6個(gè)測(cè)試函數(shù)對(duì)算法性能進(jìn)行驗(yàn)證，并將結(jié)果分別與基本人工蜂群算法ABC和基本貓群算法CSO進(jìn)行比較。

測(cè)試函數(shù)見表1。其中Sphere、Schewefel 2.22為單模函數(shù)，單模函數(shù)檢驗(yàn)算法局部搜索能力，測(cè)試算法收斂速度和尋優(yōu)精度；Griewank、Ackley、Rastrigin、Schaffer為復(fù)雜多模函數(shù)，多模函數(shù)檢驗(yàn)算法綜合能力，測(cè)試算法搜索全局最優(yōu)解、擺脫局部最優(yōu)解的能力。

算法參數(shù)設(shè)置：種群規(guī)模N=60，個(gè)體維數(shù)D=30和D=60,最大評(píng)價(jià)次數(shù)分別為2 000和4 000。對(duì)于CSO算法,SMP=5,SRD=0.2,CDC=0.8,SPC=0,MR=0.02,c1=2.05。MCSO算法參數(shù)同上。對(duì)于MABC算法，q=10,其他參數(shù)同上。對(duì)于HABC算法，MR=0.5,其他參數(shù)同上。算法獨(dú)立運(yùn)行30次，并記錄多次運(yùn)行結(jié)束后的最優(yōu)值、平均值、最差值和標(biāo)準(zhǔn)差，展示在表2中。各算法的收斂曲線對(duì)比如圖3所示，為了便于對(duì)比，只展示了部分迭代次數(shù)下的收斂曲線。

表2 各算法收斂精度對(duì)比

續(xù)表2

2.2 結(jié)果分析

由表2可知，與ABC算法相比，MABC算法收斂精度更高；與CSO算法相比，MCSO算法收斂精度更高；而HABC算法收斂精度則優(yōu)于MABC和MCSO算法，表明文中提出的改進(jìn)策略和混合人工蜂群算法的有效性。具體的，對(duì)于單模函數(shù)，MABC算法收斂精度得到一定程度提高，對(duì)于多模復(fù)雜函數(shù)，MABC算法優(yōu)勢(shì)突出，能收斂到理論最優(yōu)解，表明基于隨機(jī)新解引導(dǎo)的搜索策略和多次高斯搜索機(jī)制相結(jié)合，能有效增加種群多樣性、緩解算法易陷入局部極值的問(wèn)題。MCSO算法在單模和多模函數(shù)上收斂精度都得到不同程度的提升，表明優(yōu)化后的跟蹤模式不僅簡(jiǎn)化了算法，而且具有更強(qiáng)的搜索能力。HABC算法在MABC算法的基礎(chǔ)上，增加了基于貓群思想的搜索過(guò)程，由表2可知，對(duì)于單模函數(shù)，HABC算法能唯一收斂到理論最優(yōu)解，表明了基于貓群思想的搜索過(guò)程能有效提高算法局部搜索能力；對(duì)于多模函數(shù)，HABC算法與MABC表現(xiàn)一致，除了Ackley函數(shù)，均能收斂到理論最優(yōu)解，表明HABC算法具有MABC算法的優(yōu)點(diǎn)，對(duì)于多模復(fù)雜函數(shù)具有較好的優(yōu)化性能。而在Ackley函數(shù)上，應(yīng)用優(yōu)化策略后收斂精度也得到了一定程度的提升。

圖3 各算法收斂過(guò)程對(duì)比

通過(guò)圖3對(duì)各算法收斂速度進(jìn)行分析可知，MCSO算法相比CSO算法，達(dá)到最后收斂精度所需的迭代次數(shù)有了不同程度的下降；MABC算法與ABC算法相比，在多模函數(shù)上，所需迭代次數(shù)顯著下降；HABC算法則在單模函數(shù)和多模函數(shù)上，都能在最少的迭代次數(shù)內(nèi)達(dá)到最優(yōu)收斂精度。

可見，優(yōu)化后的跟蹤模式在簡(jiǎn)化算法的同時(shí)，一定程度上加快了算法收斂；基于隨機(jī)新解引導(dǎo)的搜索策略與多次高斯搜索機(jī)制的結(jié)合，能有效應(yīng)對(duì)多模函數(shù)易陷入局部極值的問(wèn)題，進(jìn)而提升算法收斂速度；基于貓群思想的搜索過(guò)程則通過(guò)加強(qiáng)算法的局部搜索能力和全局搜索能力，顯著提高了對(duì)單模函數(shù)的收斂速度。

3 結(jié)束語(yǔ)

針對(duì)基本人工蜂群算法存在的缺陷，提出新的混合人工蜂群算法。具體地，在雇傭蜂階段引入基于隨機(jī)新解引導(dǎo)的搜索策略和多次高斯搜索機(jī)制；在觀察蜂階段后，引入基于貓群思想的搜索過(guò)程；對(duì)原始跟蹤模式進(jìn)行優(yōu)化。

通過(guò)標(biāo)準(zhǔn)函數(shù)的驗(yàn)證表明，基于隨機(jī)新解引導(dǎo)的搜索策略與多次高斯搜索機(jī)制的結(jié)合能有效應(yīng)對(duì)多模函數(shù)易陷入局部極值的問(wèn)題，有效提升算法收斂速度和收斂精度；基于貓群思想的搜索過(guò)程能有效提高算法局部搜索能力和全局搜索能力，收斂精度得到大幅提升；優(yōu)化后的跟蹤模式在簡(jiǎn)化算法的同時(shí)一定程度上提高了算法收斂速度；綜合以上優(yōu)化策略的混合人工蜂群算法的優(yōu)化性能最優(yōu)。