（应用数学专业论文）改进遗传算法及其在降雨径流模型中的应用.pdf

坷海犬学硕士研究生论文 改进遗传算法及其在降雨径流模型中的压用 摘要 本文对遗传算法理论进行了系统的分析，指出了标准遗传算法的不足之处，提出了一种 改进的遗传算法。针对水文模型所出现的大量高维、多峰、非线- 肚、不连续、非凸性等复杂 的参数优选问题，考虑到遗传算法的优点，提出用改进遗传算法来解决。并将其成功地应用 在降雨径流模型的参数率定中，提高了水文模型参数优选的效率和解的精度。主要研究内容 如下： 1 给出了二进制遗传算法的一般模型和标准遗传算法的一般描述，介绍了遗传算法的 理论基础。 2 从模式定理的要求和遗传算法的收敛速度及求解精度之问的矛盾入手，提出了改进 遗传算法，在理论上分析了其收敛性，并j = j 典型测试函数验证了其在精度上较标准遗传算法 的优越性。 3 将提出的改进遗传算法应用在密赛流域三水源新安江模型的参数率定中，并取得了 较好的效果。计算结果表明改进遗传算法在精度上优于基本遗传算法。在改进遗传算法适应 度函数的选取上，做了理论上的分析和大照的实验，很好地结合了模型的目标函数和遗传算 法的适应度函数。 4 针对传统的单目标优化的弊端，提出采用修正的目标函数参数优选法。就密赛流域 三水源新安江模型的参数优选问题，通过和单目标参数优选的情况进行对比分析，结果表明： 修正的目标函数能较好地考虑到水文预报中各个要素之间的平衡约束关系，更好地满足人们 实际生产实践中的不同需求。 关键词：改进遗传算法、降雨径流模型、参数率定 珂海大学硕士研究生论文 改进遗传算法及其在降雨径流模型中的压用 a b s t r a c t t h et h e s i sm a k e ss y s t e m i ca n a l y s i so ft h ef u n d a m e n t a lt h e o r yo ft h eg e n e t i ca l g o r i t h m s ， p o i n t so u tt h es h o r t a g eo ft h es t a n d a r dg e n e t i ca l g o r i t h ma n dp u t sf o r w a r da ni m p r o v e dg e n e t i c a l g o r i t h m t h ec a l i b r a t i o no ft h em a n ym o d e l si nw a t e rr e s o u r c ei sv e r yc o m p l e x i ti sh i g h d i m e n s i o n sa n dn o n l i n e a r i ti sc o n v e xa n dn o tc o n t i n u o u s ，i th a sm a n yl o c a lo p t i m a c o n s i d e r i n g t h ee x c e l l e n c eo ft h eg e n e t i ca l g o r i t h m s ，t h et h e s i sp r o p o s e st oe l s et h ei m p r o v e dg e n e t i ca l g o r i t h m t os o l v et h ep r o b l e m so ft h em o d e lc a l i b r a t i o no ft h ew a t e rr e s o u r c e i nt h ec a l i b r a t i o no ft h e r a i n f a l l r u n o f fm o d e l ，t h et h e s i sa p p l i e st h ei m p r o v e dg e n e t i ca l g o r i t h ms u c c e s s f u l l ya n di m p r o v e s t h ee f f i c i e n c ya n dt h ep r e c i s i o n t h em a i na c h i e v e m e n t sa r ea sf o l l o w s ： 1 t h et h e s i sg i v e st h ed e s c r i p t i o no ft h eg e n e r a lm o d e lo ft h eb i n a r yg e n e t i ca l g o r i t h m sa n d t h es t a n d a r dg e n e t i ca l g o r i t h m ，a n di n t r o d u c e st h ef u n d a m e n t a lt h e o r yo ft h eg e n e t i ca l g o r i t h m s 2 b a s e do nt h ec o n t r a d i c t i o no ft h er e q u i r e m e n t so ft h es c h e m at h e o r ya n dt h ec o n v e r g e n t s p e e da n dt h ep r e c i s i o no ft h er e s u l t so ft h eg e n e t i ca l g o r i t h m s ，t h et h e s i sp r o p o s e sa ni m p r o v e d g e n e t i ca l g o r i t h m f u r t h e r m o r e ，t h et h e s i sa n a l y z e si t sc o n v e r g e n c ei nt h e o r ya n dp r o v e si t s a d v a n t a g ei np r e c i s i o n ( c o m p a r e sw i t ht h es t a n d a r dg e n e t i ca l g o r i t h m ) b yu s i n gt h et o o lo ft y p i c a l l e s if u n c t i o n 3 a p p l y i n gt h ei m p r o v e dg e n e t i ca l g o r i t h mt ot h ec a l i b r a t i o no ft h et h r e e s o u r c e x i n a n j i a n gm o d e l ，t h et h e s i sg e t sb e t t e rr e s u l t si nw h i c hs h o w st h ea d v a n t a g eo ft h ei m p r o v e d g e n e t i ca l g o r i t h m i nt h ep r o c e s so ft h es e l e c t i o no ft h ef i t n e s sf u n c t i o n ，t h et h e s i sd o e sl o t so f t h e o r e t i c a la n a l y s i sa n de x p e r i m e n t s ，f i n a l l yc o m b i n e st h eo b j e c t i v ef u n c t i o na n dt h ef i t n e s s f u n c t i o nt o g e t h e ra p p r o p r i a t e l y 4 a c c o r d i n gt ot h es h o r t a g eo ft r a d i t i o n a ls i n g l e o b j e c t i v eo p t i m i z a t i o n ，t h et h e s i sp r o p o s e s t ou s ea m e n d a t o r yo b j e c t i v ef u n c t i o np a r a m e t e r so p t i m i z a t i o n b yt h ec o m p a r i s o no ft h er e s u l t so f t h em i s a iv a l l e yi ts h o w st h a tt h ea m e n d a t o r yo b j e c t i v ef u n c t i o np a r a m e t e r so p t i m i z a t i o ni sb e t t e r b e c a u s ei tp a y sm o r ea t t e n t i o nt ot h eb a l a n c er e l a t i o n s h i po ft h ee s s e n t i a lf a c t o r sa n dc a nf u l f i l l t h ed i f f e r e n tr e q u i r e m e n t so ft h es o c i a la c t i v i t i e 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 m ，r a i n f a l l r u n o f fm o d e l ，p a r a m e t e rc a l i b r a t i o n 1 1 学位论文独创性声明： 本人所呈交的学位论文是我个人在导师指导卜进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致 谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工 作的同事对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。如不实，本人负全部责任。 论文作者( 签名) ：盔盘也“年乡月刀e t 学位论文使用授权说明 河海大学、中国科学技术信息研究所、国家图书馆、中国学术 期刊( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件或 电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子 文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外， 允许论文被查阅和借阅。论文全部或部分内容的公布( 包括刊登) 授权 河海大学研究生院办理。 论文作者( 签名) ：蕉墼生伽f 年；y - t 歹拿日 河海大学硕士研究生论支改进遗传算法及其在降雨径流模型中的压用 第一章绪论 1 1 遗传算法的理论原型 自然界充满了奇迹，而生命的繁衍生息则是这些奇迹中的奇迹。生命从单 细胞开始经过复杂的演化，不但延续下来，产生了众多的生命体，而且还产生了 人类这样有思维和智力的高级生命体。1 9 世纪中叶，查儿斯达尔文( c h a r l e s d a r w i n ) 在总结前人进化思想的基础上，用大量的科学事实证明了生物进化过程 在总体上表现为：从低级到高级，从简单到复杂，从单一适应到多种适应，从不 完善形式到完善形式发展。达尔文认为，生物进化的动力和机制在于自然选择。 自然选择以变异为基础，通过生存斗争实现。有利于适应环境的变异个体，在生 存斗争中将会有更多的机会生存和繁衍，而适应性差的个体将被逐渐淘汰，因此， 生物进化是“物竟天泽，适者生存”的过程。 人类找到了生命的最佳结构和形式，不仅可以被动的适应环境，更重要的是 能够通过学习和创造不断提高自己适应环境的能力。自然演化过程是一个学习与 优化的过程，这一优化过程的目的是使生命体达到适应环境的最佳结构与效果。 人类直立行走解放出双手是来自于类人猿求生的努力，而正得益于这双手，人类 才有了现在主宰世界的地位；青蛙的存活依靠其水陆两栖，左右逢源的能力；而 曾经主宰地球的恐龙却由于它庞大的身躯适应不了环境的变迁而灭绝。自然演化 的规律完美而奇妙。所以人们完全有必要向生命的演化过程学习以增强决策问题 的能力。 按照孟代尔的遗传学理论，遗传物质作为一种指令密码封存在每一个细胞， 并以基因的形式排列在染色体上，每个基因有确定的位置并控制着生物的某种特 性。由不同的基因组合产生的个体对环境的适应程度不一样，通过基因的杂交与 变异可以产生对环境适应性高的后代，经过优胜劣汰的自然选择，适应性高的基 因结构保存下来，从而逐渐形成了经典的遗传学染色体理论，它揭示了遗传和变 异的基本规律。现代遗传学和医学则对基因的功能、结构、突变和调控进行了深 入研究，开辟了遗传工程研究的新领域。 基因结构的稳定性保证了生物种群的稳定性，基因组合的多样性决定了生物 体的多样性，而基因的杂交和变异使生物进化成为可能。生物的遗传就是通过父 代向子代传递基因来实现的，而某些遗传信息的改变导致了生物体的变异。 因此，生物进化过程的发生需要三个基本条件：存在有众多个体组成的种群， 这是选择与杂交的基础；生物个体之间存在差异即或生物种群的多样性；个体生 物对环境适应能力有强有弱，具有优良基因结构的个体繁殖能力强，反之则弱。 f t 进连传茸击醍乓在降雨径流模型6 的压用 而生物的进化机制可以分为= 种基本形式： 1 自然选择；能够适应环境变化的牛物个体具有较高的生存能力，使得 他们在种群中的数量不断增加，l j 叫浚生物个体所具有的染色体性状特征在自然 选择中得以保留。自然选择确定了生物体群体的发展方向。自然界中恐龙的灭亡 干u 人炎的兴盛便是很好的例子。 2 交叉：生命繁衍过程中，随机组合柬自父代的染色体上的遗传物质， 产生不同于他们父代的新的染色体。从而产生了有父代部分特征的新的生物个 体。如子女和父母双亲的相似性及相异性。 3 变异：以较小的概率随机改变父代个体的染色体上的某些基因结构， 产生具有新的染色体的子代生物个体。变异是一种不可逆过程，具有突发性、间 断性和不可预测性，它对于保证群体的多样l 生具有不可替代的作用。变异有好的 变异有差的变异。而通过自然选择h 有好的变异会被更多的保留下来。 1 2 遗传算法的发展历史 遗传算法( g e n e t i ca g o r i t h m s ，简称g a ) 起源于刘生物系统所进行的计算机 模拟研究。早在2 0 世纪5 0 年代，一些生物学家就着手于计算机模拟生物的遗传 系统。6 0 年代，就有少数科学家进行了所谓“人工进化系统”的研究，其出发 点是进化的思想可以发展成为许多工程问题的优化工具。 1 9 6 7 年，美国芝加哥大学j o h nh o l l a n d 教授的学生b a g l e y “。在其博士论文 中提出“遗传算法”一词，这是第篇关于遗传算法的文章。该文采用双倍体编 码，芨展了与目前机制类似的复制、交换、突变、显性、倒位等基崮操作，形成 了遗传算法的雏形。 1 9 6 8 至1 9 7 1 年，h o l l a n d 提出了重要的模式理论，h o l l a n d 首次采用二进 制编码来研究函数优化问题，并指出了运用g r a y 码的一些优点，他研究了从生 物系统引申出的各种小同的选择和配对策略出的各种不同的选择和配对策略。 h o | 1 a n d 的模式理论也渐趋成熟，但在编码策略r m 现了至今仍执争论的二派， 一派根据模式定理建议用尽量少的符号编码，一派以数值优化计算的方便和精度 为准采用一个基因一个参数的方法，并把相应的基因操作改造成适合实数操作的 形式，b o s w o r t h ，z o o 和z e i g l e r “是后者的开创者。 1 9 7 5 年，j o h nh o l l a n d 教授的专著“1 自然界和人工系统的适应性 ( a d a p t a t i o ni nn a t u r a la n da r t i f i c i a ls y s t e m s ) 问世，全面地介绍了遗传 算法，不仅设计了遗传算法的模拟与操作原理，更重要的是，他运用统计决策理 论对遗传算法的搜索机理进行了理论分析，建立了著名的模式( s c h e m a ) 定理和 隐合并行性( i m p l ic i tp a r a l l e l js m ) 原理，为遗传算法的发展奠定了基础。将遗 传算法用于卤数优化归功于h n l1a n d 的学生d ejc l n g ”1 ，他于同年在其博l 论文 传算法用于函数优化归功于e o l 】a n d 的学生d ej o n g ”1 ，他于同年在其博t 论文 河海大学硕士研究生论文 改进遗传算击及其在降雨径流模型中的应用 中设计了一系列遗传算法的执行策略和性能评价指标，对遗传算法性能做了大量 的分析。d ej o n g 精心挑选的5 个实验函数( 称作d ej o n g sf i v et e s tf u n o t i o n s ) 也是目前遗传算法数值实验中用的最多的实验函数。因此1 9 7 5 年也被公认为是 遗传算法的诞生年。 2 0 世纪8 0 年代中期以来是遗传算法的蓬勃发展期。以遗传算法、进化计算 为主题的多个国际会议在世界各地定期召开。1 9 8 5 年，在美国卡附基梅降大 学召开的第一届国际遗传算法会议i c g a 8 5 ，并成立了国际遗传算法叻、会 ( i s g a ) ，规定遗传算法及其应用国际会议每两年召开一次，有关人工智能的会 议上和刊物上也列有遗传算法的专题。 1 9 8 9 年美国伊利诺大学的g o l d h e r g ”。出版了g e n e t i ca l g o r i t h m si n s e a r c h ，o p t i m i z a t i o na n dm a c h i n el e a r n i n g 一书，系统地总结了遗传算法 地主要研究成果，全面完整地论述了遗传算法的基本原理及其应用，有力的推进 了遗传算法的传播。 1 9 9 7 年夏季在美国密歇根大学召开了i c g a 9 7 。现在与之平行进行的国际 会议很多，其中i n t e r n a t i o n a lc o n f e r e n c eo ne v o l u t i o n a r yp r o g r a m m i n g 和 i e e ei n t e r n a t i o n a lc o n f e r e n c eo ne v o l u t i o n a r yc o m p u t a t i o n 也分别召开了 6 届和4 届。此外，每年夏季在美国斯坦福大学召开有关遗传程序设计国际会议 ( t h ea n n u a lc o n f e r e n c eo fg e n e t i cp r o g r a m m i n g ) 。有关遗传算法基础理论 的学术活动也很活跃，第一届遗传算法与分类系统研讨会( t h ef i r s tw o r k s h o p o nt h ef o u n d a t i o n so fg e n e t i ca l g o r i t h m sa n dc 1 a s s i f i e rs y s t e m s ，f o g a c s ) 1 9 9 0 年在美国印第安那大学召开，以后每隔两年召开一次。 进入九十年代，以不确定性、非线性、时间不可逆为内涵，以复杂问题为对 象的科学新范式得到学术界普遍认同，由于遗传算法能有效地求解属于n p c 类型 的组合优化问题及非线性多模型、多目标的函数优化问题，从而得到了多学科的 广泛重视，一些学者也认识到求解复杂问题最优解是不现实的，故而寻求满意解 ( 6 至今，遗传算法已经有了很大的发展，并开始渗透到自适应行为、人工智能、 神经网络、机器人、运筹学、人工生命等领域，成为当前国际学术界和工程界跨 学科的热门研究课题。德国d o r t m u n d 大学1 9 9 3 年末的一份研究报告表明，根据 不完全统计，遗传算法已在1 6 个大领域、2 5 0 多个小领域中获得了应用。遗传 算法在机器学习、过程控制、经济预测、工程优化等领域取得的成功，已引起了 数学、物理学、化学、生物学、计算机科学、社会科学、经济学及工程应用等领 域专家的极大兴趣。由于遗传算法在应用研究方面的长处主要得益于其求解的有 效性、现有仿真环境下易于实现、可扩充性和易于与其他方法相结合，可以预料 在不远的将来，随着理论研究的不断深入和应用领域的不断拓广，遗传算法将取 j 可海文学硕士研究生论支 改进遗传算法及其在降雨径流模型中的应用 得长足的发展。 1 3 遗传算法的研究现状 1 3 1 遗传算法的理论研究现状 目前，关于遗传算法基础理论的研究主要是从以下几个方面进行： 1 模式定理与隐含并行性定理，是遗传算法的数学基础。 h 0 1 l a n d 的模式理论。”奠定了遗传算法的数学基础，根据隐性并行性得出的 每一代处理有效模式的下限值”是。，玎c l m l ，其中n 是种群大小，l 是串长， c 是小整数，文献 3 把结果简化为。，。建筑块假设从定性的角度解释了模式定 理的有效性，它们一起组成了解释遗传算法运行机理的数学工具。在建筑块假设 成立与否的问题上，目前的工作主要集中在遗传算法的欺骗函数的研究上。所谓 欺骗函数就是那些对遗传算法进行误导，使其错误的收敛到非全局最优解状态的 函数。一旦研究清楚一卜函数是遗传算法的欺骗函数的条件，也就给出了建筑块 假设成立的条件。研究欺骗函数问题的主要方法是w a l s h 变换。 2 遗传算法的马尔可夫链( 马氏链) 分析。 遗传算法中使用了大量的随机操作，所以遗传算法是一个随机搜索算法。研 究者们建立了不同形式的马氏链模型对遗传算法的极限行为进行各种角度的刻 画。对于有限的编码空间和有限的种群，遗传算法的搜索过程可以表示为离散时 间的马尔可夫链模型。1 9 8 7 年，6 0 l d b e r g 和s e g r e s t ”1 首次运用有限马尔可夫链 理论对遗传算法进行了收敛性分析。此后，基于有限状态马尔可夫链模型分析各 种遗传算法的收敛性的研究较为广泛”3 。这些分析在遗传算法的全局收敛性方 面取得了一定的突破，但他们的结论基于分析特定条件下的遗传算法模型，复杂 遗传算法的收敛性分析仍然是相当困难的。 在v o s e 模型中，种群的状态由一个维数为所有可能个体的数目的概率向量 表示，其中第f 个分量表示第f 个个体在种群中占的个数比例( 相对频率) 。在 种群规模无限大的假设下，相对频率就表示每一个个体在种群中出现的频率，这 样便可以导出表示种群的概率向量的迭代方程，从而研究种群概率向量的不动点 及稳定性，刻画遗传算法的极限行为。详见文献”“。 法国学者r c e r f 将遗传算法看成一种特殊形式的广义模拟退火算法模型， 利用动力系统的随机扰动理论对遗传算法的极限行为及收敛速度进行了研究。 3 遗传算法的早熟收敛问题。 遗传算法中，一个较为普遍的现象是存在过早收敛的问题，即种群收敛现象 发生在种群演化到非全局最优状态，它使得算法的继续迭代已经不能产生更好的 可行解。文献 5 和 1 2 提出了遗传算法的早熟收敛现象，并提出了一些克服的 珂海欠学硕士研究生论文 改进遗传算法及其在降雨径流模型中的压用 办法，但是没有对早熟的起因、表现形式和预防措施进行系统研究。徐宗本 等经过仔细的理论研究，提出交叉运算成熟化效应是过早收敛的起因，并提出了 相应的预防措施。 4 遗传算法的编码方式。 编码对遗传算法的搜索效果和效率有重要影响。遗传算法中通常采用定长编 码，但这种方法的优化精度不高。为此，s c h r a u d o l p h 提出动态编码( d y n a m i c p a r a 【l e t e r e n c o d i n g ) “”动态的改变自变量的定义域。当种群已经收敛，则缩小自 变量的范围，从而在全局最优解的附近进行精确搜索。这样通过改变编码长度来 协调搜索进度和效率之间的关系。试验表明，通过对d ej o n g 的五个函数的测试， 显示了较高的精度。 h o l l a n d 模式定理建议采用二进制编码，这得到许多学者。1 的支持。但由于 浮点数编码有精度高、便于大空间搜索的优点，浮点数编码越来越受到重视“。”3 ， h i c h a l e w i c z “”比较了两种编码法的优缺点。最近q i 和p a l m i e r “”对浮点数编 码的遗传算法进行了较为严密的数学分析，用m a r k o v 链建模，进行了全局收敛 性分析，但其结果是基于群体数为无穷大这一假设的。由于编码是遗传算法应用 中的首要问题，因此建立完善的理论上指导是必要的，二进制编码的进化层次是 基因，而浮点数编码的进化层次是个体，用前者理论来指导后者是不合适的。 5 遗传算法的算子设计。 遗传算法的算子主要包括选择、交叉和变异，适应度尺度变换等，另外，还 有如删除、显性、倒位、分离和易位、迁移等，由于应用的较少在此不作详细介 绍。这部分内容的研究在遗传算法理论研究中最为丰富。 发展各种选择操作的目的是为了避免基因缺失，提高全局收敛性和效率，目 前为止选择算子的类型主要有：随机抽样“1 ，均匀排序“，稳态复制“，保留晟 优个体。”等。选择的主要思想是染色体的选择概率正比于其适应度。交叉操作的 作用是组合出新的个体，在编码空间进行有效搜索，但是同时必须尽量减少对有 效模式的破坏，交叉操作是遗传算法区别于其它进化算法的重要特征“，用不同 的编码方式所用的交换策略不一样，目前二进制编码的主要交叉策略有：单点交 叉。“，双点交叉“ 2 ，多点交叉“”1 ，均匀交叉“”等。模块假说。t ”建议用单 点交叉，s y s w e r d a ”3 的函数优化实验研究表明，均匀交叉比单点交叉和双点交 叉好，b o o k e r 的研究”1 认为双点交叉比单点交叉好。交叉操作的许多重要特性及 适用范围有待深入研究。在交叉操作之前必须首先配对，目前常用的配对策略是 随机配对。当交叉操作产生的后代的适应度不再比它们的前辈好又未到全局最优 解时，就会发生早熟收敛，早熟收敛的根源是发生了有效基因缺失o “，这时，为 克服这种情况，只有依赖于变异，但常规位变异的效果是不明显又很慢的，变异 在遗传算法中的作用是第二位的，目前二：进制编码的主要变异操作有：常规位变 珂海走学硕士研究生论更 改进遗传算法及其在降雨径流模型中的应用 异”1 ，有效基因变异”“，自适应有效基因变异”。哜口概率自适应变异。 6 遗传算法参数的选择。 遗传算法中需要选择的参数主要有串长f ，群体大小n ，交叉概率以及变异 概率己等，这些参数对遗传算法性能影响很大。二进制编码时，串长f 的选择取 决于特定问题解的精度。为了选择合适n ，e 和只，许多学者进行了研究。 s c h a f f e r ”“建议的最优参数范围是：n = 2 0 3 0 ，只= o 0 5 0 2 5 ，只= o 0 0 5 0 0 1 ，文献 2 3 建议n 的选择与所求问题的非线性程度相关，非线性越大，n 越 大。在简单遗传算法或标准遗传算法中，这些参数是固定的。目前许多学者认识 到这些参数需要随着遗传进程而自适应变化，这种有自组织性的遗传算法具有更 高的鲁棒性、全局最优性和效率”。2 ”。在今后的研究中，遗传算法结构、基因操 作和参数都会向自组织的形式发展并将进行系统的综合。 7 混合遗传算法研究。 遗传算法的一个优点是易于和其它算法结合。g o l d b e r g “3 等研究了遗传算法 和梯度法、爬山法等局部搜索方法的结合，取得了较好的效果。p e t e r s e n ”利 用旅行商问题比较研究了遗传算法、模拟退火和人工神经网解决组合优化问题的 能力，结果显示遗传算法性能较优。l i n 等”。3 把遗传算法和模拟退火。“进行综合， 构成模拟遗传算法，在解决几种n p 完全问题中显示了良好的性能。 1 3 2 遗传算法的应用研究现状 遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题具 体的领域，对问题的种类有很强的鲁棒性，所以广泛应用于许多学科。近十年来， 遗传算法得到了迅速发展。目前，遗传算法在很多科学、工程领域都得到了广泛 的应用。其典型应用领域如下： 1 复杂的非线性优化问题 函数优化是遗传算法的经典应用领域。对于具有多峰的非线性优化问题，普 通优化算法一般很难达到全局最优解。而遗传算法可以克服这一缺点，在整个问 题空间搜索，找到全局最优解。 2 复杂的组合优化问题 随着问题规模的扩大，组合优化问题的搜索空间也急剧增大，按现在的计算 条件用枚举法不能得到问题的最优解。如经典的组合优化问题：背包问题 ( k n a p s a c kp r o b l e m ) 、旅行商问题( t s p ) 、图划分等“3 ”适于采用遗传算法解决。 其中t s p 问题己被广泛的应用于评价不同遗传操作及选择机制的性能。 3 图像处理，模式识别 坷海走学硕士研究生论文改进遗传算法及其在降雨径流模型中的应用 大量的文献将遗传算法应用于边缘检测、图像分割”、自动目标识别等领 域。文献 3 5 用遗传算法大大缩短了图像纹理边缘检测的处理时间，取得了较好 的效果。在工程应用领域，如美国军方的休斯遗传程序系统。”3 ( h u g h e sg e n e t i c p r o g r a m m i n gs y s t e m ) 在判别红外图像的目标方面，效果很好。美国新墨西哥州 立大学开发的f a c e p r i n t 系统。根据目击者的描述生成嫌疑犯的面貌，并利用遗 传算法生成新的面貌。 4 分类系统和神经网络 遗传算法被用于模糊控制规则的学习，利用遗传算法学习隶属度函数，从而 更好地改进了模糊系统的性能。遗传算法与神经网络的结合是目前发展的一个趋 势，这一点可以从很多文献中看到”1 。如优化神经网络的权系数和网络的空间结 构，选择n n 的学习规则与算法参数，分析神经网络的性能等。”。y a o ”给出了该 方面的详细综述。该领域的研究显示了良好的性能和潜在的应用前景。 5 机器人智能控制 机器人复杂的难以精确建模的人工系统，而遗传算法来源于对人工自适应系 统的研究，所以自然被用于机器人智能控制。据i e e ee x p e r t ( 9 4 4 ) 报道，美 国海军的s a m u e l 系统利用遗传算法控制计算机模拟军舰的操作和作战规划，如 导航、导弹躲避和跟踪等。 6 工程应用 遗传算法广泛应用于工程领域。如生产调度“o “3 ，工程结构优化，任务分配， 自动控制“2 。4 。，通讯网络的优化设计，大规模集成电路的布线设计，参数辨识” 等领域。 7 遗传程序设计 k o z a “5 1 删发展了遗传程序设计的概念，他使用l i s p 语言编码，基于对一种树 型结构所进行的遗传操作自动生成计算机程序。并成功地用于人工智能、机器学 习、符号处理“5 删。 1 4 遗传算法的特点 1 4 1 遗传算法与传统方法的比较 优化计算问题的多样性使人们提出了各种不同的优化算法，如梯度法、动态 规划法、穷举法、蒙特卡罗法等。不同的优化算法有其自身的特点和适用的范围， 也有一定的局限性。 传统搜索算法主要有三种类型： 1 解析法。解析法寻优是研究最多的方法，一般可分为直接法、间接法。 直接法是根据梯度信息按最陡的方向逐次运动柬寻求局部极值，即爬山法。唰接 = i 可海大学硕士研究生论文 改进遗传算法及鼻在降雨径流模型中的应用 法是通过让目标函数的梯度为零，进而求解一组非线性方程来寻求局部极值。一 般而言，如果目标函数连续可微，方程比较简单，解空间维数较少时，解析法是 适用的。它的主要缺点是：只能寻找局部极值而非全局极值；要求目标函数是连 续光滑的，而且需要导数信息。这两点使解析法的鲁棒性较差。鲁棒性 ( r o b u s t n e s s ) 是指能在许多不同环境中通过效率及功能之间的协调平衡以求生 存的能力。 2 枚举法。枚举法枚举出可行解集合内的所有可行解，以求出精确最优解。 对于连续函数，该方法要求先对其进行离散化处理，这样就可能困离散处理而永 远达不到最优解。此外，当枚举空间比较大时，该算法的求解效率比较低，即使 是动态规划法也遇到指数爆炸的问题。 3 随机搜索法。随机搜索法通过在搜索空间中随机的漫游并随时记录下所 取得的最好结果。但该算法得出的并非最优值，本质上仍然是一种枚举法。 这些算法对于目标函数连续可微，单峰，解空间较小的情况较为适用，而对 于多峰且具有较大解空间的问题效率明显下降。 遗传算法是一类以达尔文自然进化论与遗传变异理论为基础的求解复杂全 局优化问题的仿生型方法，是模拟自然界生物进化过程与机制求解极值问题的一 类自组织、自适应人工智能技术。它是一种宏观意义下的仿生算法，通过模 拟达尔文“优胜劣汰、适者生存”的原理和孟代尔的遗传变异理论在迭代过程中 保持已有的结构，同时寻找更好的结构：它适合于无表达式或有表达的任何类函 数，具有可实现的并行计算行为；它能解决任何类实际问题，具有广泛的应用价 值。遗传算法是一个利用随机化技术对一个被编码的参数空间进行高效搜索的方 法，遗传算法具有十分顽强的鲁棒性，与传统的搜索方法不同，它采用了许多独 特的方法和技术，归纳起来主要有以下四个方面： 1 遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接利 用决策变量值本身来进行优化计算，但遗传算法是以决策变量的某种形式的编码 作为运算对象。这样就可以借鉴生物学中的染色体和基因等概念，模仿自然界中 生物的遗传和进化机制的机理，对于一些无数值概念或很难有数值概念的优化问 题，如各种组合优化问题，编码处理方式显现出了独特的优越性。 2 遗传算法使用概率搜索技术。确定的搜索算法指一个搜索点到另一个搜 索点的转换规则是确定的。按照这一定义遗传算法就不是确定性搜索算法。算法 中交叉变异等操作是随机选择被操作个体，以产生下一代个体，即遗传算法的搜 索点并不是依据确定规则给出的，但遗传算法又比一般的随机搜索技术的效率要 高得多，这仅由遗传操作的随机性来解释，更源于遗传算法的选择压力。这就如 同自然界的自然选择迫使生物“向适应环境的方向搜索基因结构”。选择的压力 决定了遗传算法是有方向的，它使个体适应度或种群平均适应度不断增加从而增 河海大学硕士研究生论文 改进遗传算法及其在降雨径流模型中的应用 加了搜索效率。遗传算法属于一种自适应的概率搜索技术，实践和理论都已证明， 在一定条件下遗传算法总是能以概率l 收敛于问题的最优解。 3 遗传算法直接以目标函数值作为搜索信息。传统的优化算法不仅需要利 用目标函的数值信息，而且一般也需要目标函数的导数等其他一些辅助信息才能 确定搜索方i 向。遗传算法仅使用由目标函数值变换得到的适应度函数值的信息， 就可以确定进一步的搜索方向和搜索范围，无需其它辅助手段。这个特性使很多 目标函数无法或难于求导的问题，或导数不存在的函数的优化问题，以及组合优 化等问题，应用遗传算法就显得较为方便。并且直接利用目标函数值和个体适应 度值，也可以把搜索范围集中到适应度值较高的部分空间中，从而提高了搜索效 率。因此遗传算法对于大规模、高度非线性的不连续的多峰值函数的优化以及无 解析表达式的目标函数的优化，具有很强的通用性。 4 遗传算法同时使用多个搜索点的搜索信息。许多传统搜索算法都是单点 搜索算法，对于多峰分布的搜索空间，常常会陷于局部的某个单峰的优解，而遗 传算法的操作对象是一组可行解，即同时对搜索空间中的多个解进行评估。这一 特点使遗传算法具有较好的全局搜索性能和良好的全局收敛性能。减少了陷入局 部最优解的风险，同时这使遗传算法本身也十分易于并行化。 这使遗传算法具有以下优点： 1 应用的广泛性：易于写出通用算法，求解不同优化问题，只需少量改变 算法，即可适用于不同问题。 2 可扩展性：易于和别的技术相融合。 3 不需要辅助信息：其他多数算法都需与可导、线性、凸性等性质相联系， 遗传算法只需适应度函数为非负，可用于具有高度非线性问题的寻优。 4 易于并行实现。 5 遗传算法对给定问题，可以产生许多的潜在解，最终选择可以由使用者 确定。如多目标优化问题不止一个解存在，而是一组解。故对于确认可替代解集 而言是特别合适的。 1 4 2 遗传算法的不足之处 尽管遗传算法与传统方法相比有很多优点，但是遗传算法也有其不足之处， 主要表现在以下几个方面： l _ 编码的不规范性及编码表示的不准确性： 2 遗传算法本身不能表示问题的约束条件； 3 遗传算法容易出现早熟现象； 4 遗传算法对算法的精度、可信度、算法复杂性方面还没有有效的定量分 析方法。 河j 每太学硕士研究生论文 改进遗传算法及其在降雨径流模型中的应用 1 5 概念。 生降雨径流模型简介 入与自然要和谐发展，离开自然人类无法生存，但是自然灾害也会给人类带 来惨重的灾难。人类为了生存发展，要与自然和谐相处，尽可能的减轻自然灾害 带来的损失，就必须先认识自然。为了避免洪涝灾害给人类生存带来的苦难，人 们在不断总结经验教训中逐渐认识到了自然界的水文现象及其运动、变化规律， 发展了水文科学。当人们掌握了这些水文规律后就可以对出现的水文现象进行分 析，并对随之将发生的水文事件作出预测，从而指导人们做出相应的部署以兴利 除害。 传统的水文计算往往采用各种经验相关的方法，如水位流量关系、降雨径流 相关图、单位线等等”。它们都是针对单独的一个水文环节( 如产流、汇流等) 进行的，没有把整个降雨径流过程当作一个完整的系统考虑其整体的运行机理。 无法很好的考察降雨的时空变化和流域状态对径流产生的影响。而且在建立经验 关系时，往往带来较大的主观性。在实际应用中也很难解决本流域内资料范围以 外的外延与对缺乏水文资料地区的外延问题。因为经验相关是统计规律，原则上 只能用于样本条件范围内的内插，不能用于范围外的外延。 随着计算机科学的普及和发展以及水文科学技术的提高，人们开始把水文的 表面过程作为一个完整的系统来研究，提出了“流域模型”的概念，从定量上分 析流域出口断面流量过程线形成的全部过程，6 0 年代提出了不少概念性降雨径 流模型。流域水文模型应用范围非常广泛。它比过去传统的方法可以考虑更细更 多的因素，使用与实际水文过程尽可能接近的数学函数，可以模拟各种时段长的 径流系列。由于模型可以输出出流断面的流量过程，据此可以取得日平均流量， 洪水的流量过程，年、月、次产流量等基本资料，因此可以用于插补短缺资料。 1 6 概念- 生降雨径流模型参数的率定 概念性降雨径流模型是以流域为系统，降雨径流形成理论为基础，模拟经概 化和简化后的流域降雨径流形成过程。当模型的结构已选定时，通过给定的输入 ( 降雨量及蒸散发量) 和输出( 径流过程) 求出模型的参数，称为参数率定“。 一个流域模型通常具有多个参数，少则十多个，多则几十个，目前还不能像 解方程组那样把它们一次求得。即使能做到一次求得，由于输入输出资料含有误 差，求出的参数在物理意义上可能完全不合理。因此，参数率定的技术直接影响 所建模型的模拟效果“。赵人俊“，林三益“”给出了人工调试法的一些经验，杨 晓华”“”1 ，谭炳卿“2 1 等给出了参数自动优选的的一些方法和分析。 河海大学硕士研完生淹文 改进遗传算法及其在降雨径流模型中的应用 1 7 本文的研究内容 本文针对遗传算法的理论和实际应用两个方面都进行了研究，力求在遗传算 法有待解决的问题上有所拓展。通过对遗传算法理论的系统分析，针对遗传算法 编码表示的不准确性与遗传算法精度不高的缺点，以及标准遗传算法不能以概率 1 收敛到全局最优解的问题，提出了一种改进的遗传算法，并将其成功地应用在 密赛流域三水源新安江模型的参数率定中，提高了水文模型参数优选的效率和解 的精度。 本章介绍了遗传算法的起源、发展历史、特点、研究现状并对概念性降雨 径流模型及其参数率定的必要性和率定方法作了简要的介绍。第二章介绍标准遗 传算法和遗传算法的基础理论知识，为全文奠定理论基础。第三章中通过对遗传 算法理沦的分析，从模式定理的要求和遗传算法的收敛速度及求解精度之阃的矛 盾入手，提出了改进遗传算法，从理论上分析了其收敛性，并从典型的测试实例 中就其有效性得到了较好的验证。第四章就水文预报中的一个经常使用的降雨径 流模型一三水源新安江模型作了简要的介绍，对实例应用中用到的密赛流域的概 况进行了描述且就其产流方式作了论证。将本文提出的改进遗传算法应用于密赛 流域三水源新安江模型的参数率定中，取得了很好的效果。通过对标准遗传算法 和改进遗传算法得到的计算结果的比较，表明改进遗传算法在精度上优于标准遗 传算法。 河海太学硕士研宄生论文 改进遗传算法及其在降雨径流模型中的应用 2 1 引言 第二章遗传算法基础理论 遗传算法从一个初始种群出发，经过不断地选择、交叉、变异，使种群越来 越接近某个目标。如果把种群看作是超空间中的一组点，则选择、交叉、变异的 过程便是在超空间中点集之间的变换过程，通过这些信息的变换使种群不断地进 化，直至达到目标。 遗传算法计算过程和形式看似较为简单，但是其运行机理非常复杂。随着遗 传算法在复杂优化问题求解和实际工程设计中的应用，人们对遗传算法的理论基 础给予了越来越多的关注。一般来说，每种搜索算法都是将整个搜索空间分为多 个子空间来进行计算。而遗传算法本质上也是一种搜索算法，那么遗传算法是如 何对搜索空间进行划分的呢? 遗传算法又是怎样在各个子空间中分配搜索次数 的呢? h o l l a n d 教授提出的模式定理回答了这些问题：遗传算法通过模式来对搜 索空间进行划分，并通过选择、交叉、变异等遗传操作来为各个子空间分配搜索 次数。 遗传算法按其编码方案来进行划分，主要可分为二进制遗传算法与十进制遗 传算法。由于二进制遗传算法应用的广泛性以及其机器编码的方便性，本章将仅 就二进制的遗传算法进行介绍，重点是研究模式定理和收敛性分析方面的理论。 对于十进制遗传算法，其原理与二进制遗传算法十分相似“”。 遗传算法的理论依据为模式