文獻標識碼: A
DOI:10.16157/j.issn.0258-7998.2016.02.024
中文引用格式: 張冰龍,徐建敏,江浩. 基于模擬退火的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.
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)是均衡器的輸出信號。
均衡器輸出為:
式中,wr(k)、wi(k)分別表示均衡器權向量的實部與虛部。
WTMMA的代價函數為:
式中,分別表示對小波變換系數uj,m(k)和尺度變換系數sJ,m(k)的平均功率估計,可由下式遞推得到:
式中,β為平滑因子,且0<β<1。以上各式構成了小波多模盲均衡算法(WTMMA)[8]。
2 基于模擬退火算法的DNA遺傳算法
2.1 基于模擬退火算法的DNA遺傳算法操作算子
2.1.1 DNA編碼
DNA編碼是將變量用A、T、C、G四種堿基表示的過程。首先建立堿基與數字的映射關系,例如A/0、T/1、C/2、G/3映射,然后變量表示成由0、1、2、3這四個數字表示的四進制序列,這樣就建立了變量與堿基序列的映射關系。
2.1.2 DNA遺傳算法交叉算子
在交叉操作中包含三種類型的交叉算子,分別為置換交叉算子、轉位交叉算子和重構交叉算子。
(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星座圖比另外三種算法輸出的星座圖更加清晰。
5 結論
本文提出了一種基于模擬退火的DNA遺傳優化小波多模盲均衡算法。將模擬退火算法應用到DNA遺傳算法中,提高了DNA遺傳算法的搜索效率并且有效避免了局部收斂。仿真結果表明,與MMA、WTMMA和DNAGA-WTMMA相比,該算法在收斂速度和均方誤差方面都得到了提高,因此更適合用于通信系統中的信號處理。
參考文獻
[1] 郭業才.自適應盲均衡技術[M].合肥:合肥工業大學出版社,2007:17-25.
[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.