基于模擬退火遺傳算法解決MC-CDMA系統(tǒng)NP完備問題

MC-CDMA集OFDM和CDMA的優(yōu)點于一體，具有很大應(yīng)用潛力。但該系統(tǒng)存在嚴(yán)重的多址干擾，這不僅嚴(yán)重影響了系統(tǒng)的抗干擾性，也嚴(yán)重限制了系統(tǒng)容量的提高。多用戶檢測技術(shù)是消除多址干擾的有效手段，但其算法復(fù)雜度較高，建設(shè)成本較大，尤其是檢測性能最好的最佳多用戶檢測技術(shù)，其算法復(fù)雜度隨用戶數(shù)目成指數(shù)增長，不適合實際應(yīng)用。

遺傳算法是一種通用的求解最優(yōu)化問題的智能算法。它的計算性能好，運算量較小?？紤]到最佳多用戶檢測是求二次整數(shù)非線性優(yōu)化問題的全局最優(yōu)解，因此將解決優(yōu)化問題的遺傳算法應(yīng)用于最佳多用戶檢測技術(shù)中是行之有效的。

基本遺傳算法存在局部搜索能力較弱和收斂速度較慢等問題。模擬退火法是一種模擬高溫金屬降溫的熱力學(xué)過程的隨機組合優(yōu)化方法。在初始溫度足夠高、溫度下降足夠慢的條件下，能以概率1向全局最優(yōu)值收斂。若將模擬退火應(yīng)用于遺傳算法中，便能克服遺傳算法易陷入局部極小點的缺點，使得搜索沿著全局最優(yōu)化方向發(fā)展。本文研究模擬退火遺傳算法在MC-CDMA系統(tǒng)多用戶檢測技術(shù)中的應(yīng)用，利用其求解NP（Non-deterministic Polynomial）完備問題。

1 模擬退火遺傳算法

1.1 遺傳算法

遺傳算法（GA）是基于生物自然選擇和遺傳學(xué)原理的一種自適應(yīng)啟發(fā)式、概率性迭代式的全局搜索算法，其主要借用了生物進化中“適者生存”和“優(yōu)勝劣汰”的規(guī)律。它利用簡單的編碼技術(shù)和繁殖機制來表現(xiàn)復(fù)雜的現(xiàn)象，以編碼空間代替問題的參數(shù)空間，以適應(yīng)度函數(shù)為評價依據(jù)、以編碼群體為進化基礎(chǔ)，以對群體中個體位串的遺傳操作實現(xiàn)選擇和遺傳機制，建立迭代過程。在這一過程中，通過隨機重組編碼位串中的優(yōu)秀基因，使子代群體優(yōu)于父代群體，群體個體不斷進化，逐漸接近最優(yōu)解，最終實現(xiàn)問題求解。它模擬自然界中的生命進化機制，在人工系統(tǒng)中實現(xiàn)特定目標(biāo)的優(yōu)化。實踐證明，遺傳算法對于NP問題非常有效，但是它容易陷入局部最優(yōu)，即全局搜索能力弱。

1.2 模擬退火算法

模擬退火算法（SA）是基于金屬退火的機理而建立起來的一種隨機算法。它是一種全局最優(yōu)化方法，能夠以隨機搜索技術(shù)從概率的意義上找出目標(biāo)函數(shù)的全局最小點。在搜索最優(yōu)解的過程中，模擬退火算法除了接受最優(yōu)化解外，還用隨機接受準(zhǔn)則有限地接受惡化解，這使得算法有可能擺脫局部最優(yōu)，盡可能找到全局最優(yōu)解，保證算法收斂。它通過控制溫度的變化過程來實現(xiàn)大范圍的粗略搜索與局部的精細搜索。采用指數(shù)降溫策略對溫度的變化進行控制，即：

使用上述準(zhǔn)則的優(yōu)點是：當(dāng)新解更優(yōu)時，完全接受新解的當(dāng)前解；而當(dāng)新解為惡化解時，以概率P接受惡化解為新的當(dāng)前解。這使得SA能夠避免陷入局部最優(yōu)。隨著優(yōu)化的進行，SA的局部搜索能力也逐漸增強，確保算法有足夠的搜索精度。

模擬退火算法有可能擺脫局部最優(yōu)，找到全局最優(yōu)解，保證算法收斂。但是它只是搜索解空間中的一點且對解空間中已知試探的區(qū)域知之甚少，因此難以判斷哪些區(qū)域有更多的機會找到最優(yōu)解。所以，其收斂到全局最優(yōu)解是非常耗時的。

1.3 模擬退火遺傳算法

鑒于遺傳算法的并行性和它在算法結(jié)構(gòu)上的特點， 可以很容易地將遺傳算法和其他算法混合使用， 從而達到揚長避短的作用。從上文的論述中可以看出，若將遺傳算法的全局搜索功能和模擬退火的局部搜索功能互相補充，將相得益彰。

本文在遺傳算法中融入模擬退火思想，首先，在選擇操作中引入退火思想并允許適應(yīng)度高的少量父代與子代共同競爭；其次，根據(jù)模擬退火思想設(shè)計出自適應(yīng)交叉概率和變異概率，從而保證了種群的多樣性以及收斂速度。模擬退火遺傳算法的流程如下：

（1）初始群體的產(chǎn)生：為了得到理想的初始種群，首先在每個變量的取值范圍內(nèi)均勻產(chǎn)生種群，然后通過設(shè)計重組與篩選算子進行重新組合，從而保證其多樣性和組合隨機性。在經(jīng)過交叉變異產(chǎn)生的子代中同樣采用篩選算子使新一代種群中避免出現(xiàn)大量重復(fù)個體，使算法能夠趨于收斂。篩選算子流程如圖1所示。

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

其中，{Tk}漸趨于0的退火溫度，Tk=1/ln（k/T0+1），T0為起始溫度。

（3）自適應(yīng)度交叉概率和變異概率

GA的交叉概率Pc與變異概率Pm對其性能影響很大，它們的選擇直接影響算法的收斂性。在進化初期，為了避免個別適應(yīng)度高的個體迅速繁殖，出現(xiàn)早熟現(xiàn)象，Pc和Pm不宜過小，以增加種群的多樣性；在進化后期，個體接近最優(yōu)解時，Pc和Pm不宜過大，以避免個體長期無法達到最優(yōu)解［8］。文中的Pc和Pm根據(jù)模擬退火思想按照如下公式進行自適應(yīng)調(diào)整：

其中T′類似于模擬退火中的溫度T，為進化代數(shù)的倒數(shù)；gen為設(shè)定的進化總代數(shù)。在進化初期T′較高，則Pc和Pm較大，以利于種群的多樣性；隨著進化代數(shù)的增加，T′逐漸減小，Pc和Pm漸進減小，便于個體向最優(yōu)解靠近。

從上述內(nèi)容可知，將模擬退火應(yīng)用于遺傳算法中，在優(yōu)選交叉和變異個體的過程中通過加入一定的“擾動”以達到保持群體中位串多樣性和位串之間的競爭機制，從而克服算法易陷入局部極小點的問題，使得搜索沿著全局最優(yōu)化方向趨進。

2 模擬退火遺傳算法在多用戶檢測技術(shù)中的應(yīng)用

模擬退火算法與遺傳算法相結(jié)合，取長補短，形成了模擬退火遺傳算法。多用戶檢測是一個NP完備問題，將模擬退火遺傳算法用于多用戶檢測中是可行的。圖2為模擬退火遺傳算法多用戶檢測原理框圖，由濾波器和多用戶檢測器兩部分組成。它有 k個輸入和k個輸出。

基于模擬退火遺傳算法的多用戶檢測器以匹配濾波器的輸出作為模擬退火遺傳算法的初始值，再通過模擬退火遺傳算法的啟發(fā)式搜索，提高多用戶檢測器的抗多址干擾和抗遠近效應(yīng)能力。同時通過模擬退火算法來減輕遺傳算法的選擇壓力，這樣不但可以避免遺傳算法的早熟收斂問題，并且使群體中的最優(yōu)解得到了保留。模擬退火遺傳算法多用戶檢測器的基本操作流程如下：

（1）初始化控制參數(shù)。如群體規(guī)模N、用戶數(shù)K、初始溫度t0、變化系數(shù)？墜、變異概率Pm和交叉概率Pc等。

（2）編碼。解向量b是由{-1，1}組成的二進制序列，無需編碼。

（3）初始化種群。將經(jīng)匹配濾波器并經(jīng)判決后的結(jié)果作為初始種群中的一個個體B1送入模擬退火遺傳算法多用戶檢測器，其余N-1個個體均由其隨機擾動產(chǎn)生。

（4）適應(yīng)度函數(shù)評價。采用與簡單遺傳算法多用戶檢測相同的適應(yīng)度函數(shù)，計算種群中每個個體的適應(yīng)度函數(shù)值f。

（5）交叉。隨機選取兩個個體Bi和Bj進行交叉，產(chǎn)生新個體Bi′和Bj′，計算f（j）和f（i），并按Metropolis準(zhǔn)則計算接收概率，若P=min{1，exp［f（i）-f（j）/tk］}≥random［0，1］，則接收新解，否則保持原狀態(tài)。

（6）對交叉后的個體進行變異操作，按與（5）中同樣的判決方法判斷是否接受變異后產(chǎn)生的新個體。

（7）判斷是否滿足收斂條件。若已經(jīng)達到預(yù)先設(shè)定的最大遺傳代數(shù)，則迭代過程結(jié)束，輸出最優(yōu)解；否則有ti+1=？墜ti，？墜《1，并轉(zhuǎn)至（4）進行下一步的迭代尋優(yōu)工作。

從上述內(nèi)容可知，與基于復(fù)雜矩陣算法的傳統(tǒng)多用戶檢測器相比，基于模擬退火遺傳算法的多用戶檢測器算法降低了難度。

3 仿真研究

利用MATLAB仿真平臺將基于模擬退火遺傳算法的多用戶檢測器（SAGA）與傳統(tǒng)最佳多用戶檢測器（OMD）、基于遺傳算法的多用戶檢測器（GA）以及其他典型多用戶檢測算法進行性能比較，以誤碼率隨信噪比的變化曲線作為比較參數(shù)。

仿真環(huán)境：上行同步的CDMA系統(tǒng)，采用BPSK調(diào)制，使用正交Walsh碼作為擴頻碼，其中碼長為16。系統(tǒng)中共有8個用戶且信道信息已知，設(shè)定信道為2徑等增益衰落信道（L=2），每條徑的幅度服從瑞利分布，相位服從［0，2π］間的均勻分布，使用理想功率控制。遺傳算法中所取各參數(shù)值分別為：種群數(shù)為10，變異概率為0.9，交叉概率為0.1。

圖3比較了各種典型多用戶檢測算法性能。其中最優(yōu)多用戶檢測算法性能最好，但其計算量太大，復(fù)雜度高。圖4比較了最佳多用戶檢測器、遺傳算法多用戶檢測器和模擬退火遺傳算法檢測器的抗干擾性能。結(jié)合圖3和圖4可以看出：本文所采用的基于模擬退火遺傳算法的多用戶檢測器性能優(yōu)于遺傳算法多用戶檢測器和其他次優(yōu)多用戶檢測器，且非常接近最佳多用戶檢測器。

通過將模擬退火算法融入遺傳算法框架中，對基本遺傳算法進行改進，即一方面允許父代參與競爭，將父代群體中最優(yōu)個體和子代群體中最優(yōu)個體組成新的群體并進行退火選擇;另一方面根據(jù)模擬退火思想自適應(yīng)調(diào)整Pc和Pm，從而形成SAGA，然后將其應(yīng)用到多用戶檢測技術(shù)中，有效地解決了移動通信系統(tǒng)中存在的多址干擾等問題。由于其算法性能接近最優(yōu)多用戶檢測器，有效地消除了多址干擾，而且算法難度有所降低，很適合在實際系統(tǒng)中的應(yīng)用。

責(zé)任編輯：gt