（通信与信息系统专业论文）应用遗传算法研究用于高密度信息存储的多元环形滤光片.pdf

浙江工业大学硕士学位论文 应用遗传算法研究用于高密度信息存储的 多元环形滤光片 摘要 随着光存储技术的发展，如何提高光盘存储密度备受关注。在高密 度光学信息存储领域中，由衍射引起的分辨率限制是影响存储密度进一 步提高的关键问题。采用远场超分辨技术可以突破分辨率的限制以达到 提高目前通用光盘存储系统存储密度的目的。本文设计了两种满足这一 要求的超分辨多元环形滤光片一一二元环形滤光片和四元环形滤光片。 超分辨二元环形滤光片的设计是一个多目标优化问题。本文在对一 种多目标遗传算法v e g a 算法进行改进的基础上，提出一种i v e g a 算法， 并将其应用于高密度信息存储中二元超分辨环形滤光片结构参数的设 计。而超分辨四元环形滤光片的代价函数则是一个多峰函数，为避免遗 传算法陷入局部最优值并提高遗传算法的局部搜索能力，本文设计了基 于神经网络的遗传算法以用于四元环形滤光片结构参数的设计。 计算机仿真结果显示，二元环形滤光片能使横向的半峰全宽半径值 减小2 8 ，而四元环形滤光片则使得这一数值减小3 0 ，因而减小了 记录光斑提高了记录密度。另一方面任何一种环形滤光片都能使变长， 减小了在记录过程中因为光盘的微小波动而引起的记录信息的错误率。 实际光学实验表明，二元环形滤光片和四元环形滤光片确实达到了 理论分析的结果。但是四元环形滤光片有较大的衍射情况，可能因此而 浙江工业大学硕士学位论文 影像到光斑刻录的质量。 关键词：遗传算法，高密度信息存储，多元环形滤光片，超分辨率 浙江工业大学硕士学位论文 u s i n gt h eg e n e t i ca l g o r i t h mt os t u d yt h em u l t i p l e a n n u l a rf i l t e r sf o r t h eh i g hd e n s i t ys t o r a g es y s t e m a b s t r a c t w i t ht h e d e v e l o p m e n t o f o p t i c a l d a ms t o r a g e t e c h n o l o g y , t h e i m p r o v e m e n to ft h es t o r a g ed e n s i t yh a sb e e np a i dm u c ha t t e n t i o n t o g e n e r a l l y , i ti sd i f f i c u l tt os o l v et h ep r o b l e mw i t ht h er e s o l v i n gl i m i t a t i o n c a u s e db yt h ed i f f r a c t i o n ，w h i c hm a k e sad e 印i n f l u e n c eo i lt h ei m p r o v e m e n t o ft h es t o r a g ed e n s i t yi nt h ef i e l do ft h eh i 曲d e n s i t ys t o r a g es y s t e m w ec a n m a k ea d v a n t a g eo ft h ef a rf i e l ds u p e r r e s o l u t i o nt e c h n i ct ob r e a ku pt h i s l i m i t a t i o n ，s ot h a tw ec a ni m p r o v et h es t o r a g ed e n s i t yo ft h ec o n v e n t i o n a l s t o r a g es y s t e mn o w a d a y s a c c o r d i n g l y , w ed e s i g n t w ok i n d so f s u p e r r e s o l v i n ga n n u l a rf i l t e r st os o l v et h ep r o b l e mi nt h i sp a p e r t h eb i n a r y a n n u l a rf i l t e ra n dt h em u l t i p l ea r m u l a rf i l t e r i nc o n s i d e r a t i o no fi t sn e e do ft h es o l u t i o nf o rm u l t i o b j e c t i v e o p t i m i z a t i o n ，t h es u p e r r e s o l v i n ga n n u l a rb i n a r yf i l t e r sa r ed e s i g n e do nt h e g r o u n do fm u l t i o b j e c t i v eo p t i m i z e dg e n e t i ca l g o r i t h m s ( m o g a ) t h e r e f o r e ， w ep r o p o s ean e wk i n do ft h eg e n e t i ca l g o r i t h m sa si v e g a ，b a s e do nt h e m e t h o di nt h ev e c t o re v o l u t i o n a r yg e n e t i ca l g o r i t h m ( v e g a ) a n dt h ep a r e t o o p t i m a lc o n c e p t i o n t h e nw ea p p l y i tt o d e s i g n i n gt h es u p e r r e s o l v i n g a n n u l a rb i n a r yf i l t e r s o nt h eo t h e rh a n d ，w ed e s i g na n o t h e rk i n do fg e n e t i c ；针 浙江工业大学硕士学位论文 a l g o r i t h mt of i g u r eo u tt h eo p t i m a lv a l u eo ft h em u l t i p l ea n n u l a r f i l t e r b e c a u s eo fi t sm u l t i p l ep e a kv a l u eo fi t sf u n c t i o n ，t h en e u r a ln e t w o r ki su s e d i nt h eg e n e t i ca l g o r i t h mt oi m p r o v et h el o c a ls e a r c h i n gp e r f o r m a n c eo ft h e a l g o r i t h r a a c c o r d i n gt ot h er e s u l to ft h ec o m p u t e rs i m u l a t i o n ，t h eb i n a r ya n n u l a r f i l t e r se n a b l et h ef w h md e c r e a s e s2 8 0 1 1t r a n s v e r s ea n dt h em u l t i p l e a n n u l a rf i l t e rg e t3 0 d e c r e a s e ，w h i c hb o t hh e l pt or e a l i z et h ea i mo f i m p r o v i n gt h ed e n s i t yo fi n f o r m a t i o ns t o r a g e m e a n w h i l e ，b o t ho ft h e mc a n a l s om a k et h ed e p t ho ff o c u sl o n g e r , t h e r e f o r ec a l la v o i dt h em i s t a k ei nt h e p r o c e s so f r e c o r d i n g r e a d i n gt h ei n f o r m a t i o nb e c a u s eo f t h es m a l lu n d u l a t i o n o f t h e o p t i c a ld i s k t h ep h y s i c a le x p e r i m e n ts h o w st h a tt h er e s u l to ft h ee x p e r i m e n ti s c o n s i s t e n tw i t ht h et h e o r e t i ca n a l y s i s h o w e v e r , t h e r ei sm u c hd i f f r a c t i o ni n t h ei m a g eo f t h e m u l t i p l ea n n u l a rf i l t e r s a n dt h a tm a y h a v ei n f l u e n c eo nt h e q u a l i t yo f t h eo p t i c a lw r i t i n g k e yw o r d s ：t h eg e n e t i ca l g o r i t h m ，t h eh i 曲d e n s i t ys t o r a g e ， m u l t i p l ea n n u l a rf i l t e r s ，s u p e r r e s o l u t i o n 浙江工业大学 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行 研究工作所取得的研究成果。除文中已经加以标注弓i 用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的研究成果，也不含为获得浙 江工业大学或其它教育机构的学位证书而使用过的材料。对本文的研究作 出重要贡献的个人和集体，均已在文中以明确方式标明。本人承担本声明 的法律责任。 作者签名：描洋望日期：纠年 f 月；阳 f 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权浙江工业大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印，缩印或扫描等复制手段保存 和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密。 ( 请在以上相应方框内打“”) 日期易习年f 月岁日 醐2 彳厂月j 日 浙江工业大学硕士学位论文 第1 章绪论 1 1遗传算法的提出 3 0 年来，人们从不同角度对生物系统及其行为特征进行了模拟，产生了一些对 现代科级发展有重大影响的新兴学科。例如，对人类模糊思维方式的模拟产生了模 糊集合理论；对动物脑神经的模拟产生了人工神经网络理论；对自然界中动、植物 免疫机理的模拟产生了免疫算法；而对于自然乔中生物进化机制的模拟就产生了进 化算法( e v o l u t i o n a r yc o m p u t a t i o n ) 理论。 进化计算是指以进化原理为仿真依据，在计算机上实现的具有进化机制的算法 和程序。目前，进化计算侧重于算法的研究，因此有时也称之为进化算法 ( e v o l u n t i o n a r ya l g o r i t h m s ，e a ) 。以性质区分，现有的进化算法又可细分为：基本遗 传算法( 6 h ) 、侧重于数值分析的进化策略( 五洛) 、介于数值分析与人工智能间的 进化规划( e p ) 、偏向进化的白组织和系统动力学特性的进化动力学( e v o l u t i o n a r y d y n a m i c s ) 、偏向以程式表现人工智能行为的遗传程序设计( g p ) 、适应动态环境学 习的分类系统( c l a s s i f i e r s y s t e m ) 、用于观察复杂系统交互的各种生态模拟系统( e c h o s y s t e m a n d e t c ) 、研究人工生命( a r t i f i c i a l l i f e ) 的元胞自动机( c e l l u l a r a u t o m a t a ) 以及模拟蚂蚁群体行为的蚁元系统( a n t s y s t e m ) 等。 虽然进化计算拥有如此多的分支，但任何分支在总体的算法结构上却基本相同， 都模拟生物进化的选择、交叉、变异的过程。 图1 - 1 ：进化计算框架结构 进化计算作为完整的体系，包括了最优性、统计分析、选择策略和相应判据等 内容。 基因型与表现型之间的关系是进化计算中的一个基本关系，在其复杂的非线性 关系中“一因多果”和“一果多因”是突出的两个特点。 表现型的变化是对象遗传结构和当时环境条件交互作用所致的结果。非线性效 果很明显，甚至相差很大的遗传结构可能会导致类似的行为。这样在研究基因型一 表现型相互关系及其进化过程中的规律时就必须充分利用非线性系统工具和随机 过程的统计测度理论，动力学机制也是必须加以研究的动态属性。适应度状态图描 述了适应度与基因型间的关系，自适应状态图则勾画了适应度与表现型之间的联系 状况。 浙江工业大学硕士学位论文 在进化计算中算子占有重要的地位，相应的操作也应反映动态的机制。因此， 进化计算体系可归纳为： 进化计算= 进化算子+ 进化操作+ 选择策略+ 进化计算理论。 而遗传算法作为进化算法的一支，是近年来研究的重点。而因为遗传算法本身 的优势和实际的使用意义，多目标遗传算法成为众多领域的关注焦点。 1 2 基于遗传算法的多元环形滤光片的研究 进入2 l 世纪，人类迎来了信息时代。计算机技术的发展，光通信网络技术的日 渐成熟，使得海量信息处理技术成为人们关注的热点。解决好这一技术，将突破信 息技术发展的瓶颈，使得信息技术跨上新的台阶。 信息存储可以有三种主要的实现方式：具有最高存取速度的半导体存储( 计算机 内存、f l a s h 等) ，价格低廉、携带方便的光存储器( 光盘、d v d 等) ，以及具有最 佳综合性能的磁存储器( 包括声音记录、图像记录、数据记录三种) 。这三种信息 存储方式各有自己的适用范围，彼此不可替代。 作为现今主流的存储技术之一的光盘存储技术，提高存储密度的主要途径可以 通过两种方式来实现。一是采用新型的存储材料，二是采用新兴物理研究新成果。 本文即采用新兴的二元光学设计一种多元环形滤光片以提高光学刻录系统的性能。 二元光学是基于光波衍射理论发展起来的一个新兴的光学分支学科，是光学与 微电子技术相互渗透、交叉而形成的前沿学科。基于计算机辅助设计和微米级加工 技术制成的二元光学元器件具有重量轻、易复制、造价低等特点，并能实现传统光 学器件难以完成的新功能。鉴于以上一些优点，二元光学元器件已广泛用于数据存 储、光通信、光学传感、光计算、激光医学、娱乐消费以及其他特殊光学系统中。 二元光学器件目前已然发展到第三代。随着它的发展，其优化设计方法也随之 不断地被创新和完善，从而设计得到更为优越的二元光学器件结构。本文即采用遗 传算法对理论推导得到的二元环形滤光片结构参数的数学函数进行优化，从而得到 函数的优化解也即滤光片的优化结构参数，并制作出相应的滤光片，搭建相关的光 学平台，通过图像分析手段，验证滤光片对光学刻录系统刻录焦斑性能的提高( 包 括光斑的直径大小以及光斑光强的均匀性) 。 1 3 本文内容以及研究重点 本文从遗传算法理论开始，着重介绍遗传算法在高密度信息存储系统设计上的 应用。本文所设计高密度信息存储系统，其关键是多元环形滤光片的设计。而多元 环形滤光片的设计，主要在于函数的优化。遗传算法在此解决的正是求解函数的最 优解。由此得到的最优解最后被具体实现，制作出相应的多元环形滤光片，并构建 了光学实验平台，验证理论分析的正确性。 本文共分六章。第一章主要介绍遗传算法被提出的背景。遗传算法实际是模拟 生物进化过程的一种算法，是进化计算的一个重要分支。 浙江工业大学硕士学位论文 第二章系统地阐述了遗传算法的基础理论，包括遗传算法的发展历程，遗传算 法的优缺点以及遗传算法的具体流程和程序实现方法。由于遗传算法在局部搜索上 的局限性，很多局部搜索算法被结合进入遗传算法，以克服其缺点。而遗传算法在 具体的程序实现上则以初始化和随机数发生器为关键。在实际的操作中，这两者均 被编写为函数直接调用。 第三章着重对遗传算法在函数优化问题上的应用进行了论述。尤其是有约束条 件的函数优化问题，它更具有实际应用的意义。文章主要介绍了g e n o c o p 的含约 束条件优化问题的解法。 第四章首先介绍了信息存储技术的概况。之后对基本的光学原理进行了阐释。 主要介绍了惠更斯一菲涅耳原理，并根据源点和场点距孔径平面的远近，分析了衍 射的两种类型一一菲涅耳衍射和夫琅和费衍射。然后对圆孔衍射焦点附近的三维光 分布的情况进行了分析，推导出在焦平面和轴向平面上的强度分布表达式。 第五章主要讨论了多元环形滤光片的实际设计方法，包括二元环形滤光片的设 计和四元环形滤光片的设计。在两者的设计中，针对二元环形滤光片的函数求解， 采用了基于p a r e t o 择优思想的改进的v e g a 算法；针对四元环形滤光片，则考虑到 函数本身的多峰特征，采用了基于神经网络的遗传算法。同时对两种滤光片的理论 设计结果进行了比较。 第六章主要介绍了论文作者所进行的实验研究结果。主要包括环形滤光片的掩 模版设计，环形滤光片的制作工艺，光学实验平台的搭建以及实验结果的分析四部 分的内容。 本文研究的重点，在于遗传算法在多元环形滤光片设计中的应用。重点讨论了 基于p a r e t o 优化思想的改进的v e g a 算法在二元环形滤光片设计中的应用和基于神 经网络的遗传算法在四元环形滤光片设计中的应用。同时制作实现了二元环形滤光 片和四元环形滤光片实物，并搭建了验证理论结果的光学实验平台，最后通过计算 机图像分析技术分析验证了二元环形滤光片和四元环形滤光片的性能。 浙江工业大学硕士学位论文 第2 章遗传算法基础理论 2 1 遗传算法的发展历史 2 0 世纪7 0 年代初期，美国m i c h i g a n 大学的j o h nh o l l a n d 与其同事、学生根据 达尔文提出的自然系统中生物的适应过程，模拟生物进化的机制，研究形成了一个 较为完整的理论和方法遗传算法。 h o l l a n d 将基于遗传的机器学习方法发展成为认识系统c s l 的分类系统学习方 法，为遗传算法奠定了重要的基础。1 9 7 5 年，h o l l a n d 的学生d ej o n g 发表了“a n a n a l y s i so f t h eb e h a v i o ro f ac l a s so f g e n e t i ca d a p t i v es y s t e m s ”的学位论文，为遗传 算法应用于函数最优化问题指明了方法。而g r e f e n s t e t t e 开发的第一个遗传算法软件 g 舰娓s i s 使遗传算法得以普及推广。1 9 8 9 年，美国伊利诺大学的g o l d b e r g 出 版了一本在遗传算法研究领域影响巨大的专著“g e n e t i ca l g o r i t h m s 加s e a r c h ， o p t i m i z a t i o n ，a n dm a c h i n el e a r n i n g ”。该书对遗传算法的理论及其在各个领域中的 应用展开了详尽深入的讨论。1 9 9 2 年，m i e h a l e w i c z 出版了又一本很有影响力的著 作“g e n e t i ca l g o r i t h m s - - d a t as t r u c t u r e s = e v o l u t i o np r o g r a m s ”，使得遗传算法在 最优化问题上的应用迈进了一大步。 近年来，许多人提出的“遗传算法”已与h o l l a n d 最初提出的算法大相径庭， 实数形式的基因、新的交叉和变异方式、特殊算子的引用和日益复杂精巧的选择方 法等都是在当初的基础上的改进。但是这些改进仍然是因循生物进化过程的大框架， 故而仍然可把这些新算法归为一套遗传算法的“算法簇”。 遗传算法遵循生物进化的过程，将整个算法依次分为初始种群产生，( 个体) 选 择，( 个体间基因) 交叉，( 基因) 变异和( 个体在种群中) 适应性判断。很多方面 的研究都集中在通过尝试新的数学手段来改变其中一个步骤的计算方法，从而提高 整个算法的性能( 或避免陷入局部极值，或避免过早收敛，或提高运行速度) 。然而 在多目标优化领域，研究的焦点则集中于遗传算法整体结构的调整，逐渐形成一个 新的研究分支：多目标进化算法( m u l t i o b j e c t i v ee v o l u t i o n a r y a l g o r i t h m ，m o e a ) 。 2 2 多目标遗传算法 多目标优化问题( m u l t i o b j e c t i v eo p t i m i z a t i o np r o b l e m ，m o p ) 的经典求解方法 是使用目标函数线性组合法或基于p a r e t o 概念的方法。所谓p a r c t o 最优概念，即是， 不存在比其中至少一个目标好而其它目标不劣的更好的解，也就是不可能通过优化 其中部分目标而其它目标不至于劣化。p a r e t o 最优解集中的元素就所有目标而言是 彼此不可比较的。 1 9 6 7 年，r o s e n b e r g 提出可用遗传搜索算法来求解m o p ，而直到1 9 8 5 年，才 出现第一个多目标遗传算法一基于向量评估的v e g a 算法。”，但在本质上，该算 法是一种间接的加权算法而非基于p a r e t o 最优概念。1 9 9 0 年后，众多不同的基于 4 浙江工业大学硕士学位论文 p a r e l o 思想的m o e a 相继被提出，针对m o p 的遗传算法研究进入了繁荣期。其中 较有代表性的是1 9 9 3 年f o n s e c a 与f l e m i n g 提出的m o g a “1 算法，它基于p a r e t o 优劣定义，提出了基于排序的适应值赋值策略，共赏函数与小生境技术，约束杂交 技术，算法执行相对容易且效率高但受小生境大小影响较大，不过f o n s e c a 与f l e m i n g 已经从理论上解决t d , 生境大小的计算问题。1 9 9 4 年，s r i n i v a s 和d e b 提出了n s g a 算法，它基于对多目标解群体进行逐层分类的方法，可允许任意个优化目标个数， 非劣最优解分布均匀。其后，d e b 又于2 0 0 2 年提出了二代n s g a i i 3 1 算法，通过 引进新的解给体快速非劣性排序和多样性保护方法克服了一代计算效率低，计算复 杂度高的缺点。几乎同时，h o r n 和n a f p l i o t i s 也与1 9 9 4 年发表了基于p a r e t o 最优概 念的锦标赛选择机制的n p g a 1 算法，它能很快找到一群较好的非劣最优解。1 9 9 8 年，z i t z l e r 和t h i e l e 又提出了一种采用精英保留策略的多目标进化算法s p e a 5 1 j 算法计算复杂度大大降低。而k n o w l e s 和c o m e 提出的一种类似( 1 + 1 ) - - e s 进化 策略的p a e st 8 1 算法则又将算法的计算复杂度降了一阶。此外，还有一些基于决策 者预期目标的目标向量方法，如目标规划、目标实现、最大最小法等等，它们一般 均以计算效率高见长，但都短于不易确定各优化指标的预期目标。 v a nv e l d h u i z e n m 依据最优解的形成与决策过程的交互方式( 如：先验偏好链 接、进程偏好链接和后验偏好链接) ，从决策的观点出发对现有的m o e a 方法进行 了较为系统的分类。从统计数据来看，目前较为流行后验方式，而其中又以p a r e t o 选择策略为主，且遗传算法的应用率又是其它进化算法( 如：进化规划、进化策略 等) 的9 倍。故而可见，在目前的m o e a 设计中，基于p a r e t o 的遗传算法是应用焦 点。 2 3 遗传算法的特点 遗传算法是一种优化算法，以快捷并准确地搜寻出计算目标的最优解为首要目 的。而在遗传算法之前，传统的优化算法如：枚举法、启发式算法和搜索算法已经 有了成熟的应用。 2 3 1 传统优化算法的特点 枚举法：枚举出可行解集合内的所有可行解，以求出精确的最优解。对于连续 函数，该方法要求先对其进行离散化处理，这样就可能因离散处理而永远达不到最 优解。此外，当枚举空间比较大时，该方法的求解效率比较低，有时甚至在目前先 进计算工具上无法求解。 启发式算法：寻求一种能产生可行解的启发式规则，以找到一个最优解或者近 似最优解。该方法的求解效率比较高，但对每个要求解的问题必须找出其特有的启 发式规则，而这个启发式规则一般没有通用性，不适合其他问题。 搜索算法：寻求一种搜索算法，该算法在可行解集合的一个子集内进行搜索操 作，以找到问题的最优解或者近似最优解。该方法虽然保证不了一定能够得到问题 5 浙江工业大学硕士学位论文 的最优解，但若适当利用一些启发知识，就可以在近似解的质量和效率上达到一种 较好的平衡。 2 3 2 遗传算法特点 随着问题种类的不同以及问题规模的扩大，要寻求一种能够以有限的代价来解 决搜索和优化的通用方法。而遗传算法正是为我们提供的一个有效的途径，它不同 于传统的搜索和优化方法。其主要特点在于： ( 1 )并行性。遗传算法按并行方式搜索一个种群数目的点，而不是单点。其 并行性表现在两个方面：其一是遗传算法的内在并行性( i n h e r e n tp a r a l l e l i s m ) ，即 遗传算法本身非常适合大规模并行，比如最简单的并行方式是让几百甚至数千台计 算机各自进行独立种群的演算，运行过程中甚至不进行任何通信，等到运算结束时 再通信比较，选取最佳个体。这样的并行方式对并行系统结构没有什么限制和要求， 所以，遗传算法适合在目前所有的并行机或者分布式系统上进行并行处理，以提高 运算速度。 其二是遗传算法的内含并行性( i m p l i c i t p a r a l l e l i s m ) 。由于遗传算法采用种群的 方式组织搜索，因而可以同时搜索解空间的多个领域，并相互交流信息。使用这种 搜索方式，虽然每次只执行与种群规模n 成比例的计算，但实际上已进行了大约 次有效搜索，这就使遗传算法能够以较少的计算获得较大的收益。 ( 2 )遗传算法只需要确定问题的目标函数( 适应度函数) ，并不需要其他辅 助的要求( 如函数连续性，微分性等) ，适用问题的范围较大。 ( 3 )遗传算法的运算主要在参数经过编码的码元字串上，而并非参数本身， 所以在搜寻分析上不受参数连续性的限制。 ( 4 )遗传算法对于给定的问题，可以产生许多的潜在解，最终选择可以由使 用者确定( 在某些特殊情况下，如多目标优化问题不止一个解存在，有一组p a r e t o 最优解。这种遗传算法对于确认可替代解集而言是特别合适的) 。 2 4 遗传算法流程 遗传算法采纳了自然进化模型，如选择、交叉、变异等。图2 - i 表示了基本遗 传算法的过程。计算开始时，一定数目n 个个体也即初始种群随机地初始化，并计 算每个个体的适应度函数，第一代随即产生。经过一定的优化准则进行判断，若不 满足优化准则，则开始产生新一代的计算过程。为了产生截然不同的新一代，父代 要如同自然界生物繁衍一般，经过基因重组( 父代编码的重组) 而产生子代。而所 有的子代，又有一定的变异率( 子代编码的码值突变) 。然后，所有的子代的适应度 被计算，适应度高的群体被插入并代替父代中适应度低的个体，从而构成新的一代。 循环执行此过程，直到满足优化准则为止。 6 浙江工业大学硕士学位论文 图2 - 1 ：遗传算法流程图 2 4 1 种群初始化 初始种群的产生涉及到种群大小、染色体长度和运行最大世代数的确定，以及 决策变量的编码方式和种群产生方式的确定等事。 一般情况下，一个种群的个体数在3 0 至1 0 0 之间，过少或过多的种群个体数量 都会产生问题，前者会限制种群的多样性，使得算法过早收敛，达不到最优解，若 在多峰函数的情况下，还可能会陷入次优点；后者保持了种群的多样性，但是过大 的搜索空间会降低遗传算法的效率，甚至退化到随机搜索方式，此时遗传算法的一 些数学特性和强力的搜索能力便不复存在。 染色体的长度取决于变量的编码方式。现有的编码方式主要分二进制和实值两 种。一般情况下，遗传算法中大多采用单层的二进制串染色体表示方法。每一个决 策变量被编成一个二进制串，多变量的各个二进制串串在一起组成一条染色体，该 染色体通过二进制与实数值之间的转换关系式转换成的实数值即为一个个体。 c a r u a n a 和s c h a f f e r 【8 1 已经证明，在使用标准的二进制表示方法下，临近值白j 过大的海明( h a m m i n g ) 距离易导致搜索到欺骗性结果或无法有效地定位于全局最 优解上。有鉴于此，格雷码( g r e yc o d e ) 编码方式被提出，以改进和提高遗传算法 的局部搜索能力。另一方面，w i n t e r y 9 提出，使用实值表示的遗传算法在数值函 数优化上比二进制编码有更多的优点：在函数计算前，不需从染色体转换到实数值， 提高了算法的效率；相对二进制值，没有精度磨损；计算机内部高效的浮点表示可 7 浙江工业大学硕士学位论文 直接使用，减少了内存需求。 2 4 2 选择 根据相关文献显示1 1 0 - 1 2 1 , 选择的方式可以分为线性排序选择( l i n e a rr a n k i n g s e l e c t i o n ) ，锦标赛选择( t o u r n a m e n t s e l e c t i o n ) ，截断选择( t r u n c a t i o n s e l e c t i o n ) 。 1 线性排序选择 线性排序一般有轮盘赌选择法( r o u l e t t ew h e e ls e 跆c t i o n ) 、随机遍历抽样法 ( s t o c h a s t e cu n i v e r s a ls a m p l i n g ) 、局部选择法( 1 0 c a ls e l e c t i o n ) 等方法。其主要思想 均是采用对每个个体的适应度值分别与随机产生的随机数比较来决定选择与否。以 轮盘赌选择法为例：表2 1 表示了1 1 个个体适应度、选择概率和累积概率。为了选 择交配个体，需要进行多轮选择。每一轮产生一个【o ，l 】间的均匀随机数，将该随机 数作为选择指针来确定被选个体。例如，第一轮产生的随机数为0 8 1 ，则第六个个 体被选中，第二轮随机数为0 3 2 ，相应的第二个个体被选中；依此类推，第三、四、 五、六轮随机数分别为：o 9 6 ，0 0 1 ，0 6 5 ，o 4 2 ，则有第9 ，1 ，5 ，3 个个体依次被 选中。这样经过选择产生的交配种群由以下个体组成：l ，2 ，3 ，5 ，6 ，9 。 表2 - 1 ：轮盘赌选择法的选择概率计算表 斧倦i尹7 z 鼍黟爹缆? ”矽“铲一j 口“”“臻 鍪适应度 2 o ；。1 、8 l 61 41 21 00 8。0 6 + 0 。4 ， o ；2 。o t l 葫 + 选择概率 0 1 8o 1 6o 1 5o 1 3o 1 10 0 90 0 70 0 60 0 30 0 20 0 囊景积概率 0 t 黟，；0 = 3 4 t ，o 迥2 t 。；。9 。熬。曩稳。：壁，8 2 氛0 8 9 ：o 黪，0 ，9 & 。0 0 。i o o 毪 2 截断选择法 截断选择法为人工方法，它适合于大种群。在截断法中，个体按照适应度排序。 只有最优秀的个体能够被选择作为父个体，截断选择的参数叫做截断阈值( t r u r m ) 。 它定义为被选作父个体的百分比，取值范围为0 5 0 1 。在该阈值之下的个体不能 产生予个体。通常选择强度与截断阈值的关系如表2 - 2 ： 表2 - 2 ：选择强度和截断阈值的关系 其中选择强度为： s e l i n t m n c ( t r u n c ) = r r u c 4 1 - f f 一 多样化损失为： ( 2 1 ) 浙江工业大学硕士学位论文 l 鲫d f 。( 乃甜甩c ) = 1 t r u n c ( 2 2 ) 选择方差为： & ，玩，靠。( n 明c ) = 1 一砌岛概( z h w ) ( & 砌f 什。( 乃z 打配) 一z ) ( 2 渤 上式中石为下列高斯分布的积分下限： t r u n c = f 去 矽 3 锦标赛选择法 在此种选择方法中，随机地从种群中挑选一定数目( t o u r ) 个体，然后将最好 的个体选作父个体。这个过程重复进行直至完成个体的选择。锦标赛选择的参数为 竞赛规模t o u r ， 其取值范围为【2 ，n i n d 表2 - 3 表示了竞赛规模与选择强度之间的关系： 表2 - 3 ：竞赛规模与选择强度之间的关系 选择强度为： s e l v a r r o 。( 2 ) = l i 1 多样化损失为； !丝 l o s s d i v r o 。( t o u r ) = t o u r 胁一一t o u r t o u r - i ( 2 6 ) 当t o u r = 5 时多样化损失大约为5 0 * , o 选择方差为： s e l v a r r o 。( 乃甜，) = l o 0 9 6 l o g ( 1 + 7 1 l ( t o u r - 1 ) ) ( 2 7 ) & ，( 2 ) = l i 1 ( 2 8 ) e 述几种选择方法均以适应度为基础进行选择，这就可能在进化过程中导致以 9 浙江工业大学硕士学位论文 下的问题： 其一：在种群中出现个别或者极少数适应度相当高的个体时，采用这样的选择 机制就有可能导致这些个体在种群中迅速繁殖。经过少数几次迭代后占满了种群的 位置。这样，遗传算法的求解过程就结束了，也即收敛了。但这样很有可能是收敛 到局部最优解，即遗传算法的不成熟收敛，即早熟现象的出现，这是因为搜索的范 围很有限。因此一般不希望有个别个体在遗传算法运算的最初几次迭代时就在种群 中占据主导地位。 其二，当种群中个体适应度彼此非常接近时，这些个体进入配对集的机会相当， 而且交配后得到的新个体也不会有多大变化。这样，搜索过程就不能有效地进行， 选择机制有可能趋向于纯粹的随机选择，从而使进化陷于停顿的状态，难以找到全 局最优解。 上述问题，一般可以采用适应度函数尺度变换的方法来解决。另外，可以采用 以下几种提高遗传算法性能的选择方法。 1 稳态繁殖( s t e a d ys t a t er e p r o d u c t i o n ) 在迭代过程中用部分优质新子个体来 更新种群中部分父个体作为下一代种群。 2 没有重串的稳态繁殖( s t e a d y s t a t er e p r o d u c t i o nw i t h o u td u p l i c a t e s ) 在形成新 一代种群时，使其中的种群均不重复。做法是：在将某个个体加入到新的一代种群 之前，先检查该个体与种群中现有的个体是否重复，如果重复就舍弃。这种做法会 明显改善遗传算法的行为，因为其增大了个体在种群中的分布区域，但增加了计算 时间。 不同选择方法的行为是有差别的，基本遗传算法达到收敛的世代数与选择强度 成反比，较高的选择强度是很好的选择方法，但是太高会导致收敛过快，解的质量 很差。最小限度的种群大小往往依赖于目标函数的维数和选择强度，而选择强度又 与选择参数( 如选择压力、截断阀值、竞赛规模) 有关。锦标赛选择法只能赋离散 值，线性排序选择法只允许较小区间值的选择强度。截断选择会导致比排序选择和 锦标赛选择更高的多样化损失，截断选择倾向于用更好的个体取代较差的个体，因 为所有低于适应度阀值之下的个体没有机会被选择，排序选择与锦标赛选择比较相 似，但是在锦标赛选择法因其离散性不能发挥作用的场合下，我们往往使用排序选 择法。 2 4 3 交叉 交叉( c r o s s o v e r ) 过程又称基因重组( r e c o m b i n a t i o n ) 过程，其本质是将两个 父个体的部分结构加以替换重组而生成新的个体，就像人类社会的婚姻过程，通过 重组交叉操作，遗传算法的搜索能力得以飞跃地提高。基因重组和交叉是遗传算法 获取新优良个体最重要的手段。 交叉主要分为二进制重组和实值重组。但是从本质来看，实值重组是二进制重 o 浙江工业大学硕士学位论文 组的特殊形式。图2 - 2 是单点交叉的示意图。 c l 二 l i 二 c 2 图2 - 2 ：单点交叉重组示意图 对于实值重组而言，在计算机中仍然是对遗传二进制数值进行操作，只是其重 组交叉时是整个字节地进行。如i n t 型整数，一个实整数分配字节为4 字节，则对 此实数进行交叉时就是整4 个字节的交叉。 在交叉方式上，有单点交叉亦有多点交叉，又有均匀交叉，而在t s p 巡回旅行 商问题( t r a v e l i n gs a l e s m a np r o b l e m ) 中还涉及到部分匹配交叉、顺序交叉、循环 交叉、洗牌交叉、缩小代理交叉等等，随具体问题而改变。 2 4 4 变异 重组之后进行子代的变异( m u t a t i o n ) 操作。子个体变量以很小的概率或者步 长产生转变，变量转变的概率或者步长与维数( 即变量的个数) 成反比，而与种群 的大小无关。有研究资料显示，对于单峰函数l l n 是最好的选择，开始时增加变异 率，结束时减少变异率可以改善搜索速度。但是对于多峰函数变异率的自适应过程 则更有意义。变异本身是一种局部随机搜索，与选择交叉算子结合在一起，保证了 遗传算法的有效性，使得遗传算法具有局部的随机搜索能力；同时使得遗传算法保 持种群的多样性，以防止出现非成熟收敛。在变异操作中，变异率不能取的太大， 若变异率大于o 5 ，则遗传算法会退化为随机搜索，那么遗传算法的一些重要的数学 特性和搜索能力也不复存在了。有些问题，专门针对变异率设计变化的方式，如满 足某种分布等，将这些程序加入到遗传算法的主程序中就构成了自适应遗传算法。 2 4 5 适应度函数 遗传算法在进化搜索中基本不利用外部信息，仅以适应度函数( f i t n e s s f u n c t i o n ) 为依据，利用种群中每个个体的适应度值来进行搜索。因此适应度函数的选取至关 重要，直接影响到遗传算法的收敛速度以及能否找到最优解。一般而言，适应度函 数是由目标函数变换而成的。对目标函数值域的某种映射变换称为适应度尺度变换 c f i t n e s ss c a l i n g ) 。 浙江工业大学硕士学位论文 = ：，= = = _ ：一 适应度函数基本有以下三种： 一 1 接以待求解的目标函数的转化为适应度函数，即： 若目标函数为最大化问题只f ( 厂o ) ) = ，( x ) 若目标函数为最小闯题f 舒( 厂( x ) ) = 一，( z ) 这种适应度函数简单直观，但存在两个问题，其一是可能不满足常用的轮盘赌 选择中概率非负的要求；其二是某些代求解的函数在函数值分布上相差很大，由此 得到的平均适应度可能不利于体现种群的平均性能，影响算法的性能。 2 若目标函数为最小问题，则 砌) ) 竺 其中c m 。为，0 ) 的最大值估计。 若目标函数为最大问题，则 鼢驴= 卜。嚣 ( 2 9 ) ( 2 1 0 ) 其中c 二为g ) 的最小值估计。 这种方法称为“界限构造法”，但有时存在界限值预先估计困难、不可能精确的 问题，由此有以下方法作为改进。 3 目标函数为最小问题： 励( ( 刁) 2 而1 c o ，f + 巾) 。 目标函数为最大问题： ，f f ( 巾) ) 2 而1 c 。，c 一饰) 。 ( 2 1 1 ) ( 2 1 2 ) 此方法与第二种方法类似，c 为目标函数界限的保守估计值。 在遗传操作时往往会出现以下问题： 1 在遗传进化的初期，通常会产生一些超常的个体，若按照比例选择法，这些 异常个体因为竞争力太强而控制了选择过程，影响算法的全局优化性能。 1 2 浙江工业大学硕士学位论文 2 在遗传进化的后期，即算法接近收敛时，由于种群中个体适应度差异较小时， 继续优化的潜能降低，可能获得某个局部最优解。 上述问题，我们通常称为遗传算法的欺骗问题。而适应度函数设计不当就有可 能造成这种问题的出现。所以，一般而论，适应度函数在设计时主要要满足以下的 条件： 单值、连续、非负、最大化 合理、一致性，要求适应度值反映对应解的优劣程度，这个条件的达成往 往比较难以衡量。 计算量小，适应度函数设计应尽可能简单，这样可以减少计算时自j 和空间上 的复杂性，降低计算