模擬退火遺傳禁忌搜索的多用戶檢測(cè)算法

刁 鳴，鄒 麗

（哈爾濱工程大學(xué)信息與通信工程學(xué)院，黑龍江 哈爾濱150001）

模擬退火遺傳禁忌搜索的多用戶檢測(cè)算法

刁 鳴，鄒 麗

（哈爾濱工程大學(xué)信息與通信工程學(xué)院，黑龍江 哈爾濱150001）

為了設(shè)計(jì)一種具有較低運(yùn)算復(fù)雜度并能解決早熟收斂的準(zhǔn)最優(yōu)多用戶檢測(cè)器，提出一種將遺傳算法、模擬退火算法和禁忌搜索結(jié)合到一起的新型多用戶檢測(cè)算法，稱為模擬遺傳禁忌搜索算法。在該算法中，模擬退火遺傳算法的結(jié)果為禁忌搜索提供一個(gè)初值。同時(shí)，將模擬退火的思想融入到遺傳算法中，提出自適應(yīng)的交叉概率和變異概率。仿真結(jié)果表明：應(yīng)用該算法的檢測(cè)器能夠有效避免局部最優(yōu)解，并能逐漸的收斂到全局最優(yōu)。

碼分多址；多用戶檢測(cè)；遺傳算法；禁忌搜索；模擬退火算法

傳統(tǒng)檢測(cè)器（conventional detector，CD）是將接收到的信號(hào)通過一組匹配濾波器進(jìn)行相干處理，然后基于輸出進(jìn)行門限判決。每個(gè)用戶都被獨(dú)立的檢測(cè)，并把其他的用戶當(dāng)作干擾或噪聲。雖然這種單用戶檢測(cè)策略容易實(shí)施，但是這種方法也會(huì)帶來一定的問題：不能抗遠(yuǎn)近效應(yīng)、抗多址干擾能力弱。最優(yōu)多用戶檢測(cè)器（optimal multiuser detection，OMD）由Verdu提出［1］，他證明了這種檢測(cè)器可以達(dá)到最小錯(cuò)誤概率，但是具有和用戶數(shù)成指數(shù)增長(zhǎng)的計(jì)算復(fù)雜度，這在當(dāng)前硬件水平下是不可能實(shí)現(xiàn)的。因此，探索具有較低計(jì)算復(fù)雜度且在降低多址干擾和遠(yuǎn)近效應(yīng)方面能夠達(dá)到較好效果的次優(yōu)多用戶檢測(cè)器是現(xiàn)在的主要研究方向。

多用戶檢測(cè)問題可以看成是一個(gè)多項(xiàng)式復(fù)雜程度的非確定性（non-deterministic polynomial，NP）完備問題［2］，智能算法可以被應(yīng)用于解決這樣的問題。遺傳算法收斂速度慢，并且容易收斂至局部最優(yōu)解，而將遺傳算法、模擬退火算法結(jié)合起來，不僅能夠增強(qiáng)遺傳算法的全局收斂性和爬山性，而且使進(jìn)化后期的收斂速度加快了。禁忌搜索是一種局部搜索能力很強(qiáng)的全局迭代尋優(yōu)算法，但是對(duì)初始解有很強(qiáng)的依賴性，一個(gè)好的初始解可以極大的提高算法的性能，因此，可以將模擬退火遺傳算法的結(jié)果作為禁忌搜索的初始值，這樣能提高禁忌搜索的收斂速度。

1 多用戶檢測(cè)模型

在直接擴(kuò)頻序列DS-CDMA通信系統(tǒng)中，每個(gè)用戶對(duì)應(yīng)的特征波形對(duì)用戶傳遞信號(hào)擴(kuò)頻后迭加再加上信道噪聲就得到了接收信號(hào)，接收信號(hào)的數(shù)學(xué)模型可以表示為

傳統(tǒng)多用戶檢測(cè)器是將接收到的信號(hào)分別通過具有K個(gè)匹配濾波器的濾波器組：

然后進(jìn)行門限判決：

最優(yōu)多用戶檢測(cè)器可以表示為

式中：H∈RK×K，H中元素為取遍共2（2M+1）K個(gè)所有可能的組合后必能找到這個(gè)使函數(shù)最大的值作為檢測(cè)的結(jié)果，顯然這種方法的計(jì)算復(fù)雜度與用戶數(shù)成指數(shù)關(guān)系增長(zhǎng)。

2 遺傳算法、模擬退火算法和禁忌搜索

2.1 遺傳算法

遺傳算法（genetic algorithm，GA）是一種基于達(dá)爾文遺傳選擇和自然淘汰的生物進(jìn)化理論的全局搜索算法，它以一組隨機(jī)產(chǎn)生的解開始，每次迭代中又模擬進(jìn)化和繼承的遺傳操作產(chǎn)生一組新解，這些解都會(huì)根據(jù)適應(yīng)度函數(shù)進(jìn)行估計(jì)［3-5］，不斷重復(fù)這樣的過程，直到達(dá)到某種形式上的收斂。

2.2 模擬退火算法

模擬退火算法是模擬物理熱力學(xué)中固體退火原理來尋找最優(yōu)解的隨機(jī)搜索方法。當(dāng)新解更優(yōu)時(shí)，則接受新解為當(dāng)前解；而當(dāng)新解的質(zhì)量沒有提高時(shí)，以一定的概率接受這個(gè)較差的新解為當(dāng)前解［6］。接受概率可由Metropolis準(zhǔn)則來確定：

式中：fk+1是新解的適應(yīng)度函數(shù)值，fk是當(dāng)前解的適應(yīng)度函數(shù)值，P（tk+1）是在溫度為tk+1條件下的接受概率。

2.3 禁忌搜索

禁忌搜索算法是一種亞啟發(fā)式隨機(jī)搜索算法，通過引入一個(gè)靈活的存儲(chǔ)結(jié)構(gòu)和相應(yīng)的禁忌規(guī)則來進(jìn)行搜索，從而實(shí)現(xiàn)全局優(yōu)化。為了避免陷入局部最優(yōu)，禁忌搜索中采用了一種靈活的記憶技術(shù)，對(duì)已經(jīng)進(jìn)行的優(yōu)化過程進(jìn)行記錄和選擇，指導(dǎo)下一步的搜索方向，這就是Tabu表的建立。

3 多用戶檢測(cè)中的模擬退火遺傳禁忌搜索算法

3.1 模擬退火遺傳算法

考慮到遺傳算法結(jié)構(gòu)上的特點(diǎn)及其并行性，可以很容易地將遺傳算法和其他算法結(jié)合起來，從而更好地發(fā)揮算法的優(yōu)勢(shì)［7-9］。從以上的論述中可以看到，如果將遺傳算法的全局搜索功能和模擬退火的局部搜索功能相互結(jié)合，將會(huì)達(dá)到更好的搜索效果。

本文將模擬退火思想融入到遺傳算法中。首先，在交叉和變異后，以一定的概率接受惡化解；其次，設(shè)計(jì)出自適應(yīng)交叉概率和變異概率，從而避免局部最優(yōu)，達(dá)到收斂。

為了改善遺傳算法的不足，在遺傳算法中引入模擬退火的思想，具體可以體現(xiàn)在以下2個(gè)方面中：

1）在交叉和變異操作中引入模擬退火思想，適當(dāng)允許適應(yīng)度高的少量父代和子代共同競(jìng)爭(zhēng)；

2）根遺傳算法的交叉概率和變異概率對(duì)算法的性能有很大影響，在進(jìn)化的初始階段，為了防止少數(shù)適應(yīng)度高的個(gè)體過度繁殖，使算法過早收斂，Pc和Pm的值不宜過小；而在進(jìn)化的后期，個(gè)體已經(jīng)接近最優(yōu)解，此時(shí)Pc和Pm的值不宜過大。因此依據(jù)模擬退火的思想，提出自適應(yīng)的交叉概率和變異概率，這樣不但可以保證種群的多用性，還能提高算法的收斂速度：

式中：K為遺傳總代數(shù)，k為當(dāng)前的遺傳代數(shù)，λ1和λ2分別為交叉概率和變異概率系數(shù)。

模擬退火遺傳算法步驟如下：

1）設(shè)置種群規(guī)模N，退火初始溫度t0，溫度冷卻參數(shù)α，交叉概率和變異概率系數(shù)λ1和λ2。

2）確定初始種群。在遺傳算法中，通常在解空間中隨機(jī)地生成N個(gè)個(gè)體作為初試種群。為了保證初始種群的質(zhì)量，不失種群的多樣性，本文選擇傳統(tǒng)檢測(cè)器的輸出作為初始種群的一個(gè)個(gè)體，再隨機(jī)產(chǎn)生其他個(gè)體。

3）對(duì)當(dāng)前種群實(shí)施如下操作，直至產(chǎn)生新的群體：

①計(jì)算種群中所有個(gè)體的適應(yīng)度函數(shù)值f（xi），i＝1，2，…，N；

②隨機(jī)選取2個(gè)個(gè)體xi和xj進(jìn)行交叉，按照式（6）的交叉概率進(jìn)行交叉，產(chǎn)生2個(gè)新個(gè)體分別計(jì)算它們的適應(yīng)度函數(shù)值，按照模擬退火的接受概率

“適時(shí)修憲”包括兩層涵義：第一，需要修憲則修憲，不需要修憲則不修憲。第二，修憲要選擇適當(dāng)時(shí)機(jī)，既不能早，也不能晚。修憲是最直接有效的憲法適應(yīng)機(jī)制，尤其1982年憲法頒布之后，每次修憲都為憲法注入了新的活力，但一直以來我國(guó)修憲頻率較高，即使秉承“能改能不改的不改”的原則，而由于其他適應(yīng)機(jī)制缺位，修憲一直占據(jù)主導(dǎo)地位。除此之外，1982年修憲之后的歷次修憲多為事后的合法性確認(rèn)，未能及時(shí)為改革提供憲法依據(jù)。

判斷是否接受新解；

③按照式（7）對(duì)交叉后的個(gè)體進(jìn)行變異操作，判斷是否接受新解，方法同上。

4）判斷是否滿足收斂條件若滿足則結(jié)束，否則tk+1＝αtk并轉(zhuǎn)第3）步繼續(xù)執(zhí)行。

3.2 基于模擬退火遺傳算法的多用戶檢測(cè)

基于以上討論，本節(jié)以獲得性能較好、復(fù)雜度較低的多用戶檢測(cè)方法為目標(biāo)，結(jié)合CDMA通信的實(shí)際特點(diǎn)，針對(duì)CDMA的多用戶檢測(cè)問題，在遺傳算法中引入模擬退火算法的思想，通過模擬退火算法來減輕遺傳算法的選擇壓力，并設(shè)計(jì)了自適應(yīng)交叉概率和變異概率，不僅增強(qiáng)了遺傳算法的全局收斂性，而且使算法有較強(qiáng)的爬山性，加快了進(jìn)化后期的收斂速度。圖1為基于模擬退火遺傳算法的多用戶檢測(cè)框圖。

圖1 基于模擬退火遺傳算法的多用戶檢測(cè)框圖Fig.1 MUD diagram based on SAGA

3.3 基于模擬退火遺傳禁忌搜索算法的多用戶檢測(cè)

禁忌搜索算法的實(shí)現(xiàn)效果取決于一些技術(shù)問題的確定，如初始值和鄰域的選擇、禁忌長(zhǎng)度的確定等。在多用戶檢測(cè)中，解都是由+1和-1組成的向量，因此可以采用漢明距來度量向量之間的距離，文獻(xiàn)［10］指出，在多用戶檢測(cè)問題中，以漢明距離為1產(chǎn)生的當(dāng)前解的鄰域的方法最有效，故本文選擇與解b?漢明距離為1的所有碼組集合作為b?的鄰域，即

式中，dH為漢明距離。這樣產(chǎn)生的鄰域大小與用戶數(shù)相等。

禁忌搜索對(duì)初始值的依賴很強(qiáng)，一個(gè)好的初始值可以提升算法的性能，因此，本節(jié)將模擬退火遺傳算法的輸入作為禁忌搜索的初值，提出模擬退火遺傳禁忌搜索（simulated annealing genetic algorithm in Tabu search，SAGATS）算法，使具有較強(qiáng)爬山能力的禁忌搜索（Tabu search，TS）在解空間中能夠搜索到較好的解，同時(shí)提高了算法的收斂速度。

SAGATS的算法操作與參數(shù)設(shè)計(jì)如下：

1）編碼。在多用戶檢測(cè)中，檢測(cè)器的判決輸出是雙極性信號(hào)，故不需要編碼。

2）生成初始種群。

3）評(píng)價(jià)適應(yīng)度函數(shù)值。為了保證適應(yīng)度值非負(fù)，令適應(yīng)度函數(shù)為

式中：Z表示一個(gè)足夠大的正數(shù)，C（b）＝2bTAybTHb，Cw表示當(dāng)代種群中最差的目標(biāo)函數(shù)值。

4）交叉操作。采用式（4）進(jìn)行交叉，λ1選取一個(gè)較大的值（如0.9），按照模擬退火的接受概率判斷是否接受新解。

5）變異操作。采用式（5）進(jìn)行變異，λ2不宜過大（如0.5），同樣按接受概率進(jìn)行判斷。

6）判斷是否達(dá)到收斂條件，如果達(dá)到就將搜索結(jié)果作為TS的初始解并執(zhí)行下一步，否則返回步驟（3）執(zhí)行。

7）確定當(dāng)前解的鄰域，取與當(dāng)前解漢明距為1的向量作為鄰域。

8）求評(píng)價(jià)函數(shù)值

對(duì)當(dāng)前鄰域中解的適應(yīng)度函數(shù)值進(jìn)行比較，取值最大的解向量作為迭代的最優(yōu)解和下一次迭代的當(dāng)前解。

9）將搜索過的解存入禁忌表中。

10）判斷是否滿足終止條件，若滿足，則輸出最優(yōu)解，否則返回步驟7）執(zhí)行。

4 SAGATS算法仿真

對(duì)最優(yōu)多用戶檢測(cè) （OMD）、傳統(tǒng)多用戶檢測(cè)（CD）、基于遺傳算法的多用戶檢測(cè) （GA）、基于模擬退火遺傳算法的多用戶檢測(cè) （SAGA）、基于禁忌模擬退火的多用戶檢測(cè) （TSAGA）進(jìn)行性能仿真比較。考慮一個(gè)具有10個(gè)用戶的CDMA通信系統(tǒng)，擴(kuò)頻序列采用31位的Gold碼序列，最大歸一化互相關(guān)系數(shù)為9／31。為了便于比較，GA、SAGA和SAGATS的種群數(shù)都設(shè)為30，GA中交叉概率和變異概率分別為Pc＝0.95，Pm＝0.05，SAGA和SAGATS中令t0＝999，α＝0.9，λ1＝0.9，λ2＝0.5。

1）誤碼率分析。圖2給出了信噪比為1～8 dB情況下，OMD、CD、GA、SAGA和SAGATS的誤碼率曲線。由圖可知，傳統(tǒng)檢測(cè)器的誤碼率隨信噪比的增加下降的最慢，其誤碼率性能最差；GA和SAGA的誤碼率性能雖然有所改進(jìn)，但與最優(yōu)多用戶檢測(cè)方法相比還有一定的距離；而本文提出的SAGATS的誤碼率接近OMD，優(yōu)于其他4種方法。

2）抗遠(yuǎn)近效應(yīng)分析。用戶1為期望用戶，其信噪比為5 dB，其余9個(gè)用戶為干擾用戶。由圖3可知，隨著干擾用戶功率的增加，SAGA和SAGATS的抗遠(yuǎn)近效應(yīng)性能優(yōu)于CD和GA。

3）收斂性能分析。信噪比Eb／N0＝5 dB。圖4給出了GA、SAGA和SAGATS的誤碼率和迭代次數(shù)的關(guān)系。由圖可見，SAGATS的收斂速度比GA和SAGA快，與理論分析一致；由于采用了模擬退火思想，SAGA以一定概率接受較差的解，因此當(dāng)?shù)螖?shù)較少時(shí)，其收斂性能不如GA。

圖2 誤碼率與信噪比關(guān)系曲線Fig.2 BER versus SNR of TSAGA and some previous detectors

圖3 抗遠(yuǎn)近效應(yīng)Fig.3 BER versus Ei／E1of five detecors

圖4 收斂性能曲線Fig.4 BER comparison of three detectors

5 結(jié)論

本文得出結(jié)論如下：

1）SAGATS的誤碼率低于CD、GA和SAGA；

2）隨著干擾用戶功率的增加，SAGA和SAGATS的抗遠(yuǎn)近效應(yīng)性能優(yōu)于CD和GA；

3）SAGATS的收斂速度比GA和SAGA快。

［1］VERDU S.Minimum probability of error for asynchronous Gaussian multiple-access channels［J］.IEEE Trans Inform Theory，1986，32（1）：85-96.

［2］VERDU S.Optimum multi-user asymptotic efficiency［J］.IEEE Trans Commun，1987，34：890-897.

［3］ZHOU Yue，WANG Hong，WEI Yingzi.Simulated annealing-genetic algorithm and its application in CDMA multi-user detection［C］／／2010 3rd International Conference on Intelligent Networks and Intelligent Systems（ICINIS）.Shenyang，China，2010：638-640.

［4］YAMINDI J B，WU Muqing.The genetic algorithm in the minimum bit error rate multi-user detection assisted space division multiple access system［C］／／2011 International Conference on Internet Computing＆ Information Services（ICICIS）.Ningbo，China，2011：111-114.

［5］王鴻斌，張立毅.基于遺傳算法優(yōu)化神經(jīng)網(wǎng)絡(luò)的多用戶檢測(cè)［J］.計(jì)算機(jī)工程，2011（7）：207-209.

WANG Hongbin，ZHANG Liyi.Multi-user detection based on genetic algorithm optimization neural network［J］.Computer Engineering，2011（7）：207-209.

［6］王彥，王超，劉宏立.模擬退火遺傳算法在多用戶檢測(cè)技術(shù)中的應(yīng)用［J］.通信與網(wǎng)絡(luò)，2011（4）：102-105.

WANG Yan，WANG Chao，LIU Hongli.Application of simulated annealing genetic algorithm in multiuser detection technique［J］.Communication and Network，2011（4）：102-105.

［7］常禹.基于混合遺傳算法的多用戶檢測(cè)技術(shù)研究［D］.南京：南京理工大學(xué)，2009：42-44.

CHANG Yu.The multi-user detection technology based on hybrid genetic altorithm［D］.Nanjing：Nanjing University of Science and Technology，2009：42-44.

［8］廖永忠，姚暢.一種基于改進(jìn)自適應(yīng)遺傳算法的多用戶檢測(cè)器［J］.計(jì)算機(jī)工程與應(yīng)用，2009（3）：127-129.

LIAO Yongzhong，YAO Chang.Multi-user detector based on improved adaptive genetic algorithms and decorrelation algorithm［J］.Computer Engineering and Applications，2009（3）：127-129.

［9］劉巧紅.基于模擬退火遺傳算法對(duì)多用戶檢測(cè)仿真［J］.計(jì)算機(jī)仿真，2011（5）：118-121.

LIU Qiaohong.Multiuser detection based on genetic algorithm and simulated annealing algorithm［J］.Computer Simulation，2011（5）：118-121.

［10］TAN P H，RASMUSSEN L K.Multiuser detection in CDMA-a comparison of relaxations，exact and heuristic search methods［J］.IEEE Transactions on Wireless Communications，2004，3（5）：1802-1809.

Multi-user detection based on the simulated annealing genetic Tabu search

DIAO Ming，ZOU Li

（College of Information and Communication Engineering，Harbin Engineering University，Harbin 150001，China）

In order to design a quasi-optimal multi-use detector with low complexity and for being able to solve the local convergent problem，a hybrid approach named the simulated genetic Tabu search algorithm is proposed，which employs a genetic algorithm（GA），simulated annealing（SA）and a Tabu search（TS）for multi-user detection problems in the code-division multiple-access（CDMA）communications system.Using this approach，the GA and SA were used to provide a good initial value for the Tabu search.Additionally，the SA idea was applied to the GA to design the self-adaptation crossover probability and mutation probability.The results show that the new detector can avoid local optimization and is convergent to the feasible globally optimal solution gradually，using the algorithm we proposed.

code-division multiple-access；multi-user detection；genetic algorithm；Tabu search；simulated annealing algorithm

10.3969／j.issn.1006-7043.201212073

TN911.7

A

1006-7043（2014）03-0373-05

http：／／www.cnki.net／kcms／detail／23.1390.U.20140108.0934.001.html

2012-12-18. 網(wǎng)絡(luò)出版時(shí)間：2014-1-8 9：34：00.

刁鳴（1960-），男，教授，博士生導(dǎo)師.

刁鳴，E-mail：diaoming＠hrbeu.edu.cn.