（计算机应用技术专业论文）基于遗传算法的分形二值图像压缩研究与实现.pdf

武汉理工大学硕士学位论文 中文摘要 一般而言，图像或数据压缩是一种优化问题，其目的是在满足一定质量约 束条件下，给出这些图像或数据最短的描述。分形图像压缩因为其非常高的压 缩比成为了目前非常流行的技术之一。本论文的分形图像压缩算法基于分形自 相似自仿射理论及核心理论迭代函数系统( 1 f s ) 理论。其基本思想足对一幅 原图像寻找一个有效的i f s ，它由组压缩仿射变换组成，而利用该i f s 可以以 任意大小重构出与原始图像十分相似的图像。 然而，1 f s 的求解属于n p h a r d 问题，在复杂的约束条件下，并要在庞火的 搜索窄问中寻求最优解，传统的搜索方法几乎是不可能的。本论文把擅长解决 这类难题的遗传算法应用于分形图像压缩中，提出了一种较为有效的基于遗传 算法的分形二值图像压缩方法。遗传算法，模拟自然界演化过程，通过保持一 个潜在解的种群进行多个方向搜索。种群的进化繁殖遵从优胜劣汰，从而在可 扩展的搜索空间中将搜索引向潜在的最优解。 本论文首先介绍了迭代函数系统和遗传算法的基本理论，然后具体阐述了 基于遗传算法和迭代函数系统的二值图像压缩的基本思想和实现方法，包括染 色体编码、染色体评估、选择策略选取、遗传算子设计、解码图像重构和算法 实现。本文提出1 r 可变长的染色体编码及可扩展的搜索空间等解决方案。同时， 设计了多目标适应值函数，并设计了多种杂交算子与变异算子，使得算法的性能 及效率有了极人的提高。实验结果表明，该算法有较强的搜索能力，能找到近 似最优的i f s 解，其解码图像近似于原图像，并有较高的图像质量。 研究表明，遗传算法具有内在的并行性，正是这一点决定了它具有大规模 并行求解的可能性。本文根据现有的并行遗传算法的框架，实现了一种基于分 布式环境的简单分布式遗传算法，随即，本文又阐述了一种基于分布式系统的 并行遗传算法的没想。实现这一设想将是本人下一步的工作重点。 最后本文对全文做了总结，并讨论了有待进一步研究的内容。 关键词：分形图像压缩，迭代函数系统，压缩仿射变换，遗传算法，分布式，并行 武汉理工大学碗：上学位论文 a b s t r a c t g e n e r a l l ys p e a k i n g ，i m a g ec o m p r e s s i o n o rd a t ac o m p r e s s i o ni sap r o b l e mo f o p t i m i z a t i o n a n du n d e rt h ec o n d i t i o n o fs a r i s f y i n gac e r t a i nl i m i t ，t h e t a r g e to f c o m p r e s s i o n i st oa c q u i r et h es i m p l e s td e s c r i p t i o no ft h ei m a g eo rd a t a n o wf r a c t a l i m a g ec o m p r e s s i o n h a sb e e na p o p u l a rt e c h n i q u ef o rv e r yh i g hc o m p r e s s i o n r a t i o s i n t h i s p a p e r , f r a c t a li m a g ec o m p r e s s i o na l g o r i t h m i sb a s e do nt h ef f a c t a lt h e o r yo f s e l f - s i m i l a ra n ds e l f - a f f i n ct r a n s f o r m a t i o na n dt h ek e r n e lt h e o r yo fi t e r a t e df u n c t i o n s y s t e m t h em a i n i d e ai st of i n do n em o r ee f f e c t i v ei f sw h i c hc o n s i s t so fc o n t r a c t i o n a f f i n et r a n s f o r m a t i o n s m o r e o v e r , u s i n gt h e1 f sc a nr e c o n s t r u c ta n ys c a l eo fi m a g e w h i c hi sv e r ys i m i l a rt ot h eo r i g i n a li m a g e - l o w c v c r ，f i n d i n g t h ei f sb e l o n g st on p - h a r dp r o b l e m u n d e rc o m p l i c a t e d c o n s t r a i n t s ，i ti sh a r d l yt oo b t a i ni t sb e s tr e s u l ti ns u c hh u g er e s e a r c h i n gs p a c eb y t r a d i t i o n a ls e a r c hm e t h o d s t h e r e f o r e ，i nt h i sp a p e r , i m p o r t i n gg e n e t i ca l g o r i t h m ( g a ) w h i c hh a sb e e na p p l i e ds u c c e s s f u l l yt od e a lw i t ht h i sp r o b l e m ，w ep r e s e n tab e t t e r a p p r o a c h t oc o m p r e s sa b i n a r yi m a g eb yu s i n gi t e r a t e df u n c t i o ns y s t e m a n dg e n e t i c a l g o r i t h m g e n e t i ca l g o r i t h m s i m u l a t e sn a t u r a l e v o l u t i o n a r yp r o c e s s e s ，t h o u g h r e t a i n i n g a p o p u l a t i o n o fc a n d i d a t es o l u t i o ns e t st os e a r c hm u l t i _ d i r e c t i o n t h e e v o l u t i o na n dr e p r o d u c t i o no fp o p u l a t i o ni s c o m p l yw i t hs e l e c t i n gt h es u p e r i o ra n d e l i m i n a t et h ei n f e r i o r , t h e r e f o r e ，s e a r c h i n gc a nb ed i r e c t e dt ot h ep o t e n t i a lm o s tr e s u l t i nt h ee x t e n s i b l es e a r c hs p a c e t h e p a p e rs t a r t sb yi n t r o d u c i n g t h eb a s i ct h e o r yo fi t e r a t e df u n c t i o ns y s t e ma n d g e n e t i c a l g o r r h m t h e nt h et h e o r y o ft h ef r a c t a l i m a g ec o m p r e s s i o n a n dt h e i m p l e m e n t a t i o nm e t h o da r ce l a b o r a t e db a s e do nt h ei d e ao fg e n e t i ca l g o r i t h ma n d i f s ，i n c l u d i n gf f a c t a li m a g e m a t h e m a t i cm o d e l ，c h r o m o s o m ee n c o d i n g ，e v a l u a t i o no f c h r o m o s o m e ，s e l e c t i o ns t r a t e g y , d e s i g n e d o f g e n e t i co p e r a t i o n s ，d e c o d i n g r e c o n s t r u c t i o no f i m a g e t h ev a r i a b l e - l e n g t h c h r o m o s o m e e n c o d i n g a n dt h e c x t e n s i b l es e a r c hs p a c ew e r ep r o p o s e di nt h i sp a p e r t h ea l g o r i t h mp e r f o r m a n c ea n d e f f i c i e n c yh a v eb e e ni m p r o v e dg r e a t l yb yi n t r o d u c i n gm u l t i - o b j e c tf i t n e s sf u n c t i o n s ， m a n i f o l dc r o s s o v e ro p e r a t o r sa n dm u t a t i o no p e r a t o r s t h ee x p e r i m e n tr e s u l t ss h o w 1 1 武汉理工大学硕士学位论文 t h a to u ra l g o r i t h mh a st r e m e n d o u sa b i l i t yi ns e a r c h i n gb e s ts o l u t i o n s ，a n dc a nf i n do u t o n eo ft h em o s ta p p r o x i m a t er e s u l to fi f sw h o s e d e c o d i n gi m a g e i sq u i t es i m i l a rw i t h o r i g i n a lo n e a n da l s oh a sh i g hi m a g e q u a l i t y g e n e t i ca l g o r i t h mi t s e l fh a st h ei m m a n e n tp a r a l l e lm e c h a n i s m ，s oi th a st h e p o s s i b i l i t yo fp a r a l l e lc o m p u t eo nal a r g es c a l e t h i sp a p e ri m p l e m e n t e das i m p l e d i s t r i b u t e dg ab a s e do nd i s t r i b u t e de n v i r o n m e n t ，a c c o r d i n gt ot h ee x i s t e n tf r a m e w o r k a n d t h e n ，t h ep a p e re x p l a i n e di t si d e at od e s i g nap a r a h e lg e n e t i ca l g o r i t h ma b o u t b a s e do nt h ed i s t r i b u t e ds y s t e m t h er e a l i z a t i o no ft h i sb l u e p r i n tw i l lb et h en e x tf o c a l p o i n t f i n a l l y , t h i sp a p e r s u m m a r i z e st b rt h i sw h o l et h e s i s a n dt h e nt h ef u r t h e r r e s e a r c hi sd i s c u s s e d k e y w o r d s ：f r a c t a li m a g ec o m p r e s s i o n ，i t e r a t e df u n c t i o ns y s t e m0 f s ) ，c o n t r a c t i o n a f f i n et r a n s f o r m a t i o n ，g e n e t i c a l g o r i t h m ，d i s t r i b u t e d ，p a r a l l e l i 此页若属实请申请人及导师签名。 独创性声明 本人声明，所呈交的论文是我个人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得武汉理工大学或其它教育机构的学位或证书而使用过 的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示了谢意。 研究生签名：袒日期 拄日 关子论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定， 即：学校有权保留送交论文的复印件，允许论文被查阅和借阅；学 校可以公布论文的全部内容，可以采用影印、缩印或其他复制手段 保存论文。 ( 保密的论文在解密后应遵守此规定) 研究生签名：监导师签名：一叠丑丝日期娅 注；请将此声明装订在论文的目录前。 1 1 问题的提出 武汉理工大学硕士学位论文 第1 章绪论 随着图像技术的广泛应抖j ，特别是通信的实时性要求，使得图像压缩比要 求越来越高，如何高效的减少存贮及记录和传输图像的开销成为问题的关键。 一般来说，图像或数据压缩是一种优化问题，其目的是在满足一定质量约 束条件下，给出这些图像或数据最短的描述。基于分形几何学理论的分形图像 压缩是目前最有前途的压缩技术之一。利用分形中迭代函数系统( i f s ) 理论进行 图像压缩属于反问题也是一个n p h a r d 问题f 1 1 ：给定一幅图像，如何找到一个 i f s ，它的吸引子尽_ h j 能相似于该图像。 遗传算法是计算机模拟大自然的演化过程，来求解复杂问题的类计算模 型。遗传算法作为一种有效的随机优化工具广泛应用_ r 各种领域。遗传算法自 身内在的并行性，特别适合于大规模的并行处理，同时也为本论文的进一步研 究基于遗传算法的异构分布式并行分形图像压缩算法提供了新途径。 本论文所提出的基于遗传算法的分形二二值图像压缩算法就是要解决这样一 个n d 题：给定一幅二值图像，通过遗传算法找到该图像的分形编码( - 。个有效的 i f s ) ，其可重构出较高质量的与原始图像十分相似的图像。 虽然本课题只做了基本的研究工作，但无论从理论还是算法实践中都可以 看到其有效性及可行性，其有不可估量的发展前景，为图像信息提取和识别、 以及图像存贮和传输这一通讯领域的瓶颈问题提供了一种新的解决方法。同时 当前许多需要高性能计算的课题都面临着这样的困境，一方面是计算能力的匮 乏，一方面是计算复杂性的快速增长。本论文的研究内容对于解决这类问题也 将具有借鉴和参考价值。 1 2 分形简介 混沌论( c h a o s ) 研究自然界线性过程内在随机性所具有的特殊规律性。而与混 沌沦密切相关的分形理论( f r a c t a lt h e o r y ) ，则揭示了非线性系统中有序与无序的 1 武汉理工大学硕士学1 ：i ) = c 仓文 统。，确定性与随机性的统- - 2 1 。“分；形( f r a c t a l l ，词是由美国i b m 公司研究 中心物理部研究员暨哈佛大学数学系教授曼德勃罗特( b e n o i tb m a n d e l b r o t ) 在 1 9 7 5 年首次提出的。分形还没有确切的简明的定义，从字面上来说是指一类极 其零碎而复杂，但有其白相似性或自仿射性的体系【2 1 。曼德勃罗特指出了分形 的三个要素3 1 ：形状、偶然性、维数。分形的主要特征如f 4 1 ： ( 1 、自相似性：指某种结构或过程的特征从不同的空间尺度来看都是相似的， 或者某系统或结构的局部区域性质或局部区域结构与整体类似。 ( 2 ) 标度不变性( 伸缩对称性或尺度不变性) ：指在分形上任选一个局部区域， 对它进行放大，所得到的放大图又会显示出原图的形态特性。 ( 3 ) 自仿射性：指通过对局部区域结构在不同方向进行不同比率的收缩或扩 展或旋转或位移，有时甚至是产生畸变等仿射变换可获得全局区域结构。 分形形态在自然界中普遍存在，许多形态都很不规则，甚至是支离破碎的。 例如，海岸线和山川形状、天空上的浮云、许多花卉和植物都具有分形的特征。 分形具有j “阀的应用前景，在分形的发展过程中，许多传统的科学难题，由于 分形的引入而取得显著进展。分形理论的应用领域涵盖了生物学、物理学、化 学、天文学、材料科学、计算图形学、经济学与情报学等等学科。 1 2 1 分形几何学与图像压缩 大自然的美，就在于她在本质上是简单的，若我们能找到这些有效的信息， 我们就能简洁地表述自然界的图景。不少复杂的图形，根据分形理论，从计算 的观点来看，利用较小信息量，就可以用简单的程序来构造这些复杂形体。这 是能够采用分彤方法进行图像压缩的重要依据之一。 自仿射分形，其本质反映了大自然的复杂性和丰富性5 l 。能使复杂的图形 寓于简单的算法之中。这说明，通过迭代这全反馈的动态过程，用参数不多的 算法就可以在计算机上显示出相当复杂的自然图形。这是可以采用分形方法进 行图像压缩的另一个重要依据。 分形几何学能为自然界中存在的各种景物提供逼真的描述2 1 。用迭代函数 系统对图像数据进行压缩，其压缩比可望达到1 5 0 0 甚至更好6 1 。这一压缩方法 的关键在于存储迭代函数系统而不是存储迭代函数系统所绘制的图像。而利用 所存储的这i f s 可以以任意大小重构出与原图像十分相似的图像。比如蕨类植 物的图形，利用分形方法中迭代函数系统( i f s ) 即可在计算机上利用简单的随机 武汉理工大学硕：上学位论文 迭代算法就可描绘出来，仅需4 * 6 = 2 4 个数据。如表1 - 1 和图1 1 。 当然，这些称为分形的自然体，没有一个是真正的分形，而是在一定的尺 度范围内可以看作分形f 7 1 。“自然分形”与数学上“分形集”是有区别的，自然 界中分形形态还受到了很多外界因素的影响，更为复杂。本质上不存在真正的 分形，就像并不存在真正的线和圆一样。但是，这并不妨碍我们用欧几里德几 何方法去描述物体的形状，也不妨碍我们用分形方法去进行图像压缩。 表1 1 蕨叶迭代函数系统参数表 wabcdef 1o0o0 1 6o0 20 8 5 0 0 4 0 0 40 8 5o1 6 30 2o 2 60 2 30 2 201 6 40 1 50 2 80 2 60 2 4o0 4 4 1 2 2 分形图像压缩方法的研究现状 图1 - 1 蕨叶 1 9 7 9 年美国的b a r n s l e y 与s l o a n 从数! 学上找到了重要的理论根据。发现了 把图形简化为系列仿射变换的。般过程，这项技术为电视图像与计算机图像 的传送开辟了令人振奋的前景。b a r n s l e y 的弟子j a c q u i n 首次提出分块的迭代变 换理论算法，对分形图像压缩方法的实用化，起了奠基的作用。 分形图像压缩的研究进展包括；( 1 ) 与向量量化( v q ) 压缩方法相结合。( 2 ) 与 小波压缩方法相结合。( 3 ) 区域分形图像压缩方法。( 4 ) 增大区域和减少搜索时问 的分块式改进算法。( 5 ) 基于正交基的分形压缩方法。( 6 ) 与演化算法相结合的方 法。( 7 ) 与遗传程序设计相结合的方法。( 8 ) 其它方面的改进：如拼贴定理的改进、 分彤图像压缩的收敛性研究等。 1 3 本文的主要工作 围绕本章第一节提出的问题，本论文具体的内容安排如下：第一章绪论提 出问题及分形图像压缩研究进展：第二章介绍了基于遗传算法的分形图像压缩 的两个核心理论：迭代函数系统1 f s 和遗传算法的基本理论；第三章具体描述- r 基 j 遗传算法的分形图像压缩基本思想和算法实现过程；第四章对实验结果分 析与探讨；第五章提出一种基于遗传算法的异构分布式并行分形图像压缩算法 思想和一些难点的解决方案；第六章为总结与展望。 武汉理工大学硕士学位论文 第2 章基于遗传算法的分形图像压缩算法理论基础 2 1 迭代函数系统i f $ 基本理论 2 1 1 迭代函数系统概述 曼德勃罗特( m a n d e l b r o t l 揭示了分形的本质特征，确定了分形几何的理论框 架 2 卜美国的b a r n s l e y 与s l o a n 发现了把图形简化为一系列仿射变换的般过 程，并定义了迭代函数系统( i t e r a t e df u n c t i o ns y s t e m ) ，这项技术为图像压缩及传 送开辟了令人振奋的前景。i f s 既包含了确定性的过程也包含了随机的过程，是 目前利用数学系统去解析构造分形图形最为成功的理论8 1 。至今，i f s 仍是分形 图像压缩的核心理沧，本论文所介绍的压缩算法就足基于i f s 理论的。 仿射变换是一种实现几何变换的公式，它可以按比例放大或缩小图形，使 图形旋转或位移，甚至使图形产生畸变。若用一组为数不多的仿射变换就能够 绘出引人入胜的作品。由于这种类型的变换会使任何点集内的点之间的距离发 生收缩，被称为收缩变换，并且这种变换不改变原图形的形状。当反复不断地 应用若十变换公式时，这些公式就构成了一个迭代函数系统。因此收缩和保形 性是i f s 方法中所使用的仿射变换的关键性质。大多数图像在一定程度上是由 与整体相似的各部分组成的。即使对于复杂的图像，也能由一i f s 中一系列仿射 变换利用随机迭代的方法获得f 9 1 。 基二i f s 理论的分形压缩方法就是要把数量少又匹配最好的一个i f s 找出 来，仅需这组压缩变换的系数，就可以用简单的程序以任何尺度大小重构图像， 从而实现1 厂图像的压缩1 1 0 l 。 为了定义迭代函数系统，首先要介绍“完备度量空间”和“压缩映射”等 基本概念。 2 1 2 分形图像压缩的数学基础 2 1 2 1 分形图像研究空间 分形图像压缩所研究的空间为完备的度量空间( x ，d ) 与( 日弘) ) 。其中x 为 4 武汉理工大学硕：e 学位论文 空间或为一个集合，d 为空间上的距离函数。衄田记为空间x 中非空紧子集( 在 有限维空间上等价有界闭集) 的全体，h 定义为h t x ：j 上的距离f 称为豪斯多夫距 离) 1 1 】。实际上，我们可以把川想象成x 中全体二值图像的集合，因此，任 意一幅二值图像都可以由脚御的一个子集来表示。h 则可认为足任意两幅图f 子 集、之间的距离，其依赖于基本空间x 的距离d 。 定义2 1 ：度量1 1 1 2 1 设x 足个空间或一个集合。d ：x r 是x 到r 的函数，若慨，y ，z e x ， 对应有实数d y ) ，满足以下条件： ( 1 ) d ( x ，y ) 0 , d ( x ，y ) = o 当且仅当x y ； ( 2 ) d ( j ，y ) = d ( y ，z ) ； ( 3 ) a ( x ，z ) s a ( x ，y ) + a ( y ，z ) ；( 三角不等式) 则d 称是x 上的度量( 距离) 函数，瞄，d ) 记为度量( 距离) 空间。 实例2 - 1 1 如度量空间： 对于n 维实数空间，其度量函数为a ( x ，y ) 一( 兰k y i 】2 ) 1 胆，y l r ，i - 1 一， 此空间俾”，d ) 称为欧几里德( e u c l i d ) 空间。 ( 1 ) ( r 1 ，d ) ，a ( x ，y ) = i x y l ，v x , y e r 是一维的欧几里德空间。 ( 2 ) ( r 2 ，d ) ，d 似y ) 一( _ 一y 1 ) 2 + 2 一y 2 ) 2 ，y 1 ，z 2 ，y 2 e r 是二维的欧几 里德空间。 定义2 2 ：完备性1 设( x ，d ) 为度量空间，x n 圈= 1 ，2 ，。) 。 ( 1 ) 若。个序列k 囊。收敛j 二x x ，则乜矗。是一个柯西( c a u c “y ) 序列。 ( 2 ) 若x 中的每个柯西序列是收敛序列，即孰x ，s t 1 i 。d o 。，曲0 ，则称该 度量空间( x ，d ) 是完备的。 f 定义2 3 ：豪斯多夫度量1 设( x ，d ) 为完备的度量空间，h ( 习为x 上非空紧子集的全体。令a ，b e h 俾) ， 相应的a ，b c 盖。定义a 到b 的距离为： d ( a ，曰) = m a x a ( x , 曰) ；x a a ( x ，b ) = m i n d ( x ，y ) ；y e b ；x e a 则两子集a ，b 问的豪斯多夫度量( 距离妒定义为：h ( a ，曰) = d ( a ，口) vd p ，a ) ； 其中v 表示两个距离函数值中取较大的一个。 5 武汉理工大学硕士学位论文 i | 昌昌昌= = 昌昌昌昌昌墨昌暑昌昌昌昌昌薯昌昌= = 昌昌昌| 昌昌墨昌昌昌昌昌昌昌昌昌昌昌昌_ i 昌眚 2 ，1 2 2 迭代函数系统i f s 定义2 4 ：压缩映射及不动点l 设度量空间( j ，d ) ，t ：石一z 是一个映射：若存在常数c 【o ，1 】；s f 对 帆，y e x ，d ( r o ) ，丁o ”c d ( x ，y ) 则称t 是x 上的一个压缩映射。c 称为压缩网 子。若存在x 。x 使得t ( x 。) = x o ，则称是t 的不动点。 定理2 1 ：，1 i 动点定理1 完备度量空问上的压缩映射具有惟一的不动点。 i 定义2 5 ：迭代函数系统i f s l 设完备的度量空间( x ，d ) ，有n 个压缩映射乃：z x ( i - l 2 ，m ) ( 其压缩大l 子 分别为e l , c 2 ，c 。) 组成一个迭代函数系统( i t e r a t e d f u n c t i o ns y s t e m ) 。简称i f s ，记 作 x ，t 1 ，t 2 ，t n ，c = m a x ( c l ，c 2 ，c 。) 称为i f s 的压缩因子【1 3 卜 【定理2 2 ：分形空间上的压缩映射及不动点1 设留：五，兄，l ：c ) 是度量空间( 工，d ) 上的一个i f s ，则 ( 1 ) 定义映射w ：h 盯) 一h ( x ) ，即w ( 曰) - u ntp ) ，v b e h ( x ) 是在完备度量空 间( h ( x ) ， ) 上的压缩映射，其压缩因子是c ，日jh ( w ( a ) ，w p ”s c + h ( a ，b ) 。 ( 2 ) 压缩变换w 存在唯一的不动点。若3 a e h ( x ) ，满足a = w ( a ) 一6 w “) ， 则称a 为w 的不动点( 实质上是不动点集) ，又称为该i f s 的吸引子( 该定理又称 吸引子定理) ，而且不动点可以通过迭代而得到。则对v b e h ( x ) ，l i mw ”( 曰) = a ， 其中w o ( 口) = ( 口) ，而“) = w ( w ”1 p ”。 【定理2 - 3 ：拼贴定理l 设完备的度量空间( z ，d ) ，给定集合b e h ( x ) 和存在s ，0 ，若能找到一个 i f s 忸：w 1 ，w 2 ，w n ：c i ( o s c s l ) ，使： h ( b ，u n m 俾) s ，则 f 一1 n h ( b ，a ) j h ( b ，u w i ( b ) ) o c ) ss 0 一c ) ， i = 1 其中h 是豪斯多夫距离，而a 是该i f s 的不动点( 吸引子) 。 拼贴定理也可作以下更形象的描述：如果试图找一个i f s ，使其吸引子与某 个给定的集合部分相似或相近，我们还必须在给定的图像空间中找一组收缩变 换，使得用给定的集合通过各收缩映射变换后得到自身的拷备，并能拼贴成一 6 武汉理工大学硕二e 学位论文 个新的集合，且与原定的整幅图像十分相i ! i 1 1 4 1 。 【实例2 2 】枫叶的拼贴图：左边为拼贴而成图像( i f s 的吸引子) ；右边轮廓部分表 示拼贴的过程【1 5 】。 图2 - 1 ：枫叶拼贴图 由图2 - 1 可以看到，这样一个外形复杂的集合，我们可以用一个i f s 来表示， 而记录这个i f s 只需寥寥几个压缩变换参数，在本例中参数的个数为4 * 6 = 2 4 个 ( 参见表2 1 ) 。 表2 - l 枫叶的i f s wabcdc f 1o 6o00 6o 1 8 o 3 6 20 6o00 60 1 8 0 1 2 30 4o 3一o 30 40 2 7 0 3 6 40 40 30 30 + 40 2 7 0 0 9 显然，将其应用于数据压缩或图像压缩中，可获得极高的压缩比。 2 1 2 3 二维压缩仿射变换 定义2 - 6 ：线性变换1 若映射t ：r ”一r 一，对v x , y r “，a 只满足 ( 1 ) r ( x + y ) = 丁+ t ( y ) ： ( 2 ) t ( a x ) = 灯( x ) ；则变换z 称为线性变换。线性变换通常可以用矩阵表示。 若当且仅当x ：0 时有丁x 1 ：0 ，则该线性变换称为非奇异的。 f 定义2 7 ：仿射变换1 若变换s ：r ”一只“，s 0 ) = 丁( 砷+ “) ， 换s 称为仿射变换。仿射变换是平移、 t 是非奇异的线性变换，a e r “，则变 旋转、伸缩以及反射的组合，其在不同 方向上可以有不同的伸缩比。注意，仿射变换不是线性变换，其不满足线性变 换的定义。 武汉理工大学硕士学位论文 几种常用典型仿射变换 1 6 1 ：相等、缩放、反射、位移、相似、旋转、扭曲 或剪切。将这些基本仿射变换加以组合，还可以构成所有其它复杂的仿射变换。 定义2 - 8 ：二维压缩仿射变换l 二维欧氏空间r 2 中的仿射变换w ：r 2 一r 2 具如下的形式1 1 7 1 ： 似z ，y ) = ( a , x + 缈+ p ，c 茁+ 毋+ ，) ，口d b c 一0 ， r 口 悯吨炉”雕l x l y + ； = 埘m 其中口，b ，c ，d ，岛，r ，则称 为二维仿射变换。其中a 2 ： ，丁2 ； 。当线性部分a 是压缩的，该仿射变换 就是压缩的，则为二维压缩仿射变换。则定义在二维空间，2 - 【o 棚2 上的压缩仿 剁变换所组成的迭代函数系统日n d 为：i f s 2 ，m ，w 2 ，j ，为定义在二维空问 ，2 上的压缩仿射变换。为保证w y ) u 1 2 ，则二维压缩仿射变换的参数需满足以 f 条件： ( 2 1 ) 汁算方法详解如下： ( 1 ) 因为w ( o ，o ) e t 2 ，把z = o ，y o 代入到上面不等式组中，解得o s p s l ，o s f s 1 ； ( 2 ) 凶为w o , o ) e _ ，2 ，把x = 1 ，y = 0 代入到上面不等式组中，解得 一e s 口s 1 一e , - e j b e l 一e ： ( 3 ) 因为w ( o ，1 ) e l2 ，把z = o ，y = 1 代入到上面不等式组中，解得 一，s c s l 一f ，一，量d s l 一f ； ( 4 ) 因为w ( 1 ，1 ) e 1 2 ，把z = 1 ，y = 1 代入到上面不等式组中，解得0 4 十6 + p s l ， 0 s c + d + _ rs 1 ； 即二维压缩仿射变换的参数需满足以下条件： 表2 2 二维压缩仿射变换参数的条件 8 l 1 s s p r， + 妙方 + 甜 甜 s o o f_，1_【 武汉理工大学硕二e 学位论文 2 2 遗传算法基本理论 人自然是人类获得灵感的源泉0 8 1 。几百年来，将生物界所提供的答案应用 于实际问题求解己被证明是一个成功的方法，并且已经形成一个专f 1 的科学分 支仿生学( b i o n i c s ) 【2 1 。我们知道，自然界所提供的答案是经过漫长的自 适应过程演化过程而获得的结果。人类也可以利用这一过程木身去解决。 些较为复杂的问题。这样，我们就不必非常明确问题所描述的全部特征，只需 要根据自然法则来产生新的更好解。遗传算法正是基于这种思想而发展起来的 一种通用的问题求解方法。遗传算法( 简称g a ) 是在本世纪六七十年代由美国 m i c h i g a l l 大学的j h h o l l a n d 教授及其同事发展起来雕j 1 9 1 。 在本节中，主要介绍遗传算法的基本理论，它们将是用遗传算法解决分形 图像压缩方泫所遵循的基本步骤。 2 2 1 遗传算法的基本特征 遗传算法基木特征如下： f 1 1 智能性：遗传算法的智能性包括自组织，自适应和自学习性等。应用遗传算 法求解问题时，在确定了编码方案，适应值函数及遗传算子以后，算法将利用 演化过程中获得的信息自行组织搜索。遗传算法的这种智能性也赋予了它具有 能根据环境的变化自动发现环境的特征和规律的能力f 2 0 1 。 f 2 1 本质并行性：遗传算法的本质并行性表现在两个方面：一是遗传算法是内在 并行的，即遗传算法本身非常适合大规模并行。最简单的并行方式是让几百甚 至数干计算机各自进行独立种群的遗传计算，运行过程中甚至不进行任何通信 f 独立的种群之间若有少量的通信一般会带来更好的结果) ，等到运算结束时才通 信比较，选取最佳个体，这种并行处理方式对并行系统结构也没有什么限制和 要求。n r 以说，遗传算法适合在目前所有的并行机或分布式系统上进行并行处 理，而且对其并行效率没有太大的影响。二二是遗传算法的内含并行性，由于遗 传算法采用种群的方式组织搜索，从而它可以同时搜索解空间内的多个区域， 并相互交流信息，这种搜索方式使得它虽然每次只执行与种群规模n 成比例的 计算，而实质上己进行了大约o ( 3 1 次有效搜索。这使得遗传算法能以较少的计 算获得较人的效益。 ( 3 1 多解性：遗传算法记录的是一个群体，它可以记录多个解而不同于局部搜索、 9 武汉理t 大学硕： 学位论文 禁忌搜索和模拟退火仅仅是一个解，这多个解的进化过程正好适合于多目标优 化问题的求解。 f 4 1 过程性：遗传算法通过自然选择和遗传操作等自组织行为来增强群体的适应 性。遗传算法模拟的是一个过程，实施的也是一个过程。在这个过程中，算法 本身无法削定个体所处解空n 的位置，因此需要人为干预( 即事先确定终止准 则) 才能终止， ( 5 ) 不确定性：遗传算法的不确定性是伴随其随机性而来的。遗传算法的主要步 骤都含有随机因素。从而在算法的演化过程中，事件发生的与否带有很大的不 确定性。 ( 6 ) 群体性：遗传算法是通过群体的演化来进行的。演化的主体是一个群体而不 是单独的一个个体。 ( 7 ) 内在学习性：学习是一种有选择保留的行为。知识通过反复实践按得。学习 是演化过程自身所具有的不可与其分割的行为方式【2 1 1 。这种行为方式体现在遗 传算法的整个过程中。 ( 踯统计性：遗传算法的种群方式决定它是一个统计过程。在每一代演化都要进 行统计，以确定个体的优劣并推动演化的进程。 f 9 1 稳健性：算法的稳健性是指在不同条件和环境下算法的适用性和有效性。因 为遗传算法具有自然系统的自适应特征，算法在效率和效益之间的权衡使得它 能适j h 不同的环境并取得较好的效果。 ( 1 0 ) 整体优化：遗传算法的群体性使得该算法能够保持在解空间不同区域中多个 点的搜索，因此遗传算法能够以更大的概率找到整体最优解。 这些崭新的特点使得遗传算法不仅能获得较高的效率而且具有简单、易于 操作和通用的特性，而这些特性正是遗传算法越来越受到人们青睐的主要原冈 之一【2 2 】。 2 2 2 设计遗传算法的基本步骤 遗传算法主要由6 个基本步骤，确定编码方案、确定适应值函数、确定选 择策略、算法参数的设置、设计遗传算子、确定算法终止条件 2 3 1 。针对本论文 所要解决的问题，还需步骤7 确定解码方法。 ( 1 ) 确定编码方案：遗传算法求解问题不是直接作用在问题的解空间上，而是解 1 0 武汉理工大学硕= t 学位论文 的某种编码表示。选择何种编码表示有时将对算法的性能，效率等产生很大的 影响。编码表示方案的选取很大程度一卜依赖于问题的性质及遗传算子的设计。 本论文中采用的是实数编码方法，这种方式更贴近于自然。 ( 2 ) 确定适应值函数：适应值是对解的质量的一种度量，它通常依赖于解的行为 与环境( 即种群) 的关系【2 4 1 。解的适应值是演化过程中进行优劣个体选择的重要 依据。所以适应值评价函数是遗传算法与问题的接口，对遗传算法的收敛和结 果影响很大。遗传算法通常是使用评价函数的数值来确定遗传选择概率f 2 5 1 。 ( 3 ) 确定选择策略：优胜劣汰的选择机制使得适应值大的解有较高的存活概率， 这是遗传算法与一般搜索算法的主要区别之一2 6 1 。不同的选择策略对算法的性 能也有较大的影响。遗传算法常用的选择策略有：轮盘赌选择法( r o u l e t t ew h e e l s e l e c t i o m 、随机遍历抽样法( s t o c h a s t i c u n i v e r s a l s a m p l i n g ) 、局部选择法( 1 0 c a l s e l e c t i o n ) 、锦标赛选择法( t o u r n a m e n ts e l e c t i o n ) 。本论文采用了轮盘赌选择法。该 策略有一个明显的优点：群体成员在转盘选择策略下都有被选择的机会，而在 其它一些选择策略中，具有较小适应值的个体将被剥夺生存的权力。 f 4 ) 算法参数设置：遗传算法的参数主要包括群体大小、算法的执行代数、选择 概率、杂交概率、变异概率等，不同的参数取值使遗传算法体现不同的行为。 针对实际问题还需考虑其它一些辅助性的控制参数的设黄。 ( 5 、设计遗传算子：遗传操作是算法的主体，是实现信息遗传、优胜劣汰思想的 重要步骤。主要包括复制( r e p r o d u c t i o n ) 、杂交( c r o s s o v e r ) 以及变异( m u t a t i o n ) 等操作。 ( 6 ) 确定算法终止条件：由于遗传算法没有利用目标函数的梯度等信息，所以在 演化过程中，无法确定个体在解空间的位置2 7 卜常用的方法是预设一个最大的 演化代数或算法在连续多少代以后解的适应值没有什么明显的改进时，即终止。 或者当找到的个体的评价函数值的精度达到一定要求后，通常也认为可终止。 ( 7 ) 确定解码方法：从遗传子型到表现型的映射2 8 】。解码方法依赖于具体的问题。 2 2 3 分布式并行遗传算法研究现状 研究表明，遗传算法本身具有内在的以及内含的并行性，其中正是内在的 并行性决定了遗传算法特别适合大规模并行。一些实例证明，在并行或分布式 系统上进行演化计算，不仅可以提高解题的速度和解的质量，甚至可以获得超 线性加速比。 1 1 武汉理工大学硕士学位论文 遗传算法并行实现的方法和策略大多都来自于种群遗传学( p o p u l a t i o n g e n e t i c s ) 。简而言之，传统遗传算法总是会出现过早收敛。而在并行遗传算法中 种群被分离成一些小的子群体，从而形成了隔离的物种。当收敛之后将一些个 体从小同的子种群输入某一子种群，则带来一些新的基因构造块；同时迁移来 的个体将对子群体的平均适应值带来很大的改变。这两个因素加在一起将诱导 物种形成，从而伴随着一个快速进化阶段。这样，使并行遗传算法能在一定程 度上避免过甲收敛的发生。 如上文所述，对遗传算法进行并行处理是很自然的解决途径。目前并行遗 传算法的实现方案人致可分为三类。 第一类方案称作全局型方案，又名主从式模型( m a s t e r - s l a v em o d e l ) 。需要 注意的是，主从式模型在适应值评价上很费时，且在远远超过通讯时间的情况 下才有效，否则通讯时间超过计算时间，反而会降低整个演化的速度。 第一类方案为独立型方案，) 己名粗粒度模型( c o a r s e g r a i n e dm o d e l ) 。粗粒 度模型也称岛屿模型( i s l a n dm o d e l ) ，基于粗粒度模型的遗传算法也称为分布式 遗传算法( d i s t r i b u t e dg e n e t i c a l g o r i t h m ，d g a ) ，它是目前应用最广泛的一种并 行遗传算法。岛屿模