（模式识别与智能系统专业论文）遗传算法在都江堰渠首配水中的应用研究.pdf

四川大学硕士学位论文遗传算法在都江堰渠首配水中的应用研究模式识剐与智能系统专业研究生：陈敏指导教师；古钟璧资料表明，都江堰灌区岷江来水有逐年下降的趋势，同时为顺应灌区经济的发展，灌区需水量又逐年增加。为解决这一矛盾，本文针对都江堰渠首六大干渠进行了优化配水的研究，而选择合适的优化算法又是整个配水过程中的关键部分。遗传算法是一种模仿自然界生物种群选择和进化的随机搜索算法，是一种新型的优化技术。在比较了传统优化算法和遗传算法的基础上。得出选用遗传算法进行优化配水的结论。本文研究具体内容如下：( 1 ) 基本遗传算法的学习和讨论。系统学习了基本遗传算法的生物学模型、基本思想、实现技术、模式理论以及遗传算法的特点等，讨论了几种传统优化算法和它们的不足，得出遗传算法进行优化的优势所在。( 2 ) 都江堰渠首配水模型研究。系统阐述了都江堰渠首水资源配置的基本概念、配置原则和目标以及优化配置机理。给出配水模型的功能，探讨了经济效益最大原则、损失水量最小原则、水库蓄放水优先级原则等，并给出三类目标函数表达式。由于都江堰灌区的水主要用于灌溉，因此本文研究的模型是以灌溉效益最大为目标的，依据经济效益最大原则，提出本文的目标函数和约束条件。( 3 ) 改进遗传算法研究。针对基本遗传算法存在早期收敛和后期收敛速度缓慢等缺点，对基本遗传算法进行改进。改进包括以下几方面：编码设计、适应值函数的选取、选择策略、遗传操作、控制参数选择以及进化终止准则等。本文采用非均匀算术交叉和非均匀变异，同时设计了与进化代数相关的交叉概率以及自适应变异概率，有效改进了遗传算法的性能，提高了运行速度。- 一四川大学硕士学位论文( 4 ) 配水问题的仿真研究。以都江堰灌区渠首2 0 0 5 年5 月下旬预测来水为依据，进行优化配水的仿真研究。在m a t l a b 7 0 环境下，运用常规估算办法模拟数据，对六大干渠的效益函数进行多项式拟合。最后将基本遗传算法和改进遗传算法分别进行配水计算，得出结论。本文的特点在于针对具体的都江堰渠首配水问题，将基本遗传算法有针对性地进行改进，有效的解决具体问题，具有一定的应用价值，对类似的优化分配问题有一定的参考价值。关键词：改进遗传算法都江堰渠首灌溉效益配水模型l i塑型查兰堡圭堂堡堡塞a p p ii c a t i o no fg e n e t i ca i g o r i t h mo nd is i r i b u t i o no fw a t e rr e s o u r c e sind u jia n g y a nc a n aih e a dm a j o r ：p a t t e r nr e c o g n i t i o na n di n t e l l i g e n c es y s t e mg r a d u a t e ：c h e nm i nt u t o r ：g uz h o n g bh i s t o r yd a t as h o w st h en u m b e ro fm i nr i v e rl sd e c l i n i n gy e a rb yy e a r a tt h es a m et i m e ，t h ee c o n o m yd e v e l o p m e n to fd u j i a n g y a nn e e d sm o r ea n dm o r ew a t e r t os o l v et h ec o n t r a d i c t i o n ，t h i sp a p e rd i s c u s s e sh o wt od i s t r i b u t ew a t e rr e s o u r c ea m o n g6c a n a l s w h i c ho p t i m a lm e t h o di st ob ec h o s e ni st h ek e ye l e m e n t g e n e t i ca l g o r i t h m ( g a ) san e w s t y l eo p t i m i z i n gt e c h n i q u e ，i ti m i t a t e st h es e l e c t i o na n de v o l u t i o no fb i o l o g yi nt h en a t u r ea n di tl sar a n d o ms e a r c ha l g o r i t h m w h i c hc a nm a k eu pl h ed e f i c i e n c i e so fc o n v e n t i o n a io p t i m i z a t i o na l g o r i t h m s t h ec o n c r e t ec o n t e n t sa r ea sf o l l o w s ：( 1 ) s t u d ya n dd i s c u s s i o no fs g a b i o l o g ym o d e l ，b a s i ci d e a ，i m p l e m e n tt e c h n i q u e s s c h e m at h e o r ya n df e a t u r ea r es y s t e m a t i c a l l yl e a r n e d ( 2 ) s t u d yo fw a t e rd i s t r i b u t i o nm o d e l b a s i ct h e o r y p r i n c i p l ea n dm e c h a n i s ma r ei n t r o d u c e d m o d e lf u n c t i o nl sg i v e na n de v a l u a t i o nc r i t e r i ao fe c o n o m y a m o u n to fw a t e ra n de n e r g ya r ed i s c u s s e d c o n s i d e r e dt h ew a t e ri sm a i n l yu s e dt oi r r i g a t ei nd u j i a n g y a ni r r i g a t e da r e a ，t h i sp a p e rm a i n l yd i s c u s s e sl r r i g a t e db e n e f i t a c c o r d i n gt ol h r e ep r i n c i p l em e n t i o n e da b o v e ，o b j e c lf u n c t i o na n dr e s t r i c t i o nc o n d i t i o na r eg i v e n ( 3 ) s t u d yo fi m p r o v e dg a ( i g a ) t os o l v et h ep r o b l e mt h a ts g ah a ss o m ed i s a d v a n t a g e ss u c ha se a r l yc o n v e r g e n c ea n dt h es l o wu p p e rl u四川大学硕士学位论文c o n v e r q e n c er a t e i nt h i sp a p e rs g ai si m p r o v e do ft h ef o l l o w i n ga s p e c t sc o d i n gd e s i g n ，s e l e c t i o no ff i t n e s s ，s e l e c t i o ns t r a t e g y 。g e n e t i co p e r a t i o n ，s e l e c t i o no fc o n t r 0 1p a r a m e t e r sa n dp r i n c i p l eo fe n d i n go fe v o l u t i o n f n c o n s i s t e ncc r o s s o v ero p e r a t ora n dm u t a t i o no p e r a t o ra r ea d o p t e d a n dc r o s s o v e rr a t ec o r r e l a t i v et oe v o l u t i o ng e n e r a t i o na n da d a p t i v em u t a t i o nr a t ea r ed e s i g ni nt h i sp a p er t h ea p p l i c a t i o ni n d i c a t e st h a tt h i sa l g o r i t h mh a st h eo p t i m u mr e s u l t sw i t hi m p r o v e dp r e c i s i o na n dc o n v e r g e n c es p e e d ( 4 ) s i m u l a t i o ns t u d yo fw a t e rd i s t r i b u t i o n b a a e do r o r e c a s t i n gw a t e rd a t ao fi a s fl e n d a yo fm a y ，2 0 0 5 ，b e n e f i lf u n c t i o n so f6c a n a l sa r ef i t t e dw i t hp o l y n o m i a lf i t t i n gm e t h o d f i n a l l ys g aa n di s g aa r ea p p f i e dt ow a t e rd i s t r i b u t i o nr e s p e c t i v e l y t h eo u t s t a n d i n gp o i n to f t h i sp a p e rc o n s i s t si ns g ai sp o i n t e d l yf m pr o v e db a s e do nc o n cr e t ep r o b l e mo fw a t e rr e s o u r c ed i s t r i b u t i o n t h er e s u l t si n d i c a t et h a ti g ai 8e f f e c t i v ea n dh a sa p p l i c a t i o nv a l u ew h i c hh a sr e f e r e n c e dv a l u el oo t h e rs i m i l a rp r o b l e m s k e yw o r d s ：i m p r o v e dg e n e t i ca l g o r i t h md u j i a n g y a nc a n a lh e a di r r i g a t i o nb e n e f i tw a t e rd i s t r i b u t i o nm o d e iv四川大学硕士学位论文第一章绪论1 1 课题研究的背景和意义水资源是自然资源中的母体资源，是生态环境的控制性要素之一；同时又是战略性经济资源。随着经济的快速发展，人口的持续增长，城市化水平的提高，产业结构的调整，生态环境的保护，都需要以水资源作为支撑和保障。为此，要认真贯彻落实治水方针和可持续发展战略，协调解决水资源短缺和浪费并存问题，合理安排好生活、生产和生态用水，优化配置水资源，提高水资源和水环境对经济和环境的承载压力，实现水资源的可持续利用。都江堰灌区【6 8 】位于四j i i 政治、经济、文化、交通的中心地带，是支撑四川经济社会发展不可替代的物质基础。跨过2 2 6 0 年，都江堰已经成为地跨岷江、沱江、涪江三个流域，幅员面积2 3 2 万k r n 2 ，总体规划灌溉面积1 0 0 万h m 2 ，近期规划为7 9 万h r n 2 ，目前实灌6 7 2 k i n 2 的特大型灌区，不仅满足了成都平原和川中丘陵地区农业用水的需要，而且还为灌区的生活、工业、防洪、环保、发电、水产、旅游等提供了综合服务。水资源是都江堰灌区社会经济发展的重要支撑之一，水资源的供给构成了灌区可持续发展的资源基础。要实现都江堰灌区的可持续发展，既要考虑社会的发展，对水的需求的功利性目标，又要重视“天人协调”“人水和谐”的理性化目标。因此，都江堰水利可持续发展的战略指导思想，就是要适应建立社会主义市场经济体制和进入信息时代的要求，按照“效率与公平”的原则，在水资源信息管理上，把当前利益和长远利益、开源和节流、开发利用和治理保护有机结合起来，推动灌区水利发展模式由传统的工程水利向现代的资源水利的战略转变，从而使灌区水利的发展满足我国可持续发展总战略的要求，并为之提供支撑，发挥保障和促进作用。尽管都江堰的持续发展已经使它成为中国水利的骄傲，但它在发展中仍然面临着一些问题。一是总量不足。灌区人均占有水资源量1 3 0 0 m 3 ，仅为全省4 3 ：农田亩四川大学硕士学位论文平均水资源量1 7 8 0 m 3 ，仅为全省的4 7 ，两项指标均低予国际公认警戒线。二是时空分布不均。每年6 、7 、8 三个月岷江上游来水和区间降雨都占年总量的7 0 ，1 2 月到次年5 月只占年总量的1 0 ，供需矛盾突出。三是水环境恶化污染严重。都江堰渠首的岷江径流主要由降水补给，其次为地下水和高山融雪补给。多年平均流量4 5 9 m 3 s ，占灌区用水量的5 0 8 0 ，岷江上游水资源丰富，利用率比较高，是都江堰灌区用水的主要来源。1 9 3 8 2 0 0 0 年实测年径流量统计计算结果表明，岷江上游来水量的实际关系变化比较稳定，但根据岷江5 0 余年实测资料按时段逐年分析，岷江来水有逐年减少的趋势p 3 1 ( 见表1 1 ) 。表1 12 0 世纪岷江来水趋势岷江来水月平均最小流量年代备注亿( m 3 )( m 3 s )2 0 4 01 6 21 5 45 01 5 51 4 66 0 7 01 5 21 3 68 01 4 21 1 79 91 1 4 81 2 81 9 9 8 年最小流量低于1 0 0m 3 s 的历史最低值目前，都江堰内外江引入水量9 3 8 7 亿m 3 ，占岷江来水的6 3 3 ，已达国际公认的水资源承载能力自9 极限。但是由于岷江来水年内分配不均，引入水量中丰水期较多，枯水期( 每年l 5 月) 平原直灌区几乎年年缺水，多年平均缺水3 2 4 亿m 3 ，p = 9 0 的大早年缺水3 2 4 亿i n 3 ，缺水时段主要集中在每年的2 5 月。要解决上述问题，提高现有岷江来水的利用效率，达到节约、高效的目的，必须依赖灌区用水管理水平的提高。本文对渠首六大干渠的水量分配问题正是基于这样的背景提出的。基于可持续发展的都江堰灌区水资源优化分配，是以可持续发展战略为指导思想，运用系统分析理论与遗传算法优化技术，将有效水资源在各条干渠进行最优化分配，从而获得最佳灌溉效益。其研究意义是：2四川大学硕士学位论文( 1 ) 促进水资源的合理有效利用渠首水资源优化配置没有增加供水量。也没有减少需水量，但它却使总体效益最大化。这是因为灌区水资源配置是以总的灌溉效益最大为目标，利用优化方法和技术，减少水资源单耗量大的迸水口的占有量，将节省下来的水资源用于水资源利用率高、单耗小、经济效益大的进水口，从而使水资源得到合理有效利用。( 2 ) 促进工程水利向资源水利的转变灌区优化配水虽然无法从数量上减少缺水量，但它是减缓水资源供需矛盾的最经济最快速的方法，同时它还使科学技术渗透到水资源管理工作中，提高管理者的科学意识和管理水平，促进工程水利向资源水利的转变。( 3 ) 促进智能优化理论与方法的探讨本文所讨论的只是灌区水资源优化配置中的一个方面，只考虑了灌溉效益最大。但是对于整个都江堰灌区水资源系统来说，它是一个复杂的大系统，目标也应该是综合多方面的。传统的线性规划、动态规划方法受到了问题复杂程度的限制。新发展起来的智能优化算法，例如遗传算法、模拟退火、神经网络、禁忌搜索等等，为解决复杂优化问题提供了新的思路和手段。因此，探讨智能优化算法在都江堰灌区水资源系统中的应用，对于促进这些算法的实际应用以及为解决其他复杂大系统问题积累经验，具有重要意义。( 4 ) 对其他优化分配问题有一定的参考价值水资源是自然资源之一，任何自然资源都与水资源一样，具有一定使用价值和价值，却又受到一定量的限制，同样存在着合理有效分配的问题。资源优化配景问题有一定的相似性和差异性，本文的优化配水对解决其他资源优化配置具有一定的参考价值。1 2 主要研究内容本文首先分析了都江堰灌区渠首配水的必要性和重要性以及研究配水问题的意义所在。接着系统学习了基本遗传算法的原理、实现技术、模式理论等，在介绍了传统优化算法不足的基础上，得出使用遗传算法进行优化的必然性并总结了遗传算法的特点。针对都江堰渠首配水问题，提出系统模型并相应地改四川大学硕士学位论文迸基本遗传算法。最后，构造了六大干渠的灌溉效益函数，进行优化配水的实例研究。本文主要研究的内容有：( 1 ) 分析基本遗传算法的原理和运行机制。讨论了传统优化方法及它们的不足之处，指出遗传算法在解决优化问题方面的优势。( 2 ) 针对本文研究的配水问题，对基本遗传算法进行改进，得到一种改进的遗传算法，主要包括以下几方面的改进：夺编码设计。比较了二进制和浮点数两种编码方式，由于本文变量变化范围较大，故采用浮点数编码：群体初始化。随机产生群体规模为p o p s i z e 盼个体，对适应度极差的个体直接抛弃，不加至u 初始群体中。确定适应度函数。适应度函数能有效指导搜索沿着面f 参数优化的方向进行，其选取是算法好坏的关键。遗传操作。包括选择、交叉、变异三步，这是遗传算法最关键的部分，夺控制参数的选择。控制参数选择恰当，可以大大减少程序运行时间，提高程序运行效率。算法终止条件。根据配水问题，确定算法终止的两个条件。( 3 ) 基于改进遗传算法的都江堰渠首配水研究夺都江堰灌区配水的一些基本概念和理论。夺在对系统分析的基础上，建立系统总体模型，提出灌溉效益最大模型。根据历史数据，运用经验法、常规估算法和多项式拟合的方法建立六大干渠的灌溉效益与配水量之间的函数关系；审运用改进遗传算法和基本遗传算法分别求解配水问题，对结果进行分析评价。1 3 本文结构第一章绪论，介绍课题提出的背景和研究意义以及本文进行的主要工作。第二章遗传算法概述，介绍了本文优化方法一遗传算法的些基础知识，包括遗传算法的基本思想、基本实现技术、模式理论和遗传算法与其他传统优化方法相比的优势。第三章是基于遗传算法的都江堰渠首配水模型和算法研究，4四川大学硕士学位论文在全面分析系统的基础上给出系统模型以及确定灌溉效益的方法。针对本文的配水问题，指出基本遗传算法的不足之处，提出改进的遗传算法。第四章是配水问题的仿真研究，建立六大干渠的灌溉效益函数，运用改进遗传算法求解，对结果进行分析。第五章是本文的结论部分，总结论文并提出今后有待进一步深入的工作。四川大学硕士学位论文第二章遗传算法概述生物的进化是一个奇妙的优化过程，它通过选择淘汰、突然变异，基因遗传等规律产生适应环境变化的优良物种。1 8 5 9 年达尔文创立了进化论，进化论作为生物界以及人类文明史上的一个里程碑，促进了科学技术的发展，形成了一种新的计算方法一遗传算法。遗传算法就是根据生物进化思想启发而得到的一种强有力的随机搜索和全局优化方法，以其简单、通用、鲁棒性强、适于并行处理以及应用范围广等特点，成为当今影响最广泛的智能优化算法之，赢得了许多应用领域 1 1 , 1 2 , 1 3 l 。本章概述了遗传算法的原理、实现技术、模式理论等，阐述了遗传算法较传统优化算法的特点等。2 1 生物进化和遗传算法【1 0 ，3 自然界的生物自有生命起，就开始漫长的生物进化历程。达尔文用自然选择( n a t u r a ls e l e c t i o n ) 来解释物种的起源和生物的进化，其自然选择学说包括以下三个方面：( 1 ) 遗传( h e r e d i t y ) 这是生物的普遍特性，亲代把生物信息交给子代，子代按照所得信息而发育、分化，因而子代总是和亲代具有相同或相似的性状。生物有了这个特征，物种才能稳定存在。( 2 ) 变异( m u t a t i o n ) 亲代和子代之间以及子代的不同个体之间总有些差异，这种现象称为变异。变异是随机发生的，变异的选择和积累是生命多样性的根源。( 3 ) 生存斗争和适者生存自然选择来自繁殖过剩和生存斗争。由于弱肉强食的生存斗争不断地进行，其结果是适者生存，具有适应性变异的个体被保留下来，不具有适应性交异的个体被淘汰，通过一代代的生存环境的选择作甩，物种变异被定向着一个方向积累，于是性状逐渐和原先的祖先种不同，演变为新的物种。这种自然选择过程是一个长期的、缓慢的、连续的过程。虽然人们对生物进化的一些细节还不是很清楚但一些进化理论的特性已经普遍被研究者接受。刘勇等在其著作【2 5 l 中对生物进化特性总结如下：6四川大学硕士学位论文进化过程发生在染色体上，而不是发生在它们所编码的生物体上；自然选择把染色体以及由它们所译成的结构的表现联系在一起，那些适应性好的个体的染色体经常比差的染色体有更多的繁殖机会；繁殖过程是进化发生的那一刻。变异可以使生物体子代的染色体不同于它们父代的染色体。通过结合两个父代染色体中的物质，重组过程可以在子代中产生有很大差异的染色体：生物进化没有记忆。有关产生个体的信息包含在个体所携带的染色体的集合以及染色体编码的结构中，这些个体会很好地适应它们的环境。总之，生物在进化过程中，经过优胜劣汰的自然选择，会使得种群逐步优化。经过长期的演化，优良的物种得以保留。不同的环境，不同物种的基因结构，导致最终的物种群不同，但它们都有一个共同的特征：最能适应自己所处的生存环境。遗传算法模拟的是怎样的生物进化模型呢? 假设对相当于自然界中的一群人的一个种群进行操作，第一步的选择是以现实世界中的优胜劣汰现象为背景的；第二步的重组交叉则相当于人类的结婚和生育；第三步的变异则与自然界中偶然发生的变异是一致的。人类偶然出现的返祖现象便是一种变异。由于包含着对模式的操作，遗传算法不断地产生出更加优良的个体，正如人类向前进化一样，所采用的遗传算法都与生物尤其是人类的进化过程相对应。表2 1 给出了遗传算法与生物进化之间的对应关系1 4 】。2 2 遗传算法的基本思想与生物的自然进化过程类似。遗传算法从代表问题可能潜在解集的种群尸( f ) ( f 代表遗传代数) 开始，其运算对象是由个个体所组成的种群，每一个个体均代表问题的一个潜在解，每一个个体都被评价优劣并得到其适应值。算法开始时，首先要进行编码，初代种群产生之后，对种群中的个体按其适应度进行选择，某些个体要经历称作遗传操作的随机变换，由此产生新的个体。主要有两种变换方法：杂交( c r o s s o v e r ) 的方法是将两个个体的有关部分组合起来形成新的个体；变异( m u t a t i o n ) 的方法是将一个个体改变，从而获得新的个体。新产生的个体( 称作后代( o f f s p r i n g ) c ( f ) ) 继续被评价优劣。从父代种群7四川大学硕士学位论文和子代种群中选择比较优秀的个体就形成了新的种群。在若干代以后，算法收表2 1生物进化与遗传算法之间的对应关系生物进化中的概念遗传算法中的作用环境适应函数适应性适应值函数适者生存适应函数值最大的解被保留的概率最大个体问题的一个解染色体解的编码基因编码的元素群体被选定的一组解( 以编码形式表示)种群根据适应函数选择的一组解( 以编码显示表示)交配以一定的方式由双亲产生后代的过程变异编码的某些分量发生变化的过程敛到一个最优个体，该个体很有可能代表着问题的最优或次优解。遗传算法中，将优化问题中的n 维决策向量彳= 鼍，屯，- ，x n 7 ，用h 个记号鼍( f = 1 ，2 ，”) 所组成的符号串x 来表示：肖= 墨x 2 以；爿= x l ，x 2 ，矗】7每一个x 。可看作一个遗传基因，它的所有可能取值称为等位基因，这样，z 就可看作是由”个遗传基因所组成的一个染色体( 或个体) 。最简单的染色体编码方法为二进制表示的符号串，编码所形成的排列形式是个体的基因型，与之对应的决策变量的值是个体的表现型。对于每一个个体z ，要按照一定的规则确定出其适应度。个体的适应度与其对应的个体表现型x 的目标函数值相关联。z 越接近于目标函数的最优点，其适应度越大；反之，其适应度越小。遗传算法中，决策变量x 组成了问题的解空间。对问题最优解的控索是通过对所有染色体所组成的搜索空间进行的，从而也就对应了对决策变量所组成的解空间的搜索。遗传算法的基本流程如图2 1 所示。四川大学硕士学位论文图2 1 遗传算法的基本流程遗传算法的一般结构可以描述如下：b e g i nt o初始化p ( t )评价p o )，w h i l e ( 终止条件不满足) d ob e g i n重组p ( t ) 以产生c ( f )评价c ( t )从p ( t ) 和c ( t ) 中选择p ( t + 1 )t t + 1e n de n d9四川大学硕士学位论文2 3 遗传算法的基本操作 2 , 1 0 , 1 5 , 1 8 , 2 2 3 1 编码解码编码是指将可行解从其解空间转换到遗传算法所能处理的搜索空间的转换操作。遗传算法中进化过程是建立在编码机制基础上的，编码对于算法的性能和效率影响很大。因此，编码技术是遗传算法设计中需要解决的首要问题和关键步骤。( 1 ) 编码的分类实际应用问题中的编码设计，要根据具体情况不同而进行设计。迄今为止已经提出了许多种不同的编码方法1 5 , 1 5 , 3 1 , 3 2 ，例如，为提高遗传算法局部搜索能力，提出了格雷码( g r a yc o d e ) 编码；为改善遗传算法的计算复杂性、提供运算效率，提出了实数编码：便于在遗传算法中结合所求解问题的专门知识，利于与相关近似算法之间的混和使用，提出了符号编码法；此外还有许多参数级联编码和交叉编码方法等等。下面我们简单介绍其中的几种编码。a 二进制编码二进制编码方法是遗传算法中最常用的一种编码方法，它仅使用二进制符号0 和1 所组成的二值符号集 0 、1 ) ，个体基因型是一个二进制符号串。二进制编码、解码操作简单，交叉、变异等遗传操作便于实现，而且便于利用模式定理进行理论分析等。但二进制编码存在连续函数离散化带来的映射误差，以及符号串的长度对问题的求解精度和算法运行效率有很大的影响等问题。特别是当编码串长度较长时，急剧扩大了搜索空间，大大降低了算法的效率。b 实数编码实数编码是指个体的每个基因值用某一个范围内的一个实数来表示，个体编码长度等于其决策变量的个数。实数编码对于函数优化问题最为有效。关于实数编码在函数优化和约束优化领域比二进制编码和格雷编码更有效的说法，已经得到了广泛的验证阳1 2 2 】。由于实数编码基因型空间中的拓扑结构与其表现型空间中的拓扑结构一致，因此很容易从传统优化方法中借鉴好的技巧来形成有效的遗传算予。本文在优化1 0四川大学硕士学位论文配水的实例中，由于决策变量搜索空间比较大，就采用了实数编码，将染色体基因与决策变量相对应，取得了较好的效果。c 整数和字母排列编码( 即符号编码)这种编码方法是指个体染色体编码串中的基因值取自一个无数值含义，而只有代码含义的符号集。如 a ，b ，c ，d ，) 、 1 ，2 ，3 ，4 ，) 等等。这种方法对于组合优化问题最为有效。由于组合优化问题最关键的是要寻找满足约束项目的最佳排列或组合，因此字母排列编码对于这类问题是最有效的方法。( 2 ) 编码的性质每当提出一种新的编码方式，就需要验证能否采用该编码建立有效的遗传搜索。关于评价编码方式的原财有如下几个方面伫3 - 2 9 1 ：a 不冗余( n o n r e d u n d a n c y ) ：从编码到解的映射应该是1 对1 的。b 合法性( 1 e g a l i t y ) ：对编码的任意排列都对应着一个解。该性质确保大多数现有的遗传算法操作可以被简单地应用于该编码。c 完备性( c q m p l e t e n e s s ) ：任意解都对照着一个编码。该性质确保空间中任惹点对于遗传搜索来说都是可达的。d l a m a r c k i a n 性质：某个基因的等位基因的含义不依赖于其他基因。关于编码的l a m a r c k i a n 性质考虑的是一个染色体能否将其价值通过常用的遗传操作传到将来的种群中的问题【1 】。e 因果性( c a u s a li t y ) ：由于变异带来的基因型空间中的小扰动在表现型空问中也对应着小扰动，该性质由r e c h e n b e r g 在关于进化策略的讨论中提出【2 3 1 。该性质强调保护邻域结构。也就是说，在变异算子带来有用的新信息的同时，它应该保留在对应表现型空间中的邻域结构。解码是编码的逆运算是由表现空间向问题空间的映射。本文实例中，由于采用了实数编码，染色体基因座与决策变量所代表的含义相同，因此不需要解码这一个步骤。四川大学硕士学位论文2 3 2 遗传算法的初始化遗传算法计算过程的开始步骤就是产生解向量的初始种群。最常用的初始化方法是随机初始化，产生一组在解空间内均匀分布的随机向量，通常一个随机向量就是种群中的一个个体。设置最大进化代数r 、群体规模m 、交叉概率e 、变异概率昂；设置进化代数计数器，卜0 ；随机生成m 个个体作为初始群体p ( o ) 。2 3 3 适应度函数遗传算法在进化搜索中基本不利用外部信息，仅以适应度函数( f i t n e s sf u n c t i o n ) 为依据，利用种群中每个个体的适应值来进行搜索。适应度函数是用来区分群体中个体好坏的标准。是算法进化过程的驱动力，因此适应度函数的选取至关重要，直接影响到遗传算法的收敛速度以及能否找到最优解。一般而言，适应度函数是由目标函数变换而成的。1 原始适应度函数：直接以待求解的目标函数作为个体的适应性度量。2 标准适应度函数：为了统一极大极小化问题，可以通过对原始适应函数进行标准化后作为遗传算法中的适应值函数，我们称变换后的函数为标准适应函数。若目标函数为最大化问题，则蒜小巍氓谊亿，式中c 。为( x ) 的最小值估计。若目标函数为最小化问题，则胁 苌 x 嚣z ，式中。为( 功的最大值估计。3 适应度函数的尺度变换l m 在遗传算法的初期，通常会出现一些超常的个体，这些个体因竞争力太突出而控制了选择过程，使算法过早收敛；在遗传算法后期，由于种群中个体适应度差异较小而使种群失去竞争压力导致停滞现象。为解决上述问题，我们应该对适应度函数进行尺度变换( f i t n e s ss c a l i n g ) 。目前常用的尺度变换方法主要有三种：线性变换法、幂函数变换法和指数变换法。2 3 4 搡作算子遗传算法的操作算子包括选择、交叉和变异。2 3 4 1 选择算子选择过程的第一步是计算适应度，每条染色体都有被选择的可能，遗传算法根据个体的适应度，使用选择算子( 也称复制算子) 来对群体中的个体进行优胜劣汰操作：适应度高的个体被选择，适应度低的个体被淘汰。对于不同的问题，人们提出了各种各样的选择算子，下面简单介绍几种选择算子：a 轮盘赌选择( r o u l e t t ew h e e ls e l e c t i o n )轮盘赌选择也称比例选择法或m o n t ec a r l o 法，是最简单也是最常用的一种方法。该方法是利用比例于各个个体适应度的概率决定其子孙的遗留可能性。假设种群大小为m ：某个体墨为种群中第f 个染色体，则可计算出其适应度为厂( 一) ，再根据，( 薯) 计算出个体的选择概率，由下式给出：只= 罟垫生( 2 3 )厂( 葺)t = l同时，计算出累积概率。然后产生m 个 0 ，1 之间的随机数，比较随机数和累积概率的大小来确定入选个体。具体运算步骤如下：( 1 ) 计算每个染色体的适应度值厂( 而) ；( 2 ) 累加所有染色体的适应度值，得最终累加值s u m = 厂( 而) ，同时也记录对于每个染色体的中间累加值s m i d ：四川大字坝士学位论文( 3 ) 产生一个随机数n ，0 n j “坍；( 4 ) 选择其对应的中间累加值s m i d n 的第一个染色体进入交换集；( 5 ) 重复( 3 ) 、( 4 ) ，直到交换集中包含足够多的染色体为止。下面给出一个例子来说明如何使用该方法。例2 1 种群规模为1 0 的一代种群，各个体的适应度、选择概率和累积概率如表2 2 所示，确定入选个体。表2 2 轮盘赌选择法的选择概率计算个体12345适应度5 32 10 57 31 5选择概率o 3 2o 1 30 0 30 4 40 0 8累积概率0 3 20 4 50 4 8o 9 21 0假设产生随机数序列为0 8 9 ，0 2 3 ，0 8 5 ，0 4 9 ，0 9 6 ，将该随机序列与计算获得的累积概率比较，如下图所示：个体123哇5图2 3 轮盘赌选择法则被选个体依次为序号4 ，i ，4 ，4 ，5 。显然适应度高的个体被选中的概率大，而且可能被选中；而适应度低的个体则很有可能被淘汰。本例中，个体2 和3被淘汰，代之以适应度较高的个体4 。b 最佳个体保存法( e l i t i s tm o d e l )最佳个体保存法是将当前群体中适应度最高的个体，不参与交叉运算和变异运算。而是直接复制到下一代中。此种选择操作又称为复制( c o p y ) 。它准确的定义是：设到时n t ( 第，代时) ，群体中口( ，) 为最佳个体。又设a ( t + 1 ) 为新1 4四川大学硕士学位论文一代群体，若其中不存在口( f ) ，则把它作为彳o + 1 ) 中的第伽+ 1 ) 个个体( 其中盯为群体大小) 。采用该选择方法的优点是进化过程中某一代的最优解不会被随机进行的遗传操作所破坏。但是这也隐含了一种危机，即局部最优个体的遗传基因会急速增加，而使得进化有可能陷于局部解。也就是说，该方法的全局搜索能力差，它更适合单峰性质的搜索空间搜索，而不是多峰性质的空间搜索。该方法一般应与其他选择方法配合起来使用。c 随机遍历抽样法随机遍历抽样法提供了零偏差和最小个体扩展。设定n p o j n t e r 为需要选择的个体数目，等距离选择个体，选择指针的距离为l n p o j n t e r ，第一个指针的位置由 0 ，i n p o i n t e r 区间的均匀随机数决定。d 锦标赛选择法在锦标赛选择法中，随机地从种群中挑选一定数目( t o u r ) 的个体，然后将最好的个体选做父个体。这个过程重复进行完成个体的选择。锦标赛选择的参数为竞赛规模t o u r ，其取值范围为 2 ，t o u r 。表2 3 表示了竞赛规模与选择强度之闻的关系。表2 3 竞赛规横与选择强度之闻的美系竞赛规模12351 03 0选择强度00 5 6o 8 51 1 51 5 32 0 4e 其他选择方法，包括( j + 五) 选择、局部选择法，截断选择法，排序选择法，繁殖池选择，b o l t z m a n n 选择等。2 3 4 2 交叉算子选择操作虽然能从旧种群中选择出优秀者，但不能创造新的染色体。因此，遗传算法的开创者提出了交换操作。交叉( 也称基因重组) 操作是按照一定的概率e 在配对库中随机地选取两个个体进行的。交叉的位置也是随机确定的。交叉率只的值一般取的很大，在0 6 到0 9 之间。交叉的目的是为了能在下一四川大学硕士学位论文代产生新的个体，使遗传算法的搜索能力得以飞跃地提高。这是遗传算法获取新优良个体的最重要的手段。交叉算子因算法的编码方式不同而有所不同，算子设计的好坏将直接影响到算法的收敛性和收敛速度。由于本文在配水问题中采用了实数编码的遗传算法，下面主要讨论实数编码下的交叉算子，简介二进制交叉。( 1 ) 实值重组a 。离散重组离散重组在个体之间交换变量的值，考虑如下含有三个变量的个体：父个体11 22 55父个体21 2 343 4子个体的每个变量可按等概率随机地挑选父个体，例如重组之后一个子个体为：子个体l1 2 32 55子个体21 243 4b 中间重组中间重组只能用于实变量，而非二进制变量。子个体按下列公式产生：子个体= 父个体1 + 口 ( 父个体2 一父个体1 )( 2 4 )这里口是一个比例因子，可由【- d ，l + d 】上均匀分布的随机数产生。对于中间重组d = 0 ，一般选择d = o 2 5 。子代的每个变量的值按上面的表达式计算。对每个变量要选择一个新的- t t 值。考虑含有三个变量的两个个体：父个体11 22 55父个体21 2 343 4口值的样本为：样本l0 51 1一o 1样本20 10 8o 5计算出新的子个体为：子个体1子个体2c 线性重组6 7 51 92 12 3 18 21 9 51 6四川大学硕士学位论文线性重组与中间重组比较相似，只是对所有变量只有一个口值。父个体11 22 55父个体21 2 343 4口值的样本为：样本10 5样本20 1计算出新的子个体为：子个体16 7 51 4 51 9 5予个体22 3 12 2 97 9( 2 ) 二进制交叉交叉算子有单点交叉( o n e - p o i n tc r o s s o v e r ) ，多点交叉( m u l t i p o i n tc r o s s o v e r ) ，均匀交叉( u n i f o r mc r o s s o v e r ) 等。我们主要介绍单点交叉。单点交叉中，交叉点k 的范围是 1 ，n v a t 一1 ，n v a t 为个体变量数目，在该点为分界相互交换变量。考虑如下两个l l 位变量的父个体：父个体iol1l0 01l010父个体2ldi0l1o 01o1交叉点的位置为5 ，交叉后产生两个子个体：子个体10ll101o oj01子个体21010l01l010父个体l子个体 二】一亡= 【二图2 4 单点交叉1 7四川大学硕士学位论文2 3 4 3 变异算子变异运算用来模拟生物在自然的遗传环境下由于各种偶然因素引起的基因突变，它以很小的概率圪随机地改变群体中个体( 染色体) 的某些基因的值。变异操作的基本过程是：对于交叉操作中产生的后代个体的每一基因值，产生一个 0 ，1 之间的伪随机数r a n d ，如果r a n d 0 为罚因子。2 3 6 遗传算法的终止条件遗传算法的终止条件，一般依据问题的不同有不同的确定方式。通常可以采用下面的准则之一作为结束条件：( 1 ) 种群中个体的最大适应度超过预先设定值；( 2 ) 种群中个体的评价适应度超过预先设定值；( 3 ) 世代数超过预先设定值。2 3 7 遗传算法优化实例下面以一个简单的优化问题为例，说明遗传算法求解问题的具体步骤：考虑下列一元函数求最大值的优化问题：厂( x ) = x s i n ( 1 0 万功+ 2 0 x - 1 ，2 】( 2 6 )用遗传算法求解此问题的步骤如下：( 1 ) 编码假设求解精确到6 位小数，由于区间长度为2 一( - 1 ) = 3 ，必须将闭区间 一1 ，2 分为3 1 0 0 等份。因为20 9 71 5 2 = 2 2 1 3 1 0 6 2 2 2 = 41 9 43 0 41 9四川大学硕士学位论文所以编码的二进制串至少需要2 2 位。( 2 ) 初始化一个个体由串长为2 2 的随机产生的二进制串组成染色体的基因码，我们可以产生一定数目的个体组成种群，种群的大小( 规模) 就是指种群中的个体数目。( 3 ) 解码将该种群中的每个个体转化为区间 一1 ，2 内的实数，转换公式详见参考文献 1 0 。( 4 ) 计算适应度对于个体的适应度计算，考虑到本例目标函数在定义域内均大于0 ，而且是求函数最大值，所以直接弓 用目标函数作为适应度函数；厂( j ) = f ( x )这里二进制串s 对应交量x 的值。( 5 ) 选择采用轮盘赌选择方法：产生一个在o l 之问均匀分布的随机数，此数位于哪一个小区间，则与该区间对应的个体被选中，重复弗次，就可以选出n 个个体。很明显，适应度大的给被选中的机会大，甚至有可能多次被选中，反之，适应度小的被选中的可能性就小，甚至不被选中。( 6 ) 交叉根据事先确定的交叉概率只，从选择后的甩个个体中，随机选择胛个个体( 若投只不为整数，还需将其取整) ，两两匹配，并随机选择一位作为交叉位，交换此位之后的内容。例如：匹配的两个个体是a ：b ：随机选择一个交叉点，如第5 位与第6 位之间的位置，交叉后产生的新的子个体：a ：b ：( 7 ) 变异四川大学硕士学位论文根据事先确定的变异概率匕，从门个个体的2 2 位中，随机选出1 2 n 位( - 若1 2 n 只不为整数，需要取整) 进行取反运算，即由0 变1 或1 变0 ，这样得到新一代的行个个体。( 8 ) 重复步骤3 7 ，直到种群中的最高适应度或平均适应度不再提高，则迭代过程收敛，算法结束。2 4 遗传算法的模式理论【1 町在遗传算法中，染色体是由一个字符串来代表的，而在分析字符串时，常常只关心某一位或某几位字符，即只关心字符串的某些特定形式，这种特定的形式，或者说在字符串中具有类似特征的子集，称为“模式”。在具体模式中，已有明确含义( 二进制字符时指o 或1 ) 的字符个数称为模式的阶次，记作d ( 日) ，其中日代表模式。模式中第一个和最后一个具有明确含义的字符之间的距离，称为模式的长度( 1 e n g t h ) ，记作8 ( h ) 。很明显，模式的阶次越低，模式的概括性越强，所代表的字符串个数也越多，而模式的长度代表该模式在今后遗传操作( 交叉、突变) 中被破坏的可能性，其长度越短，被破坏的可能性越小。2 4 1 选择对模式的影响假定在给定时间步，一个特定的模式日有m 个代表串包含在种群a ( t ) 中记为m = m ( 日，f ) 。在再生阶段，种群中的一个串4 的再生概率为 l ，当采j = l 乃用非重叠的, 个串的种群代替种群4 ( f ) ，可以得到下式：州( 何，f + 1 ) ：所( 圩，帅粤( 2 。7 )盖