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

刁 鳴，鄒 麗

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

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

刁 鳴，鄒 麗

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

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

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

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

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

1 多用戶檢測模型

在直接擴頻序列DS-CDMA通信系統中，每個用戶對應的特征波形對用戶傳遞信號擴頻后迭加再加上信道噪聲就得到了接收信號，接收信號的數學模型可以表示為

傳統多用戶檢測器是將接收到的信號分別通過具有K個匹配濾波器的濾波器組：

然后進行門限判決：

最優多用戶檢測器可以表示為

式中：H∈RK×K，H中元素為取遍共2（2M+1）K個所有可能的組合后必能找到這個使函數最大的值作為檢測的結果，顯然這種方法的計算復雜度與用戶數成指數關系增長。

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

2.1 遺傳算法

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

2.2 模擬退火算法

模擬退火算法是模擬物理熱力學中固體退火原理來尋找最優解的隨機搜索方法。當新解更優時，則接受新解為當前解；而當新解的質量沒有提高時，以一定的概率接受這個較差的新解為當前解［6］。接受概率可由Metropolis準則來確定：

式中：fk+1是新解的適應度函數值，fk是當前解的適應度函數值，P（tk+1）是在溫度為tk+1條件下的接受概率。

2.3 禁忌搜索

禁忌搜索算法是一種亞啟發式隨機搜索算法，通過引入一個靈活的存儲結構和相應的禁忌規則來進行搜索，從而實現全局優化。為了避免陷入局部最優，禁忌搜索中采用了一種靈活的記憶技術，對已經進行的優化過程進行記錄和選擇，指導下一步的搜索方向，這就是Tabu表的建立。

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

3.1 模擬退火遺傳算法

考慮到遺傳算法結構上的特點及其并行性，可以很容易地將遺傳算法和其他算法結合起來，從而更好地發揮算法的優勢［7-9］。從以上的論述中可以看到，如果將遺傳算法的全局搜索功能和模擬退火的局部搜索功能相互結合，將會達到更好的搜索效果。

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

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

1）在交叉和變異操作中引入模擬退火思想，適當允許適應度高的少量父代和子代共同競爭；

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

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

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

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

2）確定初始種群。在遺傳算法中，通常在解空間中隨機地生成N個個體作為初試種群。為了保證初始種群的質量，不失種群的多樣性，本文選擇傳統檢測器的輸出作為初始種群的一個個體，再隨機產生其他個體。

3）對當前種群實施如下操作，直至產生新的群體：

①計算種群中所有個體的適應度函數值f（xi），i＝1，2，…，N；

②隨機選取2個個體xi和xj進行交叉，按照式（6）的交叉概率進行交叉，產生2個新個體分別計算它們的適應度函數值，按照模擬退火的接受概率

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

判斷是否接受新解；

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

4）判斷是否滿足收斂條件若滿足則結束，否則tk+1＝αtk并轉第3）步繼續執行。

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

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

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

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

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

式中，dH為漢明距離。這樣產生的鄰域大小與用戶數相等。

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

SAGATS的算法操作與參數設計如下：

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

2）生成初始種群。

3）評價適應度函數值。為了保證適應度值非負，令適應度函數為

式中：Z表示一個足夠大的正數，C（b）＝2bTAybTHb，Cw表示當代種群中最差的目標函數值。

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

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

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

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

8）求評價函數值

對當前鄰域中解的適應度函數值進行比較，取值最大的解向量作為迭代的最優解和下一次迭代的當前解。

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

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

4 SAGATS算法仿真

對最優多用戶檢測 （OMD）、傳統多用戶檢測（CD）、基于遺傳算法的多用戶檢測 （GA）、基于模擬退火遺傳算法的多用戶檢測 （SAGA）、基于禁忌模擬退火的多用戶檢測 （TSAGA）進行性能仿真比較。考慮一個具有10個用戶的CDMA通信系統，擴頻序列采用31位的Gold碼序列，最大歸一化互相關系數為9／31。為了便于比較，GA、SAGA和SAGATS的種群數都設為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的誤碼率曲線。由圖可知，傳統檢測器的誤碼率隨信噪比的增加下降的最慢，其誤碼率性能最差；GA和SAGA的誤碼率性能雖然有所改進，但與最優多用戶檢測方法相比還有一定的距離；而本文提出的SAGATS的誤碼率接近OMD，優于其他4種方法。

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

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

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

圖3 抗遠近效應Fig.3 BER versus Ei／E1of five detecors

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

5 結論

本文得出結論如下：

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

2）隨著干擾用戶功率的增加，SAGA和SAGATS的抗遠近效應性能優于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］王鴻斌，張立毅.基于遺傳算法優化神經網絡的多用戶檢測［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］王彥，王超，劉宏立.模擬退火遺傳算法在多用戶檢測技術中的應用［J］.通信與網絡，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］常禹.基于混合遺傳算法的多用戶檢測技術研究［D］.南京：南京理工大學，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］.計算機工程與應用，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］劉巧紅.基于模擬退火遺傳算法對多用戶檢測仿真［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. 網絡出版時間：2014-1-8 9：34：00.

刁鳴（1960-），男，教授，博士生導師.

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