（应用数学专业论文）遗传算法的模式理论及收敛理论.pdf

摘要 遗传算法的已有研究主要集中于设计新的算法，或改进已有算法及应用 已有算法去解决实际问题而相关基础理论的研究相对滞后，研究成果也相 对较少，其中模式理论和算法的收敛理论是两个核心的理论问题本文主要 针对这两个核心的理论问题进行了研究，主要创新成果如下 1 深入研究了单点杂交的模式理论对于单点杂交算子，目前的模式理论主 要研究它对模式存活的影响只有极少数文献研究了它对模式的新建( 指 在杂交算子作用下模式从无到有) 的影响，但这些研究结果还存在一些严 重缺陷，如不能区分开它对模式的存活和新建的各自影响为了能分别研 究杂交算子对模式存活和新建的影响本文提出一种三进制表示法，利用 这种表示法能完全区分模式的存活情况和新建情况，从而既可以分别研究 杂交算子对模式的存活和新建能力的影响又可研究在存活和新建共同作 用下单点杂交对模式的影响这是已有研究所没有的 2 研究了均匀杂交的模式理论目前广泛使用的杂交算子有很多种，其中均 匀杂交算子是最常使用的杂交方式之一基于三进制表示法，深入研究了 均匀杂交对模式的存活能力和新建能力的影响，然后研究了在存活和新建 共同作用下均匀杂交对模式的影响并且，比较了单点杂交和均匀杂交对 模式的存活和新建的影响 3 将前述的研究结果推广到任意杂交算子中去，研究了任意杂交算子的模式 理论 4 建立了一类遗传算法的模型，该类算法包含常用的经典遗传算法在内的许 多算法，利用m a r k o v 链模型，证明了该类算法的全局收敛性，并估计了该 类遗传算法的收敛速度讨论收敛速度的方法与已有的方法不同，而且较 于其他收敛速度的结果，本文的结果具有更强的实用性 5 研究了一类不使用精英保留策略的遗传算法的收敛速度利用m a r k o v 链 一个特殊的m i n o r i z a t i o n 条件，讨论了该类遗传算法的收敛速度它推广了 已有的结论 关键词：遗传算法模式理论全局收敛性收敛速度m a r k o v 链 i i j a b s t r a c t i nt h ep a s t ，t h er e s e a r c ho ng e n e t i ca l g o r i t h m sh a sm a i n l yb e e nf o c u s e do nd e s i g n i n g n e wa l g o r i t h m s ，i m p r o v i n ge x i s t i n ga l g o r i t h m sa n da p p l y i n gt h ee x i s t i n ga l g o r i t h m st o r e a lw o r l dp r o b l e m s h o w e v e r ，t h et h e o r e t i c a lr e s u l t so i ls c h e m at h e o r ya n dc o n v e r g e n c e t h e o r y , t w oi m p o r t a n tt h e o r e t i c a li s s u e so ng e n e t i ca l g o r i t h m s ，a r er e l a t i v e l yf e w i nt h i s d i s s e r t a t i o n ，t h e s et w oi m p o r t a n tp r o b l e m sw e r es t u d i e d t h em a i nc o n t r i b u t i o n si nt h i s d i s s e r t a t i o na r ea sf o l l o w s ： 1 t h es c h e m at h e o r yf o ro n e - p o i n tc r o s s o v e ri sp r o p o s e d f o ro n e - p o i n tc r o s s o v e r o n l y t h es u r v i v a la c t i o nt os c h e m ai sm a i n l yd i s c u s s e di nt h ee x i s t i n gs c h e m at h e o r y t h e r e a r ef e ww o r k st a c k l i n gt h ec o n s t r u c t i o na c t i o nt os c h e m a f u r t h e r m o r e ，t h e r ee x i s t s o m el i m i t a t i o n si nt h e s er e s e a r c hr e s u l t so ns c h e m ac o n s t r u c t i o nt h e o r y f o re x a m p l e ， t h ee f f e c t so ft h es c h e m as u r v i v a la n dt h es c h e m ac o n s t r u c t i o nb yc r o s s o v e rc a l ln o t b ed i s t i n g u i s h e d i no r d e rt oa n a l y z et h ee f f e c t s o ft h es u r v i v a la n dc o n s t r u c t i o n o fc r o s s o v e r ，r e s p e c t i v e l y , at e r n a r yr e p r e s e n t a t i o nf o rs c h e m ai sp r o p o s e di nt h i s d i s s e r t a t i o n ，t h r o u g hw h i c ht h ee f f e c t so ft h es u r v i v a la n dc o n s t r u c t i o no fas c h e m a c a nb ee a s i l yd i s t i n g u i s h e d a sar e s u l t ，n o to n l yt h ee f f e c t so ft h es c h e m as u r v i v a l a n dt h es c h e m ac o n s t r u c t i o nb yc r o s s o v e rc a nb ea n a l y z e ds e p a r a t e l y , b u ta l s ot h e e f f e c to ft h e ku n i t e da c t i o nc a nb ea n a l y z e d 2 t h es c h e m at h e o r yf o ru n i f o r mc r o s s o v e ri sp r e s e n t e d u n i f o r mc r o s s o v e ri so n eo f t h em o s tp o p u l a rc r o s s o v e r s i nt h i sd i s s e r t a t i o n ，t h ee f f e c t so ft h es c h e m as u r v i v a l a n dt h es c h e m ac o n s t r u c t i o no fu n i f o r mc r o s s o v e ra r ea n a l y z e db a s e do nt e r n a r y r e p r e s e n t a t i o n s u b s e q u e n t l y , t h eu n i t e da c t i o no fs c h e m as u r v i v a la n dc o n s t r u c t i o n o fu n i f o r mc r o s s o v e ri sd i s c u s s e dt o o m o r e o v e r ，t h er e s u l t so ft h es c h e m as u r v i v a la n d s c h e m ac o n s t r u c t i o nb e t w e e no n e - p o i n tc r o s s o v e ra n du n i f o r mc r o s s o v e ra r ec o m p a r e d ， r e s p e c t i v e l y 3 t h ea f o r e m e n t i o n e dr e s e a r c hr e s u l t so no n e - p o i n tc r o s s o v e ra n du n i f o r mc r o s s o v e r a r eg e n e r a l i z e dt oa n yc r o s s o v e ro p e r a t o r ，a n dt h ec o r r e s p o n d i n gs c h e m at h e o r yf o r a r b i t r a r yc r o s s o v e ri sp r e s e n t e d 4 am o d e lf o rac l a s so fg e n e t i ca l g o r i t h m si sp r o p o s e d t h i sm o d e li n c l u d e sm a n y v g e n e t i ca l g o r i t h m sb e s i d e st h ec a n o n i c a lg e n e t i ca l g o r i t h m s b yu s i n gm a r k o vc h a i n m o d e l ，t h eg l o b a lc o n v e r g e n c eo ft h i sc l a s so fg e n e t i ca l g o r i t h m si sp r o v e d m o r e o v e r ， t h ec o n v e r g e n c er a t eo ft h i sc l a s so fg e n e t i ca l g o r i t h m si se s t i m a t e d ，a n dt h ee s t i m a t i o n m e t h o di sm o r ea p p l i c a b l ea n dd i f f e r e n tf r o mt h ee x i s t i n gm e t h o d s 5 t h ec o n v e r g e n c er a t eo fa n o t h e rc l a s so fg e n e t i ca l g o r i t h m sw i t h o u tt h ee l i t i s ts c h e m e i sd i s c u s s e d o n es p e c i a lm i n o r i z a t i o nc o n d i t i o no fm a r k o vc h a i ni su s e dt oe s t i m a t e i t sc o n v e r g e n c er a t e ，w h i c he x t e n d st h ee x i s t i n gr e s u l t s k e y w o r d s ：g e n e t i ca l g o r i t h ms c h e m at h e o r y g l o b a lc o n v e r g e n c e c o n v e r g e n c e r a t em a r k o vc h a i n 符号说明 k 阶模式 模式日所在串的长度 模式风的阶 模式风的定义距 均匀杂交交换字符的概率 在基因位l 两字符相同的概率 模式风存活下来的概率 模式峨被新建的概率 模式趣既存活下来又被新建的概率 经过存活和新建后子代中属于模式风的个体数目的期望值 杂交的概率 变异的概率 杂交事件 基于兰进制表示法的可行情况j 基于二进制表示法的可行情况j 父母对l 概率空间 状态t 转移到状态j 的概率 状态转移矩阵 概率测度”。和概率测度地的全变差距离 凰如蜊删删一一乳鼽以町毋鼠一p一 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的 研究成果尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论 文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子 科技大学或其它教育机构的学位或证书而使用过的材料与我一同工作的同 志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意 申请学位论文与资料若有不实之处，本人承担一切相关责任 本人签名t 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即t 学 校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的 全部或部分内容，可以允许采用影印、缩印或其他复制手段保存论文( 保密的 论文在解密后遵守此规定) 本人签名。趁 7 导师签名。垒篁垒 第一章绪论 本章首先介绍了遗传算法及其相关理论产生的背景，然后介绍了遗传算 法的现状与研究发展最后，介绍了本文的主要内容及结构安排 1 1 引言 目前遗传算法的已有研究大都集中于算法的设计和应用，而相关的基础 理论研究远落后于对算法的设计和应用研究本文着重研究遗传算法理论方 面的两个关键问题，遗传算法的模式理论和遗传算法的收敛理论 h o l l a n d 在1 9 7 5 年提出了遗传算法，模式理论及与其相关的隐并行性原理 是其最初的主要理论基础人们试图用模式理论来阐述遗传算法的搜索机理， 但结果不尽人意，还存在一些问题正是模式理论的不足，迫使人们思考并完 善这种理论最初的模式理论只是讨论了单点杂交算子对模式的影响，并且 只考虑了杂交算子的破坏作用杂交算子可以破坏一个模式，也可以不破坏 这个模式，即就是使这个模式存活下来，这种不破坏一个模式的作用我们称 为杂交算子的存活作用而事实上，杂交算子不仅仅对模式有破坏作用，并且 有存活作用，除此之外还能建设一个新的模式，我们称其为杂交算子的新建 作用最初的模式理论只考虑了单点杂交算子的存活作用，而没有考虑其新 建作用杂交算子能使模式存活和建立新模式的情形有很多，我们分别称为 存活情形和新建情形本文提出一种三进制表示法，利用这种表示法能完全 区分模式的存活情形和新建情形，从而可以分析杂交算子的存活和新建能力 本文研究了单点杂交、均匀杂交的存活和新建能力，并研究了在存活和新建 共同作用下任意杂交算子的模式理论 遗传算法的收敛性分析和收敛速度的研究是遗传算法的另一个核心理论 问题其中收敛速度是衡量遗传算法性能的重要指标，众所周知，即使具有 收敛性的遗传算法，在用于实际问题时是否有效，取决于其收敛的快慢程度， 即收敛速度对于一个收敛很慢的遗传算法，若在解决问题时花费的时间代 价是人们难以忍受的，则这种算法可以认为是无效的由此可见，遗传算法收 敛速度的研究是算法理论与应用的必然要求这方面的研究不仅可从另一个 侧面阐明遗传算法的收敛性，并且对于建立合适的停机准则及恰当的度量标 准，以全面、客观地评价算法的各种执行策略有重要意义然而目前关于收敛 2 西安电子科技大学博士学位论文：遗传算法的模式理论及收敛理论 速度的研究结果还不够系统和深入，并且结果还不够实用本文首先提出一 类采用精英保留策略的遗传算法模型，它包含很多常见的遗传算法分析了 该类算法的全局收敛性，然后利用m a r k o v 链的性质估计了这类算法的收敛速 度，结果中不含有需要进一步估计的参数，具有较好的实用性本文还利用一 个m a r k o v 链的m i n o r i z a t i o n 条件研究一类不使用精英保留策略的遗传算法的 收敛速度，推广了已有的结论。 1 2 遗传算法产生的背景 1 8 5 9 年达尔文在其物种起源一书中根据大量考察资料详细阐述了一种 生物进化的理论这种理论认为：生物不是从来就有的，物种是进化的，地球 生物界是一个历史有序的统一体，生物产生与生物进化是一种由无序到有序， 由低级的单细胞生物到高级有序的人类社会进化的过程生物进化的结果导 致生物种类的繁多，功能和结构的复杂，这是一个有序增加的过程【” 人类的产生，正是自然界中生物演化过程一由低级向高级，由简单到复 杂，由无生命体向有生命体进化的产物人类自身也是在不断进化着，人自直 立时起，人类的各组成部分随着适应环境的需要在趋于合理，人类大脑的智 力活动也逐渐从低级向高级发展人类在与自然界作斗争的过程与求生存的 生产劳动过程中，不断地积累了知识、经验和技能，逐渐提高自身适应自然环 境的能力然而，作为个体的人，有的是“劣质”的，如，体弱、多病，先天不 足等因素而使其。天折”，这正体现了达尔文的。适者生存”，。优胜劣汰”的 进化理论 研究生物进化及生物表现出的性状导致遗传学的诞生，遗传学是研究控制 生物遗传的基本单位一基因( g e n e ) n 的二十世纪初，人们重新发现了孟德尔 十九世纪七十年代的生物遗传学理论自然界中的各种生物呈现出多种多样 的性状，可以用孟德尔遗传理论得到解释如今，孟德尔的遗传变异理论已被 扩充经典的遗传学仅仅研究不连续性状的遗传，在最简单的情况下，生物的 性状是由单基因决定的，且不受环境变化的影响但是，生物学上具有重要意 义的许多性状，表现为连续变异，可能受大量微效基因以及不同环境因子的 影响特别的，二十世纪七十年代早期发现的基因在个体染色体之间的跳跃 或迁移现象，使得基因表达形式发生变化，这在生物物种起源与进化过程中发 挥重要作用，这是人们已达成的共识此外，现代遗传学已经注意到( 人工选 第一章绪论3 择，自然选择) 的作用，无论是人工选择还是自然选择，它对生物进化产生的 影响是重大的，只是有关选择效应相当复杂，人们对其还没有很深入的了解 生物学上的这些研究成果为有思维，有智能与创造力的人类向自然学习，模拟 生物功能与进化过程等提供了有力的背景支持人类从模拟飞禽的飞翔天空， 昆虫复眼的纵观太空，到模拟人类自身的大脑的“电脑”人类的这种学习模 拟能力的范围逐渐延伸开来，模拟从低级向高级、从简单到复杂，由无智能向 有智能过程不断地发展是必然的趋势在现实世界里，有着大量的实际问题， 如组合优化中的n p c o m p l e t e 问题，人工神经网络的训练问题，模糊系统的知 识与规则的学习问题，海量数据的处理问题等等，已有的工具难以得到令人满 意的解答，于是，借助于模拟生物进化的“适者生存”，“优胜劣汰”过程及孟 德尔的遗传理论，通过对生物进化中的繁殖、变异、竞争和选择这四种基本形 式进行模拟，使人们得到解决问题的一类新方法一进化算法，进化算法最初有 三大分支，遗传算法( g e n e t i ca l g o r i t h m ，g a ，由j h h o l l a n d 于1 9 7 5 年提出【3 】) ， 进化规划( e v o l u t i o n a r yp r o g r a m m i n g ，e p ，由l j f o g e l 等于1 9 6 6 年提出州) 和进 化策略( e v o l u t i o n a r ys t r a t e g y , e s ，由i r e c h e n b e r g 于1 9 7 3 年提出【5 】) 9 0 年代初， 在遗传算法的基础上又形成了一个分支：遗传程序设计( g e n e t i cp r o g r a m m i n g ， g p , 由j k o z a 于1 9 9 0 年提出【6 】) 虽然这几个分支在算法实现方面有一些差 别，但是这些差别正在逐渐缩小，它们的一个共同点是借助生物进化的思想 和原理来解决实际问题在进化算法中使用最普遍又最具有代表性的便是遗 传算法溉7 - 1 2 1 遗传算法自二十世纪七十年代产生以来越来越受到人们的关注，这是由于 遗传算法在解决人工智能领域、组合优化、工程设计控制与计算大规模数据 处理等方面一系列复杂难问题时具有独特功效【9 _ 蚓作为一种随机搜索算 法，它较其他算法有其自身显著特色，其中算法演化的并行性、对全局优化问 题的有效性与实用性，以及对问题求解的稳健性是其他算法无法比拟的当 然，遗传算法产生的意义不仅仅表现在它能有效的解决实际问题，更重要的 是，如 1 0 】前言中所展望的，它将可能指导人类自身的诸多智力活动的演化 1 3 遗传算法的发展与现状 由于遗传算法固有的本质并行性，自组织适应性以及优胜劣汰的自然选 择和简单的进化操作，使得遗传算法具有不受搜索空间限制性条件的约束且 4 西安电子科技大学博士学位论文：遗传算法的模式理论及收敛理论 不需要其他的辅助信息( 如相关函数可微，单峰，多峰) 的特点，如今，遗传 算法已成为一个引人注目的研究方向 根据德国d o r t m u n d 大学提供的一份研究报告【”】，进化剪法( 遗传竹法足 进化算法中产生最早、影响最大、应用也比较广泛的一个研究方向) ，它已经 在1 6 个大领域2 5 0 个小领域中获得了应用【1 。目前有数种以进化竹法为主题 的国际会议在世界各地定期召开现在已有一些专门刊登进化算法的国际专 业杂志，如：“e v o l u t i o n a r yc o m p u t a t i o n ”( 由m i tp r e s s 出版，1 9 9 3 创刊，d e j o n g 主编) 和“i e e et r a n s a c t i o n so i le wj l u t i o n a l yc o m p u t a l ，| i o n ”( i e e e 汇刊，1 9 9 7 年创 刊，d a v i db f o g e l 主编) 一些国际性期刊也竞相出版以遗传算法为主题的专刊 1 6 - 1 9 。某些学者研 究了遗传算法的灵现行为( e m e r g e n tb e h a v i o r ) 后声称，遗传算法将与混沌理论 和分形几何一道成为人们研究非线性现象和复杂巨系统的新的三大方法，并 且将和神经网络一道成为人们认知过程的重要工具 2 0 - 2 2 i 目前，遗传算法的研究主要集中在以下方面： 一、遗传算法的基础理论研究 设计新颖、有效，实用的算法执行策略并非易事通常，由于受到主客观 条件的限制，人们对自己所需解决的实际问题了解得不够或不可能全面掌握 问题的有效信息，这使得其相应的算法设计难免会出现不可预知的结果更 为突出的问题是，目前，人们对遗传算法的搜索机制( 如，遗传算子的搜索能 力，遗传算子间的协作能力) 以及算法的性能评价分析( 如算法的收敛性和 收敛速度，算法的复杂性，算法间优劣等) 知之不多对这一系列理论问题的 研究，不仅仅是遗传算法理论自身完善的需要，更重要的是人们借助于这些 理论问题研究的深入，将这些研究结果用来更有效地指导算法设计及其应用 因此，遗传算法的理论研究是人们关注的十分重要的研究方向之一显然，遗 传算法的理论研究涉及广泛，从待解决问题可行解的编码格式、遗传操作中 的参数设置，遗传算子的搜索机制与选择方式的选取，到遗传算法的收敛性 与收敛速度分析，复杂性分析，算法性能优劣的评价以及算法生成的方式方 法等等，都是理论工作者与应用工作者十分关注的基本问题 然而，模式理论和收敛理论是其中两个热点和关键问题对于模式理论， 由于其自身的不系统性和不完整性，导致人们目前对其后续研究的方向产生 了两种观点： 第一章绪论 5 ( i ) 完善已有的模式理论，将s c h e m a 理论从不同角度和层面进行推广和补充， 使得模式理论分析更合理化和系统化； ( i i ) 扬弃已有的模式理论，在生物遗传学的背景里寻找模拟生物进化的其它途 径，建立新的理论 对于收敛性理论，作为遗传算法的另一个核心理论问题它包含收敛性与 收敛速度的研究收敛性问题曾困扰了人们很长时间，直到最近才有一些令人 欣慰的研究成果出现 ”- 5 4 1 如【2 3 】利用m a r k o v 链的遍历性给出收敛结果；【2 4 】 利用f e r i d l i n - w e n t z e l l 理论给出遗传算法的渐进强收敛性结果； 2 5 ，2 6 】利用不 动点理论给出简单遗传算法的收敛性结果，等等尽管遗传算法收敛性的研 究已取得了较大进展，但是其理论的系统性和通用性还远远不够仍有很多 问题需要进一步研究，如对基于个体水平与基因水平上的算法模型的收敛性 分析，非e l i s t i s t 选择型算法的收敛性分析及非二进制编码算法的收敛性研究 等等 与遗传算法收敛性的研究相比，遗传算法收敛速度的研究相对滞后研究 成果是非常有限的，4 3 , 5 4 , 删，【2 7 综述了遗传算法收敛性及收敛速度估计的 近期研究结果，并指出遗传算法理论研究存在的亟待解决的问题【4 3 】研究了 具有e l i b i t 选择的遗传算法的收敛速度估计问题【5 4 】将遗传算法分为时齐和 非时齐遗传算法，并利用m i n o r i z a t i o n 条件讨论了这两类算法的收敛速度【5 5 】 利用特殊的m i n o r i z a t i o n 条件研究了经典遗传算法的收敛速度因此，需要人 们花费更多的时间精力去深入研究 二、遗传算法的设计与执行策略 自从1 9 7 5 年j h h o l l a n d 系统的提出遗传算法的完整结构和理论以来，众 多学者一直致力于推动遗传算法的发展，对编码方式，控制参数的确定、选 择、交叉以及变异算子的改进进行了深入的研究和探讨，引入了动态策略和 自适应策略来改进遗传算法的性能，并针对遗传算法收敛速度慢等特点，有 的结合传统的优化方式，使得整个算法的性能得到很大的提高，改进策略大 致可以概括为以下几个方面， ( 1 ) 改进遗传算法的组成成分或使用技术，如选用优化控制参数、适合问 题特性的编码技术等； ( 2 ) 采用混合遗传算法； ( 3 ) 采用动态自适应技术，在进化过程中调整控制参数； 6 西安电子科技大学博士学位论文：遗传算法的模式理论及收敛理论 ( 4 ) 采用非标准的遗传操作算子； ( 5 ) 采用并行遗传算法 一些典型的改进方法有。g l o v e r 等刚提出了遗传算法与禁忌搜索( t a b u s e a r c h ) 相结合的策略；p o t h s 等【5 8 1 为克服遗传算法的早熟现象，提出了基于迁 移和人工选择的遗传算法；为提高遗传算法的搜索性能，k a z a r l i s 等【5 9 】把微遗 传算法( m i c r o - g e n e t i ca l g o r i t h m s ，种群规模小且进化代数少的遗传算法) 作为 标准遗传算法的广义爬山算子，构成了混合遗传策略；张讲社等提出了遗 传算法与模拟退火算法( s i m u l a t e da n n e a l i n g ) 的混合策略，以克服遗传算法早 熟的缺点此外，还有遗传算法与模糊集( f u z z ys e t ) 结合的混合算法1 8 1 - “ ，遗 传算法与混沌( c h a o s ) 相结合的策略p 删，遗传算法与爬山法、梯度法等局部 搜索算法的结合【7 ，弘删，遗传算法与单纯形法相结合【7 4 ，碉，神经网络与遗传 算法相融合的策略p 】，遗传算法与正交设计的结合m - ，s 2 1 以及在遗传算法中 加入免疫算子，构成免疫进化算法( i m m u n ee v o l u t i o n a r ya l g o r i t h m s ) s a - s s 等等 遗传算法的设计与执行策略包含编码方法、选择机制、杂交与变异机制， 执行策略的设计与改进目前发展了各种各样的执行策略，例如，溶入退火机 制、结合已知的局部寻优技巧、并行演化机制，协作演化及编码形式等一些 典型的执行策略，如退火遗传算法- ，5 哪，f o r k i n g 遗传算法【8 6 】、自适应遗传算 法【1 1 ，”、抽样型遗传算法【5 5 1 ，协作型遗传算法 8 8 】、混合遗传算法口o 删，实编 码遗传算法 9 1 1 、动态参数编码遗传算法1 9 2 】及矿一编码遗传算法【9 3 1 ，等等虽 然已有多种不同的算法形式，但这对人们将要面临的各类现实问题而言，已 有的这些算法形式是远远不够的因此，研究采用合理有效的策略或模拟生 物进化的新理论来设计或生成新颖有效的算法形式，是遗传算法研究的重要 方向之一 三、遗传算法在神经网络、模糊系统和机器学习等方面中的应用 无论是算法设计还是理论分析，最终目的归结到应用任何形式的算法 设计是否合理有效，评价衡量的最终标准只能是对解决问题所表现出的实际 效果遗传算法已被人们广泛地应用于组合优化、机器学习、信号处理、自 适应控制和人工生命等领域陋1 0 1 】例如，由计算机根据教师的意愿，利用遗 传算法自动进行排课，最大限度地满足教师的愿望，对资源作出优化合理的 安排， 9 4 ，9 5 】将遗传算法应用于教师排课问题遗传算法的商业应用五花八 门，覆盖面甚广，比如通用电器公司的计算机辅助设计系统e n g e n e o u s ，这是一 第一章绪论 7 个采用了遗传算法以及其他传统的优化技术作为寻优手段的混合系统( h y b r i d s y s t e m ) e n g e n e o u s 已成功的应用于汽轮机设计，并改善了新的波音7 7 7 发动 机的性能，这是目前正在研究和应用的一个重要方面遗传算法已经广泛应 用于前向神经网络、径向神经网络、k o h o n e n 特征映射及r e c u r r e n t 网络等各 种人工神经网络的训练与设计中【9 6 】将遗传算法与人工神经网络结合建立了 震灾风险预测的遗传神经网络模型，【9 7 】讨论了遗传神经网络法及其在机器人 误差补偿中的应用遗传算法也成功地用于模糊系统的隶属函数形式、参数 优化以及推理规则的选取【9 8 】提出了一种基于模糊聚类和遗传算法的模糊分 类系统的设计方法，利用遗传算法对约简后的模糊分类系统进行优化，提高其 精确性【9 9 为了提高足球机器人的射门成功率，给出了一种基于遗传模糊算 法的足球机器人射门实现方法遗传算法在机器学习系统上的应用也十分活 跃【1 0 0 】讨论了遗传算法在一般车辆优化调度中的应用，1 1 0 1 】将基因遗传算法 应用于产品人机形态设计，实现了产品人机形态设计的优化随着对遗传算 法研究的深入，遗传算法的应用涉及从工程技术到社会管理等诸多领域，可 以预计其应用前景一定会更为广阔 1 4 本文的主要工作与内容安排 本文深入探讨了遗传算法的模式理论以及遗传算法的收敛速度，本文的 主要内容安排如下t 第一章为绪论部分，简要介绍了遗传算法产生的背景，发展和现状，以及 本文的主要内容安排 第二章作为预备知识，介绍了遗传算法的基本概念、遗传算法的主要特点 和遗传算法的基本框架，以及遗传算法现有的的基本理论研究 第三章深入研究了单点杂交的模式理论最初的的模式理论只是讨论了 单点杂交算子对模式的影响，并且只考虑了杂交算子对模式理论的影响但 事实上，杂交算子不仅仅对模式的存活有影响，而且还能建设一个新的模式， 我们称为杂交算子的新建作用本文提出一种三进制表示法，利用这种表示 法能完全区分模式的存活情形和新建情形，从而可以分别研究杂交算子对模 式的存活和新建能力的影响本文不仅分别单独研究了单点杂交的存活能力， 和单点杂交的新建能力，还研究了在存活和新建共同作用下单点杂交对模式 的影响 8 西安电子科技大学博士学位论文：遗传算法的模式理论及收敛理论 第四章研究了均匀杂交的模式理论目前在广泛使用的多种杂交算子中， 均匀杂交算子是最重要的的杂交方式之一利用三进制表示法，本文分别研究 了均匀杂交的存活能力和新建能力，然后研究了在存活和新建共同作用下均 匀杂交对模式的影响并且，比较了单点杂交、p o = 0 2 的均匀杂交和p o = 0 5 的 均匀杂交三个杂交算子的存活和新建能力，结果表明，在存活能力上，p o = 0 5 的均匀杂交算子让模式存活的能力最小，相应地，它对模式的破坏作用最大， 其次是单点杂交，而p o = 0 2 的破坏作用最小而在新建能力上，p o = 0 5 的均 匀杂交算子新建一个模式的能力最强，其次是单点杂交，最后是p o = 0 2 的均 匀杂交算子，它的新建作用最小研究者在选择杂交方式的时候可以采用自 适应的杂交算子，即在进化过程中根据种群中个体多样性的变化来选择破坏 性大或新建能力大的杂交算子 第五章研究任意杂交算子的模式理论在讨论了单点杂交的模式理论和 均匀杂交的模式理论后，将这些结果推广到了任意杂交算子中去，得到了一 些规律性的结果 第六章首先提出了一类具有全局收敛能力的遗传算法，该类算法包含除 常用的经典遗传算法之外的许多算法然后利用m a r k o v 链模型，讨论了该类 算法的全局收敛性，最后估计了该类遗传算法的收敛速度较于其他收敛速 度的结果，本文的结果具有较强的实用性收敛速度的研究是一项重要而困 难的课题 第七章研究了一类不使用精英保留策略的遗传算法的收敛速度其思想 是利用m a r k o v 链一个特殊的m i n o r i z a t i o n 条件，讨论了任该类遗传算法的收敛 速度推广了已有的结论 最后在结束语部分中，对本文的工作进行总结，并指出工作中的不足和下 一步研究的方向 第二章遗传算法的基本理论 随着经济，科技和社会的不断发展，人们遇到的各种问题越来越复杂，迫 切需要寻找一种更好的求解方法遗传算法作为一种有效的全局搜索方法，是 二十世纪六十年代末期开始形成的一种较为完整媳理论和方法它是一种基 于自然选择和遗传变异等生物进化机制而发展起来的仿生算法它不受搜索 空间限制性的约束，也不需要其他的辅助信息( 如梯度信息) ，因此，遗传算 法是一种简单、随机、自适应的搜索算法，能够解决传统方法感到困难的许多 复杂优化问题 遗传算法从产生至今不断地扩展其应用领域，比如工程设计、制造业、人 工智能、计算机科学、生物工程、自动控制，社会科学商业和金融等领域，同 时应用实践又促进了遗传算法的发展和完善目前，遗传算法作为高性能优 化方法逐渐成熟起来但是，遗传算法也存在很多问题，如理论不完善，存在 早成熟收敛，收敛速度慢等缺点 2 1 遗传算法的主要特点 遗传算法是一种基于自然选择和遗传变异等生物机制的全局性概率搜索 算法与基于导数的解析方法和其他启发搜索方法一样，遗传算法在形式上 也是一种迭代方法它使用种群搜索技术，通过对当前的种群采用类似于自 然选择和有性繁殖的方式，在继承原有优良基因的基础上，生成具有更好性 能指标的下一代解的群体它不是简单的随机化搜索方法，而是通过对染色 体的评价和对染色体中基因的作用，利用已有的信息来指导搜索，逐渐使得 种群进化到包含或接近最优解的状态遗传算法的主要本质特征在于群体搜 索策略和简单的进化算子群体搜索使遗传算法得以突破邻域搜索的限制，可 以实现整个解空间上的分布式信息搜索、采集和继承，从而保证了解的全局 性；进化算子仅仅利用适应值度量作为运算指标进行染色体的随机操作，降 低了一般启发式算法在搜索过程中对人机交互的依赖这样就使得遗传算法 获得强大的全局最优解搜索能力问题域独立性，信息处理的隐并行性，应用 的鲁棒性，操作的简明性，使得遗传算法成为一种具有良好普适性和可规模 化的优化方法但遗传算法也有其自身的缺点，比如容易产生早熟收敛以及 收敛速度慢等遗传算法是一种仿生优化算法，它与传统的优化算法有许多 9 1 0 西安电子科技大学博士学位论文：遗传算法的模式理论及收敛理论 不同之处，其最主要的特点体现在以下五个方面t 遗传算法的搜索过程从一群初始点开始搜索，而不是象传统优化方法那样 从单一的初始点开始搜索，这种机制意味着搜索过程可以有效的跳出局部 极值点 遗传算法只需要利用目标函数值的信息，而不是象传统的优化方法主要采 用目标函数的梯度等解析信息； 遗传算法具有显著的隐并行性遗传算法虽然在每一代只对有限个个体进 行操作，但处理的信息量为群体规模的高次方； 遗传算法便于与其他方法相结合，而且非常适合于大规模并行计算机计 算，因此可以有效地用于解决较为复杂的优化问题，具有良好的通用性； 遗传算法具有很强的鲁棒性，即在存在噪音的情况下，对同一问题的遗传 算法的多次求解中得到的结果是相似的 2 2 遗传算法的基本框架 遗传算法是一种具有“生成+ 检验特征的搜索算法，以编码空间代替问 题的参数空间，以适应度函数为评价依据，以编码群体为遗传基础，以对群体 中个体位串的遗传操作实现遗传机制，建立起一个迭代过程从代表问题可能 潜在解集的一个种群( p o p u l a t i o n ) 开始( 该种群由一些经过基因( g e n e ) 编码( e n - c o d i n g ) 的一定个数的个体( i n d i v i d u a l ) 组成) ，根据问题的特点，制定特定的适 应度函数( f i t n e s sf u n c t i o n ) ，对每一代种群，根据问题域中个体的适应度( f i t n e s s ) 大小来选择( s e l e c t i o n ) 个体，利用杂交算子( c r o s s o v e r ) 和变异算子( m u t a t i o n ) 等 遗传算子( g e n e t i co p e r a t o r ) 进行作用，从而产生出代表新的解集的下一代种群 遗传算法在整个遗传过程中的遗传操作是随机性的，但它呈现出的特征并不 是完全随机搜索，它能有效的利用历史信息来推测下一代期望性能有所提高 的寻优点集这样一代代的不断遗传，最后收敛到一个最适应环境的个体上， 求得问题的最优解遗传算法的基本框架如下t s t e p l 按照某种方式( 比如随机方式) 产生初始种群p ( 0 ) = 胡，建，鼎) ， 令= 0 ，对p ( t ) 中每一个个体( i n d i v i d u a l ) 霹0 【1 ，n d ，进行编码( e n c o d i n g ) ， 第二章遗传算法的基本理论 1 l 得到相应的点叫做染色体( d l r o m o m e ) 或字符串( s t r i n g ) 6 0 = + + ( 一 般的，经典遗传算法采用二进制编码，如哿= 0 0 1 0 0 1 ) ； s t e p 2 计算p ( t ) 中每个个体霹的适应度； s t e p 3 按照某种规则从p ( t ) 中选择一个子种群r ( t ) cp ( t ) 作为产生子代的 父母，用杂交( c r o s s o v e r ) 算子作用于p ，( t ) 产生一些子代( o f f s p r i n g ) ，再用变 异( m u t a t i o n ) 算子作用于每个子代产生新的子代集合o ，计算o 中每个个 体的适应度；k s t e p 4 用选择( s e l e c t i o n ) 算子从p ( t ) u o 或0 中选出下一代种群p 0 + 1 ) ，令t = t + 1 ； s t e p 5 若中止条件成立，则停止；否则，转s t e p 2 以下是遗传算法几种常见的基本算法形式， ( 1 ) 经典遗传算法( c a n o m c a lg e n e t i ca l g o r i t h m ，c g a 1 0 2 ) l s t e p l 确定算法参数：种群规模，杂交概率纯，变异概率p m ； s t e p 2 随机产生初始种群x ( o ) ，置k = o ； s t e p 3 从x ( 女) 中独立选取对父本； s t e p 4 独立地对对父本进行杂交运算产生个中间个体； s t e p 5 独立地对个中间个体进行变异得到下一代种群x ( k + 1 ) ； s t e p 6 若满足停机准则，则停止；否则置k = k + 1 ，s t e p 3 ( 2 ) e l i t i s t 选择遗传算法( e f i t i s ts e l e c t i o ng e n e t i ca l g o r i t h m ，e s g a r 1 叫) s t e p l 确定算法参数。种群规模，杂交概率p c ，变异概率p m ； s t e p 2 随机产生初始种群x ( o ) ，置 = 0 ； s t e p 3 从x ( k ) 中独立选取n 一1 对父本； s t e p 4 独立地对n 一1 对父本进行杂交运算产生n 一1 个中间个体； 1 2 西安电子科技大学博士学位论文：遗传算法的模式理论及收敛理论 s t e p 5 独立地对n 一1 个中间个体进行变异得到下一代种群x ( k + 1 ) 的前n 一1 个个体； s t e p 6 将x ( k ) 中的最优个体作为第七+ 1 代的第个个体； s t e p 7 若满足停机准则，则停止；否则置k = k + 1 ，转s t e p 3 。 ( 3 ) 父代参与竞争的遗传算法 1 0 3 z s t e p l 确定算法参数：种群规模，杂交概率p c ，变异概率p m ； s t e p