改进型遗传算法及其在代数码书搜索中的应用*

(重庆邮电大学 信号与信息处理重庆市重点实验室，重庆 400065)

1 引 言

目前，语音编码技术已广泛应用于多媒体通信中。为了兼具高语音品质和低速率，码激励线性预测(CELP)[1]编码采用合成分析(A-B-S)搜索、感知加权、矢量量化(VQ)、线性预测(LP)等技术，编码时用码书中存储的码向量来代替LP余量信号作为激励信号源，通常用一个自适应码书中的码向量来逼近语音的基音(长时周期性)结构，用一个固定的随机码书中的码向量来逼近语音的经过短时、长时预测后的余量信号。两者乘以各自增益相加后构成CELP的激励信号，再通过短时合成滤波器得到合成语音。CELP以原始语音与合成语音的加权均方误差最小为准则，搜索最佳码向量和幅度增益[2]。传统CELP存在码向量存储量大和运算量大的缺点。代数CELP(ACELP)码书具有一定的代数结构，无需存储，结构灵活，可以大大降低复杂度，因此被广泛应用于各种语音编码标准中，如ITU-T G.729、G.723.1、ETSI GSM-EFR和3GPP AMR等[3]。

ACELP码书中的每个码向量由位置受限的几个脉冲组成，搜索最佳的码向量就是要找到脉冲位置及其符号的最佳组合。如果使用全搜索来获得全局最优的码向量，其运算量仍很大，难以达到系统的实时性要求。因此，标准的搜索算法常采用次优方法，如G.729和G.723.1采用集中搜索法、G.729A[4]和GSM-EFR采用深度优先树搜索(DFTS)等降低运算量，并尽量维持语音品质。文献[5]总结了前人对码书搜索研究的一些成果，并从简化相关矩阵的角度进行了研究。

遗传算法(GA)[6]是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于目标函数的梯度信息，是一种有效的全局优化搜索算法。文献[7]利用基本遗传算法(SGA)对CELP码书搜索进行了研究。针对SGA存在的早熟收敛、全局优化速度缓慢和局部搜索能力弱等缺点，本文提出一种改进型遗传算法(IGA)，并将其应用于ITU-T G.729A语音编码器的代数码书搜索中，最后给出了仿真结果。

2 传统的代数码书搜索

G.729A码书是基于代数结构的固定码书，使用交织单脉冲排列(ISSP)方法设计而成。如表1所示，每个码向量含有4个非零脉冲，幅度为+1或者-1，整个码书需用17 bit编码。每子帧中激励码向量c(n)由40维(子帧长度)零向量、在4个位置上置4个单位脉冲并乘以相应的符号来构造。

表1 G.729A代数码书结构Table 1 Structure of G.729A algebraic codebook

(1)

式中，mi是第i个脉冲的位置，si是它的幅度。ACELP码书搜索原则是使加权输入语音和合成语音之间的均方误差Ek最小：

Ek=‖x-gHck‖2

(2)

式中，ck是索引为k的码向量；x是固定码书搜索的目标向量，由加权输入语音减去加权合成滤波器的零输入响应和自适应码书的贡献得到；g是码书增益；H是由感知加权合成滤波器的脉冲响应h(n)截断而成的下三角Toeplitz矩阵，主对角线上的元素为h(0)，次对角线元素依次为h(1),h(2),…,h(39)。令式(2)中Ek/g=0，求得增益g再代回原式，易知最佳激励码向量应使下式最大化：

(3)

式中，d=Htx是目标信号x(n)和脉冲响应h(n)的相关信号；Φ=HtH为h(n)的自相关矩阵，它的第(i,j)个元素表示为φ(i,j)。d和Φ在码书搜索之前就可计算。由于ck仅有少数非零脉冲，代数结构的码书允许快速搜索。式(3)的分子和分母可简化为

(4)

(5)

为简化搜索过程，用适当的量化信号d(n)先作脉冲幅度预判决，即设置某一位置脉冲幅度的符号等于d(n)在此位置的符号，有：

si=sign(d(mi))

(6)

则式(4)和式(5)可分别表示为

(7)

(8)

其中，

(9)

深度优先树搜索(DFTS)[4]沿着局部最大值的树路径执行搜索步骤。如图1所示，G.729A使用深度优先树搜索，将每子帧可能的脉冲位置分成5个脉轨(见表2)，分两阶段进行搜索。

图1 G.729A深度优先树搜索示意图
Fig.1 Illustration of depth-first tree search for G.729A

第一阶段：先从T2中找到两个最大的|d(mi)|，其对应位置分别与T3的8个位置组合以确定最佳位置(i2,i3)，再对T0和T1进行全搜索，找到使式(3)最大的组合(i0,i1)，因此经过2×8+8×8=80次搜索即可确定出(i0,i1,i2,i3)。之后，通过改变脉冲轨道的搜索顺序重复上述步骤。故第一阶段需搜索2×80=160次。第二阶段与第一阶段操作类似，只是用T4替换掉T3。因此，G.729A深度优先树搜索的搜索量为2×160=320，为全搜索(213=8 192)的3.9%。

表2 G.729A深度优先树搜索的轨道分布Table 2 Track assignment of depth-first tree search for G.729A

3 改进型遗传算法(IGA)

基本遗传算法(SGA)是一种基于概率的全局优化算法。它将问题的可行解编码为由基因组成的个体,模拟生物界“优胜劣汰、适者生存”的机制，通过比例选择、单点交叉和基本位变异3种基本操作，不断迭代，最终求得问题的最优解或满意解[6]。SGA尽管有其优点，但在实际应用中存在易于早熟、优化速度缓慢和局部搜索能力弱等缺点。本文在SGA的基础上，结合ACELP代数码书搜索的特点，从种群的初始化、混合选择算子、自适应交叉率和变异率、移民策略、局部爬山和终止条件等多方面进行研究，提出一种改进型遗传算法(IGA)。

3.1 适应度评价

遗传算法以适应度函数作为进化目标,朝着适应度函数值增大的方向进化。因此，可直接选取式(3)作为个体适应度函数，适应度值大的个体有较大的机会遗传到下一代。

3.2 种群初始化及编码

产生初始种群方法通常有两种[8]:一种是完全随机方法产生，它适合于对问题解无任何先验知识的情况；另一种是由某些先验知识转变为必须满足的一组要求，然后在满足这些要求的解中再随机地选取样本。参考式(3)、式(7)和标准算法DFTS，IGA使用经验式的随机方法初始化种群，即选取|d(mi)|值较大的脉冲位置初始化种群，这样既不失种群的多样性，又可加快寻优速度、提高搜索效率。编码采用多参数级联二进制编码方式，其中要编码的参数是4个脉冲在轨道中所处位置的相对值，故个体基因串长度为13。

3.3 选择算子

SGA的比例选择(轮盘赌选择)容易因超级个体的过度繁殖而导致早熟收敛，IGA采用规模为2的随机联赛和精英保存策略相结合的混合选择算子：每次从群体中随机选取2个个体加以比较，择其适应度最大者遗传到下一代群体，重复多次以完成种群个体的选择。为防止在选择、交叉和变异过程中最佳个体意外丢失，将当前群体中最佳的2个个体保留，用以替换经交叉和变异后所产生的较差个体。精英保存策略是遗传算法收敛性的一个重要保证条件。

3.4 交叉和变异算子

SGA以固定的交叉概率Pc和变异概率Pm进行交叉和变异运算，这不能很好地反映群体的进化情形，而应随着进化对其动态地调整[9-11]：在进化初期，Pc较大和Pm较小有利于增加群体的多样性，加速算法向最优解靠拢；在进化后期，Pc较小和Pm较大有利于保护优良个体，并可在一定程度上抑制早熟收敛。IGA设计的自适应交叉概率Pc和自适应变异概率Pm为

(10)

(11)

式中，g为当前进化代数，G为设定的最大进化代数，Pc,max和Pc,min为设定的最大和最小交叉概率,Pm,max和Pm,min为设定的最大和最小变异概率，k为调整系数。本文取Pc,max=0.8,Pc,min=0.6,Pm,max=0.08，Pm,min=0.05，k=10。

3.5 移民策略

为增加群体多样性，防止进化中因封闭竞争而导致的早熟，IGA引入定期移民策略[12，13]：每隔M代采用一次移民操作淘汰一部分个体，并引入相同数目的外来移民及时补充到群体中。淘汰的个体(假设为N个)包括种群中重复的个体以及适应度最小的10%的个体，外来移民则从随机产生的1.5N个个体中择优选出。本文取M=3。

3.6 终止条件及局部爬山

遗传算法的局部搜索能力弱，导致进化后期群体中最优解改善的速度大为降低，这时可终止遗传进化而引入爬山法完成局部寻优。具体操作过程为：以当前搜索到的最优解和次优解为起点，进行单个脉冲的局部寻优，分别经过36步邻域搜索即可完成爬山操作(40个候选脉冲位置中不重复搜索)，从中确定最优的一组解。这里，遗传进化的终止条件为以下两种情形之一：

(1)达到设定的最大进化代数G；

(2)种群中最优个体适应度值连续L代未发生变化。本文取L=5。

其中，情形(2)是执行局部爬山操作的前提条件。

3.7 改进型遗传算法流程

改进型遗传算法的流程用伪代码描述如下：

Procedure IGA

begin

t=1

对第七代种群P(t)初始化和适应度评

while不满足终止条件

对P(t)精英保存

对P(t)选择、交叉和变异，产生P(t+1)

对P(t+1)适应度评价

对P(t+1)精英替换

if满足移民条件

对P(t+1)移民

end if

t=t+1

end while

if满足局部爬山条件

对P(t)局部爬山

end if

输出最优解

end

4 IGA在代数码书搜索中的应用

将改进型遗传算法(IGA)应用于ITU-T G.729A语音编码器的代数码书搜索，以检验该算法的性能。本文代数码书搜索算法的搜索量(Load)统一用个体适应度函数的计算次数来衡量[7]，客观合成语音质量用分段信噪比(SegSNR)和ITU-T P.862建议的感知语音质量评价(PESQ)[14]衡量。测试所用语音材料如表3所示。遗传算法的参数设置：种群大小PopSize=25，最大进化代数G=12，每次实验运行30次求平均值。对于SGA：Pc=0.8，Pm=0.05。

表3 测试语音材料Table 3 Speech test materials

实验1：选取一段语音材料F1对IGA进行性能测试，结果如表4所示。其中，IGA1～IGA5均是从IGA中除去了某种操作(或者相应地保留与SGA一致的操作)的算法，这些操作依次为：经验式随机初始化种群、混合选择算子、自适应交叉和变异算子、移民策略、局部爬山搜索机制。从表4可以得出以下结论：IGA使用的经验式的随机初始化方法加快了全局优化速度、提高了搜索效率；IGA采用的混合选择算子、自适应交叉、变异算子和移民策略，一方面保证了算法的收敛性，另一方面有效地维持了种群的多样性、抑制了早熟收敛；IGA引入的局部爬山搜索机制使其搜索量有所增加，但是明显地改善了搜索质量，这弥补了GA局部搜索能力弱的缺陷。

表4 IGA性能测试Table 4 Performance test for IGA

实验2：将IGA与全搜索(FS)、深度优先树搜索(DFTS)和基本遗传算法(SGA)进行对比，表5、表6和表7分别给出了4种算法在搜索量、SegSNR和PESQ上的对比结果。从中可以得出以下结论：

(1)对比SGA，IGA灵活的算法终止条件使其搜索量有所降低，而且合成的语音品质也要好于SGA，因此IGA具有更高的搜索效率；

(2)对比DFTS，IGA在搜索量和语音品质上均要略胜于DFTS，这表明IGA具有较强的全局搜索能力；

(3)对比FS，IGA减少了大约96.6%的搜索量，却使合成语音品质稍微降低，这显示出IGA对于大容量码书搜索的优越性。

因此，本文提出的基于IGA的代数码书搜索方法是可行、有效的。

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

表6 SegSNR 对比Table 6 Comparison of SegSNR dB

表7 PESQ对比Table 7 Comparison of PESQ

5 结束语

本文针对基本遗传算法易于早熟收敛、全局优化速度缓慢和局部搜索能力弱等缺点，提出改进型遗传算法(IGA)，将其应用于G.729A语音编码器的代数码书搜索中，并与全搜索、深度优先树搜索和基本遗传算法进行了比较，仿真结果表明了IGA的可行性和有效性,从而为研究代数码书搜索方法提供了新思路。同时应注意到，遗传算法由于含有选择、交叉和变异等操作算子，搜索过程要比标准算法复杂一些，在实时应用中还有待进一步优化。本文所述仅是GA用于代数码书搜索的一隅。对于其它诸如3GPP AMR、AMR-WB和ITU-T G.722.2等高速率模式下脉冲数更多、结构也更复杂的代数码书，如何充分利用GA搜索的全局性和内在并行性，是值得进一步研究的问题，相信GA的优势会在其中得到更好的发挥。

参考文献：

[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] 周明,孙树栋.遗传算法原理及应用[M].北京:国防工业出版社,1999.

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

[7] 徐自励,王永德,何培宇.基于遗传搜索算法的码激励线性预测编码[J].四川大学学报(自然科学版),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] 王小平,曹立明.遗传算法——理论、应用与软件实现[M].西安:西安交通大学出版社,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] 宋平,张焰,蓝毓俊,等.改进遗传算法在配电网重构中的应用[J].上海交通大学学报,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] 田延硕.遗传算法的研究与应用[D].成都：电子科技大学,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].北京航空航天大学学报,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].系统仿真学报,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] 王全国,王三民,袁茹.三维循环对称结构的多目标多约束拓扑优化算法研究[J].西北工业大学学报,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].