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

MC-CDMA集OFDM和CDMA的优点于一体，具有很大应用潜力。但该系统存在严重的多址干扰，这不仅严重影响了系统的抗干扰性，也严重限制了系统容量的提高[1]。多用户检测技术是消除多址干扰的有效手段，但其算法复杂度较高，建设成本较大，尤其是检测性能最好的最佳多用户检测技术，其算法复杂度随用户数目成指数增长，不适合实际应用[2-3]。
遗传算法是一种通用的求解最优化问题的智能算法[4]。它的计算性能好，运算量较小。考虑到最佳多用户检测是求二次整数非线性优化问题的全局最优解，因此将解决优化问题的遗传算法应用于最佳多用户检测技术中是行之有效的。
基本遗传算法存在局部搜索能力较弱和收敛速度较慢等问题[5]。模拟退火法是一种模拟高温金属降温的热力学过程的随机组合优化方法。在初始温度足够高、温度下降足够慢的条件下，能以概率1向全局最优值收敛[6-7]。若将模拟退火应用于遗传算法中，便能克服遗传算法易陷入局部极小点的缺点，使得搜索沿着全局最优化方向发展。本文研究模拟退火遗传算法在MC-CDMA系统多用户检测技术中的应用，利用其求解NP（Non-deterministic Polynomial）完备问题。
1 模拟退火遗传算法
1.1 遗传算法
遗传算法(GA)是基于生物自然选择和遗传学原理的一种自适应启发式、概率性迭代式的全局搜索算法，其主要借用了生物进化中“适者生存”和“优胜劣汰”的规律。它利用简单的编码技术和繁殖机制来表现复杂的现象,以编码空间代替问题的参数空间,以适应度函数为评价依据、以编码群体为进化基础,以对群体中个体位串的遗传操作实现选择和遗传机制，建立迭代过程。在这一过程中，通过随机重组编码位串中的优秀基因，使子代群体优于父代群体，群体个体不断进化，逐渐接近最优解，最终实现问题求解。它模拟自然界中的生命进化机制，在人工系统中实现特定目标的优化。实践证明，遗传算法对于NP问题非常有效[8]，但是它容易陷入局部最优，即全局搜索能力弱。
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根据模拟退火思想按照如下公式进行自适应调整：