（基础数学专业论文）分区域隔离小生境遗传算法及其在多峰函数极值问题中的应用.pdf

东北大擘硕士擘住论文 摘要 分区域隔离小生境遗传算法 及其在多峰函数极值问题中的应用 摘要 遗传算法是一种新兴的求解优化问题的全局优化概率搜索算法，它是根据达尔 文的生物进化论、孟德尔的遗传学以及摩尔根的基因学说，对自然界中遗传和变异 现象的模拟遗传算法的思想最早由h o l l a n d 教授在二十世纪6 0 年代提出，经过4 0 多年的发展，它的理论体系已相对完善 函数优化是遗传算法的经典应用领域，常用于评价遗传算法的性能遗传算法 具有较强的鲁棒性，可以解决多领域的实际问题 基本遗传算法在求解优化问题时容易出现。早熟”现象，其主要原因是群体中 基因多样性的缺失，而且基本遗传算法通常只能找到一个最优解， 隔离小生境遗传算法是引入生物界中的地理隔离概念所产生的对基本遗传算 法的改进算法，它可以有效地抑制“早熟”，以其独有的特性被广泛应用于众多领域， 对工程领域中存在的大量的复杂函数的优化闯题具有重要的应用价值 基于隔离小生境遗传算法，我们提出分区域隔离思想以及种群密度的概念，给 出分区域隔离技术以及分区域隔离小生境遗传算法该算法实现了遗传算法操作技 术的突破，具有很强的收敛性对可行解。区域”形成具有“地理隔离”意义的小生 境，保证了群体的多样性，抑制了“早熟”，保证锝到更多的最优织及解的质量，父 代不参与子代的竞争，可以有效避免近亲繁殖，保证群体的多样性，抑制“早熟” 我们将分区域隔离小生境遗传算法应用到多峰函数优化问题上，对许多多峰函 数进行仿真实验，结果表明：采用了分区域隔离技术的小生境遗传算法不仅能保证 群体的多样性，有效抑制。早熟”，而且搜索速度以及收敛速度有很大的提高，最优 解也具有更高的精度 分区域隔离小生境遗传算法特别适合求解低维函数优化问题 关键词：遗传算法；小生境；隔离技术；种群密度；多峰函数； 东北大擘硕士擘住论文 a b s t r a c t n i c h eg e n e t i ca l g o r i t h mb a s e do nd i v i d e d a r e a ss e g r e g a t i v et e c h n i q u ea n di t sa p p l i c a t i o ni n e x t r e m u m - v a l u ep r o b l e mo fm u l t i p l eh u m pf u n c t i o n a b s t r a c t g e n e t i ca l g o r i t h m s ( g a ) i sak i n do fn o v e lg l o b a lo p t i m i z a t i o ns t o c h a s t i cs e a r c h i n g a l g o d t h nt os o l v et h eo p t i m i z a t i o np r o b l e m s i ti m i t a t e sh e r e d i t ya n dm u t a t i o no f s p e c i e si n n a t u r a la c c o r d i n gt oe v o l u t i o n a r yt h e o r yp r o p o s e d b yd a r w i n ，g e n e t i c s p r o p o s e db ym e n d e la n dg e n e t i cd o c t r i n ep r o p o s e db ym o r g a n t h ei d e ao fg a w a sf i r s t p r e s e n t e db yh o l l a n di n1 9 6 0 s f o r4 0y e a r si t h a sb e c o m ear e l a t i v ep e r f e c tt h e o r y s y s t e m f u n c t i o no p t i m i z a t i o np r o b l e mi sat y p i c a ld o m a i ni ng a sa p p l i c a t i o na n di ti sa l s o u s e dt ot e s tt h ep e r f o r m a n c eo ft h eg a g ah a sb e e na b r o a da p p l i e di nm u l t i p l ed o m a i n s w i t hi t ss t r o n gr o b u s t s i m p l eg e n e t i ca i g o d t h m ( s g a ) i sp r o n et oc o n v e r g ep r e m a t u r e l yb e f o r et h eb e s t s o l u t i o nh a sb e e nf o u n dw h e nu s e df o ro p t i m i z a t i o np r o b l e m s t h em a i nr e a s o no f p r e m a t u r ec o n v e r g e n c ei st h el o s so fg e n e t i cd i v e r s i t yi nt h ep o p u l a t i o n m e a n w h i l e ，t h e s g a u s u a l l yc a nf i n do n l yo n es o l u t i o n i s o l a t e dn i c h eg e n e t i ca l g o f i t l u n ( i n g a ) i st h ei m p r o v e da l g o r i t h mo ft h es g a t h ec o n c e p to fg e o g r a p h i cs e g r e g a t i o ni si n t r o d u c e di n t ot h ei n g a i tc a np r e v e n t p r e m a t u r ec o n v e r g e n c ee f f e c t i v e l ya n db eu s e di nm a n yd o m a i n sb e c a u s eo fi t ss p e c i a l f e a t u r e s i th a sa ni m p o r t a n ta p p l i c a t i o nv a l u et ol o t so fo p t i m i z a t i o np r o b l e m so f c o m p l e xf u n c t i o n se x i s t e di ne r i g i n c c r i n gd o m a i n b a s e do nt h ei n g a , i nt h i sp a p e r , w ep u tf o r w a r dan e wi d e ao fd i v i d e da r e a s s e g r e g a t i v ea n d t h ec o n c e p to ft h ed e n s i t yo fa p o p u l a t i o n w ep r o p o s et h ed i v i d e da r e a s s e g r e g a t i v et e c h n i q u ea n dt h en i c h eg e n e t i ca l g o r i t h mb a s e do nd i v i d e da r e a ss e g r e g a t i v e t e c h n i q u e ( d a - s n g a ) t h i sa l g o r i t h i nr e a l i z e s ak i n do fi n n o v a t i o no f o p e r a t i o n t e c h n i q u ei ng e n e t i ca l g o r i t h ma n di th a ss t r o n gc o n v e r g e n c e an i c h ew h i c hi sg e n e r a t e d 东北大学硕士学住论文a b s t r a c t t h r o u g hd i v i d i n gt h ep r o b a b l es o l u t i o ns p a c es h o w st h er e a lm e a n i n go fg e o g r a p h i c s e g r e g a t i o n d a - s n g am a i n t a i n st h ed i v e r s i t yo ft h ep o p u l a t i o na n dp r e v e n t sp r e m a t u r e c o n v c r g e u c e w e 啪o b t a i nt h em 跖yo p t i m a ls o l u t i o n sa n db e t t e rq u a l i t yo p t i m a l s o l u t i o n sb yu s i n gt h i sa l g o r i t h mt os o l v et h eo p t i m i z a t i o np r o b l e m s t h ei n d i v i d u a l si n t h ep o p u l a t i o nd o n tc o m p e t ew i t ht h e i rc h i l d r e n ，w h i c ha v o i dp r o p a g a t i o ni ns i m i l 暂 i n d i v i d u a l s , s om a i n t a i nt h ed i v e r s i t y o ft h e p o p u l a t i o na n da v o i dp r e m a t u r e c o n v e r g e n c e w ea p p l yt h ed a s n g at ot h co p t i m i z a t i o np r o b l e m so fm a n ym u l t i p l eh u m p f u n c t i o n s 柚dd om a n yi m i t a t i v ec x p a r i m e n t sw i t hc o m p u t e ra n d 湖p a r et h er e s u l t s w i t ht h eo t h e rp a p e r s c o m p u t a t i o n a lr e s u l t ss h o wt h a tt h ed a s n g ai sc a p a b l eo fn o t o n l ym a i n t a i n st h ed i v e r s i t yo ft h ep o p u l a t i o n ，b e ta l s oa v o i d sp r e m a t u r ec o n v e r g e n c e i t ss p e e d i n go fc o n v e r g e n c ei sf a s t e ra n dt h eq u a l i t yo fs o l u t i o n si sh i g h e rt h a no t h e r p a p e r s t l h cd a - s n g ai sf nt ot h eo p t i m i z a t i o np r o b l e m so fl o w d i m e n s i o nf u n c t i o n k e yw o r d s ：g e n e t i ca l g o r i t h m ；n i c h e ；i s o l a t e dt e c h n i q u e ；t h ed e n s i t yo f ap o p u l a t i o n ； m u l t i p l eh u m pf u n c t i o n 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人已经发表或撰写 过的研究成果，也不包括本人为获得其他学位而使用过的材料与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示谢意 学位论文作者签名： 百移 日期：刎，2 。 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位 论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许论文被查阅和借阅本人同意东北大学可以将学位论文 的全部或部分内容编入有关数据库进行检索、交流 学位论文作者签名： 研私 日 期：拍砂，2 t 意 另外，如作者和导师不同意网上交流，请在下方签名；否则视为同 学位论文作者签名：1 佛 签字日期：皇重量 c = = = ， 导师签名：多长希瑟 、， 、 签字日期：匝 愉 东北大擘硕士学位论文 第一章引言 第一章引言 1 1 遗传算法产生的生物学背景 地球上的生物大约起源于3 8 亿年前最早的生物是原核生物经过漫长的历 史过程，原核生物才逐渐演变和进化成具有复杂细胞结构的现代生物生物进化论 认为，地球上最早的生命物质是由非生命物质转化来的，现在生存的各种生物有着 共同的祖先在生物的进化过程串，生物的种类由少到多，生物的结构和功能从简 单到复杂、从低级到高级演变【1 h 2 i 1 8 5 9 年，达尔文在物种起源一书中提出生物进化理论，其核心思想是。自 然选择，适者生存”。所谓“自然选择，适者生存”是指在复杂的生存环境下，具有 较强生存能力的生物个体容易存活下来，繁殖的机会越来越多；薅具有较低生存毙 力的生物个体则逐渐被淘汰，直至消亡达尔文的生物进化理论主要包括三个方面 的内容：一是遗传，父代把生物信息传递给子代，子代继承父代的信息后发育、分 化，形成与父代具有相同或相似性状的个体，遗传是生物具有的普遍特征，生物的 这一特征使得物种稳定存在二是变异，父代与子代之间总是存在一些差异变异 是随机发生的，变异的选择和积累是生命多样性的根源三是自然选择，适者生存 在自然选择过程中，弱肉强食的生存斗争在不断进行，其结果是生命力较强的生物 个体被保留下来，而那些生命力较弱的生物个体则被淘汰达尔文的生物进化理论 是生物学史上的一个里程碑，是现代生物进化学说的理论基础，它觞释了自然选择 作用下生物的渐变式进化 。 达尔文认为，在生存环境的选择作用下，物种变异沿着适应环境的方向进化， 形成不同于祖先的性状，演变为新的物种这种自然选择过程是一个长期的、缓慢 的，连续的过程 俗话说，。种瓜得瓜，种豆得豆”，这是遗传规律在起作用1 8 6 6 年，奥地利生 物学家、经典遗传学奠基人孟德尔在“植物杂交实验”论文中，提出遗传学的两个 基本定律：遗传因子的分离定律和自由组合定律，奠定了现代遗传学的基础盂德 尔通过对遗传现象的研究及大量实验，总结出颗粒性遗传观念他认为遗传是由粒 1 一 东北大学硕士学位论文第一幸引言 子性遗传因子决定的，双亲的相对性状的决定者在子代处于杂合状态中是彼此独立、 互不干扰、互不沾染的成对的因子既可通过杂交结合在一起，在杂种形成生殖细 胞时又可以分离开来，不同对的因子还可以进行自由组合，正因如此，生物才具有 稳定遗传和发生变异的特征孟德尔的颗粒性遗传观念，把粒子遗传理论推向了一 个新阶段孟德尔所提出的遗传因子只是一种逻辑推理的产物，作为一种遗传性状 的符号并没有任何物质内容后来，随着遗传学的发展，遗传因子的概念被我们现 在所使用的基因的概念所代替，并且赋予了新的形式和内容 美国遗传学家摩尔根在孟德尔的遗传学基础上，进一步确立了基因学说，他认 为遗传性状是由基因决定的，染色体的变化必然在遗传性状上有所反映，生物的形 状不是简单地由单个基因决定的，而是不同基因相互作用的结果，基因表达要求一 定的环境条件，同一基因型在不同的环境条件下可以产生不同的表现型 随着遗传学理论的发展，科学家们不断地利用新的理论成果来解释达尔文的自 然选择学说，种群遗传学就是其中之一种群遗传学是以种群为单位，研究种群中 基因的组成及其变化的生物学种群遗传学认为，生物的进化实质上是种群的进 化在一定地域中，种群是由一个物种的全体成员构成的，种群的基因库受个体基 因型变化的影响，个体在多变的环境下，经历着生死存亡的过程，旧个体的消亡， 新个体的出现，使得种群的基因型发生改变，这一过程就是种群的进化过程 遗传算法( g e n e t i ca l g o r i t h m s ，简称g a ) 是由美国m i c h i g a n 大学的j h h o l l a n d 教授及其学生根据达尔文的生物进化论、盂德尔的遗传学和摩尔根的基因学说，模 拟生物在自然环境中的遗传和进化过程，创立的一种自适应全局优化概率搜索算 法他们利用编码技术用二进制数串表示染色体，并将这些数串有组织地、随机地 交换来模拟生物进化过程，重新组合成适应性好且具有优良性状的染色体新数串， 或者是在数串结构中用新的数串片段来替代原来的部分，形成新的染色体数串群体 1 2 遗传算法的发展历程及其在我国的发展状况 遗传算法一问世便引起了广大学者的关注，在之后的几十年里得到迅速发展， 现已形成比较完善的理论体系遗传算法的发展大致经历了以下三个阶段。 1 起步阶段( 2 0 世纪6 0 7 0 年代) 2 东北大学硕士擘住论文第一章引言 1 9 6 2 年，h o l l a n d 教授在“o u t l i n e f o ra l o g i c t h e o r y o f a d a p t i v es y s t e m s ”一文中 首次提出监控程序的概念，即利用群体进化模拟适应性系统的思想尽管当时他没 有给出实现这一思想的具体技术，但却引进了群体、适应值、选择、变异、交叉等 基本概念1 9 6 7 年，h o l l a n d 教授的学生j d b a g l e y 在其博士论文中首次提出“遗 传算法”一词，并发表了遗传算法应用方面的第一篇论文1 9 7 5 年。h o l l a n d 教授出 版了第一本系统论述遗传算法和人t 自适应系统的专著自然与人工系统中的自适 应性该书系统地阐述了遗传算法的基本理论和方法，提出了遗传算法的基本定 理模式定理( s c h e m a t h e o r e m ) ，首次确认了选择、交叉和变异等遗传操作，以 及遗传算法的隐并行性，并将遗传算法应用于适应性系统模拟，函数优化、机器学 习、自动控制等领域，为遗传算法的发展奠定了坚实的基础同年，美国的d ej o n g 在其博士论文。a 丑a n a l y s i so ft h eb e h a v i o ro fuc l a s so fg e n e t i ca d a p t i v es y s t e m s ”中 首次把遗传算法应用于函数优化问题，并对遗传算法的机理与参数设计问题进行了 较为系统的研究，同时深入全面地研究了模式定理和遗传操作的行为，将其与实验 相结合，建立了著名的d ej o n g 五函数测试平台另外，d j c a v i c c h i o 在其博士论 文中将基于整数编码的遗传算法应用于模式识别问题，研究了保持群体差异性的选 择策略 2 发展阶段( 2 0 世纪8 0 年代) 2 0 世纪舳年代，h o l l a n d 教授建立了第一个基于遗传算法的机器学习系统分 类器系统( c l a s s i f i e rs y s t e m s ) ，为分类器的构造提出了一个完整的框架，开创了基 于遗传算法的机器学习的新概念1 9 8 眸，s m i t h 首次提出使用变长位串的概念， 在某种程度上为日后的遗传规划奠定了基础；b e t h k e 对函数优化遗传算法进行了研 究，包括应用研究和数学分析同时，g o l d b e r g 、d a v i s 、g r e f e n s t e t t e 、b a u e r 、s r i n i v a i 和p a t n a i k 等一大批人对遗传算法理论的基本框架和遗传操作进行构建和改进，并 将遗传算法分别应用于工程设计、自动控制、经济金融、博弈问题、机器学习等诸 多领域，1 9 8 9 年，g o l d b e r g 出版了遗传算法的第一本教科书搜索、优化和机器学 习中的遗传算法该书对当时遗传算法领域的研究工作做了全面而系统的总结，给 出了遗传算法的许多应用实例和大量可以使用的应用程序同年，j r k o z a 教授首 次提出染色体结构的树状表示方法，把染色体表示为随环境变化的动态变化层次结 3 - 东北大擘硕士学位论文第一幸引言 构，使得对问题的表示更加自然准确 3 商涨阶段( 2 0 世纪8 0 年代末至现在) 2 0 世纪8 0 年代中后期以来，遗传算法和进化计算蓬勃发展以遗传算法、进化 计算为主题的国际会议在世界各地定期召开1 9 8 5 年，在美国召开了第一届遗传算 法国际会议，即i c g a ( i n t e r n a t i o n a lc o n f e r e n c eo ng e n e t i ca l g o r i t h m ) ，这次会议是 遗传算法发展的重要里程碑，此会以后每隔一年举行一次以遗传算法理论基础为 中心的学术会议f o g a ( f o u n d a t i o no fg e n e t i ca l g o r i t h m ) 从1 9 9 0 年起每踽一年举办 一次世界上第一本关于人工智能研究的杂志a it r e n d s 于1 9 9 3 年更名为c r i t i c a l t e c h n o l o g yt r e n d s ，在更名启事中指出“遗传算法、自适应系统、细胞自动机、混 沌理论和人工智能一样，都是对今后十年的计算机技术有重大影响的关键技术” 1 9 9 1 年，d a v i s 出版了遗传算法手册，书中包括了遗传算法在工程技术和社 会生活中的大量应用实例k o z a 教授提出遗传规划( g e n e t i c p r o g r a m m i n g ) 的概念， 并于1 9 9 2 年出版了第一本遗传规划专著g e n e t i cp r o g r a m m i n g , o nt h ep r o g r a m m i n g o f c o m p u t e r sb ym e a n so f n a t u r a ls e l e c t i o n ，两年后他又出版了第二本关于遗传规划 的专著( g e n e t i cp r o g r a m m i n gi i ，a u t o m a t i cd i s c o v e r yo fr e u s a b l ep r o g r a m s ) ) 此外，许多世界知名的学术机构都在进行遗传算法及相关方面的研究唧 美国乔治马松大学遗传算法研究组主要研究协同进化遗传算法、并行遗传算 法、遗传机器学习以及遗传算法分析美国伊利诺斯遗传算法实验室主要从事遗传 算法的理论与应用研究美国密歇根州立大学遗传算法研究与应用组主要研究遗传 算法、复杂自适应系统及人工生命英国布鲁内大学计算机神经和进化系统研究中 心主要从事神经网络、遗传算法、遗传程序设计、人工生命、自适应系统等应用研 究英国谢费尔大学自动控制系统工程系主要研究多目标遗传算法在生产调度、控 制系统设计等领域的应用澳大利亚公益科学和工业科学组织信息技术部高性能计 算项目组主要研究并行遗传算法及时问表问题荷兰利穆伯格大学知识系统研究所 主要从事协同进化遗传算法、约束满足问题、过程控制方面的研究西班牙格兰拉 达大学计算机与人工智能系主要研究进化系统与模糊逻辑的融合阿根廷布诺斯爱 丽斯大学进化计算研究组主要从事进化计算、复杂自适应系统、经济学、分布式遗 传机器学习等方面的研究日本名古屋大学信息电子学系在遗传算法及模糊控制方 4 东北大学硕士学位论文第一章 l 言 面有所研究 我国对遗传算法、进化计算的研究起步较晚，但自上世纪9 0 年代以来，有关遗 传算法、进化计算方面的研究也取得了举世瞩目的成果，不仅出版了一些专著，而 且在国内外刊物上发表了大量论文其中专著有刘勇、康立山，陈毓屏等人于1 9 9 5 年出版的非数值并行算法( 第二册) 遗传算法 ；陈国良、王煦法等人于1 9 9 6 年出版的 c 。 其他 这种方法有时存在界限值预先估计困难、不可能精确的问题 在遗传算法中，适应度函数的设计与选择对遗传算法的性能有较大影响在进化的 初期，通常会产生一些超常个体。若按照比例选择法，这些超常个体因竞争力太强而控 制了选择过程，从而影响算法的全局优化性能在进化的后期，算法接近收敛时，种群 中的个体适应度差异变小，使得继续优化的潜能下降，可能导致获得的只是局部最优解， 这通常称为遗传算法的欺骗问题因此，有时在遗传算法运行的不同阶段需要对个体的 适应度进行适当的扩大和缩小 1 2 东北大学硕士学位论文第二章遗传算法 步骤三初始化群体 产生初始种群的方法通常有两种：一种是完全随机产生，它适合于对问题的解无任 何先验知识的情况；另一种是将先验知识转变为必须满足的某种要求，然后在满足这些 要求的解中再随机地选取样本，这样选择的初始化群体可以加快达到最优解的速度 步骤四群体规模设定 群体规模是指群体中所包含个体的数量群体规模越大，含有的模式越多，越能有 效防止“早熟”但是，群体规模过大，会使搜索空间增大，从而降低收敛速度 基本遗传算法所取的群体规模一般为2 0 1 0 0 步骤五遗传操作 基本遗传算法使用三种基本遗传操作：选择、交叉、变异 i ) 选择操作 选择又称为复制，是从当前群体中选择出适应值高的个体组成新的群体，以进行交 叉和变异操作从生物学角度讲，选择过程体现了生物进化过程中“适者生存，优胜劣 汰”的思想，保证了优良基因能够在下一代中得以保留选择操作的好坏，直接影响到 遗传算法的计算结果选择操作不当，一方面会造成群体中相似个体增加，导致进化停 滞不前；另一方面，适应度偏大的个体会误导群体进化方向，导致“早熟” 年 遗传算法中常用的选择方法主要有：适应度比例选择、b o l t z m a n n 选择、排序选择、 联赛选择和最优个体保存策略等 基本遗传算法采用适应值比例选择方法 i i l 交叉操作 交叉是指生物在自然进化过程中，两个同源染色体通过交配、重组形成新的染色体， 从而产生出新的个体或物种遗传算法中的交叉是指对两个相互配对的。染色体”按某 种方式相互交换部分“基因”，从而形成两个新的个体 交叉操作是遗传算法的独有特征，也是遗传算法区别于其它进化算法的重要特征， 它在遗传算法中起着关键作用，是产生新个体的主要方法 不同的编码方法应采用不同的交叉方式对实数编码来说，交叉方式有离散重组、 中问重组、线性重组等形式对二进制编码来说，交叉方式有单点交叉、多点交叉、均 1 3 东北大学硕士学位论文第二章遗传算法 匀交叉等形式除此之外，还有部分匹配交叉、顺序交叉、循环交叉、洗牌交叉、缩小 代理交叉等形式 基本遗传算法使用单点交叉方式 i i i ) 变异操作 遗传算法中的变异操作是对自然界生物进化过程中染色体上基因位发生的突变现象 的模拟变异操作改变了染色体的结构和物理性状，它将个体的染色体编码串中的某些 基因位的基因值用其它等位基因的基因值来替换，形成新的个体例如：对采用二进制 编码串的个体进行变异操作时，只需将选定的基因位的基因值取反即可 在遗传算法中使用变异操作即能改善遗传算法的局部搜索能力，又能维持群体的多 样性，防止“早熟”现象的发生 遗传算法的变异操作一般有基本位变异、均匀变异、边界变异、非均匀变异及高斯 近似变异等形式 基本遗传算法使用基本位变异操作或均匀变异操作 步骤六终止条件 由于遗传算法是一个迭代的过程，因此在进化过程中要给出终止准则一般采用设 定最大进化代数的方法来终止进化过程，该方法简单易行，但准确率较差其次，可以 根据群体的收敛程度来判断，通过计算种群中的基因多样性测度，即所有基因位的相似 程度来控制进化过程第三，根据算法的离线性能和在线性能的变化进行判定第四， 在采用精英保留选择策略的情况下，根据每代最佳个体的适应值变化情况来确定 基本遗传算法采用设定最大进化代数的方法来终止进化过程，一般取最大进化代数 为1 0 0 - - 5 0 0 步骤七控制参数的选择 基本遗传算法运行前，除了群体大小以及最大进化代数需要预先给定以外，还有交 叉概率见和变异概率p 一等两个参数也需要预先给定交叉概率控制着交叉操作中交叉 算子的应用频率交叉概率越高，群体中新结构的引入越快，同时已获得的优良基因结构 丢失的速度也越快；交叉概率太低则可能导致搜索停滞不前变异概率的取值不易过大， 变异概率大于0 5 遗传算法将退化为随机搜索算法基本遗传算法的交叉概率一般取为 1 4 东北大学项士学位论文第二章遣传算法 0 4 0 9 9 ，变异概率一般取为0 0 0 0 1 0 1 所有参数的选择对算法的性能有很大影响参数的选择与问题的类型有关问题越 复杂，参数的选择就越困难从理论上讲，不存在一组适用于所有问题的最佳参数值， 随着问题特征的变化，有效参数的差异往往非常显著 如何设定控制参数以改善算法的性能，有待进一步深入探讨和研究 3 基本遗传算法的缺陷 基本遗传算法的缺陷：收敛速度慢，稳定性差；在进化过程中，易陷入“早熟”， 不能保证收敛到全局最优解在求解多峰函数优化问题时，由于二进制编码方法本身的 缺陷，使基本遗传算法无法求出满意的最优解 2 3 遗传算法理论 2 3 1 模式理论 遗传算法在机理方面具有搜索过程和优化机制的特征，其数学方面的性质是通过模 式定理和积木块假设加以分析和讨论的模式定理和积木块假设是解释遗传算法寻优原 理的较系统豹理论，被称为模式理论( s c h e m at h e o r y ) 1 模式定理 h o l l a n d 在早期研究中提出了模式的概念以及模式定理模式定理是遗传算法的基本 原理，从进化动力学的角度提供了能较好地解释遗传算法机理的数学工具，同时也是编 码策略、遗传策略等分析的基础 定义2 1 具有某些基因相似性或共同基因特征的个体组成的集合称为模式，通常 用h 表示 例如：模式o 1 ，这里第二、四位为确定位、第一、三位为不确定位( 可取o l 中的一个字符) ，描述的是以第二确定位取值为0 、第四确定位取值为1 的共同基因特征的 位串子集 o o o l ，0 0 1 1 ，1 0 0 1 ，1 0 1 1 ) f l y 2 2 模式h 中含有确定的基因位的个数称为模式的阶，记作d ( 日) 例如：0 ( 0 1 1 1 ) - 4 ，0 ( 0 ) - 1 1 5 ： 东北大擘硕士学位论文第二章遗传算法 模式的阶反映了不同模式问确定性的差异，模式的阶数越高，模式的确定性越高， 所能匹配的样本数就越少 定义2 3 模式h 中从左到右第一个确定位和最后一个确定位之间的距离称为模式 的定义距，也称定义长度，记作6 ( h ) 例如：模式0 1 1 * 1 的定义距为5 ，因为第一个确定位置为1 ，最后一个确定位置为6 ， 它们之间的距离6 ( 0 1 1 1 ) - 6 1 - 5 ；模式o 的定义距为o ，因为第一个确定位置 和最后一个确定位置都是1 ，它们之间的距离为6 ( 0 ) 1 10 在遗传算法中，即使阶数相同的模式，也会有不同的性质，而模式的定义距就反映 这一性质的差异 对于给定的模式，进行遗传操作后，模式一般会发生改变下面分别讨论选择、交 叉、变异等遗传操作对模式生存能力的影响 ( 1 ) 选择操作对模式生存能力的影响 设群体规模为n ，模式h 在第f 代群体4 ( f ) 中所包含的个体位串数量即生存数量为 m ( h ，f ) ，且在选择操作过程中个体q 按概率n - ，( q ) ：。f ( u j ) 被选择- ，那么在f + 1 代模式日的生存数量为 历( 巩h ( 儿。器， 其中，( 仃，, ) - 7 2 ，( 口伽，坍- m ( u ，f ) 为第f 代群体中的适应值估计 若令群体平均适应值为7 艺：。厂( q ) ，则上式又可表示为 用( 圳m ( 却) 掣 该式说明下一代群体中模式的生存数量与模式日在第f 代的适应值成正比，与群体平 1 6 东北大学硕士学位论文第二章遗传算法 均适应值成反比当，( 日，f 卜7 时，日的生存数量增加；当，( h ，f ) t 7 时，日的生存 数量减少群体中任一模式的生存数量都将在选择操作中按上式规律变化 ( 2 ) 交叉操作对模式生存能力的影响 交叉操作对模式日的影响与其定义距6 ( 日) 有关6 ( 日) 越大，模式被破坏的可能 性越大；反之，6 ( h ) 越小，模式被破坏的可能性越小 若染色体位串长度为，那么在单点交叉算子作用下模式8 的存活概率为 p ! 。，- 1 - 6 ( h ) ( l - 0 ； 而在具有交叉概率为见的单点交叉算子的作用下模式h 的存活概率有 p 。1 一( 6 ( ) ( 三一1 ) ) 见 基于( 1 ) 和( 劲在选择算子与交叉概率为见的交叉算子共同作用下模式日的生存数 量则有 。脚俾。t + 1 ) - m ( h ，1 ) ( ，限，f 汀) p 。叫 七册( 曰，t ) f ，( 抒，f 矿7 ) l p ( 舒) 伍一1 ) ) 见) 可见，在选择算子与交叉算子的共同作用下，模式生存数量的变化与其平均适应值 及其定义距密切相关当，( 日，) 7 且6 ( 打) 较小时，模式日的生存数量以指数规律 增长 c 3 ) 变异操作对模式生存能力的影响 假设变异操作是以概率几随机地改变同一等位基因，那么模式h 能在变异操作中 生存下来即所有确定位的等位基因均不发生变化的概率为( 1 一儿) 咖一般情况下 凡1 ，所以模式h 的生存概率可近似表示为l d ( 日) p 一 综合考虑选择算子、交叉算子及变异算子的共同作用，模式h 的生存数量近似地有 1 7 东北大学硕士学位论文第二幸遗传算法 m ( m ，- 1 ) 乏m ( x ，f ) ( ，( 日，f 厉) ( 1 一( 6 ( 日) 仁一1 ) ) p c ) ( 1 一d ( 日) p ) ， ( ) 若忽略高次极小项( 6 ( h ) ( 工一1 ) ) d ( h ) 见儿，式( ) 则变为 m ( h ，1 ) 研( 日，f ) ( ，( 圩，f ) 7 ) ( 1 一( 6 ( 日) 仁一1 ) ) 版一d ( 何) p 二) 通过分析三种遗传算子对模式生存数量的影响，可以得出下面的结论： 定理2 1 ( 模式定理)在遗传算子选择、交叉和变异操作的作用下，具有低阶、 短定义距以及超过群体平均适应值的模式，其生存数量将随着进化代数的增加以指数级 增长 模式定理在一定意义上解决了基本遗传算法的有效性问题，但它仍有以下缺点： i1 模式定理只适用于二进制编码，对其它编码方法尚没有相应的结论成立 n ) 模式定理只给出了在子代中包含模式h 的个体数的下限，无法据此推断算法的 收敛性 i i i ) 模式定理没有解决算法设计中控制参数选取等问题 2 积木块假设 在模式定理中所指的具有低阶、短定义距以及高于群体平均适应值的模式被定义为 积木块( b u i l d i n gb l o c k ) 假设2 1 ( 积木块假设)低阶、短定义距以及高于群体平均适应值的模式( 即积 木块) ，在遗传算子选择、交叉和变异操作的作用下，相互结合，形成高阶、长定义距以 及高于群体平均适应值的模式，最终生成全局最优解 模式定理说明遗传算法具备搜索到全局最优解的可能性，积木块假设则说明遗传算 法具备找到全局最优解的能力模式定理和积木块假设构成了关于遗传算法进化过程能 够发现最优解的一个充分条件 3 模式欺骗问题 在求解优化问题时，存在着一类用遗传算法难以求解的问题，称为。g a - 难”的问 题这类问题往往不满足积木块假设，即由积木块拼接后，往往会欺骗遗传算法，使其 进化过程偏离最优解，统称为遗传算法的模式欺骗问题 1 8 东北大擘硕士擘往论文第二章遗传算法 大多数实际优化闯题的目标函数属于非单调函数或多峰函数，所谓多峰函数是指具 有多个局部极大点的目标函数在搜索过程中，这类函数可能存在某些低阶模式难以重 组成所期望的高阶模式，或者更为严重的是低阶模式的重组引导搜索方向偏离全局最优 解，从而形成模式欺骗问题。 文献【5 】在对模式理论的收敛性分析的基础上得出结论：采用二进制编码求解单调函 t 数或单峰函数优化问题时遗传算法不仅满足模式定理，而且符合积木块假设；算法具有 强概率收敛性；在采用最优保留策略的情况下，随着迭代次数趋于无穷大，遗传算法将 以概率1 收敛于问题的最优解 2 3 2 遗传算法的收敛性 对于求解优化问题的任何搜索算法而言，其收敛性是至关重要的 1 遗传算法收敛性结论 这里给出有关遗传算法收敛性的重要结论 定义2 4 给定非空集合s 作为搜索空间，：s r 为目标函数，全局优化问题 警，( 工) ( 或嘧，i 工) a 的求解是指在搜索空间s 中寻找点矿s ，使v x e s 部有，( j ) ，o l ( 或 ，卜) 七l ( x ) ) ，罩称为全局极大点( 或全局极小点) ，函数值，b ) t + * 称为全局极 大值( 或全局极小值) 定义2 5 同用遗传算法求解问题( 2 1 ) ，设随机变量r m - m p z 一：正- ， 表示首 次击中全局极值点的时间，如果e rcm - 1 且与初始群体无关，则称遗传算法以概率1 在有限时间内访问到全局极值点 定义2 6 i 习对一个定义在概率空问( q ，a ，p ) 上的非负随机变量序列 邑，万- o , 1 ， j ) 称似) 完全收敛到o ，如果对v ，0 ，有e l p ( x ，) 收敛： 1 9 东北大学硕士擘位论文第二章遗传算法 i i ) 称 以) 以概率l 收敛到o ，如果对v e ，o ，有p ：船以( 珊) - 0 - 1 成立； i i i ) 称 墨) 依概率收敛到o ，如果对v ，0 有熙p 以( 珊卜) - o 成立 定义2 7 嘲用遗传算法求解问题( 2 1 ) ，称遗传算法完全收敛( 或以概率1 收敛，或 依概率收敛) 到全局极大值，如果由它所产生的非负随机变量序列( q ：l o ) 完全收 敛( 或以概率1 收敛，或依概率收敛) 到0 ，其中d | ，。一z ，z 是在第f 代时产生的 最优个体的适应值 在遗传算法运行过程中，通过交叉、变异等遗传操作可以不断产生新的个体，虽然 随着进化过程能产生大量优良个体。但是，由于选择、交叉、变异等遗传操作的随机性， 也可能破坏掉当前群体中的最佳个体，以至影响遗传算法的运行效率和收敛性为了将 优良个体尽可能地保留到下一代群体当中，可以采用最优保留策略，即把当前群体中适 应值最高的个体直接复制到下一代群体中，去替换经过交叉、变异操作后所产生的适应 值最低的个体，以实现优胜劣汰的选择机制采用最优保留策略是遗传算法收敛性的一 个重要保证条件 定义2 8 阁用采用最优保留策略的遗传算法求解问题( 2 1 ) ，称算法完全收敛( 或以 概率1 收敛，或依概率收敛) 于全局极大值，如果非负随机变量序列( 置：f 2 0 ) 完全 收敛( 或以概率1 收敛，或依概率收敛) 到0 ，其中五- f 一只，e 是在第f 代所保留的 最优个体的适应值 假设2 2 嘲在每一进化代f ，对群体p o ) 中的每个个体z p ( f ) 和任意的y s ，s 为搜索空间，如果石一y ，则通过变异算子的一次作用使得x 变异为y 的概率大于等于 p ( t ) ，其中p ( f ) 是一个可能与代数f 有关的大于。的常数 假设2 3 嘲在假设2 2 中。能找到一个常数p 缸o ，使得对所有的f ，都有p ( f ) 2 p 知 定理2 2 嘲当遗传算法的变异操作满足假设2 2 r 采用最优保留策略时，遗传算法 依概率收敛到问题( 2 1 ) 的最优解，且收敛性与初始群体无关当遗传算法的变异操作还 2 0 东北大学硕士学位论文 第二章连传算法 满足假设2 3 时，则遗传算法完全收敛于问题( 2 1 ) 的最优解 2 基本遗传算法。早熟”的原因 在应用基本遗传算法求解实际问题时，存在着并不总是收敛到全局最优解或满意解 的现象，这种现象被称为“早熟”或成熟前收敛这种现象的发生表现为群体中的各个 个体非常相似，群体的多样性急剧减少，当前群体缺乏有效等位基因，使得在遗传算子 作用下也不能生成具有竞争力的高