基于粒子群算法的码书设计研究

1、基于粒子群算法的码书设计研究浦灵敏,胡宏梅 (健雄职业技术学院， 江苏 太仓 215411)摘 要：在基于粒子群算法码书设计研究中，提出采用随机概率扰动的方式作为基本粒子群算法的全局极值更新条件，从而增加全局最优区域的搜索能力，避免了粒子过早的“趋同性”。关键词：矢量量化；码书设计；粒子群算法中图分类号：TN 911 文献标识码：A1引言码书设计是矢量量化的关键技术，码书性能的好坏直接影响到矢量量化的效果。研究码书设计算法的目的就是寻求有效的算法尽可能找到全局最优或接近全局最优的码书以提高码书性能，并尽可能减少计算复杂度。由Linde、Buzo和Gray于1980年首先提出一种有效和直观的矢量

2、量化码书设计算法LBG算法1。该算法容易实现、理论严密，但计算量大且易陷入局部最优解。针对这些问题，学者们开始提出各种改进的算法，如模拟退火码书设计算法2、禁止搜索码书设计算法3、神经网络码书设计4以及蚁群算法码书设计5等，实验证明，这些算法均在不同程度上改善码书质量，但均存在不同的问题。粒子群算法（Particle Swarm Optimization, PSO）6是在1995年由美国社会心理学家James Kennedy和电气工程师Russell Eberhart共同提出的。自粒子群算法提出以来，由于它的计算快速性和算法本身的易实现性，引起了国际上相关领域众多学者的关注和研究。PSO算法最

3、早应用于人工神经网络的训练方法，随后，在函数优化、约束优化、极大极小问题、多目标优化等问题中均得到了成功的应用。针对PSO应用到码书设计中容易陷入局部最优解的问题，又由于模拟退火算法具有全局搜索能力的特点，提出将模拟退火算法及PSO共同应用到码书设计中，实验证明，本文算法有一定的可行性。2标准粒子群算法标准粒子群算法78（PSO）是一种有效的全局寻优算法，它是基于群体智能理论的优化算法，通过群体中粒子间的合作和竞争产生的群体智能指导优化搜索。与进化算法比较，PSO也采用了“群体”和“进化”的概念，同样是依据个体（微粒）的适应值大小进行操作。所不同的是PSO保留了基于种群的全局搜索策略，且它不象

4、其他算法那样对于个体使用进化算法，而是将每个个体看作是在n维搜索空间中的一个没有重量和体积的微粒，并在搜索空间中以一定的速度飞行。该飞行速度由个体的飞行经验和群体的飞行经验进行动态调整。在每次迭代中，每个个体（微粒）根据下式来调整它的飞行速度和位置： (1) (2)其中，下标“j”表示粒子的第j维，“i”表示粒子i，“t”表示第t代，、为加速常数，通常在02间取值，为两个相互独立的随机函数。粒子群算法的基本实现步骤如下，步骤1，在初始化范围内，对粒子群进行随机初始化，包括随机位置和速度。步骤2，计算每个粒子的适应值。步骤3，对于每个粒子，将其适应值与所经历过的最好位置的适应值进行比较，如果更好

5、，则将其作为粒子的个体历史最优值，用当前位置更新个体历史最好位置。步骤4，对每个粒子，将其历史最优适应值与群体内或邻域内所经历的最好位置的适应值进行比较，若更好，则将其作为当前的全局最好位置。步骤5，根据式（1）和式（2）对粒子的速度和位置进行对比。步骤6，若未达到结束条（件通常为足够好的适应值或达到一个预设最大代数），则返回步骤2。3基于粒子群算法的码书设计基于粒子群算法的码书设计9是利用标准粒子群算法有良好的全局搜索性，使每个粒子对要聚类的训练矢量进行搜索、聚类，每个粒子都能得到一组码书，更新胞腔质心。若满足了终止条件，则输出最好的那组码书；否则，再重新聚类，直到产生性能足够好的码书为止。

6、3.1粒子群码书设计算法的编码表示与适应度选择粒子群算法采用实数编码，一个编码对应一个可行解。在本文算法中，采用的是基于聚类中心的编码方式，也就是每个粒子的位置是由n个聚类中心组成。粒子除了位置以外，还有速度和适应值。由于训练矢量维数为d，因此粒子的位置X是维变量，所以粒子的速度V也应当是维变量，另外每个粒子还有一个适应度。当粒子初始位置确定时，也就是聚类中心确定时，为训练矢量集，则聚类的划分由下面的最近邻法则决定。若满足： (3)则属于第j类。聚类完后，可得第j类的类内离散度为。对于某粒子，按照以下方法计算其适应度：（1）按照最近邻法则（3）式，确定与该粒子对应的聚类划分。（2）根据聚类划分

7、，计算类内离散度和，即各类中矢量到对应类中心的距离的总和。（3）个体的适应度可采用，其中是总类内离散度和，L是调节常数，根据具体情况定。这样个体的适应度与离散度和负相关，离散度和越小，个体适应度越大。3.2 粒子群码书设计算法的实现步骤步骤1，种群的初始化。在初始化粒子时，先将每个样本随机指派为某一类，作为最初的聚类划分，并计算各类的聚类中心，作为初始粒子的位置编码，计算粒子的适应度，并初始化粒子的速度。若有N个粒子，则反复进行N次，共生成N个初始粒子群。步骤2，对每个微粒，比较它的适应度和它经过的最好位置Pbest的适应度，如果更好，更新Pbest。步骤3，对每个粒子，比较它的适应度和群体所

8、经过的最好位置Gbest的适应度，如果更好，更新Gbest。步骤4，根据粒子群算法的速度和位置更新公式（1）、（2）调整粒子的速度和位置。步骤5，对新个体进行LBG算法优化。对于新一代粒子，按照以下的LBG算法进行优化：（1）根据粒子的聚类中心编码，按照最近邻法则，来确定对应该粒子的聚类划分；（2）按照聚类划分，计算新的聚类中心，即形成新的码字，更新粒子的适应值，取代原来的编码值。步骤6，如果达到结束条件（形成足够好的码书或最大迭代次数），则结束，否则转步骤2。4 改进的粒子群码书设计算法粒子群算法的本质是利用本身信息、个体极值信息和全局极值三个信息，指导粒子下一步迭代位置。但是粒子群在追逐最

9、优粒子过程中，随着它接近最优粒子，其速度越来越小，因此粒子群表现出强烈的“趋同性”，容易陷入局部极小点10。本文将针对该项缺陷，提出引进模拟退火算法对其进行相应改进研究。4.1 改进算法的思想在粒子群算法的码书设计算法中，粒子通过更新其全局最优和自身最优的方法来搜索全局最优解，进而设计性能较好的码书。但在其更新过程中，粒子只有遇到更好解的时候才会更新极值，这样做缩小了粒子的搜索邻域，使其很容易达到收敛，陷入局部最优。本文提出引进模拟退火算法对全局极值的更新条件做了改进，基本思想如下：当新粒子的适应值大于当前全局极值时，系统一定接受该粒子；当新粒子适应度小于全局极值时，按式（4）计算出模拟退火概

10、率p，当p大于阈值r的时候，r为 (0,1) 间的随机值，也接受该粒子，否则不接受。模拟退火概率计算如下： (4)式中为第t次迭代的温度，K为降温系数；为当前粒子失真变化， ， 为第i个粒子的当前适应值，为当前全局最优适应值。改进算法的全局极值更新条件采用了随机概率扰动接受的方式，既接收优化解，也可以接受恶化解，增大全局搜索范围。很大时，使局部极值与全局极值之间的差值很大，接受概率比较大，可以接受的较差解比较多；不是很高时，使差值小的状态易于接受，即中温时，易于接受与当前状态相比不是很差的解；很小时，差值足够小的状态才易于接受，即低温时，只能接受与当前状态相比差很少的解。当经过足够长时间的温度

11、下降过程，固体达到最小能量状态时，相应也达到了全局最优解。4.2 实验结果本文主要是对语音信号进行矢量量化码书设计。这里的训练矢量为8kHz采样16比特PCM格式的原始语音波形数据，每个矢量为5ms，即40维矢量。设计的码书大小分别为512、1024。算法中的参数选取源于经验值，粒子数N=30，迭代次数T=10，、分别为2。关于惯性权重w的选取，根据其对粒子搜索影响的特点，采用了 (5)其中的取为0.9, 取为0.4，iter为迭代次数，为最大的迭代次数。采用这样的惯性权重，使得开始时有较好的全局收敛能力，随着迭代次数的增加，w不断减小，晚期时使得算法具有较强的局部收敛能力。本文分别从客观和主

12、观两方面来评价改进算法及原算法设计码书的性能。客观评价指标包括类间离散度、矢量量化不均匀度及全局极值更新性能。而主观评价指标还是依靠人的听觉感知。类间离散度是指各个胞腔质心间的距离，是一个用来评价码书设计算法优劣的有效指标。其值越大，码书的性能就越好。计算公式如下： (6)其中、分别是指第i、j胞腔的质心，T为转置计算。矢量量化不均匀度用来衡量各个胞腔所聚类的训练矢量数量是否均衡。其值越小，码书性能越好。假设训练矢量的总数为N个，类的个数即胞腔的个数为M个，定义类的均衡矢量数为： (7)其中表示向下取整。在聚类完成后，属于第k个胞腔的训练矢量数量是， 则定义矢量量化不均匀度为： (8)表1为标

13、准粒子群码书设计算法及改进算法在类间离散度及矢量量化不均匀度上的对比结果。表中显示，在512及1024两种码书的情况下，改进算法的类间离散度均大于基本粒子群算法，而矢量量化不均匀度却均小于基本粒子群算法，说明了改进算法比起基本粒子群算法能更好地改善码书性能。除了这两个指标外，还可以从全局极值的更新性能上比较，可以看出它们趋向全局搜索的能力。通过分析可知，若有N个粒子，迭代次数为T，基本算法中全局极值更新次数不多于T次，而改进算法中全局极值更新次数可达到次。图1和图2 分别为码书大小为512和1024时标准粒子群码书设计算法和改进算法对全局极值更新过程，反映出这两种算法的全局搜索能力。算法中T=

14、10，可以得到基本算法更新次数最多为10次，而改进算法的更新次数可达。从图中可以看出标准粒子群算法更新次数小于10次，易达到收敛，而改进算法却能较长时间更新极值，其全局搜索能力远远高于基本粒子群算法，能更好地改善码书的性能。一个通过语音矢量量化码书编码后重构语音质量主要依靠人的听觉感知主观评价。这里采用非正式语音听力测试语音质量。由于码书大小为512和1024，所以不可能得到高质量的重构语音，但依然能测试出两种算法的性能优劣。通过试听，可以发现基本算法所重构的语音具有轻微的模糊，有一定的噪声，信号不稳定，而改进算法所重构的语音无论是从清晰度、自然度还是理解性上都要好过基本粒子群算法所重构的语音

15、。表1 类间离散度及矢量量化不均匀度对比码书大小 粒子群算法码书设计改进后的粒子群算法类间离散度不均匀度类间离散度不均匀度5124.1256e-006386.07125.6545e-006361.345610240.5452e-006822.36940.7124e-006712.03125 结论本文介绍了基本粒子群算法及其在码书设计中的应用。重点分析了基本粒子群算法码书设计原理，针对其不足，提出了相应的改进算法。为提高全局搜索能力，在改进的算法中采用随机概率扰动接受作为全局极值更新条件。最后通过将改进算法应用到语音矢量量化实验中来验证其有效性。 图1 码书大小为512的全局更新对比图 图2 码

16、书大小为1024的全局更新对图参考文献1 -95.2 Wenhuan Xu, Asoke K.Nandi, “Novel quantiser design using reinforced learning as a pre-process” , Signal Processing, 2005, 7 (85): 1315-1333.3 Shin-Ming Pan, Kuo-Sheng Cheng, “An evolution-based tabu search approach to codebook design”, Pattern Recognition, 2007, 2 (40): 47

17、6-491.“A novel training scheme for neural-network-based vector quantization and its application in image compression”, Neurocomputing, 2004, 61: 421-427.“Application of ant K-means on clustering analysis”, Computers&Mathematics with Applications, 2005, 50(1012): 1709-1724.6 Nagoya, Japan, 1995.7

18、 “A Mortified Particle Swarm Optimization”, Proceedings of the IEEE International Conference on Evolutionary Computation. IEEE Press, Piscataway, NJ, 1998, 69-73.8 Shi Y, Eberhart R C, “Empirical Study of Particle Swarm Optimization”.In: Proceedings of the 1999 Congress on Evolutionary Computation, Piscataway, NJ, IEEE Service Centers, 1999, 1945-1950.9 刘靖明，韩丽川，“基于粒子群的K均值聚类算法”，系统工程理论与实践，2005，6：54-58。10 Xie X F, Zhang W J, Yang Z L,“Overview of particle swarm optimization”, Control and Decision, 2003, 18(2): 129-134.Study of Code