模拟退火遗传禁忌搜索的多用户检测算法

刁 鸣，邹 丽

（哈尔滨工程大学信息与通信工程学院，黑龙江 哈尔滨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.