（通信与信息系统专业论文）群体智能算法在矢量量化及求解tsp问题中的应用研究.pdf

群体智篷塞法在矢壁量丝垦查望t s p 问题中的应用研究 中文摘要 群体智能算法在矢量量化及求解t s p 问题中的应用研究 中文摘要 本文较系统地综述了群体智能算法和矢量量化数据压缩理论。特别是矢量量化码 书设计和码字搜索的发展历程和研究现状。回顾了经典的矢量量化码书设计算法 l b g 算法和传统的码字搜索算法探讨了新兴的群体智能算法在解决诸如t s p 组合问题的性能，并针对经典的矢量量化码书设计算法的固有缺陷，提出了一种将群 体智能算法和l b g 算法结合的码书设计算法。仿真实验证明了它在图像压缩编码中 的有效性。传统的码字搜索算法穷尽搜索算法会随着码书规模的增大和码字维数 增加，计算量急剧增加。为了克服该缺陷，重点探讨了矢量量化码字搜索算法问题。 本文在变换域内搜索码字，并引入c h e b y s h e v 距离测度和p d s 算法仿真实验表明 此改进算法能快速有效地搜索码字。 群体智能算法包括蚁群算法和微粒群算法。这两种算法都具有很强的鲁棒性和并 行性。本文在码书设计中，根据l b g 算法具有较快地发现局部最优解的能力，微粒 群算法具有全局搜索晟优的性能，将这两种算法结合提出了一种新的优化策略，设计 出了性能良好的码书。本文为了研究群体智能算法的特性，在传统的组合优化t s p 问题上用经典的遗传算法与之对比，仿真实验表明智能算法具有一定的优势。最后对 全文的工作进行了总结，对矢量量化技术和群体智能算法的进一步研究进行了展望。 关键词：群体智能，矢量量化，码书设计，码字搜索t s p 作者：蔡光跃 指导教师：董恩清 墅竺! 篓! ! ! 堡! ! ：竺竺! ! 型! 堡竺! ! 垒坚! ! 堡竺竺! 殳竺生竺!坐型 r e s e a r c ho ft h es w a r m i n t e l l i g e n c ea l g o r i t h m o nv e c t o rq u a n t i z a t i o na n dt s p a b s t r a c t t h es w m - mi n t e l h g e n c ea l g o r i t h ma n dt h et h e o r yo fv e c t o rq u a n t i z a t i o n ( v q ) d a t a c o m p r e s s i o na r es u m m a r i z e ds y s t e m i c a l l yi nt h ep a p e r i np a r t i c u l a r , t h ec u r r e n tr e s e a r c h s t a t u sa n dd e v e l o p m e n th i s t o r yo fv qc o d 曲o o kd a s t g na n dc o d w o r ds e a r c ha r ea l s o i n t r o d u c e d t h ec l a s s i c a lm g o f i t h mo fv qc o d e b o o kd e s i 鲈也b ga i g o f i t h ma n d t r a d i t i o n a lc o d e w o r ds e a r c ha l g o r i t h m sa r er e v i e w e d t h es w a m ii n t e l l i g e n c ea l g o r i t h mo n c o m b i n a t i o i lp r o b l e m s 飘l c ha st s p 龇d t s c a s s e d t oo v e r c o r r 峙t h el i m i t a t i o no f e l a s s i c a l a l g o f i t h mo fv qc o d e b o o kd e s i g n , a r ti m p r o v e da l g o d t h mt h a tc o m b i n e st h es w a m i n t e l l i g e n c ea l g o r i t h mv a t ht h el b ga l g o r i t h mi sp r o p o s e d t h cs i m u l a t i o nr e s u l t ss h o w t h ev a l i d i t yo ft h ei m p r o v e da l g o r i t h mi ni m a g ec o m p r e s s i o nc o d i n g t h et r a d i t i o n a l c o d e w o r ds e a r c ha l g o r i t h m f u l la l g e r i t h r a ( f s ) h a s8s e r i o u sd i s a d v a n t a g e , w h o s e c o m p u t a t i o nq u a n t a t yw t l lr i s es h a r p l yw l t ht h ei n c r e a s eo ft h ec o d e b o o ks i z ea n dt h e e , o d e w o r dd i m e n s i o n t h i sp a p e rp r o p o s e sa r le f f e c t i v ea l g o d t h mw h i c hi m p l c r a c n t si n h a d a m a r dd o m a i n , a n dt h ec h e b y s h e vd i s t o r t i o nm c a s b r ea n dp d s a l g o r i t h ma r ea d o p t e d t h e e x p e r i m e n ts h o w s t h e i m p r o v e d a l g o r i t h mc a n s e a r c h c o d e w o r d f a s t e r a n d e f f e c t i v e m es w a r m i m e l l x g e n o e a l g o r i t h m i n c l u d e sa n t c o l o n yo p t i m i z a t l o n ( a c o ) a n d p a r t i c i e s w a r mo p t i m i z a t i o n ( p s o ) a c oa n dp s oh a v eh i g hr o b u s t n e s sa n dp a r a l l e lc h a r a c t e r s b e c a u s el b ga l g o r i t h mc a nf i n dt h el o c a lo p t i m a ls o l u t i o nl a s t l ya n dp s oh a st h ea b n 时 o f s e a r c h i n gt h eg l o b a lo p t i m a ls o l u t i o n , an e wo p t i m a ls t r a t e g yi sp r o p o s e di nt h ep a p e r a b e t t e rc o d e b o o kc a nb ed e s i g n e du s i n gt h ei x c wo p t i m a ls t r a t e g y ，t os t u d yt h ec h a r a c t e r so f t h es w a l t i ii n t e l l i g e n c ea l g o r i t h m , c o m p a r i s o nw t t hg e n e r a h o na l g o r i t h m ( g a ) o nt s p s h o w st h ea d v a n t a g eo ft h e a mi n t e l l i g e n c e f i n a l l y t h ep a p e rw o r k sa r es u m m a r i z e d ， a n ds o m ef a r t h e rr e s e a r c hs u g g e s t i o n sr e g a r d i n gv qa n dt h es w a r mi n t e l h g e n c ea l g o n t h m l i f ep r o v i d e d k e y w o r d s ：s w a r mi m e l h g e n c e ；v e c t o rq u a n t l z a t i o n ( v q ) ；c o d e b o o kd e s i g n ；c o d e w o r d s e a r c h ；t s p 儿 w h r e n b y ：g u a n g y u ec a l s u p e r v i s e db y ：e n q m gd o n g 苏州大学学位论文独创性声明及使用授权的声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含 其他个人或集体已经发表或撰写过的研究成果，也不含为获得苏州大学 或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡 献的个人和集体，均己在文中以明确方式标明。本人承担本声明的法律 责任。 研究生签名：丛竖! 厶日期：! ：! ! ： 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文 合作部、中国社科院文献信息情报中心有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本 人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分 内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名：擞丛 日 期：上：! l ；_一 导师签名：垄堙i 漳一目期：竺! ! 竺1 2导师签名：匀乒坐蜱一目期：竺坐上斗 群体智能算法在矢量量化及求解t s p 问题中的应用研究 第l 章绪论 1 1 课题背景 第1 章绪论 随着计算机和大规模集成电路的飞速发展，数字信号的分析和处理技术得到迅猛 发展，并已经广泛用于通信、雷达和自动化等领域。数字信号的明显优点是便于传输、 存储、交换、加密和处理等。信号必须通过一定的系统进行传输或加工处理。在信息 科学与技术领域中，常常利用通信系统、控制系统和计算机系统进行信号的传输、交 换和处理。信号的传输和处理通常在通信系统中进行，它可分为两大类：一类是传输 模拟信号厂( f ) 的模拟通信系统；另一类是传输数字信号m ) 数字通信系统。与模拟 通信系统相比，数字通信系统具有抗干扰能力强、保密性好，便于传输、存储、交换 和处理等优点。但是在数字通信中，码速率高不仅影响传输效率，而且增加了存储和 处理的负担。因此，在数字通信中通常要对数字信号缸n ) 进行进一步压缩( 模拟信号 ，( f ) 到数字信号“n ) 的量化过程也是一种压缩过程) ，这个过程也是信源编码的一部 分。信源编码在数据传输系统中主要解决的是有效性问题，即通过对信源的压缩、扰 乱、加密等一系列处理，力求用最少的代码传递最大的信息量，使信号更容易传输； 而信道编码主要解决系统的可靠性问题，即运用一些容错技术( 错误纠正及错误掩 盖) ，尽可能使经过信源压缩算法处理过的数据信号在传输过程中不出错或少出错。 数据压缩是信源编码的目的和手段【i 】。数据压缩就是减少分配给指定消息集合或 数据采样集合的信号空间大小。该信号空间可以是物理容积，也可以是时间间隔，还 可以是电磁谱的一部分。压缩的主要目的是尽可能减小传输或存储所需的比特率或者 说是给定通信系统的带宽和存储空间。简单地说，数据压缩是为了在现有系统特陛( 如 频带限制) 条件下满足工作的要求，或者在新系统的设计中降低成本。在通过研究各 种数据压缩算法并将它们应用到实际中去的过程中，人们意识到数据压缩是上个世纪 中后期人类科技飞速发展和进步的一个不可或缺的条件，特别是在计算机日益广泛地 第1 章绪论群体智能算庄在矢量量化及求解t s p 问题中的的应用研究 被各行各业所采用并作为必不可少的工具以及互联网迅速普及的情况下，数据压缩的 意义更加不容忽视。归纳起来可以列为下面几点： ( 1 ) 较快地传输各种信源( 降低信道占用费用) 时间域的压缩； ( 2 ) 在现有通信干线上开通更多的并行业务( 如电视、传真、电话、可视图文 等) 频率域的压缩； ( 3 ) 降低发射机功率能量域的压缩； ( 4 ) 紧缩数据存储容量( 降低存储费用) 空间域的压缩。 数据压缩可以分为可逆压缩( 冗余度压缩) 和不可逆压缩( 有损压缩或熵压缩) 两 大类。熵压缩将导致信息失真，它是不可逆的。若把数据看作信息和冗余度的叠加， 冗余度压缩的工作机理就是去除或者减少数据的冗余度，它是一个可逆过程。量化是 有损数据压缩中常用的技术，基本上可以分为三种，即标量量化、矢量量化和序列量 化。最基本的标量量化每次只量化一个采样，并对所有采样都采用相同的量化器特性 进行量化，而且每个采样的量化都和其它采样无关。矢量量化和序列量化则利用相邻 采样之间的相关性。矢量量化( v q ：v e c t o r q u a n t i z a t m n ) 2 - 5 ) 在量化时用输出组集合( 码 书) 中最匹配的一组输出值( 字) 来代替一组输入采样值( 输入矢量) 。矢量量化的优点 是解码简单、压缩比大。 矢量量化技术的研究涉及多学科领域的理论和技术，如信息论、编码理论、通信 原理、保密技术、信号处理、优化理论、模糊集合论、矩阵分析、神经网络、小波变 换、拓扑学、随机概率理论、预测技术、模式识别等等，矢量量化技术的研究将给这 些理论和技术注入新鲜血液。因此，无论从理论角度还是从应用角度来看，开展对矢 量量化技术的研究，不但具有重要的学术意义，还有极为重要的国防意义和经济意义。 目前，群体智能理论研究领域有两种主要的算法：蚁群算法( a n tc o l o n y o p t i m t z a t i o n ，a c o ) 和微粒群算法( p a r t i c l es w m no p t i m i z a t m n ，p s o ) 。前者是对蚂 蚁群落食物采集过程的模拟，已成功应用于许多离散优化问题。微粒群算法也是起源 于对简单社会系统的模拟，最初是模拟鸟群觅食的过程，但后来发现它是一种良好的 优化工具。 与大多数基于梯度应用优化算法不同，群体智能依靠的是概率搜索算法。虽然概 率搜索算法通常要采用较多评价函数，但与梯度方法及传统的演化算法相比，其优点 2 群体智能算法在矢量量化及求解t s p 问题中的应用研究 第1 章绪论 还是显著的：( 1 ) 无集中控制约束，不会因个别个体的故障影响整个问题的求解，确 保了系统具备更强的鲁捧性；( 2 ) 以非直接的信息交流方式确保了系统的扩展性；( 3 ) 并行分布式算法模型，可充分利用多处理器；( 4 ) 对问题定义的连续性无特殊要求； ( 5 ) 算法实现简单。 群体智能算法易于实现，算法中仅涉及各种基本数学操作，其数据处理过程对 c p u 和内存的要求也不高。群体智能算法只需目标函数的输出值，而无需其梯度信 息。已完成的群体智能理论和应用方法研究证明群体智能算法是一种能够有效解决大 多数全局优化问题的新方法。更重要的是，群体智能潜在的并行性和分布式特点为处 理大量的以数据库形式存在的数据提供了技术保证。无论是从理论研究还是应用研究 的角度分析，群体智能算法的理论和应用研究都具有重要学术意义和现实价值的。 1 2 矢量量化技术的研究现状 在二十世纪六十年代初期和中期，出现了最早的矢量量化思想。h u a n g 和 s c h u l t h e l s s 提出最早的分组量化的基本实现方法，这些最早的研究并没有给出矢量量 化的严格定义。直到1 9 8 0 年由l i n d e ，b u z o 和g r a y 将聚类算法引入到矢量量化器设 计中，提出了一种著名的矢量量化码书设计算珐，即l b g 算麽( 又称为g l a 算珐) 】。随后，现代的矢量量化研究得到了h 益广泛的关注。各国学者以l b g 算法为基 础，针对矢量量化的特点，将神经网络、最优化理论、模糊数学、遗传算法等各种方 法与新思想引入到矢量量化中来，以期得到快速、高效、性能好的矢量量化器，矢量 量化的研究进入了一个飞速的发展时期并且取得了很多成果。二十世纪九十年代，半 导体技术和微电子工艺日臻成熟，d s p ( d i g i t a ls i g n a lp r o c e s s i n g ) 技术已经广泛地应用 于各种领域，d s p 芯片的高速运行和并行处理能力为各种数据压缩算法提供了理想的 实现环境。各国学者也针对d s p 的结构特点对传统的矢量量化技术进行改进，研究 各种适合于硬件实现的矢量量化算法。 矢量量化的研究主要包括三部分，即矢量量化码书设计算法，矢量量化码字搜索 算法，以及后来为减少传输信道中噪声影响而提出的码字索引分配算法。其中最重要 的一点就是如何设计出性能优良的码书，这是整个矢量量化器设计成功与否的关键， 3 第1 章绪论群体智能算法在矢量量化及求解t s p 问题中的的应用研究 是决定矢量量化器性能的主要因素。矢量量化码字搜索算法的研究，就是在设计出性 能优良的码书的基础上，设法减少搜索分配码字所需的计算量，缩短搜索时间，进一 步提高矢量量化器的整体性能。而码字索引分配的研究内容主要是在码书生成的过程 中如何让码字以一种更合理的顺序排序，以便将信道传输过程中，由于信道噪声导致 的数据变更，在数据接收端引起的额外误差降低到最小，同时也尽可能地降低搜索码 字的计算复杂度和搜索时间。 1 2 1 矢量量化码书设计算法研究现状 二十世纪八十年代，著名的l b g 算法作为一种非常有效的码书设计算法提出以 后，矢量量化码书设计算法的研究得到了广泛的关注和研究，并且取得了很多成果。 这些算法大致可归为五类：( 1 ) 传统码书设计算法及改进算法；( 2 ) 基于神经网络的码 书设计算法，如学习神经网络，竞争学习神经网络，自组织特征映射神经网络等；( 3 ) 基于全局优化技术的码书设计算法，如随机松弛算法，遗传算法，模拟退火算法和禁 止搜索算法；( 4 ) 基于模糊集合理论的码书设计算法；( 5 ) 基于群体智能理论的码书设 计算法。 ( 1 ) 传统码书设计算法_ ib g 算法 采用l b g 算法设计码书时，最终码书的性能强烈的依赖于初始码书，而l b g 算 法的初始码书采用随机选择法和分裂法，优化效果不好。为了获得更好的初始码书， 文献【7 】提出了一种改进的初始化技术。该技术在设计前计算训练矢量的方差，根据 方差大小将训练矢量归为四类，然后选取各类的中值矢量作为该类的码字，计算各类 的均方误差，选取均方误差最大的类按上述方法进一步分类，一直到码书大小符合要 求为止。仿真结果表明了该技术的有效性。 除了针对初始化技术的改进以外，对l b g 算法的其它改进方法有两大类：一是 将快速码字搜索算法引入到l b g 算法中以提高设计速度；二是采用其它技术提高码 书性能或加快设计速度。对于融入快速码字搜索技术的改进算法，都归入到码字搜索 算法中，这里不予以叙述。在文献【8 】中，e q m t s 提出成对最近邻( p m r w i s e n e a r e s t - n e i g h b o r , p n n ) 的码书设计算法。这个算法刚开始令每个训练矢量各占一类， 然后每次把两个具有最小距离的类合并，直到获得所要求大小的码书( 各类的质心矢 量作为码字) 。这算法明显减少了计算复杂性，但最终得到的码书性能比l b g 算法差。 4 群体智能算盎在矢量量化及求解t s p 问题中的应用研究第1 章绪论 如果把p n n 算法得到的码书作为初始码书用l b g 算法进一步优化则最终的码书性 能将得到较大提高。文献 9 】提出一种最大下降算法( m a x i m u md e s c e n t ，m d ) 。这种算 法开始将整个训练矢量集当作一类，该类被最优分割超平面分成两个新类，这两个类 又根据最大失真下降准则进一步分成三个新类，继续用最大失真下降准则直到获得所 要求数目的类。同l b g 算法相比，该算法提高了码书性能，减少了计算时问。文献 1 0 提出了基于快速胞腔划分的改进分裂法矢量量化码书设计算法。该算法采用特征 变量对码书进行合理排序，使得码书在结构上具有一定的秩序，利用这种秩序进行快 速胞腔划分来减少分裂法码书设计中庞大的运算量。文献 1 1 提出一种称为部分l b g 的码书设计算法，该算法采用基于方差的k - d 树分裂法得到初始码书，而用所谓的部 分l b g 算法逐步优化初始码书，从而获得更好的码书性能。 ( 2 ) 基于神经网络的码书设计算法 近年来，神经网络已成功地应用到矢量量化码书设计中。这类算法利用神经网络 强大的学习功能，在学习过程中不断更新获胜神经元( 码字) 或者更新获胜神经元邻域 内的码字，甚至根据失真大小以不同程度更新所有码字。且学习速度( 收敛速度) 可由 学习率等控制因子控制a 文献【1 2 】提出了一种简单的学习矢量量化算法( l e a r n i n g v e c t o rq u a n u z a t l o n ，l v q ) 。在学习过程中，只有获胜的码字得到更新。该算法得到的 码* 陛能不如l b g 算店。为了解决l v q 算庄的码字欠利用问题，文献中提出了各种 各样的竞争学习算底。几种代表陛方雇如下：a 利用自组织特缸 ：映射神经网络，通 过邻域作用以争取史多的码字得以更新，即获胜神经元邻域内的各码字一同得到更新 j 3 】；b a h a l t 等提出一种频域敏感竞争学习算法1 4 , 1 5 ( f r o q u e n c y - s e n s m v ec o m p e t l h v e l e a r n i n g 。f s c l ) ，该算法通过在失真测度计算中 i 入每个神经元对应的获胜频率因 子，使各神经元得到公平等机率的利用；c y a i r 等提出基于随机松弛思想，提出 一种软竞争学习算法1 1 6 l ( s o f lc o m p e t i t i v el e a r n i n g ，s c l ) ，在该算法中没有明确的获胜 神经元，每个神经元根据失真大小得到不同程度的调整：d 文献【1 7 提出失真均衡竞 争学习算法( d i s t o r t i o ne q u a h z e dc o m p e t i h v e l e a r m n g , d e c l ) ，文献 1 8 提出部分失真 均衡竞争学习算法( p a r a a ld l s t o r t t o nu r n f o r mc o m p e t l t ：l v el e a r n i n g , p d u c l ) 。文献 1 7 ， 1 8 这两种算法基于最佳量化器的渐进必要条件，即各码字对应的部分失真基本相等 来设计矢量量化码书。它们不仅能解决码字欠利用问题，而且使各码字在表征输入空 s 第1 章绪论群体智能算庙在矢量量化及求解t s p 问韪中的的应用研究 间数据分布时得到有效利用，使最终的平均失真接近晟小。此外，文献【1 9 ，2 0 提出基 于n e u r a l g a s 的码书设计算法。 ( 3 ) 基于全局优化技术的码书设计算法 码书设计的目标是找到训练矢量的最佳分类。给定m 个训练矢量和码书大小n ， 码书设计的目的是寻求把m 个训练矢量分成n 类的最佳方案。若m 和n 较大，传 统的搜索方法难以在众多的分类中找到全局最优的分类。基于此，学者们采用了各种 各样的全局优化技术 2 1 2 6 进行码书设计以改善码书性能，但是这些算法的普遍缺点 是增加了计算时间。文献 2 7 1 将模拟退火算法运用到矢量量化码书设计中。该算法每 次迭代中都用到l b g 算法，所以设计时间比较长，但性能比l b g 算法有较大提高。 文献1 2 8 将随机松弛算法应用到码书设计中。文献 2 9 ，3 0 】将遗传算法用于码书设计中， 该算法对码字进行基因编码，而且每次迭代都用到l b g 算法，所以算法设计时间长， 但性能比l b g 算法好。禁止搜索( t a b us e a m h ) 算法是一种崭新的全局优化技术，它 在码书设计上的应用研究也刚刚起步。文献【3 1 】首先将禁止搜索算法应用到码书设计 中，结果表明该算法性能比l b g 算法要好。 ( 4 ) 基于模糊集合理论的码书设计算法 上面的各种矢量量化码书设计算法是将每个训练矢量根据一定的准则分配给单 个聚类( 硬判决) ，而忽略了训练矢量属于其它聚类的可能性，导致算法局部最优或强 烈依赖于初始码书的选择。基于此，学者们将模糊聚类理论f 3 2 j 3 1 应用到码书设计算法 中。文献 3 4 中提出模糊c - 均值( f u z z yc - m e a n s ，f c m ) 算法，该算法为每一个输入矢 量分配一个成员隶属度来表征该输入矢量以何等程度隶属于某个特定聚类。该算法的 性能比l b g 算法要好，但是计算量比l b g 算法大得多。近几年研究较多的模糊矢量 量化( f u z z y v e c t o rq u a n t t z a t a o n , f v q ) 算法n 5 】5 将模糊逻辑引入到矢量量化的码书设计 中。该算法对初始码书依赖性小，性能和f c m 算法相当，运算量小于f c m 算法， 但相对于l b g 算法还是比较大。为此，文献1 3 6 提出模糊k 邻域算法( f f k n ) 。该算 法在训练过程中以每个聚类的码字为胞腔中心，寻找与每个胞腔码字晟邻近的k 个训 练使矢量，该算法简单实用设计速度快，但性能有所下降。文献【3 7 在f f k n 的基 本原理下，以每个训练矢量为中心形成胞腔，并给出一种新的码书更新公式和隶属函 数，该算法运算速度快，玛书性能高。但到目前为止，f v q 的设计时间仍然超过l b g 群体智能算法在矢量量化及求解t s p 问题中的应用研究第l 章绪论 算法。 ( 5 ) 基于群体智能理论的码书设计算法 2 0 世纪5 0 年代中期出现了仿生学，人们从生物进化机理中受到启发，提出了许 多用以解决复杂优化问题的新方法，如遗传算法、进化规划、进化策略等。这些以生 物特性为基础演化算法的发展，及对生物群落行为的发现引导研究人员进一步开展了 对生物社会性的研究，从而出现了基于群体智能理论的蚁群算法和微粒群算法。这两 种新兴的算法很快在许多领域得到应用。文献 3 8 】是将蚁群算法应用于图像压缩的矢 量量化技术，提出一种基于人工蚁群优化的矢量量化码书设计算法。该算法利用人工 蚁群系统中蚂蚁通过信息素留存寻找最优路径的机制，结合单只蚂蚁通过拾起、放下 物体从而使物体聚堆的行为模型，合理设计放下概率、禁忌列表以及信息素更新方式， 从而可以获得胜能较好的码书。单单基于微粒群算法的码书设计算法至今还提出，但 微粒群算法是很好的全局优化算法，可以用来优化其它算法所得的结果。 1 2 2 矢量量化码字搜索算法研究现状 在矢量量化中，最原始的码字搜索算法是穷尽搜索算法【4 】。如果码本大小为n ， 码字为k 维矢量，对应每个输入矢量，它要比较输入矢量与码本中每个码字之间的误 差，然后找出失真最小的码字，将该码字的索引i 作为编码结果。该算珐的优点显而 易见，就是可以在现有码本的基础上，得刮对输入数据的最优编码结聚。但是，该算 法的致命缺陷是当码本尺寸n 和维数k 增大时，对一个输入矢量编码时要进行nk 次 乘法，n ( 2 k - 1 ) 次加法，和n 一1 次比较，搜索码字耗费的计算量将急剧增长，需要 的时间也是不能容忍的，这限制了它在实际应用中的实用性。 针对穷尽搜索算法的缺点，许多文献在穷尽搜索过程中或搜索前加入一些判据排 除不必要的失真计算从而较少计算时间而形成一系列快速算法。文献 3 9 】 中提出了一种部分失真搜索( p a r t l a ld 1 s t o n l o ns e a r c h ，p d s ) 算法。实际应用显示出p d s 算法能够有效地降低码字搜索的计算量，缩短搜索时间，算法思想简单明了，并且在 后面的各种码字搜索算法研究中得到了广泛的应用。文献 4 0 】在p d s 算法的基础上提 出了一种称为最大失真分量最小算法( m m x m a xm e t h o d ，m m ) ，它将p d s 算法简化为 依据输入矢量与码字间误差矢量的最大分量来判断是否排除该码字。 文献【4 1 4 5 】中提出了基于绝对误差不等式判据的码字搜索算法。其中利用了最大 7 第1 章绪论群体智能算往在矢量量化及求解t s p 问题中的的应用研究 失真分量最小方法查找初始匹配码字。文献 4 6 4 8 1 中提出了基于距离三角不等式 ( t r i a n g u l a ri n e q u a l i t y ) 判据码字搜索算法，t i 方法需要额外的n ( n - 1 ) 2 个存储单元 来存储事先计算好的各码字间距。该算法的缺点是当码书尺寸n 增大时，急剧增长 的额外存储空间将会成为实际应用的一个障碍。 文献 4 9 5 4 提出并验证了基于均值( 或和值) 及方差的不等式判据的快速码字搜 索算法，如等均值最近邻搜索算法、等均值等方差最近邻搜索算法，以及多种相关的 改进算法，如i e n n s 算法，i e e n n s 算法等，它们充分利用矢量的和值与方差所体 现的矢量特性，在搜索过程中尽量减少算法的复杂度，缩短搜索时间。这类算法也需 要一些额外的存储空间来存储事先计算的矢量的和值与( 或) 方差。 基于变换域的快速码字搜索算也是一个研究热点。众所周知，正交变换和离散小 波变换都具备能量集中特性，即能量集中在少数几个交换域系数中，且变换前后能量 保持不变。因此，加入p d s 算法将非常有效。文献 5 5 5 6 介绍了基于小波变换的快 速码字搜索算法( w a v e l e tt r a n s f o r ms e 砌，w t s ) 。该算法的主要思想是利用小波变换 将码字的能量集中到少数几个变换系数中，然后在这些系数上利用p d s 算法高效地排 除不匹配码字。文献 5 7 5 8 提出了基于哈德码变换域的快速码字搜索算法( h a d a r n a r d t r a n s f o r ms e a r c h ，h t s ) 。哈德码变换虽然不是严格意义上的正交变换，但变换前后 的能量成倍数关系，因此在变换域中搜索码字与空( 时) 域中搜索码字是等价的。仿真 结果表明，哈德码变换域比小波变换域算法效率略高一些。 还有其它的各类算法也取得了较大的发展，如p r o j e c t l o nm g c l l o d ，f a s tm m s e v q ，基于图像块的均值金字塔结构的v q 快速搜索算法 5 9 】。文献 6 0 】中提出了一种 基于最小均方误差测度的快速矢量量化编码算法，它在进行均方误差测度计算之前， 通过自定义的一组距离判据和预排序的码书，排除大部分候选码字。 1 2 3 矢量量化码字索引分配算法研究现状 码字索引分配是矢量量化算法研究领域里相对较新的方向，各国科学家在意识到 索引分配在整个矢量量化器设计中的重要作用后，已经在这方面做出了一些成绩。 1 9 9 0 年，f a _ r v a r d l n 提出矢量量化索引分配概念后，索引交换算法及t a b u 搜索算法等 概念与方法被采用，并相继提出了几种行之有效的方法。这些算法力图找到全局最优 的或者接近全局最优的码书索引分配方案，消除传输过程中可能引入的信道噪声产生 群体智能算j 圭在矢量量化及求解t s p 问题中的应用研究第l 章绪论 的失真。 1 3 群体智能算法研究现状 群体智能算法的基本原理是以生物社会系统为依托的，也就是由简单个体组成的 群落与环境以及个体之间的互动行为。这种生物社会性的模拟系统利用局部信息产生 难以估量的群体行为。群体智能理论研究领域有两种主要的算法：蚁群算法( a n t c o l o n yo p t i m i z a t i o i n , a c o ) 和微粒群算法( p a r t i c l es w a r mo p t i m i z a t i o n ，p s o ) 。虽然二 者的研究基础和基本思想是一致的，但它们的产生和发展却是相对独立的。 1 3 1 蚁群算法研究现状 9 0 年代d o n g o 最早提出了蚁群优化算法蚂蚁系统( a n ts y s t e m , a s ) ，并将其 应用于解决计算机算法学中经典的旅行商问题m e l i n gs a l e s m a np r o b l e m , t s p ) 。从 蚂蚁系统开始，基本的蚁群算法得到了不断地发展和完善，并在t s p 以及许多实际优 化问题求解中进一步得到了验证。这些改进算法的一个共同点就是增强了蚂蚁搜索过 程中对最优解的探索能力，它们之间的差异仅在于搜索控制策略方面。而且，取得了 最佳结果的蚁群算法是通过引入局部搜索算法实现的，这实际上是一些结合了标准局 部搜索算法的混合型概车搜索算珐，有利于提高蚁群各级系统在优化f u j 题中的求解质 量。 最初提出的a s 有三种模型，a n t - d e n s i t y 、a n t q u a n t i t y 和a n t - c y c l 0 6 ”。它们的 区别在于前两种模型利用的是局部信息，而后者利用的是整体信息。在求解t s p 问题 时，用a n t - c y c l e 性能较好。 基本的蚁群算法有两个基本缺陷：搜索时间过长和容易陷入局部解。为了克服这 两个缺点，近年来，很多改进的策略在很大程度上克服了这两个缺陷，取得了良好的 结果。g a m b a r d e l l a 等【6 2 坦出了一种修正的蚁群算法，对转移概率进行了修订，采用 强化学习策略，有效地提高了收敛速度。l t l c i d 等 6 3 j 提出了一种模糊蚂蚁系统( f u z z y a n ts y s t e m ) 对转移概率进行了模糊化处理，实验结果表明效果很好。德国学者s t a t z l et 和h o o sh 提出了另一种改进的蚁群算法“最大最小蚂蚁系统”( m a x m i na n t s y s t e m ，m m a s ) 【洲】。m m a s 是解决t s p 等离散域优化问题的最好蚁群算法模型之 9 第l 章绪论群体智能算法在矢量量化及求解t s p 问题中的的应用研究 一，很多蚁群算法的改进策略都渗透着m m a s 的思想。但一直以来，蚁群算法中参 数的选择缺乏理论上严格的证明和指导，往往要采用实验方法来确定其优化组合。 1 3 2 微粒群算法研究现状 微粒群算法是在1 9 9 5 年由美国社会心理学家j a m e sk e n n e d y 和电气工程师 r u s s e l le b e r h a r t 共同提出的【6 7 1 ，其基本思想是受他们早期对鸟类群体行为研究结果的 启发，并利用了生物学家f r a n kh e p p n e r 的生物群体模型。 作为一种新颖的优化搜索算法，从其出现至今，研究者们的大部分精力主要集中 于对其算法结构和性能的改善方面上进行研究，主要包括：参数设置、微粒多样性、 种群结构和算法融合。微粒群算法与其它计算智能方法的一个显著区别就是所需调整 的参数很少，但是这些关键参数的设置对算法的精度和效率却存在显著影响。文献 6 8 1 中针对算法中的种群规模、迭代次数和微粒速度的选择方法进行了详细分析，利用统 计实验方法对约束优化问题的求解论证了这三个参数对算法性能的基本影响，并给出 了具有一定通用性的三种参数选择原则。 文献 6 9 q a ，y u s h ih u i 和r u s s e l le b e r h a r t 首次提出了惯性权重的概念，并对基 本算法中的微粒速度更新公式进行了修正，以获得更佳的全局优化效果。为了避免算 法的过早收敛问题，一些研究者提出了通过控制种群多样性提高算法总体性能的方 法。j a c q u e sm g e t 和j a k o bsv e s t e r s t r o m 设计了一种以基本微粒群算法为基础的，通 过多样性度量控制种群特征，从而实现微粒间吸引和互斥平衡以避免算法收敛性早熟 的方澍7 0 1 。t h i e m ok r i n k 等提出了一种微粒空间扩展的方法来解决微粒间的冲突和聚 集闯题，并增强微粒突破局部极小值的能力【7 ”。 为了进一步提高微粒群算法的基本性能，许多学者还尝试了将其与其它智能方法 相融合，以突破其自身局限。文献 7 2 弓i a t 具有遗传思想改进的微粒群算法，仿真 结果表明算法对某些测试函数具有优越性。 随着群体智能理论和应用算法研究的不断发展，研究者已尝试着将其应用于各种 工程优化问题，并取得了意想不到的收获。多种研究表明，群体智能在离散求解空间 和连续求解空间中均表现了良好的搜索效果，尤其在组合优化问题中表现更突出。事 实上，群体智能方法能够被用于解决大多数优化问题或者能够转化为优化求解的问 题。现在其应用领域已扩展到多目标优化、数据分类、模式识别、电信q o s 管理、 1 0 群体智能算法在矢量量化及求解t s p 问题中的应用研究第l 章绪论 生物系统建模、流程规划、信号处理、机器人控制、决策支持以及仿真和系统辨识等 方面。 1 4 本文主要研究内容和结构 本文研究内容：探讨矢量量化技术在静止图像处理上的应用，主要包括码书的设 计和码字的搜索。在已有算法的基础上，用群体智能算法改进并设计码书。本文还详 细分析了群体智能算法和其它算法在解决组合优化方面的对比。 本文结构如下： 第1 章中简要介绍矢量量化技术和群体智能算法的产生、发展和研究现状，阐明 本文要研究的内容。 第2 章中系统地介绍了矢量量化的理论基础，然后给出了矢量量化的定义，介绍 矢量量化技术的基本原理，并介绍与矢量量化技术研究密不可分的一些相关基础知 识。 第3 章中系统地介绍了群体智能的基本原理，包括蚁群算法和微粒群算法的原理 以及它们在解决计算优化问题上思路。 第4 章中重占研究了经典的矢量量化码书设计算弦l b g 算底，并讨论了它 的优缺点。最后通过仿真实验，分析了它的收敛陛能。针对它的不足，提出了一种基 于微粒群算法改进的l b g 算法。该算法较好地结合了微粒群算法和l b g 算法。提出 的算法基本思想是虽然l b g 算法容易陷入局部最优，但收敛速度快，算法简单，同 时利用微粒群算法有发现全局最优解的能力。两种算法的结合，能很好地克服l b g 算法的缺陷，设计出性能良好的码书。仿真实验验证了提出算法的有效性。在图像压 缩编码中，使用提出的算法设计出的码书在重建图像的信噪比和峰值信噪比等方面都 优于l b g 算法。 第5 章中研究了基于变换域的码字搜索算法基于哈德码变换域的码字搜索 算法，讨论了它的优缺点。提出了一种改进的基于哈德码变换域的快速码字搜索算法。 该算法运用c h e b s h e v 距离测度和p d s 算法。码字搜索算法中一个重要的课题是如何 减少乘法运算，在该算法中，离线计算哈德码变换不需要乘法计算，c h e b s h e v 距离 苎! 兰堕堡 登竺塑丝兰堕垄叁墨墨些墨垄鳖! ! ! 塑垦! 塑竺里! ! ! ! 翌 测度也没有乘法计算，最后运用p d s 算法最大限度地减少了乘法运算仿真实验表 明，该算法能快速有效地找到匹配码字。 第6 章中对比研究了群体智能算法中的蚁群算法和遗传算法在求解如t s p 组合 优化问题上的有效性，并深入分析了两种算法在求解不同规模t s p 问题时的性能 通过大量的仿真实验，给出两种算法求解t s p 问题的指导意见。 第7 章中对全文的工作进行了总结，对矢量量化技术和群体智能算法的进一步研 究进行了展望。 群体智能算i 击在矢量量化及求解t s p 问题中的应用研究第2 章矢量量化基础知识 第2 章矢量量化基础知识 在本章里，我们将介绍矢量量化的基本概念，以及在矢量量化技术研究过程中经 常用到的数学概念及相关知识。 2 1 矢量量化的理论基础 现代信息科技领域里的各个分支，包括数据压缩以及本文关心的矢量量化技术， 都是建立在香农( s h a n n o n ) 的信息论基础上。在信息论里，香农给出了最初的一些概 念，如采样定理、信源编码、信道编码、差错控制编码、有噪声信道的可靠性编码等 等。1 9 5 9 年，香农又提出了率一失真函数r ( d ) ，并证明只要r ( d ) 不超过信道容量 就能保证接收端的失真不超过给定阈值d 。在数学上，r ( d ) 定义为在给定失真d 的 条件下，系统所能够达到的最小码速率。对于幅值离散的信源，r ( d ) 定义如下： r ( d ) - m t n 萎莩职) p ( 舢) l n 等( 2 1 ) zrg 、1 ， 式中 q ( y ) = 尸( x ) p