一種基于“擁擠度”概念的人工蜂群算法改進(jìn)*

王文國，吳宗月

（曲阜師范大學(xué) 信息科學(xué)與工程學(xué)院，山東 日照 276826）

一種基于“擁擠度”概念的人工蜂群算法改進(jìn)*

王文國，吳宗月

（曲阜師范大學(xué) 信息科學(xué)與工程學(xué)院，山東 日照 276826）

為了彌補(bǔ)原始人工蜂群算法中執(zhí)行效率低和收斂速度慢的缺點(diǎn)，提出了一種引入“擁擠度”概念的人工蜂群算法。當(dāng)采蜜蜂進(jìn)行鄰域搜索時(shí)，通過擁擠度對(duì)采蜜蜂進(jìn)行數(shù)量調(diào)控，避免過多的采蜜蜂在同一蜜源附近搜索；當(dāng)擁擠度高時(shí)，增加偵查蜂的數(shù)量，從而有效提高算法的全局搜索能力，特別是加快算法后期的收斂。通過4個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)對(duì)改進(jìn)后的算法進(jìn)行可行性驗(yàn)證，結(jié)果表明改進(jìn)的人工蜂群算法在執(zhí)行效率和后期收斂速度上都優(yōu)于原始的人工蜂群算法，可用于網(wǎng)絡(luò)中組播QoS路由選擇的優(yōu)化過程。

人工蜂群算法；擁擠度；收斂速度；組播路由選擇

0 引 言

現(xiàn)代多媒體通信對(duì)網(wǎng)絡(luò)的帶寬、延時(shí)、延時(shí)抖動(dòng)、丟包率等參數(shù)提出了嚴(yán)格要求。而網(wǎng)絡(luò)服務(wù)質(zhì)量路由（QoSR）算法的目的是在網(wǎng)絡(luò)中搜索最佳路由，該路由須滿足帶寬、延時(shí)、丟包率等條件。由于包含兩個(gè)或兩個(gè)以上不相關(guān)可加或可乘性參數(shù)的路由選擇是一個(gè)NPC問題[1]，傳統(tǒng)路由算法無法在有效時(shí)間內(nèi)找到最優(yōu)解，因而啟發(fā)式搜索算法已成為解決多約束QoS路由問題的有效途徑[2-4]。

基于群體智能優(yōu)化的人工蜂群算法模擬了自然界不同類型蜜蜂的勞動(dòng)分工，通過對(duì)食物源信息的某種共享，達(dá)到對(duì)食物源的最佳搜索與采集效果。最早提出的人工蜂群算法用于解決函數(shù)優(yōu)化問題[1]。近年來，該算法憑借其工作原理簡(jiǎn)單、控制參數(shù)相對(duì)較少、算法過程易于實(shí)現(xiàn)的特點(diǎn)，而受到越來越多的關(guān)注。隨著有關(guān)研究的不斷深入，人工蜂群算法已經(jīng)被成功應(yīng)用于解決計(jì)算機(jī)網(wǎng)絡(luò)的QoS單播或多播路由選擇問題[4]。

許多研究者嘗試對(duì)人工蜂群算法進(jìn)行各種改進(jìn)。Mezura等[5]使用一個(gè)新算子改善逼近可行域的方式，該算子允許生成偏離當(dāng)前最優(yōu)解的搜索方向，并將兩種動(dòng)態(tài)容錯(cuò)方法應(yīng)用于約束處理機(jī)制，以便生成新的可行域；Lei等[6]對(duì)蜂群算法的鄰域方程進(jìn)行改進(jìn)，使搜索具有了非線性下降特性，從而實(shí)現(xiàn)對(duì)搜索空間的壓縮，同時(shí)在搜索方程中加入一個(gè)隨機(jī)擾亂項(xiàng)，以提升優(yōu)化結(jié)果的準(zhǔn)確性和有效性；Tarun等[7]在搜索演化過程中使用種群規(guī)模下降機(jī)制來加強(qiáng)對(duì)算法的控制，同時(shí)使用等級(jí)選擇策略來維持種群的多樣性，以提高算法的性能；Saxena等[8]為了平衡算法中采集現(xiàn)有蜜源和搜索更好蜜源的能力，使用當(dāng)前蜂的最優(yōu)值與全局最優(yōu)解比較以產(chǎn)生新解，從而給出一種新的搜索策略。

但是，上述各種人工蜂群算法中仍然存在執(zhí)行效率低和收斂速度慢的缺點(diǎn)。為了克服此類缺陷，本文將針對(duì)采蜜蜂引入“擁擠度”的概念，即試圖通過調(diào)控蜜蜂的空間分布密度，進(jìn)一步優(yōu)化人工蜂群算法的搜索性能。

1 人工蜂群算法

在人工蜂群算法中，把蜜蜂分為三類：觀察蜂、偵查蜂和采蜜蜂。采蜜峰存儲(chǔ)著蜜源的相關(guān)信息，且將這些信息以一定的概率在舞蹈區(qū)與觀察蜂分享；觀察蜂駐留在蜂巢的舞蹈區(qū)，通過采蜜蜂與之分享的蜜源信息選擇蜜源；偵查蜂則進(jìn)行隨機(jī)搜索以發(fā)現(xiàn)新的蜜源。一般而言，各類蜜蜂的采蜜過程可用圖1表示，其中S為偵查蜂，EF為采蜜峰，UF為觀察蜂。

圖1 蜜蜂采蜜過程示意

人工蜂群算法的主要流程如下：

（1）初始化；

（2）重復(fù)以下四個(gè)步驟：

①根據(jù)存儲(chǔ)的食物源信息，采蜜峰確定最優(yōu)食物源的位置；

②根據(jù)采蜜峰分享的食物源信息，觀察蜂以一定的概率選擇食物源；

③偵查蜂在搜索區(qū)域不斷搜索，以發(fā)現(xiàn)新的食物源；

④存儲(chǔ)目前最優(yōu)的食物源信息。

（3）直到滿足某種停止條件。

在上述算法中，假定蜜蜂的數(shù)量N等于食物源的數(shù)量。

初始化階段，人工蜂群算法按照式（1）隨機(jī)生成N個(gè)解決方案：

式中，i的取值范圍是（1,2,…,N），j的取值范圍是（1,2,…,D），N的大小與食物源相等，D是向量的維度，Xjmin和Xj

max分別是解空間的下限和上限。

采蜜蜂階段，計(jì)算每種解決方案的適應(yīng)性，然后每個(gè)蜜蜂在當(dāng)前位置附近按照式（2）產(chǎn)生新的解決方案：

式中，k的取值范圍是（1,2,…,N），且k≠i，j是隨機(jī)產(chǎn)生的，而rand()是介于-1與1之間的隨機(jī)數(shù)。新位置的產(chǎn)生與之前的位置有關(guān)，且是在附近隨機(jī)選擇的。新位置New_的適應(yīng)度將按照式（3）計(jì)算，然后通過貪婪選擇機(jī)制與之前的位置進(jìn)行比較，以便選取適應(yīng)度更好的位置。

在觀察蜂階段，主要是根據(jù)采蜜蜂提供的食物源相關(guān)信息，以一定的概率選擇食物源。適應(yīng)度的計(jì)算公式是：

食物源被選擇的概率如下：

式中，fiti是第i個(gè)位置的適應(yīng)度。對(duì)于觀察蜂來說，它們使用輪盤賭選擇法挑選食物源，以確保適應(yīng)度較好的蜜源被選擇的概率更大。觀察蜂確定食物源后，開始并行執(zhí)行任務(wù)。在某個(gè)食物源附近搜索時(shí)，如果食物源的適應(yīng)度一直得不到改善，那么達(dá)到預(yù)先設(shè)定的循環(huán)次數(shù)limit的食物源就會(huì)被放棄。放棄蜜源后的采蜜峰變成偵查蜂，開始在整個(gè)搜索空間中隨機(jī)搜索新的解決方案，搜索到蜜源之后偵查蜂又轉(zhuǎn)變成采蜜峰。

最后，系統(tǒng)存儲(chǔ)到目前為止適應(yīng)度最佳的蜜源，然后重復(fù)搜索過程直至終止條件滿足。比如，到達(dá)預(yù)先設(shè)定的最大周期數(shù)或者搜索結(jié)果小于預(yù)先設(shè)定的誤差等。

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

在上述基本人工蜂群算法的搜索機(jī)制中，不難看出適應(yīng)度高的食物源附近會(huì)有大量的采蜜峰進(jìn)行鄰域搜索，而局部匯聚大量蜜蜂將導(dǎo)致其他區(qū)域的搜索能力下降，其結(jié)果會(huì)降低該算法的收斂速度和搜索效率。

圖2展示了一般情況下蜂群可能遇到的蜜源分布情形。

圖2 一種假設(shè)的蜜源分布情況

如圖2所示，假設(shè)x1是采蜜蜂的當(dāng)前位置，而系統(tǒng)在搜索過程中，一個(gè)新的蜜源將會(huì)在x1的鄰域空間出現(xiàn)。例如，圖中的x2是一個(gè)局部的最優(yōu)值，但是算法在執(zhí)行過程中會(huì)在x1附近不斷發(fā)現(xiàn)比x1優(yōu)秀的解，從而吸引大量的采蜜峰在臨近區(qū)域搜索，因此算法往往會(huì)在局部最優(yōu)位置的鄰域空間來回?cái)[動(dòng)，容易陷入局部收斂。采蜜峰的大量聚集必然會(huì)影響到x3、x4等優(yōu)秀蜜源的發(fā)現(xiàn)效率，導(dǎo)致算法運(yùn)行后期的收斂速度相對(duì)較慢。為了避免這種不利情況出現(xiàn)，引入“擁擠度”這一概念，以限制采蜜峰的數(shù)量：當(dāng)擁擠度低時(shí)，蜂群不需要進(jìn)行任何的調(diào)整，當(dāng)擁擠度高時(shí)，適當(dāng)減少采蜜蜂的數(shù)量，同時(shí)增加偵查蜂的數(shù)量來擴(kuò)大對(duì)解空間的全局搜索。這樣就能在一定程度上幫助算法避免早熟現(xiàn)象，同時(shí)在后期提高算法的收斂速度。

定義crowd為擁擠度參數(shù)，表示解空間中采蜜蜂與其鄰域空間中其他個(gè)體之間的接近程度。crowd的值越大，表示該區(qū)域內(nèi)的采蜜蜂越少。

觀察蜂選擇食物源的概率相應(yīng)修改為：

此外，原始人工蜂群算法初始化時(shí)，蜜蜂的群體會(huì)被分為采蜜峰和觀察蜂，觀察蜂在蜂巢中被動(dòng)等待采蜜峰帶回的蜜源信息。本文的另一個(gè)改進(jìn)思路是假設(shè)蜂群中偵查蜂一直存在，一般使其比例保持在蜂群總數(shù)的5%～10%左右，這樣會(huì)迫使部分觀察蜂轉(zhuǎn)變?yōu)閭刹榉洌员憷^續(xù)保持對(duì)解空間的不斷搜索，進(jìn)而有利于提高算法后期的收斂速度。

3 仿真測(cè)試和分析

人工蜂群算法作為一種仿生學(xué)的智能算法，在搜索過程中會(huì)表現(xiàn)出很強(qiáng)的隨機(jī)性。按照上節(jié)引入擁擠度的改進(jìn)蟻群算法，具體實(shí)現(xiàn)方案包含三個(gè)步驟：第一步，在采蜜峰階段所獲得的解將按照適應(yīng)值的優(yōu)劣進(jìn)行降序排列；第二步，觀察蜂對(duì)排序后的解以一定的概率進(jìn)行選擇；第三步，跟蹤優(yōu)勢(shì)解的分布情況，及時(shí)調(diào)整蜂群的多樣性及搜索方向，當(dāng)擁擠度高時(shí)，對(duì)采蜜峰的數(shù)量進(jìn)行限制。

為了測(cè)試上述改進(jìn)蟻群算法的性能，在Intel(R) Pentium E6500、CPU主頻2.93 GHz、2 GB內(nèi)存、Windows 7操作系統(tǒng)下，運(yùn)用MATLAB 7.8進(jìn)行仿真試驗(yàn)。所采用的4個(gè)測(cè)試函數(shù)及其值域范圍羅列在表1中。

實(shí)驗(yàn)中，主要關(guān)注兩種人工蜂群算法的優(yōu)化曲線和算法執(zhí)行時(shí)間，從而比較其收斂速度和執(zhí)行效率。實(shí)際測(cè)試中的參數(shù)設(shè)置如下：測(cè)試函數(shù)維度D=5，解空間中蜜源的數(shù)量NP=100、limit=50、maxCycle=500。由于算法在執(zhí)行過程中存在隨機(jī)性，本次實(shí)驗(yàn)選取的數(shù)據(jù)取算法隨機(jī)執(zhí)行50次后所得的平均值。

圖3、圖4、圖5和圖6分別為Sphere、Griewank、Rastrigin和Rosebrock函數(shù)的優(yōu)化曲線對(duì)比。從中可以看出，改進(jìn)后的蜂群算法之收斂速度明顯優(yōu)于原始的人工蜂群算法。

表2則是改進(jìn)后的蜂群算法與原始算法在執(zhí)行時(shí)間上的對(duì)比。從表2中可以看出，在相同的尋優(yōu)精度和相同的參數(shù)設(shè)置情況下，改進(jìn)后的算法在運(yùn)行時(shí)間上減少了35%以上，明顯地提高了算法的尋優(yōu)效率。

表1 仿真所用的四個(gè)測(cè)試函數(shù)

圖3 Sphere優(yōu)化曲線

圖4 Griewank優(yōu)化曲線

圖5 Rastrigin優(yōu)化曲線

圖6 Rosenbrock優(yōu)化曲線

表2 改進(jìn)的蜂群算法與原始算法的運(yùn)行時(shí)間對(duì)比

4 結(jié) 語

本文從人工蜂群算法的搜索機(jī)制出發(fā)，通過引入擁擠度參數(shù)對(duì)采蜜蜂數(shù)量進(jìn)行調(diào)控，以避免過多的采蜜蜂在同一蜜源附近搜索，同時(shí)保持偵查峰占蜂群總數(shù)的比例為5%～10%左右。仿真測(cè)試結(jié)果表明，改進(jìn)后的蜂群算法能夠有效提高算法的收斂速度和執(zhí)行效率。下一步工作是把本文改進(jìn)的蜂群算法用于解決網(wǎng)絡(luò)中組播QoS路由選擇的優(yōu)化問題。

[1] Karaboga D.An Idea Based on Honey Bee Swarm for Numerical Optimization[R].TR06.Kayseri Erciyes University,2005.

[2] Wang Z,Crowcroft J.Quality-of-Service for Routing Supporting Multimedia Applications[J]. IEEE Journal of Selected Areas in Communicatio ns,1996,14(07):1228-1234.

[3] 劉洋,王文國.差異化密集蟻群算法與網(wǎng)絡(luò)QoS路由選擇[J].通信技術(shù),2015,48(08):949-953. LIU Yang,WANG Wen-guo.Differentiated Dense Ant Colony Algorithm and Network QoS Routing Selection[J]. Communications Technology,2015,48(08):949-953.

[4] 楊原.基于群智能優(yōu)化算法的QoS組播路由算法研究[D].西安:西安科技大學(xué),2014. YANG Yuan.Research on QoS Multicast Routing Algorithm based on Swarm Intelligence Optimization Algorithm[D].Xi'an:Xi'an University of Science and Technology,2014.

[5] Mezura M E,Damian A M,Cetina D O.Smart Flight and Dynamic Tolerances in the Artificial Bee Colony for Constrained Optimization[C]. Barcelona: Proceedings of 2010 IEEE Congress on Evolutionary Computation,2010:1-8.

[6] Lei X J,Huang X,Zhang A D.Improved Artificial Bee Colony Algorithm and Its Application in Data Clustering[C]. Changsha:Proceedings of IEEE 5th International Conference on Bio-Inspired Computing,2010:514-521.

[7] Tarun K S,Millie P.Some Modifications to Enhance the Performance of Artificial Bee Colony[C]. Brisbane:Proceedings of IEEE Congress on Evolutionary Computation,2012:1-8.

[8] Saxena S,Sharma K,Shiwani S,et al.Best Artificial Bee Colony Using Structured Swarm[C]. Gurgaon: Proceedings of IEEE International Advanced Computing Conference,2014:1354-1360.

王文國（1960—），男，博士，教授，主要研究方向?yàn)榫W(wǎng)絡(luò)與信息安全；

吳宗月（1990—），男，碩士研究生，主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)。

Improved Artificial Bee Colony Algorithm based on Congestion concept

WANG Wen-guo, WU Zong-yue
(Dept. of Info. Science & Engineering, Qufu Normal University, Rizhao Shandong 276826, China)

In order to overcome shortcomings of low efficiency and slow convergence in original ABC(artificial bee colony) algorithm, a new concept of "congestion degree" is introduced into the basic ABC procedure. The proposed congestion concept is used mainly in employed bee, and when many employed bees search in adjacent domains, these bees would affect each other; by limiting the number of employed bees working in the same area and increasing the number of scouts, the global searching ability and speed of convergence of the algorithm would be enhanced. The feasibility and performance of the improved ABC algorithm is verified with four standard testing functions, and the results show that the improved ABC algorithm outperforms the basic algorithm in both execution efficiency and speed of convergence. This new algorithm could be used to optimize QoS multicast routing protocol.

artificial bee colony algorithm; congestion; speed of convergence; multicast routing protocol

National high level talents attracting program of China（No.200461）

TP311

A

1002-0802(2016)-07-0867-05

10.3969/j.issn.1002-0802.2016.07.014

2016-03-10;

2016-06-20 Received date:2016-03-10;Revised date:2016-06-20

國家人事部高層次留學(xué)人員回國工作資助項(xiàng)目（No.200461）)