2 0 0 5 中国控制与决策学术年会论文集P r o c e e d i n g so f2 0 0 5C h i n e s eC o n t r o la n dD e c i s i o nC o n f e _ e c e9 0 3基于混合粒子群的矢量量化索引值分配方法陈倩，杨建刚( 浙江大学计算机学院，浙江杭州3 1 0 0 2 7 )摘要：矢量量化是一种有鼓的参数压缩方法，台理地给码书矢量分配二进制索引值，可以有效降低传输过程中由于信道误差引起的传输性能下降提出一种基本粒子群算法和遗传算法中选择和交叉算子相结合的混合粒子群算法，井把此算法用于索引值分配实验表明此方法简单，客品实现，并且收敛速度快，效果明显美键词：矢量量化 索引值分配 混合粒子群算法Ah y b r i dP S Ob a s e dm e t h o df o rV Qi n d e xa s s i g n m e n tC I - E NQ i a n ，Y A N GJ i a n g a n g( C o l l e g eo fC o m p u t e rS c i e n c e ，Z h e j i a n gU n i v e r s i t y ，H a n g z h o u3 1 0 0 2 7 ，C h i n a C o r r e s p o n d e n t C H E NQ i a nE m a i l 】m a r c h z 1 1 6 5 c o r n )A b s t r a c t ：V e c t o rq u a n t i z a t i o ni sav e r ye f f e c t i v ec o m p r e s s i o nm e t h o d Ab i tc h a n g e di n t e r f e r e di n d e xv a l u ei sa s s i g n e dt oc o d e v e c t o r sr e a s o n a b l e l y w h i c hc a nr e d u c ep e r f o r m a c ed e c r e a c ei nt r a n s m i s s i o nc a u s e db yc h a n n e le r r o r s Ah y b r i dP S Oa l g o r i t h mi sp r e s e n t e dt os o l v et h ei n d e xa s s i g n m e n tp r o b l e m T h ea l g o r i t h mc o m b i n e sb a s i cP S Ot h e o r yw i t hs e l e c t i o na n dc r o s s o v e ro p e r a t o r so fG e n e t i cA l g o r i t h m E x p e r i m e n t sS h O Wt h a tt h ea l g o r i t h mh a st h ec h a r a c t i s t i eo fs i m p l ei m p l e m e n t ，q u i c kc o n v e r g e n c e ，a n do b v i o u se f f e c t K e yw o r d s v e c t o rq u a n t i z a t i o n ；i n d e xa s s i g n m e n t ；h y b r i dP S O1 引言用矢量量化技术进行压缩编码是低码率传输中经常使用的编码方法传输信道噪声的影响会使解码后的矢量参数产生严重的失真给码书矢量合理 地分配二进制索引值可以有效地改善量化器的性能 1 。，因为给相互比较接近的码书矢量分配汉明距离较小的索引值后，当信道差错引起一个索引值被错误解码时，解码后的码书矢量会与编码端选择的原码书矢量比较接近，可以近似认为是无错解码索引值的分配问题本质上是一个组合优化问题，很多文献都提出了各种各样的算法文献 2 提出一种基于上边界近似方法的二进制交换算法来寻找局部最优码矢的索引值分配，但是这种方法找到的最优解是局部最优文献 3 3 将并行遗传算法应用于索引值分配中文献C 4 用模拟退火算法解决索引分配问题这两种方法实现起来都比较复杂，而且收敛速度慢因此本文提出使用粒子群优化( P S O ) 算法来搜索问题的全局最优解，并且引入遗传算法中的选择和交叉算子，使算法更适合组合优化问题实验表明，这种混合粒子群算法实现简单，收敛速度快，而且能有效克服信道误差引起的性能下降 2 基本粒子群( P S O ) 优化算法原理P S O ：“”算法是由K e n n e d y 和E b e r h a r t 提出的一种启发式搜索技术它源于对鸟群捕食行为的研究一群鸟在随机搜寻食物，如果这个区域里只有一块食物，那么搜寻目前离食物最近的鸟的周围区域是最简单有效的策略受到这种行为的启示，可将问题的解对应于空间中鸟的位置，这些鸟被看作维搜索空间中一个没有体积和质量的粒子每个粒子在搜索空间中以一定的速度飞行，这个速度根据它本身的飞行经验和同伴的飞行经验来动态调整粒子群的初始位置和速度是随机分布的，并且按照空间划分为几个区域，在每次迭代过程中，粒子通过跟踪两个极值来更新自己：一个极值是粒子本身在迭代过程中找到的自身的最优解，称之为个体极值+ 用p b e s t 表示；另一个极值是整个种群目前找作者简介：陈倩( 1 9 7 8 一) 女浙江富阳人博士生，从事模式识别、神经网络的研究9 0 42 0 0 5 中国控制与决策学术年会论文集到的最优解，这个极值是全局极值，用g b e s t 表示找到个体极值和全局极值后，粒子需要更新自己的速度和位置假如粒子i 的信息可以用D 维向量表示，位置可以用X 。；( z n z n ，z 。) 表示，速度为V 。一( ”。矾。，r I D ) ，而速度和位置的更新方程为t J 1 = 西+ C j r a n d ：( p b e s t , k z z b ) +c 2 r a n d ；( g b e s t ：一z 0 ) ，( 1 )z 铲1 一工备+ 口才1 ( z )其中：。0 是粒子i 在第k 次迭代中第d 维的速度，c ，和c 。是学习园子，用来调节向全局最好粒子和个体最好粒子方向飞行的最大步长，r a n d 。和r a n d 。是 o ，1 之间的随机数。z 0 是粒子i 在第k 次迭代中第d维的当前位置为了防止粒子远离搜索空间，粒子的每一维速度巩都被限制在 一。一一，。一 之间 3混合粒子群优化的索引分配方法3 1 优化函数的选取矢量量化系统包括一个预先确定的码矢集合( 码书) ，Y b 。，Y 。，y ”一1 I Y R 。) N 为码书长度，用来传输码书的二进制索引值b 一( 0 ，l ，l =l o g 。N 索引值在传输信道的发送端被发送，通常其接受端收到的也是一系列二进制值信道噪声对索引值可能导致解码矢量的严重失真，这个失真用矢量之间的均方误差进行度量，即 o d ( X ，r ) 一( z ：一y ) 2 ( 3 )f 一1 所有信道误差引起的总平均矢量失真可以表示为一 D = 葡1 P ( V 。) P ( b ( V ，) t b ( V 。) ) d ( V 。，V ，) I 一1J = 1( 4 )其中： T 是码奉的长度，P ( n ) 根据输人矢量统计特征得到的先验概率，P ( 6 ( y ，) | b ( V 。) ) 是输人矢量V 。的索引值被误传成矢量V ，的索引值的条件概率，d ( V 。，V ，) 是矢量y 与矢量y ，之间的均方误差本文的目标是在码本和信道误差概率一定的情况下使总平均矢量失真最小，所以优化函数可以表达为m i n D 一，NN 寺P ( V - ) P ( b ( V ，) 1 6 ( y i ) ) d ( y 。，V ，) ( 5 ) 一1，一1 3 2 混合粒子群算法基本的P S O 算法的搜索过程很大程度上依赖p b e s t 和g b e s t ，所以它的搜索区域受到p b e s t 和g b e s t 的限制而遗传算法中的选择机制用来选择相对较好的区域和舍弃较差的区域可以更合理地分配有限的资源遗传算法中的交叉操作是针对各个染色体的基因进行操作。这种操作比较适合组合优化问题基本P S O 算法和遗传算法中的选择、交叉机制相结合，就形成了混台P S O 粒子群算法口 下面先介绍用于粒子群算法的选择和交叉算子选择：混台粒子群的选择机制与遗传算法中用到的十分相似混台P S O 算法计算每个粒子基于当前位置的适应值，并按照适应值大小排序，按照一定的比例将差的粒子当前位置和速度淘汰，复制好的粒子但是保留每个粒子的当前最好位置p b e s t ，一直到满足粒子数量为止交叉：假设有长度为8 的码本，两个粒子的当前位置表示为尸1 一( 2 ，1 ，8 ，7 ，4 ，6 ，5 ，3 ) ，P 2 一( 3 6 ，1 ，8 ，7 ，5 ，4 ，2 ) 随机选取一个交换点r ，对P ，来说，当k r 时，从只中从头到尾选取一个P ，中从头到r 位置没有的值，替代掉P ，中 位置的值如此，一直到P ，中所有的值本更新，所得到的P 。就是更新后的串算法图解如图1 所示P ，E j 工r 口j 工工正丑三工妇围1交叉过程混合粒子群算法如下：1 ) 设定粒子数M ，最大迭代次数C ，粒子的初始位置为随机分配的索引值序列2 ) 根据式( 3 ) 为每个粒子计算适应值，设置当前适应值为粒子个体极值p b e s t ，根据个体极值计算全局极值g b e s t 3 ) 按照一定的比例对粒子群进行选择4 ) 选择后的每个粒子位置与全局极值对应的粒子位置进行交叉，得到新的粒子位置；每个新的粒子位置再与全局极值对应的粒子位置交叉进行更新5 ) 对每个粒子位置计算适应值，并且与当前个体极值比较，太则更新个体极值对应的粒子位置，否则不变根据所有的个体极值更新全局极值和全局极值对应的粒子位置6 ) 计算当前迭代次数，如果超出最大迭代次数，则结束；否则重复3 ) 6 ) 陈倩等：基于混合粒子群的矢量量化索引值分配方法9 0 57 ) 输出最大极值及其对应的粒子位置，这个粒子位置就是所要求的索引值分配序列4交验实验中采用矢量量化后的L P C 语音参数作为输人矢量，并在噪声信道上传输从一个说话者中录制了1 j O 个单词的语音样本这些样本取样频率为j 6k H z ，然后从每个样本长度为2 0m s 豹分帧中提取l o 维的L P C 参数用l ，B G 算法为这些L P C 参数产生长度为1 6 ，3 2 ，6 4 和1 2 8 的码本，用混合粒子算法和随机分配两种方法为码矢量进行索引值分配其中混合粒子群算法中使用如下初始参数；粒子数目3 2 ，选择比例0 z ( 即保留1 5 的粒子进行复制) ，最大迭代次数60 0 0 次，然后把生成的索引值不同的噪声在信道中进行传输，通过计算总平均矢量失真作为评价的标准图2 和图3 分别显示了在码本长度为3 2 和1 2 8的情况下，对不同的码本进行1 0 次传输后得到的平图信道差错概率圈3 码本长度为1 2 8 时总矢量平均失真均矢量失真可以明显地看到，当信道噪声增加时，两种方法导致总平均矢量失真也在增加，但是采用混合粒子群算法对码矢量分配台理的索引值分配