改進(jìn)人工蜂群算法在信道分配上的應(yīng)用

劉俊霞，賈振紅，覃錫忠，常 春，王 浩

LIU Junxia1，3,JIA Zhenhong1,QIN Xizhong1,CHANG Chun2,WANG Hao2

1.新疆大學(xué) 信息科學(xué)與工程學(xué)院，烏魯木齊 830046

2.中國移動新疆分公司，烏魯木齊 830063

3.新疆機(jī)電職業(yè)技術(shù)學(xué)院，烏魯木齊 830011

改進(jìn)人工蜂群算法在信道分配上的應(yīng)用

劉俊霞1，3，賈振紅1，覃錫忠1，常 春2，王 浩2

LIU Junxia1，3,JIA Zhenhong1,QIN Xizhong1,CHANG Chun2,WANG Hao2

1.新疆大學(xué) 信息科學(xué)與工程學(xué)院，烏魯木齊 830046

2.中國移動新疆分公司，烏魯木齊 830063

3.新疆機(jī)電職業(yè)技術(shù)學(xué)院，烏魯木齊 830011

移動通信網(wǎng)絡(luò)中頻率資源是有限的，為了提高無線資源的利用率，將改進(jìn)的人工蜂群算法用于解決無線信道分配問題。提出的算法用逐步減小鄰域搜索范圍的動態(tài)步長來均衡局部與全局搜索能力；對單個體引入選擇性變異技術(shù)，增加了種群的多樣性，加快了算法的收斂速度。仿真結(jié)果表明，改進(jìn)后的算法能較好地解決無線信道分配問題，提高了算法的收斂率和收斂速度。

信道分配；人工蜂群算法；選擇性變異；搜索步長

1 引言

移動通信系統(tǒng)面臨著移動用戶數(shù)快速增長與有限的頻率資源之間的矛盾，為了提高有限的頻率資源利用率，采用信道分配技術(shù)是行之有效的方法。通常是根據(jù)干擾約束條件以及信道分配問題模型，按照不同的算法求解信道的最佳分配方案。在早期，信道分配問題的研究大多是以圖形理論或啟發(fā)式方法為基礎(chǔ)的，近年來，主要用神經(jīng)網(wǎng)絡(luò)、遺傳算法、模擬退火算法和微正則退火算法來處理信道分配問題[1-4]。但在搜索最優(yōu)解過程中，它們依然存在收斂時間較長，容易陷入或難以擺脫局部最優(yōu)解等缺點(diǎn)。

為了解決上述缺點(diǎn)，利用固定信道分配的數(shù)學(xué)模型，在普通人工蜂群算法的基礎(chǔ)上，提出了一種用改進(jìn)的人工蜂群算法來求解最佳信道分配的方案。人工蜂群算法是一類新興的基于蜜蜂群智能搜索行為的優(yōu)化算法，它與其他智能算法一樣具有優(yōu)良的優(yōu)化性能。由于智能算法自身還存在一定缺陷，許多研究者提出了一些改進(jìn)措施并應(yīng)用于不同的領(lǐng)域[5-10]。本文針對人工蜂群算法收斂速度慢，易陷入局部最優(yōu)等缺點(diǎn)，將人工蜂群算法進(jìn)行改進(jìn)，并用于解決固定信道分配問題；仿真證明了該算法的優(yōu)越性。

2 信道分配模型

信道分配問題即頻率分配問題，其基本模型是可行性頻率分配，目標(biāo)是在不違反干擾約束的前提下，所有小區(qū)都能分配到所需數(shù)量的頻點(diǎn)。通常只考慮三種主要干擾約束條件：同頻干擾（CCC）、鄰頻干擾（ACC）、共地干擾（CSC）。通常用一個N×N維的兼容矩陣C=Cij(i，j=1，2，…，N)來表示以上主要的干擾約束條件（N為蜂窩系統(tǒng)的小區(qū)數(shù)），矩陣C中對角元素Cij表示分配給小區(qū)i的信道之間的最小間隔，矩陣中的非對角元素Cij(i≠j)表示分配給小區(qū)i中的信道與小區(qū) j中的信道的最小間隔。每個小區(qū)頻率需求數(shù)用矩陣R=[ri]，i=1，2，…，N來表示，其中矩陣 R中的元素ri表示第i個小區(qū)的頻點(diǎn)需求數(shù)，可用的頻點(diǎn)集合為FN={1 ，2，…，F(xiàn)Num} ，其中FNum=max{fij}，設(shè) fik為給第i個小區(qū)的第k個位置分配的頻點(diǎn)，fik取值為正整數(shù)，fjl同理，它們之間應(yīng)滿足| fik-fjl|≥Cij，(1≤i，j≤N; 1≤k，l≤ri)，目標(biāo)函數(shù)的適應(yīng)度S(F)定義為信道分配方案F違反約束條件的總數(shù)量，F(xiàn)ikjl描述 fik與 fjl是否滿足約束條件Cij，數(shù)學(xué)模型如下[4，11]：

即在給定的C、R和可用頻點(diǎn)集合FN，找到使目標(biāo)函數(shù)S(F)值最小即為0的信道分配方案F。

信道分配方案F采用最小間隔實(shí)數(shù)編碼方式，F(xiàn)是一個N×rmax的矩陣，即：

式中rmax是需求向量R的最大值，fij=χ，1≤χ≤FNum，表示將頻點(diǎn) χ分配給第i個小區(qū)的第 j個位置，當(dāng)ri≤j≤rmax時，fij=0。

3 人工蜂群算法

在人工蜂群算法中蜂群主要有引領(lǐng)峰、跟隨蜂和偵查蜂，一個蜜源位置(θi)與一個引領(lǐng)蜂(ei)相對應(yīng)，ei先出去尋找蜜源位置θi,跟隨蜂(oi)在舞蹈區(qū)等待ei帶回蜜源的相關(guān)信息，等到ei回到舞蹈區(qū)后，oi根據(jù)ei的舞蹈得知θi信息，采用公式（4）以概率Pi選擇一個θi，并在其鄰域內(nèi)采用公式（5）搜索新蜜源，比較蜜源θi和在其領(lǐng)域內(nèi)搜索的新蜜源，選擇較好的蜜源采蜜。在迭代過程中，若某個oi在設(shè)定的搜索次數(shù)內(nèi)沒有獲得更好的蜜源，ei便放棄該θi，同時成為偵查蜂。并隨機(jī)搜索新蜜源。

令蜂群數(shù)量為M，第t次迭代之后，現(xiàn)有的蜜源位置集合為{θi(t)}，i=1，2，…，M，ei在該次搜索之后，獲得的蜜源收益度為H(θi(t))，oi選擇θi(t)的概率為：

oi以概率Pi選擇θi(t)之后，在其鄰域內(nèi)選擇一個新的蜜源(θi(t+1))進(jìn)行訪問，選擇的方法為：

其中ψi為隨機(jī)產(chǎn)生的步長。如果H(θi(t+1))＞H(θi(t))，則用θi(t+1)更蜜源θi(t)，否則θi(t)不變。若在連續(xù)的 Limt次迭代之后，均不能發(fā)現(xiàn)更優(yōu)的蜜源，則ei放棄該θi，同時成為偵查蜂隨機(jī)搜索新蜜源[12-14]。

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

4.1 調(diào)整的鄰域搜索步長

人工蜂群算法中，跟隨蜂在選中的蜜源鄰域范圍內(nèi)按式（5）搜索新蜜源，搜索步長具有隨機(jī)性，算法尋優(yōu)速度相對較慢，易陷入局部最優(yōu)或易錯過全局最優(yōu)解。本文根據(jù)文獻(xiàn)[15]的研究成果，在實(shí)驗(yàn)數(shù)據(jù)的基礎(chǔ)上將隨機(jī)產(chǎn)生的步長改為隨迭代次數(shù)動態(tài)變化的步長，不僅提高了算法的搜索精度，還能較好地平衡局部與全局搜索能力，如式（6）所示：

其中，tmax為最大迭代次數(shù)；θmax(t)為第t次迭代的最優(yōu)蜜源位置；0.5(1-t/tmax)是鄰域搜索步長的動態(tài)權(quán)值，它隨迭代次數(shù)的增加線性減小。該動態(tài)權(quán)值在算法初期有較大的值，使跟隨蜂有較強(qiáng)的全局搜索能力，加快算法收斂速度；在算法后期隨迭代次數(shù)的增加有較小的值，使跟隨蜂有較強(qiáng)的開發(fā)能力并增強(qiáng)了算法的搜索精度，從而使蜂群在全局搜索和局部搜索之間達(dá)到動態(tài)平衡。

4.2 新增的選擇性變異技術(shù)

為了提高種群的多樣性和算法的收斂速度，引入了選擇性變異技術(shù)。

選擇性變異技術(shù)是一種單個體進(jìn)化的方法，在信道分配問題中首先對待變異的個體計算適應(yīng)度值S(F)，即公式（1）的值。若S(F)＞0，則遍歷該個體解F中的每一個頻點(diǎn) fij，用公式（2）進(jìn)行分析，考察該頻點(diǎn) fij是否對其他小區(qū)產(chǎn)生干擾。如果不產(chǎn)生干擾，則什么也不做；如果產(chǎn)生干擾，則需要對該頻點(diǎn) fij進(jìn)行變異替換。替換頻點(diǎn) fij的頻點(diǎn)必須滿足第i個小區(qū)的共地約束（CSC），即Cii，同時還必須與前PCell個具有較大分配難度的小區(qū)滿足兼容矩陣所要求的鄰頻約束（ACC）和同頻約束（CCC）。分配難度deg計算公式為[16]：

5 信道分配算法及步驟

5.1 蜂群采蜜行為與信道分配問題的對應(yīng)關(guān)系

一個蜜源位置θi與一個信道分配方案Fi相對應(yīng)，蜜源收益度H(θi)代表該蜜源相對應(yīng)的信道分配方案Fi的質(zhì)量，H(θi)越大相應(yīng)的Fi違反約束條件的頻點(diǎn)數(shù)越少，即解越接近最優(yōu)解。具體關(guān)系見公式（8）。最大收益度與最佳信道分配方案相對應(yīng)，搜索最佳蜜源的快慢代表尋找最佳信道分配方案的速度，即算法收斂速度的快慢。

公式（8）中S(Fi)見公式（1）。在信道分配模型中目標(biāo)是找到最小值，即找到使目標(biāo)函數(shù)S(F)=0的信道分配方案F，該信道分配方案中沒有違反干擾約束條件的頻點(diǎn)；在改進(jìn)蜂群算法中目標(biāo)是求最大值，即蜜源的收益度H(θi)的最大值。信道分配目標(biāo)函數(shù)S(F)的值越小，蜜源收益度值H(θi)越大，當(dāng)S(F)為最小值等于0時，蜜源收益度 H(θi)達(dá)到最大值。因此在改進(jìn)蜂群算法中，求解最大收益度和信道分配方案中的尋找S(F)=0的最佳信道分配方案是相對應(yīng)的。

5.2 信道分配算法步驟

步驟1確定蜂群規(guī)模M，最大迭代次數(shù)tmax，可用頻點(diǎn)總數(shù)FNum、PCell、Limt的值，引領(lǐng)蜂個數(shù)與跟隨蜂個數(shù)相等，等于M。

步驟2初始化M個可行解Fi(i=1，2，…，M)，計算初始化后的各個可行解的適應(yīng)度S(F)和各個可行解所對應(yīng)的蜜源收益度H(θi)，并記錄全局最優(yōu)解θmaxx（收益度H(θi)最大或適應(yīng)度S(F)最?。?。若初始解中有S(F)=0的解，結(jié)束算法并輸出S(F)=0的信道分配方案，否則執(zhí)行下一步。

步驟3模擬蜂群行為，oi根據(jù)ei的舞蹈得知θi信息，用公式（4）以概率 Pi選擇一個θi(t)，并在其鄰域內(nèi)用公式（6）搜索新蜜源θi(t+1)。

步驟4比較蜜源θi(t)和θi(t+1)收益度，選擇蜜源收益度大的進(jìn)行采蜜。

步驟5對步驟4選中的蜜源進(jìn)行3.2節(jié)的選擇性變異。計算變異后的蜜源的收益若此次變異產(chǎn)生的蜜源收益度大于變異之前的蜜源收益度，則接受此次變異，否則沿用變異之前選中的蜜源。

步驟6若某些引領(lǐng)蜂對應(yīng)的蜜源（解）收益度在Limt次循環(huán)后都沒有改進(jìn)，則放棄該蜜源，同時引領(lǐng)蜂轉(zhuǎn)變?yōu)閭刹旆潆S機(jī)搜索一個新蜜源取代該蜜源。計算本次迭代全局最優(yōu)解θmax，與上一次迭代的全局最優(yōu)解比較，選擇收益度大的作為本次迭代的全局最優(yōu)解。

步驟7計算所有蜜源的收益度H(θi)和蜜源相對應(yīng)可行解的適應(yīng)度S(F)，若有S(F)=0，即蜜源收益度達(dá)到最大值，則結(jié)束運(yùn)算并輸出S(F)=0的信道分配方案；否則跳轉(zhuǎn)到步驟3進(jìn)入下一次迭代。

步驟8若達(dá)到最大迭代次數(shù)都沒有找到使S(F)=0的最佳信道分配方案，則結(jié)束運(yùn)算，并認(rèn)為算法不收斂。

6 算法仿真

算法用MATLAB 7.0進(jìn)行仿真，頻率分配方案采用實(shí)數(shù)最小間隔編碼方式，種群個數(shù) M=35，引領(lǐng)蜂個數(shù)=跟隨蜂個數(shù)=M,算法循環(huán)總代數(shù) tmax=200,Limt=6, PCell=5；對文獻(xiàn)[4]的21小區(qū)系統(tǒng)進(jìn)行頻率分配，可用頻率總數(shù)FNum分別取55、65、70、80、90，每種可用頻點(diǎn)數(shù)各運(yùn)行50次。圖1為本文算法在采用可用頻點(diǎn)數(shù)為55的收斂代數(shù)仿真圖，圖1中橫坐標(biāo)t為算法迭代次數(shù)，縱坐標(biāo)為適應(yīng)度函數(shù)S(F)的最小值，即信道分配方案F違反約束條件的總數(shù)量的最小值。表1為本文算法與文獻(xiàn)[4]算法的比較結(jié)果；表2為人工蜂群算法與本文算法比較結(jié)果。

圖1 可用頻點(diǎn)數(shù)為55的仿真圖

表1 本文算法與文獻(xiàn)[4]算法仿真結(jié)果比較

表2 普通人工蜂群算法與本文算法仿真結(jié)果比較

由圖1可以看出，在可用頻點(diǎn)數(shù)不充足為55的情況下，算法也有著較快的收斂速度，僅用17次迭代即可收斂。

從表1的實(shí)驗(yàn)結(jié)果中看出，當(dāng)可用頻點(diǎn)數(shù)設(shè)為70時，文獻(xiàn)[4]只有90%的收斂率，而本文算法能達(dá)到100%的收斂率，且平均收斂代數(shù)在3.8代；同時應(yīng)用到65和55個可用頻點(diǎn)數(shù)中，文獻(xiàn)[4]不收斂，而本文算法的收斂率仍能達(dá)到100%，且平均收斂代數(shù)也只為5.4代和18代，可用頻點(diǎn)為55的仿真結(jié)果如圖1所示。這表明改進(jìn)后的人工蜂群算法在頻率分配上的效果優(yōu)于傳統(tǒng)的微正則退火算法。從表2的結(jié)果中可用看出，在頻點(diǎn)數(shù)充足且相同的情況下，改進(jìn)的人工蜂群算法的收斂代數(shù)在各可用頻點(diǎn)的情況下均小于基本人工蜂群算的收斂代數(shù)，并且當(dāng)頻點(diǎn)數(shù)為65和55時，基本人工蜂群算法不收斂，而本文算法的收斂率為100%。用本文算法去處理文獻(xiàn)[17]的信道分配問題時，僅用1次迭代就可以實(shí)現(xiàn)，而文獻(xiàn)[17]卻用19次迭代才收斂。這些實(shí)驗(yàn)結(jié)果都證明，改進(jìn)后的人工蜂群算法在解決信道分配問題上具有優(yōu)越性和可行性。

7 結(jié)束語

本文針對人工蜂群算法鄰域搜索步長的隨機(jī)性、算法的收斂率和收斂速度的問題進(jìn)行了改進(jìn)，在信道分配數(shù)學(xué)模型的基礎(chǔ)之上將改進(jìn)蜂群算法用于解決固定信道分配問題。仿真結(jié)果證明：改進(jìn)人工蜂算法在解決信道分配問題上有較好的尋優(yōu)能力，在收斂率和收斂速度上優(yōu)于微正則退火算法和普通人工蜂群算法。

[1]Duque-Anton M，Kunz D，Ruber B，et al.Channel assignment for cellular radio using simulated annealing[J].IEEE Transactions on Vehicular Technology，1993，42（1）：14-21.

[2]羅文堅(jiān)，曹先彬，王煦法.用一種免疫遺傳算法求解頻率分配問題[J].電子學(xué)報，2003，31（6）：915-917.

[3]朱曉錦，陳艷春，邵勇，等.面向信道分配的分段退火混沌神經(jīng)網(wǎng)絡(luò)模型[J].通信學(xué)報，2008，29（5）：122-127.

[4]徐俊杰，忻展紅.基于微正則退火的頻率分配方法[J].南京郵電大學(xué)學(xué)報，2007，30（2）：67-70.

[5]Karaboga D.An idea based on honey bee swarm for numerical optimization，Technical Report-TR06[R].Kayseri，Turkey：Erciyes University，2005.

[6]Basturk B，Karaboga D.An Artificial Bee Colony（ABC）algorithm fornumericfunction optimization[C]//ProcofIEEE Swarm Intelligence Symposium，2006.

[7]丁海軍，馮慶嫻.基于boltzmann選擇策略的人工蜂群算法[J].計算機(jī)工程與應(yīng)用，2009，45（31）：53-55.

[8]胡中華，趙敏.基于人工蜂群算法的TSP仿真[J].北京理工大學(xué)學(xué)報，2009，29（11）：978-982.

[9]羅鈞，樊鵬程.基于遺傳交叉因子的改進(jìn)蜂群優(yōu)化算法[J].計算機(jī)應(yīng)用研究，2009，26（10）：3716-3717.

[10]Mezura-Montes E，Velez-Koeppel R E.Elitist artificial bee colony forconstrained real-parameteroptimization[C]//Proc of IEEE Evolutionary Computation（CEC），Barcelona，2010：1-8.

[11]Aardal K I，Hoesel S P M V，Koster A M C A，et al.Models and solution for frequency assignment problems[M].Berlin：Springe-Verlag，2001.

[12]Karaboga D，Basturk B.On the performance of Artificial Bee Colony（ABC）algorithm[J].Applied Soft Computing，2008，8：687-697.

[13]Karaboga N.A new design method based on artificial bee colony algorithm fordigitalIIR filters[J].Journalofthe Franklin Institute，2009，346（4）：328-348.

[14]李端明，程八一.基于人工蜂群算法求解不同尺寸工件單機(jī)批調(diào)度問題[J].四川大學(xué)學(xué)報：自然科學(xué)版，2009，46（3）：657-662.

[15]池元成，朱浩，方杰，等.改進(jìn)粒子群優(yōu)化算法在亞軌道飛行器固液混合發(fā)動機(jī)設(shè)計中的應(yīng)用[J].航空動力學(xué)報，2011，26 （9）：1-6.

[16]Seyed A G S，Hamidreza A.A hybrid method for channel assignment problems in cellular radio networks[C]//Proceeding of IEEE WCNC，USA，2006.

[17]池越，趙東明，夏克文，等.基于QPSO算法的信道分配方法[J].通信技術(shù)，2009，42（2）：204-209.

1.Institute of Information Science and Engineering,Xinjiang University,Urumqi 830046,China

2.Xinjiang Mobile Communication Company,Urumqi 830063,China

3.Xinjiang Institute of Electrical and Mechanical Technology,Urumqi 830011,China

The frequency resources of mobile communication network are limited,in order to improve wireless resource utilization,the improved artificial bee colony algorithm is to solve the wireless channel allocation problem.The proposed algorithm with gradually reduced dynamic step balances local and global search capability.The introduction of the single-individual selective mutation increases population diversity and the convergence speed.Simulation results show that the improved algorithm can be better to solve the wireless channel allocation,improve the convergence rate and convergence speed of algorithm.

channel assignment;artificial bee algorithm;selective mutation;search step

A

TN91

10.3778/j.issn.1002-8331.1108-0257

LIU Junxia,JIA Zhenhong,QIN Xizhong,et al.Applications in channel assignment based on improved artificial bee colony algorithm.Computer Engineering and Applications,2013,49（7）：119-122.

中國移動新疆分公司研究發(fā)展基金（No.xjm2010-1）。

劉俊霞（1980—），女，講師，主要研究方向：信號與信息處理；賈振紅，男，教授，博士生導(dǎo)師，研究方向：信號與信息處理；覃錫忠，副教授；常春，高級工程師；王浩，高級工程師。E-mail：ljxljx@sina.cn

2011-08-31

2011-11-22

1002-8331（2013）07-0119-04

CNKI出版日期：2011-12-09 http://www.cnki.net/kcms/detail/11.2127.TP.20111209.1001.032.html