改進(jìn)型遺傳算法及其在代數(shù)碼書搜索中的應(yīng)用*

(重慶郵電大學(xué) 信號(hào)與信息處理重慶市重點(diǎn)實(shí)驗(yàn)室，重慶 400065)

1 引 言

目前，語音編碼技術(shù)已廣泛應(yīng)用于多媒體通信中。為了兼具高語音品質(zhì)和低速率，碼激勵(lì)線性預(yù)測(CELP)[1]編碼采用合成分析(A-B-S)搜索、感知加權(quán)、矢量量化(VQ)、線性預(yù)測(LP)等技術(shù)，編碼時(shí)用碼書中存儲(chǔ)的碼向量來代替LP余量信號(hào)作為激勵(lì)信號(hào)源，通常用一個(gè)自適應(yīng)碼書中的碼向量來逼近語音的基音(長時(shí)周期性)結(jié)構(gòu)，用一個(gè)固定的隨機(jī)碼書中的碼向量來逼近語音的經(jīng)過短時(shí)、長時(shí)預(yù)測后的余量信號(hào)。兩者乘以各自增益相加后構(gòu)成CELP的激勵(lì)信號(hào)，再通過短時(shí)合成濾波器得到合成語音。CELP以原始語音與合成語音的加權(quán)均方誤差最小為準(zhǔn)則，搜索最佳碼向量和幅度增益[2]。傳統(tǒng)CELP存在碼向量存儲(chǔ)量大和運(yùn)算量大的缺點(diǎn)。代數(shù)CELP(ACELP)碼書具有一定的代數(shù)結(jié)構(gòu)，無需存儲(chǔ)，結(jié)構(gòu)靈活，可以大大降低復(fù)雜度，因此被廣泛應(yīng)用于各種語音編碼標(biāo)準(zhǔn)中，如ITU-T G.729、G.723.1、ETSI GSM-EFR和3GPP AMR等[3]。

ACELP碼書中的每個(gè)碼向量由位置受限的幾個(gè)脈沖組成，搜索最佳的碼向量就是要找到脈沖位置及其符號(hào)的最佳組合。如果使用全搜索來獲得全局最優(yōu)的碼向量，其運(yùn)算量仍很大，難以達(dá)到系統(tǒng)的實(shí)時(shí)性要求。因此，標(biāo)準(zhǔn)的搜索算法常采用次優(yōu)方法，如G.729和G.723.1采用集中搜索法、G.729A[4]和GSM-EFR采用深度優(yōu)先樹搜索(DFTS)等降低運(yùn)算量，并盡量維持語音品質(zhì)。文獻(xiàn)[5]總結(jié)了前人對碼書搜索研究的一些成果，并從簡化相關(guān)矩陣的角度進(jìn)行了研究。

遺傳算法(GA)[6]是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過程的計(jì)算模型，主要特點(diǎn)是群體搜索策略和群體中個(gè)體之間的信息交換，搜索不依賴于目標(biāo)函數(shù)的梯度信息，是一種有效的全局優(yōu)化搜索算法。文獻(xiàn)[7]利用基本遺傳算法(SGA)對CELP碼書搜索進(jìn)行了研究。針對SGA存在的早熟收斂、全局優(yōu)化速度緩慢和局部搜索能力弱等缺點(diǎn)，本文提出一種改進(jìn)型遺傳算法(IGA)，并將其應(yīng)用于ITU-T G.729A語音編碼器的代數(shù)碼書搜索中，最后給出了仿真結(jié)果。

2 傳統(tǒng)的代數(shù)碼書搜索

G.729A碼書是基于代數(shù)結(jié)構(gòu)的固定碼書，使用交織單脈沖排列(ISSP)方法設(shè)計(jì)而成。如表1所示，每個(gè)碼向量含有4個(gè)非零脈沖，幅度為+1或者-1，整個(gè)碼書需用17 bit編碼。每子幀中激勵(lì)碼向量c(n)由40維(子幀長度)零向量、在4個(gè)位置上置4個(gè)單位脈沖并乘以相應(yīng)的符號(hào)來構(gòu)造。

表1 G.729A代數(shù)碼書結(jié)構(gòu)Table 1 Structure of G.729A algebraic codebook

(1)

式中，mi是第i個(gè)脈沖的位置，si是它的幅度。ACELP碼書搜索原則是使加權(quán)輸入語音和合成語音之間的均方誤差Ek最?。?/p>

Ek=‖x-gHck‖2

(2)

式中，ck是索引為k的碼向量；x是固定碼書搜索的目標(biāo)向量，由加權(quán)輸入語音減去加權(quán)合成濾波器的零輸入響應(yīng)和自適應(yīng)碼書的貢獻(xiàn)得到；g是碼書增益；H是由感知加權(quán)合成濾波器的脈沖響應(yīng)h(n)截?cái)喽傻南氯荰oeplitz矩陣，主對角線上的元素為h(0)，次對角線元素依次為h(1),h(2),…,h(39)。令式(2)中Ek/g=0，求得增益g再代回原式，易知最佳激勵(lì)碼向量應(yīng)使下式最大化：

(3)

式中，d=Htx是目標(biāo)信號(hào)x(n)和脈沖響應(yīng)h(n)的相關(guān)信號(hào)；Φ=HtH為h(n)的自相關(guān)矩陣，它的第(i,j)個(gè)元素表示為φ(i,j)。d和Φ在碼書搜索之前就可計(jì)算。由于ck僅有少數(shù)非零脈沖，代數(shù)結(jié)構(gòu)的碼書允許快速搜索。式(3)的分子和分母可簡化為

(4)

(5)

為簡化搜索過程，用適當(dāng)?shù)牧炕盘?hào)d(n)先作脈沖幅度預(yù)判決，即設(shè)置某一位置脈沖幅度的符號(hào)等于d(n)在此位置的符號(hào)，有：

si=sign(d(mi))

(6)

則式(4)和式(5)可分別表示為

(7)

(8)

其中，

(9)

深度優(yōu)先樹搜索(DFTS)[4]沿著局部最大值的樹路徑執(zhí)行搜索步驟。如圖1所示，G.729A使用深度優(yōu)先樹搜索，將每子幀可能的脈沖位置分成5個(gè)脈軌(見表2)，分兩階段進(jìn)行搜索。

圖1 G.729A深度優(yōu)先樹搜索示意圖
Fig.1 Illustration of depth-first tree search for G.729A

第一階段：先從T2中找到兩個(gè)最大的|d(mi)|，其對應(yīng)位置分別與T3的8個(gè)位置組合以確定最佳位置(i2,i3)，再對T0和T1進(jìn)行全搜索，找到使式(3)最大的組合(i0,i1)，因此經(jīng)過2×8+8×8=80次搜索即可確定出(i0,i1,i2,i3)。之后，通過改變脈沖軌道的搜索順序重復(fù)上述步驟。故第一階段需搜索2×80=160次。第二階段與第一階段操作類似，只是用T4替換掉T3。因此，G.729A深度優(yōu)先樹搜索的搜索量為2×160=320，為全搜索(213=8 192)的3.9%。

表2 G.729A深度優(yōu)先樹搜索的軌道分布Table 2 Track assignment of depth-first tree search for G.729A

3 改進(jìn)型遺傳算法(IGA)

基本遺傳算法(SGA)是一種基于概率的全局優(yōu)化算法。它將問題的可行解編碼為由基因組成的個(gè)體,模擬生物界“優(yōu)勝劣汰、適者生存”的機(jī)制，通過比例選擇、單點(diǎn)交叉和基本位變異3種基本操作，不斷迭代，最終求得問題的最優(yōu)解或滿意解[6]。SGA盡管有其優(yōu)點(diǎn)，但在實(shí)際應(yīng)用中存在易于早熟、優(yōu)化速度緩慢和局部搜索能力弱等缺點(diǎn)。本文在SGA的基礎(chǔ)上，結(jié)合ACELP代數(shù)碼書搜索的特點(diǎn)，從種群的初始化、混合選擇算子、自適應(yīng)交叉率和變異率、移民策略、局部爬山和終止條件等多方面進(jìn)行研究，提出一種改進(jìn)型遺傳算法(IGA)。

3.1 適應(yīng)度評價(jià)

遺傳算法以適應(yīng)度函數(shù)作為進(jìn)化目標(biāo),朝著適應(yīng)度函數(shù)值增大的方向進(jìn)化。因此，可直接選取式(3)作為個(gè)體適應(yīng)度函數(shù)，適應(yīng)度值大的個(gè)體有較大的機(jī)會(huì)遺傳到下一代。

3.2 種群初始化及編碼

產(chǎn)生初始種群方法通常有兩種[8]:一種是完全隨機(jī)方法產(chǎn)生，它適合于對問題解無任何先驗(yàn)知識(shí)的情況；另一種是由某些先驗(yàn)知識(shí)轉(zhuǎn)變?yōu)楸仨殱M足的一組要求，然后在滿足這些要求的解中再隨機(jī)地選取樣本。參考式(3)、式(7)和標(biāo)準(zhǔn)算法DFTS，IGA使用經(jīng)驗(yàn)式的隨機(jī)方法初始化種群，即選取|d(mi)|值較大的脈沖位置初始化種群，這樣既不失種群的多樣性，又可加快尋優(yōu)速度、提高搜索效率。編碼采用多參數(shù)級聯(lián)二進(jìn)制編碼方式，其中要編碼的參數(shù)是4個(gè)脈沖在軌道中所處位置的相對值，故個(gè)體基因串長度為13。

3.3 選擇算子

SGA的比例選擇(輪盤賭選擇)容易因超級個(gè)體的過度繁殖而導(dǎo)致早熟收斂，IGA采用規(guī)模為2的隨機(jī)聯(lián)賽和精英保存策略相結(jié)合的混合選擇算子：每次從群體中隨機(jī)選取2個(gè)個(gè)體加以比較，擇其適應(yīng)度最大者遺傳到下一代群體，重復(fù)多次以完成種群個(gè)體的選擇。為防止在選擇、交叉和變異過程中最佳個(gè)體意外丟失，將當(dāng)前群體中最佳的2個(gè)個(gè)體保留，用以替換經(jīng)交叉和變異后所產(chǎn)生的較差個(gè)體。精英保存策略是遺傳算法收斂性的一個(gè)重要保證條件。

3.4 交叉和變異算子

SGA以固定的交叉概率Pc和變異概率Pm進(jìn)行交叉和變異運(yùn)算，這不能很好地反映群體的進(jìn)化情形，而應(yīng)隨著進(jìn)化對其動(dòng)態(tài)地調(diào)整[9-11]：在進(jìn)化初期，Pc較大和Pm較小有利于增加群體的多樣性，加速算法向最優(yōu)解靠攏；在進(jìn)化后期，Pc較小和Pm較大有利于保護(hù)優(yōu)良個(gè)體，并可在一定程度上抑制早熟收斂。IGA設(shè)計(jì)的自適應(yīng)交叉概率Pc和自適應(yīng)變異概率Pm為

(10)

(11)

式中，g為當(dāng)前進(jìn)化代數(shù)，G為設(shè)定的最大進(jìn)化代數(shù)，Pc,max和Pc,min為設(shè)定的最大和最小交叉概率,Pm,max和Pm,min為設(shè)定的最大和最小變異概率，k為調(diào)整系數(shù)。本文取Pc,max=0.8,Pc,min=0.6,Pm,max=0.08，Pm,min=0.05，k=10。

3.5 移民策略

為增加群體多樣性，防止進(jìn)化中因封閉競爭而導(dǎo)致的早熟，IGA引入定期移民策略[12，13]：每隔M代采用一次移民操作淘汰一部分個(gè)體，并引入相同數(shù)目的外來移民及時(shí)補(bǔ)充到群體中。淘汰的個(gè)體(假設(shè)為N個(gè))包括種群中重復(fù)的個(gè)體以及適應(yīng)度最小的10%的個(gè)體，外來移民則從隨機(jī)產(chǎn)生的1.5N個(gè)個(gè)體中擇優(yōu)選出。本文取M=3。

3.6 終止條件及局部爬山

遺傳算法的局部搜索能力弱，導(dǎo)致進(jìn)化后期群體中最優(yōu)解改善的速度大為降低，這時(shí)可終止遺傳進(jìn)化而引入爬山法完成局部尋優(yōu)。具體操作過程為：以當(dāng)前搜索到的最優(yōu)解和次優(yōu)解為起點(diǎn)，進(jìn)行單個(gè)脈沖的局部尋優(yōu)，分別經(jīng)過36步鄰域搜索即可完成爬山操作(40個(gè)候選脈沖位置中不重復(fù)搜索)，從中確定最優(yōu)的一組解。這里，遺傳進(jìn)化的終止條件為以下兩種情形之一：

(1)達(dá)到設(shè)定的最大進(jìn)化代數(shù)G；

(2)種群中最優(yōu)個(gè)體適應(yīng)度值連續(xù)L代未發(fā)生變化。本文取L=5。

其中，情形(2)是執(zhí)行局部爬山操作的前提條件。

3.7 改進(jìn)型遺傳算法流程

改進(jìn)型遺傳算法的流程用偽代碼描述如下：

Procedure IGA

begin

t=1

對第七代種群P(t)初始化和適應(yīng)度評

while不滿足終止條件

對P(t)精英保存

對P(t)選擇、交叉和變異，產(chǎn)生P(t+1)

對P(t+1)適應(yīng)度評價(jià)

對P(t+1)精英替換

if滿足移民條件

對P(t+1)移民

end if

t=t+1

end while

if滿足局部爬山條件

對P(t)局部爬山

end if

輸出最優(yōu)解

end

4 IGA在代數(shù)碼書搜索中的應(yīng)用

將改進(jìn)型遺傳算法(IGA)應(yīng)用于ITU-T G.729A語音編碼器的代數(shù)碼書搜索，以檢驗(yàn)該算法的性能。本文代數(shù)碼書搜索算法的搜索量(Load)統(tǒng)一用個(gè)體適應(yīng)度函數(shù)的計(jì)算次數(shù)來衡量[7]，客觀合成語音質(zhì)量用分段信噪比(SegSNR)和ITU-T P.862建議的感知語音質(zhì)量評價(jià)(PESQ)[14]衡量。測試所用語音材料如表3所示。遺傳算法的參數(shù)設(shè)置：種群大小PopSize=25，最大進(jìn)化代數(shù)G=12，每次實(shí)驗(yàn)運(yùn)行30次求平均值。對于SGA：Pc=0.8，Pm=0.05。

表3 測試語音材料Table 3 Speech test materials

實(shí)驗(yàn)1：選取一段語音材料F1對IGA進(jìn)行性能測試，結(jié)果如表4所示。其中，IGA1～I(xiàn)GA5均是從IGA中除去了某種操作(或者相應(yīng)地保留與SGA一致的操作)的算法，這些操作依次為：經(jīng)驗(yàn)式隨機(jī)初始化種群、混合選擇算子、自適應(yīng)交叉和變異算子、移民策略、局部爬山搜索機(jī)制。從表4可以得出以下結(jié)論：IGA使用的經(jīng)驗(yàn)式的隨機(jī)初始化方法加快了全局優(yōu)化速度、提高了搜索效率；IGA采用的混合選擇算子、自適應(yīng)交叉、變異算子和移民策略，一方面保證了算法的收斂性，另一方面有效地維持了種群的多樣性、抑制了早熟收斂；IGA引入的局部爬山搜索機(jī)制使其搜索量有所增加，但是明顯地改善了搜索質(zhì)量，這彌補(bǔ)了GA局部搜索能力弱的缺陷。

表4 IGA性能測試Table 4 Performance test for IGA

實(shí)驗(yàn)2：將IGA與全搜索(FS)、深度優(yōu)先樹搜索(DFTS)和基本遺傳算法(SGA)進(jìn)行對比，表5、表6和表7分別給出了4種算法在搜索量、SegSNR和PESQ上的對比結(jié)果。從中可以得出以下結(jié)論：

(1)對比SGA，IGA靈活的算法終止條件使其搜索量有所降低，而且合成的語音品質(zhì)也要好于SGA，因此IGA具有更高的搜索效率；

(2)對比DFTS，IGA在搜索量和語音品質(zhì)上均要略勝于DFTS，這表明IGA具有較強(qiáng)的全局搜索能力；

(3)對比FS，IGA減少了大約96.6%的搜索量，卻使合成語音品質(zhì)稍微降低，這顯示出IGA對于大容量碼書搜索的優(yōu)越性。

因此，本文提出的基于IGA的代數(shù)碼書搜索方法是可行、有效的。

表5 搜索量對比Table 5 Comparison of search load

表6 SegSNR 對比Table 6 Comparison of SegSNR dB

表7 PESQ對比Table 7 Comparison of PESQ

5 結(jié)束語

本文針對基本遺傳算法易于早熟收斂、全局優(yōu)化速度緩慢和局部搜索能力弱等缺點(diǎn)，提出改進(jìn)型遺傳算法(IGA)，將其應(yīng)用于G.729A語音編碼器的代數(shù)碼書搜索中，并與全搜索、深度優(yōu)先樹搜索和基本遺傳算法進(jìn)行了比較，仿真結(jié)果表明了IGA的可行性和有效性,從而為研究代數(shù)碼書搜索方法提供了新思路。同時(shí)應(yīng)注意到，遺傳算法由于含有選擇、交叉和變異等操作算子，搜索過程要比標(biāo)準(zhǔn)算法復(fù)雜一些，在實(shí)時(shí)應(yīng)用中還有待進(jìn)一步優(yōu)化。本文所述僅是GA用于代數(shù)碼書搜索的一隅。對于其它諸如3GPP AMR、AMR-WB和ITU-T G.722.2等高速率模式下脈沖數(shù)更多、結(jié)構(gòu)也更復(fù)雜的代數(shù)碼書，如何充分利用GA搜索的全局性和內(nèi)在并行性，是值得進(jìn)一步研究的問題，相信GA的優(yōu)勢會(huì)在其中得到更好的發(fā)揮。

參考文獻(xiàn)：

[1] Schroeder M R,Atal B S.Code-excited linear prediction(CELP):high-quality speech at very low bit rates[C]//Proceedings of IEEE ICASSP’85.Tampa,Florida,USA:IEEE,1985:937-940.

[2] 王炳錫,王洪.變速率語音編碼[M].西安:西安電子出版社,2004.

WANG Bing-xi,WANG Hong.Variable rate speech coding[M].Xi′an: Xidian University Press,2004.(in Chinese)

[3] Benesty J, Sondhi M M, Huang Y. Springer Handbook of Speech Processing[M].Berlin:Springer，2008.

[4] Salami R, Laflamme C,Bessette B,et al.ITU-T G.729 Annex A:reduced complexity 8 kb/s CS-ACELP codec for digital simultaneous voice and data[J].IEEE Communication Magazine,1997,35(9):56-63.

[5] Tsai S-M,Yang J-F.Efficient algebraic code-excited linear predictive codebook search[J].IEE Proceedings of Vision Image and Signal Processing,2006,153(6):761-768.

[6] 周明,孫樹棟.遺傳算法原理及應(yīng)用[M].北京:國防工業(yè)出版社,1999.

ZHOU Ming,Sun Shu-dong.Genetic algorithms:theory and applications[M]. Beijing: National Defense Industry Press,1999.(in Chinese)

[7] 徐自勵(lì),王永德,何培宇.基于遺傳搜索算法的碼激勵(lì)線性預(yù)測編碼[J].四川大學(xué)學(xué)報(bào)(自然科學(xué)版),2004,41(2):323-327.

XU Zi-li,WANG Yong-de,HE Pei-yu. CELP based on genetic algorithms[J].Journal of Sichuan University (Natural Science Edition),2004,41(2):323-327.(in Chinese)

[8] 王小平,曹立明.遺傳算法——理論、應(yīng)用與軟件實(shí)現(xiàn)[M].西安:西安交通大學(xué)出版社,2002.

WANG Xiao-ping,CAO Li-ming.Genetic algorithms-theory,application and software implement[M].Xi′an:Xi′an Jiaotong University Press, 2002.(in Chinese)

[9] 宋平,張焰,藍(lán)毓俊,等.改進(jìn)遺傳算法在配電網(wǎng)重構(gòu)中的應(yīng)用[J].上海交通大學(xué)學(xué)報(bào),1999,33(4):488-491.

SONG Ping,ZHANG Yan,LAN Yu-jun,et al.Application of improved genetic algorithm in power distribution system reconfiguration[J].Journal of Shanghai Jiaotong University,1999,33(4):488-491.(in Chinese)

[10] 田延碩.遺傳算法的研究與應(yīng)用[D].成都：電子科技大學(xué),2004.

Tian Yan-shuo. Research and application of genetic algorithm[D].Chengdu:University of Electronic Science and Technology of China,2004.(in Chinese)

[11] 呂善偉,韓艷菊,王偉.遺傳算法綜合陣列的幅度和相位方向圖[J].北京航空航天大學(xué)學(xué)報(bào),2005,31(9):1014-1017.

LV Shan-wei,HAN Yan-ju,WANG Wei.Synthesis of the array's amplitude and phase pattern using genetic algorithm[J].Journal of Beijing University of Aeronautics and Astronautics,2005,31(9):1014-1017.(in Chinese)

[12] 歐陽森,王建華,宋政湘,等.一種新的改進(jìn)遺傳算法及其應(yīng)用[J].系統(tǒng)仿真學(xué)報(bào),2003,15(8):1066-1068.

OUYANG Sen,WANG Jian-hua,SONG Zheng-xiang,et al.A new improved genetic algorithm and its application[J].Journal of System Simulation,2003,15(8):1066-1068.(in Chinese)

[13] 王全國,王三民,袁茹.三維循環(huán)對稱結(jié)構(gòu)的多目標(biāo)多約束拓?fù)鋬?yōu)化算法研究[J].西北工業(yè)大學(xué)學(xué)報(bào),2008,26(4):425-429.

WANG Quan-guo, WANG San-min,YUAN Ru.Exploring multi-objective topological optimization of 3D cyclically symmetric structure under multiple constraints[J].Journal of Northwestern Polytecnical University,2008,26(4):425-429.(in Chinese)

[14] ITU-T Recommendation P.862,Perceptual evaluation of speech quality(PESQ):An objective method for end-to-end speech quality assessment of narrow-band telephone networks and speech codes[S].