MC-CDMA集OFDM和CDMA的優(yōu)點(diǎn)于一體,，具有很大應(yīng)用潛力,。但該系統(tǒng)存在嚴(yán)重的多址干擾，這不僅嚴(yán)重影響了系統(tǒng)的抗干擾性,，也嚴(yán)重限制了系統(tǒng)容量的提高[1],。多用戶檢測(cè)技術(shù)是消除多址干擾的有效手段，但其算法復(fù)雜度較高，建設(shè)成本較大,，尤其是檢測(cè)性能最好的最佳多用戶檢測(cè)技術(shù),，其算法復(fù)雜度隨用戶數(shù)目成指數(shù)增長，不適合實(shí)際應(yīng)用[2-3],。
    遺傳算法是一種通用的求解最優(yōu)化問題的智能算法[4],。它的計(jì)算性能好，運(yùn)算量較小,?？紤]到最佳多用戶檢測(cè)是求二次整數(shù)非線性優(yōu)化問題的全局最優(yōu)解，因此將解決優(yōu)化問題的遺傳算法應(yīng)用于最佳多用戶檢測(cè)技術(shù)中是行之有效的,。
    基本遺傳算法存在局部搜索能力較弱和收斂速度較慢等問題[5],。模擬退火法是一種模擬高溫金屬降溫的熱力學(xué)過程的隨機(jī)組合優(yōu)化方法。在初始溫度足夠高,、溫度下降足夠慢的條件下,，能以概率1向全局最優(yōu)值收斂[6-7]。若將模擬退火應(yīng)用于遺傳算法中,，便能克服遺傳算法易陷入局部極小點(diǎn)的缺點(diǎn),，使得搜索沿著全局最優(yōu)化方向發(fā)展。本文研究模擬退火遺傳算法在MC-CDMA系統(tǒng)多用戶檢測(cè)技術(shù)中的應(yīng)用,，利用其求解NP（Non-deterministic Polynomial）完備問題,。
1 模擬退火遺傳算法
1.1 遺傳算法
    遺傳算法(GA)是基于生物自然選擇和遺傳學(xué)原理的一種自適應(yīng)啟發(fā)式、概率性迭代式的全局搜索算法,，其主要借用了生物進(jìn)化中“適者生存”和“優(yōu)勝劣汰”的規(guī)律,。它利用簡單的編碼技術(shù)和繁殖機(jī)制來表現(xiàn)復(fù)雜的現(xiàn)象,以編碼空間代替問題的參數(shù)空間,以適應(yīng)度函數(shù)為評(píng)價(jià)依據(jù)、以編碼群體為進(jìn)化基礎(chǔ),以對(duì)群體中個(gè)體位串的遺傳操作實(shí)現(xiàn)選擇和遺傳機(jī)制,，建立迭代過程,。在這一過程中，通過隨機(jī)重組編碼位串中的優(yōu)秀基因,，使子代群體優(yōu)于父代群體,，群體個(gè)體不斷進(jìn)化，逐漸接近最優(yōu)解,，最終實(shí)現(xiàn)問題求解,。它模擬自然界中的生命進(jìn)化機(jī)制，在人工系統(tǒng)中實(shí)現(xiàn)特定目標(biāo)的優(yōu)化,。實(shí)踐證明,，遺傳算法對(duì)于NP問題非常有效[8]，但是它容易陷入局部最優(yōu),，即全局搜索能力弱,。
1.2 模擬退火算法
    模擬退火算法(SA)是基于金屬退火的機(jī)理而建立起來的一種隨機(jī)算法,。它是一種全局最優(yōu)化方法，能夠以隨機(jī)搜索技術(shù)從概率的意義上找出目標(biāo)函數(shù)的全局最小點(diǎn),。在搜索最優(yōu)解的過程中,，模擬退火算法除了接受最優(yōu)化解外，還用隨機(jī)接受準(zhǔn)則有限地接受惡化解,，這使得算法有可能擺脫局部最優(yōu)，盡可能找到全局最優(yōu)解,，保證算法收斂,。它通過控制溫度的變化過程來實(shí)現(xiàn)大范圍的粗略搜索與局部的精細(xì)搜索。采用指數(shù)降溫策略對(duì)溫度的變化進(jìn)行控制,，即：

    使用上述準(zhǔn)則的優(yōu)點(diǎn)是：當(dāng)新解更優(yōu)時(shí),，完全接受新解的當(dāng)前解；而當(dāng)新解為惡化解時(shí),，以概率P接受惡化解為新的當(dāng)前解,。這使得SA能夠避免陷入局部最優(yōu)。隨著優(yōu)化的進(jìn)行,，SA的局部搜索能力也逐漸增強(qiáng),，確保算法有足夠的搜索精度。
　 模擬退火算法有可能擺脫局部最優(yōu),，找到全局最優(yōu)解,，保證算法收斂。但是它只是搜索解空間中的一點(diǎn)且對(duì)解空間中已知試探的區(qū)域知之甚少,，因此難以判斷哪些區(qū)域有更多的機(jī)會(huì)找到最優(yōu)解,。所以，其收斂到全局最優(yōu)解是非常耗時(shí)的,。
1.3 模擬退火遺傳算法
    鑒于遺傳算法的并行性和它在算法結(jié)構(gòu)上的特點(diǎn), 可以很容易地將遺傳算法和其他算法混合使用, 從而達(dá)到揚(yáng)長避短的作用,。從上文的論述中可以看出,若將遺傳算法的全局搜索功能和模擬退火的局部搜索功能互相補(bǔ)充，將相得益彰,。
    本文在遺傳算法中融入模擬退火思想,，首先,在選擇操作中引入退火思想并允許適應(yīng)度高的少量父代與子代共同競爭；其次,根據(jù)模擬退火思想設(shè)計(jì)出自適應(yīng)交叉概率和變異概率,，從而保證了種群的多樣性以及收斂速度,。模擬退火遺傳算法的流程如下：
    (1)初始群體的產(chǎn)生:為了得到理想的初始種群，首先在每個(gè)變量的取值范圍內(nèi)均勻產(chǎn)生種群,，然后通過設(shè)計(jì)重組與篩選算子進(jìn)行重新組合,，從而保證其多樣性和組合隨機(jī)性。在經(jīng)過交叉變異產(chǎn)生的子代中同樣采用篩選算子使新一代種群中避免出現(xiàn)大量重復(fù)個(gè)體,，使算法能夠趨于收斂,。篩選算子流程如圖1所示,。

    (2)退火選擇操作：運(yùn)用適者生存法則，繁殖操作在舊的群體中“隨機(jī)”選擇符號(hào)串生成一個(gè)新的種群,，但選擇并非完全隨機(jī),，它基于一個(gè)符號(hào)串相對(duì)于整個(gè)群體的適應(yīng)度。在常用的輪盤賭選擇方法中,，個(gè)體被選中的概率遵循Montecarlo方法,，與其適應(yīng)度和種群的平均適應(yīng)度的比值成正比：

其中，{Tk}漸趨于0的退火溫度,，Tk=1/ln(k/T0+1),，T0為起始溫度。
    (3)自適應(yīng)度交叉概率和變異概率
    GA的交叉概率Pc與變異概率Pm對(duì)其性能影響很大,，它們的選擇直接影響算法的收斂性,。在進(jìn)化初期，為了避免個(gè)別適應(yīng)度高的個(gè)體迅速繁殖,，出現(xiàn)早熟現(xiàn)象,，Pc和Pm不宜過小，以增加種群的多樣性,；在進(jìn)化后期,，個(gè)體接近最優(yōu)解時(shí)，Pc和Pm不宜過大,，以避免個(gè)體長期無法達(dá)到最優(yōu)解[8],。文中的Pc和Pm根據(jù)模擬退火思想按照如下公式進(jìn)行自適應(yīng)調(diào)整：

其中T′類似于模擬退火中的溫度T,為進(jìn)化代數(shù)的倒數(shù)；gen為設(shè)定的進(jìn)化總代數(shù),。在進(jìn)化初期T′較高,，則Pc和Pm較大，以利于種群的多樣性,；隨著進(jìn)化代數(shù)的增加,，T′逐漸減小，Pc和Pm漸進(jìn)減小,，便于個(gè)體向最優(yōu)解靠近,。
    從上述內(nèi)容可知，將模擬退火應(yīng)用于遺傳算法中,，在優(yōu)選交叉和變異個(gè)體的過程中通過加入一定的“擾動(dòng)”以達(dá)到保持群體中位串多樣性和位串之間的競爭機(jī)制,，從而克服算法易陷入局部極小點(diǎn)的問題，使得搜索沿著全局最優(yōu)化方向趨進(jìn),。
2 模擬退火遺傳算法在多用戶檢測(cè)技術(shù)中的應(yīng)用
    模擬退火算法與遺傳算法相結(jié)合,，取長補(bǔ)短，形成了模擬退火遺傳算法,。多用戶檢測(cè)是一個(gè)NP完備問題,，將模擬退火遺傳算法用于多用戶檢測(cè)中是可行的,。圖2為模擬退火遺傳算法多用戶檢測(cè)原理框圖，由濾波器和多用戶檢測(cè)器兩部分組成,。它有 k個(gè)輸入和k個(gè)輸出,。

    基于模擬退火遺傳算法的多用戶檢測(cè)器以匹配濾波器的輸出作為模擬退火遺傳算法的初始值，再通過模擬退火遺傳算法的啟發(fā)式搜索,，提高多用戶檢測(cè)器的抗多址干擾和抗遠(yuǎn)近效應(yīng)能力,。同時(shí)通過模擬退火算法來減輕遺傳算法的選擇壓力，這樣不但可以避免遺傳算法的早熟收斂問題,，并且使群體中的最優(yōu)解得到了保留,。模擬退火遺傳算法多用戶檢測(cè)器的基本操作流程如下：
    (1)初始化控制參數(shù)。如群體規(guī)模N,、用戶數(shù)K、初始溫度t0,、變化系數(shù)?墜,、變異概率Pm和交叉概率Pc等。
    (2)編碼,。解向量b是由{-1,1}組成的二進(jìn)制序列,，無需編碼。
    (3)初始化種群,。將經(jīng)匹配濾波器并經(jīng)判決后的結(jié)果作為初始種群中的一個(gè)個(gè)體B1送入模擬退火遺傳算法多用戶檢測(cè)器,，其余N-1個(gè)個(gè)體均由其隨機(jī)擾動(dòng)產(chǎn)生。
    (4)適應(yīng)度函數(shù)評(píng)價(jià),。采用與簡單遺傳算法多用戶檢測(cè)相同的適應(yīng)度函數(shù),，計(jì)算種群中每個(gè)個(gè)體的適應(yīng)度函數(shù)值f。
    (5)交叉,。隨機(jī)選取兩個(gè)個(gè)體Bi和Bj進(jìn)行交叉,，產(chǎn)生新個(gè)體Bi′和Bj′，計(jì)算f(j)和f(i),，并按Metropolis準(zhǔn)則計(jì)算接收概率,，若P=min{1,exp[f(i)-f(j)/tk]}≥random[0,1]，則接收新解,，否則保持原狀態(tài),。
    (6)對(duì)交叉后的個(gè)體進(jìn)行變異操作，按與(5)中同樣的判決方法判斷是否接受變異后產(chǎn)生的新個(gè)體,。
    (7)判斷是否滿足收斂條件,。若已經(jīng)達(dá)到預(yù)先設(shè)定的最大遺傳代數(shù)，則迭代過程結(jié)束,，輸出最優(yōu)解,；否則有ti+1=?墜ti,?墜<1,，并轉(zhuǎn)至(4)進(jìn)行下一步的迭代尋優(yōu)工作。
　    從上述內(nèi)容可知,，與基于復(fù)雜矩陣算法的傳統(tǒng)多用戶檢測(cè)器相比,基于模擬退火遺傳算法的多用戶檢測(cè)器算法降低了難度,。
3 仿真研究
    利用MATLAB仿真平臺(tái)將基于模擬退火遺傳算法的多用戶檢測(cè)器（SAGA）與傳統(tǒng)最佳多用戶檢測(cè)器（OMD）、基于遺傳算法的多用戶檢測(cè)器（GA）以及其他典型多用戶檢測(cè)算法進(jìn)行性能比較,，以誤碼率隨信噪比的變化曲線作為比較參數(shù),。
　    仿真環(huán)境：上行同步的CDMA系統(tǒng),采用BPSK調(diào)制，使用正交Walsh碼作為擴(kuò)頻碼,，其中碼長為16,。系統(tǒng)中共有8個(gè)用戶且信道信息已知，設(shè)定信道為2徑等增益衰落信道(L=2),，每條徑的幅度服從瑞利分布,，相位服從[0,2&pi;]間的均勻分布，使用理想功率控制,。遺傳算法中所取各參數(shù)值分別為：種群數(shù)為10,，變異概率為0.9，交叉概率為0.1,。
    圖3比較了各種典型多用戶檢測(cè)算法性能,。其中最優(yōu)多用戶檢測(cè)算法性能最好，但其計(jì)算量太大,，復(fù)雜度高,。圖4比較了最佳多用戶檢測(cè)器、遺傳算法多用戶檢測(cè)器和模擬退火遺傳算法檢測(cè)器的抗干擾性能,。結(jié)合圖3和圖4可以看出：本文所采用的基于模擬退火遺傳算法的多用戶檢測(cè)器性能優(yōu)于遺傳算法多用戶檢測(cè)器和其他次優(yōu)多用戶檢測(cè)器,且非常接近最佳多用戶檢測(cè)器,。

    通過將模擬退火算法融入遺傳算法框架中，對(duì)基本遺傳算法進(jìn)行改進(jìn),，即一方面允許父代參與競爭,，將父代群體中最優(yōu)個(gè)體和子代群體中最優(yōu)個(gè)體組成新的群體并進(jìn)行退火選擇;另一方面根據(jù)模擬退火思想自適應(yīng)調(diào)整Pc和Pm，從而形成SAGA,，然后將其應(yīng)用到多用戶檢測(cè)技術(shù)中,，有效地解決了移動(dòng)通信系統(tǒng)中存在的多址干擾等問題。由于其算法性能接近最優(yōu)多用戶檢測(cè)器,，有效地消除了多址干擾,，而且算法難度有所降低，很適合在實(shí)際系統(tǒng)中的應(yīng)用,。
參考文獻(xiàn)
[1] 王少尉,季曉勇.最優(yōu)多用戶檢測(cè)問題研究[J].電子學(xué)報(bào), 2007,35(121):2339-2342.
[2] VERDU S. Minimum probability of error for asynchronous gaussian multiple access channels[J]. IEEE Trans on Info.1986,32(1):85-96.
[3] AAZMAN B. Nerual network for multi-user detection in code-division mutiple-access communication[J]. IEEE. TrailS.onComm, 1992,40(7):1212-1222.
[4] ERGUN C, HACIOGIU K. Multi-user detection using a genetic algorithm in CDMA communications systems [J]. IEEE Trans Commun,2000,48(8):1374-1383.
[5] 周麗,孫樹棟.遺傳算法原理及應(yīng)用[M].北京:國防工業(yè)出版社,2001.
[6] 朱顥東,鐘勇.一種改進(jìn)的模擬退火算法[J].計(jì)算機(jī)技術(shù)與發(fā)展.2009, 19(6):32-35.
[7] 周麗,黃素珍.基于模擬退火的混合遺傳算法研究[J].計(jì)算機(jī)應(yīng)用研究,2005,22(9):72-73,76.
[8] 王小平,曹立明.遺傳算法理論,、應(yīng)用與軟件實(shí)現(xiàn)[M]. 西安:西安交通大學(xué)出版社,2002.