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

2011-07-08 15:42:05来源: 互联网

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根据模拟退火思想按照如下公式进行自适应调整:

[1] [2]

关键字:模拟退火遗传算法  多用户检测技术

编辑:什么鱼 引用地址:http://www.eeworld.com.cn/Test_and_measurement/2011/0708/article_2931.html
本网站转载的所有的文章、图片、音频视频文件等资料的版权归版权所有人所有,本站采用的非本站原创文章及图片等内容无法一一联系确认版权者。如果本网所选内容的文章作者及编辑认为其作品不宜公开自由传播,或不应无偿使用,请及时通过电子邮件或电话通知我们,以迅速采取适当措施,避免给双方造成不必要的经济损失。
论坛活动 E手掌握
微信扫一扫加关注
论坛活动 E手掌握
芯片资讯 锐利解读
微信扫一扫加关注
芯片资讯 锐利解读
推荐阅读
全部
模拟退火遗传算法
多用户检测技术

小广播

独家专题更多

TTI携TE传感器样片与你相见,一起传感未来
TTI携TE传感器样片与你相见,一起传感未来
TTI携TE传感器样片与你相见,一起传感未来
富士通铁电随机存储器FRAM主题展馆
富士通铁电随机存储器FRAM主题展馆
馆内包含了 纵览FRAM、独立FRAM存储器专区、FRAM内置LSI专区三大部分内容。 
走,跟Molex一起去看《中国电子消费品趋势》!
走,跟Molex一起去看《中国电子消费品趋势》!
 
电子工程世界版权所有 京ICP证060456号 京ICP备10001474号 电信业务审批[2006]字第258号函 京公海网安备110108001534 Copyright © 2005-2016 EEWORLD.com.cn, Inc. All rights reserved