劉計(jì)永, 張　蕾

(1.中國移動 河北分公司，河北 石家莊 050000；2.北京郵電大學(xué) 信息與通信工程學(xué)院，北京 100876)

?

遺傳算法在UMTS自動小區(qū)規(guī)劃中的應(yīng)用

劉計(jì)永1, 張蕾2

(1.中國移動 河北分公司，河北 石家莊 050000；2.北京郵電大學(xué) 信息與通信工程學(xué)院，北京 100876)

針對需要高維優(yōu)化的通用移動通信系統(tǒng)(UMTS)無線網(wǎng)絡(luò)自動小區(qū)規(guī)劃(ACP)問題，應(yīng)用了改進(jìn)的遺傳算法。該算法用特殊的正交方法產(chǎn)生初始解，采用精英選擇策略，并自適應(yīng)地改變交叉概率和變異概率的值。仿真結(jié)果顯示:相對于其他遺傳算法，該算法的性能有較大的提升，可以更加有效地找到高維UMTS-ACP問題的優(yōu)化解。

無線網(wǎng)絡(luò)優(yōu)化； 通用移動通信系統(tǒng)； 遺傳算法

0　引　言

通用移動通信系統(tǒng)(universal mobile telecommunications system,UMTS)無線網(wǎng)絡(luò)中由于基站天線參數(shù)配置不合理容易使網(wǎng)絡(luò)出現(xiàn)諸如弱覆蓋、導(dǎo)頻污染等覆蓋質(zhì)量問題，使某些區(qū)域的信號質(zhì)量不能滿足用戶的服務(wù)質(zhì)量(QoS)需求，因此，進(jìn)行無線網(wǎng)絡(luò)優(yōu)化是一項(xiàng)重要的工作。但是，隨著無線網(wǎng)絡(luò)規(guī)模的日益龐大和維護(hù)工作的日益復(fù)雜，網(wǎng)絡(luò)維護(hù)優(yōu)化的難度在不斷加大，選取一種新的適當(dāng)?shù)姆椒▉斫鉀Q網(wǎng)絡(luò)優(yōu)化的問題是很有必要的[1]。近幾年，利用自動小區(qū)規(guī)劃(automatic cell planning,ACP)進(jìn)行無線網(wǎng)絡(luò)的優(yōu)化是一項(xiàng)研究熱點(diǎn)[2,3]，它可以解決最大化網(wǎng)絡(luò)性能問題。

無線網(wǎng)絡(luò)優(yōu)化問題實(shí)質(zhì)上是一個(gè)NP-hard問題，解決這類問題一個(gè)有效的方法就是采用智能算法，目前常用的智能算法有遺傳算法、模擬退火算法、粒子群算法、蟻群算法等[4～6]，其中，遺傳算法的應(yīng)用較為廣泛。但由于標(biāo)準(zhǔn)遺傳算法收斂速度慢，且有易于收斂到局部最優(yōu)解的缺陷[7～9]。文獻(xiàn)[7]提出了一種基于精英選擇的改進(jìn)遺傳算法，精英種群中的最優(yōu)解即為所求問題的解。文獻(xiàn)[8]提出了一種自適應(yīng)遺傳算法，對交叉概率和變異概率給出了改進(jìn)的公式。文獻(xiàn)[9]提出了一種大規(guī)模全局優(yōu)化問題的初始解產(chǎn)生方法，用一種特殊的正交方法產(chǎn)生問題的初始解，使初始解在搜索空間均勻地分布。

本文結(jié)合文獻(xiàn)[7]的精英選擇策略、文獻(xiàn)[8]的自適應(yīng)改變交叉概率和變異概率的算法以及文獻(xiàn)[9]提出的一種特殊的正交方法產(chǎn)生問題的初始解，得到一種改進(jìn)的遺傳算法，本文采用改進(jìn)的遺傳算法來解決高維的UMTS-ACP問題。

1　遺傳算法

標(biāo)準(zhǔn)遺傳算法的運(yùn)算流程如圖1。

圖1　標(biāo)準(zhǔn)遺傳算法流程圖Fig 1　Flow chart of standard genetic algorithm

圖1中,Gen為迭代次數(shù)。

標(biāo)準(zhǔn)遺傳算法在對許多復(fù)雜的問題進(jìn)行優(yōu)化時(shí)，很難收斂到全局最優(yōu)解；經(jīng)過若干次迭代之后，種群相似度提高，這會降低交叉算子的效率，新的優(yōu)質(zhì)個(gè)體的產(chǎn)生效率就會下降。

2　UMTS-ACP問題的算法設(shè)計(jì)方案

UMTS-ACP系統(tǒng)可以通過調(diào)整天線參數(shù)(包括機(jī)械下傾角、電子下傾角、方位角、發(fā)射功率、天線類型)，通過對MR數(shù)據(jù)、工參數(shù)據(jù)等工程參數(shù)進(jìn)行分析，利用改進(jìn)的遺傳算法進(jìn)行優(yōu)化，實(shí)現(xiàn)所選地區(qū)的各項(xiàng)指標(biāo)的優(yōu)化。

具體的優(yōu)化指標(biāo)包括接收信號碼功率(RSCP)、導(dǎo)頻信道信噪比(Ec/Io)，1st-Nth 導(dǎo)頻污染。將RSCP作為優(yōu)化目標(biāo)是為了優(yōu)化接收功率，將Ec/Io作為優(yōu)化目標(biāo)是為了優(yōu)化接收質(zhì)量，將1st-Nth導(dǎo)頻污染作為優(yōu)化目標(biāo)是為了抑制導(dǎo)頻污染和越區(qū)覆蓋。

實(shí)際的UMTS網(wǎng)絡(luò)中，相鄰小區(qū)之間的關(guān)聯(lián)很密切，需要同時(shí)對幾百個(gè)小區(qū)進(jìn)行優(yōu)化。如果每個(gè)小區(qū)有5個(gè)參數(shù)可以調(diào)整，對500個(gè)小區(qū)的這5個(gè)優(yōu)化參數(shù)進(jìn)行優(yōu)化，優(yōu)化問題的維數(shù)將達(dá)到2 500維，這是一個(gè)高維的優(yōu)化問題。

UMTS-ACP問題的目標(biāo)函數(shù)的表示為

f(k→)=∑wRSCP·U(RSCP(k→))+wEcIo·U(EcIo(k→))+

w1st-Nth·U(ΔRSCP1st-Nth(k→))+wLoad·U(ΔLoad(k→))

(1)

式中變量k→是由機(jī)械下傾角、方位角、電子下傾角、天線類型五個(gè)變量組成的向量。U(RSCP(k)),U(EcIo(k)),U(ΔRSCP1st-Nth(k)),U(ΔLoad(k))為各優(yōu)化目標(biāo)的目標(biāo)函數(shù)；wRSCP,wEcIo,w1st-Nth,wLoad是各優(yōu)化目標(biāo)的權(quán)重。

UMTS-ACP問題的約束條件是優(yōu)化成本和負(fù)載均衡等，這里的優(yōu)化成本是指天線的參數(shù)調(diào)整時(shí)所花費(fèi)的人工成本，考慮負(fù)載均衡作為約束條件是為了在優(yōu)化過程中保證小區(qū)之間的負(fù)載均衡。

可以看出，這類優(yōu)化問題就是在滿足優(yōu)化成本和負(fù)載均衡的約束條件下，最大化網(wǎng)絡(luò)性能的問題，這是一個(gè)單目標(biāo)帶約束的高維優(yōu)化問題。

UMTS-ACP問題的優(yōu)化過程就是目標(biāo)函數(shù)的迭代優(yōu)化過程，每次迭代修改變量 ，使目標(biāo)函數(shù)的值不斷優(yōu)化，同時(shí)要滿足約束條件，達(dá)到最大迭代次數(shù)時(shí)，迭代終止。

采用改進(jìn)的遺傳算法此類問題的具體流程如下:

1)首先,產(chǎn)生UMTS-ACP問題的初始解，問題的解就是式(1)中的向量 。算法采用一種特殊的正交方法得到問題的初始解，即將所有變量的定義域分別劃分成N個(gè)子區(qū)間，N為種群中個(gè)體的數(shù)量，每個(gè)初始解的每個(gè)變量逐個(gè)在子區(qū)間內(nèi)隨機(jī)地取值，這樣每個(gè)解所在的子區(qū)間是正交的，使得解在搜索空間分布的更加均勻，加強(qiáng)了種群的多樣性。根據(jù)文獻(xiàn)[9]，對生成的正交解采用相對位學(xué)習(xí)法求解它們的相對位，形成了一組新解，將新舊解的適應(yīng)度值進(jìn)行對比，保留適應(yīng)度值較大的解。這樣不僅使初始解在搜索空間均勻地分布，而且可以選擇較有潛力的區(qū)域進(jìn)行后續(xù)的搜索。

2)復(fù)制種群:對復(fù)制的種群進(jìn)行自適應(yīng)交叉操作，交叉概率的計(jì)算公式為[11]

(2)

式中favg為種群中所有個(gè)體的平均適應(yīng)度，favg是種群中最大的個(gè)體適應(yīng)度，f′是兩個(gè)待交叉的個(gè)體中適應(yīng)度函數(shù)值較大的個(gè)體的適應(yīng)度值，pc1>pc2>pc3,A=9.903 438,r為一個(gè)很小的正數(shù)。交叉概率隨適應(yīng)度函數(shù)的增大而漸漸變小，在進(jìn)化的初期基因種類比較豐富，但是缺乏優(yōu)良的個(gè)體，所以要增大交叉概率，進(jìn)化的后期基因種類趨于一致，優(yōu)良的個(gè)體比較多，所以要減小交叉概率，防止破壞優(yōu)良的個(gè)體。

3)交叉操作后，評估每個(gè)解的適應(yīng)度值，然后進(jìn)行自適應(yīng)變異操作，變異概率的計(jì)算公式為[8]

(3)

式中f為要變異個(gè)體的適應(yīng)度值，pm1>pm2>pm3，變異概率隨適應(yīng)度函數(shù)值的增大而逐漸增大。進(jìn)化初期基因種類豐富，所以要減小變異概率，進(jìn)化后期基因種類趨于一致，種群的多樣性減小，所以,要增大變異概率增加種群的多樣性。

4)評估變異操作后的解，用精英種群代替最差的M個(gè)解，找到當(dāng)前的全局最優(yōu)解，更新全局最優(yōu)解，選出適應(yīng)度值較大的前N個(gè)解，迭代次數(shù)加1。

5)判斷是否達(dá)到最大迭代次數(shù)或者到達(dá)，到達(dá)最大迭代次數(shù)算法結(jié)束，輸出最優(yōu)解;否則，返回到B繼續(xù)進(jìn)行迭代。

改進(jìn)算法的流程圖如圖2。

圖2　改進(jìn)遺傳算法流程圖Fig 2　Flow chart of improved genetic algorithm

3　仿真結(jié)果與分析

3.1仿真場景

用一個(gè)UMTS現(xiàn)網(wǎng)中的數(shù)據(jù)進(jìn)行仿真，該區(qū)域有454個(gè)小區(qū)，每個(gè)小區(qū)有機(jī)械下傾角、方位角、電子下傾角、發(fā)射功率、天線類型五個(gè)變量，整個(gè)優(yōu)化問題的維度高達(dá)2 000多維，搜索空間巨大。仿真區(qū)域包含1 590 000多條MR數(shù)據(jù)，218種天線信息。地圖的最小分辨率為20 m×20 m，為一個(gè)柵格的大小，數(shù)據(jù)經(jīng)過地理平均后，地圖上的柵格有205 650個(gè)。優(yōu)化目標(biāo)有RSCP，Ec/Io，1st-Nth 導(dǎo)頻污染，各目標(biāo)的權(quán)重設(shè)置為1。本文采用標(biāo)準(zhǔn)遺傳算法和文獻(xiàn)[8]中提出的自適應(yīng)遺傳算法進(jìn)行對比，標(biāo)準(zhǔn)遺傳算法的交叉概率和變異概率為固定值，分別為0.8和0.1。式(2)中，pc1=0.9，pc2=0.8，pc3=0.6，式(3)中，pm1=0.1，pm2=0.05，pm3=0.01。

仿真過程中的其他參數(shù)配置：N階RSCP的N值為4;RSCP達(dá)標(biāo)門限值為-80 dBm;Ec/Io達(dá)標(biāo)門限值為-8 dB;1st RSRP～4th RSRP達(dá)標(biāo)門限值為5 dB;負(fù)載均衡的約束值為0.8 dB;負(fù)載達(dá)標(biāo)的門限值為0.05 dB。

3.2仿真結(jié)果與分析

將本文提出的改進(jìn)的遺傳算法與標(biāo)準(zhǔn)遺傳算法和文獻(xiàn)[8]中自適應(yīng)遺傳算法進(jìn)行比較，如圖3所示。

圖3　改進(jìn)的遺傳算法與其他遺傳算法對比Fig 3　Comparison of improved genetic algorithm and other genetic algorithms

圖3中可以看出：在算法前期，標(biāo)準(zhǔn)遺傳算法的效果比較好，但是很快陷入局部最優(yōu)，出現(xiàn)早熟現(xiàn)象，在18代之后就停止進(jìn)化了。自適應(yīng)算法前期有一段時(shí)間進(jìn)化很慢，陷入局部最優(yōu)，但經(jīng)過多次迭代之后可以跳出局部最優(yōu)，到中后期速度開始變快，經(jīng)過100次的迭代之后，性能值接近0.89，而本文提出的改進(jìn)的遺傳算法在整個(gè)迭代過程中表現(xiàn)得較好，沒有明顯陷入局部最優(yōu)解，這是因?yàn)樵谒惴ǔ跏蓟瘯r(shí)，采用了正交方法獲得問題的初始解，經(jīng)過100次的迭代，性能值接近0.9，得到的結(jié)果更加理想。

圖4是采用改進(jìn)的遺傳算法優(yōu)化前后柵格RSCP的累計(jì)分布曲線(CDF曲線)。優(yōu)化前RSCP小于等于-80 dB的柵格為70 %，優(yōu)化后RSCP小于等于-80 dB的柵格為25 %，說明優(yōu)化后大多數(shù)柵格的RSCP值變大，優(yōu)化指標(biāo)RSCP在優(yōu)化后有很大的改善。圖5是采用改進(jìn)的遺傳算法優(yōu)化前后柵格Ec/Io的累計(jì)分布曲線。優(yōu)化前Ec/Io小于等于-4 dB的柵格為60 %，優(yōu)化后Ec/Io小于等于-4 dB的柵格為40 %，說明優(yōu)化后大多數(shù)柵格的Ec/Io值變大，優(yōu)化指標(biāo)Ec/Io在優(yōu)化后有很大的改善。

圖4　優(yōu)化前后累計(jì)分布曲線-RSCPFig 4　Cumulative distribution curve before and after optimization-RSCP

圖5　優(yōu)化前后累計(jì)分布曲線Fig 5　Cumulative distribution curve before and after optimization

4　結(jié)束語

為了解決ACP-UMTS無線網(wǎng)絡(luò)優(yōu)化的問題，本文采用了改進(jìn)的遺傳算法，該算法用一種特殊的正交方法產(chǎn)生初始解，采用精英種群策略，并自適應(yīng)地改變交叉概率和變異概率。仿真結(jié)果表明：與其他遺傳算法相比，改進(jìn)的遺傳算法能夠很好地處理ACP問題，它避免算法陷入局部最優(yōu)，能達(dá)到良好的優(yōu)化效果。

[1]程敏.自動小區(qū)規(guī)劃在LTE小區(qū)射頻控制中的應(yīng)用[J].移動通信，2014，3(4):30-37.

[2]歐陽暉.自動小區(qū)規(guī)劃的實(shí)際應(yīng)用考慮[J].現(xiàn)代電信科技，2012，8(8):71-76.

[3]沈亮，周俊.自動規(guī)劃工具對無線規(guī)劃設(shè)計(jì)的影響[J].電信工程技術(shù)與標(biāo)準(zhǔn)化，2008(5):51-55.

[4]Guo Pengfei,Wang Xuezhi,Han Yingshi.The enhanced genetic algorithms for the optimization design[C]∥International Confe-rence on Biomedical Engineering and Informatics (BMEI),2010:2990-2994.

[5]Zhao Xin,Xiu Chunbo.New genetic algorithm improved and its applications[C]∥International Conference on Electronics Communications and Control (ICECC),2011:926-928.

[6]Zheng Jiezhen,Wang Zhijun,Wang Shiyun.BP neural network optimize based on improved genetic algorithm[C]∥International Conference on Computer Engineering and Technology(ICCET),2010:526-529.

[7]祁榮賓,錢鋒,杜文莉,等.基于精英選擇和個(gè)體遷移的多目標(biāo)遺傳算法[J].控制與決策，2007，22(2):164-168.

[8]李延梅.一種改進(jìn)的遺傳算法及應(yīng)用 [D].廣州:華南理工大學(xué)，2012.

[9]Kazimipour Borhan,Li Xiaodong,Qin A K.Initialization methods for large scale global optimization[C]∥2013 IEEE Congress on Evolutionary Computation (CEC),2013:2750-2757.

Application of genetic algorithm in UMTS automatic cell planning

LIU Ji-yong1, ZHANG Lei2

(1.Hebei Branch，China Mobile,Shijiazhuang 050000,China；2.School of Information and Communication Engineering,Beijing University of Posts and Telecommunications，Beijing 100876,China)

Aiming at problem of wireless network automatic cell planning (ACP) of a high-dimensionally optimizing universal mobile telecommunications system (UMTS),is used improved genetic algorithm This algorithm adopts a special orthogonal method to give initial solutions,use the elitist selection strategy and adaptively changes the values of crossover probabilities and mutation probabilities.The simulation results show that the performance of the algorithm is significantly upgraded compared with other genetic algorithms,and the optimal solutions to high-dimensional UMTS-ACP issue can be found more effectively.

wireless network optimization; universal mobile telecommunications system(UMTS); genetic algorithm

2015—10—12

TN 929.5

B

1000—9787(2016)08—0148—03

劉計(jì)永(1974-)，男，河北館陶人，通信工程師，從事無線通信、管理信息化研究工作。

DOI:10.13873/J.1000—9787(2016)08—0148—03