人工蚁群聚类码书设计算法.docVIP

人工蚁群聚类码书设计算法 胡宏梅1，董恩清2 (1.健雄职业技术学院, 江苏 太仓 215411；2.苏州大学电子学院，江苏 苏州 215006) 摘 要：文中将频率敏感算法引入到基本的蚁群算法中，提出了一种改进的蚁群聚类码书设计算法。在提出的码书设计算法中采用LBG码书优化准则。由于引入了频率敏感算法，通过增加失真测度来减小蚂蚁重复选择同一个聚类的可能性，从而增加了聚类选择的随机性，避免停滞现象发生而陷于局部最优解，有效地提高了其全局有哪些信誉好的足球投注网站能力。通过仿真实验表明提出的频率敏感蚁群聚类码书设计算法在码书设计的收敛性和码书性能方面较其他方法都有明显改善。 关键词：蚁群算法；矢量量化；码书设计；聚类 中图法分类号: TN912.3 　　 文献标识码:A 1 引言( 矢量量化(Vector Quantization ,VQ）[1]是语音识别、语音编码和图像压缩的关键技术。它具有压缩比大、编码速度快等优点，其重要性在实际的应用逐渐显示出来。矢量量化研究包含有：码书设计、码书有哪些信誉好的足球投注网站和码字索引。在这三项研究中，码书设计是矢量量化的关键技术。 自Linde、Buzo和Gray于1980年提出LBG码书设计算法以来[2]，针对其初始码书选择具有较强的敏感性的缺点，出现了很多种新型的码书设计算法，如k-均值算法(K-Mean)、模拟退火码书设计算法(Simulated Annealing, SA)、遗传码书设计算法(Genetic Algorithm,GA)以及禁止有哪些信誉好的足球投注网站码书设计算法(Tabu Search,TS)等等[3~6]。这些算法在一定程度上提高了码书的性能，但同时也存在一些缺点，如易于达到局部极小点及缺乏全局有哪些信誉好的足球投注网站的能力。 蚁群算法（Ant Colony Algorithm）是近几年提出的一种新型的模拟进化算法，由意大利学者M.Dorigo等人提出的[7],已成功应用于求解旅行商问题（TSP）等研究中。它采用了分布式并行计算机制，易于与其它方法相结合，不仅具有较高的鲁棒性，而且具有较强的全局有哪些信誉好的足球投注网站能力。本文将频率敏感算法引入到基本的蚁群算法中，得到一个改进的蚁群聚类算法，将该改进的算法称为频率敏感蚁群聚类算法。通过采用频率敏感蚁群聚类算法，利用大量蚂蚁并行地对矢量迭代聚类，并在提出的码书设计算法中采用LBG码书优化准则。这样使码书设计真正是在全局优化过程中得到的全局最优解。 2 蚁群算法 蚁群算法包含适应和协作两个基本阶段。在适应阶段，各候选解根据积累信息不断调整自身结构，当某一路径上经过的蚂蚁越多，信息素数量越大，则该条路经越容易被选择为候选解；在协作阶段，候选解之间通过信息交流，以期望产生性能更好的解。为了更清楚地说明蚁群算法的数学模型，下面以求解典型的TSP问题为例进行说明。 2.1 转移概率准则 (1) 其中表示在t时刻第k只蚂蚁由城市i转移到城市j的概率，表示t时刻蚂蚁由位置i转移到位置j的信息量；初始时，各条路径上信息量相等，设(c为常数)，m为蚂蚁总数，n为总的路径数，第k只蚂蚁运动过程中，根据各条路径上的信息量决定转移方向。，分别表示第k只蚂蚁在运动过程中所积累的信息及启发式因子在蚂蚁选择路径中所起的不同作用；表示由城市i转移到城市j的期望程度，可根据某种启发式算法确定；记录第k只蚂蚁所走过的路径表；记录第k只蚂蚁下一步可能走的路径。与实际蚂蚁不同的是，人工蚁群系统具有记忆功能，随时间的推移禁止表和都做动态调整，这样就避免了重复选择已走过的路径。 2.2 信息素更新 为了避免“早熟”现象，在每只蚂蚁或所有蚂蚁均完成一次路径选择循环后，各路径上的信息素均按下式进行更新： (2) 其中，参数表示信息消逝程度，表示第k只蚂蚁在本次循环中留在路径ij上的信息增量，表示所有蚂蚁在本次循环中留在路径ij上的信息总增量。 根据信息增量求取的方法，文献[8]给出了三种不同的蚂蚁算法模型：Ant-Cycle模型、Ant-Quantity模型及Ant-Density模型。 在Ant-Cycle中， (3) 式中，Q是信息素强度，它影响算法的收敛速度，表示第k只蚂蚁在本次循环中所走路径的总长度。 在Ant-Quantity中， (4) 在Ant-Density中， (5) 在以上三种模型中，(4)和(5)式中利用的是局部信息，而(3)利用的是全局信息。对于求解不同的问题需要采用不同的更新方法，如需要利用整体信息得到一个全局优解，通常采用(3)式。 3 蚁群聚类的码书设计算法 3.1 码书设计 设表示由N个训练矢量所构成的训练序列，码书设计过程就是寻求将这些训练矢量分成M个子集的一种最佳聚类方案。而子集的质心矢量用来作为码字，这些子集又称之为胞腔。码书设计的目的是使平均失真最小，