基于改進蜂群算法的移動通信信道分配方法

1基于改進的人工蜂群算法在移動通信系統中，移動用戶的快速增加與有限頻率資源之間存在矛盾。為了提高有限頻率資源的利用率，采用頻道分布技術是一種明顯的方法。通常是根據干擾約束條件以及信道分配問題模型,按照不同的算法求解信道的最佳分配方案。在早期,信道分配問題的研究大多是以圖形理論或啟發式方法為基礎的,近年來,主要用神經網絡、遺傳算法、模擬退火算法和微正則退火算法來處理信道分配問題。但在搜索最優解過程中,它們依然存在收斂時間較長,容易陷入或難以擺脫局部最優解等缺點。為了解決上述缺點,利用固定信道分配的數學模型,在普通人工蜂群算法的基礎上,提出了一種用改進的人工蜂群算法來求解最佳信道分配的方案。人工蜂群算法是一類新興的基于蜜蜂群智能搜索行為的優化算法,它與其他智能算法一樣具有優良的優化性能。由于智能算法自身還存在一定缺陷,許多研究者提出了一些改進措施并應用于不同的領域。本文針對人工蜂群算法收斂速度慢,易陷入局部最優等缺點,將人工蜂群算法進行改進,并用于解決固定信道分配問題;仿真證明了該算法的優越性。2數值分配算法信道分配問題即頻率分配問題,其基本模型是可行性頻率分配,目標是在不違反干擾約束的前提下,所有小區都能分配到所需數量的頻點。通常只考慮三種主要干擾約束條件:同頻干擾(CCC)、鄰頻干擾(ACC)、共地干擾(CSC)。通常用一個N′N維的兼容矩陣來表示以上主要的干擾約束條件(N為蜂窩系統的小區數),矩陣C中對角元素Cij表示分配給小區i的信道之間的最小間隔,矩陣中的非對角元素Cij(i1j)表示分配給小區i中的信道與小區j中的信道的最小間隔。每個小區頻率需求數用矩陣來表示,其中矩陣R中的元素ri表示第i個小區的頻點需求數,可用的頻點集合為,其中FNum=max{fij},設fik為給第i個小區的第k個位置分配的頻點,fik取值為正整數,fjl同理,它們之間應滿足,目標函數的適應度S(F)定義為信道分配方案F違反約束條件的總數量,Fikjl描述fik與fjl是否滿足約束條件Cij,數學模型如下:即在給定的C、R和可用頻點集合FN,找到使目標函數S(F)值最小即為0的信道分配方案F。信道分配方案F采用最小間隔實數編碼方式,F是一個N′rmax的矩陣,即:式中rmax是需求向量R的最大值,,表示將頻點χ分配給第i個小區的第j個位置,當時,fij=0。3基于概率pi的新蜜源搜索算法在人工蜂群算法中蜂群主要有引領峰、跟隨蜂和偵查蜂,一個蜜源位置(θi)與一個引領蜂(ei)相對應,ei先出去尋找蜜源位置θi,跟隨蜂(oi)在舞蹈區等待ei帶回蜜源的相關信息,等到ei回到舞蹈區后,oi根據ei的舞蹈得知θi信息,采用公式(4)以概率Pi選擇一個θi,并在其鄰域內采用公式(5)搜索新蜜源,比較蜜源θi和在其領域內搜索的新蜜源,選擇較好的蜜源采蜜。在迭代過程中,若某個oi在設定的搜索次數內沒有獲得更好的蜜源,ei便放棄該θi,同時成為偵查蜂。并隨機搜索新蜜源。令蜂群數量為M,第t次迭代之后,現有的蜜源位置集合為M,ei在該次搜索之后,獲得的蜜源收益度為H(θi(t)),oi選擇θi(t)的概率為:oi以概率Pi選擇θi(t)之后,在其鄰域內選擇一個新的蜜源(θi(t+1))進行訪問,選擇的方法為:其中ψi為隨機產生的步長。如果H(θi(t+1))>H(θi(t)),則用θi(t+1)更蜜源θi(t),否則θi(t)不變。若在連續的Limt次迭代之后,均不能發現更優的蜜源,則ei放棄該θi,同時成為偵查蜂隨機搜索新蜜源。4改進的手動集群算法4.1迭代次數優化人工蜂群算法中,跟隨蜂在選中的蜜源鄰域范圍內按式(5)搜索新蜜源,搜索步長具有隨機性,算法尋優速度相對較慢,易陷入局部最優或易錯過全局最優解。本文根據文獻的研究成果,在實驗數據的基礎上將隨機產生的步長改為隨迭代次數動態變化的步長,不僅提高了算法的搜索精度,還能較好地平衡局部與全局搜索能力,如式(6)所示:其中,tmax為最大迭代次數;θmax(t)為第t次迭代的最優蜜源位置;0.5(1-t/tmax)是鄰域搜索步長的動態權值,它隨迭代次數的增加線性減小。該動態權值在算法初期有較大的值,使跟隨蜂有較強的全局搜索能力,加快算法收斂速度;在算法后期隨迭代次數的增加有較小的值,使跟隨蜂有較強的開發能力并增強了算法的搜索精度,從而使蜂群在全局搜索和局部搜索之間達到動態平衡。4.2自由或c為了提高種群的多樣性和算法的收斂速度,引入了選擇性變異技術。選擇性變異技術是一種單個體進化的方法,在信道分配問題中首先對待變異的個體計算適應度值S(F),即公式(1)的值。若S(F)>0,則遍歷該個體解F中的每一個頻點fij,用公式(2)進行分析,考察該頻點fij是否對其他小區產生干擾。如果不產生干擾,則什么也不做;如果產生干擾,則需要對該頻點fij進行變異替換。替換頻點fij的頻點必須滿足第i個小區的共地約束(CSC),即Cii,同時還必須與前PCell個具有較大分配難度的小區滿足兼容矩陣所要求的鄰頻約束(ACC)和同頻約束(CCC)。分配難度deg計算公式為:5頻域分配算法和步驟5.1基于2.2目標函數的多通道分配算法一個蜜源位置θi與一個信道分配方案Fi相對應,蜜源收益度H(θi)代表該蜜源相對應的信道分配方案Fi的質量,H(θi)越大相應的Fi違反約束條件的頻點數越少,即解越接近最優解。具體關系見公式(8)。最大收益度與最佳信道分配方案相對應,搜索最佳蜜源的快慢代表尋找最佳信道分配方案的速度,即算法收斂速度的快慢。公式(8)中S(Fi)見公式(1)。在信道分配模型中目標是找到最小值,即找到使目標函數S(F)=0的信道分配方案F,該信道分配方案中沒有違反干擾約束條件的頻點;在改進蜂群算法中目標是求最大值,即蜜源的收益度H(θi)的最大值。信道分配目標函數S(F)的值越小,蜜源收益度值H(θi)越大,當S(F)為最小值等于0時,蜜源收益度H(θi)達到最大值。因此在改進蜂群算法中,求解最大收益度和信道分配方案中的尋找S(F)=0的最佳信道分配方案是相對應的。5.2采蜜、分級回歸步驟1確定蜂群規模M,最大迭代次數tmax,可用頻點總數FNum、PCell、Limt的值,引領蜂個數與跟隨蜂個數相等,等于M。步驟2初始化M個可行解,計算初始化后的各個可行解的適應度S(F)和各個可行解所對應的蜜源收益度H(θi),并記錄全局最優解θmaxx(收益度H(θi)最大或適應度S(F)最小)。若初始解中有S(F)=0的解,結束算法并輸出S(F)=0的信道分配方案,否則執行下一步。步驟3模擬蜂群行為,oi根據ei的舞蹈得知θi信息,用公式(4)以概率Pi選擇一個θi(t),并在其鄰域內用公式(6)搜索新蜜源θi(t+1)。步驟4比較蜜源θi(t)和θi(t+1)收益度,選擇蜜源收益度大的進行采蜜。步驟5對步驟4選中的蜜源進行3.2節的選擇性變異。計算變異后的蜜源的收益,若此次變異產生的蜜源收益度大于變異之前的蜜源收益度,則接受此次變異,否則沿用變異之前選中的蜜源。步驟6若某些引領蜂對應的蜜源(解)收益度在Limt次循環后都沒有改進,則放棄該蜜源,同時引領蜂轉變為偵察蜂隨機搜索一個新蜜源取代該蜜源。計算本次迭代全局最優解θmax,與上一次迭代的全局最優解比較,選擇收益度大的作為本次迭代的全局最優解。步驟7計算所有蜜源的收益度H(θi)和蜜源相對應可行解的適應度S(F),若有S(F)=0,即蜜源收益度達到最大值,則結束運算并輸出S(F)=0的信道分配方案;否則跳轉到步驟3進入下一次迭代。步驟8若達到最大迭代次數都沒有找到使S(F)=0的最佳信道分配方案,則結束運算,并認為算法不收斂。6仿真結果與分析算法用MATLAB7.0進行仿真,頻率分配方案采用實數最小間隔編碼方式,種群個數M=35,引領蜂個數=跟隨蜂個數=M,算法循環總代數tmax=200,Limt=6,PCell=5;對文獻的21小區系統進行頻率分配,可用頻率總數FNum分別取55、65、70、80、90,每種可用頻點數各運行50次。圖1為本文算法在采用可用頻點數為55的收斂代數仿真圖,圖1中橫坐標t為算法迭代次數,縱坐標為適應度函數S(F)的最小值,即信道分配方案F違反約束條件的總數量的最小值。表1為本文算法與文獻算法的比較結果;表2為人工蜂群算法與本文算法比較結果。由圖1可以看出,在可用頻點數不充足為55的情況下,算法也有著較快的收斂速度,僅用17次迭代即可收斂。從表1的實驗結果中看出,當可用頻點數設為70時,文獻只有90%的收斂率,而本文算法能達到100%的收斂率,且平均收斂代數在3.8代;同時應用到65和55個可用頻點數中,文獻不收斂,而本文算法的收斂率仍能達到100%,且平均收斂代數也只為5.4代和18代,可用頻點為55的仿真結果如圖1所示。這表明改進后的人工蜂群算法在頻率分配上的效果優于傳統的微正則退火算法。從表2的結果中可用看出,在頻點數充足且相同的情況下,改進的人工蜂群算法的收斂代數在各可用頻點的情況下均小于基本人工蜂群算的收斂代數,并且當頻點數為65和55時,基本人工蜂群算法不收斂,而本文算法的收斂率為100%。用本文算法去處理文獻的信道分配問題時,僅用1次迭