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

MC-CDMA集OFDM和CDMA的優(yōu)點(diǎn)于一體，具有很大應(yīng)用潛力。但該系統(tǒng)存在嚴(yán)重的多址干擾，這不僅嚴(yán)重影響了系統(tǒng)的抗干擾性，也嚴(yán)重限制了系統(tǒng)容量的提高[1]。多用戶檢測技術(shù)是消除多址干擾的有效手段，但其算法復(fù)雜度較高，建設(shè)成本較大，尤其是檢測性能最好的最佳多用戶檢測技術(shù)，其算法復(fù)雜度隨用戶數(shù)目成指數(shù)增長，不適合實(shí)際應(yīng)用[2-3]。
遺傳算法是一種通用的求解最優(yōu)化問題的智能算法[4]。它的計(jì)算性能好，運(yùn)算量較小?？紤]到最佳多用戶檢測是求二次整數(shù)非線性優(yōu)化問題的全局最優(yōu)解，因此將解決優(yōu)化問題的遺傳算法應(yīng)用于最佳多用戶檢測技術(shù)中是行之有效的。
基本遺傳算法存在局部搜索能力較弱和收斂速度較慢等問題[5]。模擬退火法是一種模擬高溫金屬降溫的熱力學(xué)過程的隨機(jī)組合優(yōu)化方法。在初始溫度足夠高、溫度下降足夠慢的條件下，能以概率1向全局最優(yōu)值收斂[6-7]。若將模擬退火應(yīng)用于遺傳算法中，便能克服遺傳算法易陷入局部極小點(diǎn)的缺點(diǎn)，使得搜索沿著全局最優(yōu)化方向發(fā)展。本文研究模擬退火遺傳算法在MC-CDMA系統(tǒng)多用戶檢測技術(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)整：