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

劉俊霞

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

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

劉俊霞

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

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

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

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

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

針對(duì)上述問(wèn)題，由于粒子群算法是基于鳥(niǎo)群智能搜索行為的優(yōu)化算法，它具有算法簡(jiǎn)單、易實(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é)模型

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

其中fik為給第i個(gè)小區(qū)的第k個(gè)位置分配的頻點(diǎn)，fik取值是正整數(shù)，fjl同理，是給第j個(gè)小區(qū)的第l個(gè)位置分配的頻點(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}。

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

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

2.1 粒子群算法

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

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

2.2 雙粒子群

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

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

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

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

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

2.3 選擇性變異

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

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

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

3 SM-DPSO信道分配算法

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

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

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

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

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

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

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

步驟6：判斷是否t=tmax，若達(dá)到最大迭代次數(shù)都沒(méi)有找到使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)是一個(gè)N×rmax的矩陣，即：

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

參數(shù)設(shè)置：種群個(gè)數(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。本文對(duì)一組benchmark問(wèn)題各做50次仿真，benchmark問(wèn)題選自文獻(xiàn)[1]。求取了平均收斂代數(shù)和收斂率，仿真結(jié)果及比較結(jié)果如表1所示。

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

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

5 結(jié)束語(yǔ)

本文對(duì)粒子群算法進(jìn)行了改進(jìn)，并用于解決信道分配問(wèn)題，對(duì)benchmark問(wèn)題進(jìn)行仿真，仿真試驗(yàn)結(jié)果表明提出的改進(jìn)雙粒子群優(yōu)化算法在信道分配問(wèn)題上具有迭代次數(shù)少、收斂率高的優(yōu)點(diǎn)，能更好地解決信道分配問(wè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)，許國(guó)軍，鄧?yán)冢?基于改進(jìn)并行遺傳算法的蜂窩網(wǎng)絡(luò)信道分配[J].計(jì)算機(jī)工程與應(yīng)用，2014，50（3）:89-92

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

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

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

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

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

[12]韓毅，蔡建湖，周根貴，等.隨機(jī)蛙跳算法的研究進(jìn)展[J].計(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ì)算機(jī)系統(tǒng)，2004，25（8）:1420-1421.

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

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

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

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

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

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

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

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

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

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

新疆維吾爾自治區(qū)高校科研計(jì)劃青年教師科研啟動(dòng)基金項(xiàng)目（XJEDU2014S074）

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