（水文学及水资源专业论文）免疫进化算法研究及其在水问题中的应用.pdf

免疫进化算法研究及其在水问题中的应用水文学及水资源专业博士研究生倪长健指导教师丁晶摘要进化算法作为解决复杂优化闯题的关键技术，世界各国对其进行了持续的研究，取得了丰硕的成果。本文在现有进化算法的基础上，作了进一步的研究工作，其涉及的主要内容有：1 本文较系统地介绍了进化算法的发展、基本原理、实现技术和应用，并就遗传算法的相关问题进行了重点的阐述。另外，还分析了遗传算法所存在的不足，指出了对其改进的可能途径。2 基于现有进化算法，受生物免疫机制启发，本文创造性地提出了一种新的进化算法一免疫进化算法( 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 ，i e a ) 。针对免疫进化算法，所进行的研究主要包括以下三个部分：首先，介绍了简单免疫进化算法的设计思想、流程和特点，提出了该算法的一般收敛性理论，并通过多峰函数优化的测试结果从应用的角度说明了它的可行性和正确性。其次，在简单免疫进化算法的基础上。分别提出了两种改进算法，即基于区间变换的免疫进化算法和基于网络调节的免疫进化算法。和简单免疫进化算法相比，基于区间交换的免疫进化算法不仅在多峰函数和g a 欺骗问题的应用中取得了更好的效果，而且提高了计算效率，增强了模式的统一性；基于网络调节的免疫进化算法是建立在上述两种算法基础上的一种改进算法，通过复杂约束优化问题的初步应用显示了该算法具有解决更复杂问题的能力。最后，对免疫进化算法的实现技术进行了详细探讨，并对其特点进行了总结。3 本文将免疫进化算法应用于解决水科学某些方面的优化问题，获得了满意的效果。其应用结果表明，该算法简单、高效、稳定性好，能较好地克服传统优化方法和现有进化算法的不足。总之，免疫进化算法是一种性能良好的优化算法，它能够被广泛用于解决水科学中的复杂优化问题。关键词：优化，免疫进化算法，水问题s t u d yo ni m m u n ee v o l u t i o n a r ya l g o r i t h ma n di t sa p p l i c a t i o nt ow a t e rp r o b l e mm a j o r ：h y d r o l o g ya n dw a t e rr e s o u r c e sp h d c a n d i d a t e ：n ic h a n g i i a ns u p e r v i s o r ：p r o f d i n gj i n ga b s t r a e ta sk e yt e c h n o l o g i e st os o l v ec o m p l e xo p t i m i z a t i o np r o b l e m s ，e v o l u t i o n a r ya l g o r i t h m sa l es t u d i e dc o n t i n u o u s l yb o ma th o m ea n da b r o a d ，a n dg r e a ta c h i e v e m e n th a sb e e nm a d e i nt h ep a p e r , b a s e do nt h ee x i s t e de v o l u t i o n a r ya l g o r i t h m s ，f u r t h e rs t u d yh a sb e e nd o n e ，a n dm a i nw o r k sa r ei l l u s t r a t e da sf o l l o w s ：i t h i sp a p e rp r e s e n t sac o m p a r a t i v e l ys y s t e m a t i cr e v i e wa b o u tp r o g r e s s ，b a s i cp r i n c i p l e ，p r o c e s s i n gt e c h n o l o g i e sa n da p p l i c a t i o no ft h ee x i s t e de v o l u t i o n a r ya l g o r i t h m s ，a n ds t r e s so ft h i sp a r ti sm a i n l yp u to nr e l a t e dp r o b l e m so fg e n e t i ca l g o r i t h m b e s i d e st h a t ，d i s a d v a n t a g e so fg e n e t i ca l g o r i t h ma r ea l s oa n a l y z e d ，a n dp o s s i b l ei m p r o v e da p p r o a c h e sa r ep o i n t e do u t 2 b a s e do ns t u d yo ft h ee x i s t e de v o l u t i o n a r ya l g o r i t h m s p r o p e r t ya n de n l i g h t e n e db yt h ei m m u n ep r i n c i p l eo fc r e a t u r e ，an o v e le v o l u t i o n a r ya l g o r i t h m - - l e a ( 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 ) i sc r e a t i v e l yp r o p o s e d a st ot h i sa l g o r i t h m ，o u rr e s e a r c hc o n s i s t so f t h en e x tt h r e ep a r t s f i r s t ，w ei n t r o d u c et h ed e s i g ni d e a ，f l o wc h a r ta n dc h a r a c t e r i s t i c so fs i e a ( s i m p l ei m m u n ee v o l u t i o n a r ya l g o r i t h m ) ，p u tf o r w a r dg e n e r a lc o n v e r g e n c et h e o r ya b o u ti t ，a n dp r o v ei tt ob ef e a s i b l ea n dc o r r e c tf r o mt h ea s p e c to fa p p l i c a t i o nt h r o u g ht h et e s t i n gr e s u l t so nf u n c f i o n s 谢t l lm u l t i m o d e s e c o n d ，b a s e do ns 工e a ，w ep r o p o s et w oi m p r o v e da l g o d t h m sr e s p e c t i v e l y , w h i c ha r ct h ei e a - - b i t ( i m m u n ee v o l u t i o n a r ya l g o r i t h mb a s e do i li n t e r v a lt r a n s i t i o n ) a n di e a - b n r ( i m m t m ee v o l u t i o n a r ya l g o r i t h mb a s e do nn e t w o r kr e g u l a t i o n ) c o m p a r e dw i t hs i e a ，i e a - b i tn o to n l ya c h i e v e sb e t t e rr e s u t si na p p l i c a t i o nt of u n c t i o n sw i t hm u l t i m o d e la n dg ad e c e p t i o np r o b l e m ，b u ta l s of i r t b e ri m p r o v e sc o m p u t a t i o ne f f i c i e n c ya n de n h a n c e sg e n e r a l i z a t i o no ft h em o d e l i e a - b n ri sa ni m p r o v e da l g o r i t h mt h a tb a s e si t s e l fo nt h ea b o v et w oa l g o r i t h m s ，a n dt h m u g hp r l m a r ya p p l i c a t i o nt oc o m p l e xc o n s t r a i n e do p t i m i z a t i o np r o b l e m ，i ti sp r o v e dt oh a v et h ea b i l i t yt os o l v em o r ec o m p l e xp r o b l e m s f i n a l l y ，w em a k ed e t a i l e dd i s c u s s i o na b o u tt h ep r o c e s s i n gt e c b , n o l o g i e so fi e a ，a n d 慨s u n l m a r i z et h ec h a r a c t e r i s t i c so f i t 3 i e ai sa p p l i e dt os o l v es o m e o p t i m i z a t i o np r o b l e m si nw a t e rs c i e n c e ，a n dt h er e s u l t ss h o wt h a tl e ai ss i m p l e ，e f f i c i e n ta n dr o b u s t ，a n dc a r lp r e f e r a b l yo v e r c o l n et h ed i s a d v a n t a g e so ft r a d i t i o n a lo p t i m i z a t i o nm e t h o d sa n dt h ee x i s t e de v o l u t i o n a r ya l g o r t h r n s 。a b o v ea l l ，i e ai sa na l g o r i t h mw i t hg o o dp r o p e r t i e s ，a n di tc a nb ew i d e l ya p p l i e dt os o l v ec o m p l e xo p t i m i z a t i o np r o b l e m si aw a t e rs c i e n c e k e y w o r d s ：o p t i m i z a t i o n ，i m m u n ee v o l u t i o n a r ya l g o d t h m ，w a t e rp r o b l e m四川大学博士学位论文第一章绪言1 1 从生物进化到进化计算按照达尔文的进化论，地球上每一物种从诞生开始就进入了漫长的进化历程，在其间，具有较强生存能力的生物个体容易存活下来，并有较多的机会产生后代；具有较低生存能力的个体则被淘汰，或者产生后代的机会越来越少，直至消亡。达尔文把这一过程叫做“自然选择，适者生存”。进化论揭示了生物种群从低级到高级，从简单到复杂的进化规律，提出了对物种多样性的动态解释，它是1 9 世纪生物学的重大成就。与之有关的生物进化的研究结论，已得到广泛的接受和应用。按照孟德尔和摩根的遗传学理论，遗传物质是作为一种指令密码被封装在每个细胞中，并以基因的形式排列在染色体上，每个基因有特殊的位置并控制生物的某些特性。不同基因组合产生的个体对环境的适应性是不一样的，通过基因杂交和突变可以产生对环境适应性强的后代。经过优胜劣汰的自然选择，适应值高的基因结构得以保留下来，从而逐渐形成了经典的遗传学染色体理论，它揭示了遗传和变异的基本规律。在一定的环境影响下，生物物种通过自然选择、基因交换和变异等过程进行繁殖生长，构成了生物的整个进化过程。遗传物质是细胞核中染色体上的有效基因，其中包含了大量的遗传信息【l 】。染色体上携带着关于生物性状的物质元素，生物体表现出来的外在特征是对其染色体构成的一种体现。生物进化的本质体现在染色体的改变和改进上，生物体自身形态的变换是染色体结构变化的表现形式。基因组合的特异性决定了生物体的多样性，基因结构的稳定性保证了生物物种的稳定性，而基因的杂交和变异使生物进化成为可能。生物遗传是通过父代向子代传递基因来实现的，而这种遗传信息的改变决定了生物体的变异。生物进化过程的发生需要四个基本条件：存在有多个生物个体组成的种群：生物个体之间存在着差异；生物能够自我繁殖；不同个体具有不同的环境生存能力，具有优良基因结构的个体繁殖能力强，反之则弱。四川大学博士学位论文生物群体的迸化机制可以分为以下三种基本形式：( 1 ) 自然选择：控制生物体群体行为的发展方向，能够适应环境变化的生物个体具有较高的生存能力，使得它们在种群中的数量不断增加，同时，该生物个体所具有的染色体性状特征在自然选择中得以保留。( 2 ) 杂交：通过杂交随机组合来自父代染色体上的遗传物质，产生不同于它们父代的染色体。( 3 ) 突变：随机改变父代个体的染色体上的基因结构，产生具有新染色体的子代个体。自然界的生物进化是一个不断循环的过程。在这一过程中，生物群体的自身也在不断完善和发展。可见，生物进化过程的本质上是一种优化过程，这给计算科学提供了直接的借鉴。在计算机技术迅猛发展的时代，我们可以模拟进化过程，创立新的优化计算方法，并把其应用到复杂的领域当中。2 0 世纪6 0 年代以来，生物学的进化论被推广应用于工程领域，形成了一种新型的计算方法一进化算法。进化算法仿效生物学中的进化和遗传的过程，按“生存竞争，优胜劣汰”的原则，同时考察多个候选解，淘汰劣质解，鼓励发展优质解，逐步提高解群体的质量，从而逼近所研究问题的最优解。一般认为进化计算( e c ) 包括遗传算法( g a ) 、进化规划( e p ) 和进化策略( e p ) 。他们用不同的进化控制模式模拟了生物进化过程，从而形成了三种具有普遍影响的模拟进化的优化计算方法。这三种方法也统称为进化算法( e v o l u t i o n a r ya l g o r i t h m s ，简称e a 或e a s ) 。进化算法是一种基于自然选择和遗传变异等生物进化机制的全局性概率搜索算法，其求解的一般过程包括以下步骤【2 l ：1 ) 随机给定组初始解；2 ) 评价当前这组解的性能；3 ) 根据2 ) 的评价结果，从当前解中选择一定数量的解作为基因操作对象；4 ) 对所选择的基因进行操作( 交叉、变异) ，得到一组新的解；5 ) 返回到2 ) ，对该组新的解进行评价；6 ) 若当前解满足要求或进化达到一定的代数，计算结束，否则转向3 ) 继续进行。与其它搜索技术( 如梯度搜索技术、随机搜索技术、启发式搜索技术和枚2四川大学博士学位论文举技术) 相比，进化算法具有以下特点：( 1 ) 进化算法的搜索过程是从一群初始点开始搜索，而不是从单一的初始点开始搜索。这样，其获得全局最优解的概率大大提高了。( 2 ) 进化算法使用的是目标函数的评价信息，其具有良好的普适性。( 3 ) 进化算法具有显著的隐式并行性。( 4 ) 进化算法具有很强的鲁棒性。目前，进化算法作为一种具有自适应调节功能的寻优技术，其独特的性能已在众多领域内获得了成功的应用，着重用于解决结构性优化、非线性优化、并行计算等复杂问题，其中遗传算法的研究最为深入、持久、应用面也最广。1 2 遗传算法1 2 1 遗传算法的发展简介遗传算法( g a ：g e n e t i ca l g o r i t h m ) 是一种全局随机搜索的优化计算方法。它以群体为基础，模拟生物遗传进化过程，通过保留适应度高的个体( 可行解) ，从而逐步提高群体适应度水平，实现群体收敛，最终获得( 准) 最优解。遗传算法作为一种现代优化算法，它具有良好的性能，在众多科学分支当中都得到广泛的应用。遗传算法和其它科学技术一样，都经历了一个不断发展完善的过程。此过程大致可以分为以下三个阶段，现简述如下：萌芽期( 上世纪5 0 年代后期至7 0 年代初期)在上世纪五十年代中期创立了仿生学，在五十年代后期，一些生物学家就着手采用电子计算机模拟生物遗传系统，在其中已使用现代遗传算法的一些标识方式。6 0 年代期间，美国芝加哥大学教授j h h o l l a n d 在研究自适应系统时，提出了系统本身与外部环境相协调的遗传算法 3 】。1 9 6 2 年加利福尼亚大学伯克利分校的b r e m e r m a r m 4 首次提出了杂交算子，即后代的特征取决于双亲有关基因的总合。第一次正式使用遗传算法( g e n e t i ca l g o r i t h m ) 这个术语，是在1 9 6 7年美国j d b a g a y 5 】关于搏弈论的论文中，他采用复制、交换、突变等手段研究国际象棋得到对弈策略。他还觉察到防止早熟收敛的机理，发展了自组织遗传算法的概念。1 9 6 8 年h o l l a n d 教授又提出了模式定理，它成为遗传算法的主要理论基础。在此阶段，c a v i c c h i o 【6j 研究了基于遗传算法的子程序选择和模式四川大学博士学位论文识别等问题，w e i n b e r g 7 】提出运用多层遗传算法进行g a 的参数优化，1 9 7 2 年，f r a n t z lg j 研究了g a 的基因迁移操作及多点交换操作等问题。通过上述等人的工作，为遗传算法的诞生打下了必要的基础。成长期( 上世纪7 0 年代中期至8 0 年代末期)1 9 7 5 年，h o l l a n d 教授的专著1 9 _ a d a p t a t i o ni n n a t u r a la n da r t i f i c i a ls y s t e m s ”正式出版，该书是作者十几年间许多思想的结晶，它详细阐述了遗传算法的理论，发展了一套模拟生物自适应系统的理论。人们把这一事件视为遗传算法问世的标志，h o l l a n d 也被视为遗传算法的创始人。同年，d e j o n g l l 0 】在其博士论文中对模式定理做了大量严格的计算实验，给出了明确的结论，他还建立了著名的五函数测试平台，定义了性能评价标准，以函数优化为例，对遗传算法的性能和机理进行了详细的实验和分析，为后继者提供了研究范例，并为g a 的广泛应用奠定了坚实的基础。上述两人的工作被视为遗传算法发展史上的两块里程碑。8 0 年代，对遗传算法的研究已成为人工智能领域的又一个热点。1 9 8 7年d l a w r e n c e 出版了遗传算法和模拟退火一书，用大量的事例介绍了遗传算法。另外，g o l d b e r g f l l 】和其他学者的专著【91 2 1 3 f r o m 版也大大地推动了遗传算法的传播和实际应用。发展期( 上世纪9 0 年代以后)在这个阶段，遗传算法不断向广度和深度发展。1 9 9 1 年，d l a w r e n c e 1 41出版了遗传算法手册一书，详尽地介绍了遗传算法的工作细节。1 9 9 6 年z m i c h a l e w i c z 的专著【l 川遗传算法+ 数据结构= 进化程序深入讨论了遗传算法的各种专门问题。自1 9 8 5 年起，遗传算法及其应用国际会议每两年召开一次，遗传算法基础会议也于1 9 9 0 年召开，随后于1 9 9 2 ，1 9 9 4 ，1 9 9 7 年举行。有关a i 的会议和刊物上大多会有g a 的专题或论文。另外，文献 1 6 1 9 】对模式定理作了进一步的研究，丰富了遗传算法的数学基础。到目前为止，g a 已渗透到很多领域，成为多学科结合和渗透的产物，为一些实际问题的解决发挥重要的作用。生物进化的历史比任何数学证明都强有力，随着遗传学、进化论及分子生物学最新研究成果的不断涌现，遗传算法也在吸收这些成果的同时自身也得到了进化。1 2 2 遗传算法的基础和基本原理四川大学博士学位论文1 2 2 1 遗传算法的基苯概念遗传算法主要借用生物进化中“适者生存”的规律。“适者生存”揭示了大自然生物进化过程中的一个规律：最适合自然环境的群体往往产生了更多的后代群体。生物进化的基本过程见图1 1 【2 0 1 。图1 - 1以这个循环圈的群体( p o p u l a t i o n ) 为起点，经过竞争后，一部分群体被淘汰而无法再进入这个循环弱，而另一部分则成为种群( r e p r o d u c t i o n ) 。优胜劣汰在这个过程中起着非常重要的作用，这在自然界显得更加突出。种群通过婚配的作用产生子代群体。在进化过程中，可能会因为变异而产生新的个体。综合上述作用，新群体取代了旧群体，这样，新的群体将作为新循环的开始。19 6 2 年，h o l l a n d 教授发现【9j ，按照生物界的自然选择( s e l e c t i o n ) 和杂交( c r o s s o v e r ) 的自然进化( n a t u r a le v o l u t i o n ) 的方式，编制的计算机程序能够解决复杂的优化问题，这种新的优化方法就是遗传算法。生物进化的过程可以视为生物群体在其生存环境的约束下，通过各个个体的竞争( c o m p e t i t i o n ) 、自然选择、杂交、变异( m u t a t i o n ) 等方式，在“适者生存，不适者被淘汰”这一法则指导下的自然优化过程。因此，生物进化的过程，可以被认为是某种优化问题的求解过程【2 1 1 。遗传算法主要借鉴了生物进化的一些特征，其主要特征体现为：( 1 ) 进化发生在解的编码上。这些编码按生物学的术语称为染色体或基因串。由于对解进行了编码，优化问题的一切性质都通过编码来研究。编码和解四川大学博士学位论文码是遗传算法的一个主题。( 2 ) 自然选择规律决定哪些染色体产生超过平均数的后代。遗传算法中，通过优化问题的目标而人为地构造适应函数以达到好的染色体产生超过平均数的后代。( 3 ) 当染色体结合时，双亲的遗传基因的结合使得子女保持父母的特征。( 4 ) 当染色体结合后，随机的变异会造成子代同父代的不同。假设我们考虑的是如下一个优化问题：m a x f ( x ) i x 工)( 1 - 1 )这里厂是x 的一个正值函数，即对任意x z ，厂( x ) 0 。是问题的解空间，即问题的所有可能解全体。它可以是一个有限集合( 如组合优化问题) ，也可以是实空间r n 的一个子集( 如连续优化问题) 等。遗传算法在求解问题时是从多个解开始的，这多个解的集会称为一个群体( p o p u l a t i o n ) ，记为p o p ( t ) 。这里t 表示进化代。一般地，p o p ( o 中元素的个数在整个进化过程中是不变的，我们将此称为群体的规模，常记为n 。p o p ( t ) 中的元素称为基因串或个体( i n d i v i d u a l ) 或染色体( c h r o m o s o m e ) ，记为崩( f ) ，x ，( f ) ，等。而个体对环境的适应程度叫做适应度( f i t n e s s ) , 它是进行选择操作的基础。当我们进行遗传操作时，要选择当前解进行交叉以产生新解，这些当前解称为新解的父代( p a r e n t ) ，产生的新解称为子代( o f f s p r i n g ) 。一般而言，遗传算法在求解实际问题时常常还需要将问题的解进行编码，通常采用二进制编码。假定个体x 表现为基因串形式，假设x = b ”= f o ，1 ) ，即x长度为n 的二进制串全体，则一个长度为n 的二制串称为一个染色体。染色体的每一位称为基因( g e n e ) ，基因所在染色体中的位置称为基因位( 1 0 c u s ) 。依照生物术语，z 中的点称为基因型( g e n o t y p e ) 。在对遗传算法进行理论分析时，常常还要用到模式( s c h e m a ) 的概念。模式表示的是一些特定的子集，基因串的各分量取值0 ，1 ，一个模板中0 和1 所占的位置成为模板位置，+ 所占的位置成为非模板位置。出现在模式中取确定值位置的数目称为模式日的阶，记为o ( 明。模式中第一个取确定值位置与最后一个取确定值位置之间的距离定义四川大学博士学位论文为模式的长度，记为8 ( h ) 。模式、模式的阶及其长度的定义对于区分基因串( 即染色体) 的相似程度是很有用的概念，并且它们提供了分析基本遗传算予对群体中基因块作用效果的一种基本方法。1 2 2 2 遗传算法的表述最优化问题的求解过程是从众多的解中选出最优的解。g a 正是把一组随机生成的可行解作为父代群体，把适应度作为父代个体适应能力大小的一种度量，经选择、杂交、变异等算子的作用，优胜劣汰，通过反复迭代，群体适应能力不断提高，以逼近或达到最优解。因此，g a 是模拟生物进化的一种优化算法，这样的共同点使得遗传算法可以在优化问题中得以应用。遗传算法就其流程而言，编码的不同和算子不同的实现方式可以构成不同的遗传算法。但就遗传算法的一般结构来说可以描述为【2 3 l _s t e p l选择问题的一个编码：给出一个有个染色体的初始群体p o p ( 1 ) ，f = 1 ：s t e p 2对群体p 叩中的每个染色体p 印，( t ) 计算它的适应函数厂i = f i t n e s s ( p o p f ( f ) ) ；s t e p 3若停止规则满足，则算法停止；否则，计算概率p ，：# ，f - 1 ，2 ，( 1 _ 2 )磊厂，并以概率分布( 1 - 2 ) 从p o p ( t ) 随机选一些染色体构成一个种群n e w p o p ( t + i ) = p o p 弘) j j = 1 , 2 ，) ；s t e p 4通过交配，交配概率为p 。，得到一个有n 个染色体的c r o s s p o p ( t + 1 ) ；s t e p 5以一个较小的概率p 。，使得一个染色体的一个基因发生变异，7婴型查兰苎主兰垡丝苎形成r n u t p o p ( t + i0 = 什j ，一个新的群体p o p ( t ) = m u t p o p ( t ) ；返回s t e p 2 。遗传算法包含以下的主要处理步骤：对优化问题的解进行编码。此处，我们称一个解的编码为一个染色体，组成编码的元素称为基因。编码的目的主要是用于优化问题解的表现形式和利于之后遗传算法中的计算。适应函数的构造和应用。适应函数基本上依据优化问题的目标函数而定。当适应函数确定以后，自然选择规律是以适应函数值的大小决定的概率分布来确定哪些染色体适应生存，哪些被淘汰，生存下来的染色体组成种群，形成一个可以繁衍下一代的群体。染色体的结合。双亲的遗传基因结合是通过编码之间的交配( c r o s s o v e r ) 达到下一代的产生。新一代的产生是一个生殖过程，它产生了一个新解。最后是变异，新解产生过程中可能发生基因变异，变异使某些解的编码发生变化，使解有更大的遍历性。这样，予代个体有别于父代个体，也改变了其对环境的适应能力。表卜l 列出了生物遗传基本概念在遗传算法中作用的对应关系。g a 就是用计算机技术来模拟上述生物进化特征，并逐渐发展为一类新型的优化方法【弘2 5 1 。表卜1 生物遗传概念在遗传算法中的对应关系。2生物遗传概念遗传算法中的作用适者生存在算法停止时，最优目标值的解有最大的可能被留住个体( i n d i v i d u a l )解染色体( c h r o m o s o m e )基因( g e n e )适应性( f i t n e s s )群体( p o p u l a t i o n )种群( r e p r o d u c c j o n )交配( c r o s s o v e r )变异( m u t m i o n )解的编码( 字符串、基因串、向量等)解中每一分量的特征( 如各分量的值)适应函数值选定的一组解( 其中解的个数为群体的规模)根据适应函数值选取的一组解通过交配原则产生一组新解的过程编码的某一个分量发生变化的过程1 2 2 3 遗传算法的基本理论1 、模式定理( s c h e m at h e o r e m )四川大学博士学位论文在g a 中，称个体基因串中的相似样板为模式( s c h e m a ) ，它描述了在某些特征位置上具有相同基因值的基因串集合。对s g a 而亩，群体和种群的维数相等，且不随代数的变化而变化；适应函数直接选用目标函数；种群中的个体通过轮盘赌的方式选取；种群中的一对个体采用随机交配位的方式产生一对子代：每一个基因有相同的变异概率。若基因串x 在日模板位置上对应的分量相同，则称工具有日模板。具有相同模板预示着两个基因串具有一些共同的性质。对于n 维的向量，共有3 “个模板。在遗传算法在进化的过程中。含有模板的个体的遗传概率 2 0 】可以表述为：记g ( f ) 是第t 代群体，即第t 代基因串的集合，t ( h ，g ( f ) ) = 缸g ( f ) k 具有模板h )( 1 - 3 )其中t 称为遗传的第t 代，t ( h ，g ( f ) ) 为g ( t ) 中具有模板h 的所有染色体集合。针对s g a 而言，每一代帕群体中染色体数相同。由于遗传算法的三个算子”分别为：种群选取、交叉和变异。下面三个引理分别针对这三种情况独立考虑模板的变化。引理1 1 对s g a 的交叉算予而言，在新种群n e w p o p ( t 十1 ) 中具有模板日的染色体期望数为e l ( ，t + 1 ) = f ( h ，t ) n ( h ，f ) ，( 1 - 4 )其中n ( h ，t ) 为f 蝴j t ( h ，p 印( f ) ) 所包含的基因串数，少加e s s ( y )胭力= 型裂煞铲s ，r ：y 乏劫i t ( p o p ( t ) l引理1 2对s g a 的交叉算子而言，若在r 时刻，模板日的长度为6 ( h ) ，9四川大学博士学位论文采用简单交叉方法，随机选一个交叉位，交换位后基因，在t + l 时刻模板h 保留下来的概率为眯即+ 1 ) 小鲁( 1 _ 朋力)其中，p ( l r ，f ) 表示f 时刻模板日的出现概率。交叉的概率为p 。- 则( 1 6 )引理1 3 对s g a 的变异算子而言，每个基因的变异概率为p 。，假设模板日经过简单变异在t 时刻的存在概率为p 2 ( h ，f )p 2 ( 日，f + 1 ) = ( 1 一p 。) 。打l p 崩d ( 日)( 1 7 )通过上面三个引理，从数学理论上得到种群选取、交叉和变异后，一个模板的变化概率。由此，可以综合得到下面定理；定理1 1 ( 模式定理) 假设群体在t 时刻时有相同模板h 的染色体个数为n ( h ，t ) ，经过满足引理1 1 的种群选取、满足引理1 2 的以概率p 。交叉和满足引理1 3 以概率p 。的变异，则在t + l 时刻，群体中具有模板的染色体数的期望值为e ( 髟，f + 1 ) ( 1 一j 旦! 譬尘一p m 0 ( 日) ) ( 日， ) ( 日，f ) ( 1 - 8 )p u 果f ( h ，f ) ( 1 一p d ( _ h 一) 一po ( 日) ) ，则从概率意义上来说，每代具有“一l模扳的基因串将随迭代次数的增加而增加。在一个有个染色体，每个染色体的编码长度为n 的群体中，经过一代遗传可生存的模板可以这样粗略的估计：可生存的模板一定有较大的出现概率，给一个固定的概率值r ，由于交配使得长度大的模板不易生存，再由引理1 21 0四川大学博士学位论文得则要求1 一! 兰堕；堕( 1 一p ( h ，f ) ) l 一! ! 兰蔓；堕尸。n l咒一l艿( 日) ( n - 1 ) ( 1 - p s ) ：万。p 。( 1 9 )由引理只考虑长度较短的模板，考虑染色体中长度小于占。的模板。这样长度的模板数量的一个下限为2 5 s - 8 。) 。由于群体中有个基因串，故长度小于艿。的模板出现数的下界为2 如0 一艿。)( 1 一l o )若群体维数= 2 警，则长度小于艿。的模板出现数为o ( n 3 ) ，这是g o l d b e r g 估计的一个结果n l 。在确定一个合适的群体维数后，它隐含着遗传算法的一次进化中平行处理d ( 3 ) 种不同的模板，这一性质一般被称为遗传算法的隐式并行性( i m p l i c i tp a r a l l e l i s m ) 。图式定理是研究较深入、影响较大的g a 理论，它奠定了g a 的数学基础，它指出短的、低阶、优于平均的图式( 建筑块) 的数目在迭代进化中将以指数增长，含有这种模板的个体具有较大的遗传概率【“】。其将g a 的运行过程理解为模板的操作，并依此解释了g a 的运行特性，从一种结构的角度说明遗传算法的收敛性。另外，在一个规模为的群体中，g a 每次在处理个个体的同时，也获得了对o ( n 3 ) 个图式的并行处理，这一隐含的并行性揭示了g a 的很强的并行搜索能力。2 、g a 的马尔可夫链收敛性分析粤查兰苎主兰堡堡苎全局收敛是遗传算法得以应用前提，迸年来，人们对遗传算法的全局收敛性分析做了大量的分析工作。g o l d b e r g 2 6 】等首先使用马尔可夫链分析了遗传算法，e i b e n f 2 7 】等用马尔可夫链证明了保留最优个体( e l i t i s t ) 的g a 是概率性全局收敛的，r u d o l p h 2 8 1 证明了s g a 不是全局收敛的。b a c k 2 9 和m u h l e n b e i n 划研究了g a 的时间复杂性问题。文献c 3 l l 利用马尔可夫链对十进制、多种变异形式g a的收敛性进行了分析，得到了一些相应的结论。引理1 4 若c 、m 和s 是随机的，兵中m 0 和s 是列容的，则c m s o引理1 5 若p 是本原随机阵，p 。= 二肺= ( 1 ，1 ，1 ) 7 ( 以，p 2 ，则e 田收敛到一个全正稳定随机阵，其中( | p 。，尸：，p ) 7 唯一满足，( p l ，p 2 ，p 。) p = ( p l ，p 2 ，p n ) ，量p i = l 暑l l p ，= l i mp 擎) 0 。i - l。 _ 。即( p ，p ，p 。) 7 是矩阵，的特征值为l 且每一个分量为正数的特征向量，且满足量p 。= 1 。引理，e 若p = 匮爿为随机阵，其中可约阵中c 为一个m m 全正随机阵，r 的每行中至少有一个非零元，则p m ：工拥尸t ：ic 。oi 是一个稳定的女j r 0随机矩阵，r 。表不k z - i t i r c i - 1 的极限。对s g a 而言，只要染色体空间维数有限，其状态空间维数m = l q ( i q i 为所有个体形成的空间，n 为群体的规模) 也有限。遗传算法由三个算子种群选取、交叉和变异所组成。这里，我们按交叉、变异和种群选取顺序使得群体从个四川大学博士学位论文状态到达另一个状态，这就是一个有限状态的马氏链。( 1 ) 交叉记交叉概率矩阵c = ( c f ) 盯。村，其中c f 为从状态j 经过交叉变为状态的概 ，率，c 。= 1 ，c 为个随机阵。j = 1( 2 ) 变异经过每个基因有相同的变异概率的简单变异，刚对应的转移概率矩阵为m = 渤f ) m 。村，可得m 是一个全正随机阵。( 3 ) 种群选取通过种群的选取从一个状态到达另一个状态的概率转移矩阵s = ( s 口) m 。吖，可得j 是列容的。定义1 1 设y 0 ) = ( z i ( f ) ，彳2 ( f ) ，x i 、，( f ) ) 是s g a 进行到t 代后得到的一个群体，记z ，_ m a x f ( x ，( f ) ) i ，= 1 , 2 ，) ，f ( x ) 为目标函数。遗传算法收敛到全局最优，当且仅当：l i mp ( z i _ f + ) = l ，式中，+ 为全局最优值。t - - + o o定理1 2 若参数满足：变异概率0 p 。 1 ，交叉概率0 p ，1 ，则s g a不收敛到全局最优值。证明：由关于交叉矩阵c 、变异矩阵m 和选择矩阵s 的讨论和引理1 4 知c m s 为全正矩阵，再由引理1 5 得l i m p ( z 。= 厂) _ 。且优化目标为最小。( 1 - 1 5 )简单适应函数的优点是构造简单，与目标函数直接相关。在遗传算法初始阶段，各个个体的性态明显不同，其适应度大小差别很大。个别优良个体的适应度有可能远远高于其他个体，从而增加被复制的次数。反之，个别适应度很低的令体，尽管本身含有部分有益的基因( 字符) ，但却会被过早舍弃。这种不正常的取舍，对于个体数目不多的群体尤为严重，会把遗传算法的搜索引向误区，过早地收敛于局部最优解。这时，需要将适应度按比例缩小，减少群体中适应度的差别，另一方面，当遗传算法到后期，群体逐渐收敛，各个体适应度判别不大，为了更好地优胜劣汰，希望适当地放大适应度，突出个体之间的差别。无论是缩小或放大适应度，下式对适应度进行线性变换是常用的方法。f = o f + b式中一缩放后的适应度( 1 - 1 6 )四川大学博士学位论文厂一原来的适应度a 、b 一系数。在g a 后期，放大适应度相近个体的差异，使优秀个体的优势更明显的作法还有s t o f f a 4 3 1 提出的模拟退火拉伸；f o r r c s t 提出o - 截断；g i l l i e s 提出的乘幂标等。另外。对带有约束条件的优化问题，处理适应度函数常采用罚函数【2 3 1 。2 、选择算子( s e l e c t i o no p e r a t o r )选择的作用是从当前种群中选出优良个体作为父代以繁殖下一代。遗传算法在搜索过程中，一方面要选择优良个体，实现优胜劣汰，使搜索收敛于全局最优解；另一方面，在搜索过程要保持群体多样性，使搜索空间不断扩大，避免收敛于局部最优解。因此，选择力度和群体多样性是遗传算法的一对矛盾。若加大选择力度，能提高收敛速度，但群体缺乏多样性。反之，减少选择力度，能保持群体多样性，但影响收敛速度。选择算子是g a 最重要的算子之一，它在群体多样性和收敛性之间起着动态的调整作用，它性能的好坏直接关系到g a的求解质量。为此，人们发展各种选择操作，其目的是为了避免有效基因缺失，提高全局收敛性和计算效率。选择的主要思想是个体复制概率正比于其适应度，但适应度的分布与问题有关，比例复制不一定合适，故而采用适应度尺度交换方法进行弥补。排序选择方法则与适应度的分布和正负无关。目前，常用的选择算子有以下几种：( 1 ) 适应度比例方法( f i t n e s sp r o p o r t i o n a lm o d e l )它选择的依据是个体适应度的大小。个体被选中的概率为：旷轰( i - 1 7 )式中，为个体i 的适应度，厂，为各个体适应度的累加值。这种方法的缺点是存在统计误差。( 2 ) 分级选择法( r a n k i n gs e l e c t i n g )它用连续渐变的分级替代数值悬殊的适应度，因此，它能消除个体适应度婴型查兰竖主堂垡堡兰差别悬殊时的影响，但此方法未能充分利用遗传信息。( 3 ) 竞技选择法( t o u r n a m e n ts e l e c t i n g )此方法每次在每一代群体中随机选取k 个个体构成一个小群体，通过相互竞争，优胜者成为下一代个体。该方法的选择力度取决于k 的大小。( 4 ) 波尔兹曼选择法( b o l t z m a n ns e l e c t i n g )此方法的一个重要特点是：其选择力度随时间而变化。目前在遗传算法中，最常用的仍是比例选择法，其原因一是由于它是h o l l a n d 教授最早提出的一种经典方法，二是由于它符合遗传算法的图式理论。在实际工作中我们发现，比例选择法要作一些修正才能获得较好的实际应用，因此，近年来分级选择法、竞技选择法等新的选择方法日益被重视。对选择操作进行的主要研究工作可参见文献【5 ，1 0 ，1 6 ，2 9 ，4 4 4 61 等。3 、交叉算子交叉的作用是按照一定概率随机地交换一对染色体的部分基因的形成新的子染色体。交叉算予的作用是实现现有基因的重构，组合出新的个体。要在串空间进行有效搜索，同时须降低对有效模式的破坏概率。通过交叉使前一代中优秀个体的性状能在后代个体得到遗传和继承，它通过基因重构，可以使得好的模式得以组合，是产生新个体的重要手段，交叉操作是g a 区别于其它迸化算法的重要特征，交叉操作的许多重要特性及适用范围有待深入研究。目前常用的交叉规则有：( 1 ) 常用方法双亲双子法这种方法是在双亲确定后，以一个随机位进行位之后的所有基因对换。( 2 ) 变化交配法其采用的方法是从头开始先比较它们的相同的基因，从不同基因位置按常规方法随机选取交配位。( 3 ) 多交配位法随机选择多个交配位，双亲以一个交配位到下一个交配位基因相互替代和下一个交配位到再下一个交配位不变这样交叉形成两个新的后代。四川大学博士学位论文( 4 ) 双亲单子法从常规交配法的两个后代中根据优胜劣汰选一个优良的个体。( 5 ) 显性遗传法它将双亲中具有超优关系的基因遗传到下一代。( 6 ) 单亲遗传法下一代个体由单一父代自身的基因变化而产生。岑文辉等【38 】根据每代个体的相似程度和每两代2 _ f 日q 解群质量的差异来动态调整交叉概率；s r i n v i v a s 等1 3 3 1 提出了一种交叉概率随个体适应度自动改变的方法；最近提出了一种基于知识的非均匀的杂交算子【4 ，这种算子体现了问题的特征，能有效提高g a 的计算效率和解的质