劉俊霞

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

SM-DPSO算法在頻率分配問題上的應(yīng)用

劉俊霞

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

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

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

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

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

針對上述問題，由于粒子群算法是基于鳥群智能搜索行為的優(yōu)化算法，它具有算法簡單、易實(shí)現(xiàn)、收斂速度快、適應(yīng)性強(qiáng)等特點(diǎn)[5-8]，將粒子群算法進(jìn)行改進(jìn)并用于信道分配技術(shù)，經(jīng)仿真證明了改進(jìn)算法的優(yōu)越性。

1 頻率分配數(shù)學(xué)模型

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

其中fik為給第i個小區(qū)的第k個位置分配的頻點(diǎn)，fik取值是正整數(shù)，fjl同理，是給第j個小區(qū)的第l個位置分配的頻點(diǎn)。分配的頻點(diǎn)之間的距離應(yīng)滿足（2）式，否則認(rèn)為產(chǎn)生了干擾。

其中1≤i，j≤N，1≤k，l≤ri。可以用的頻點(diǎn)集合{1，2，...，fmum}，fmum=max{fik}。

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

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

2.1 粒子群算法

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

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

2.2 雙粒子群

在文獻(xiàn)[[10-11]的研究基礎(chǔ)上，將粒子群劃分為兩個數(shù)量相等的子群N1、N2，兩個子群采用不同的尋優(yōu)進(jìn)化策略，使粒子跳出局部最優(yōu)解。

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

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

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

比較Pg1和Pg2的適應(yīng)值大小，選擇適應(yīng)值較小的做為全局最優(yōu)解Pg。

2.3 選擇性變異

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

選擇性變異是一種單個個體進(jìn)化的方法，在信道分配問題中首先對待變異的個體計算適應(yīng)度值M（F），即計算公式（1）的值。若M（F）〉0，則遍歷該個體解F中的每一個頻點(diǎn)fij，1≤i≤N，1≤j≤ri，考察該頻點(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和pCell的計算公式為[15-14]：

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

3 SM-DPSO信道分配算法

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

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

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

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

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

步驟4：對所有粒子按照2.3節(jié)方法進(jìn)行變異操作。

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

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

4 仿真試驗(yàn)

算法用MATLAB進(jìn)行仿真，信道分配方案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[5]。

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

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

表1 仿真結(jié)果比較

5 結(jié)束語

本文對粒子群算法進(jìn)行了改進(jìn)，并用于解決信道分配問題，對benchmark問題進(jìn)行仿真，仿真試驗(yàn)結(jié)果表明提出的改進(jìn)雙粒子群優(yōu)化算法在信道分配問題上具有迭代次數(shù)少、收斂率高的優(yōu)點(diǎn)，能更好地解決信道分配問題。

[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]馮志強(qiáng)，許國軍，鄧?yán)冢?基于改進(jìn)并行遺傳算法的蜂窩網(wǎng)絡(luò)信道分配[J].計算機(jī)工程與應(yīng)用，2014，50（3）:89-92

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

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

[5]劉俊霞，賈振紅，覃錫忠，等.改進(jìn)人工蜂群算法在信道分配上的應(yīng)用[J].計算機(jī)工程與應(yīng)用，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]聶立新，張?zhí)靷b，郭立新．并行定向擾動的混合粒子群優(yōu)化算法[J].計算機(jī)應(yīng)用研究，2013，30（6）:1633-1635．

[8]仲昭明，李向陽，逄珊.混合擇優(yōu)的多目標(biāo)免疫粒子群優(yōu)化算法[J].計算機(jī)工程與應(yīng)用，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]李愛國.多粒子群協(xié)同優(yōu)化算法[J].復(fù)旦學(xué)報：自然科學(xué)版，2004，43（5）:923-925.

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

[12]韓毅，蔡建湖，周根貴，等.隨機(jī)蛙跳算法的研究進(jìn)展[J].計算機(jī)科學(xué)，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]李滿林，王玉娜，杜雷，等.蜂窩系統(tǒng)中一種固定信道分配方法的研究[J].小型微型計算機(jī)系統(tǒng)，2004，25（8）:1420-1421.

[16]仲向遠(yuǎn)，金敏，仲向前，等.基于自適應(yīng)遺傳算法的蜂窩網(wǎng)絡(luò)信道分配[J].計算 機(jī)工程，2010，36（17）:189-191.

【相關(guān)參考文獻(xiàn)鏈接】

李俊萍，蓋國權(quán).基于自適應(yīng)遺傳算法的電力變壓器優(yōu)化設(shè)計[J].2015，23（8）：129-131.

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

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

潘廣全，王偉.基于遺傳算法的云臺控制系統(tǒng)的參數(shù)優(yōu)化[J].2015，23（14）：39-41.

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

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

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

張茜，田祥龍.基于ANN交互式遺傳算法的智能手機(jī)外觀概念設(shè)計研究[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

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

劉俊霞（1980—），女，新疆博州人，碩士，講師。研究方向：移動通信網(wǎng)絡(luò)規(guī)劃與建模。