基于模拟退火遗传算法解决MC-CDMA系统NP完备问题

MC-CDMA集OFDM和CDMA的优点于一体，具有很大应用潜力。但该系统存在严重的多址干扰，这不仅严重影响了系统的抗干扰性，也严重限制了系统容量的提高。多用户检测技术是消除多址干扰的有效手段，但其算法复杂度较高，建设成本较大，尤其是检测性能最好的最佳多用户检测技术，其算法复杂度随用户数目成指数增长，不适合实际应用。

遗传算法是一种通用的求解最优化问题的智能算法。它的计算性能好，运算量较小。考虑到最佳多用户检测是求二次整数非线性优化问题的全局最优解，因此将解决优化问题的遗传算法应用于最佳多用户检测技术中是行之有效的。

基本遗传算法存在局部搜索能力较弱和收敛速度较慢等问题。模拟退火法是一种模拟高温金属降温的热力学过程的随机组合优化方法。在初始温度足够高、温度下降足够慢的条件下，能以概率1向全局最优值收敛。若将模拟退火应用于遗传算法中，便能克服遗传算法易陷入局部极小点的缺点，使得搜索沿着全局最优化方向发展。本文研究模拟退火遗传算法在MC-CDMA系统多用户检测技术中的应用，利用其求解NP（Non-determinisTIc Polynomial）完备问题。

1 模拟退火遗传算法

1.1 遗传算法

遗传算法（GA）是基于生物自然选择和遗传学原理的一种自适应启发式、概率性迭代式的全局搜索算法，其主要借用了生物进化中“适者生存”和“优胜劣汰”的规律。它利用简单的编码技术和繁殖机制来表现复杂的现象，以编码空间代替问题的参数空间，以适应度函数为评价依据、以编码群体为进化基础，以对群体中个体位串的遗传 *** 作实现选择和遗传机制，建立迭代过程。在这一过程中，通过随机重组编码位串中的优秀基因，使子代群体优于父代群体，群体个体不断进化，逐渐接近最优解，最终实现问题求解。它模拟自然界中的生命进化机制，在人工系统中实现特定目标的优化。实践证明，遗传算法对于NP问题非常有效，但是它容易陷入局部最优，即全局搜索能力弱。

1.2 模拟退火算法

模拟退火算法（SA）是基于金属退火的机理而建立起来的一种随机算法。它是一种全局最优化方法，能够以随机搜索技术从概率的意义上找出目标函数的全局最小点。在搜索最优解的过程中，模拟退火算法除了接受最优化解外，还用随机接受准则有限地接受恶化解，这使得算法有可能摆脱局部最优，尽可能找到全局最优解，保证算法收敛。它通过控制温度的变化过程来实现大范围的粗略搜索与局部的精细搜索。采用指数降温策略对温度的变化进行控制，即：

使用上述准则的优点是：当新解更优时，完全接受新解的当前解；而当新解为恶化解时，以概率P接受恶化解为新的当前解。这使得SA能够避免陷入局部最优。随着优化的进行，SA的局部搜索能力也逐渐增强，确保算法有足够的搜索精度。

模拟退火算法有可能摆脱局部最优，找到全局最优解，保证算法收敛。但是它只是搜索解空间中的一点且对解空间中已知试探的区域知之甚少，因此难以判断哪些区域有更多的机会找到最优解。所以，其收敛到全局最优解是非常耗时的。

1.3 模拟退火遗传算法

鉴于遗传算法的并行性和它在算法结构上的特点， 可以很容易地将遗传算法和其他算法混合使用， 从而达到扬长避短的作用。从上文的论述中可以看出，若将遗传算法的全局搜索功能和模拟退火的局部搜索功能互相补充，将相得益彰。

本文在遗传算法中融入模拟退火思想，首先，在选择 *** 作中引入退火思想并允许适应度高的少量父代与子代共同竞争；其次，根据模拟退火思想设计出自适应交叉概率和变异概率，从而保证了种群的多样性以及收敛速度。模拟退火遗传算法的流程如下：

（1）初始群体的产生：为了得到理想的初始种群，首先在每个变量的取值范围内均匀产生种群，然后通过设计重组与筛选算子进行重新组合，从而保证其多样性和组合随机性。在经过交叉变异产生的子代中同样采用筛选算子使新一代种群中避免出现大量重复个体，使算法能够趋于收敛。筛选算子流程如图1所示。

（2）退火选择 *** 作：运用适者生存法则，繁殖 *** 作在旧的群体中“随机”选择符号串生成一个新的种群，但选择并非完全随机，它基于一个符号串相对于整个群体的适应度。在常用的轮盘赌选择方法中，个体被选中的概率遵循Montecarlo方法，与其适应度和种群的平均适应度的比值成正比：

其中，{Tk}渐趋于0的退火温度，Tk=1/ln（k/T0+1），T0为起始温度。

（3）自适应度交叉概率和变异概率

GA的交叉概率Pc与变异概率Pm对其性能影响很大，它们的选择直接影响算法的收敛性。在进化初期，为了避免个别适应度高的个体迅速繁殖，出现早熟现象，Pc和Pm不宜过小，以增加种群的多样性；在进化后期，个体接近最优解时，Pc和Pm不宜过大，以避免个体长期无法达到最优解［8］。文中的Pc和Pm根据模拟退火思想按照如下公式进行自适应调整：

其中T′类似于模拟退火中的温度T，为进化代数的倒数；gen为设定的进化总代数。在进化初期T′较高，则Pc和Pm较大，以利于种群的多样性；随着进化代数的增加，T′逐渐减小，Pc和Pm渐进减小，便于个体向最优解靠近。

从上述内容可知，将模拟退火应用于遗传算法中，在优选交叉和变异个体的过程中通过加入一定的“扰动”以达到保持群体中位串多样性和位串之间的竞争机制，从而克服算法易陷入局部极小点的问题，使得搜索沿着全局最优化方向趋进。

2 模拟退火遗传算法在多用户检测技术中的应用

模拟退火算法与遗传算法相结合，取长补短，形成了模拟退火遗传算法。多用户检测是一个NP完备问题，将模拟退火遗传算法用于多用户检测中是可行的。图2为模拟退火遗传算法多用户检测原理框图，由滤波器和多用户检测器两部分组成。它有 k个输入和k个输出。

基于模拟退火遗传算法的多用户检测器以匹配滤波器的输出作为模拟退火遗传算法的初始值，再通过模拟退火遗传算法的启发式搜索，提高多用户检测器的抗多址干扰和抗远近效应能力。同时通过模拟退火算法来减轻遗传算法的选择压力，这样不但可以避免遗传算法的早熟收敛问题，并且使群体中的最优解得到了保留。模拟退火遗传算法多用户检测器的基本 *** 作流程如下：

（1）初始化控制参数。如群体规模N、用户数K、初始温度t0、变化系数？坠、变异概率Pm和交叉概率Pc等。

（2）编码。解向量b是由{-1，1}组成的二进制序列，无需编码。

（3）初始化种群。将经匹配滤波器并经判决后的结果作为初始种群中的一个个体B1送入模拟退火遗传算法多用户检测器，其余N-1个个体均由其随机扰动产生。

（4）适应度函数评价。采用与简单遗传算法多用户检测相同的适应度函数，计算种群中每个个体的适应度函数值f。

（5）交叉。随机选取两个个体Bi和Bj进行交叉，产生新个体Bi′和Bj′，计算f（j）和f（i），并按Metropolis准则计算接收概率，若P=min{1，exp［f（i）-f（j）/tk］}≥random［0，1］，则接收新解，否则保持原状态。

（6）对交叉后的个体进行变异 *** 作，按与（5）中同样的判决方法判断是否接受变异后产生的新个体。

（7）判断是否满足收敛条件。若已经达到预先设定的最大遗传代数，则迭代过程结束，输出最优解；否则有TI+1=？坠TI，？坠《1，并转至（4）进行下一步的迭代寻优工作。

从上述内容可知，与基于复杂矩阵算法的传统多用户检测器相比，基于模拟退火遗传算法的多用户检测器算法降低了难度。

3 仿真研究

利用MATLAB仿真平台将基于模拟退火遗传算法的多用户检测器（SAGA）与传统最佳多用户检测器（OMD）、基于遗传算法的多用户检测器（GA）以及其他典型多用户检测算法进行性能比较，以误码率随信噪比的变化曲线作为比较参数。

仿真环境：上行同步的CDMA系统，采用BPSK调制，使用正交Walsh码作为扩频码，其中码长为16。系统中共有8个用户且信道信息已知，设定信道为2径等增益衰落信道（L=2），每条径的幅度服从瑞利分布，相位服从［0，2π］间的均匀分布，使用理想功率控制。遗传算法中所取各参数值分别为：种群数为10，变异概率为0.9，交叉概率为0.1。

图3比较了各种典型多用户检测算法性能。其中最优多用户检测算法性能最好，但其计算量太大，复杂度高。图4比较了最佳多用户检测器、遗传算法多用户检测器和模拟退火遗传算法检测器的抗干扰性能。结合图3和图4可以看出：本文所采用的基于模拟退火遗传算法的多用户检测器性能优于遗传算法多用户检测器和其他次优多用户检测器，且非常接近最佳多用户检测器。

通过将模拟退火算法融入遗传算法框架中，对基本遗传算法进行改进，即一方面允许父代参与竞争，将父代群体中最优个体和子代群体中最优个体组成新的群体并进行退火选择;另一方面根据模拟退火思想自适应调整Pc和Pm，从而形成SAGA，然后将其应用到多用户检测技术中，有效地解决了移动通信系统中存在的多址干扰等问题。由于其算法性能接近最优多用户检测器，有效地消除了多址干扰，而且算法难度有所降低，很适合在实际系统中的应用。

责任编辑：gt