（信号与信息处理专业论文）基于人工鱼群算法的信号mp稀疏分解.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 信号的稀疏分解是一种新兴的信号分析与处理方法，具有许多优良特性。 其中基于匹配追踪( m a t c h i n gp u r s u i t ，m p ) 的信号稀疏分解是目前进行信号稀 疏分解的常用算法，在数据压缩、信号特征提取、时频分析等领域得到了广泛 的应用，但它是一个典型的n p 问题，计算复杂度高是其应用的瓶颈。 近年来，具有高度的适应性、鲁棒性、并行性以及全局性等特点的群集智 能算法吸引了众多科学领域中的研究人员，并在函数优化、模式识别、图像处 理等中得到广泛地应用。本文首次将新型算法人工鱼群算法( a r t i f i c i a l f i s h s w a r ma l g o r i t h m ，a f s a ) 引入到信号的稀疏分解及其相关应用中。该算 法具有良好的克服陷入局部极值，获得全局极值的能力，对初值可随机地选取， 并且算法的实现无需目标函数的梯度值等特性，故其对搜索求解问题空间具有 一定的自适应能力。 文中首先分析了信号稀疏分解及其最常用的算法m p 算法，然后对人 工鱼群算法的原理、结构、收敛性能、实现方法进行系统的阐述和研究。并对 人工鱼群算法进行改进，在人工鱼群算法觅食行为中增加了吸引因子，使得有 更多的人工鱼集中在全局极值附近进行搜索。改进算法在保留原算法搜索精度 的同时，增大了搜索效率，加快了收敛速度。利用改进人工鱼群算法实现了基 于m p 的信号稀疏分解，给出实验仿真结果和分析，结果证明改进人工鱼群算 法能快速寻找m p 分解每一步中的最优原子，较大地降低了计算量。另外，信 号的采集与传输过程中，不可避免会受到大量噪声信号的干扰，因此对信号进 行去噪，提取出原始信号具有重要意义。本文最后利用基于人工鱼群算法的信 号m p 稀疏分解对受噪声污染的信号进行处理，一定程度提高了信号的信噪 比，达到了去噪的目的。 关键词：稀疏分解；匹配追踪；人工鱼群算法；去噪 西南交通大学硕士研究生学位论文第1 i 页 a b s tr a c t t h es i g n a ls p a r s ed e c o m p o s i t i o ni se m e r g i n gi t san e wm e t h o df o ra n a l y z i n g a n dp r o c e s s i n gs i g n a l s ，w h i c hh a sm a n ye x c e l l e n tc h a r a c t e r i s t i c s a n ds i g n a ls p a r s e d e c o m p o s i t i o nb a s e do nm a t c h i n gp u r s u i t ( m p ) i su s e dc o m m o n l y i ns i g n a ls p a r s e d e c o m p o s i t i o n i th a sb e e na p p l i e dt om a n ya r e a ss u c ha sd a t ac o m p r e s s i o n ，s i g n a l f e a t u r ee x t r a c t i o n ，t i m e f r e q u e n c ya n a l y s i sa n de t c b u ti ti san pd i f f i c u l tp r o b l e m t h el a r g ec o m p u t a t i o n a lc o s ti st h eb o t t l e n e c ko fs p a r s ed e c o m p o s i t i o n i nr e c e n ty e a r s ，s w a r mi n t e l l i g e n c ea l g o r i t h mh a sa t t r a c t e dl o t so fr e s e a r c h e so f n u m e r o u ss c i e n c ea r e a s ，w h i c hh a sh i g h e ra d a p t a b i l i t y , r o b u s t n e s s ，p a r a l l e la n d g l o b a lq u a l i t ye t c ，a n da r eu s e dw i d e l yi ns o m ea r e a ss u c ha sf u n c t i o no p t i m i z a t i o n ， p a t t e r nr e c o g n i t i o na n di m a g ep r o c e s s i n ge t c t h i sa r t i c l es t u d i e st h ea p p l i c a t i o no f an e ws w a r mi n t e l l i g e n c ea l g o r i t h m a r t i f i c i a lf i s h s w a r ma l g o r i t h m ( a f s a ) ，i n s o l v i n gs i g n a ls p a r s ed e c o m p o s i t i o na n dt h er e l a t e da p p l i c a t i o n t h i se v o l u t i o n a l g o r i t h mc a no v e r c o m el o c a le x t r e m u ma n dg e ts o m eg l o b a le x t r e m u m s ，i n i t i a l v a l u e sc a l lb ec h o s e nr a n d o ma n dc a r r y i n go u tt h i sa l g o r i t h md o e s n tn e e dt ok n o w g r a d i e n tv a l u eo f t h eo b j e c t i v ef u n c t i o n ，s oi th a sr o b u s t n e s sf o r t h es e a r c h i n ga r e a t h ep a p e rs t a r t sw i t ht h es i g n a ls p a r s ed e c o m p o s i t i o na n dm a t c h i n gp u r s u i t a l g o r i t h m a f t e r w a r d sa r t i f i c i a lf i s h - s w a r ma l g o r i t h mi s i n t r o d u c e d i tp r e s e n t s s y s t e m i ce x p a t i a t i o na n ds t u d ya b o u tt h ep r i n c i p l e ，s t r u c t u r e ，a s t r i n g e n c ya n d i m p l e m e n t sm e t h o d so ft h ea l g o r i t h m a n da ni m p r o v e da r t i f i c i a l f i s h - s w a r m a l g o r i t h mi sp r o p o s e d i nt h ep r e ya c t i o no fa r t i f i c i a lf i s h ，t h ep u l lm e a n s i sa d d e d w h i c hc a nc o l l e c tm o r ea r t i f i c i a lf i s hn e a rt h eg l o b a le x t r e m u m t h ei m p r o v e d a l g o r i t h mn o to n l yr e t a i n st h ep r e c i s i o no fo r i g i n a la l g o r i t h m ，b u ta l s oa d v a n c e st h e e f f i c i e n c ya n dc o n v e r g e n ts p e e d t h e nt h ei m p r o v e d a r t i f i c i a lf i s h - s w a r m a l g o r i t h mi sa p p l i e dt ot h es i g n a ls p a r s ed e c o m p o s i t i o nb a s e do nm p , a n dt h e s i m u l a t i o nr e s u l t sa n da n a l y s i sa r eg i v e n i ts h o w st h a tt h ei m p r o v e da r t i f i c i a l f i s h s w a r ma l g o r i t h mc a nf a s ts e a r c hf o ra p p r o x i m a t e l yo p t i m a la t o ma te a c hs t e p o fm pa n dt h eq u a n t u mo fc o m p u t i n gi sr e d u c e dal o t i na d d i t i o n ，i ti si n e v i t a b l et o 西南交通大学硕士研究生学位论文第1 i i 页 | i i _ _ _ _ _ _ - _ _ - - _ _ _ _ _ _ _ _ _ _ _ - _ _ b ei n t e r f e r e db yal a r g ea m o u n to fn o i s es i g n a li nt h ep r o c e s so fs i g n a lg a t h e r i n g a n dt r a n s m i s s i o n s oi t se s s e n t i a lt od e n o i s ea n de x t r a c to r i g i n a ls i g n a l a tt h ee n d o ft h ea r t i c l e ，d e a l i n gn o i s e ds i g n a lw i t hs i g n a lm p s p a r s ed e c o m p o s i t i o nb a s e do n a r t i f i c i a lf i s h - s w a r ma l g o r i t h mh a sm a d ec e r t a i ns u c c e s si ni m p r o v i n gt h er a t i oo f s i g n a lt on o i s ea n dd e n o i s i n g k e yw o r d s ：s p a r s ed e c o m p o s i t i o n ；m a t c h i n gp u r s u i t ( m p ) ；a r t i f i c i a lf i s h s w a r m a l g o r i t h m ( a f s a ) ；d e n o i s i n g 西南交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规 定，同意学校保留并向国家有关部门或机构送交论文的复印件和电 子版，允许论文被查阅和借阅。本人授权西南交通大学可以将本学 位论文的全部或部分内容编入有关数据库进行检索，可以采用影 印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 保密口，在5 年解密后适用本授权书； 2 不保密囱，适用本授权书。 学位论文作者签名：雠， 日期：僻1 月况日 指剥雠：尹聊 吼膨年7 月况日 西南交通大学曲南父逋大字 学位论文创新性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下独立进行研究工 作所取得的成果。除文中已经注明引用的内容外，本论文不含任何其它个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均 已在文中作了明确的说明。本人完全意识到本声明的法律结果由本人承担。 本学位论文的主要创新点如下： 1 由于信号的稀疏分解计算量十分巨大，计算时间在现有计算条件下令 人无法忍受。针对此问题，本文在分析稀疏分解的基础上，利用人工鱼群算法 去对信号进行匹配追踪( m a t c h i n gp u r s u i t ，m p ) 稀疏分解，并对人工鱼群算法 进行改进，提高稀疏分解的速度。 2 信号中噪声的消除是信号处理的一个重要内容，能否有效地滤出噪声直 接影响后续工作的进行。提出利用基于人工鱼群算法的信号m p 稀疏分解对含 噪信号进行去噪处理，此方法可以有效去除噪声而保留原始信号，从而提高信 号的信噪比。 西南交通大学硕士研究生学位论文第1 页 1 1 课题的背景和意义 第1 章绪论 现实世界中充满了各种各样的信号，生活中的数字音频、视频，医学上的 x 光片、c t ，军事上的雷达、声纳，地质上的地震波等等。客观地讲，信号 不仅与我们的生活息息相关，而且在很多工程应用中都起着举足轻重的作用。 从理论上说，信号一般都可以用加权的基函数的迭加形式来表示，并且人们总 希望以尽量简单的形式描述出信号。如果一个表达式不仅能够准确而且简洁地 表示出一个信号，则可以断言该信号表示式抓住了此信号的主要特征，这对信 号的压缩、去噪、识别等后继处理十分有利。显然，信号分解的一个主要目标 就是寻找有效的信号表示方法，使信号的某种特征显示出来并进行分析。所以 信号分解在信号处理与分析中起着很重要的作用，是一种常用、有效的分析手 段。可以说，在信号分析与处理学科中，信号分解和信号表达是一个根本性的 问题，具有非常重要的意义。 对于如何进行信号表示，许多学者进行了大量的工作，传统的信号表示方 法如正弦函数或小波函数等是用一组完备的正交基来表示信号，这些基函数均 有较强的物理意义，对于某些特定类型的信号取得了较好的表示效果。但这类 表示方法都试图使用性质相同的一类基函数来表达任意的信号，一旦基函数确 定以后，对于一个信号只能有唯一的一种分解方法，从而对于一般的信号不能 总得到信号简约的表示。因此，更好的信号分解方式应该根据信号的特点，自 适应地选择合适的基来分解信号，这对于含有分布较广的时域和频域局部化信 息分量的信号来说尤其显得重要。 随着信号分解理论的发展，信号的非正交分解引起研究者越来越多的兴 趣。为了实现对信号更加灵活、简洁和自适应的表示，在小波分析的基础上， m a l l a t 等人提出了信号在过完备库( o v e r - c o m p l e t ed i c t i o n a r y ) 上分解的思想， 开创了信号稀疏分解( s p a r s ed e c o m p o s i t i o n ) 这一信号分析的新方向【l 】。逐渐 地，信号的稀疏表示( s p a r s er e p r e s e n t a t i o n ) 越来越引起人们的关注和研究， 西南交通大学硕士研究生学位论文第2 页 并且得到广泛的应用。但是目前信号的稀疏分解在实际工程中很难产业化。阻 碍其应用发展的关键因素是其计算量十分巨大，无法满足实时运算的要求。因 此，如何提高稀疏分解的运算速度，以解决信号稀疏分解计算速度缓慢的难题 将是研究的重点。 目前具有高度的适应性、鲁棒性、并行性等特点的群集智能算法【2 】吸引了 众多科学领域中的研究人员，并在函数优化、模式识别、图像处理等中得到广 泛地应用。在动物的进化过程中，经过漫长的自然界的优胜劣汰，形成了形形 色色的觅食和生存方式，这些方式为人类解决问题的思路带来了不少启发和鼓 舞。人工鱼群算法【3 1 ( a r t i f i c i a lf i s h s w a r ma l g o r i t h m ，a f s a ) 就是一种基于模 拟鱼群行为的随机搜索优化算法，利用鱼群的觅食和生存活动来实现在空间中 寻求全局最优的一种新思路，是群集智能思想的一个具体应用。它的主要特点 是不需要了解问题的特殊信息，只需要对问题进行优劣的比较，有着较快的收 敛速度。该算法在组合优化、函数优化等方面已经得到了很好的应用，由于信 号的稀疏分解可以转化为最优化问题，因此该算法也可推广到信号的稀疏分解 中。本文主要是针对信号的稀疏分解和人工鱼群算法的优点，给出一种信号稀 疏分解的群集智能算法。 本文首次将人工鱼群算法引入到信号匹配追踪( m a t c h i n gp u r s u i t ，m p ) 稀疏 分解中，并对其进行改进，使人工鱼群算法得到更广泛的应用，也使得信号的 稀疏分解有了更有效的解决方法。最后将基于人工鱼群算法的信号m p 稀疏分 解应用到信号去噪上来，从而能够更好的解决工程技术等方面大量的实际问 题。本研究不但在解决实际生活问题中有一定的现实意义，在相关理论探讨方 面也有一定的帮助。 1 2 信号稀疏分解的研究发展现状 在1 9 9 3 年，s m a l l a t 和z z h a n g t l 】首先提出信号在过完备库上分解的思 想，开创了信号稀疏分解这一信号处理的新方向。在所著文献中，作者用自然 语言表述来做浅显的类比，说明了过完备冗余原子库对信号表示的必要性，同 时强调原子库的构成应较好的符合信号本身所固有的特性，以实现m p 的自适 应分解。 西南交通大学硕士研究生学位论文第3 页 m p 算法的提出引起了人们对基于组合优化的方法在稀疏表示领域的研究 兴趣，因此使用基于组合优化的方法对信号进行稀疏表示时，一般要求字典d 是已知的，并且要求d 是超完备的。若需要使用m 项来表示信号，基于组合优 化的方法来实现信号稀疏表示的目标是在字典d 中选出一个含有聊个向量的 子集g = 信h ，g r ，) ，使得在同样使用项来逼近信号的情况下误差信号,g r 的能量达到最小，即 m m - i 2 占- - i i s e a , g 0 加。用不同的方法构造原子，参数组y 所含有的参数及参数个数 也不一样。原子毋的长度与信号本身长度相同，但原子应作归一化处理，即 范数为1 。于是任意给定的信号f 7 - 1 ，信号长度为，在口中自适应地选取 肌个原子对信号厂做m 项逼近： 厶= c r g r ( 2 - 1 2 ) ，e ，_ 其中l 是毋的下标集，c a r d ( & ) = m ，则召= s p a n ( g r , y l ) 就是由m 个原子 在原子库刃中张成的最佳子集。定义逼近误差为： ( 厂，d ) = 啦l l 厂一无l l ( 2 1 3 ) j m 由于m 远小于空间的维数，这种逼近也被称作稀疏逼近。鉴于原子库 的冗余性( p ) ，原子g ，不再是线性独立的，因而表达式( 2 - 1 2 ) 有多种解 答，不同组合中原子所张成的子空间8 构成原子库d 中不同的向量基。稀疏 分解的问题就是在满足条件( 2 1 3 ) 的前提下，如何从各种可能的组合中，拣 选出分解系数最为稀疏的一个，或者说m 取值为最小的一个。 。 西南交通大学硕士研究生学位论文第13 页 2 4 2 过完备原子库 对于表达那些具有强烈时频局部化特性的信号而言( 如图像、语音等时 变信号) ，灵活的信号分解方法是非常重要的。通常为了获得关于信号的稀 疏表达，就要求时频原子库具有广泛的时频特性【l 】，即存在一定的冗余度。 从而使得信号能够在一些特定的波形上分解，这些波形的时频特性适应于该 信号的局部结构，一般称这样的波形为时频原子。 对单个窗函数g ( t ) r ( 尺) ，且满足条件： ( 1 ) 连续可微的实函数； ( 2 ) 并且o ( 1 i ( t 2 + 1 ) ) ； ( 3 ) 范数为1 ，即l i g l i = 1 ； ( 4 ) l g ( t ) d t o ，g ( o ) 0 ； 进行伸缩( s c a l i n g ) 、平移( t r a n s l a t i n g ) 和调制( m o d u l a t i n g ) 变 换可以生成通用的过完备时频原子库。这些条件保证了原子的局部特征，并 具有较快的衰减速度。 为了分析稀疏分解中过完备原子库的结构特性，给出一个具体的过完备 原子库，过完备原子库由g a b o r 原子组成【2 2 1 。 令g ( f ) 为高斯窗函数： g ( f ) = e 吲 ( 2 1 4 ) 那么经过伸缩、平移和调制，可以得到如下的时频原子： ， 易( f ) ：；g ( 丝) c o s ( v t + c o ) ( 2 1 5 ) q s s 其中，y = ( j ，u ，v ，c o ) 是时频参数，其中j 是伸缩因子( 尺度因子) ，u 是 原子的平移因子( 位移因子) ， ，是原子的频率，国是原子的相位，这样的 时频原子被称为g a b o r 原子。时频参数可以按以下方法离散化： y = ( 口7 ，p a 7 a u ，k a a v ，i a c o ) ，其中，a = 2 ，a u = 1 2 ，a v = 万，a r o = 万6 ， 0 l 0 9 2n ，0 p n 2 一，0 k l 2 1 6 ) 其中， 是信号厂与原子的内积。 信号因此可以分解为在最佳原子g ，上的分量和残余两部分，即为： f = ( 厂，g ) g h + r 1 f ( 2 一1 7 ) 其中，( ，g ，0 ) g 托是信号厂在原子g ，o 上的分量或投影，尺1 厂是用最佳原子 g ，。对信号厂进行最佳匹配的残余。显然，r f - 与g ，。是正交的，所以，可以 得到： 2 = 鼠) | 2 + | | 尺1 f l l 2 ( 2 - 1 8 ) 西南交通大学硕士研究生学位论文第15 页 这里为了使得逼近误差的能量忙1 s l l 最 j 、，我们必须选择g ，o 日使得 i l 最大。在无穷维的情况下，通常无法找到i i 的极值，只可 能选择在某种意义上近似最佳的原子g ，使得 i j 口磐l i ( 2 - 1 9 ) 其中口为优化因子，满足0 口1 。 下一步对残差r 1 f 进行同样的步骤，得到 r i f = yr ( 此处以求极大值为例，求极小值问题可以和此进行转换) ，则人工鱼 向该方向前进一步；反之，再重新选择状态石，判断是否满足前进条件；这样 反复尝试t r y n u m b e r 后，如果仍不满足前进条件，则随机移动一步，上面的过 程可表示为： f 鲥= x , + r a n d o m ( s t e p ) ( x y 一彪) 函， y j y i ( 3 - 1 ) i 耐= 石+ r a n d o m ( s t e p ) e l s e 其中反_ ，= 0 石一为0 为x j 与x 之间的距离，鲥表示人工鱼下一步的状态， r a n d o m ( s t e p ) 表示 0 ，s t e p 】间的随机数，以下各式中的符号含义与此相同。 西南交通大学硕士研究生学位论文第2 1 页 ( 2 ) 聚群行为( s w a r m ) ： 设人工鱼的当前状态为形，该状态的食物浓度为y t ，探索其视野范围内 ( 即反sv i s u a l ) 伙伴的数目n f ，这些人工鱼形成集合肌，即： m = 乃l 反_ ，= l l 石一x y 万y f ( 3 4 ) 表明伙伴中心的附近有较多的食物并且不太拥挤，则朝伙伴的中心位置方向前 进一步，即按式( 3 - 5 ) 执行，否则人工鱼执行觅食行为。 彪恻= 石+ r a n d o m ( s t e p ) ( x 鲫捃一彪) 反蝴 ( 3 - 5 ) 其中矾嘲舸= 0 埘石0 为兄与彪之间的距离。 如果n f = 0 ，即m = o ，表明在其视野范围内没有其他伙伴存在，人工鱼 执行觅食行为。 ( 3 ) 追尾行为( f o l l o w ) ： 设人工鱼的当前状态为彪，该状态的食物浓度为y ，探索其视野范围内 ( 即破，s v i s u a l ) 伙伴的数目n f ，如果n f 0 ，则就探索当前可感知的伙伴中 状态最优的伙伴。计算该最优伙伴的食物浓度y 一，如果 y 麟n f 8 y i ( 3 6 ) 表明伙伴x 树的附近有较多的食物并且不太拥挤，则人工鱼朝伙伴x 。的方向 前进一步，即按式( 3 7 ) 执行，否则人工鱼执行觅食行为。 石恻= 石+ r a n d o m ( s t e p ) ( x m , 口一石) 反一 ( 3 7 ) 其中反= 0 石煅一石0 为石哪与彪之间的距离。 如果n f = 0 ，表明在其视野范围内没有其他伙伴存在，人工鱼执行觅食行 为。 西南交通大学硕士研究生学位论文第2 2 页 3 3 3 行为选择及最优值的获取 ( 1 ) 行为选择： 根据所要解决问题的性质，对人工鱼的当前所处环境进行评价，从而选择 一种合适的行为。对于求解极大值的问题，最简单的评估方法可以使用试探法， 就是模拟执行聚群、追尾等行为，然后评价行动后的值，选择其中的最大者来 实际执行，缺省的行为方式为觅食行为。一般情况下，可以应用进步最快或者 进步即可的原则来选择合适行为。 ( 2 )公告板： 算法中设立一个公告板，用以记录最优人工鱼个体状态及该人工鱼所处位 置的食物浓度。每条人工鱼行动一次之后就将自身状态与当前公告板状态进行 比较，如果优于公告板则用自身状态取代公告板状态，最终公告板的状态就是 系统的最优解。只要公告板的状态稳定在了满意的误差界内就可以结束算法的 执行，也可以直接规定算法的迭代次数。 图3 1 给出了人工鱼群算法基本流程图。 3 3 4 人工鱼群算法的全局收敛性 人工鱼群算法中，人工鱼的觅食行为奠定了算法收敛的基础，聚群行为增 强了算法收敛的稳定性和全局性，追尾行为则增强了算法收敛的快速性和全局 性，其行为选择也对算法收敛的速度和稳定性提供了保障。总的来说，算法中 对各参数的取值范围还是很宽容的，并且对算法的初值也基本无要求。 算法中，使人工鱼逃逸局部极值实现全局寻优的因素主要有以下几点： ( 1 ) 觅食行为中的尝试次数较小时，为人工鱼提供了随机游动的机会，从 而加大了能跳出局部极值的邻域的可能； ( 2 ) 移动步长的采用，使得在前往局部极值的途中，有可能转而游向全局 极值，当然，其相反的一面也会发生的，就是在去往全局极值的途中，可能转 而游向局部极值，这对一个个体就当然不好判定他的祸福，但对于一个群体来 说，好的一面往往会具有更大的机率； ( 3 ) 拥挤度因子的引入限制了聚群的规模，只有较优的地方才能聚集更多 的人工鱼，使得人工鱼能够更广泛的寻优； 西南交通大学硕士研究生学位论文第2 3 页 i 在整个搜索空间随机初始化人工鱼的 i 位置，设置鱼群中人工鱼的数目为m 图3 - 1 人t 鱼群算法流程图 ( 4 ) 聚群行为能够促使少数陷入局部极值的人工鱼向多数趋向全局极值的 人工鱼方向聚集，从而逃离局部极值； ( 5 ) 追尾行为加快了人工鱼向更优状态的游动，同时也能促使陷于局部极 西南交通大学硕士研究生学位论文第2 4 页 值的人工鱼向趋向全局极值的更优人工鱼方向的追随而逃离局部极值域。 经过上面的分析可以看出，人工鱼群算法从构造人工鱼的个体行为出发， 达到最终结果的突现，为优化问题的解决提供了一条新的思路。总结以上的分 析叙述，可以得出人工鱼群算法的以下特点： 并行性：多个人工鱼并行地进行搜索； 简单性：算法中仅使用问题的目标函数值，避免了传统方法要计算梯度的 麻烦； 全局性：算法具有很强的跳出局部极值的能力； 快速性：算法中虽然有一定的随机因素，但总体是在步步向最优搜索； 跟踪性：随着工作状况或其他因素的变更造成的极值点的漂移，本算法具 有快速跟踪变化的能力。 3 4 本章小结 本章介绍了一种新的群集智能优化算法一人工鱼群算法。算法的基本 原理为各人工鱼通过一定的规则选择聚群行为、追尾行为或觅食行为来调整自 身的位置。各人工鱼逐渐向各极值点聚集，并且全局极值附近聚集较多的人工 鱼，随着移动次数的增加，人工鱼渐渐达到全局最优值。此算法具有全局收敛 性好，收敛速度快的优点，且在求解实际问题时，有很大的灵活性，有多种行 动组合可以选取。正因为人工鱼群算法所具有的特性，所以可以将其应用在一 些计算复杂度较高，耗时多的算法和应用中去。 西南交通大学硕士研究生学位论文第2 5 页 第4 章利用a f s a 实现基于m p 的信号稀疏分解 4 1 引言 在信号分析与信号处理中，以下三个方面具有重要的研究意义：( 1 ) 信号 的表示方式和分解方法；( 2 ) 信号分解的快速算法；( 3 ) 信号表示在信号处理 中的应用。从前面内容可知，信号的稀疏表示与稀疏分解，是信号的一种新的、 十分简洁的表示方式和分解方式，具有巨大的研究价值，广阔的应用前景。但 是信号的稀疏分解的计算量十分巨大，计算时间在现有条件下令人无法忍受。 国内有研究人员指出，信号长度为1 0 2 4 采样点时，信号的稀疏分解的难度将 十分巨大【4 9 1 ，所以计算时间长是阻碍其发展的关键因素。为促进信号稀疏表示、 稀疏分解的研究与应用，研究其快速算法是十分必要的。否则，信号稀疏分解 和信号稀疏表示也就无法产业化，而只能停留在研究阶段。针对此问题，本文 中采用m p 的方法进行信号的稀疏分解，在m p 的每一步中，用人工鱼群算法 ( a f s a ) 快速实现在过完备库中选取最佳的原子，为了进一步提高算法的速 度，提出了改进人工鱼群算法，最后根据原子的特性，对基于改进人工鱼群算 法的信号m p 稀疏分解进行进一步的优化。 4 2 信号m p 稀疏分解算法流程 国内外很多高校和科研机构对基于m p 的信号稀疏分解进行了大量的研 究。通过学习和研究，把基于m p 的信号稀疏分解的具体算法大致可分为两类。 由于基于m p 的信号稀疏分解的第l 类算法需要的存储量远远超出我们实验用 的计算机内存，所以我们没有做关于第l 类算法的实验。 在图4 1 中给出了第2 类算法的粗略的算法流程图。以此信号稀疏分解的 计算流程进行说明： ( 1 )设置分解参数。为了对信号进行稀疏分解，首先根据信号本身的特性和 信号稀疏分解的用途及要求，设计、选取进行信号稀疏分解的参数。这 西南交通大学硕士研究生学位论文第2 6 页 里参数主要是指原子库的结构、相干性、原子库中原子在信号空间分布 的稠密程度，分解每一步中的最优性因子等。 ( 2 ) 形成过完备原子库，寻找最佳原子，删除形成的原子库。设定分解参数 后，可以形成一系列的原子，进而形成原子库，然后在原子库中寻找最 佳原子。如果采用常规m p 算法，解公式i ( 尺f ，g “) i = s u p ( r f ，g ，) i 代 表的最优化问题，其解的结果可得到在过完备原子库中与信号或信号残 差最匹配的原子，最后删除形成的原子库。实质上，这里从来没有形成 一个完整的过完备原子库。它一边生成原子，一边进行最佳原子的搜索， 一边删除生成的原子。 ( 开始 ) 输入待分解信号 上 设置分解参数 f 形成过完备原子库，寻找最佳原 子，删除形成的原子库 上 1 在信号或信号残差中减去其在最佳原子 上的分量，完成一步分解 n 士 y 图4 _ l 基于m p 的信号稀疏分解算法流程图 ( 3 ) 完成一步分解。利用( 2 ) 中寻找到的最佳原子，从信号或信号的残差 中把信号或信号的残差在此原子上的投影分量去除，就可完成一步分 西南交通大学硕士研究生学位论文第2 7 页 解。记录此步的最佳原子的参数，作为此步分解的结果。 ( 4 ) 分解完成的判定。由于信号的稀疏表示是一个相对的概念，所以稀疏分 解的完成可以根据不同的标准来断定。如可以用分解步数( 对应于表示 信号的原子数目) 来判定，如果分解达到了一定的步数，l ，就停止分解， 用此时的 乳来近似地表示信号f 。另外，也可以根据信 号分解的残差与原子库的相干性来判定是分解是否完成或者以残差信 号的能量下限为迭代停止条件。 4 3 信号m p 稀疏分解的快速算法 基于m p 的信号稀疏分解在数据压缩、信号特征提取、时频分析等领域得 到了广泛的应用，但它是一个典型的n p 问题，计算复杂度高是其应用的瓶颈。 m p 算法是信号稀疏分解最常用的算法，与其他的信号稀疏分解算法相比，m p 算法易于理解，便于实现，但是依然存在存储量大、计算量大的问题。对此， 现在已经提出信号稀疏分解的一些快速算法，对信号稀疏分解过程有很大的改 进 3 3 , 5 0 - 5 5 】。 针对信号稀疏分解中过完备原子库存储量大的问题，信号实现稀疏表示的 根本原因在于在分解中使用了一个过完备的原子库，但是过完备原子库的使用 也是造成信号稀疏分解计算复杂度特别大的关键因素。文献 5 0 】提出了利用信 号集合划分研究过完备原子库的方法，这种方法利用原子之间的等价关系，可 以把过完备原子库划分成互不相交