（计算机应用技术专业论文）扩展的连锁学习遗传算法.pdf

中文摘要 ，、 f 遗传算法是由j h h o ll a n d 在1 9 7 5 年首先提来出的，它主要是模拟 生物界自然选择和自然进化过程来解决复杂i o l 题的随机搜索算法。作为一 种拟生优化算法，它可以在复杂的空阳j 进行搜索、优化。因其具有极高的 鲁棒性，遗传算法已经被成功地应用于解决商业、工程和科学等领域中复 杂的优化问题，成为新一代的优化工具。 但是，l 于经典遗传算法尚存在某些不足，致使遗传算法的应用受到 影响。近年米，钊。对以上问题，研究人员做了大量的工作，提出了多种解 决方法。但是，诸如早熟收敛，收敛速度慢等问题依然存在。因而，如何 提高算法的效率和准确性是遗传算法中最主要的问题。、一 本文应用遗传学和进化生物学的理论和方法对遗传算法进行了研究。 在三个方面对遗传算法进行了改进： 1 应用生物学的理论及实验结果指出，生物对于选择的响应大部分 是以已经存在的遗传变异为基础的，而响应选择的速度，则取决于生物是 否已经具备有利于进化方向或选择方向的连锁。将以上结论应用到遗传算 法的研究中，就可以很清楚地知道，初始种群所包含的基因和连锁不平衡 方式是非常重要的，它既关系到遗传算法最终解的f 确性，也对算法的效 率有很大的影响。遗传算法的初始种群是随机选取的，这是遗传算法作为 一个全局搜索算法的特征，是不能加以改变的。但是，我们可以通过设定 某些条件或使用某些方法，对随机选取的种群进行处理，使之尽量达到符 合我们要求的状态。因而本文根据近交理论，提出了以小种群、短染色体 进行预处理的方法，使之为其后的标准算法提供具有大量优秀基因和有利 于进化方向的连锁的初始种群。 北方交通人学碰i i ：毕业论文 2 2 提出了用基因流取代突变算子，以保持种群的多样性，避免早熟 收敛。遗传学中遗传变异程度的增加，等同于遗传算法中种群多样性的增 加。衡量遗传变异程度的指标为遗传方差。本文通过比较突变和基因流的 遗传方差，从理论上证明了基因流导致的遗传变异大于突变，因而得出基 因流更有利于保持种群多样性，避免早熟收敛的结论。并进步给出了基 因流的取值，为其实际应用提供了方便。 3 讨论了内含子在遗传算法中的作用，及引入内含子的时机。在预 处理种群中的染色体，仅包含少量内含子，而经过预处理的染色体己经具 备以有利于进化方向的基因组成的优秀的建筑块，此时再将大量的内含子 插入到内含子群中，使内含子处于恰当的位置，以提高算法的效率。 最后在连锁学习遗传算法的基础上，加入以上三点改进方法，进而提 出了扩展的连锁学习遗传算法。并通过连锁学习遗传算法和扩展的连锁学 习遗传算法比较的实例，证明了新的算法具有更高的效率和准确性。 关键字：遗传算法进化生物学： 遗传学： 连锁霉冬传算法 连锁预处理：基因流： 内含子 ：坐查銮望叁堂塑! ：生、业堡兰一二_ ! 二一 a b s t r a c t g e n e t i ca l g o r i t h m ( g a ) w a sf i r s t l yp r o p o s e db yjhh o l l a n dir l1 9 7 5 i tisar a n d o ms e a r c h n gc a l c u l a t i o nt os o l v et h ec o m p e xp r o b l e m b ym i m i c k i n gt h ep r o g r e s s o ft h en a t u r es e e c t i o na n dn a t u r e e v o l u t i o ni nb i o l o g i c a lk i n g d o m 。a sa no p t i m a lm i m i cm e t h o do f c a l c u l a t i o n g ai sa b l et os e a r c ha n do p t i m i z e i nt h ec o m p l e x e n v ir o n m e n t d u et ot h eq u i t eh i g hr e b u s t n e s s ，g ah a sb e e n s u c c e s s f u l l ya p p l i e dt os o lv et h ec o m p l e xo p t i m a lp r o b l e mi n c o m m e r c i a l ，i n d u s t r y ，a n ds c i e n c e ，e ta 1 h o w e v e r ，s o m ed r a w b a c ki nt h ec l a s s i cg ac a u s e st h ec o m p r o m i s e t h ea p p l i c a t i o no fg a r e c e n t l y ，f o c u s i n go nt h i sp r o b l e m ，m a n y r e s e a r c h e r sd i dt r e m e n d o u sw o r ka n dp r o p o s em a n ym e t h o d st os o l v e i t d e s p i t et h a t ，s o m ep r o b l e m ，s u c ha sp r e m a t u r ec o n v e r g e n c ea n d s l o wi nc o n v e r g e n c e 。s t i l le x is t e d t h u s ，h o wt oi m p r o v et h e e f f i c i e n c ya n da c c u r a c yo fc a l c u l a t i o ni st h em o s ti m p o r t a n tp o i n t f o rg a t h ist e x ts t u d i e sg aw i t ht h et h e o r ya n dm e t h o d so fg e n e t ic sa n d e v o l u t i o n a r yb i o l o g ya n di m p r o v e sg ai nt h r e ea s p e c t s ： 1 a c c o r d i n gt ot h eb i 0 1 0 9 i c a lt h e o r ya n de x p e r i m e n t ，c r e a t u r e s r e s p o n s et os e l e c t i o ni sm a i n l yb a s e do nt h ee x i s t i n gg e n e t ic v a r i a n c e o nt h eo t h e rh a n d ，t h es p e e do ft h i sr e s p o n s eisd e p e n d i n g u p o nw h e t h e rc r e a t u r e sd oa l r e a d yh a v e1 i n k a g ew h i c hi sg o o df o rt h e d i r e c t i o no fe v o l i j t i o no fs e 】e c t i o n w h e nw eu s e dt h ea b o v e ! ! 变塞塑查兰璺! ：望些堡曼 ：! ： c o n c u sj o ni n t ot h es t u d yo fg a ，w ec l e a r l yk n e wt h a tt h eg e n ea n d i i n k a g ed i s e q u i l i b r i u mi nt h ei n i t i a lp o p u l a t i o n w a sc r i t i c a l ，w h i c h w a se s s e n t i a lf o rg an o to n l yi nt h ea c c u r a c yo ff i n a lr e s u l tb u t i nt h ee f f i c i e n c y 。l 氇er a n d o mc h o o s eo ft h e n i t i a lp o p u j a t i o nc a r r o t b ec h a n g e da si ti st h ec h a r a c t e r i s t i cw h e ng ai st h o u g h tt ob ea g l o b es e a r c hc a l c u l a t i o n w e ，h o w e v e r ，w e r ea b l et om a k et h ei n i t i m p o p u l a t i o nf i tt ot h es t a t u sw er e q u i r e db ye i t h e rs e t t i n gu ps o m e c o n d i t i o no ru s i n gs o m em e t h o d s a c c o r d i n gt ot h ei n b r e e d i n gt h e o r y ， t h ist e x tp r o p o s e dt h a tt h em e t h o db yp r e t r e a t i n gs m a l lp o p u t a t i o n a n ds h o r tc h r o m o s o m em a y p r o v i d e t ot h et h e r e a t 、t e rs t a n d a r d c a l c u l a t i o nw i t ht h ei n i t i a lp o p u l a t i o i lw i t hal o to fg o o dg e n e sa n d 1 i n k a g eg o o df o re v o l u t i o n 2 。w ea l s op r o p o s e dt h a tb yu s i n gt h eg e n i cs t r e a mt or e p i 8 , c e m u t a t i o no p e r a t o r w 0m j g h tk e e pt h ev a r i e t yo ft h ep o p u l a t i o na n d a v o i dt h ei m m a t u r ec o n v e r g e n c ea sw e l l t h ei n c r e a s ei nt h eo e n e t i c v a r i a n e ei se q u i v a l e n tt ot h ei n c r e a s ei nt h ev a r i a n c eo fp o p u l a t i o n i ng a g e n e t i cv a r i a n c ei st h er u l et om e a s u r et h ed e g r e eo fg e n e t i c v a r i a n c e b yc o m p a r i n gt h eg e n e t i cs q u i r ed e v i a n c eh e t w e e nm u t a t i o n a n dg e n es t r e a m ，w et h e o r e t i c a l l yp r o v e dt h a tt h eg e n e t i cm u t a t i o n c a u s e db yg e n es t r e a mw a sl a r g e rt h a nj tc a u s e db ym u r a t i o n t h e r e f o r e ，w ec o n c lu d e dt h a tt h eg e n es t r e a mw a sb e t t e rf o rk e e p in g t h ev a r i e t yo f p o p u l a t i o na n da v o i d i n gp r e m a t u r ec o n v e r g e n c e m e a n w h il e ，w ef u r t h e rg a v et h ev a l u eo fg e n es t r e a ma n dm a d et h e p r a c t i e ec o n v e n i e n t 3 w ed i s c u s s e dt h ef u n c t i o no fi n t r o ni n 懿a n dt h ea p p r o p r i a t e ! ! ! j 塑窒塑叁竺塑! ! 皇些堡苎 ：! ： t i m et oi n t r o d u c ei n t r e n t h ec h r o m o s o m e i nt h ep r e t r e a t in g p o p u l a t i o no n l yc o n t a i n e d f e win t r o n w h i l et h ec h r o m o s o m eh a v e a l r e a d yh a dg o o dc o n s t r u c t i o nm o d u l et h a tc o n s is t e di ng e n eg o o df o r e v o l u t i o na f t e rp r e t r e a t m e n t ，l o t so fi n t r o nw a si n s e r t e di n t ot h e c l u s t e ro fi n t r o n w h i c hm a d et h ei n t r o ni nt h er i g h t1 0 c a t i o n ，a n d t h e r e a f t e ri m p r o v e dt h ee f f i c ie n c yo fc a l c u l a t i o n f i n a l l y ，b a s eo nt h el i n k a g el e a r n i n gg e n e t i ca l g o r i t h m ( l l g a ) ， ，l i t e ra d d i n gt h ea b o v et h r e ep o i n t w es u g g e s t e de x t e n d e dl in k a g e l e a r n in gg e n e t i ca 1 9 0 t i t h m ( e l l g a ) b e s i d e s ，w ep r o v e dt h isn e w a 1g o t i t h mh a dm o r ee f f i c i e n c ya n da c c u r a c ya f t e rd e m oc o m p a r i n gt h e 1 1 g f l n de 1 i ，g k e y w o r d s ：g e n e t i ca 1 9 0 r i t h m ：e v e l u t i o n a r yb i o l o g y ： g e n e t jc l i n k a g el e a r n i n g g e n e t i c a 1 9 0 r i t h m ：l i n k a g e ： l i n k a g ep r e t r e a t i n g ： g e n i cs t r e a m ：i n t r o n 此打交通入学坝i ：毕业l 仑殳 第一章序言 遗传算法( g e n e t ica g o r jt b m ，o h ) 是由j h h o l l a n d 在19 7 5 年首先 提来出的，它主要是以模拟生物界自然选择和自然进化过程来解决复杂问 题的随机搜索算法。 地球上的生物都经历了一个漫长的进化过程，大凡生存下来的生物， 无论是动物、植物、微生物乃至病毒，都形成了自己独特的生活和行为方 式、独特的功能，以适应其生存的环境。各种生物都被生活所限定，或者 说被自然所优化。 在自然界巾，一切生物都受到自然的选择，适者生存与自然条件选择 支配着自然界中万物的演变。 生物为了适应环境，通过交配、变异和繁殖等方式末改变遗传基因， 适合环境的便生存，否则将被淘汰。此过程经过数代乃至数十代的繁衍之 后，就会产生更为适应环境的遗传基因。这种改变遗传基因以适应环境的 生命进化机制为我们在优化人工生命系统的研究方面提供了一套崭新的方 法。这就是在自然科学研究中使用的一种方法，即拟生法。在计算机算法 中利用生物进化机制的拟生法实现优化及建造自适应的人工生命系统就产 生了遗传算法。 达尔文的“自然选择”和“适者生存”原理是遗传算法的参照依据。 遗传算法模拟了生物为适应自然环境而发生的进化过程，通过选择、交叉、 突变生成专门化的基因组，即遗传算法是模拟自然选择与适者生存的生命 进化机制来实现优化和建造人工生命系统的一套算法技术。因而可知，遗 传算法是生物学、生命科学和计算机技术的交叉科学，创立了新的优化方 法。遗传算法具有演变为复杂系统的能力和灵活性。演变包含了历史继承 北方交通人学坝i j 毕业论史 - 2 - 性和时i 剐构造的复杂性。演变是遗传算法的本质和核，心，具有时间发展行 为。 遗传算法的有效性在于列入了时间算予的作用。生命现象发展到今天 是数百万乃至上亿年生物进化的结果。数百代选择、交叉、突变的结果本 质上是一个极复杂的时空结构的积淀。这就是遗传算法区别于传统优化技 术的本质。自然生物的复杂性都来源于反复应用一些简单的动态规律，非 常复杂的行为产生于非常简单的控制系统。 自然生物系统利用遗传、变异和自然选择过程构成了完整的生命机 制，因而它具有极好的适应性和有效性。一般的系统不具备演化的功能， 没有发展多样化及选择的前提。遗传算法的选择、交叉和突变所构成的机 制为演化出具有复杂结构和功能的系统以及最终的演化提供了前提条件。 使之完全不同于一般的系统。 遗传算法将字符串结构中的适者生存与随机信息变换相结合，构成一 个搜索算法。此算法对于人工搜索有某种程度的革新意义。遗传算法虽然 是随机的，但它不是简单地随机漫游，它有效地利用历史信息以推测新的 搜索点，达到期望的高性能。 遗传算法是拟生优化算法，此外，目前尚存在多种类型的优化算法， 包括拟物算法，如模拟退火法；数学方法，如导数法、枚举发、随机法等。 但它们都存在各自的局限性，只适应于一定的条件范围，即缺乏鲁棒性。 但设计人工系统时无疑希望系统具有鲁棒性，这样可以达到高层次的适应 性，做到事半功倍。 遗传算法可以在复杂的空倒进行搜索、优化，这已被理论和实践所证 明。作为一种新型的具有极高鲁棒性的优化方法，它已经被成功地应用于 解决商业、工程和科学等领域中复杂的优化问题耻】。遗传算法作为基于自 然选择和遗传学原理的有效搜索方法，在有噪声干扰的大系统中动态寻 生塑奎塑苎竺丝! 兰些堡兰一二三二- 优，已成为新一代的优化工具。 遗传算法与传统方法的不同之处在于： 1 遗传算法使用参数集的编码，而不是参数本身。 2 遗传算法的目标函数指引遗传过程，不是采用求导数或其他定理。 3 遗传算法在多点上搜索，而不是一个点。 4 遗传算法使用可能性变换，而不是定论法则。 但是，由于经典遗传算法尚存在某些不足o “，如早熟收敛，收敛速度 慢，收敛过程稳定性差，搜索过程可控性差等等，致使遗传算法的应用受 到影响。近年来，针对以上问题，研究人员做了大量的工作，提出了多种 解决方法。其中如连锁学习遗传算法( l l g a ) 、最优保留遗传算法”“1 ( e g a ) 在提高遗传算法的效率方面取得了一定的进展，但仍然存在一些 不足。l l ( 3 a 强调了连锁在进化中的重要性，但由于初始种群是随机选取 的，因而很可能导致连锁的进化速度不必要地减慢；同时，随着选择压力 的增加，各基因问的连锁更加紧密，有害的基因因为与有利的基因紧密连 锁。被清除的可能性减少，这些都影响了算法的效率。e g a 通过保留每 一世代的最优个体提高算法的收敛速度，最优保留操作的特点和性质决定 了变异在算法中起重要作用，但由于变异的速度无法与选择的速度竞争， 致使算法出现早熟收敛的问题。 - 所以本文应用遗传学和进化生物学的理论和方法对遗传算法进行了研 究。在三个方面对遗传算法进行了改进：一、指出当有利于进化方向的连 锁在初始种群大量存在时，算法的收敛速度及稳定性都会有所提高，进而 提出了以连锁预处理提高遗传算法的效率的方法；二、提出了用基因流取 代突变算子。以保持种群的多样性，避免早熟收敛：三、讨论了内含子在 遗传算法中的作用，及引入内含子的时机。最后在连锁学习遗传算法的基 础上，加入以上三点改进方法，进而提出了扩展的连锁学习遗传算法。并 j ! 查奎望叁兰塑! ! 兰些笙墨一二生 通过连锁学习遗传算法和扩展的连锁学习遗传算法比较的实例，证明了新 的算法具有更高的效率和准确性。 本文共分六章，第一章序占，介绍了遗传算法来源于对生物进化机制 的模仿。因而它较其他的优化算法更具鲁棒性。但同时，经典遗传算法仍 存在某些不足需要加以改善。 第二章经典遗传算法，介绍了经典遗传算法的编码、交叉、选择和突 变等主要操作及模式理论。 第三章进化生物学，介绍了哈迪一温伯格定律、遗传方差、近交理论 等本文应用到的一些遗传学和进化生物学的概念和理论，以及一个重要的 生物对人工选择响应的实验。 第四章连锁学习遗传算法，介绍了连锁学习遗传算法的连锁理论，新 的编码方式和交叉算子。 第五章连锁预处理、基因流和内含子，介绍了连锁预处理、基因流和 内含子的内容和意义，以及如何利用他们对连锁学习遗传算法进行改进， 以构成新的算法扩展的连锁学习遗传算法。 第六章扩展的连锁学习遗传算法，介绍了扩展的连锁学习遗传算法的 内容和结构，并通过实例将连锁学习遗传算法和扩展的连锁学习遗传算法 进行比较，证明了新的算法具有更高的效率和准确性。最后两章概括了本 人主要的研究工作。是本文的重点。 北方交通人学坝l 。毕业论业 第二章经典遗传算法 经典遗传算法将字符串结构中的适者生存与随机信息交换相结合，构 成一个搜索算法，它对于人工搜索具有某种程度的革新意义。 作为遗传算法的创始人，j h 1 t o l l a n d 及其学生们为此作出了极大贡 献m 。他们定义了算法的编码方式和算法的三个主要的算子一一交叉算 予、选择算子、突变算子，并提出了模式理论( 或建筑块假设) ，为遗传 算法以后的研究奠定了基础。当时他们从事这项研究的目的有两个，一是 试图抽象并精确地阐述自然系统的可适应性过程，二是设计人工系统软件 并使其保持自然系统的重要特色。这种尝试导致了自然和人工系统科学的 一些重要发现。 2 1 遗传算法概述 经典遗传算法”3 是建立在达尔文自然选择和遗传进化基础上的迭代搜 索过程，问题的解由定长的字符串表示。在每次迭代中，都保留一组候选 解，并按照某种原则从中选出一些解，利用遗传算子，如交叉和突变等， 对其进行演算。产生新一代的一组候选解。重复此过程。直至收敛于某种 指标。 遗传算法的核心有两个方面：i 如何选择父代来产生予代，以保证后 代具有优良的特征。而且分布广泛，以增加求得全局最优解的机会。2 采 用何种遗传算子对解进行操作，既要能够保留原有解中的优良特性，又能 恢复丢失的重要信息，因而研究和设计性能优良的遗传算子始终是推动遗 传算法发展的动力。 北方交通大学颂l 毕业论文 2 1 1 遗传算法的主要操作 1 编码 遗传算法中，问题的解一般是用二进制的字符串表示的，遗传算子也 是直接作用于字符串的，这样，如何x t 问题的解编码以形成字符串也就成 为遗传算法的一个重要问题。 2 选择算子 是从父代种群中，以适值函数的概率，选择留种的种群。 3 交叉算子 是随机从种群繁殖交配池中选取交配对象进行交配。 4 突变算子 是随机将种群字符串的某一位进行更改。 5 收敛判断 常规的数学方法有数学上比较严格的收敛判掘，但遗传算法的收敛判 据是启发式的。目前使用的收敛判断有多种，如根据时间或迭代次数：或 根据解的质量等等。 2 1 2 遗传算法应用实例 为了更形象地说明遗传算法的各个主要操作及其过程，这里给出一个 使用经典遗传算法处理特定优化问题的实例，求函数f ( x ) = x 2 的最大值， 其中x 取0 到3 l 之间的整数。首先对参数按二进制( 也可取其他进制) 编码成定长的字符串。对于我们给出的具体问题，主要使用5 位二进制就 可以表述x 的取值区间。 我们规定5 位长度的字符串表示一个元素，这样随机选取4 个元素构 成初始种群，如表2 - 1 所示。这些字符串表示了x 的值，通过x 和f ( x ) 的 j ! 垄窒望叁兰墼! ：兰些堡兰 ：! ： 函数关系就可以知道f ( x ) 的数值。以初始种群中的第三个字符串0 1 0 0 0 为例，这是一个无符号的二进制整数，表示十进制的数值8 ，为了计算出 8 所对应的函数值或者说是目标函数值，只需简单地将x = 8 代入f c x ) ， 求得f ( x ) = 6 4 。我们这里定义f ( x ) 为字符串的适值，而百分比是指每个 字符串的适值与种群中4 个字符串适值和的比率。 表2 1 初始种群 现在开始讨论遗传算法的全过程。先从选择开始，从初始种群中随机 选取4 个放入交配池中。由于是随机选取，初始种群中的元素有的可能被 多次选中，有的元素可能未被选中，不能遗传而被淘汰。那么随机选取的 原则是什么呢? 根据生物学中“适者生存”的思想，在这里就是适值高的 存活率高，反之存活率低。显然，第2 号、4 号字符串的适值高，因此它 们被遗传的可能性大。我们把适值百分比作为选取字符串的随机数。通过 计算四个字符串的适值函数可得到适值的总和为1 1 7 0 ，这样各个字符串 的百分比也就容易产生了。 下面用旋转一个圆盘的方法来模拟选择过程。首先将圆盘按上述适值 百分比划分区域。再设定一固定指针位置，当旋转的圆盘停止时，指针所 指示的百分比区间就是所要取的字符串。旋转四次可以选取出四个字符 串，假设初始种群中的字符串1 号被选中一次，2 号被选中两次，3 号未 北方交通人学坝l + 毕业论艾 被选中，4 号被选中一次，从而组成了被放入交配池中的四个字符串。这 个过程就是选择。3 号字符串的适值低，被选中的概率就低，在本例中未 被选中是可信的。被选中的四个字符串会放入交配池中，准备进行交叉操 作。 交叉操作分两步进行，第一步是自由配对，即随机选取配对的两个字 符串：第二步是随机选取每对字符串的交叉位置。表2 2 中的选择是l 、 2 号字符串配对，3 、4 号字符串配对，第一对的交叉位置在4 ，而第二对 的交叉位置在2 。通过交叉产生了四个新字符串构成的额种群，新种群的 最大适值、平均适值均高于父代种群，它表现了进化。 表2 - 2 交配池中的种群 经典遗传算法的最后一个操作是突变，突变是在字符串上进行的。并 非在每一次交叉操作之后都进行，而且突变率不能太高，生物的遗传也是 如此。假如取突变率为0 0 0 1 ，则种群中共有2 l o 个可转换的位置，因而 只有2 0 o 0 0 1 = o 0 2 位会发生突变。在这个例子中没有一位发生突变。 非常明显，以上例子给出了一个很好的结果。从进化的过程可以看出， 种群的不断改善并非侥幸。第一次生成的初始种群中，字符串11 0 0 0 能得 到两个拷贝并非偶然，这是和它的适值相联系的。而新种群中出现了适值 更高的字符串1 1 0 1 1 ，是交叉算子作用于字符串1 l x 和x 1 1 连接成新 概念的结果。 北方交通人学坝l 。毕业论史 9 在仞始种群中，表面上没有太多的信息，只是四个独立字符串和它们 的适值。当我们仔细观察是就会发现其中特定的相似性，字符串的类型与 性能有着密切的关系。例如，以l 开头的字符串性能最好，因而这是进化 过程中的一个重要成分。在种群中寻找相似性以及它们和对应值之间的因 果关系，在这个过程中会接受大量的信息来帮助和指导我们进行研究。 而接受信息量的多少，准确性如何，是以模式来衡量的。 2 1 3 模式 一个模式是一个相似模板，相似模板是指在特定字符串位置上具有栩 似性的字符串。例如，在二进制的字符串中增加号。通过这个扩展的字 符集可以产生新的字符串。如果在模式的每个位置上的l 、0 和都与特 定字符串中的l 、0 和x 相匹配，则模式与这个特定字符串相匹配。例如， 模式x 0 0 0 0 与两个字符串相匹配，它们分别是1 0 0 0 0 和0 0 0 0 0 。再例如， 模式1 1 l x 描述了含有四个成员的集合，f 0 1 1 1 0 ，叭1 1 1 ，1 1 1 1 0 ，1 1 1 1 1 ) 。 计算有多少可能的模式是一件有启发的事情。在前面的例子中，当字 符串的长度f - 5 时，就会有3 5 = 2 4 3 种不同的模扳，因为五个位置中的每 个位霞都可能是1 、0 或x 三种情况。通常，对于基数为r 、长度为，的字 符集有( 月+ 1 ) 。种模式。 在前面讨论的例子中，种群包含四个字符串，如果把这四个字符串孤 立地看，则可得到四条信息。然而，当我们把字符串和字符串对应的值， 以及种群中字符串的相似性一起考虑，就会获得许多的信息，精确地计算 获得信息的数量，需要了解一个特定种群中的字符串。为了获得一个特定 种群中模式个数的范围，首先要计算包含在一个独立字符串中的模式个 数，然后得到这一种群中的模式总个数的上界。 为了弄清楚以上问题。以一个长度为5 的字符串1 1 1 1 1 为例子。这个 北方交通人学颂i + 毕业论史 1 0 - 字符串是25 种模式中的一个，因为每个位簧都有一个实际值或一个不相 关符号，通常一个特定字符串包含2 7 种模式，包含月个元素的种群中大约 有2 7 到疗27 种模式，它们依赖于种群的变化。考虑相似性的最初动机是为 获得更多的信息以帮助指导对遗传算法的研究。对计算模式个数问题的讨 论表明，关于相似性的很多重要信息真正包含在大小适度的种群中。 在个种群中包含有2 喹0 ”2 种模式，有多少能通过遗传算法被实际 处理呢? 为了回答这个问题，我们考虑一下从个种群到生成下一个种群 过程中的选择、交叉、突变对重要模式的增长和衰减的影响。选择对一个 模式的影响是容易确定的，因为越是符合要求的字符串被选中的可能性越 大。按平均数计算，给观察到的最相似模板以增量就可以了。然而，仅仅 是选择将不会有新的产生物。那么当选用了交叉算子，它对特定摸板产生 什么影响昵? 若交叉未切断模式，它就留下一个完好的模式，反之，切断 了模式，就将原模式破坏掉。显然1x 0 容易被破坏，而1 0 有可能 不被破坏。 另外，突变是以低速率进行的，即在多次选择、交叉之后才进行一次 突变，它不会经常破坏一个特定的模式，并且能得到意想不到的结果。 2 2 遗传算法的形式描述 2 2 1 基本理论 遗传算法的操作是非常简单的。首先根据处理对象的固有特征建立字 符串组成的种群，字符串的产生是随意的没有任何约束条件。然后拷贝其 中部分字符串，拷贝是随机的，适值高的字符串被拷贝的概率高，反之， 被拷贝的概率低这就是选择过程。被选择的种群放入交配池中随机配对， ! ! 查窒望叁兰堡：! ：兰些笙兰 一 ：! ! ： 并随机选取每一配对字符串的交叉点进行交叉。突变对遗传算法是必要 的。但是，它是第二位的，因此应按一较低速率进行，最终目的是经过一 个多次反复的过程得到一个最优结果。 为了严密地说明遗传算法的过程，我们有必要给出有关的定义 爿= 口ld 2 口3 a ， 口，( o ，1 ) 按照与自然生物相类似的方法，a 表示基因。在字符串中代表某一特征值， 也称指示值。当然，字符串没有必要必须按一定顺序排列，因此可以认为 字符串或是有序的，或是无序的，如 a = a tn nk 遗传算法需要一个由多个字符串组成的种群，一个独立的字符串a ( _ ，= l ，2 ， ) 包含在，时刻的a ( t ) 种群中。 对于模式( s c h e m a ) h ，由三个字符表示，即( 0 ，l ， 。定义可 以代表l 也可以代表0 。如模式h = 1 l 包含了a = 0 0 1 l l l ，这是因 为爿在第3 、4 位与模式相匹配。由此可知，一个长度为岫 0 ，1 ) 串，其 模式数为3 。 以上定义了遗传算法中信息量的描述方法，但仅此还不能开始进一步 的讨论，还需要辨别不同模式的一些描述方法。不同模式所表达的意思的 明确度是不同的。例如0 1 l x l 要比0 x x x 表达更明确，1 x l 要比1 x l x x 跨越更大的部分。为了定量地表示这些概念，在此定义两 个概念：模式的“位数”或“序”以及模式的定义长度。 模式的位数用o ( h ) 表示，指模式中确定位的数量。如h = 0 1 1 l 中的1 、2 、3 、5 位是确定位，故d ( 片) = o ( 0 1 1 1 x ) = 4 。同理，模式 h = 0 x 的位数o ( o x x ) = 1 。 模式的定义长度用巧( 日) 表示，它指模式中第一个确定位与最后一个 北方交通人学倾l 毕业论史 确定位之问的跨度距离，如h = 0 1 1 1 x x 的第个确定位是“0 ”，在第1 位( a ，：1 ) ，而最后一个确定位是“1 ”，在第5 位( a ，= 5 ) ，故 万( ) = a ，一a ，= 5 一i = 4 。同理，模式= 0 x x x x x 的定义长度 6 ( h ) = 0 。 2 2 2 选择对模式的影响 假设在给定的时刻，一个特定的模式包含在种群a ( t ) 中有种，则 我们计为：州= m ( n ，t ) 。当然在不同时刻的不同模式圩和m 的数量可能 不相同。在选择过程中，个串按照某一合理的过程拷贝。其拷贝的概率 为尸= ，：( 其中，表示某一串i 的适值) 。我们用m ( h ，+ 1 ) 表示种 群在t + l 时刻模式匹配的数量当种群的大小为 则 m ( h ，t + 1 ) = m ( h ，小n - 厂( h ) ， 其中，( ) 是在时刻，与模式h 匹配串的平均适值，若种群的平均适值 记作 ? = f j | n 那么 m ( h ，+ 1 ) = m ( h ，) + f ( h ) f 该式表明，一个特定模式的增减与模式的平均适值与种群的平均适值之比 有关。换句话说，模式的平均适值在种群的平均适值之上时，将会得到一 次遗传样本的增量，而在之下时，遗传样本将得到一个减量。 进一步讨论，我们假设f ( h ) = ，+ ，其中c 为常数，则 m ( h ，f + 1 ) = m ( h ，) 十( + c 厂) i f = m ( h ，) ( 1 + c ) 若选择从初始种群开始( ，= 0 ) ，且假设c 是一个稳定的值，则有 北方交通人学坝i 毕业论义 m ( h ，) = m ( h ，0 ) ( 1 + f ) 从上式可知，选择并行地按照指数形式增长( c 0 ) 或减少( c f 或厂( ) 厂) 以及定义长度万( 汀) 的大小。显然，( h ) 越大，占( ) 越小，则h 的数量越多。 2 2 4 突变对模式的影响 最后分析突变产生的影响。假设某一位的突变率尸卅，则保持率为 l 一只。显然每一个突变是独立的。当一个模式有0 ( ) 个确定位置时，则 模式的存活率为( 1 一只) “。一般情况下，匕 l ，则模式h 的存活率 可近似地表示为 1 一o ( h ) + 只 北方交通人学倒! l + 毕业论史 综合考虑选择、交叉、突变三个算子的共同作用，模式h 经过三个算子 的作用后，在下一代中的数量可表示为 m ( h ，f 十1 ) m ( h ，) f ( h ) f + 1 一p 占( j v ) ( 1 一，) 一d ( 日) + 己】 现在我们可以得出以下结论：定义长度短的、确定位数少的、平均适值高 的模式数量将随着遗传代的次数呈现指数增长。 、 2 2 5 举例 为了说明模式理论的正确性，有必要使用2 1 2 小节中遗传算法实例 的有关数据。该数据列于表2 3 一表2 7 。它除了以前给出的信息外，还 给出了三个特定的模式h i = l x ，h 2 = 1 0 ，h 3 = l 0 。 表2 4 选择前的模式处理 最人 7 2 9 表2 7 所有操作后的模式处理 观察选择、交叉、突变对模式日的影响。在选择阶段，字符串依据 它们的适值进行拷贝。在表2 3 中，我们注意到，2 号和4 号字符串体现 了模式。在选择之后记录了三个拷贝( 在交配池中的2 号、3 号、4 号 字符串) 。根据公式m ( t + 1 ) = m ( t ) f ( h ) f 可以计算以上结果是否符合模 式理论。模式平均值f ( h ) = ( 5 7 6 + 3 6 1 ) 2 ，种群平均值f = 2 9 3 ，则 m ( h ，十1 ) = 2 4 6 8 5 2 9 3 = 3 2 0 。该值与实际选取的数进行比较，说明拷 北方交通人学坝l j 毕业论文 贝数肌( h ，) = 2 ，量是正确的。进一步可以看到交叉对模式不会造成进一 步的影响，其原因是定义长度艿( h 。) = 0 。另外。在这个例子中只进行了 一代遗传，而突变率又很低，故没有任何一位发生突变。结果，根据模式 理论，对模式h ，得到了期望中的模式递增。 由于模式。有它自身的特殊性，在模式中只有一个确定位，缺乏普 遍性。因此还应进一步讨论模式h ，和肌。 在初始种群中与模式h ，1 0 匹配的串有2 和3 ，即m ( h ，) = 2 ， f ( h ：) = ( 5 7 6 + 6 4 ) 2 = 3 2 0 ，f = 2 9 3 ，所以 m ( h 2 ，t + 1 ) = m ( h 2 ，t ) 十f ( h 2 ) f = 2 + 3 2 0 2 9 3 = 2 1 8 在初始种群中与模式风l 0 匹配的字符串有2 ，即m ( 凰，) = l ， f ( h ，) = 5 7 6 ，f = 2 9 3 ，所以 m ( h ，+ 1 ) = m ( h 3 ，) 厂( h 3 ) f = 1 + 5 7 6 2 9 3 = 1 9 7 通过以上的计算可知，选择的情况符合模式理论。 交叉的情况有些不同，模式乩在交叉之后两个模式依然保存，因为 模式：的定义长度短，易于存活。字符串的总长度只有5 ，8 ( ：) = 1 ， 故打断或破坏模式圩：的可能性只有l 4 ，p = 1 一只= 1 1 4 = o 7 5 。所以 m ( h 2 ，t + 1 ) = m ( h 2 ，) ( 日2 ) f 只= 2 1 8 + 0 7 5 = 1 6 4 。该值与实际取2 基本符合。模式也则不同，它的定义长度6 ( h ：) = 4 ，巴= l ，只= 0 ， m ( h ，+ 1 ) = m ( h ，t ) f ( h 3 ) f + 只= 0 ，而实际为l 。这与模式理论并 不矛盾，交叉破坏了模式，但又可能被其他的模式所创生。 我们已从定性和定量两个方面了解了选择、交叉、突变的模式的影响。 短的定义长度、低序，在平均适值以上的模式可以在下一代中得到。这是 一个不依赖任何实际问题的事实。 ! ! 互奎些叁堂塑! 兰些堡皇 ：! ! ： 2 2 6 遗传算法处理的模式数目 根据前面的讨论可知，定义长度较长、确定位数较多的模式存活率较 低。那么如何估计在新的一代产生过程中，经历了选择、交叉和突变之后 模式个数的变化。 在有几个长度为j 的位串种群中，我们仅考虑存活率大于只的模式， 则死亡率为s 卜只，其中只为一给定的常数。如果突变率小，忽略不计t 经过交叉操作，某一模式的死亡率为只= 占( ) ( ，一1 ) 。为了保证其存活 率大于p ，则 b 占，f = l p 8 ( h ) ( t 一1 ) 占，得至u8 ( h ) s ( ，一1 ) 。设，。= 6 ( h ) + 1 ，贝0 = e ( 1 1 1 + 1 。 下面计算一个长 假设? = 1 0 ，? 。= 5 ， 符串可以表示为 度为，的字符串中模式长度小于等于l 的模式个数。 我们首先计算前5 位上的模式，将最后一位固定，字 l x x 其中表示为确定值0 或l 或。显然有2 h 个模式。为了计算总的模 式数，可以将样本逐次向右移一格，一共可移动，一l + 1 次。这样就可以 估算出长度为，。或短一些的模式数为 2 ( 1 一- j ) ( ，一，。+ 1 ) 由于模式数是二项分布的，我们可以得出大于，2 的模式数目和小于，2 的模式数目相等，而总的模式数为 2 “ 于f 2 的模式，则有 若我们只考虑大于等 n n ， 些立奎塑叁鲎型! ! ：兰些笙兰 一二! 竺二_ i n 2 一1 ( ，一，+ 1 ) 2 = n 2 2 ( ，一，+ 1 ) 如果我们选取种群大小为t l = 2 ，2 ，则 疗，=