基于列维飞行复形猴群算法的多模盲均衡算法

高 敏,郭业才

1.中国矿业大学物联网(感知矿山)研究中心，徐州,221008;2.淮南职业技术学院信息与电气工程系，淮南,232001;3.南京信息工程大学江苏省气象探测与信息处理重点实验室，南京,210044

基于列维飞行复形猴群算法的多模盲均衡算法

高 敏1,2,郭业才3*

1.中国矿业大学物联网(感知矿山)研究中心，徐州,221008;2.淮南职业技术学院信息与电气工程系，淮南,232001;3.南京信息工程大学江苏省气象探测与信息处理重点实验室，南京,210044

针对传统多模盲均衡算法(MMA)在最小化代价函数时采用梯度思想而导致的易陷入局部最优、收敛速度慢、收敛后稳态误差大等问题，提出一种基于列维飞行复形猴群算法的多模盲均衡算法。用具有优秀搜索路径的列维飞行模式来确定猴群算法中的爬步长，增强搜索随机性的同时有助于跳出局部最优，将复形法嵌入望跳过程加强局部搜索，提高了猴群算法的搜索效率和优化性能，结合MMA能提高信号均衡质量。仿真实验表明，新算法收敛速度更快，均方误差更低。

多模盲均衡；猴群算法；复形法；列维飞行；全局最优位置；最优权向量

1 相关研究与问题提出

在无线通信系统中，不可避免地存在着由于多径传输等多种因素造成的码间干扰问题，严重影响传输质量。1975年由Sato提出的盲均衡技术为信源的自恢复提供了可能[1]，受其启发，各种盲均衡算法大量涌现[2]。最为经典的常模盲均衡算法(Constant Modulus Algorithm,CMA)因计算量小、易于实现且鲁棒性强而被广泛使用[3-5]。CMA借助梯度思想更新均衡器权向量以最小化高维非凸性的代价函数[6]，最终使均衡器输出的幅值收敛到一个固定的统计模值[7]，这对具有常数模的相移键控(Phase Shift Keying,PSK)信号以及低阶正交振幅调制(Quadrature Amplitude Modulation,QAM)信号有很好的效果，但对高阶QAM和正交相移键控(Amplitude phase shift keying,APSK)信号均衡效果不理想[8]，并且采用梯度思想求解多模态函数易落入局部最优。多模盲均衡算法(Multi-Modulus Algorithm,MMA)将均衡器输入信号的实部和虚部分别进行均衡，同时利用信号的幅值和相位信息，能有效避免相位旋转，可在一定程度上提高均衡质量[9]，但它在最小化代价函数时仍沿用了梯度思想，还是无法有效解决易陷入局部最优的问题，导致收敛速度慢，稳态误差大[10]。

猴群算法(Monkey Algorithm，MA)是模拟自然界中猴群登高爬山行为而设计的一种新型的群智能优化算法[11]，自2008年提出以来已被成功用于求解很多非凸函数优化问题[12-14]。该算法与其他群智能优化算法相比，最大的特点是对优化对象的维数不敏感，不会陷入“维灾难”，所以对高维非凸性函数的优化有很好的效果，但仍存在搜索速度慢、局部精度较低等问题。列维飞行(Levy flight)是法国数学Paul Pierre Levy提出的一种随机游走模式，这种游走模式的特点是在较小的移动之后发生较大的跳跃，自然界中很多动物的行为都具有这一特征，该过程表面看起来杂乱无章，实质却遵循着非常确定的统计分布规律[15]。

本文采用列维飞行模式确定MA中的爬步长，以增加搜索的随机性，提高搜索速度，有效避免落入局部最优，并将传统的复形法嵌入望跳过程，在增强局部搜索能力的同时还引入竞争机制，以保证种群的多样性，将改进后的MA用于最小化MMA的代价函数，捕获均衡器初始权向量，提出基于列维飞行复形猴群算法的多模盲均衡算法(Multi-modulus Blind Equalization Algorithm Based on Levy Flight Complex Method Monkey Algorithm，LF-CM-MA-MMA)。仿真结果表明，本文提出的算法对高阶QAM信号有很好的均衡效果。

2 多模盲均衡算法(MMA)

MMA的原理框图如图1所示。

图1 MMA原理图

图1中，a(k)是发射的信源复信号；h(k)是信号传输信道的脉冲响应向量；n(k)是加性高斯白噪声；y(k)是均衡器输入信号；F(k)是均衡器的权系数向量；z(k)为均衡器的输出复信号；s(k)为判决输出的复信号；g(·)为无记忆非线性函数，需满足s(k)=g[z(k)]=z(k)；下标Re和Im分别代表参数的实部和虚部。

均衡器的输入为：

y(k)=hT(k)a(k)+n(k)

(1a)

y(k)=yRe(k)+j·yIm(k)

(1b)

均衡器的输出为：

z(k)=zRe(k)+j·zIm(k)

(2a)

(2b)

(2c)

MMA代价函数[16]为：

(3)

发射信号同相方向统计模值为:

(4a)

发射信号正交方向统计模值为:

(4b)

MMA误差函数为：

e(k)=eRe(k)+j·eIm(k)

(5a)

(5b)

(5c)

均衡器权向量的迭代公式为：

F(k+1)=F(k)-μe(k)y*(k)

(6)

式中，μ为迭代步长。式(1a)～式(6)构成了MMA算法。方形QAM信号在同相和正交方向的分布是均匀等概率的，此时有RRe=RIm，故MMA和CMA计算复杂度相当，但其代价函数同时包含了幅度信息和相位信息，可有效纠正相位旋转，对非常模信号有很好的均衡能力。MMA的代价函数也是高维非凸性的，采用随机梯度思想更新均衡器权向量，容易落入局部最优，均衡效果有待提高。

2 基于列维飞行复形猴群算法的多模盲均衡算法(LF-CM-MA-MMA)

2.1 猴群算法

基本猴群算法是主要包括5个过程，分别是初始化、确定适应度函数、爬过程、望跳过程和翻跳过程，流程如图2所示。

图2 猴群算法流程图

主要步骤说明如下：

Step1初始化。在一个n维空间，随机产生规模为m的猴群，每只人工猴的初始位置按公式(7)进行随机分配。

xij=xmin,j+(xmax,j-xmin,j)rand

(7)

式中，xij为第i只猴子在第j维的实际位置，xmin,j和xmax,j分别表示搜索空间第j维的下界和上界，rand产生一个在区间[0,1]上的实数。

Step2适应度函数的确定。每只人工猴的位置向量代表了适应度函数的一个潜在解，将位置向量带入适应度函数进行计算，所得值越大意味着位置越好，离最高山峰也越近，猴群算法最终得到的是适应度函数的最大值。如果待优化函数是要获取最小值，只要进行简单的处理即可。比如本文中，需要最小化MMA的代价函数以获取均衡器的初始权向量，则可将均衡器的权向量和人工猴的位置向量设置为相同的形式，两函数互为倒数即可。当MA适应度函数取得最大值时,意味着MMA代价函数取得最小值，这时最大适应度函数值对应的位置向量，即为所求的MMA中均衡器初始权向量。

Step3爬过程。在搜索空间中，对第i只人工猴的当前位置进行随机扰动，生成一个随机向量ΔXi=(Δxi1,Δxi2,…,Δxin)，分量Δxij以相同的概率0.5取爬步长λ(λ>0)或-λ。计算伪梯度信息f＇i(xi)=(f＇i1(xi),f＇i2(xi),…,f＇in(xi))，其中：

(8)

设向量Yi=(yi1,yi2,…,yin)，其中各分量为：

yi=xij+λ·sign(f＇ij(xi))

(9)

若Yi在搜索空间内，则Yi→Xi；否则，保持Xi不变。重复爬过程，直到满足设定条件转入望跳过程。

Step4望跳过程。每只人工猴攀爬一段时间后，会停下来在视野范围(xij-γ,xij+γ)内向四周多次眺望以探索更好位置。每次眺望的结果用Yi=(yi1,yi2,…,yin)表示。若Yi在搜索空间并有f(Yi)>f(Xi)，则Yi→Xi；否则，保持Xi不变。重复多次探寻，每只人工猴都到达各自的最好位置，以此时位置为初始位置重复爬过程，达到设定次数转入翻跳过程。

Step5翻跳过程。这一过程是为避免落入局部最优，迫使猴群找到新的搜索域。在翻区间内随机产生一个实数θ,设Yi=(yi1,yi2,…,yin)，令：

yij=xij+θ·(pj-xij)

(10)

公式(7)～(10)构成了基本猴群算法，式中，i=1,2,…,m;j=1,2,…,n。猴群算法计算量主要集中在爬过程，借助伪梯度信息，不需要考虑适应度函数的维度，但存在搜索速度慢、局部搜索能力不高的缺点。为解决这一问题，本文提出了一种列维飞行复形猴群算法(Levy Flight Complex Method Monkey Algorithm，LF-CM-MA)。

2.2 采用列维飞行的爬步长

猴群在登山爬高过程中，并不会以一个固定步长进行，一般是几小步攀爬后会有一大步跳跃，其特征更符合列维飞行模式，并且这种搜索模式也更为有效[17]。若将猴群算法中原固定的爬步长采用列维飞行模式，则公式(9)改为：

(11)

式中，α为步长控制因子(α>0，具体数值可根据实际情况设置)；⊕为点对点乘法；Levy(β)为随机搜索路径，它移动的步长服从列维分布：

Levy～ε=t-1-β(0<β2)

(12)

2.3 嵌入复形法的望跳过程

图3 LF-CM-MA-MMA流程图

复形法本质上讲是一种局部搜索算法，引入复形思想，不仅增强了局部搜索能力，还引入了一定的竞争机制，保证种群的多样性。在望跳过程后，复形法指导下的位置向量将取代适应度值最差的位置向量，虽然复形法很容易陷入局部最优，但本文中的爬步长采用了列维飞行模式，这种方式能有效跳出局部最优，两者可很好地融合。

具体步骤：在望跳过程后，此时猴群的当前位置作为复形法的初始位置，将其按适应度函数以降序进行排列X1,X2,…,Xm，适应度值最小的为最差点。按下列方式确定一个新点来替换最差点Xm。

(1)计算复形的形心：

(13)

(2)计算复形的反射点：

Xr=Xc+ζ·(Xc-Xm)

(14)

式中，ζ为反射系数。若f(Xr)>f(Xm)，则用Xr替换Xm，执行步骤(3)，否则执行步骤(4)。

(3)延伸操作：

Xe=Xr+τ·(Xr-Xc)

(15)

式中，τ为延伸系数。若f(Xe)>f(Xm)，则用Xe替换Xm，执行步骤(1)，否则执行步骤(4)。

(4)收缩操作：

Xk=Xm-σ·(Xm-Xc)

(16)

图4 512-QAM仿真结果

其中σ为收缩系数。若f(Xk)>f(Xm)，则用Xk替换Xm，执行步骤(1)，满足设定次数结束，否则重新进行排序，重复复形。

2.4 基于列维飞行复形猴群算法的多模盲均衡算法

为提高MMA对高阶QAM的均衡性能，本文将LF-CM-MA和MMA有机结合，提出基于列维飞行复形猴群算法的多模盲均衡算法(Multi-modulus Blind Equalization Algorithm Based on Levy Flight Complex Method Monkey Algorithm,LF-CM-MA-MMA)，均衡器初始权向量的虚部和实部均采用LF-CM-MA搜索到的最佳位置向量，然后再用MMA对信号的实部和虚部分别进行均衡输出。LF-CM-MA-MMA实现流程如3所示。

3 仿真分析

为验证LF-CM-MA-MMA对高阶QAM信号的均衡性能，采用512-QAM信号，并将其与基于小波变换的多模盲均衡算法(WT-MMA)，基于猴群算法的多模盲均衡算法(MA-MMA)，基于列维飞行猴群算法的多模盲均衡算法(LF-MA-MMA)，基于复形法猴群算法的多模盲均算法(CM-MA-MMA)，基于混沌萤火虫算法的多模盲均衡算法[18](CGSO-MMA)为比较对象进行仿真实验，信道采用h=[0.9656,-0.0906,0.0578,0.2368]，高斯白噪声的信噪比40 dB，信号采样点均为15 000点，盲均衡器的权长均为16，猴群规模为100，爬过程、望跳过程、翻跳过程的迭代次数分别设置为100、20、5，视野范围为0.005，反射系数、延伸系数、收缩系数分别为1.1、0.4、0.6，步长控制因子为0.01，WT-MMA中迭代步长为0.000 000 6，MA-MMA、CM-MA-MMA、LF-MA-MMA、CGSO-MMA、LF-CM-MA-MMA中迭代步长均为0.000 000 08。

从图4不难看出，在对512-QAM信号的均衡中，本文算法比WT-MMA收敛快了6 000步，与CGSO-MMA、MA-MMA、LF-MMA、CM-MMA收敛速度几乎一致；稳态误差上，本文算法比WT-MMA低了近5.5 dB，比CGSO-MMA低了近5 dB，比MA-MMA快了低3 dB，比CM-MA-MMA低了近2.5 dB，比LF-MA-MMA低了近1.5 dB；LF-MC-MA-MMA星座图最为清晰、紧凑。

4 结束语

本文提出了基于列为飞行复形猴群算法的多模盲均衡算法，用随机性大但性能稳定的列维飞行模式来设置猴群的攀爬步长，不仅增加了搜索的随机性，还可有效避免落入局部最优。在望跳过程中引入复合形法，适当保持种群多样性的同时引入竞争淘汰机制，加强局部搜索，有效提高了算法的精度和优化效率，与MMA结合，在均衡高阶QAM信号时，收敛速度快且收敛后稳态误差小，与其他同类算法比较，性能更好。

[1]Mikael S,Lienven D L.On Jacobi-type Methods for Blind Equalization of Paraunitary Channels[J].Signal Processing (50165-1684),2012,92(1):617-624

[2]郭业才.自适应盲均衡技术[M].合肥:合肥工业大学出版社,2007:5-8

[3]孙云山.改进恒模盲均衡在医学CT图像盲恢复中的应用[J].仪器仪表学报,2012,33(4):878-884

[4]Abrar S,Ali A,Zerguine A,et al.Tracking Performance of Two Constant Modulus Equalizers[J].IEEE Communications Letters,2013,17(5):830-833

[5]Coskun A,Kale A.All-Adaptive blind matched filtering for the equalization and identification of multipath channels-a practical approach [J].IEEE Transactions on Circuits and SystemsI:Regular Paper,2013,60(1):232-242

[6]Asharif F,Tamaki S,Alshaif M R,et al.Performance improvement of constant modulus algorittun blind equalizer for 16 QAM modulation[J].ICIC Express Letters,2013,7(4):1377-1383

[7]Godard D N.Self-recovering equalization and carrier tracking in two dimensional data communication systems[J].IEEE Transactions on Communications,1980,28(11):1867-1875

[8]饶伟,高惠娟，段美怡.一种新的基于复指数函数映射的盲均衡算法[J].电子学报,2016,44(5):1009-1016

[9]Yang J,Werner J J,Dumont G A.The multi-modulus blind equalization and its generalized algorithm [J].IEEE Journal on Sel.Area in Community (S0733-8716),2002,20(5):997-1015

[10]Lin G,Zhu W.An efficient memetic algorithm for the max-bisection problem[J].IEEE Tran on Computers,2014,63(6):1365-1376

[11]ZHAO Tang W.Monkey algorithm for global numerical optimization[J].Journal of Uncertain Systems,2008,2(3):164-175

[12]陈信,周永权.基于猴群算法和单纯法的混合优化算法[J].计算机科学,2013,40(11):247-254

[13]张佳佳，张亚军，孙济洲.基于猴群算法的入侵检测技术[J].计算机工程,2011,37(14):131-133

[14]Yi H,Li H N,Zhang X D.A modified monkey algorithm for optimal sensor placement in structural health monitoring[J].Smart Materials and Structures,2012,21(10):65-69

[15]Pavlyukevich I.Levy Flight,non-local search and simulated annealing[J].Journal of Computational Physics,2007,226(2):1830-1844

[16]许小东.适合高阶QAM信号的加权多模盲均衡算法[J].电子与信息学报,2007,29(6):1352-1355

[17]Viswanathan G M,et al.Levy Flight in random searches[J].Physica A,2000,282:1-12

[18]高敏，郭业才.基于混沌萤火虫优化的小波多模盲均衡算法[J].计算机工程，2012,40(1):213-217

10.3969/j.issn.1673-2006.2017.12.023

TN911

A

1673-2006(2017)12-0086-06

2017-09-12

国家自然科学基金(61673222)；安徽省高校优秀中青年骨干人才国内外访学研修重点项目(gxfxZD2016351);安徽省教育厅自然科学研究重点项目(KJ2015A391);安徽教育厅自然科学研究重点项目 (KJ2016A663);淮南职业技术学院自然科学研究一般项目(HKJ14-4)。

高敏(1981-),女,江苏泰兴人,副教授，硕士,研究方向:智能信号处理、水声信道均衡技术。

*通讯作者：郭业才(1962-)，博士，教授，博导，主要研究方向：自适应均衡技术，通信信号处理。

刘小阳)