基于列維飛行復(fù)形猴群算法的多模盲均衡算法

高 敏,郭業(yè)才

1.中國(guó)礦業(yè)大學(xué)物聯(lián)網(wǎng)(感知礦山)研究中心，徐州,221008;2.淮南職業(yè)技術(shù)學(xué)院信息與電氣工程系，淮南,232001;3.南京信息工程大學(xué)江蘇省氣象探測(cè)與信息處理重點(diǎn)實(shí)驗(yàn)室，南京,210044

基于列維飛行復(fù)形猴群算法的多模盲均衡算法

高 敏1,2,郭業(yè)才3*

1.中國(guó)礦業(yè)大學(xué)物聯(lián)網(wǎng)(感知礦山)研究中心，徐州,221008;2.淮南職業(yè)技術(shù)學(xué)院信息與電氣工程系，淮南,232001;3.南京信息工程大學(xué)江蘇省氣象探測(cè)與信息處理重點(diǎn)實(shí)驗(yàn)室，南京,210044

針對(duì)傳統(tǒng)多模盲均衡算法(MMA)在最小化代價(jià)函數(shù)時(shí)采用梯度思想而導(dǎo)致的易陷入局部最優(yōu)、收斂速度慢、收斂后穩(wěn)態(tài)誤差大等問(wèn)題，提出一種基于列維飛行復(fù)形猴群算法的多模盲均衡算法。用具有優(yōu)秀搜索路徑的列維飛行模式來(lái)確定猴群算法中的爬步長(zhǎng)，增強(qiáng)搜索隨機(jī)性的同時(shí)有助于跳出局部最優(yōu)，將復(fù)形法嵌入望跳過(guò)程加強(qiáng)局部搜索，提高了猴群算法的搜索效率和優(yōu)化性能，結(jié)合MMA能提高信號(hào)均衡質(zhì)量。仿真實(shí)驗(yàn)表明，新算法收斂速度更快，均方誤差更低。

多模盲均衡；猴群算法；復(fù)形法；列維飛行；全局最優(yōu)位置；最優(yōu)權(quán)向量

1 相關(guān)研究與問(wèn)題提出

在無(wú)線(xiàn)通信系統(tǒng)中，不可避免地存在著由于多徑傳輸?shù)榷喾N因素造成的碼間干擾問(wèn)題，嚴(yán)重影響傳輸質(zhì)量。1975年由Sato提出的盲均衡技術(shù)為信源的自恢復(fù)提供了可能[1]，受其啟發(fā)，各種盲均衡算法大量涌現(xiàn)[2]。最為經(jīng)典的常模盲均衡算法(Constant Modulus Algorithm,CMA)因計(jì)算量小、易于實(shí)現(xiàn)且魯棒性強(qiáng)而被廣泛使用[3-5]。CMA借助梯度思想更新均衡器權(quán)向量以最小化高維非凸性的代價(jià)函數(shù)[6]，最終使均衡器輸出的幅值收斂到一個(gè)固定的統(tǒng)計(jì)模值[7]，這對(duì)具有常數(shù)模的相移鍵控(Phase Shift Keying,PSK)信號(hào)以及低階正交振幅調(diào)制(Quadrature Amplitude Modulation,QAM)信號(hào)有很好的效果，但對(duì)高階QAM和正交相移鍵控(Amplitude phase shift keying,APSK)信號(hào)均衡效果不理想[8]，并且采用梯度思想求解多模態(tài)函數(shù)易落入局部最優(yōu)。多模盲均衡算法(Multi-Modulus Algorithm,MMA)將均衡器輸入信號(hào)的實(shí)部和虛部分別進(jìn)行均衡，同時(shí)利用信號(hào)的幅值和相位信息，能有效避免相位旋轉(zhuǎn)，可在一定程度上提高均衡質(zhì)量[9]，但它在最小化代價(jià)函數(shù)時(shí)仍沿用了梯度思想，還是無(wú)法有效解決易陷入局部最優(yōu)的問(wèn)題，導(dǎo)致收斂速度慢，穩(wěn)態(tài)誤差大[10]。

猴群算法(Monkey Algorithm，MA)是模擬自然界中猴群登高爬山行為而設(shè)計(jì)的一種新型的群智能優(yōu)化算法[11]，自2008年提出以來(lái)已被成功用于求解很多非凸函數(shù)優(yōu)化問(wèn)題[12-14]。該算法與其他群智能優(yōu)化算法相比，最大的特點(diǎn)是對(duì)優(yōu)化對(duì)象的維數(shù)不敏感，不會(huì)陷入“維災(zāi)難”，所以對(duì)高維非凸性函數(shù)的優(yōu)化有很好的效果，但仍存在搜索速度慢、局部精度較低等問(wèn)題。列維飛行(Levy flight)是法國(guó)數(shù)學(xué)Paul Pierre Levy提出的一種隨機(jī)游走模式，這種游走模式的特點(diǎn)是在較小的移動(dòng)之后發(fā)生較大的跳躍，自然界中很多動(dòng)物的行為都具有這一特征，該過(guò)程表面看起來(lái)雜亂無(wú)章，實(shí)質(zhì)卻遵循著非常確定的統(tǒng)計(jì)分布規(guī)律[15]。

本文采用列維飛行模式確定MA中的爬步長(zhǎng)，以增加搜索的隨機(jī)性，提高搜索速度，有效避免落入局部最優(yōu)，并將傳統(tǒng)的復(fù)形法嵌入望跳過(guò)程，在增強(qiáng)局部搜索能力的同時(shí)還引入競(jìng)爭(zhēng)機(jī)制，以保證種群的多樣性，將改進(jìn)后的MA用于最小化MMA的代價(jià)函數(shù)，捕獲均衡器初始權(quán)向量，提出基于列維飛行復(fù)形猴群算法的多模盲均衡算法(Multi-modulus Blind Equalization Algorithm Based on Levy Flight Complex Method Monkey Algorithm，LF-CM-MA-MMA)。仿真結(jié)果表明，本文提出的算法對(duì)高階QAM信號(hào)有很好的均衡效果。

2 多模盲均衡算法(MMA)

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

圖1 MMA原理圖

圖1中，a(k)是發(fā)射的信源復(fù)信號(hào)；h(k)是信號(hào)傳輸信道的脈沖響應(yīng)向量；n(k)是加性高斯白噪聲；y(k)是均衡器輸入信號(hào)；F(k)是均衡器的權(quán)系數(shù)向量；z(k)為均衡器的輸出復(fù)信號(hào)；s(k)為判決輸出的復(fù)信號(hào)；g(·)為無(wú)記憶非線(xiàn)性函數(shù)，需滿(mǎn)足s(k)=g[z(k)]=z(k)；下標(biāo)Re和Im分別代表參數(shù)的實(shí)部和虛部。

均衡器的輸入為：

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代價(jià)函數(shù)[16]為：

(3)

發(fā)射信號(hào)同相方向統(tǒng)計(jì)模值為:

(4a)

發(fā)射信號(hào)正交方向統(tǒng)計(jì)模值為:

(4b)

MMA誤差函數(shù)為：

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

(5a)

(5b)

(5c)

均衡器權(quán)向量的迭代公式為：

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

(6)

式中，μ為迭代步長(zhǎng)。式(1a)～式(6)構(gòu)成了MMA算法。方形QAM信號(hào)在同相和正交方向的分布是均勻等概率的，此時(shí)有RRe=RIm，故MMA和CMA計(jì)算復(fù)雜度相當(dāng)，但其代價(jià)函數(shù)同時(shí)包含了幅度信息和相位信息，可有效糾正相位旋轉(zhuǎn)，對(duì)非常模信號(hào)有很好的均衡能力。MMA的代價(jià)函數(shù)也是高維非凸性的，采用隨機(jī)梯度思想更新均衡器權(quán)向量，容易落入局部最優(yōu)，均衡效果有待提高。

2 基于列維飛行復(fù)形猴群算法的多模盲均衡算法(LF-CM-MA-MMA)

2.1 猴群算法

基本猴群算法是主要包括5個(gè)過(guò)程，分別是初始化、確定適應(yīng)度函數(shù)、爬過(guò)程、望跳過(guò)程和翻跳過(guò)程，流程如圖2所示。

圖2 猴群算法流程圖

主要步驟說(shuō)明如下：

Step1初始化。在一個(gè)n維空間，隨機(jī)產(chǎn)生規(guī)模為m的猴群，每只人工猴的初始位置按公式(7)進(jìn)行隨機(jī)分配。

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

(7)

式中，xij為第i只猴子在第j維的實(shí)際位置，xmin,j和xmax,j分別表示搜索空間第j維的下界和上界，rand產(chǎn)生一個(gè)在區(qū)間[0,1]上的實(shí)數(shù)。

Step2適應(yīng)度函數(shù)的確定。每只人工猴的位置向量代表了適應(yīng)度函數(shù)的一個(gè)潛在解，將位置向量帶入適應(yīng)度函數(shù)進(jìn)行計(jì)算，所得值越大意味著位置越好，離最高山峰也越近，猴群算法最終得到的是適應(yīng)度函數(shù)的最大值。如果待優(yōu)化函數(shù)是要獲取最小值，只要進(jìn)行簡(jiǎn)單的處理即可。比如本文中，需要最小化MMA的代價(jià)函數(shù)以獲取均衡器的初始權(quán)向量，則可將均衡器的權(quán)向量和人工猴的位置向量設(shè)置為相同的形式，兩函數(shù)互為倒數(shù)即可。當(dāng)MA適應(yīng)度函數(shù)取得最大值時(shí),意味著MMA代價(jià)函數(shù)取得最小值，這時(shí)最大適應(yīng)度函數(shù)值對(duì)應(yīng)的位置向量，即為所求的MMA中均衡器初始權(quán)向量。

Step3爬過(guò)程。在搜索空間中，對(duì)第i只人工猴的當(dāng)前位置進(jìn)行隨機(jī)擾動(dòng)，生成一個(gè)隨機(jī)向量ΔXi=(Δxi1,Δxi2,…,Δxin)，分量Δxij以相同的概率0.5取爬步長(zhǎng)λ(λ>0)或-λ。計(jì)算偽梯度信息f＇i(xi)=(f＇i1(xi),f＇i2(xi),…,f＇in(xi))，其中：

(8)

設(shè)向量Yi=(yi1,yi2,…,yin)，其中各分量為：

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

(9)

若Yi在搜索空間內(nèi)，則Yi→Xi；否則，保持Xi不變。重復(fù)爬過(guò)程，直到滿(mǎn)足設(shè)定條件轉(zhuǎn)入望跳過(guò)程。

Step4望跳過(guò)程。每只人工猴攀爬一段時(shí)間后，會(huì)停下來(lái)在視野范圍(xij-γ,xij+γ)內(nèi)向四周多次眺望以探索更好位置。每次眺望的結(jié)果用Yi=(yi1,yi2,…,yin)表示。若Yi在搜索空間并有f(Yi)>f(Xi)，則Yi→Xi；否則，保持Xi不變。重復(fù)多次探尋，每只人工猴都到達(dá)各自的最好位置，以此時(shí)位置為初始位置重復(fù)爬過(guò)程，達(dá)到設(shè)定次數(shù)轉(zhuǎn)入翻跳過(guò)程。

Step5翻跳過(guò)程。這一過(guò)程是為避免落入局部最優(yōu)，迫使猴群找到新的搜索域。在翻區(qū)間內(nèi)隨機(jī)產(chǎn)生一個(gè)實(shí)數(shù)θ,設(shè)Yi=(yi1,yi2,…,yin)，令：

yij=xij+θ·(pj-xij)

(10)

公式(7)～(10)構(gòu)成了基本猴群算法，式中，i=1,2,…,m;j=1,2,…,n。猴群算法計(jì)算量主要集中在爬過(guò)程，借助偽梯度信息，不需要考慮適應(yīng)度函數(shù)的維度，但存在搜索速度慢、局部搜索能力不高的缺點(diǎn)。為解決這一問(wèn)題，本文提出了一種列維飛行復(fù)形猴群算法(Levy Flight Complex Method Monkey Algorithm，LF-CM-MA)。

2.2 采用列維飛行的爬步長(zhǎng)

猴群在登山爬高過(guò)程中，并不會(huì)以一個(gè)固定步長(zhǎng)進(jìn)行，一般是幾小步攀爬后會(huì)有一大步跳躍，其特征更符合列維飛行模式，并且這種搜索模式也更為有效[17]。若將猴群算法中原固定的爬步長(zhǎng)采用列維飛行模式，則公式(9)改為：

(11)

式中，α為步長(zhǎng)控制因子(α>0，具體數(shù)值可根據(jù)實(shí)際情況設(shè)置)；⊕為點(diǎn)對(duì)點(diǎn)乘法；Levy(β)為隨機(jī)搜索路徑，它移動(dòng)的步長(zhǎng)服從列維分布：

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

(12)

2.3 嵌入復(fù)形法的望跳過(guò)程

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

復(fù)形法本質(zhì)上講是一種局部搜索算法，引入復(fù)形思想，不僅增強(qiáng)了局部搜索能力，還引入了一定的競(jìng)爭(zhēng)機(jī)制，保證種群的多樣性。在望跳過(guò)程后，復(fù)形法指導(dǎo)下的位置向量將取代適應(yīng)度值最差的位置向量，雖然復(fù)形法很容易陷入局部最優(yōu)，但本文中的爬步長(zhǎng)采用了列維飛行模式，這種方式能有效跳出局部最優(yōu)，兩者可很好地融合。

具體步驟：在望跳過(guò)程后，此時(shí)猴群的當(dāng)前位置作為復(fù)形法的初始位置，將其按適應(yīng)度函數(shù)以降序進(jìn)行排列X1,X2,…,Xm，適應(yīng)度值最小的為最差點(diǎn)。按下列方式確定一個(gè)新點(diǎn)來(lái)替換最差點(diǎn)Xm。

(1)計(jì)算復(fù)形的形心：

(13)

(2)計(jì)算復(fù)形的反射點(diǎn)：

Xr=Xc+ζ·(Xc-Xm)

(14)

式中，ζ為反射系數(shù)。若f(Xr)>f(Xm)，則用Xr替換Xm，執(zhí)行步驟(3)，否則執(zhí)行步驟(4)。

(3)延伸操作：

Xe=Xr+τ·(Xr-Xc)

(15)

式中，τ為延伸系數(shù)。若f(Xe)>f(Xm)，則用Xe替換Xm，執(zhí)行步驟(1)，否則執(zhí)行步驟(4)。

(4)收縮操作：

Xk=Xm-σ·(Xm-Xc)

(16)

圖4 512-QAM仿真結(jié)果

其中σ為收縮系數(shù)。若f(Xk)>f(Xm)，則用Xk替換Xm，執(zhí)行步驟(1)，滿(mǎn)足設(shè)定次數(shù)結(jié)束，否則重新進(jìn)行排序，重復(fù)復(fù)形。

2.4 基于列維飛行復(fù)形猴群算法的多模盲均衡算法

為提高M(jìn)MA對(duì)高階QAM的均衡性能，本文將LF-CM-MA和MMA有機(jī)結(jié)合，提出基于列維飛行復(fù)形猴群算法的多模盲均衡算法(Multi-modulus Blind Equalization Algorithm Based on Levy Flight Complex Method Monkey Algorithm,LF-CM-MA-MMA)，均衡器初始權(quán)向量的虛部和實(shí)部均采用LF-CM-MA搜索到的最佳位置向量，然后再用MMA對(duì)信號(hào)的實(shí)部和虛部分別進(jìn)行均衡輸出。LF-CM-MA-MMA實(shí)現(xiàn)流程如3所示。

3 仿真分析

為驗(yàn)證LF-CM-MA-MMA對(duì)高階QAM信號(hào)的均衡性能，采用512-QAM信號(hào)，并將其與基于小波變換的多模盲均衡算法(WT-MMA)，基于猴群算法的多模盲均衡算法(MA-MMA)，基于列維飛行猴群算法的多模盲均衡算法(LF-MA-MMA)，基于復(fù)形法猴群算法的多模盲均算法(CM-MA-MMA)，基于混沌螢火蟲(chóng)算法的多模盲均衡算法[18](CGSO-MMA)為比較對(duì)象進(jìn)行仿真實(shí)驗(yàn)，信道采用h=[0.9656,-0.0906,0.0578,0.2368]，高斯白噪聲的信噪比40 dB，信號(hào)采樣點(diǎn)均為15 000點(diǎn)，盲均衡器的權(quán)長(zhǎng)均為16，猴群規(guī)模為100，爬過(guò)程、望跳過(guò)程、翻跳過(guò)程的迭代次數(shù)分別設(shè)置為100、20、5，視野范圍為0.005，反射系數(shù)、延伸系數(shù)、收縮系數(shù)分別為1.1、0.4、0.6，步長(zhǎng)控制因子為0.01，WT-MMA中迭代步長(zhǎng)為0.000 000 6，MA-MMA、CM-MA-MMA、LF-MA-MMA、CGSO-MMA、LF-CM-MA-MMA中迭代步長(zhǎng)均為0.000 000 08。

從圖4不難看出，在對(duì)512-QAM信號(hào)的均衡中，本文算法比WT-MMA收斂快了6 000步，與CGSO-MMA、MA-MMA、LF-MMA、CM-MMA收斂速度幾乎一致；穩(wěn)態(tài)誤差上，本文算法比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 結(jié)束語(yǔ)

本文提出了基于列為飛行復(fù)形猴群算法的多模盲均衡算法，用隨機(jī)性大但性能穩(wěn)定的列維飛行模式來(lái)設(shè)置猴群的攀爬步長(zhǎng)，不僅增加了搜索的隨機(jī)性，還可有效避免落入局部最優(yōu)。在望跳過(guò)程中引入復(fù)合形法，適當(dāng)保持種群多樣性的同時(shí)引入競(jìng)爭(zhēng)淘汰機(jī)制，加強(qiáng)局部搜索，有效提高了算法的精度和優(yōu)化效率，與MMA結(jié)合，在均衡高階QAM信號(hào)時(shí)，收斂速度快且收斂后穩(wěn)態(tài)誤差小，與其他同類(lèi)算法比較，性能更好。

[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]郭業(yè)才.自適應(yīng)盲均衡技術(shù)[M].合肥:合肥工業(yè)大學(xué)出版社,2007:5-8

[3]孫云山.改進(jìn)恒模盲均衡在醫(yī)學(xué)CT圖像盲恢復(fù)中的應(yīng)用[J].儀器儀表學(xué)報(bào),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]饒偉,高惠娟，段美怡.一種新的基于復(fù)指數(shù)函數(shù)映射的盲均衡算法[J].電子學(xué)報(bào),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]陳信,周永權(quán).基于猴群算法和單純法的混合優(yōu)化算法[J].計(jì)算機(jī)科學(xué),2013,40(11):247-254

[13]張佳佳，張亞軍，孫濟(jì)洲.基于猴群算法的入侵檢測(cè)技術(shù)[J].計(jì)算機(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信號(hào)的加權(quán)多模盲均衡算法[J].電子與信息學(xué)報(bào),2007,29(6):1352-1355

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

[18]高敏，郭業(yè)才.基于混沌螢火蟲(chóng)優(yōu)化的小波多模盲均衡算法[J].計(jì)算機(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

國(guó)家自然科學(xué)基金(61673222)；安徽省高校優(yōu)秀中青年骨干人才國(guó)內(nèi)外訪(fǎng)學(xué)研修重點(diǎn)項(xiàng)目(gxfxZD2016351);安徽省教育廳自然科學(xué)研究重點(diǎn)項(xiàng)目(KJ2015A391);安徽教育廳自然科學(xué)研究重點(diǎn)項(xiàng)目 (KJ2016A663);淮南職業(yè)技術(shù)學(xué)院自然科學(xué)研究一般項(xiàng)目(HKJ14-4)。

高敏(1981-),女,江蘇泰興人,副教授，碩士,研究方向:智能信號(hào)處理、水聲信道均衡技術(shù)。

*通訊作者：郭業(yè)才(1962-)，博士，教授，博導(dǎo)，主要研究方向：自適應(yīng)均衡技術(shù)，通信信號(hào)處理。

劉小陽(yáng))