一種遺傳學(xué)習(xí)人工蜂群算法

杜振鑫，韓德志，劉廣鐘

(上海海事大學(xué) 信息工程學(xué)院，上海 201306)

1 引 言

2016年，文獻(xiàn)[12]在傳統(tǒng)GA交叉算子的基礎(chǔ)上，提出了一種新的遺傳學(xué)習(xí)策略(Genetic Learning，GL)，吸收借鑒了現(xiàn)有群體智能進(jìn)化算法的研究成果及“行為遺傳學(xué)”原理，綜合利用gbest與精英解的信息，與傳統(tǒng)GA有明顯的不同，在提高了傳統(tǒng)GA搜索效率的同時(shí)，仍然保持了GA較高的全局搜索能力，為解決這一問題提供了新的思路.

本文將GL策略作為一種通用框架引入人工蜂群算法及其變種的偵察蜂階段，采用GL策略生成新的食物源代替被拋棄食物源.與簡單使用GA交叉算子不同，采用GL策略，可以在利用GA全局搜索特性的同時(shí)，利用gbest與較好解加快收斂速度.GA和ABC分屬于不同的進(jìn)化計(jì)算分支，具有不同的理論背景和搜索特性.多種文獻(xiàn)的研究表明[13]，由于GA的交叉、變異算子沒有方向性，因此GA具有較強(qiáng)的全局搜索能力，但也因?yàn)槿鄙倬⒔獾囊龑?dǎo)而具有較慢的收斂速度.利用GA算法構(gòu)造出來的新食物源位于問題空間地形圖中的不同峰區(qū)并且具有較好的多樣性，有助于算法跳出局部最優(yōu)解，GA中的選擇操作作用后產(chǎn)生的新食物源位于問題空間中的較好位置，能夠?yàn)榉N群的下一步搜索提供較好的指導(dǎo)，避免個(gè)體在錯(cuò)誤的指導(dǎo)下搜索造成計(jì)算資源的浪費(fèi)和算法效率的低下.一般情況下被拋棄食物源已經(jīng)處于局部峰區(qū)，僅在少數(shù)幾維上處于劣勢，其適應(yīng)度往往比較優(yōu)秀，卻因陷入局部最優(yōu)解而無法繼續(xù)進(jìn)化.因此，被拋棄食物源與GA結(jié)合，可以促進(jìn)被拋棄食物源快速從一個(gè)峰區(qū)跳躍到另一個(gè)峰區(qū)，增強(qiáng)算法的全局搜索能力.而且，GL策略在GA的基礎(chǔ)上，綜合使用了gbest、被拋棄食物源與其他精英解的信息，在保持GA全局搜索能力的同時(shí)，進(jìn)一步加快了收斂速度，增加了種群多樣性，實(shí)現(xiàn)了1+1>2的效果.在著名的cec2014函數(shù)集上的實(shí)驗(yàn)表明，改進(jìn)算法在尋優(yōu)精度與收斂速度方面明顯優(yōu)于同類改進(jìn)算法ABC-GOBL和ABC-CL.同時(shí)，改進(jìn)算法具有較好的普適性，可以作為通用框架嵌入到最新提出的ILABC、ABC_elite等改進(jìn)人工蜂群算法中，形成更高性能的算法ILABC_GL、ABC_elite_GL.

2 人工蜂群算法

在ABC[1]中，蜂群被分為三種：雇傭蜂、觀察蜂和偵察蜂.雇傭蜂搜索食物源，之后將食物源的信息以舞蹈的形式通知觀察蜂；觀察蜂收到信息后，按照優(yōu)先選擇優(yōu)秀食物源的原則挑選某個(gè)食物源繼續(xù)開采.若某個(gè)食物源的適應(yīng)度經(jīng)過limit次未更新，說明這個(gè)食物源已沒有繼續(xù)開采的必要，需要拋棄該食物源，該食物源對(duì)應(yīng)的雇傭蜂轉(zhuǎn)變?yōu)閭刹旆洌S機(jī)初始化一個(gè)新的食物源代替該食物源，但是為了保持系統(tǒng)的穩(wěn)定性，每一輪只允許trial值最高的一個(gè)食物源初始化.

在ABC算法中，一個(gè)食物源代表一個(gè)待優(yōu)化問題的可行解.每個(gè)食物源的花蜜數(shù)量相應(yīng)代表待優(yōu)化問題的適應(yīng)度，雇傭蜂和觀察蜂的數(shù)量相等.不失一般性，設(shè)待優(yōu)化問題為求最小值，首先按照公式(1)隨機(jī)生成SN個(gè)初始解(SN等于雇傭蜂或者觀察蜂的數(shù)量)：

Xi，j=Xmin，j+rand(0，1)(Xmax，j-Xmin，j)

(1)

其中，i=1，2，…SN，j=1，2，…D，D是決策變量的數(shù)量，也就是待優(yōu)化問題的維數(shù)，Xmin，j是第j維的下界，Xmax，j是第j維的上界.初始化之后，ABC在下面的三個(gè)階段搜索問題的最優(yōu)解：

1)雇傭蜂階段：每個(gè)雇傭蜂僅僅與一個(gè)食物源相關(guān)聯(lián)，所以在雇傭蜂階段，雇傭蜂的數(shù)量與食物源的數(shù)量相等.在該階段，每只雇傭蜂在相應(yīng)的食物源Xi處，利用搜索方程隨機(jī)選擇第j維更新，生成一個(gè)新的食物源Vi：

Vi，j=Xi，j+φi，j*(Xi，j-Xk，j)

(2)

其中，φi，j是[-1，1]之間的隨機(jī)數(shù)，j∈{1，2，…，D}是隨機(jī)選擇的一個(gè)維，k∈{1，2，…SN}是隨機(jī)選擇的一個(gè)食物源，k≠i.發(fā)現(xiàn)新的食物源Vi之后，如果Vi的函數(shù)值f(Vi)好于f(Xi)，就用Vi替換Xi，否則Xi保持不變.

2)觀察蜂階段：在所有雇傭蜂完成了勘探之后，觀察蜂根據(jù)接收到的信息隨機(jī)選擇一個(gè)食物源，進(jìn)一步開采.觀察蜂按照公式選擇食物源：

(3)

其中，fiti是食物源Xi的適應(yīng)度值，設(shè)待優(yōu)化問題是求最小值，則函數(shù)值越小，適應(yīng)度值越高；SN是雇傭蜂的數(shù)量，也等于觀察蜂的數(shù)量.選擇食物源之后，觀察蜂用公式搜索新的候選解，跟雇傭蜂階段一樣，采用貪婪選擇策略，如果搜索的新的解的適應(yīng)度更好，則替換掉原食物源，否則原食物源保持不變.

3)偵察蜂階段：如果一個(gè)食物源經(jīng)過limit次搜索仍然沒有成功更新，該食物源被拋棄，該食物源對(duì)應(yīng)的雇傭蜂成為偵察蜂，該偵察蜂按照公式(1)通過初始化被拋棄的食物源代替被拋棄的食物源.

3 遺傳學(xué)習(xí)框架

本文利用GL策略構(gòu)造新的食物源代替被拋棄食物源，構(gòu)造過程采用了交叉、變異、選擇三個(gè)基本遺傳算子.交叉算子作用于被拋棄食物源、精英解與gbest，以綜合利用三者的信息，增加多樣性，同時(shí)加快收斂速度.此外，算法繼承了傳統(tǒng)GA中的均勻變異策略使得產(chǎn)生的新食物源能夠覆蓋到整個(gè)問題的任意區(qū)域.進(jìn)一步的，選擇算子以較大概率保證構(gòu)造的新食物源比被拋棄食物源更好，從而有效牽引整個(gè)種群搜索越來越好的區(qū)域.

1)交叉算子：對(duì)于每個(gè)被拋棄的食物源Xi，按照下面的公式產(chǎn)生一個(gè)子代sol=[sol1，sol2，…，solD] ：

首先，在當(dāng)前種群中隨機(jī)抽取兩個(gè)食物源，其序號(hào)是s1、s2，s1≠s2≠i，令：

(4)

(5)

其中，rd是在[0，1]之間均勻分布的隨機(jī)數(shù)，gbest是當(dāng)前最優(yōu)個(gè)體.在公式的作用下，如果被拋棄的食物源Xi在Xi、Xs1、Xs2三者中適應(yīng)度最優(yōu)(即函數(shù)值最小，這里以求最小值為例)，則其后代sol來自Xi與gbest的交叉.否則，如果被拋棄食物源Xi不是三者之中最優(yōu)的個(gè)體，則其子代的第d維來自個(gè)體s1、s2中最好的一個(gè)個(gè)體s的第d維.

公式(5)與傳統(tǒng)GA算法的不同之處在于，GA算法隨機(jī)選擇種群中的兩個(gè)個(gè)體進(jìn)行交叉產(chǎn)生子代，而公式(5)同時(shí)采用了競爭策略，子代的第d維，來自i，s1、s2三者中較好的個(gè)體的第d維.在這種方式作用下，一個(gè)被拋棄食物源傾向于在自身、精英解和gbest之間進(jìn)行算術(shù)交叉，從而產(chǎn)生潛在更優(yōu)秀的子代sol.否則，如果被拋棄食物源i是當(dāng)前種群中較差的一個(gè)，sol將會(huì)有更多的維度來自其余更優(yōu)秀的精英個(gè)體.因此，不同于傳統(tǒng)的GA中隨機(jī)選擇種群中的兩個(gè)個(gè)體進(jìn)行交叉，以上交叉算子同時(shí)利用了被拋棄食物源的自身信息、gbest和精英解的信息，在已經(jīng)發(fā)現(xiàn)的優(yōu)良位置上進(jìn)行交叉操作，有助于交叉算子更加有效地產(chǎn)生優(yōu)秀的子代，而且增加了種群多樣性.同時(shí)，被拋棄食物源、gbest和精英解的引導(dǎo)加快了GA的收斂速度.

2)變異算子：產(chǎn)生子代sol之后，采用變異概率Pm對(duì)sol的每一維隨機(jī)變異，類似于傳統(tǒng)GA中的均勻變異策略.對(duì)于sol的第d維，產(chǎn)生一個(gè)隨機(jī)數(shù)[0，1]之間的隨機(jī)數(shù)rand，若rand

sold=Xmin，d+rand*(Xmax，d-Xmin，d)

(6)

其中，Xmin，d和Xmax，d分別表示搜索空間的第d維的下界和上界(d=1，2，…D).rand是[0，1]之間的隨機(jī)數(shù).這種變異方式保證了產(chǎn)生的子代能夠到達(dá)搜索空間的任意位置，從而為個(gè)體注入新的基因、防止新食物源的早熟收斂.

3)選擇算子：通過交叉和變異產(chǎn)生的子代sol將在選擇操作中與被拋棄食物源Xi競爭，如果找到的sol好于Xi，則提前結(jié)束GL過程；否則會(huì)重復(fù)上述試探過程Tmax次，直到找到比Xi更好的新食物源sol.如果超過規(guī)定的Tmax次試探仍然沒有找到好于被拋棄食物源Xi的新食物源，則取Tmax次試探過程中生成的最好的一個(gè)食物源作為新食物源，避免浪費(fèi)計(jì)算資源.這種機(jī)制保證新產(chǎn)生的食物源絕大部分情況下只會(huì)隨著代數(shù)進(jìn)化而不會(huì)發(fā)生退化，從而更有利于找到更好的峰區(qū).

4)整體流程：在ABC的每次迭代，對(duì)每個(gè)滿足triali>limit的食物源i，都執(zhí)行以上試探操作，包括交叉、變異和選擇操作，從而構(gòu)造一個(gè)優(yōu)良的新食物源代替被拋棄食物源，每個(gè)被拋棄食物源Xi最多可以試探Tmax次，如果找到更好的食物源則提前退出.注意上述過程是反復(fù)試探(try)而非迭代(iteration)，因此每次尋找新的食物源sol都是重新開始，而與上次的試探無關(guān)，因?yàn)镚L策略的目的是快速跳出局部最優(yōu)解而非精細(xì)搜索，采用試探操作可以快速的在不同峰區(qū)跳轉(zhuǎn)，尋找更有潛力的峰區(qū)以進(jìn)一步開采，而迭代操作主要圍繞某一個(gè)固定的峰區(qū)搜索.GL策略如圖1所示.

01：fori=1toSN /?對(duì)每個(gè)食物源i?/02： if triali>limit/?如果食物源i的trial值大于limit，則執(zhí)行GL策略?/03： ifiisnotgbest /?普通個(gè)體與gbest分開處理?/ 04： k=0； /?k是試探次數(shù)計(jì)數(shù)器?/05： while(k

圖1 GL策略的偽代碼

Fig.1 Pseudo-code of the GL strategy

從圖1可以看出，與基本ABC不同，在ABC-GL中，所有滿足triali>limit的食物源i均執(zhí)行GL操作(第1行)，而在ABC中每一輪只有一個(gè)trial值最大的食物源被初始化，這是因?yàn)榛続BC中，被初始化的解質(zhì)量較低，過多的食物源被初始化，容易引起算法的退化和震蕩.如果被拋棄食物源恰好是gbest，則公式(5)中的gbest用隨機(jī)選擇的5個(gè)食物源中不同于gbest的一個(gè)食物源代替(第25行)；若經(jīng)過Tmax次試探之后仍未發(fā)現(xiàn)更好的解，則gbest保持不變，以保證gbest不退化.

通過在ABC的偵察蜂階段嵌入GL策略，可以得到ABC-GL算法，其具體步驟如下：

Step1. 初始化：

a.根據(jù)公式(1)隨機(jī)生成含有SN個(gè)初始解的種群

b.評(píng)價(jià)整個(gè)種群，F(xiàn)Es=SN；/*FEs代表函數(shù)評(píng)價(jià)次數(shù)*/

Step2. 雇傭蜂階段：

fori=1：SN，do

a.根據(jù)公式(2)生成一個(gè)候選解Vi

b.評(píng)價(jià)f(Vi)，F(xiàn)Es=FEs+1

c.若f(Vi)

否則，triali=triali+1；

endfor

Step3. 由公式計(jì)算每個(gè)食物源Xi的概率pi，t=0，i=1；

Step4. 觀察蜂階段：

whilet<=SN，do /*輪盤賭選擇一個(gè)食物源開采*/

ifrand(0，1)

a.根據(jù)公式(2)，生成一個(gè)候選解Vi

b.評(píng)價(jià)f(Vi)，F(xiàn)Es=FEs+1

c.若f(Vi)

否則，triali=triali+1；

d.t=t+1

endif

i=i+1，若t=SN，置i=1

endwhile

Step5. 觀察蜂階段：

a.記住全局最優(yōu)解gbest

b.根據(jù)圖1，執(zhí)行GL模塊

Step6. 若FEs>=Max_FEs，算法終止，輸出gbest，

否則，轉(zhuǎn)step 2.

與基本ABC相比，ABC-GL與ABC的區(qū)別是在偵察蜂階段采用GL模塊(Step 5的黑體部分)，取代ABC的隨機(jī)初始化，其他部分與基本ABC相同.GL策略可以作為一種通用框架嵌入到其他改進(jìn)人工蜂群算法中，只需要將圖1中的遺傳學(xué)習(xí)策略替換掉對(duì)應(yīng)算法的偵察蜂階段即可.例如，將圖1嵌入到ABC_elite[16]的偵察蜂階段，即可得到基于遺傳學(xué)習(xí)框架的增強(qiáng)型算法ABC_elite_GL；將圖1中的遺傳學(xué)習(xí)策略嵌入到ILABC[17]可以得到增強(qiáng)的ILABC_GL算法等.

4 實(shí)驗(yàn)結(jié)果與討論

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

實(shí)驗(yàn)采用cec2014[14]中的1-16號(hào)函數(shù)，該函數(shù)集中的所有函數(shù)在基本函數(shù)的基礎(chǔ)上采用偏移、旋轉(zhuǎn)增加求解難度，具有大量的局部最優(yōu)點(diǎn)，可以較好的測試算法的綜合性能.其中，F(xiàn)1-F3是單峰函數(shù)，F(xiàn)4-F16是多峰函數(shù).

表1 四種算法在cec2014函數(shù)集上的測試結(jié)果Table 1 Experimental results of 4 algorithms on cec2014 test suite

參數(shù)設(shè)置：SN=30，limit=100，D=30，最大函數(shù)評(píng)價(jià)次數(shù)Max_FEs=300000.GL策略新增了兩個(gè)參數(shù)Pm與Tmax，根據(jù)實(shí)驗(yàn)確定較好的設(shè)置是Pm=0.03，Tmax=20.實(shí)驗(yàn)在同樣條件下重復(fù)運(yùn)行30次.

圖2 收斂曲線圖Fig.2 Convergence curves

4.2 實(shí)驗(yàn)結(jié)果與分析

表 1給出了ABC、ABC-GOBL、ABC-CL、ABC-GL四種算法在cec2014中1-16號(hào)函數(shù)上的實(shí)驗(yàn)結(jié)果.實(shí)驗(yàn)的主要目的是測試本文提出的GL策略是否可以增強(qiáng)ABC算法的性能.mean和std指標(biāo)分別表示求解結(jié)果的均值與標(biāo)準(zhǔn)差.根據(jù)表1，ABC-GL算法的求解精度除了f2之外，都好于另外3種算法.圖2給出了ABC、ABC-GOBL、ABC-CL、ABC-GL四種算法在函數(shù)F1、F6、F9、F16上的收斂曲線圖.從圖2來看，ABC-GL只在算法開始運(yùn)行的較短時(shí)間收斂速度落后于其他算法，但是很快超過其他算法.這是因?yàn)锳BC、ABC-GOBL雖然在較短的時(shí)間內(nèi)收斂速度很快，卻由于沒有充分利用多個(gè)精英解的信息，從而導(dǎo)致算法很快陷入局部最優(yōu)解，ABC-CL雖然利用了多個(gè)精英解的信息幫助算法跳出局部最優(yōu)解，卻由于缺少gbest的引導(dǎo)而收斂較慢.從圖2中F6、F9、F16上的收斂曲線圖來看，ABC-CL、ABC-GL直到算法運(yùn)行結(jié)束，仍然保持進(jìn)化狀態(tài)而未停滯，而另外兩種算法ABC與ABC-GOBL的曲線圖很快變成一條直線.這說明，由于ABC-CL與ABC-GL采用的多個(gè)精英引導(dǎo)，不容易陷入局部最優(yōu)解.同時(shí)，由于ABC-GL采用了新穎的GL策略，同時(shí)使用gbest與多個(gè)精英的信息交叉，因此收斂速度更快，且不容易陷入局部最優(yōu)解.表1、表2與表3同時(shí)給出了Wilcoxon[15]顯著性水平0.05的秩和檢驗(yàn)結(jié)果，+、=、-分別表示應(yīng)用GL策略的增強(qiáng)算法好于、等于、差于其他對(duì)比算法.表1、表2與表3的最后一行給出了Wilcoxon的統(tǒng)計(jì)結(jié)果.

表2 應(yīng)用GL策略加強(qiáng)ABC_elite算法性能的實(shí)驗(yàn)結(jié)果Table 2 Experimetal results to enhance the performance of ABC_elite using GL strategy

表3 應(yīng)用GL策略加強(qiáng)ILABC算法性能的實(shí)驗(yàn)結(jié)果Table 3 Experimetal results to enhance the performance of ILABC using GL strategy

GL策略的主要作用是增強(qiáng)其他改進(jìn)ABC算法的性能.表2給出了應(yīng)用GL策略增強(qiáng)ABC_elite[16]性能的實(shí)驗(yàn)結(jié)果，其中，應(yīng)用遺傳學(xué)習(xí)框架(GL)、綜合學(xué)習(xí)(CL)策略、反向?qū)W習(xí)(GOBL)策略的ABC_elite分別稱為ABC_elite_GL，ABC_elite_CL，ABC_elite_GOBL.從表2來看，在單峰函數(shù)f1-f3上，ABC_elite_GL算法的性能優(yōu)勢較小.而在多峰函數(shù)f4-f16上，ABC-elite_GL只在函數(shù)f6上稍差于ABC_elite_CL，在其余所有多峰函數(shù)上都表現(xiàn)出最好的性能.

表3給出了應(yīng)用GL策略增強(qiáng)ILABC[17]算法的結(jié)果.從表3結(jié)果來看，除了多峰函數(shù)f4、f7上，ILABC_GL沒有取得最好結(jié)果，在其余所有函數(shù)上均取得了最好的結(jié)果.表2和表3的結(jié)果說明，應(yīng)用GL策略可以有效增強(qiáng)其他改進(jìn)人工蜂群算法的性能，加快算法的收斂速度，提高求解精度.

5 結(jié) 論

為了加快ABC及其改進(jìn)算法的收斂速度并提高搜索精度，本文將遺傳學(xué)習(xí)策略作為通用框架引入人工蜂群算法，用于增強(qiáng)這些算法的性能.遺傳學(xué)習(xí)策略較好的平衡了算法的全局搜索與加速收斂之間的矛盾，能夠較好的彌補(bǔ)各種改進(jìn)人工蜂群算法的不足.本文僅提供一種通用框架，而非一種獨(dú)立算法.實(shí)驗(yàn)表明，采用遺傳學(xué)習(xí)策略作為通用框架，可以方便的嵌入各種改進(jìn)人工蜂群算法，顯著提高這些算法的收斂速度，提高其搜索精度.