一種單純形遺傳算法及其應(yīng)用

（中國(guó)移動(dòng)通信集團(tuán)設(shè)計(jì)院有限公司河北分公司，石家莊 030001）

1 引言

當(dāng)前，隨著TD-SCDMA網(wǎng)絡(luò)大規(guī)模建設(shè)以及對(duì)TD-SCDMA精品網(wǎng)的建設(shè)要求，對(duì)TD-SCDMA無(wú)線(xiàn)網(wǎng)絡(luò)規(guī)劃和優(yōu)化的精細(xì)度要求越來(lái)越高，廣播波束成形技術(shù)的應(yīng)用有利于改善網(wǎng)絡(luò)質(zhì)量，節(jié)約投資。本文針對(duì)已知預(yù)期方向圖的情況下，重點(diǎn)研究如何實(shí)現(xiàn)反向獲取權(quán)值的算法，即高維的優(yōu)化問(wèn)題進(jìn)行算法。

2 工程優(yōu)化問(wèn)題：廣播波束成形權(quán)值反向求解

在蜂窩組網(wǎng)中，智能天線(xiàn)主要實(shí)現(xiàn)了廣播波束和業(yè)務(wù)波束。廣播波束是在廣播時(shí)隙形成，實(shí)現(xiàn)對(duì)整個(gè)小區(qū)的廣播，所以要求波束寬度很寬，盡量做到小區(qū)無(wú)縫隙覆蓋。業(yè)務(wù)波束是在建立具體的通話(huà)鏈路后形成，也就是形成跟蹤波束，它會(huì)針對(duì)每一個(gè)用戶(hù)形成一個(gè)很窄的波束，這些波束會(huì)緊緊地跟蹤用戶(hù)。根據(jù)覆蓋的需要，調(diào)整天線(xiàn)中每個(gè)陣元的幅度和相位權(quán)值，得到對(duì)應(yīng)的廣播波束形狀，使得廣播波束可以根據(jù)需要的變化改變扇區(qū)的指向，既可以改變波束寬度；也可以改變波束的指向形成特殊場(chǎng)景需要的覆蓋形狀，比如馬鞍形。

對(duì)于大部分的場(chǎng)景來(lái)說(shuō)，比如65°、90°、65°偏轉(zhuǎn)20°等，廠(chǎng)家是給出了對(duì)應(yīng)的權(quán)值表。但是，針對(duì)特殊的場(chǎng)景需求，即不規(guī)則的覆蓋需要，這樣的情況，需要設(shè)置特殊的權(quán)值以達(dá)到更好的效果，發(fā)揮智能天線(xiàn)的優(yōu)勢(shì)。因此，面臨一個(gè)大致的期望覆蓋圖（方向圖），如何得到其對(duì)應(yīng)的權(quán)值，也就是說(shuō)如何反向獲取權(quán)值的算法，這實(shí)際上是一個(gè)高維的優(yōu)化問(wèn)題，維度為陣元的幅度和相位之和，對(duì)于單極化和雙極化的智能天線(xiàn)來(lái)說(shuō)，8個(gè)幅度權(quán)值和8個(gè)相位權(quán)值，共計(jì)16個(gè)維度。

這里智能天線(xiàn)的模型我們采用之前工作中的研究成果，本文重點(diǎn)研究相關(guān)的優(yōu)化算法，實(shí)現(xiàn)特殊形狀權(quán)值的求解自動(dòng)化。其基本步驟為：根據(jù)實(shí)際或仿真覆蓋情況，判斷出廣播波束的方向圖的大致形狀，通過(guò)程序進(jìn)行自動(dòng)仿真調(diào)整，得到每個(gè)陣元的廣播波束成形權(quán)值參數(shù)。具體來(lái)說(shuō)，根據(jù)實(shí)地勘查和網(wǎng)絡(luò)的實(shí)際情況，確定期望的廣播波束形狀。設(shè)計(jì)并采用一種優(yōu)化算法，循環(huán)逼近期望的方向圖，得到每個(gè)陣元的幅度和相位權(quán)值。在程序的迭代中，模型的選取是以圖乘法為主，加快求解權(quán)值的速度，同時(shí)矩量法模型進(jìn)行驗(yàn)證調(diào)整，綜合取定權(quán)值。

3 提出一種單純形遺傳算法

傳統(tǒng)的遺傳算法通常包括：創(chuàng)建一個(gè)隨機(jī)的初始狀態(tài)、評(píng)估適應(yīng)度、繁殖(包括子代突變)、下一代、并行計(jì)算等幾部分。可參見(jiàn)眾多書(shū)籍及文獻(xiàn)，對(duì)此不再贅述。

我們通過(guò)上一節(jié)的分析，所解決的廣播波束成形這個(gè)優(yōu)化問(wèn)題是一個(gè)16維的高維優(yōu)化問(wèn)題，并且其擬合目標(biāo)也較為復(fù)雜，為一個(gè)曲線(xiàn)。需要在算法設(shè)計(jì)上做一定的考慮。通過(guò)優(yōu)化算法文獻(xiàn)分析可知，大多數(shù)文獻(xiàn)都認(rèn)為遺傳算法容易陷入局部最小點(diǎn)，另外單純形的方法也存在類(lèi)似的問(wèn)題，對(duì)初值依賴(lài)性強(qiáng)。然而針對(duì)本優(yōu)化問(wèn)題，需要對(duì)此處進(jìn)行改進(jìn)。

我們?cè)谘芯勘苊庀萑刖植孔钚↑c(diǎn)時(shí)，提出一種單純形結(jié)合遺傳算法的新算法，具體要點(diǎn)如下：

（1）在整體流程中，每個(gè)循環(huán)先進(jìn)行遺傳算法，再進(jìn)行單純形，若不滿(mǎn)足則繼續(xù)循環(huán)。

（2）單純形處理個(gè)體。傳統(tǒng)的方式是“優(yōu)中選優(yōu)”，也就是說(shuō)，單純形處理個(gè)體中最好的n+1個(gè)，迭代一定次數(shù)返回。我們對(duì)此進(jìn)行了改進(jìn)，提出了“差中選優(yōu)”的思路，也就是說(shuō)，單純形處理個(gè)體中最差幾組n+1個(gè)點(diǎn)，迭代一定次數(shù)返回。區(qū)別在于一個(gè)是生物進(jìn)化“優(yōu)勝”的概念，一個(gè)是生物進(jìn)化“劣汰”的概念。

（3）雜交。雜交通常有一點(diǎn)雜交和兩點(diǎn)雜交兩種，針對(duì)優(yōu)化問(wèn)題通過(guò)多次測(cè)試，本改進(jìn)算法中采用的是兩點(diǎn)雜交。

（4）編碼方法，本算法采用實(shí)數(shù)來(lái)表示個(gè)體。其中算法的影響參數(shù)，群體大小M；交叉概率Pc；變異概率Pm。

新算法首先通過(guò)標(biāo)準(zhǔn)的DeJong F1～F5測(cè)試函數(shù)進(jìn)行初步測(cè)試，部分結(jié)果見(jiàn)表1所示。

4 應(yīng)用舉例

通過(guò)上述標(biāo)準(zhǔn)函數(shù)的測(cè)試驗(yàn)證了算法的性能之后，下面進(jìn)行廣播波束優(yōu)化問(wèn)題的尋優(yōu)進(jìn)行應(yīng)用。限于篇幅，給出兩個(gè)應(yīng)用舉例。

4.1 舉例1：逼近常規(guī)的廣播波束形狀

初值：采用幅度為1，相位為0，如圖1左圖細(xì)線(xiàn)所示。目標(biāo)值：為一廣播波束形狀，輸入方式360°一度一強(qiáng)度輸入，如粗色曲線(xiàn)所示。粗色方向圖對(duì)應(yīng)的權(quán)值來(lái)自天線(xiàn)廠(chǎng)家，幅度為[0.5 1 1 0.5 0.5 1 1 0.5]，相位為[0 0 0 180 0 0 0 180]。

通過(guò)改進(jìn)遺傳算法得到結(jié)果如圖1右圖所示，其中，粗色為目標(biāo)方向圖，細(xì)色為程序逼近方向圖，求解權(quán)值如下?？梢钥闯?，改進(jìn)算法能夠用較少的次數(shù)搜索出逼近期望的輸出結(jié)果。

圖1 廣播波束應(yīng)用舉例1

表1 部分測(cè)試結(jié)果

幅度[0.60 0.51 0.92 0.78 0.36 0.80 0.68 0.52]

相位[36 116 254 217 152 232 272 232]

4.2 舉例2：任意輸入方向圖

鞍馬形， 初值：采用幅度為一，相位為零。

目標(biāo)值：為一馬鞍形，輸入方式9點(diǎn)強(qiáng)度輸入，用戶(hù)輸入=[-5 -2 1 -2 -5 -2 1 -2-5]，假定非主方向是非關(guān)注形狀，即關(guān)注區(qū)間是正向±60°。通過(guò)程序插值，如圖2左圖粗曲線(xiàn)所示。

通過(guò)改進(jìn)遺傳算法得到結(jié)果如圖2右圖所示，其中，粗為目標(biāo)方向圖，細(xì)為程序逼近方向圖，求解權(quán)值如下?？梢钥闯?，改進(jìn)算法能夠用較少的次數(shù)搜索出逼近期望的輸出結(jié)果。

幅度[0.475 0.665 0.458 0.342 0.282 0.586 0.612 0.507]

相位[108.6 287.1 265.3 241.8 130.5 282.5 133.7 78.4]

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

圖2 廣播波束應(yīng)用舉例2

本文針對(duì)智能天線(xiàn)中具體的工程問(wèn)題，研究并提出了適合該特點(diǎn)的新的優(yōu)化算法，單純形遺傳算法，通過(guò)具體應(yīng)用驗(yàn)證，實(shí)現(xiàn)了較好自動(dòng)求解權(quán)值的目的。同時(shí)，本算法也可在其他網(wǎng)絡(luò)規(guī)劃和網(wǎng)絡(luò)優(yōu)化等尋優(yōu)問(wèn)題中參考使用。

[1] 李曉明. TD-SCDMA系統(tǒng)中智能天線(xiàn)發(fā)展現(xiàn)狀及未來(lái)趨勢(shì)[J].電信技術(shù)，2008(3).

[2] 南京電子技術(shù)研究所譯，相控陣天線(xiàn)手冊(cè)[M]. 北京：電子工業(yè)出版社，2007.

[3] 卜安濤，史小衛(wèi)，劉英, 等. 基于GA的智能天線(xiàn)系統(tǒng)前端扇區(qū)陣列設(shè)計(jì)[J]. 電波科學(xué)學(xué)報(bào), 2003,18(5).

[4] Teng J F; Dong J, Design of maximally flat FIR filters based on explicit formulas combined with optimization[J]. Transactions of Tianjin University，2006, 12(1), 13~18.

[5] YD/T1710.1. TD-SCDMA數(shù)字蜂窩移動(dòng)通信網(wǎng)智能天線(xiàn)第1部分：天線(xiàn)[S]，2007.

[6] Blans J J, Schmalenberger R, Papathanassiou A,et al. Smart antenna concepts for time-slotted CDMA[A]. Proc IEEE Vehicular Technology Conference[C]. Phoenix, AZ, USA, pp.11-15,vol.1, May 1997.

[7] 中國(guó)移動(dòng)通信集團(tuán). 中國(guó)移動(dòng)擴(kuò)大的TD-SCDMA規(guī)模網(wǎng)絡(luò)技術(shù)應(yīng)用試驗(yàn)網(wǎng)網(wǎng)絡(luò)優(yōu)化指導(dǎo)手冊(cè)[Z].