基于模拟退火的DNA遗传优化小波多模盲均衡算法

张冰龙，徐建敏，江　浩

(1.中国电子科技集团公司第三十六研究所，浙江 嘉兴314033；2.东南大学 信息科学与工程学院，江苏 南京 211189)

基于模拟退火的DNA遗传优化小波多模盲均衡算法

张冰龙1，徐建敏1，江浩2

(1.中国电子科技集团公司第三十六研究所，浙江 嘉兴314033；2.东南大学 信息科学与工程学院，江苏 南京 211189)

针对小波多模盲均衡算法收敛速度慢、稳态误差大、容易陷入局部最优解的缺点，提出一种基于模拟退火的DNA遗传优化小波多模盲均衡算法。该算法将模拟退火算法与DNA遗传算法相结合，利用模拟退火算法对个体的退火操作，提高了DNA遗传算法的局部搜索能力。同时，在DNA遗传算法中采用自适应变异概率，进一步改善了算法的性能。根据盲均衡算法的特点，将基于模拟退火的DNA遗传算法融入到小波多模盲均衡算法中，对均衡器权向量进行了优化。仿真结果表明，与多模盲均衡算法和小波多模盲均衡算法相比，该算法在收敛速度和均方误差方面都有显著改善。

多模盲均衡；DNA遗传算法；模拟退火；收敛速度；均方误差

0　引言

在无线通信中，由于无线电波的多径传播而引起的码间干扰严重影响通信质量，因此在接收端需要克服这些因素所带来的影响。盲均衡技术由于具有性能较好的信号恢复能力，因此被广泛应用在通信信号处理领域。在盲均衡算法中，常模盲均衡算法(Constant Modulus blind equalization Algorithm，CMA)主要适应于低阶调制信号，但对于高阶调制信号，常模盲均衡算法的均衡效果比较差，容易产生较大的误差，而多模盲均衡算法(MMA)利用了均衡器输出信号的幅度和相位信息，有效克服了CMA单一判决圆造成的误差[1]。

DNA遗传算法是在传统的遗传算法基础上发展而来的，与传统的遗传算法不同，DNA遗传算法采用了组成DNA序列的四种碱基分子进行编码，从而提高了算法的编码精度[2-3]。由于 DNA遗传算法独特的编码特性，因此便于模拟自然界生物遗传进化进程，设计出更加贴近实际的操作算子。DNA遗传算法不仅继承了传统遗传算法具有很强鲁棒性的特点，而且还具有比传统遗传算法更有效的搜索性能[4-5]。模拟退火算法(Simulated Annealing Algorithm，SAA)是基于金属退火的机理而建立起来的一种随机算法，它能够通过控制温度的变化过程来实现大范围的粗略搜索和局部的精细搜索[6-7]。由于DNA遗传算法具有很强的全局搜索能力，因此将DNA遗传算法与模拟退火算法相结合，能够获得全局搜索能力和局部搜索能力都较强的新算法。

本文将基于模拟退火的DNA遗传算法与小波多模盲均衡算法相结合，提出了一种基于模拟退火的DNA遗传优化小波多模盲均衡算法(SADNAGA-WTMMA)，该算法通过对小波多模盲均衡算法的代价函数进行优化来获得盲均衡算法均衡器权向量的最优解。与多模盲均衡算法、正交小波多模盲均衡算法(WTMMA)和基于DNA遗传优化的小波多模盲均衡算法(DNAGA-WTMMA)相比，该算法在收敛速度和均方误差方面都有显著改善。

1　WTMMA算法

图1中，a(k)=ar(k)+jai(k)是复信源发射信号，h(k)是信道脉冲响应向量，y(k)=yr(k)+jyi(k)是均衡器输入复信号，Rr(k)和 Ri(k)分别是 yr(k)和 yi(k)经过正交小波变换后的信号，n(k)是噪声干扰信号。w(k)=[wr0(k)+jwi0(k)，…，wrL(k)+jwiL(k)]T(T表示转置)是均衡器权向量，z(k)=zr(k)+ jzi(k)是均衡器的输出信号。

图1　小波多模盲均衡算法原理框图

式中，β为平滑因子，且0＜β＜1。以上各式构成了小波多模盲均衡算法(WTMMA)[8]。

2　基于模拟退火算法的DNA遗传算法

2.1基于模拟退火算法的DNA遗传算法操作算子

2.1.1DNA编码

DNA编码是将变量用A、T、C、G四种碱基表示的过程。首先建立碱基与数字的映射关系，例如A/0、T/1、C/2、G/3映射，然后变量表示成由0、1、2、3这四个数字表示的四进制序列，这样就建立了变量与碱基序列的映射关系。

2.1.2DNA遗传算法交叉算子

在交叉操作中包含三种类型的交叉算子，分别为置换交叉算子、转位交叉算子和重构交叉算子。

（1）置换交叉算子

置换交叉操作是最常见的一种交叉操作方式。该操作将两个父体的等位基因片段相互交换，从而得到新个体。

（2）转位交叉算子

转位交叉操作是对一个个体进行操作的。首先选择一个个体作为父体，然后在该父体序列中选取一段碱基片段并将其剪切下来插入自身序列中的某一位置，生成新个体。

（3）重构交叉算子

首先在种群中选取两个父体A和B，然后在父体A的末端剪切一段序列粘贴到父体B的首部，并将父体B尾部多余的碱基序列切除，同时随机生成一段与被切除序列等长度的碱基片段粘贴到父体A的首部，即可获得两个新个体。

2.1.3自适应变异概率

为了提高DNA遗传算法的收敛速度并实现对最优解的全局搜索，本文采用随进化代数变化的动态变异概率。将种群中的个体DNA序列的前半段定义为高位部分，后半段定义为低位部分。高位部分和低位部分的变异概率分别如下所示：

式中，pmh和 pml分别代表高位部分和低位部分的变异概率，g表示当前的进化代数。

2.2模拟退火算法

模拟退火算法是一种基于物理中固体物质退火机理的随机搜索算法，通过控制温度的变化过程进行搜索，局部搜索能力强[9]。假设时刻 t的温度为 T(t)，则模拟退火算法的降温公式为：

式中，T0表示初始设定温度，k表示温度下降系数。

在SA的搜索过程中，新解的产生是发生在当前解的邻域内，采用如下公式进行解变换：

式中，XL和XR分别为变量X左右边界的值，ε为(0，1)之间的随机数，U(0，1)表示随机选取 0或 1，δ(Ti)为扰动量，随 Ti的减小而减小。Ti为 T0时，δ(Ti)≤1，保证新的个体 X′不会超出边界，且当 i→G时，δ(Ti)→0，满足算法收敛的条件。

通过Meteopolis准则来确定由X变为X′的接受概率为：

式中，fk+1为新解的适应度，fk为原解的适应度。根据Meteopolis准则，当新解优于原解时，接受新解作为当前解；否则，以概率p接受其为当前解。

3　SADNAGA-WTMMA操作步骤

3.1确定适应度函数

为了获得代价函数的最小值，定义适应度函数为：

式中，b＞0。

3.2算法步骤

步骤1：根据编码规则设计初始种群 Chrom=[w1，w2，…，wM]，M为种群个体数量，wm(1≤m≤M)对应一组均衡器权向量。计算每个个体的适应度值，根据个体适应度值的大小将种群分位优质种群和劣质种群，同时保留优质种群中个体适应度值最大的个体作为精英个体。

步骤2：在优质种群中执行交叉操作。对被选中的个体分别执行置换交叉和转位交叉操作。如果以上两种交叉操作均为执行，则执行重构交叉操作。重复执行以上交叉操作直到产生M/2新个体，然后将这些新个体和父代种群个体一起组成混合种群。

步骤3：在混合种群中分别对每个个体执行自适应变异操作。变异操作完成后，执行联赛选择操作，挑选出M-1个新个体，然后将这些新个体与精英个体一起组成种群规模为M的新种群，进化代数加1，并且计算每个种群个体的适应度值。

步骤4：对种群个体进行模拟退火操作。设置退火算法计数器 t以及最大退火代数 tmax，对种群中每个个体进行模拟退火操作。分别按式(9)的新解变换规则将原解变换为新解，然后根据式(10)计算出新解的接受概率。根据 Meteopolis准则，式(10)的结果用来判断是否接受新解为当前解，如果接受，则 t=t+1，否则，t不变。如果 t＜tmax，则对个体继续进行模拟退火操作，否则，返回步骤(1)。

步骤 5：如果当前进化代数 g＜Gmax，则继续对个体进行模拟退火操作，g=g+1；否则，结束整个优化过程，输出适应度值最大的个体作为最优个体。

4　仿真结果

本文以MMA、WTMMA和DNAGA-WTMMA为比较对象，进行仿真实验。仿真试验中，信道h(k)=[0.313 2，-0.104 0，0.890 8，0.313 4]，信噪比为20 dB，均衡器权长为16，采用64QAM信号作为发射信号，SADNAGA-WTMMA的种群规模为60，最大进化为100代，置换交叉操作、转位交叉操作和重构交叉操作的执行概率分别为 pc1=0.8，pc2=0.5，pr=0.2。模拟退火算法的初始温度T0=100，温度下降系数k=0.95，最大退火代数 tmax=10。各个算法的步长为：μMMA=0.6×10-5，μWTMMA=1×10-5，μDNAGA-WTMMA=1.5×10-6，μSADNAGA-WTMMA=2×10-6。

实验采用500次蒙特卡洛仿真。仿真结果如图2所示。图2表明，与MMA、WTMMA和DNAGA-QTMMA相比，在稳态误差方面，SADNAGA-WTMMA比MMA低2.5 dB，比WTMMA低1.8 dB，比DNAGA-WTMMA低0.8 dB。在收敛速度方面，SADNAGA-WTMMA收敛速度最快。图3表明，SADNAGA-WTMMA输出的64QAM星座图比另外三种算法输出的星座图更加清晰。

图2　均方误差曲线

5　结论

本文提出了一种基于模拟退火的DNA遗传优化小波多模盲均衡算法。将模拟退火算法应用到DNA遗传算法中，提高了DNA遗传算法的搜索效率并且有效避免了局部收敛。仿真结果表明，与MMA、WTMMA和DNAGA-WTMMA相比，该算法在收敛速度和均方误差方面都得到了提高，因此更适合用于通信系统中的信号处理。

[1]郭业才.自适应盲均衡技术[M].合肥：合肥工业大学出版社，2007：17-25.

图3　输出星座图

[2]FAGHIHI V，REINSCHMIDT K F，KANG J H.Construction scheduling using genetic algorithm based on building information model[J].Expert Systems With Applications，2014，41(16)：7565-7578.

[3]CHEN X，WANG N.A DNA based genetic algorithm for parameter estimation in the hydrogenation reaction.Chemical Engineering Journal，2009，150(2)：527-535.

[4]LI Y J，LEI J.A feasible solution to the beam-angleoptimization problem in radiotherapy planning with a DNA-based genetic algorithm[J].IEEE Transactions on biomedical engineering，2010，57(3)：499-508.

[5]郭业才，张冰龙，吴彬彬.基于DNA遗传优化的正交小波常模盲均衡算法[J].数据采集与处理，2014，29(3)：366-371.

[6]贺小亮，毕义明.基于模拟退火遗传算法的编队对地攻击火力分配建模与优化[J].系统工程与电子技术，2014，36(5)：900-904.

[7]JIANG J C，LIU H R，FENG H Z，et al.Embedded static task allocation and scheduling base on simulated annealing and genetic algorithm[J].Journal of Computational Information Systems，2014，10(4)：1465-1472.

[8]郭业才，胡苓苓，丁锐.基于量子粒子群优化的正交小波加权多模盲均衡算法[J].物理学报，2012，61(5).

[9]张昊，陶然，李志勇，等.基于自适应模拟退火遗传算法的特征选择方法[J].兵工学报，2009，30(1)：81-85.

An orthogonal wavelet transform multi-modulus blind equalization algorithm based on simulated annealing DNA genetic algorithm

Zhang Binglong1，Xu Jianmin1，Jiang Hao2
(1.No.36 Research Institute of CETC，Jiaxing 314033，China；2.School of Information Science and Engineering，Southeast University，Nanjing 211189，China)

For the disadvantages of orthogonal wavelet transform multi-modulus blind equalization algorithm(WTMMA),such as slow convergence rate,large mean square error,and immerging in partial minimum easily,a WTMMA based on simulated annealing DNA genetic algorithm(DNAGA-WTMMA)was proposed.The algorithm combines simulated annealing algorithm with DNA genetic algorithm to improve the ability of local search of DNA genetic algorithm by using annealing operation of SAA for individual.Meanwhile,adaptive mutation probability was used in DNA genetic algorithm to improve the performance of the algorithm.According to the characteristics of blind equalization algorithm,SADNAGA was applied to WTMMA to optimize the equalizer weight vector.Computer simulations show that,compared with multi-modulus blind equalization algorithm(MMA)and WTMMA,the proposed algorithm was improved in convergence rate and mean square error significantly.

WTMMA；DNA genetic algorithm；simulated annealing；convergence rate；mean square error

TN911.7

A

10.16157/j.issn.0258-7998.2016.02.024

2015-11-13)(

2015-11-05)

张冰龙(1989-)，通信作者，男，硕士，助理工程师，主要研究方向：通信信号处理技术，Email：zhang-nuist@foxmail. com。

徐建敏(1982-)，男，硕士，工程师，主要研究方向：通信信号处理技术。

江浩(1989-)，男，博士研究生，主要研究方向：无线通信技术。

中文引用格式：张冰龙，徐建敏，江浩.基于模拟退火的 DNA遗传优化小波多模盲均衡算法[J].电子技术应用，2016，42 (2)：88-91.

英文引用格式：Zhang Binglong，Xu Jianmin，Jiang Hao.An orthogonal wavelet transform multi-modulus blind equalization algorithm based on simulated annealing DNA genetic algorithm[J].Application of Electronic Technique，2016，42(2)：88-91.