（信号与信息处理专业论文）基于联合智能算法和mp的信号稀疏分解.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 由于信号稀疏表示的优良特性，信号的稀疏表示已经被运用到信号处理 的许多方面，如去噪、编码和识别等。但是即使是作为稀疏分解方法中算法 复杂度最低的m a t c h i n gp u r s u i t ( m p ) 算法，其计算量仍然十分巨大，计算时间 在现有的计算条件下仍然无法满足要求，这就造成了信号的稀疏分解的实际 运用很难被产业化。 本文以一维信号为主要研究对象，以改善信号稀疏分解速度为主要研究 目的，重点研究了禁忌遗传算法，人工鱼群算法及其改进算法，改进人工鱼 群算法和遗传算法联合算法在稀疏分解上的应用。 主要工作如下： ( 1 ) 利用禁忌遗传算法求解信号稀疏分解。本文在研究遗传算法和禁忌 算法各自的特点，以及遗传算法在求解信号稀疏分解的特点的基础上，利用 联合智能算法优点，使用禁忌搜索算法和遗传算法联合算法求解信号稀疏分 解。实验结果表明，本文使用的算法提高了信号每一步m p 分解中寻找最佳 原子的能力，并由此提高了信号稀疏分解的速度。 ( 2 ) 利用改进的人工鱼群算法和遗传算法联合求解信号稀疏分解。首先， 针对信号稀疏分解中常用的原子库的特点，实现了具有不同视野的人工鱼和 最佳个体保留策略的改进的人工鱼鱼群算法。然后，在遗传算法加入改进人 工鱼群算法来求解信号稀疏分解。实验结果表明，本文使用的算法改进了单 个算法的不足，改善了信号稀疏分解的速度。 关键词信号处理；稀疏分解；匹配追踪：禁忌遗传算法；改进人工鱼群 算法； 西南交通大学硕士研究生学位论文第1 i 页 _ _ _ _ - i l _ _ _ _ _ _ _ _ - - l i l - - _ _ _ _ _ _ - - _ - - - - l _ _ - - l _ - l l _ _ 一i i i i i i 一 一i i i i i i i i i i ii - - _ i _ _ _ _ _ - _ _ _ _ _ _ _ _ _ - _ - l a b s t r a c t b e c a u s eo fi t se x c e l l e n tc h a r a c t e r i s t i c s ，s p a r s er e p r e s e n t a t i o nh a sb e e na p p l i e d t om a n ya s p e c t so fs i g n a lp r o c e s s i n g ，s u c ha ss i g n a ld e n o i s i n g ，c o d i n g ，r e c o g n i t i o n a n de t c 。e v e na sm a t c h i n gp u r s u i t ( m p ) a l g o r i t h m ，w h i c hh a st h el o w e s t c o m p l e x i t ya m o n gs p a r s ed e c o m p o s i t i o na l g o r i t h m s ，t h ec o m p u t a t i o no ft h a t m e t h o di ss t i l lg r e a t t h e r e f o r e ，s p a r s ed e c o m p o s i t i o no fs i g n a l si nt h ep r a c t i c a l a p p l i c a t i o ni st o o d i f f i c u l tt ob ei n d u s t r i a l i z e d t h ep a p e rh a sm a i n l ys t u d i e do nt a b ug e n e t i ca l g o r i t h m 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 ma n dg e n e t i ca l g o r i t h mj o i n ta l g o r i t h mf o ro n e - d i m e n s i o n a l s i g n a l 强em a i nt a s k sa sf o l l o w s ： ( 1 ) s i g n a ls p a r s ed e c o m p o s i t i o nt a k i n ga d v a n t a g e so ft a b ug e n e t i ca l g o r i t h m b a s e do nc h a r a c t e r i s t i c so fg e n e t i ca l g o r i t h m ，t a b us e a r c ha l g o r i t h ma n dj o i n t i n t e l l i g e n c ea l g o r i t h m ，t h ep a p e r p r o p o s e st h ea l g o r i t h mo ft a b ug e n e t i ca l g o r i t h m i no r d e rt os o l v et h ep r o b l e mo fs i g n a ls p a r s ed e c o m p o s i t i o n e x p e r i m e n t a lr e s u l t s s h o wt h a tt h ea l g o r i t h me n h a n c e st h ec a p a b i l i t i e sf o rs e a r c h i n gt h eb e s tp o s s i b l e a t o mi ne a c hs t e po fm pd e c o m p o s i t i o n , a n di ta l s oi m p r o v e st h es p e e do f d e c o m p o s i t i o ns p a r s e ( 2 ) s i g n a ls p a r s ed e c o m p o s i t i o nt a k i n ga d v a n t a g e so fa l g o r i t h mo fi m p r o v e d 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 mc o m b i n e dw i t hg e n e t i ca l g o r i t h m f i r s t ，t h ep a p e r a n a l y s e sc o m m o n l yu s e dc h a r a c t e r i s t i c so fa t o m si nd i c t i o n a r ya n dm a k e su s eo f t h ed i f f e r e n th o r i z o no fa r t i f i c i a lf i s ha n dt h er e s e r v a t i o no ft h eb e s ti n d i v i d u a l s t r a t e g ya 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 s e c o n d ，i tc o m b i n e sg e n e t i ca l g o r i t h m 谢ma r t i f i c i a lf i s h - s w a r ma l g o r i t h mr u n n i n gf o rs i g n a ls p a r s ed e c o m p o s i t i o n e x p e r i m e n t a lr e s u l t ss h o wt h a tt h ea l g o r i t h ma v o i d st h ed i s a d v a n t a g e so fs o l oa l g o r i t h m a n db o o s t st h ee f f i c i e n c y k e yw o r d s ：s i g n a lp r o c e s s i n g ；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 ；t a b u g e n e t i ca l g o r i t h m ；i m p r o v e da 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 西南交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅。本人授权西南交通大学可以将本论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或扫描等复印手段保存和汇编本学位 论文。 本学位论文属于 1 保密口，在年解密后适用本授权书； 2 不保密西使用本授权书。 ( 请在以上方框内打“”) 文作篙：荔：鸣臌帚期 同期：加罗2 夕 同期 叫伊刁 西南交通大学学位论文创新性声明 本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工作 所得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均已在文中作了明确的说明。本人完全意识到本声明的法律结果由本人承担。 本学位论文的主要创新点如下： ( 1 ) 利用禁忌搜索算法求解信号的稀疏分解。 ( 2 ) 针对单个智能算法缺陷，利用联合智能算法的优点，使用禁忌搜索 算法和遗传算法的联合算法( 禁忌遗传算法) 求解信号的稀疏分解。 ( 3 ) 针对信号稀疏分解中常用原子库的特点，使用改进的人工鱼群算法 和遗传算法联合求解信号的稀疏分解。 兹文写：考叫 日期：2 加罗矿2 7 ， 西南交通大学硕士研究生学位论文第1 页 第1 章绪论 1 | 1 课题的背景和意义 信号的稀疏表示近年来越来越弓| 起人们广泛的关注和研究，并且获得广 泛的应用。它可以简洁地表示出一个信号，则该信号表示式抓住了此信号的 主要特征，这对信号的压缩、去噪、识别等薏继处理十分有利。但是嚣静信 号的稀疏分解在实际应用中很难产业化。阻碍其应用发展的关键因素是信号 的稀疏分解的计算量十分巨大，计算时间在现有计算条件下无法满足要求。 研究指出当信号采样点为1 0 2 4 个采样点时，信号的稀疏分解的计算难度将十 分巨大【l 】。而当研究对象为图像时，对应的计算量将更加巨大。即使作为稀 疏分解方法中算法复杂度最低的匹配追踪( m a t c h i n gp u r s u i t 、m p ) 算法，其 计算量也是相当巨大的。 本课题旨在深入智能算法在信号稀疏分解领域的应用。智能算法是人们 受自然和生物界规律的启迪，根据其原理，模仿其求解问题的方法。其在解 决组合最优化规划、n p 难、o l 背包等问题上有良好表现。本课题主要研 究通过智能算法和联合智能算法，使其运用于稀疏分解。根据稀疏分解的弱 匹配追踪的原理【2 】，智能算法对求取弱匹配追踪下的最优原予有明显优势。 因此，研究智畿算法和联合智能算法能有效的改进基予m p 算法的信号稀疏 分解速度。 虽然露翦信号稀疏分解的最常用方法是基予m p 的稀疏分解，瑟且惩乎 也是所有算法中速度最快的，但和其它的信号稀疏分解方法一样，其存在的 关键阀题仍是计算量十分臣大【3 】。因此，如果能寻找到能降低基于m p 算法的 稀疏分解的算法复杂度，提高分解速度的方法，则能从根本上解决基于m p 算法的稀疏分解的技术瓶颈，使稀疏分解运用于产业化。 1 2 国内外稀疏分解研究的动态 1 9 9 3 年，m a l l a t 和z h a n g t 4 1 首先提出信号在过完备库( o v e r - c o m p l e t e 西南交通大学颁士研究垒学位论文繁2 页 d 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 躺、锗弩编码 5 】帮识别 国等。薮串， 在信号时频分奄研究方面鹃应蕉特别筐褥关注瓣l 。露 ；萋，穰号戆稀蠛分解澄 经发展了多种算法，如m p 算法 4 3 - 9 1 、f o c u s s 算法f l o l ( f o c a lu n d e r d e t e r m i n e d s y s t e ms o l v e r ) 、基本舔踪( b a s i sp u r s u i t ) 算法瓣 、基予小渡毯域余弦趣 鹣最佳委交萋算法( b o b ) 、芷交匹配鼹踩算法嘲( o r t h o g o n a lm p ) 和 离分辨率嚣醚跟踪算法f | 本】醚i 翡r e s o l u t i o nm p ) 等等，其孛题配遣爨 ( m a t c h i n gp u r s u i t ) 以其原理简单，算法易于理解，算法鲢计薄复杂度是隧 类新商稀疏分勰算法孛最低的慌势，成隽了蠲蓠最蠹广泛斑瘸鹣耩碗分解方 法。毽是即使是 摹薏稀蔬分解孛算法复杂度最低懿m p ，其诗舞量也是十分慷 入豹，计算对瓣在现有计弊条绛下令入无法忍受。嚣滤鸯研裁入受擐盛，镲 号长麓嚣1 0 2 4 采掸点露，信号熬稀巯分解的难度将十分巨大f 3 l 。当研究对象 鸯鹫像时，对藏的诗算巍薰褥更加甄太。 嚣梵研究鹣焦点集中在懿祷实现该藓法的诀逮计冀，降低算法熟复杂发， 馘及逡耩褥静类型麴萋构造合适的灏子库两方瑟。针对原予霹熬构成羼蠹外 瓣塞了一系列魏研究理点。铡麴原子形裁快速算法、原予痒集舍划分瓣翻等。 针对m p 抉速算法提出蒸- y f f t 的信号耩蔬分解1 9 列辩以及蒸予智能计冀的快 速冀法。 基予m p 算法懿褥流分解，察震上可滋转化隽求个垒局最优解斡阔题。 毽知莱维号长度穰长，则邋完备原予库筏褥| ，g 托 | 鬻蚓拶，g r 鬟代袭抟最 优纯翘题缀避求解。遴阔题往键转化为个求次魏解的露遂，所鞋霹潋裁瘸 最优化方法，特剐是基于智能计算鹣最傀傀方法寒求解，觚丽使的m p 算法 豹计算复杂度惫胤减少，经褥稀疏分簿豹计算成本降低，靛嚣稀疏分解在实 际应溺成为可麓。鼹她，研究基于鬻能算法抟信号的稀蘸分解商着重要意义。 餐麓计算，也稼巍“较计冀”，楚剽鼹铸垒原理寒进行设计翻计算，随着计算 祝技术酶飞速笈蕊，英寂黑领域超越来越广泛口9 - - 2 5 。在针瓣稀疏分解基于餐 糍诗算麴蔌速算法，国蠹辨研究者徽出来大爨豹研究，智麓计算豹遗传算懑 溯、蚁群优纯葵法 朔、量子遗传冀法f 蠲、p s o 算法f 2 9 j 耩人工鱼群算法 3 0 1 成功 逅焉予髂罨和匿橡鹣褥蘸分簿中。 西南交通大学硕士研究生学位论文第3 页 然焉，智能计算中其他成熟算法，如禁忌搜索算法、模拟退火算法并没 有用于稀疏分解快速算法中，这不能不说是种遗憾。特别是近年来，智能 计算方法褥到深化发展，新算法不断涌现。特别是两种或几种智能计算方法 的联合运用，不仅仅弥补单一算法的缺陷，而且在实际运用中取得了良好的 结果。如果用其运用稀疏分解的快速计算，则必将提高稀疏分解的计算速度， 改善算法复杂度。 1 。3 本文的主要工作 本文主要以一维信号为研究对象，研究禁忌遗传算法，改进的人工鱼群 算法和遗传算法联合在信号的稀疏分解上的运用。具体章节安排如下： 第一章绪论。简要介绍了本课题研究的背景和意义、国内外研究现状， 并阐明本文的主要工作。 第二章基于m p 算法和智能算法的信号稀疏分解概述。在本章中概述了 基于m p 算法的信号稀疏分解的基本理论；信号稀疏分解中的原子特性；智 能算法和联合智能计算的发展和应用。 第三章利用禁忌遗传算法及其改进算法实现信号的稀疏分解。首先，介 绍了遗传算法和禁忌搜索算法基本理论、算法基本流程，以及算法各自的优 缺点。然后，针对遗传算法和禁忌搜索算法的各自的特点，实现了利用禁忌 搜索算法优化遗传算法的变异算子和交叉算子求解信号稀疏分解的算法。最 后，给出利用禁忌遗传算法及其改进算法实现信号的稀疏分解的三种方法思 路，郎禁忌交叉算子( t r s ) 、禁忌变异算子( t m s ) 和禁忌交叉变异算子 ( t r s + t m s ) 。实验结果表明，该算法具有定速度上的优势。 第蹬章基于改进的人互鱼群算法和遗传算法联合的信号稀疏分解。善 先，介绍了人工鱼群算法的基本理论和基本流程，以及算法存在的优势和缺 陷。然后，通过分析常用方法构造的原子库中原子的特点，实现了对予原子 的不同参数利用不同视野的人工鱼和最佳个体保留策略的改进的入工鱼群算 法。最后，分别对遗传算法的变异操作和交叉操作后的群体进行改进的人工 鱼群搜索。实验结莱表明，改进的人工鱼群算法和遗传算法联合有良好的表 现。 西南交通大学硕士研究生学位论文第4 页 最蜃总结全文，对本论文作总体概括，并展望未来的磅究工作。 1 4 本章小结 本章是论文的绪论部分，在本章中首先介绍了论文研究课题的背景和研 究意义，然后叙述了国内外稀疏分解研究的动态，最瑟详细的阐述了论文的 主要工作及章节安排。 西南交通大学硕士研究生学位论文第5 页 第2 章赫p 算法和智能算法的概述 2 。1 粥p 算法的基本理论简介 m a l l a t 和z h a n g 于1 9 9 3 年在总结前人研究成果的基础上提出了信号在过 完备库( o v e r - c o m p l e t ed i c t i o n a r y ) 上分解的思想。通过信号在过完备库上的 分解，用来表示信号的基可以自适应地根据信号本身的特点灵活选取f 3 】。分 解的结果，将可以得到信号的一个非常简洁的表达( 即：稀疏表示s p a r s e r e p r e s e n t a t i o n ) 。而得到信号稀疏表示的过程称为信号的稀疏分解( s p a r s e d e c o m p o s i t i o n ) 狰l 。由于基的正交性，导致了基在由信号所组成的空闻中的分 布是稀疏的。因此，信号的能量在分解以后将分散分布在不同的基上【3 】。这 种能量分布的分散最后将导致用基的组合表示信号时表达的不简洁性，即信 号表示不是稀疏的f 4 l 。在一些信号处理，如识别和压缩等，这种非稀疏的表 示将不利于信号的处理。因此被称为原子的非正交基取代正交基，用予得到 信号的稀疏表示1 4 】。由这些原子组成的集合，是过完备的，被称为过完备库 ( o v e r - c o m p l e t ed i c t i o n a r yo f a t o m s ) 。信号在过完备库上的分解结果一定是稀 疏的【熨。 2 1 1 信号的稀疏表示 给定一个集合d = g ， ，其元索是张成整个维h i l b e r t 空间h = r 的 单位矢量，称集合移为原予库，g ，为由参数组y 定义的原子，原子库中原子 个数为p ( p ) 。用不问的方法构造原子，参数组y 所含有的参数及参数 个数也不一样。原子g ，的长度与信号本身长度相同，但原子应作归一化处理， 瑟瑟范数为l 。于是任意给定的信号厂7 - ，铸号长度为，在秽中自适应地 选取m 个原子对信号厂做m 项逼近：厶= c r g r p e l 其中是岛的下标集，c a r a ( i ) = m ，荧| j t 3 = s p a n ( g r , y ) 就是由m 个原子 在原子库移中张成的最佳子集。定义逼近误差为：( f ，d ) = i n f l i 厂一厶i l ， 由于m 远小于空间的维数，这种逼近也被称作舔蘸逼近。鉴于原子摩的冗 余性( p n ) ，原子岛不再是线性独立的，因而表达式厶= c r g ，有多种 西南交通大学硕士研究生学位论文第6 页 解答，不同组合中原子所张成的子空闻瑟构成原子库移中不同的向量基。稀 疏分解的问题就是在满足条件吒厂，引= i n k f f 一厶i i t 懈t ，如何从各种 可能的组合中，拣选出分解系数最为稀疏的一个，或者说m 取值为最小的一 冬1 3 , 4 1 l 2 1 2 匹配追踪 假设研究的信号为厂，信号长度为三。d = 毋) 。r 为用于进行信号稀疏分 解的过完备库，g ，为由参数组r 定义的原子。用不同的方法构造原子，参数 组，所含有的参数及参数个数也不一样。原予的长度与信号本身长度相同， 但原子应作归一化处理，即l l g ，0 = l 。f 为参数组厂的集合。由库的过完备性 霹知，参数组，的个数应远远大予信号的长度，帮若焉p 表示过完备库 d = 语y l r 中原予的个数，则p 应远远大于信号长度五【3 】。 m p 方法分解信号过程如下 4 】步骤，公式( 2 1 ) 到公式( 2 7 ) 来源文献 4 ： s t e po ：从过宪备库中选出与待分解信号最为匹配的原子g ，。，其满足以 下公式( 2 1 ) 的条件： 1 ( ，g 拘 i = s u p i ( 厂，g ，) i s t e pl ：信号分解为在最佳原子g 上的分量和残余两部分， ( 2 2 ) ： f = f ，g 孙 g 憝+ 灵1 厂 其中r 1 厂是用最佳原予对原信号进行最佳匹配后的残射4 1 。 s t e p2 ：对最佳匹配蜃的残余不断进行上面同样的分解过程， ( 2 3 ) ! ( 2 1 ) 即为公式 ( 2 。2 ) 即为公式 冀。= g 珞 ( 2 6 ) k = 0 事实上，由于陋”州的衰减特性，一般而论，用少数的原子( 与信号长度 相比较而言) 就可以表示信号的主要成分，即： ；( r 厂，g n ) g h k = 0 ( 2 - 7 ) 其中，嚣l 。公式( 2 。7 ) 和条件露l 集中体现了稀疏表示的思想嘲。 由于基于m p 的稀疏分解，算法易于理解，是目前信号稀疏分解的最常 用方法1 3 】。但和其它的信号稀疏分解方法一样，其存在的关键问题是计算量 十分巨大。在基于m p 的信号稀疏分解中，每一步都要完成信号或信号分解 的残余在过完备库中的每一个原子上的投影计算【4 j 。按公式( 2 4 ) 所要求， 每一步分解实际上要进行的内积计算俾2 厂，g ，) 是一个在报高维( l 维) 空间 的内积计算，而且要进行很多次( p 次) ，这是m p 信号稀疏分解计算量巨大 的根本原毽所在p 】。公式( 2 - 4 ) 所代表的问题，馨m p 每一步分解所需解决 的问题，实际上是个最优化问题，直接的求解方法是全局搜索的方法，这 将非常费时的1 2 6 j 。 2 2 信号稀疏分解中的原子特性 我们可以由文献f 6 1 得到在信号稀疏分解中使用的较一般的原子。图2 1 是 一个原孑的示意图，原子长度选为5 1 2 。从鹰2 1 我们可以看出，在信号稀疏 分解中使用的原予，一般能量集中在原子的中央地区，而原予的其它地方能 量为零。这是一个有代表性的原子，其它原予能量可能更加集中，或能量较 它分散。利用其它文献中提供的原予生成方法，也会有相似的结论。原子能 西南交通大学硕士研究生学位论文第8 页 量的这种集中的特性，原因是由于形成原子的公式中都包含一个了高斯窗函 数【6 1 。 赵 馨 心 迎望 采样点n 图2 - 1 一个原子的示意图 利用这种原子的能量特性，我们可以简化l ( r f ，g ，) l 的计算【3 】。从理论上 讲，内积( r 厂，g ，) 的计算量随着信号的长度的增大而急剧的增大。但是， 实际上，由于原子本身一般具有能量集中的特性，所以没有必要按信号的长 度来计算l ( r 厂，g ， l 。假设信号的能量集中在长度为c 的区域内，其它部分为 零。则我们只需要计算在c 的区域内的内积值俾，g ，) ，以此作为在信号的 长度上计算的内积 | = s u p ( r 。f ，g y | 所 要求，每步分解实际上要进行的内积计算( 尺厂，g ，) 是一个茬很高维空间的 内积量 算，而且要进行很多次，这是m p 信号穗豌分解计算量巨大的根本原 因所在。m p 每一步分解所需解决的问题，实际上是一个最优化问题，直接的 求解方法是全局搜索的方法，这将是非常费时的。因此对于此闯题，利用智 能计算( 如群体智能等) 可以很好地快速解决。遗传算法、蚁群算法、p s o 算法、量子遗传算法和鱼群算法已经运用于求解信号稀疏分解的问题上，并 且取得了比基于m p 算法的信号稀疏分解更好的速度优势【2 3 2 舅。 基于智能计算的信号稀疏分解虽然比m p 算法有优势，但是其仍然存在 缺陷：从已有的实验结果分析【孙3 0 】，我髑可以看到基于全局搜索的m p 稀疏 分解的重建信号要比基于智能计算的稀疏分解的重建信号更加接近于原始信 号。导致这种现象的原因是因为智能计算所求结果只能是局部最优解丽不是 全局最优解。 2 。4 智熊算法的联合 近年来，随着工程问题范围、飙模和复杂度越来越大，传统智能算法的 求解结果往往不够理想，同时算法理论研究的落后也导致了单一智能算法性 能改进程度受到了限制，并且提出新的基于自然性或社会性的智能算法( 或 群体智能算法) 的愚想来说，这是件很困难的事。同时智能算法又常常受 到两个难题的困扰：易限于局部极值、效率低下【3 1 1 。为了克服智能优化算法的 这两个关键缺陷，研究人员通过研究提出了两种或者多种单一智能进行联合 ( 混合) 的解决方案。联合智能算法是由单一的智能算法或群体智能算法融 合丽形成的种智能化启发式算法。联合的智能算法吸收了各单一算法的优 点克服了单一算法的缺点。智能算法的联合不是各单一算法的简单的相加， 丽是要根据各自单一算法本身算法的存在的优点、缺点、关键阈题、技术手 段和应用范围，来设计混合的流程、方法或手段。 联合智能算法作为一种智能化启发式算法，已经被研究人员和工程技术 人员应用子各种复杂性高、数据大、环境要求高的全髑优化闯题【3 2 稍】。联合 智能算法中进行联合的各算法，不仅仅只是传统的智能算法之间的联合，如 西南交通大学硕士研究生学位论文第11 页 遗传算法与模拟退火算法的联合【3 2 】、遗传算法与禁忌搜索算法的联合等3 3 】， 而且还包含传统智能算法和群体智能算法的联合，如模拟退火算法与蚁群算 法的联合【3 4 】、禁忌搜索算法和p s o 算法的联合【3 5 】等，还包含有群体智能算法 和群体智能算法之间的联合，如p s o 算法和蚁群算法的联创3 6 】、蚁群算法和 人工鱼群算法的联创卯j 。 联合智能算法虽然作为一种高效的智能优化算法，但是也存在其自身的 局限性。这种交叉和融合只是在某个具体问题上、在某个应用层面上的初步 结合，有很强的偶然性和随机性，缺乏系统性，因此很多组合型智能优化算 法，换一个场合甚至是改动一下初值，就变得无法使用了【3 1 1 。 一 2 5 本章小结 本章内容是基于m p 算法和智能计算的信号稀疏分解信号概述。首先，介 绍了基于m p 算法的信号稀疏分解的基本理论。然后，叙述了在信号稀疏分解 中的原子的特性。再是，简单地介绍了运用于稀疏分解的智能算法的基础知 识。最后，阐述了联合智能算法的现状、发展、运用和存在的问题。 西南交通大学硕士研究生学位论文第1 2 页 第3 章基于禁忌遗传算法的信号稀疏分解 3 遗传算法 3 。 。 遗传算法的基本原理 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 是基于生物进化理论的原理发展起来的 一种广为应用的、高效的随机搜索与优化的方法【2 翻。遗传算法怒基于“适者生 存，优胜劣汰”的一种高度并行、随机和自适应的优化算法，它将问题的求解 表示成染色体( 个体) 的适者生存过程，透过染色体群( 种群) 的一代一代不断进 化，包括选择、交叉和变异等操作，最终收敛到最佳个体的附近，从而求得 阀题的最优解或满意解3 0 2 , 3 8 - - 4 1 】。其主要的特点是群体搜索策略和群体中个体 之间的信息交换，而且搜索不依赖于梯度信息【3 】。 第一个把遗传算法用于函数优化的是h o l l s t i e n ，他在论文计算机控制 系统中的人工遗传自适应方法( a r t i f i c i a lg e n e t i ca d a p t a t i o ni nc o m p u t e r c o n t r o ls y s t e m s ) ) ) 中阐述了遗传算法用于数学反馈控制的方法，主要讨论了 二变量函数的优纯问题【4 2 妫l 。在2 0 世纪7 0 年代初期，由h o l l a n d 在他的第 一部著名的专著自然系统和人工系统的适配( a d a p t a t i o ni nn a t u r a la n d a r t i f i c i a ls y s t e m s ) ) ) 中系统地阐述遗传算法的基本理论和方法，并提出了遗传 算法的基本定理一模式定理( s c h e m at h e o r e m ) ，奠定了遗传算法的理论基础 1 4 2 1 。8 0 年代，h o l l a n d 教授实现了第一个基予遗传算法的机器学习系统一分 类系统( c l a s s i f i e rs y s t e m ) ，开创了基于遗传算法的机器学习的新概念【4 引。 g o l d b e r g 于1 9 8 9 出版的专著遗传算法在搜索优化和机器学习中的应用 ( g e n e t i ca l g o r i t h m s ) ) ) ，总结了遗传算法的主要成果，对遗传算法的基本原 理及应用做了比较洋细和全面的论述，奠定了现代遗传算法的科学基础【3 引。 在求解n p 难闻题以及毒 线性、多蜂丞数优化和多冒标优化问题上遗传算法 有优秀的表现，因此得到了众多学科的高度重视，同时也极大地推动了其自 身的理论研究和实际应用的不断深入与发展，随着进化论、遗传学和计算机 科学的进展，遗传算法也将在理论与应用中得到更加完善和发展【2 3 , 4 2 州】。 西南交通大学硕士研究生学位论文第13 页 迄今为止，遗传算法作为进化算法中最广为入知的算法，其关键闯题有 如下几个方面： ( 1 ) 解的编码和解码选择。 ( 2 ) 初始种群的选取和计算中群体的大小选择。 ( 3 ) 适应度函数的选择。 ( 4 ) 遗传算法的三个算子的选择( 选择、交叉和变异) 。 3 。1 2 遗传算法的基本工作过程 通常的基本遗传算法中有如下五个基本要素：参数编码、初始群体的设 定、适应度函数的设计、遗传操作设计、控制参数设定。 标准遗传算法的主要步骤【4 6 】可以描述如下： ( 1 ) 选择闯题的一个编码。随机的产生组初始个体构成初始群体。 ( 2 ) 计算群体中每个个体的适应度值。 ( 3 ) 根据每个个体的适应度值的大小按照按照一定的方法复制染色体。 ( 4 ) 按照设计好的交叉和变异概率，执行交叉操作和变异操作。 ( 5 ) 判断算法是否满足停止规制。如果满足则输出搜索结果，停止算法。 3 1 。3 遗传算法的优点和缺点 俸为一种借鉴生物界翻然选择和自然遗传机制的高度著行、自组织、鸯 适应的搜索算法，遗传算法有隐含并行性和收敛的全局性两大显著特点，使 其在处理复杂优化超题和工业工程领域取得令入信服的结果。遗传算法具有 以下几个优点1 4 ”： ( 1 ) 遗传算法是从问题解的一个串集开始进行搜索，而不是从单个解开 始。从串集开始搜索，覆盏面大，有利于算法的全局寻优。 ( 2 ) 遗传算法是在解空间中同时处理多个个体，而不像某些传统的搜索 方法麸一个单个的个体出发开始搜索解空闻，减少了黧入局部最优解的惫险。 这是遗传算法所特这是遗传算法特有的隐含的并行性。 ( 3 ) 遗传算法直接利用星标函数的蘧数值信息，基本上不用搜索空间的 知识或目标函数的梯度信息或其他的辅助信息。这就扩大了算法的应用范围。 西南交通大学硕士研究生学 立论文第14 页 ( 4 ) 遗传算法使用概率转移撬则来指导其的搜索方离，面不采用确定性 的转移规则。 ( 5 ) 遗传算法具有自组织、自适应和自学习性。 遗传算法作为一种群体智能的优化算法，也存在其自身的局限性4 h 5 4 刁： ( 1 ) 遗传算法在优化搜索过程中，每一代都要有一个较大的群体规模， 这使得遗传算法在一些超大规模的优化问题上的应用受到了局限。 ( 2 ) 遗传算法虽然采取了变异和交叉技术，但是由于变异概率和交叉概 率偏低，这使得算法靛“爬盘”能力弱，容易陷入局部最优，出现“早熟 特 征。 ( 3 ) 遗传算法在算法的精度、计算复杂性等方面还没有有效的的定量分 析方法。 3 2 禁忌搜索算法7 了譬，、】又力气口= 卜，a 3 2 禁忌搜索的基本原理 禁忌搜索的思想最早起源于到2 0 世纪7 0 年代，但直到1 9 8 6 年，才由 g l o v e r 正式提出禁忌搜索( t a b us e a r c h ，t s ) 这个概念。至9 0 年代初，才形成 一套完整的算法，受到了国内外学者的广泛重视并掀起了研究热潮，其应用 领域不断拓宽，几乎涵盖了组合优化的各个方面，并在函数优化等方面也取 得了成功【4 8 1 。禁忌搜索( t s ) 、模拟退火( s a ) 、进化计算( e e ) 、蚁群算法( a c s ) 、 粒子群优化( p s o ) 等一样，都属于自然计算的研究范畴。禁忌搜索算法是局部 领域搜索算法的推广，算法模拟人们常常在对己经搜索过的地方暂时不会再 次去搜索，先对尚未搜索过的地方进行搜索，如果没有更为会适的值，则返 回原来已经搜索过的地方这一寻优特性。通过局部邻域搜索机制和相应的禁 忌准则，来避免重复迂回搜索，并通过期望标准来释放一些被禁忌的优良个 体，进而保证多样化的有效搜索，以此来最终实现全局优化。禁忌搜索以这 种灵活的存储结构和相应的禁忌准则来避免迂回搜索这种寻优方式，在智能 优纯算法中独树一帜译“。 禁忌搜索算法的主要思想是采用了禁忌技术，就是禁止重复前面的工作， 西南交通大学硕士研究生学位论文第15 页 避免了局部邻域搜索陷入局部最优的主要不足。禁忌搜索算法剩用一个禁忌 表记录下已经达到过的局部最优点或达到局部最优点的些过程，在下一次 搜索中，利用禁忌表中的信息不再或有选择地搜索这些点或过程，从此以来 跳出局部最优点【4 “8 1 。 禁忌搜索在搜索过程中允许接受劣解，使锝禁忌搜索算法具有强的“爬 由”能力，可以跳懑局部最优解，进而转向其它区域进行搜索，从而大大增加 了获得更好的解或全局最优解的概率。禁忌搜索算法主要是由初始解、邻域、 禁忌表、禁忌表规模、期望标准、停止规则等要素构成。其中初始解，郄闻 题任意一可行解；邻域表示当前解所有相邻解的结合，其中包括不满足条件 约束的解；禁忌表是指在搜索过程中充当记忆器的蕉色，用来阻止出现循环 和避免陷入局部最优，它通过记录当前若干次的移动，禁止这些移动在近期 内反复；禁忌表规模就是指禁忌表的大小；期望标准表示判定可是禁忌表约 束可以被忽略的规则；停止规则，即算法终止的条件1 4 8 5 翻。 禁忌搜索算法的关键问题有如下两个方丽【4 8 j ： ( 1 ) 禁忌对象的选择。禁忌搜索对初始解有较强的依赖性，好的初始解 可使t s 在解空间中搜索到好的解，而较差的初始解则会降低t s 的收敛速度。 ( 2 ) 禁忌长度( 规模) 的选择。禁忌表的大夺在缀大程度上直接影响了 算法的效率和解的质量。禁忌表规模过大可能会限制搜索区域，最优解可能 会被跳过 反之，禁忌表规模过小，则搜索过程可能会陷入局部最优。 3 2 2 禁忌搜索算法的基本流程 禁忌搜索算法可用如下的形式描述：t s = 即， ，厶w ，其中， 表示初始解，为迭代代数， 表示移动的构成方式，k 为移动值， l 为禁忌表阳。 禁忌搜索算法的基本流程如下俐： s t e pq ：随机确定解蚴作为视始解，置禁忌表l 必空。 s t e pl ：在当前解产生的邻域中，确定最佳的个体作为候选解。 s t e p2 ：判断该候选解。是否满足期望标准。如果满足，则将该候选 解作为当前解，并将该候选解加入到禁忌表l 中。更新禁忌表， 将该候选解替代最早进入禁忌表l 的解。 西南交通大学硕士研究生学位论文第16 页 s t e p3 ：检索禁忌表l 。若该候选解聊不在禁忌表l 中，则同样接收 该候选解即作为当前解，并将该候选解即加入到禁忌表l 中。若该候 选解即在禁忌表l 中，则该候选解属于禁忌状态。 s t e p4 ：判断是否满足算法停止条件。若满足则输出最优解，反之则返回 s t e p1 。 图3 1 禁忌搜索算法的基本流程框图 西南交通大学硕士研究生学位论文第17 页 3 2 3 禁忌搜索的优缺点 禁忌搜索算法优点如下【4 8 弼】： ( 1 ) 禁忌搜索算法对目标函数没有任何特殊要求，对求解的具体问题也 没有任何特殊要求，几乎适合所有的组合优化问题。这就扩大了算法的运用 范围。 ( 2 ) 禁忌搜索算法对问题的解空间没有任何特殊要求，适合一些非连续、 多峰和突变的搜索空间。 禁忌搜索算法缺点如下【4 8 瑚1 ： ( 1 ) 禁忌搜索算法的搜索过程是一个单对单操作，缺乏并行性。在搜索 过程中只有一个初始解，而对禁忌表操作中也是将对单一解得操作( 从一个 解移动到另一个解) 。 ( 2 ) 禁忌搜索算法对初始解设定的敏感度较强。即一个较好的初始解设 定有助于在解空间中得出更好的解，而一个较差的初始解设定则会降低禁忌 搜索的收敛速度，搜索到的解也相对较差。 ( 3 ) 禁忌搜索算法没有自然性的终止条件，需要人为的限定算法的迭代 次数或是其他人为性的终止条件。 3 3 遗传算法和禁忌算法的联合 已有研究人员有对遗传算法与禁忌搜索算法进行混合的理论进行了深入 地研究【47 1 。g l o v e rf 把禁忌搜索算法的记忆功能引入了遗传算法，并提出了 把遗传算法作为遗传算法的变异算子和交叉算子，生成禁忌交叉算子( t r s ) 和禁忌变异算子( t m s ) ，使得算法在搜索过程具有了记忆性【4 1 1 。 这种混合算法针对遗传算法爬山能力差的缺陷，利用禁忌搜索爬山能力 强的优点，改进遗传算法的爬山能力。算法保留了遗传算法的种群操作，发 挥了遗传算法并行性优势，弥补了禁忌搜索的单对单操作缺乏并行性的弱点。 同时利用禁忌搜索记忆性，避免了遗传算法的早熟问题，提高了遗传算法的 收敛速度和优化质量，改善遗传算法的优化性能及其鲁棒性【5 0 】。 ( 1 ) 禁忌搜索算法对交叉算子的优化。如图3 2 所示 西南交通大学硕士研究生学位论文第18 页 图3 - 2 禁忌搜索对交叉算子的优化 ( 2 ) 禁忌搜索算法对变异算子的优化。如图3 3 所示 图3 - 2 禁忌搜索对变异算子的优化 西南交通大学硕士研究生学位论文第19 页 ( 3 ) 基本遗传禁忌算法步骤如图3 - 3 所示。 图3 - 3 基本遗传禁忌算法 3 4 基于禁忌搜索算法的信号稀疏分解 定义一个原子的参数组作为待寻优参数，首先，把n 个随机值适应度作 为禁忌表，其平均适应度作为期望标准。然后，再由这n 个值随机产生n 个 随机值，计算其适应度。比较该n 个随机值适应度和期望标准。如果大于期 望标准，则保留该值，直接进入下一次搜索；如果小于期望标准，但不属于 禁忌表，则仍保留该随机值进入下一次搜索；如果小于期望标准，但属于禁 忌表，则去除该随机值，把产生该随机值的值进入下一次搜索。最后，在算 法中加入原子特性，从而优化算法。算法流程框图如图3 4 所示。 西南交通大学硕士研究生学位论文第2 0 页 图3 - 4 禁忌算法求解信号稀疏分解流程框图 试验结果： 实验中采用长度为5 1 2 ，取值范围为【o2 5 5 的实际数字信号。n = 1 0 1 个随 机值，搜索3 0 次，t s 的禁忌表长度l = n = 1 0 1 。过完备库中原子的构造方法 按文献【6 j 。把基于m p 的信号稀疏分解的速度设为1 ，在表3 1 中给出了本文 中的方法l 的速度是基予m p 信号稀疏分解的速度的多少倍。其中 p s n r = 1 0 x l o g l o ( 2 5 5 2 m s e ) 。 表3 ，1 信号稀疏分解相对速度比较 算法计算速度( 倍)p s n r ( d b ) 基于m p 的信号稀疏分解13 2 2 2 9 6 m p + 禁忌搜索+ 原子特性6 8 *3 0 6 1 4 0 杈注：由于铅能算法本身的随机性，这里的倍数为平均值。 西南交通大学硕士研究生学位论文第2 1 页 图3 5 中给出源子药3