SM-DPSO算法在頻率分配問題上的應用

劉俊霞

（新疆工程學院 電氣與信息工程系，新疆 烏魯木齊 830023）

SM-DPSO算法在頻率分配問題上的應用

劉俊霞

（新疆工程學院 電氣與信息工程系，新疆 烏魯木齊 830023）

針對移動通信頻率分配過程中已有算法存在收斂率低和算法收斂時間長的問題，提出了基于選擇性變異（SMDPSO）的雙粒子群優化算法，并用于解決頻率分配問題。提出算法將粒子群劃分為兩個子群采用不同的更新策略，使算法易跳出局部最優解；對單個粒子進行選擇性變異，提高了種群多樣性的同時加快了算法的收斂速度。仿真結果表明：SM-DPSO能較好的解決移動通信的頻率分配問題，提高了算法的收斂率和收斂速度。

頻率分配；雙粒子群；選擇性變異

頻譜資源是寶貴的不可再生資源，隨著移動數據業務尤其是寬帶化業務需求的不斷增長，頻譜資源緊缺和移動用戶需求迅速增長的矛盾也日益凸顯。提高的頻率資源利用率，是解決無線頻譜供需矛盾的重要方法之一，優化頻譜分配技術是有效的方法之一。頻譜分配即信道分配，分配方法通常是建立標準的信道分配問題數學模型，按照不同的優化算法求解信道分配數學模型的最佳分配方案。

模擬退火算法（SA）、遺傳算法（GA）、微正則退火算、人工蜂群算法等[1-5]已經成功地用于解決信道分配問題，但在求解最優信道分配方案的過程中，依然存在著收斂時間較長、容易陷入或難以擺脫局部最優解等問題。

針對上述問題，由于粒子群算法是基于鳥群智能搜索行為的優化算法，它具有算法簡單、易實現、收斂速度快、適應性強等特點[5-8]，將粒子群算法進行改進并用于信道分配技術，經仿真證明了改進算法的優越性。

1 頻率分配數學模型

頻率分配問題的數學模型通常是考慮同頻干擾（CCC），鄰頻干擾（ACC）和同小區干擾（CSC）這3種主要的干擾問題。用矩陣CN×N=Cij（i，j=1，2，...，N）的矩陣表示干擾矩陣，N是蜂窩系統包含的小區數。矩陣CN×N的對角元素Cii代表同一個小區的信道之間的最小間隔，非對角元素Cij代表兩個不同小區的信道之間的最小間隔。N個小區的頻點需求數用矩陣R表示，R=[r1，r2，...，ri，rN]，ri是第i個小區所需要分配的頻譜個數。目標函數M（F）定義為式 （1）：

其中fik為給第i個小區的第k個位置分配的頻點，fik取值是正整數，fjl同理，是給第j個小區的第l個位置分配的頻點。分配的頻點之間的距離應滿足（2）式，否則認為產生了干擾。

其中1≤i，j≤N，1≤k，l≤ri?？梢杂玫念l點集合{1，2，...，fmum}，fmum=max{fik}。

在已知每個小區的頻譜需求R、干擾矩陣CN*N、可用頻點集合的情況下，求解目標函最小值M（F）=0，即無違反干擾約束條件的頻譜分配方案F[4-5，9]。

2 選擇性變異的雙粒子群算法

2.1 粒子群算法

基本粒子群算法的數學模型描述如下:在d維搜索空間，有L個粒子，第i個粒子的位置和速度分別定義為xi=（xi1，xi2，…，xiL）和vi=（vi1，vi2，…，viL），粒子i目前尋找的最優解是Pi（i=1，2，，...，L），全體粒子尋找到的全局最優解為Pg，每個粒子更新自己的位置和速度，依照式（3），式（4）：

其中w，c1，c2是常數，r1，r2是[0，1]上的隨機數，-vmax≤vij（t）≤vmax，vmax是常數，根據具體問題設定。

2.2 雙粒子群

在文獻[[10-11]的研究基礎上，將粒子群劃分為兩個數量相等的子群N1、N2，兩個子群采用不同的尋優進化策略，使粒子跳出局部最優解。

N1子群的粒子采用式（3），式（4）更新自己的速度和位置，并記錄子群N1的局部最優解Pg1。

N2子群的粒子采用更新局部最差解來更新子群，具體方法：在N2中隨機概率選取nn個粒子，Pj代表N2中第j個粒子被選中的隨機選取概率，如公式（5）所示[12-13]：

然后在這nn個粒子中，根據適應度計算局部最優解Pmg、子群中的局部最差解w，在信道分配方案中，解矩陣（F）的每一行代表一個小區，因此可以在局部最優個體Pmg中隨機選取i（i是一個隨機數，1≤i≤N）個小區，去替換局部最差個體w中相對應的這個i小區，如果所得新粒子個體w的適應度大于個體的適應度，則放棄使用Pmg更新w，此時計算出子群N2的最優個體Pg2，在Pg2中隨機選取i（i是一個隨機數，1≤i≤N）個小區，去替換局部最差個體w中相對應的這i個小區，無論所得新粒子個體w的適應度是否大于個體的適應度，都接受此次更新，并記錄更新后的子群N2的局部最優解Pg2。

比較Pg1和Pg2的適應值大小，選擇適應值較小的做為全局最優解Pg。

2.3 選擇性變異

為了提高種群的多樣性和算法的收斂速度，在2.2節的雙粒子群算法中引入了選擇性變異的方法，把這種基于選擇性變異的雙粒子群算法定義為SM-DPSO。

選擇性變異是一種單個個體進化的方法，在信道分配問題中首先對待變異的個體計算適應度值M（F），即計算公式（1）的值。若M（F）〉0，則遍歷該個體解F中的每一個頻點fij，1≤i≤N，1≤j≤ri，考察該頻點fij是否對其他小區產生干擾，如果不產生干擾，則什么也不做；如果產生干擾，則需要對該頻點fij進行變異替換，替換頻點fij的頻點必須滿足第個i小區的共地約束（CSC），即Cii，同時還必須與前PCell個具有較大分配難度的小區滿足兼容矩陣所要求的鄰頻約束（ACC）和同頻約束（CCC）。分配難度deg和pCell的計算公式為[15-14]：

PCell在這里是一個由適應度函數動態控制的變量，式中[]表示取整，N表示小區總數，μ∈（0，1），ε∈（0，1），λ∈（0，1），MinV是本次迭代的最小適應度值，Ω表示當算法循環運行到m的倍數代時發現適應度函數值連續l代沒有發生變化，說明算法陷入了一個局部最小，需要減小替換頻點fij所滿足的鄰頻約束（ACC）和同頻約束（CCC）個數，以跳出局部最小。

3 SM-DPSO信道分配算法

粒子的位置xi代表可行頻率分配方案Fi，粒子適應度M（F）的大小代表可行頻率分配方案Fi的質量，最小適應度與最佳信道分配方案相對應，搜索最好粒子的快慢代表尋找最佳信道分配方案的速度，即算法收斂速度。

SM-DPSO信道分配算法步驟如下：

步驟1：確定粒子群規模M、子群 N1、N2，最大迭代次數tmax、vmax可用頻點總數fnum、m、l、μ、ε、λ、nn、ω的值。

步驟2：初始化M個粒子對應的可行解，初始化t=0，計算初始化后的各個可行解的適應度M（F）并記錄最小適應度的值。若M（F）=0，結束算法并輸出結果，否則執行下一步。

步驟3：兩個子群N1、N2按照2.2節方法更新粒子。

步驟4：對所有粒子按照2.3節方法進行變異操作。

步驟5：計算所有粒子的適應度M（F），并記錄最小適應度值。若最小適應度值為零，則結束算法并輸出結果，否則將最小適應度值與上次迭代最小適應度值比較選擇較小的值作為本次迭代最優解，。

步驟6：判斷是否t=tmax，若達到最大迭代次數都沒有找到使M（F）=0的最佳信道分配方案，則結束運算，并認為算法不收斂；否則t=t+1并轉至步驟3。

4 仿真試驗

算法用MATLAB進行仿真，信道分配方案F采用最小間隔實數編碼方式，F是一個N×rmax的矩陣，即：

式中rmax是需求向量R的最大值，fij=χ，（1≤χ≤FNum）表示將頻點χ分配給第i個小區的第j個位置，當ri＜j＜rmax時，fij=0[5]。

參數設置：種群個數M=60，N1=20，N2=20算法循環總代數tmax=200，m=3、l=6、μ=06、ε=0.8、λ=0.75、nn=5、vmax=5，ω=0.4。本文對一組benchmark問題各做50次仿真，benchmark問題選自文獻[1]。求取了平均收斂代數和收斂率，仿真結果及比較結果如表1所示。

文獻[15]采用的是遺傳算法與最小化費用函數相結合的方式，而文獻[16]則采用了一種具有自適應交叉概率的遺傳算法與最小化費用函數相結合方式。從表1中可以看到本文算法在解決問題2、4、6時的收斂代數與文獻[16]相比，還具有一定的差距，但是在其它剩余的問題當中，本文算法不但保證了100%的收斂率，而且平均收斂代數也要遠少于文獻[16]，本文算法在收斂率和收斂代數上與文獻[15]相比，具有明顯優勢。

表1 仿真結果比較

5 結束語

本文對粒子群算法進行了改進，并用于解決信道分配問題，對benchmark問題進行仿真，仿真試驗結果表明提出的改進雙粒子群優化算法在信道分配問題上具有迭代次數少、收斂率高的優點，能更好地解決信道分配問題。

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

[2]馮志強，許國軍，鄧磊，等.基于改進并行遺傳算法的蜂窩網絡信道分配[J].計算機工程與應用，2014，50（3）:89-92

[3]朱曉錦，陳艷春，邵勇，等．面向信道分配的分段退火混沌神經網絡模型[J]．通信學報，2008，29（5）:122-127．

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

[5]劉俊霞，賈振紅，覃錫忠，等.改進人工蜂群算法在信道分配上的應用[J].計算機工程與應用，2013，49（7）:119-122.

[6]Kennedy J，Eberhart R C.Particle swarm optimization[C]// Proceedings of the IEEE International Conference on Neural Networks，1995:1942-1948．

[7]聶立新，張天俠，郭立新．并行定向擾動的混合粒子群優化算法[J].計算機應用研究，2013，30（6）:1633-1635．

[8]仲昭明，李向陽，逄珊.混合擇優的多目標免疫粒子群優化算法[J].計算機工程與應用，2013，49（13）:43-47．

[9]Aardal KI，Hoesel S PMV，koster AMCA，et al.models and solution for Frequency assignment problems[R].Berlin:springe-Verlag，2001.

[10]李愛國.多粒子群協同優化算法[J].復旦學報：自然科學版，2004，43（5）:923-925.

[11]彭鑫，馬林華，王俊攀，等.雙種群變異粒子群算法[J].計算機工程與應用，2010，46（18）:35-37.

[12]韓毅，蔡建湖，周根貴，等.隨機蛙跳算法的研究進展[J].計算機科學，2010，37（7）:16-18.

[13]Eusuff M M，Lan sey K E.Optimization of water distribution network design using the shuffled frog leaping algorithm[J].Journal of Water Resources Planning and Management，2003，129（3）:210-225.

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

[15]李滿林，王玉娜，杜雷，等.蜂窩系統中一種固定信道分配方法的研究[J].小型微型計算機系統，2004，25（8）:1420-1421.

[16]仲向遠，金敏，仲向前，等.基于自適應遺傳算法的蜂窩網絡信道分配[J].計算 機工程，2010，36（17）:189-191.

【相關參考文獻鏈接】

李俊萍，蓋國權.基于自適應遺傳算法的電力變壓器優化設計[J].2015，23（8）：129-131.

柴宏建，高尚策.基于聚類混合遺傳算法的LRP問題研究[J].2015，23（9）：1-4.

郭海雙，梁佳雯，張劭昀.MATLAB遺傳算法工具箱GADS優化及應用[J].2015，23（10）：27-29.

潘廣全，王偉.基于遺傳算法的云臺控制系統的參數優化[J].2015，23（14）：39-41.

李紅磊，劉家學.基于改進遺傳算法的模擬電路參數自動化設計[J].2015，23（17）：147-150.

王莉.基于遺傳算法的高校在線考試系統研究[J].2015，23（24）：29-31.

侯翔，劉篤晉，彭小利.基于遺傳算法改進的洪水預報模型[J].2014，22（2）：10-12，15.

張茜，田祥龍.基于ANN交互式遺傳算法的智能手機外觀概念設計研究[J].2014，22（6）：37-39.

The applications in channel assignment based on SM-DPSO algorithm

LIU Jun-xia
（Department of Electrical and Information Engineering，Xinjiang Institute of Engineering，Urumqi 830023，China）

For the problem of algorithm convergence rate low and algorithm convergence time long in mobile communication frequency spectrum allocation process，we presented double particle swarm algorithm based on selectivity mutation（SMDPSO），and it is used to resolve frequency spectrum allocation problem.Proposed algorithm divided the particle swarm into two subgroups，the two subgroups is updated by different update strategies，the algorithm is easy to jump out of local optima solution；The single particle is introduced selectivity mutation，it increased population diversity and the convergence speed.Simulation results shown that:the SM-DPSO algorithm can be better to solve the wireless channel allocation problem，it improved the convergence rate and convergence speed of algorithm.

frequency spectrum allocation；double particle group；selective mutation

TN91

A

1674－6236（2016）15-0109-03

2016-01-25 稿件編號：201601231

新疆維吾爾自治區高?？蒲杏媱澢嗄杲處熆蒲袉踊痦椖浚╔JEDU2014S074）

劉俊霞（1980—），女，新疆博州人，碩士，講師。研究方向：移動通信網絡規劃與建模。