環(huán)形拓撲遺傳學(xué)習(xí)人工蜂群算法研究*

王貞 李旭飛

摘要：針對人工蜂群算法探索能力強而開發(fā)能力較弱的問題，提出一種基于環(huán)形拓撲的遺傳學(xué)習(xí)人工蜂群算法。算法中引入環(huán)形拓撲遺傳學(xué)習(xí)策略來生成精英個體，可以增加種群多樣性，保證算法的探索能力。同時，在搜索方程中利用精英個體和全局最優(yōu)個體進行搜索引導(dǎo)，可以提高算法的開發(fā)能力，加快算法的收斂速度。通過對6個標(biāo)準(zhǔn)測試函數(shù)實驗，與其他算法比較發(fā)現(xiàn).所提出的算法較其他算法具有較好的優(yōu)化性能。

關(guān)鍵詞：遺傳學(xué)習(xí);人工蜂群算法;環(huán)形拓撲

中圖分類號：TP301.6文獻標(biāo)志碼：A

0 引言

2005年Karaboga通過模擬蜜蜂群體覓食行為提出了人工蜂群算法（Artificial Bee Co10ny Algorithm，ABC）。自ABC算法提出以來，由于其良好的優(yōu)化性能，受到學(xué)者們的廣泛關(guān)注，對ABC算法改進及應(yīng)用進行了大量研究。過去十幾年間，盡管ABC算法得到了有效的改進，但仍存在一些挑戰(zhàn)。與其他基于種群的算法類似，ABC算法在優(yōu)化過程中仍然存在收斂性弱的問題。這一問題與算法中的隨機搜索方向和隨機步長有關(guān)，ABC算法具有較強的探索能力，而開發(fā)能力較弱。一般而言，算法的探索能力和開發(fā)能力是互相對立的，因此為了提高算法的性能，有必要在算法的探索能力和開發(fā)能力間尋求平衡?；谝陨戏治?，本論述采用環(huán)形拓撲遺傳學(xué)習(xí)機制，以此平衡算法的探索能力和開發(fā)能力，提出基于環(huán)形拓撲遺傳學(xué)習(xí)的人工蜂群算法（Genetic learning artificial bee co10ny algorithmwith ring topo10gy，ABC-RTGL）。

ABC-RTGL算法中采用遺傳學(xué)習(xí)策略生成精英個體，并在搜索方程中利用精英個體和全局最優(yōu)個體進行引導(dǎo)，增強算法的開發(fā)能力。另一方面，由于環(huán)形拓撲可以擴大算法搜索的可行域，在增強算法開發(fā)能力的同時，平衡算法探索能力，在算法中引入環(huán)形拓撲。通過對測試問題的實驗發(fā)現(xiàn)，提出的ABC-RTGL算法具有較好的優(yōu)化性能，是可行的有效算法。

1人工蜂群算法

受蜜蜂群體采蜜行為啟發(fā)，Karaboga提出一種新的群智能優(yōu)化算法——人工蜂群算法。該算法中的人工蜂種群設(shè)置為三種類型，包括雇傭蜂、跟隨蜂和偵查蜂。首先，在雇傭蜂階段中，雇傭蜂對可行域進行隨機搜索來尋找食物源，并將食物源信息傳遞給在蜂巢中等待搜索食物源的跟隨蜂。其次，在跟隨蜂階段中，跟隨蜂根據(jù)雇傭蜂傳遞回蜂巢的食物源信息，選擇需要進行搜索的食物源進行采蜜。最后，在偵查蜂階段，如果所有食物源中有已經(jīng)被開采完蜂蜜的，則該食物源將會被拋棄，同時與之相對應(yīng)的雇傭蜂將轉(zhuǎn)變?yōu)閭刹榉?，重新隨機搜索新食物源。在算法的整個搜索過程中，食物源對應(yīng)的是優(yōu)化問題的候選解，而食物源的質(zhì)量代表了候選解的優(yōu)劣。

在ABC算法中，采用隨機初始化方式生成初始人工蜂種群，其生成方式如式（1）所示。

x=x+rand（0，1）（x+x）（1）

其中，i=1，…SN，j=1，…，D，SN表示種群數(shù)量，D表示問題維數(shù)，rand（0，1）為0-1之間的隨機數(shù)，x和x分別表示個體第j維的上界和下界。

雇傭蜂通過以下搜索方程對候選解進行搜索：

v=x+φ（x-x）（2）

其中，k∈{1，…，SN}是隨機選取的不同于i的指標(biāo)，在生成新的候選解時僅有一個隨機選取的解;j∈{1，…，D}是隨機選取的指標(biāo)，這意味著新候選解與舊解之間僅有一維發(fā)生了變化。φ是[-1，1]上均勻分布的隨機數(shù)。

跟隨蜂根據(jù)一定的概率對雇傭蜂找到的食物源進行選擇更新.其按如下方式進行計算：

其中，fit表示第i個食物源的適應(yīng)值。選擇好食物源的跟隨蜂同樣利用搜索方程（2）對食物源進行搜索。

2 基于環(huán)形拓撲的遺傳學(xué)習(xí)人工蜂群算法

通過上述ABC算法的描述，分析出算法具有較強的探索能力，而開發(fā)能力較弱，這種結(jié)構(gòu)在一定程度上會影響算法的收斂速度。針對ABC算法的上述問題，本論述引入環(huán)形拓撲的遺傳學(xué)習(xí)策略，來平衡算法的探索能力和開發(fā)能力，從而提高算法的優(yōu)化性能。

2.1環(huán)形拓撲

由于環(huán)形拓撲結(jié)構(gòu)可以增大可能的搜索空間，在算法搜索過程中，能夠有效增加算法的種群多樣性，增強算法的探索能力。因此，在精英個體生成過程中采用環(huán)形拓撲有利于算法維持種群多樣性。環(huán)形拓撲生成精英個體方式如式（4）所示。

2.2 遺傳學(xué)習(xí)策略

為了平衡算法的探索能力和開發(fā)能力，在原始ABC算法中加入遺傳學(xué)習(xí)策略。該策略主要通過引人遺傳算法的交叉、變異和選擇操作來生成能夠引導(dǎo)算法搜索的有效精英個體。具體策略如下算法2。

算法2：遺傳學(xué)習(xí)策略

Step 1：對個體o進行交叉操作。隨機選擇個體x，計算其目標(biāo)函數(shù)值fit。若fitk，則按環(huán)形拓撲式（4）生成個體o，否則將隨機個體x賦給個體o。

Step 2：對個體o進行變異操作。若隨機數(shù)小于變異概率，則對個體o按初始化方式隨機生成。

Step 3：對個體o進行選擇操作。估計個體o的目標(biāo)函數(shù)值，若其目標(biāo)函數(shù)值小于當(dāng)前精英個體e的目標(biāo)函數(shù)值，則利用o對e進行替換。

Step 4：若o的目標(biāo)函數(shù)值小于當(dāng)前全局最優(yōu)解的目標(biāo)函數(shù)值，則對當(dāng)前全局最優(yōu)解進行更新。

Step 5：若e違背更新代數(shù)超過s，則利用輪盤賭選擇在當(dāng)前局部最優(yōu)解中進行重新選擇生成。判定是否所有精英個體都已更新，若更新完成，則返回精英種群和當(dāng)前全局最優(yōu)解，否則返回Step l。

通過對原始ABC算法的搜索方程分析，發(fā)現(xiàn)該搜索方程具有較強的探索能力，而開發(fā)能力較弱。因此，受Lin等學(xué)者啟發(fā)，對ABC算法的原始搜索方程進行如下改進。

其中，k∈{1，…，SN}是隨機選取的不同于i的指標(biāo)，j∈{1，…，D}是隨機選取的指標(biāo)，φ是[-1，1]止均勻分布的隨機數(shù)，φ是[0，1.5]上均勻分布的隨機數(shù)。搜索方程中e表示由遺傳學(xué)習(xí)策略生成的第i個精英個體的第j維，y是當(dāng)前全局最優(yōu)解的第j維。由此可以看出，搜索方程（5）包含兩個學(xué)習(xí)項，其一是遺傳學(xué)習(xí)項可以增強算法的探索能力;其二是全局學(xué)習(xí)項，可以增強算法的開發(fā)能力。

2.3 基于環(huán)形拓撲的遺傳學(xué)習(xí)人工蜂群算法

結(jié)合上述的環(huán)形拓撲和遺傳學(xué)習(xí)策略，構(gòu)建了基于環(huán)形拓撲的遺傳學(xué)習(xí)人工蜂群算法（Genetic learningartificial bee co10ny algorithm with ring topo10gy，ABC-RTGL），具體算法流程如下算法3。

算法3：ABC-RTGL算法

Step 1：初始化。在搜索空間中利用初始化方程（1）隨機生成SN個初始個體組成初始化種群。計算初始種群目標(biāo)函數(shù)值和適應(yīng)值。記錄當(dāng)前最優(yōu)解和最優(yōu)值。

Step 2：雇傭蜂階段。利用算法2生成精英個體，并用搜索方程（5）生成新的個體，計算新個體的目標(biāo)函數(shù)值和適應(yīng)值。若新個體的目標(biāo)函數(shù)值優(yōu)于舊個體，則用新個體替換種群中的舊個體，否則不替換。

Step 3：跟隨蜂階段。對種群中的每個個體利用式（3）計算選擇概率，并利用輪盤賭選擇對跟隨蜂需要更新的個體進行選擇。利用算法2生成精英個體，并用搜索方程（5）生成新的個體，計算新個體的目標(biāo)函數(shù)值和適應(yīng)值。若新個體的目標(biāo)函數(shù)值優(yōu)于舊個體，則用新個體替換種群中的舊個體，否則不替換。

Step 4：偵查蜂階段。若種群中存在個體未被更新次數(shù)超過上限limit時，利用式（1）隨機生成一個新個體對該個體進行替換。

Step 5：記錄當(dāng)前最優(yōu)解和最優(yōu)值。若達到終止條件，則結(jié)束搜索，返回最優(yōu)解和最優(yōu)值，否則，返回Step 2。

3 數(shù)值實驗

為了檢驗ABC-RTGL算法的優(yōu)化性能，本節(jié)中將對6個標(biāo)準(zhǔn)測試函數(shù)進行測試實驗，測試維數(shù)D=30，最優(yōu)值均為0，具體特征見表1所列。實驗中種群數(shù)量SN為100，limit為200，最大循環(huán)代數(shù)MaxCycle對應(yīng)1000，算法獨立運行25次。

表2給出了實驗結(jié)果，包括均值和標(biāo)準(zhǔn)差。同時，在表中給出5%置信水平下Wilcoxon統(tǒng)計測試結(jié)果，在表中以“+、=、-”分別表示ABC-RTGL算法優(yōu)于、相同、劣于其他算法結(jié)果。實驗結(jié)果中較好值均由黑體標(biāo)出。表2所列，ABC-RTGL算法幾乎在所有測試問題上的優(yōu)化結(jié)果都要比原始ABC算法和GABC算法要好。

圖1給出了測試問題的收斂曲線圖來進一步展現(xiàn)ABC-RTGL算法的優(yōu)化性能。從圖中可以看出，ABC-RTGL算法的收斂速度較ABC算法和GABC算法更快。以上實驗結(jié)果說明，ABC-RTGL算法不論在搜索最優(yōu)解的質(zhì)量方面還是在魯棒性方面，都比ABC算法和GABC算法更好。

4 結(jié)束語

為了更好的求解全局優(yōu)化問題，本論述給出一種基于環(huán)形拓撲遺傳學(xué)習(xí)的人工蜂群算法。由于ABC算法注重探索能力而開發(fā)能力較弱，因此引入遺傳學(xué)習(xí)策略來增強算法的開發(fā)能力。另一方面，為了平衡探索能力和開發(fā)能力，引入了環(huán)形拓撲來生成部分精英個體。通過與其他算法在測試問題上的比較結(jié)果可以看出，ABC-RTGL算法具有較好的尋優(yōu)性和魯棒性。