（基础数学专业论文）遗传算子及群体多样性分析.pdf

j i i f iri r l li iil l li riii y 17 3 6 9 3 8 t h e a n a l y s i so f g e n e t i co p e r a t o r sa n dg r o u pd i v e r s i t y at h e s i ss u b m i t t e df o r t h ed e g r e eo fm a s t e r c a n d i d a t e ：w a n gy i n g s u p e r v i s o r ：p r o f w e ns h e n g y o u h u b e iu n i v e r s i t y w u h a n ，c h i n a 湖北大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 论文作者签名：易錾 日期砷年r 月7 日 学位论文使用授权说明 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即： 按照学校要求提交学位论文的印刷本和电子版本；学校有权保存并向国家有关 部门或机构送交论文的复印件和电子版，并提供目录检索与阅览服务；学校可以允 许采用影印、缩印、数字化或其它复制手段保存学位论文；在不以赢利为目的的前 提下，学校可以公开学位论文的部分或全部内容。( 保密论文在解密后遵守此规定) 作者签名：衫落 指导教师签名：主门芝久 日期0 3 弩 日期：2 0 1o f t0 匕上。， i “ o 摘要 二十一世纪是一个各领域的科学技术相互交叉的世纪，遗传算法的出现与发展也 正体现了生命科学与工程科学的相互渗透与促进。遗传算法是由美国人j h o l l a n d 教 授提出的，它是一种借鉴生物界的自然选择和自然遗传机制随机化搜索的算法，其主要 的特点是群体搜索策略和群体中个体之间的信息交换与搜索不依赖于梯度信息。它尤其 适用于处理传统的搜索方法难于解决的复杂和非线性问题，可以广泛应用于自适应控 制、优化组合、人工生命和规划设计等领域，是二十一世纪有关智能计算的关键技术之 一。 本文共分为四章，其中第一章简单介绍了论文的相关研究背景及选题的意义。第二 章和第三章是重点，分别对遗传算子和群体多样性进行分析。由于在遗传算法中，交叉 算子与变异算子是基本算子，其算子的选取好坏将直接影响最终的寻优结果，因此，对 于遗传算子性质的研究就显得极为重要。第二章以两点变异算子及两点交叉算子为例， 分析其性质并提出了一些改进的方案。又因为维持种群的多样性是遗传算法得以进化的 基础，但在仅有选择算子的作用下，群体很容易进入早熟状态，为了摆脱早熟的现象， 种群多样性将起到关键的作用。第三章针对二进制编码，分析选择算子、交叉算子以及 变异算子对群体多样性的影响，在此基础上着重讨论变异算子的影响。第四章是对全文 重点内容的总结，同时提出一些不足之处。 关键词：遗传算子；群体多样性；均匀分布 a b s tr a c t m a n yd i f f e r e n ts c i e n t i f i ct e c h n o l o g i e si n t e r a c ti n2 1c e n t u r y d e v e l o p m e n to fg e n e t i c a l g o r i t h m s ( g a ) e m b o d i e sm u t u a le f f e c to fl i f es c i e n c ea n de n g i n e e r i n gs c i e n c e g ai s a c c r e d i t e dt op r oj h o l l a n d i ti sak i n do fr a n d o ms e a r c ha l g o r i t h m st h a tm a k em o s to f n a t u r a lc h o i c ea n dg e n e t i cm e t h o d s i ti sc h a r a c t e r i s t i ct h a tp o p u l a t i o ns e a r c hs t r a t e g ya n d i n f o r m a t i o n e x c h a n g e a t eu n d e p e n d a b l eo fd e v i a t i o n i n f o r m a t i o n d i f f i c u l t yp r o b l e m s a p p e a r e di nt r a d i t i o n a ls e a r c hm e t h o d sa n dn o n l i n e a rp r o b l e m sm a yb es o l v e db yg a g ai s a l s oa p p l i e di nm a n yf i e l d ss u c ha sc o m b i n a t o r i a lo p t i m i z a t i o n ，m a c h i n el e a r n i n g ，a d a p t i v e c o n t r o l ，p r o g r a m m i n gd e s i g n s ，a r t i f i c i a ll i f ea n ds oo n s og ai so n eo ft h ei m p o r t a n t t e c h n o l o g i e si n2 1c e n t u r y t h i sp a p e rf a l l si n t of o u rc h a p t e r s t h ef i r s tc h a p t e ri n t r o d u c e sb a c k g r o u n do fp r o b l e m c o n c e r t e da n dm e a n i n go ft i t l ec h o s e a n dt h ef o l l o w i n gt w oc h a p t e r sa r em ym a i nw o r k s t h e yi n t r o d u c ea n a l y s i so fg e n e t i co p e r a t o r sa n dd i v e r s i t yo fg r o u pr e s p e c t i v e l y c r o s s o v e r o p e r a t o ra n dm u t a t i o no p e r a t o ra r eb a s i ci ng e n e t i ca l g o r i t h m s ，t h ec h o i c eo ft w ok i n d so f o p e r a t o r sa f f e c to p t i m u mv a l u e t h e r e f o r e ，i ti si m p o r t a n tt or e s e a r c ht h e s ek i n d so f o p e r a t o r s b a s e d o nt w o - d o t e dm u t a t i o na n d t w o d o t e d c r o s s o v e r c o n t a i n i n g a f i x e d _ l o c a t i o n t h es e c o n dc h a p t e ra n a l y z e st h e i rp r o p e r t i e sa n dp r o p o s e sa d v a n c e dr u l e s k e e p i n gd i v e r s i t yo fg r o u p si st h eb a s ef o re v o l u t i o no fg e n e t i ca l g o r i t h m s g r o u p sa r ee a s y t ob ep r e m a t u r ei nt h ec o n d i t i o no fs e l e c t i o no p e r a t o r t o g e tr i do fs t a t eo fp r e m a t u r e ， d i v e r s i t yo fg r o u p sp l a ya ni m p o r t a n tr o l e t h et h i r dc h a p t e ra n a l y s e se f f e c to fg ao nt h e b a s eo fb i n a r yc o d e a b o v ea l l ，t h i sc h a p t e rr e s e a r c h e se f f e c to fm u t a t i o no p e r a t o r i nt h el a s t c h a p t e r , is u m m a r i z em yw o r ka n ds u p p o s es h o r t c o m i n go fm yi d e a l k e yw o r d s ：g e n e t i co p e r a t o r s ；g r o u pd i v e r s i t y ；m e a nd i s t r i b u t i o n i l 目录 第一章绪论l 1 1 相关背景1 1 2 早熟和自适应问题的研究现状1 1 3 解决方法2 第二章遗传算子性质分析3 2 1 选择算子、交叉算子、变异算子的简单描述3 2 2 变异算子，交叉算子与个体均匀分布之间的关系4 2 3 均匀分布的应用1 3 2 4 ，j 、结。1 6 第三章群体多样性分析1 7 3 1 群体多样性的简介”1 7 3 2 多样性的几种描述1 7 3 3 遗传算子与群体多样性之间的关系1 9 3 4 j 、结“2 3 总结与展望2 4 参考文献2 5 墅l 【谢。“2 7 第一章绪论 第一章绪论 1 1 相关背景 遗传算法( g e n e t i ca l g o r i t h m s ) 是由美国m i c h i g a n 大学的j h o l l a n d 教授于1 9 7 5 年首先提出的，它是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。 h o l l a n d 教授的早期工作主要集中在生物学、社会学、控制工程、人工智能等领域中的 一类动态系统的适应性问题。随后，b r e m e r m a n 、d ej o n g 等人则将遗传算法应用于参 数优化问题，极大地促进了遗传算法的应用。1 9 7 5 年之后，遗传算法作为函数优化器不 但在各个领域得到了广泛的应用，还丰富和发展了若干遗传算法的基本理论。此后的大 批研究人员对遗传算法理论的基本框架和遗传算子进行构建和改进，并将它分别应用于 自动控制、工程设计、经济金融、机器学习、博弈问题等诸多领域之中。 g a 以其高效、实用的特点在各个领域中得到了广泛的应用，取得了较好的效果，并 越来越受到学术界的重视。经过三十多年不同领域科学家们的共同努力，人们从理论上 对遗传算法进行了许多有益的探索和改进，在某些理论和应用上取得了令人满意的结 果，但仍有一些有待进一步研究的工作： ( 1 ) 研究g a 遗传算子的策略，使其具有更为广泛的实用性，避免过早收敛 ( 2 ) 发展一些启发式的策略，引入知识领域，对搜索过程给予引导 ( 3 ) 参数环境对g a 的性质和结果的优劣至关重要，g a 的参数环境能改变g a 的函 数优化能力 ( 4 ) 进一步研究g a 的并行性及计算问题，使之能提高计算效益 本文主要针对( 1 ) 和( 2 ) 两方面的问题进行研究并提出一些改进方案。 1 2 早熟和自适应问题的研究现状 早熟1 1 9 1 是遗传算法中不可忽视的一个现象，它主要表现在两个方面： 接近最优化解的个体总是被淘汰，进化过程不能收敛 群体中的所有个体都陷入同一极值而停止进化 在遗传算法的运算过程中的每一个环节都可能出现产生早熟现象的因素，其具体的 表现如下： 在基于适应度比例的选择下，其它的个体被淘汰，大部分个体与x 一致 湖北人学硕上学位论文 在进化的初始阶段，生成了具有很强适应度的个体x 相同的个体进行交叉变化，从而未生成新的个体 群体中的大部分个体都处于与x 一致的状态 通过逆转或变异所生成的个体适应度高但数量少，导致被淘汰的概率很 大 由一可知，在遗传算法操作的作用下，新生代的群体不具备多样性是导致早熟 现象产生的一个主要原因，本文利用变异算子和交叉算子的性质，提出维持群体多样性 的几种方案，从理论上证明维持群体多样性的一个充要条件。 1 3 解决方法 由于遗传算法不要求被优化的对象具有连续、可导等特性，仅靠适应性函数来评估 个体，所以利用选择、交叉、变异等遗传操作，可以通过概率的变迁规划来指引遗传算 法的搜索方向。遗传算法中，交叉算子因其全局搜索能力强而作为重要算子，而变异算 子因其局部搜索能力强而作为辅助算子，遗传算法通过交叉算子与变异算子这一对既相 互配合又相互竞争的特性而具备全局和局部的搜索能力。在二进制里，本文以两点变异 和两点交叉算子为例，分析在独立、等概率的情况下生成的子代并不服从均匀分布，在 一定的代数后就会产生早熟现象，并给出子代服从均匀分布所需的条件，从而维持群体 多样性，克服早熟的现象。此外，我还将子代服从均匀分布在理论及应用上加以利用， 解决了一些问题。 同时，为了防止早熟现象，引进了衡量多样性的混合方法，并分析了遗传算子在单 独使用的情况下对混合方法的影响，在此基础上提出改进遗传算子和相应的自适应变异 概率。 2 第二章遗传算了的性质分析 第二章遗传算子的性质分析 本章我以两点变异和两点交叉算子为例，分析了在独立、等概率的情况下生成的子 代并不服从均匀分布，并给出子代服从均匀分布所需的条件。发现当子代服从均匀分布 时，能够有效的保持群体的多样性，这对防止早熟现象的产生无疑起到重要的作用，除 此之外，还简要讨论了子代服从均匀分布的一些应用。 2 1 选择算子、交叉算子、变异算子的简单描述 2 1 1 选择算子 从群体中选择优胜的个体，淘汰劣质的个体的操作叫做选择。选择算子又称为再生 算子。选择算子的目的是把优化的个体( 或解) 直接遗传到下一代或通过配对交叉产生 新的个体再遗传到下一代，选择操作是建立在群体中的个体适应度评估的基础上的。 目前用到的选择算子有以下几种： 适应度比例方法 适应度比例方法是目前遗传算法中最基本也是最常用的选择方法，在该方法中， 各个个体的选择概率和适应值成比例。 排挤方法 联赛选择方法 期望值方法 最佳个体保留方法 排序选择方法 其中 具体参见1 9 1 2 1 2 交叉算子 交叉是指两个父代个体的结构加以替换重组而生成新的个体的操作。通过交叉，遗 传算法的搜索能力得以飞跃的提高。 目前常用的基本的交叉算子： 一点交叉 在个体串中随机设定一个交叉点，实行交叉时，该点的两个个体部分进行互换， 并生成两个新的个体。 3 湖北大学硕+ l ：学位论文 两点交叉 两点交叉的操作与一点交叉类似，只是设置两个交叉点。 多点交叉 一致交叉 其中和具体参见【1 9 】 2 1 3 变异算子 变异算子的基本内容是对群体中的个体串上某些基因座上的基因组作为变动。一般 而言，变异算子操作的基本步骤如下： 在群体中所有个体的串范围内随机地确定基因座 以事先设定的变异概率矽来对这些基因座的基因值进行变异 册 遗传算法导入变异的目的有两个：一是使遗传算法具有局部的随机搜索能力，当遗 传算子通过交叉算子已经接近最优解时，利用变异算子的局部随机搜索能力，可以加快 局部最优解收敛。二是使遗传算法可维持群体的多样性，以防止早熟现象，此时的收敛 概率应取较大值。在遗传算法中如何有效地配合使用交叉和变异操作，是目前遗传算法 的一个重要研究内容。 2 2 变异算子，交叉算子与个体均匀分布之间的关系 2 2 1 变异算子分析 ( 1 ) 独立等概率变异位对子代的影响 对于父代中的任意一个个体a = 口。口：a ， 由公式知： e = 肿2 v 【智a ，2 v - j 】。由孔v ，均为取定的常数，所以为了分析方便，只需考 虑x 。= 口，2 肛。 设个体a 中，第k 位被选做变异的概率为p ( l = k ) 若第一次变异位与第二次变异位 相同时，则有彳山爿7 山a ，即a 未发生变化。其中k 仉2 。 设个体a = a i 口：口，经两点变异后( 设其变异位为。，l ：) ，得到新的个体为a 7 ，则 4 釜三主垄竺簦王塑丝垦坌堑一 一_ _ - _ - _ _ - _ _ _ - _ _ _ l - - - - _ _ _ 一一一一 a i = a , a 2 - - ( 1 一口) 1 - a l , ) 口，。有译码公式为： 。= 蕊i = 1 川一i = l i + 。_ f + ，磐+ 1 飞) 2 m + ( 1 飞) 舻 = l + ( 1 2 口厶) 2 一+ ( 1 - - 2 a 上：2 肛如 定理2 1 ：若( 1 2 口2 一岛= ( 1 一幻。) 2 - h , l 1 = l - 7 厶，厶札2 ) 证 r 若口工i = o 时，即2 喝= ( 1 一物。2 - 。 ( 1 ) 若a 吖= 0 时，即得2 一i = 2 ，亦即厶= 厶， ( 2 ) 若a 。= 1 时，即得2 n - l 1 m = - 2 一纠，此时矛盾。 2 0 若口= 1 ，一= ( 1 一物。2 肛吖 ( 1 ) 若口。；o ，一2 一= 2 一。，此时矛盾。 ( 2 ) 若a 工l i _ 1 时，即得一2 一厶- - 2 一纠，亦即= 厶7 综合1 。2 口可知结论成立。 定理2 2 ：若厶，工。工：，其中厶，工：，0 ，工：。 1 ，2 一，。 当( 1 2 口l 2 一一+ ( 1 一孙屯2 肛k = ( 1 一知。j2 “+ ( 1 2 口。2 “ + + p “= n ) p ( l ：= 耻i f ln = 雨1 ( 3 ) 式变形为： r ( x 一= x 一+ ( 1 2 a l ) 2 h 1 - ( 1 - 2 a h ) 2 ) = p “= i ) p 化甸) + p “= j ) p “= 驴寺 ( 2 ) ( 3 ) 从而可知，经过独立等概率的两点变异后的子代不再服从均匀分布。又由于 p ( x ，一x a ) = 丙1 ， p ( ) ( ，= x + ( 1 2 a k ) 2 h “1 札) 2 ) - 雨2 ，可知，当染色体的长度取较大值时， 经过两点变异的子代z 。，将会以较大的概率变异为x 。，即a 未发生变化，这说明此时的 变异是徒劳的，将会出现早熟的现象。 6 一 釜三兰鎏堡兰王塑丝要! ：堑 一 一- _ _ 一一 ( 2 ) 变异算子作用后，产生子代服从均匀分布所需满足的条件 定理2 3 ：设( 。，三：) 的联合分布为弓，若弓为方程弓+ 巳= 南( f 暮，) s ： o 1 f ，je l 2 ) 的解，则经过两点变异后子代服从均匀分布。 证由( 2 ) ，( 3 ) 可知：要使子代服从均匀分布，则需最= 匕+ 弓 ) 记m ：壹e ，则弓的矩阵表示为： i 嚣引 l 鼍- 予_ 朋刊 l 昂。 b ： “ j 又有联合分布所需满足的条件，即：壹壹弓：1 ， 即：弓+ e ( m 一巳) + m ：1 4 ) 又因为 m ：弓+ 弓o j ) ( 5 ) 由( 4 ) ，( 5 ) g n ：肘：晶 证毕。 推论2 1 ：设( 厶，岛) 的联合分布为弓，若经过两点变异子代服从均匀分布，则 打( 弓) = 矿习2 丽。 满足上式方程的解不只一个，现在给出一个具体的解( 也即( ，工：) 的联合分布) 。 在定理1 中取： 弓：弓( i n 只：巳，代入上式方程得弓= 丙f j l 再五( f 喾j ) ，昂= 经检验o 咒1 ，f ，j 札2 ) 故 弓= 酽而y 2 而丽 ： ； 1 ( n z - 。n + 2 ) 7 2 为其中一解。 寓；一 窖：南 湖北人学硕十学位论文 2 2 2 交叉算子分析 ( 1 ) 等概率的含固定位的两点交叉算子对子代的影响 现在简要介绍一下含固定位的优势：对于父代中的两个不同个体，如果对某个位置 ( 不妨设为l ，) 的两个个体厶以后的基因座都是一致的，则由交叉算子的特征得知，交 叉之后，若要生成新的的后代，其交叉位必须选择l ，以前的位置。一般地，若想使某个 较优的父代个体能在子代中保存，我们可以将固定位选为l + 1 。特别地，对于函数的最 优化问题，由于编码后，基因座上的高位对问题的影响较大，在进行交叉操作时，对于 事先给定的精度，可以忽略较低位的基因座位，虽然在固定位l 之后存在不同的基因座， 但对函数的优化结果影响不大。 设4 = 口。口：a l l 为已知父代中的一个个体，曰= 岛也气屯6 为父代中异于 a 的一个个体，l ：为交叉位，其中l 2 是固定位，0 , 2 l ：一1 ) 则爿与b 经过交叉后 得到爿7 = 口，口：屯+ 。吆口 由公式得： l ，= 髟+ 以一口，) j = 厶+ l 故以，为关于厶与6 ，的随机变量，设以，：e ，p ，厶) 又：z 一壹口，2 川z ( 6 ，厶) s t + 壹( 1 一口，) 2 州 i - l , + li - l , + t 设q ( ) ：壹( 1 - a j ) 2 一一，r ( ) ：妻口，2 一， j - z , 4 - 1，- + 1 引理2 1 【2 7 】： q ( ) ，r ( ) 均为递减的数列，即： q ( t 一1 ) e ( l ：一2 ) s e o ) ，月( 厶一1 ) r ( 厶一2 ) 尺( 1 ) 证明：直接验证可得。 从而由引理2 1 可得e ，的分布示意图： x a - r 0 ) t 一尺( 工：一1 ) 8 x a q ( t 一1 )t + q ( 1 ) 第一二章遗传算了的惟质分析 - i - _ _ - _ _ _ _ _ - _ _ - _ _ - _ - l _ - - - _ _ - _ l _ _ _ _ - _ _ - - - - _ _ 引理2 2 ： ( 1 ) p 【酢+ 1 ) 帅竭+ q ( ) 】：1 - - a l + 1 ) 2 。1 ( 掣+ 掣+ + 掣) ( 2 ) p x 。- r 锅如川刚川 = a t + 。2 q - l - j ( 掣+ 掣+ + 掣) ( 3 ) 帆( 6 ，吐】：掣+ 擎+ + 掣 ( 1 ) 对于l ，= 三。( 1 l 。 厶时 = p f 壹6 ，2 肛，壹口，2 肛，+ 量2 n - jm 壹口叫l lj = 工口+ 1j = 4 + i ，= + 1 ，= l + i ， = 1 p 【x p ，k ) 工+ q 仁) 】：p f 壹b j 2 n 一，壹口，2 一，+ 壹( 1 一口，) 2 n 一， 帆( ) 舛+ q ( ) 】= p 【，吕。叫j = 4 + l 印肛+ i = l o + ，( 卜口叫l ，= k + l 1 f 2 = p l b j 2 。 l ，= + 1 r 岛 ：p ly 、6 。2 肛 【品- 一 卢工o + l( 1 - a 加肛7 壹2 h 一壹l - a , ) 2 肛 ：! ：鱼：! ! ：鱼! 一 2 综上所述： 9 4 加纠+ 工 j = 4 + 11 - - a 加州一 ( 1 - a 加肛 ，= k + 1o。 k 埘 一 一 2 k 甜 一 p x ，( 6 ，l o ) 厶 厶 p 以+ q 仁+ 1 ) 一，p ，厶) + q 仁) 】= p ( l + q ( 三+ 1 ) 以，p ，1 ) 邑+ q ( 三) ) p ( 厶：1 ) + + p ( 以+ q ( + 1 ) ，( 6 ，l ：一1 ) 以+ q ( l ) ) p ( 厶= 厶一1 ) = 1 - a z + 。) 2 。1 劳+ 訾+ + 掣】 此即为( 1 ) 式。同理可证引理2 2 中的( 2 ) 和( 3 ) 。 当效为等概率取值时且口p k = 1 】= p k = 2 】= = 尸匕= 厶一1 】= 古时 p 【x 。+ q ( 2 ) z ，( 6 ，工。) x 。+ q ( 1 ) 】= 厶1 - 一a 2 1 ( 、1 2 1 ) p t + q ( 3 ) z 。，( 6 ，) s x 。+ q ( 2 ) 】2 工1 ：- 一a 3 1 ( 、1 2 2 ) p 队z 。m 。) z 。+ q ( ：一1 ) 卜百1 - - a t 【, 1 - - 2 - l + 1 ) p m ) 2 t 】- 再1 ( 1 。) p i x , - r ( 妒) z 。札) g 】2 丢( 1 _ 2 _ ) p x , - r ( 1 ) z 。( 6 ，工- ) z r ( 2 ) = 厶a 一21 ( 、1 2 一) 由上式可知，交叉变化后，子代并不服从均匀分布。当固定点：的位置取得较大时， x 。，( 6 ，。) 取x 。的概率较大，此时，经交叉后，未发生变化，这与交叉算子应具有全 局搜索能力的初衷相违背，也必将导致早熟现象，将不利于寻优。 第二章遗传算了的性质分析 ( 2 ) 经交叉操作后，子代服从均匀分布所需满足的条件 定理2 4 ：对于两点交叉算子，若交叉位为，工：，其中：为固定位，如果交叉算子服从 均匀分布，其充分必要条件是p k = 1 】= i 2 ，p 也= 2 】= = p l 。- l ：- 1 】2 亡 证( 充分性) 对于 a - - - a l 口：，不妨设f 1 ，屯t 一，是1 ，2 l 2 1 的某一个排列，且该排列满足： o 1 ，t 时，吒= o 2 。当工& + 2 一t 一。 时，口= 1 为了叙述方便，且又不影响证明，可设： 【1 ，2 七) 时，口。+ 。= o ；l k + 1 ，七+ 2 ，厶一1 ) 时，口。+ 。= 1 将p 峙1 】= 2 ，= 2 】= = p 。= 酬= 三l 2 代入引理2 2 中得： p q ( 2 ) “m 。) x 。+ q ( 1 ) 】= i 1 p 【置+ q ( 3 ) “批) x + q ( 2 ) 】= i 1 p 啄z 批) x 。+ q ( 厶一1 ) 】- i 1 帆( 6 ，) 一】_ i 1 p i x a - r ( ：一1 ) x 批) x 。】- i 1 p i x a - r ( ，) “批) x - r ( 2 ) 】- i 1 故由上式可知，交叉变化后的子代服从均匀分布。 p x z 。，0 ，。) s x 。+ q ( 七) 】 亦即： 2 。掣甜4 ( 掣+ 訾) = 一1 ( 掣+ 掣一掣】上述共( k - 1 ) 个等 式。 2 1 p x 。一r ( 七+ 1 ) z ( 6 ，) 一一r ( 七+ 2 ) 】= p 【z 一只( 七+ 2 ) 工，( 6 ，工，) s 一一足( 七+ 3 ) 】= ： p x + r ( ：一1 ) 一，( 6 ，工，) x 。】 亦即： 扩川。【 p l = 1 】 2 i ，。 一萼掣卜肌2 j - 1 ( 掣一掣】= = 2 t , - ( t , - 0 - 1 掣一 p k = 厶一1 】 2 上述共( ：一k 一2 ) 个等式。 3 ) 2 工l 叫一 掣甜舢i ) - 1 ( 掣萼掣) p 【= 1 】= p 【厶= 2 】= = p 【= l 2 1 】，。尸【厶= f 】1 ，f 0 , 2 工：一1 5 ) 2 + - ! 坚 芋卫：! 坠l ；卫+ 蜊+ + ! 嶂! 1 2 1 12 l , 一12 l , 一22 由于1 ) _ 5 ) 共有 一1 ) + ( t 一七一2 ) + 1 + 1 + 1 ；工：个等式，而未知数的个数为( ：一1 ) ，则 需要考虑由1 ) _ 5 ) 构成的方程组的系数矩阵。 将上式1 ) - 5 ) 用 p 阮+ q ( 2 ) f ( 0 1 ) ，f ( 1 1 ) f ( 1 0 )( 1 ) 现在，设法引入误导g a 的条件。考虑4 个一阶模式的适应度，即： 厂( o 木) ，( 1 水) ，厂( 冰o ) ，厂( 木1 ) 。一阶模式的适应度等于其包含的所有二阶模式的适应度的 平均值，即有： ，( 0 木) ：地掣 ( 2 ) ，( 1 木) = 掣 ( 3 ) 仆。) = 坐学幽 ( 4 ) 仆1 ) = 掣 ( 5 ) 如果令包含全局的最优解f ( 1 1 ) 的一阶模式的适应度小于不包含最优解的一阶模式 的适应度，即： 1 4 第二章遗传算了的性质分析 ，( o 木) 厂( 1 木) ，厂( 卑o ) ，( 爿c 1 ) 岫2 h 6 ) 有掣 掣 ( 6 ) ( 7 ) ( ! ：旦) ( 竺：旦! ! ( 里：! ) ! ! 兰! ! ( 8 ) 2 2 式( 7 ) 和( 8 ) 给出所谓的欺骗条件同时可以看出，式( 7 ) 和( 8 ) 并不能同时成立，否则就有 f ( o ，0 ) ，g 1 ) ，从而违背了，q 1 ) 是全局最优解的假设为此，不妨假定式( 7 ) 成立由此， 通过一个全局条件厂g 1 ) 为全局最优值和一个欺骗条件，( 0 木) ，( 1 宰) 就确定了一个欺骗 问题。将上述各适应值按f ( o ，0 ) 进行规一化处理如下： 致。 r = ，( 0 0 ) c = 巾( 0 。) c ，= m ( 0 0 ) 则全局条件式( 1 ) 可以表示为： 剖 于是，欺骗条件( 7 ) 可以表示为 ， l + c c 7 由式( 1 。) 和( 1 1 ) ，可以推出c c ，t ，( o ，o ) f ( 0 , 1 )( c 1 ) 类型i i ： ， 1 ) f ( o ，o ) f ( o ，1 ) f ( 1 , 0 )( c 1 ) 现在仅针对类型i 给出的均匀分布对最小欺骗问题的应用，类型i i 的方法与之一 湖北人学硕l 上学位论文 取，l c ，i c 牢1 木木料木o 水为2 2 中固定父代的个体。让木木木1 水木冰术水1 ，i c 为与之交叉的个体， 由交叉的固定位选取可知，其交叉位只能为第一个确定位到第二个确定位的位置。而此 时进行交叉后，所生成的子代中枣木木1 牛，i c 水半冰0 牢和木，i c 丰1 宰木木宰木1 木的总数不变。 当木车术0 木料木木0 木与固定个体进行交叉时，其交叉方式与上述一致，则此时所生成 的子代中，l c 木木0 水，k 术水牢0 ，l c 和水斗水1 术木水：i c 卓0 ：l c 的总数亦不变。 当木木术0 木木木料1 ，i c 与固定个体进行交叉时，子代中木，i c 木1 ，i c 宰木木，l c l ，i c 和木木木0 木，l c ，l c 木：i 0 木 的个数增加，但木木木。木，i c ，i c 木木1 木和木木木1 ，l c 木宰木木。木的个数减少。此时，( 1 , 1 ) 增j j l ，虽然 ，( o ，o ) 也增加，但由于是按子代服从均匀分布的交叉进行的，所以，整体厂( l 1 ) 的增加 幅度大于厂( o ，0 ) 。又厂( o ，1 ) 和f ( 1 , o ) 同时减少，而由欺骗问题中，( o ，1 ) fo , o ) ，当两 者均减少时，所产生的欺骗条件上垒掣 互坠掣必将遭到破坏，从而 克服最小欺骗问题。另一方面，由于，q 1 ) 是最优解模式，而子代服从均匀分布后，其 在群体中的适应值的比例将增加，这样对加速寻优是有帮助的。 类型i i 的欺骗问题讨论与上述类似。 2 4 小结 交叉算子与变异算子是遗传算法中两类较为重要的算子，交叉算子应具有全局搜索 能力，而变异算子不仅具有全局搜索能力，还具有局部搜索的能力。本章以两点变异和 两点交叉变异为例，分析了若给定的变异点与交叉点都是随机等概率选取时，其生成的 子代并不服从均匀分布，并可能产生早熟现象。提出若变异算子满足定理2 1 的条件时， 其变异后产生的子代服从均匀分布，从而具有全局的搜索能力，而交叉算子满足定理2 4 时，其子代也服从均匀分布，它的全局搜索能力加强，从而大大提高了遗传算法的全局 收敛性。 1 6 第三章群体多样性分析 第三章群体多样性分析 在寻优的过程中，如果用传统的遗传算法就会产生早熟的现象矧，而种群的多样性 能为克服这种现象的产生带来方便，目前衡量种群的多样性有很多方法【2 9 , 删，而且，遗 传算法主要是以遗传操作作为进化手段的，因此，对遗传算子的分析1 3 1 , 3 2 】也就显得尤其 重要。 本章着重以二进制编码为基础，引进衡量种群多样性的混合方法，并分析了遗传算 子若在单独使用的情况下，对上述混合方法有何影响，最后提出了改进的方案。 3 1 群体多样性的简介 群体规模的确定受遗传操作中选择操作的影响最大。模式定理蚓告诉我们，若群 体规模为，则遗传操作可从这个个体中生成和检测出3 个模式，并在此基础上不 断地形成和优化积木块，直到找到最优解。显然，越大，遗传操作所运行的模式就越 多，生成有意义的积木块并逐步进化为最优解的几率就越高。换而言之，群体规模越大， 群体中的个体的多样性也就越高，遗传算法陷入局部解的概率就越小。所以，从考虑群 体多样性出发，群体规模应较大。但是，群体规模太大也会带来若干弊病：一是群体个 体生存下来的概率大多采用适应度比例的方法，当群体个体非常多时，少量的适应度很 高的个体将会被选择而生存下来，但大多数个体被淘汰后，这将影响配对库的形成，从 而影响交叉操作；另一方面，群体规模太小，会缩小遗传算法的搜索空间范围，从而搜 索有可能停止在未成熟的阶段，引起早熟现象。二是从计算效率着眼，群体越大，其适 应评估次数增加，而计算量也将增加，从而影响算法效能。显然，要避免早熟现象的产 生，必须保持群体的多样性。 3 2 多样性的几种描述 设第f 代种群的个体为置= ( 五，五2 ，五) ，个体长度为l ，种群个数为，用矩阵 具体表示： 1 7 湖北大学硕卜学位论文 x t = t 1 11 2 2 12 2 x t l 2 n f t 工1t 2工 其中每一列对应一个个体。 定义3 - 1 ：记= 专豁川坛， ，f 眇。埘由此定义第佩种群的方差为： q = ( d r ( 1 ) ，p ( 2 ) ，b ( ) ，其中d f ( f ) = 万1 备mi 一可) 2j f 札2 ，) 。 从定义3 1 可以看出：方差d f 是维分布的行向量，每一个分向量表示种群在这坐 标系上的空i 司分布，d t ”越大，种群在第1 维坐标上的空间分布就越大。 对二进制这种特殊的编码而言，由于基因座所含1 的个数与种群个数n 的关系，可 作如下定义： 定义3 2 ：设鸭o ( 1 ) ：壹，札2 ，) ；啊p ( 0 ) ：壹( 1 一矽) ，仙2 ，) 。称鸭p ( 1 ) ，鸭( o ) 为t 代z 维基因座多样性。 显然，m y ) ( 1 ) 是表示f 代z 维基因座所含1 的个数，m t ，) ( o ) 是表示t 代，维基因座所含 0 的个数。由定义3 2 可得鸭( 1 ) + 鸭，) ( o ) = 。同时，鸭( ( 1 ) ，鸭f ) ( o ) 也可用于描述种群 多样性。在二进制编码中由于基因座的元素是1 和“0 ”，故在群体数n 取定后，在l 维中 只要已知，) ( 1 ) ( 鸭。( o ) ) 的数，就可确定另外o ( o ) ( n ，) ( 1 ) ) 的数。在理想状态下， r e ? l ( 1 ) = 鸭( o ) = 要是维持多样性的最优策略。但这样不易操作，因此可考虑取啊( 1 ) 或 m t ( 0 ( 。) 中的一个为代表，将其区间化，不妨设( 1 ) 取为代表，将( 1 ) 譬，等1 ，此时 m 0 ( o ) 巨抖 定理3 1 ：对上述记号q ( n ，m t ，) ( 1 ) ，d l 。) 是关于( ( 1 ) 的单调减函数。 证明：由q p 的定义可知： 1 8 第三章群体多样性分析 牡专黔司2 珊一赤卜+ ( 卜南h 一南卜十南】2 1 上式有珊，个( 1 - 南 2 和一个( 南】2 。若记埘科) ( 1 ，则有： 口( f ) = 专【优 - 一爿2 + ( 一肌，( 三) 2 】= 专【妻+ 埘一2 ) = 二1 亍+ 詈一号 现考虑函数，( x ) = 7 1 + 专一万2 ，对，( 工) 两边求导得： ，7 ) = 一i 1 + 万1 一- n 胁+ x 一 o 。故d | 是关于鸭f ) ( 1 ) 的单调减函数。 由定理3 1 可得：d f ( f 只是衡量f 维空间的离散程度，并不能完全衡量f 维空间的多 样性。但是用d i ( 1 )作为收敛性的判别依据，即当那达到最大值或最小值时，对应的z 维 基因座上的值取1 或o 。此时与基因座向最优化个体逼近是相符合的。当群体中的染色 体逐步向最优个体靠近时，d f ( f 或为单调减，或为单调增，此时取决于最优个体，维基因 座上的值，当( i ) 最优个体z 维基因座上的值为l 时，则d f 单调减：( 2 ) 最优个体f 维 基因座上的值为0 时则d f “) 单调增。 定理3 2 - 设优化问题的最优个体为x ，不妨设x 幸= “，c ：，气) 7 ，c ，= o 或1 g 2 ，l ， 则当群体收敛到最优值时，若c j = 1 时，则d