（土木工程专业论文）结合高斯牛顿法的广义遗传算法反演地下水渗流参数.pdf

摘要 摘要 渗流问题是岩土工程中常见的问题，也是影响工程安全的重要因素之一。而 渗流分析中水文地质参数的确定是关键。本文在广泛阅读国内外相关文献的基础 上，通过对反演分析原理的深入理解，对基于观测资料反演分析地下水渗流参数 的具体方法的探讨，考虑到遗传算法强大的全局寻优能力及高斯牛顿法的局部寻 优能力，提出了将高斯牛顿法与广义遗传算法结合的新方法。具体工作如下： 1 简要介绍遗传算法的基本理论及缺陷，在此基础上进一步介绍广义遗传算 法，讨论其算法流程与基本遗传算法不同之处及优越性； 2 分析高斯牛顿法的基本理论和缺陷，结合上述两种方法的优点提出了新的 参数反演分析方法：结合高斯牛顿法的广义遗传算法，编制此结合算法的电算程 序； 3 在回顾渗流正分析的相关原理及概念后，综合运用结合高斯牛顿法的广义 遗传算法和渗流正分析方法，建立基于结合高斯牛顿法的广义遗传算法的参数反 演分析模型，为后续地下水渗流参数反演奠定理论基础； 4 分别结合数学模型和实际工程资料，通过反演分析模型对其水文地质参数 进行反演，并对反演成果进行合理分析，验证了结合高斯牛顿法的广义遗传算法 在地下水渗流参数反演分析中的可行性，具有实用价值。 关键词：水文地质参数；反演分析；广义遗传算法；高斯牛顿法 学位论文独创性声明： 本人所呈交的学位论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工 作的同事对本研究所做的贡献均已在论文中作了明确的说明并表示 了谢意。如不实，本人负全部责任。 论文作者( 签名) ： 学位论文使用授权说明 套匀为 矽矿年月压日 河海大学、中国科学技术信息研究所、国家图书馆、中国学术期 刊( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件或电 子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文 档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允 许论文被查阅和借阅。论文全部或部分内容的公布( 包括刊登) 授权河 海大学研究生院办理。 论文作者( 签名) 李昂岛 6 擘年月日 第一章绪论 第一章绪论 1 1 研究的意义和背景 渗流是岩土工程中的常见问题之一，也是影响工程安全的最重要的因素之 一。我国五六十年代修建的大型水利工程建筑由于修建时期技术不成熟，工程质 量不高，且相当一部分水利建筑物已经运行了几十年，为安全运行留下许多隐患， 其中渗流是水利工程中一直让人困扰的问题；而沿江河边线的河岸及护堤因长期 受到河水的冲刷侵蚀，土壤和建筑材料在水的渗透作用下其自身的性能发生改 变，防护作用明显降低；道路边坡在雨水长期冲刷浸润下，岩土体孔隙裂缝充满 流动的水体，自身机理逐渐产生改变，防滑抗拉裂能力降低极易发生山体土体滑 坡。这一系列由水体渗流导致的安全问题对国家和人民的生命财产造成极大的威 胁，已经引起了各级政府和人民群众的普遍关注。可见工程中对渗流问题进行正 确的分析是必要也是十分重要的。 j 下确的渗流分析可为岩土工程设计实施预先做好全面的防渗措施，或在工程 投入运行后，对因渗流引起的安全问题进行维护补救，以使渗流对建筑的安全影 响降低，尽量减少国家和人民的财产损失。对岩土体渗流场进行渗流分析时，其 主要任务是确定渗流场的水头，流速分布和渗流量等基本物理量，并以此进行相 关的设计计掣。其中地下水渗流参数的确定是渗流分析过程的基础，其取值将 对渗流场中水头、流速等要素的分析求解产生直接影响。 迄今，确定地下水渗流参数的方法可分为试验分析法及反演分析法等。其中， 试验分析方法现场和室内试验法。现场试验法是一种精确度较高的参数确定方 法，能较为客观地确定现场岩土体中的渗流系数，但是这种方法受外界条件干扰 较大，而且为了获得高精度的参数值对试验仪器精准度要求较高，因此需耗费大 量人力财力、物力，从节约成本上考虑不是有效的可行方法。室内试验方法。该 法在试验模型施工过程中，由于受施工工艺、施工方法和施工质量的影响，模型 的岩土体参数很难与设计值相符，且室内试验中待测岩土体样本在取回时已经受 到较大扰动，很难使试验模拟与实际情况相一致。反演分析法。这种方法是根据 现场实测数据信息，采用优化方法来反算岩土体渗流参数。自7 0 年代k a v a n a g l l 提出解决岩土工程反问题方法以来，反演参数的方法在岩土工程各领域得到较为 l 河海人学硕一l ：学位论文 广泛的应用，尤其在现代控制理论和数值分析方法的飞速发展为反演法在实践中 的推广运用提供了强有力的保证之后，该法成为较精确计算岩土体渗流参数的有 效方法，随着越来越多的设计研究人员对这个领域展开研究，反分析法已成为目 前水利、土木工程等研究领域很有发展前景的研究方法。 常用的反分析方法【2 】有解析法、脉冲谱法、离散优化法及摄动法。其中解析 法是通过数理方程的定解条件得出解的解析表达式，这是一种最经典、最古老的 求解方法。该法理论严密，思路清晰，求解结果精确简明，但适用于边界条件简 单的情况，对于实际工程中复杂的边界条件，求解结果往往与实际偏离较大。离 散优化法中的单纯形法【3 1 、牛顿法、拟梯度法【4 】等直接搜索法，这些方法使用范 围广，可用于线性及各类非线性问题的反分析，但是收敛速度较慢，解的稳定性 差，容易陷入局部最优，尤其在待定参数数目较多时，不能保证搜索到全局最优 解。遗传算法、人工智能网络和模糊集理论等是八十年代以来新兴的前沿研究学 科，其求解复杂工程问题时具有优于传统优化算法的性能，目前已广泛应用于土 木工程及水利工程问题优化求解中。 针对近二十年来智能反分析法的广泛应用，本文提出将传统优化方法中的高 斯牛顿法与遗传算法结合，基于结合高斯牛顿法的广义遗传算法建立反演分析模 型对其地下水渗流参数进行反演，寻求和建立高效的反演分析方法，为岩土工程 中的渗流安全问题提供更多有效的评估手段，具有重要的现实意义及良好的推广 前景。 1 2 研究现状 参数反演的发展历史，由1 9 1 5 年瑞典的哈斯特( n h a s t ) 在纳维亚半岛首先 开始，其开创了通过现场观测信息来反演初始地应力的先河。随后，许多国家的 学者都对该领域进行了研究。随着研究的深入，参数反演已在初始地应力、扰动 围岩压力和地层材料特性参数分析中获得广泛地应用。但是，这些反演方法都局 限于通过试验测得的数据资料，然后运用假定的关系，推求出地层材料特性参数 和初始地应力。然而，严格意义上说，这些方法并不是参数反演法，而只是为如 何计算测量参数提供了可行的方法。复杂的地质条件、不同的施工技术和运行管 理水平都使通过这些方法反演出的参数通 x 第一章绪论 与实际参数接近的参数的一种计算方法。2 0 世纪7 0 年代，随着现代控制理论和数 值优化方法的飞速发展及计算机智能化计算功能的日渐强大，这些强有力的技术 后盾为反演分析方法的迅速发展提供了保证。岩土工程反演问题的研究很快成为 国内外学者和工程师们十分关注的热门课题，且该反演方法已开始应用于边坡工 程、水库大坝工程、公路工程、地震研究等许多领域，并取得了一系列较为显著 的成果，极大地推动了岩土工程问题计算理论的继续发展并提高了其理论在实际 工程中的应用价值。 在国外，1 9 7 2 年k a v a i l a g h 和c l o u g l l 提出反演弹性固体的弹性模量有限元 法后【6 1 ，1 9 7 6 年r s t 铋在岩土工程勘测学术讨论会上提出了由实测岩变形来 反分析岩体弹性模量的方法。同年，k o v 撕提出了反算地层压力参数的方法。 1 9 8 0 年g i o d a 采用单纯形法和r o s e i l b r o c k 法等优化方法求解了岩体的弹性及 弹塑性变形参数【7 1 ，之后他又采用拟梯度法和p o w e l l 法等优化方法进行了反演 分析计算【s 】，同时还就不同优化方法在岩土工程反分析中的适用性进行了讨论。 1 9 8 3 年，c i v i d 诚等人提出了平面应变问题线弹性模型参数估计的b a y e s i a i l ( 贝 叶斯) 方法【9 】。1 9 8 4 年a s a o k a 提出了采用二次梯度法求解弹性模量e 和泊松 比i l 的方法【i o 】。1 9 8 7 年g i o d a 和s a l ( 删从确定性反分析和随机反分析的角 度出发，论述了岩土工程反分析数值方法的发展，并举例说明了其实际应用【l i 】。 1 9 9 3 年，h o s h i y a 和s u t o h 提出了将扩张卡尔曼滤波器与有限元耦合运用于解 决岩土工程问题【1 2 】；s h p a o n 和p r i e s t 将遗传算法引入到岩土工程反分析中【1 3 1 。 1 9 9 4 年k 0 h 等提出自适应滤波方法对普通扩张卡尔曼滤波器进行了改进【1 4 】。 1 9 9 5 年t h e o c 撕s 等将人工神经网络应用于塑性硬化本构模型的模拟【15 1 。1 9 9 6 年l e d e s m a 和g e n s 等提出了一种基于极大似然法，考虑参数的先验信息，同 时反演参数及其方差的概率论方法【婚1 7 1 ，通过辨识与参数相对应的方差来描述量 测结果的不确定性，并将该方法应用于隧道开挖问题【1 8 】。1 9 9 9 年，j a v a d i 和 f a n i l 枷等采用遗传算法进行了巷道喷浆混凝土空气渗透性参数的辨识【19 1 。2 0 0 1 年z e i l t a r 和h i c h e r 等提出了一种辨识土体参数的方法【2 0 】，将实验数据与相同 应力路径下现场量测数据之间的差异作为反演分析的目标函数，反分析了修正剑 桥模型参数。 在国内，岩土工程中的反分析研究相对起步较晚。1 9 8 6 年刘允芳【2 1 。2 2 】应用复 河海人学硕i 卜学位论文 变函数理论得到了非圆形洞室位移反馈分析原理及公式。同年，严克强等人提出 了有限元与无界元耦合的反馈分析法；1 9 8 8 年粘精斌【2 3 】用有限元反分析确定了土 层的模型参数；次年，杨林德【2 4 彩】等较全面地阐述了反分析方法的原理和工程应 用情况并于1 9 9 0 年用边界元反演洞室围岩初始地应力及其黏弹性模型参数，开辟 了反分析方法求解问题的新路，也拓宽了边界元方法的应用范围；孙韵于1 9 9 2 年发表了“岩石力学参数弹塑性反演问题的优化问题”的研究成果，提出了局部 最优解和全局最优解的概念；刘维宁【2 6 】于1 9 9 3 年以信息论为基础，针对岩土工程 中的逆问题，在数学上建立了逆问题一般信息理论的基本框架；徐日庆【2 7 】于1 9 9 5 年在研究土的应力路径非线性行为时采用正反分析方法确定了模型参数；周志芳 【2 】于1 9 9 7 年时就裂隙渗流中渗透张量的反演进行了详细的研究，2 0 0 2 年，刘世君， 王红春【2 8 】等提出了岩石力学参数的区间参数摄动反分析方法，该方法考虑岩体量 测数据及其力学参数的不确定性，建立识别力学参数的区间反分析模型。2 0 0 4 年 陈斌、施斌等建立一套面向对象的反演分析法，并针对岩土工程反分析中使用的 传统b a y e s 方法中存在的缺陷，提出了扩展b a y e s 方法，从概率论和数理统计的 原理出发，建立了基于决策信息论中的a i c 准则和最大熵准则的岩土工程随机反 演的准则函数【2 9 1 。 反演分析方法自提出以来，在边坡工程、地下洞室工程、水利工程等许多领 域提供了多方面的研究思路，并在理论研究中及部分实际工程中取得了一系列显 著的成果。随着现代计算机技术的飞速发展，理论计算的同渐成熟及数值计算方 法的同渐完善，在地下水渗流参数反演方面的研究，又有了进一步的发展和飞跃。 参数反分析的基本思想是利用实测数据资料，建立优化模型，再运用数学优 化的理论进行求解，从而达到反算出材料参数的目的【3 0 】。参数反分析法，按数学 方法计算思路不同，可分为图解法、解析法和数值法。随着计算机技术和计算方 法的发展和改进，数值法取得了较大发展，其可分为直接反分析法、概率统计法 和间接反分析法三大类。 直接反分析法【3 i j 的求解思路是在待求参数与实测值之间直接建立关系式进 行求解的方法。虽然该方法计算原理简单直观，但只能应用于线性问题的反演计 算。 概率统计法在反演中考虑到量测数据的随机性及待估参数的不确定性，在反 4 第一章绪论 分析中引入数理统计理论；这种方法可以用来研究量测误差等因素对反演得到的 地下水渗流参数的影响。这类方法有b a y s 法、极大似然法和卡尔曼滤波法等。 间接反分析法也叫正反分析法，此法是把正分析方法和数学规划法相结合， 把参数反分析问题转化为一个目标函数的寻优问题，直接利用j 下分析的格式和过 程，通过反复地迭代计算，逐次修正未知参数的设置，直到获得“最优值”。该 方法不需建立待求参数和实测水头资料之间的关系式，只需运用最优化理论不断 修正未知参数即可。 最优化方法是间接反分析法的有力工具，传统的最优化方法有单纯形法、复 合形法、拟n e 叭o n 法和罚函数法等，这类方法是从某假定的初始值迭代求最优 解；如初值取值不当，容易误入局部最优而无法跳出，最终导致搜索不到全局最 优解；而在待估参数数目较多时，计算速度非常缓慢，且计算结果与实际数据偏 差较大，传统优化方法的这些缺陷使其应用范围非常有限。 近年来，随着计算机技术和计算方法的发展和改进，多学科交叉发展趋势的 影响，鉴于传统优化算法的缺陷，关于智能优化算法的研究越来越多，其应用也 r 渐广泛。智能优化算法具有大规模并行运算、分布式存储和处理、自适应和自 学习能力等优点，能广泛应用于各个领域，其在求解复杂优化问题时具有优于传 统优化算法的性能，目前已成为土木工程和水利工程中解决优化问题最有效的手 段之一。这类方法主要有神经网络法【3 2 】、遗传算澍3 3 1 、免疫算法【3 4 】及模糊算法【3 5 】 等。其中遗传算法( g e n e t i ca l g o r i t h m ，g a ) 是近几年来备受关注的一种新型优 化算法，其根据达尔文进化论中的“生存竞争”和“优胜劣汰”原则，从某一初 始值群体出发，借助复制、交叉、变异等操作，不断迭代计算，经过若干代的演 化后，群体中的最优值逐步逼近最优解，直至最后达到全局最优【3 6 】。该法具有智 能搜索、并行式计算和全局优化等优点。但该法亦存在不足，如在解决参数较多 的问题时速度很慢，在局部搜索时搜索效率不高；针对遗传算法以上缺陷，许多 研究学者对遗传算法提出许多改进的方法。针对目前遗传算法的研究多数在理论 层次，本文尝试结合传统最优化方法对遗传算法加以改进，寻求更为高效准确的 遗传算法，并尝试将此反演方法运用到实际工程的地下水渗流参数确定中，为遗 传算法在工程中的运用提供更多可行的选择。 5 第二章广义遗传算法 第二章广义遗传算法 2 1 引言 自地球上出现最早的生命体以来，经过三十多亿年的繁衍进化，地球上的生 命从简单、低等到复杂、高等逐步进化、发展，到现在的生命群体已经十分繁多， 且形态各异。生物体发展到今天的样子，经过不断的进化和演变，生命体的形式 一直在不断地变化。生物发展进化的一个主要特点是：适者生存、优胜劣汰，即 适应自然环境条件的生物得到生存和繁衍，不适者淘汰。 早在2 0 世纪五十年代，少数学者基于利用进化思想解决工程优化问题的出 发点，从生物进化的角度入手，对人工生命进化进行研究。这些研究是遗传算法 的雏形。2 0 世纪6 0 年代，美国m i c h i g a i l 大学的j o l l l lh o l l a i l d 和其学生们正式提 出了遗传算法的概念。1 9 6 7 年，他的学生b a 西e y 和r o s e l l b e r g 在他们的博士论文 【3 7 】【3 8 】中提出了遗传算法的概念，并发展了复制、交叉、变异等遗传算子。1 9 7 5 年 h 0 1 l a l l d 出版了第一部系统论述自然与人工自适应系统和遗传算法的专著一自 然系统和人工系统的适配( a d a p t a t i o ni nn 狐髓la n da n i f i c i a ls y s t e m s ) 【3 9 1 ，该专 著系统地对遗传算法进行了论述。 遗传算法是以自然选择和群体遗传理论为基础、模拟生物进化过程中适者生 存规则与群体内部染色体的信息随机交换机制的一类自适应并行概率性全局搜 索算法，它主要用来处理最优化问题和机器学习。 遗传算法具有十分强健的鲁棒性，可操作性和简单性；该法是对一个被编码 的参数空间进行高效搜索，且只需利用目标函数的取值信息，无需对目标函数求 导等高价信息，因而适用于大规模、高度非线性的不连续多峰函数的优化以及无 明显解析表达式的目标函数优化，具有很强的通用性；其良好的并行性、优越的 全局优化性能和稳健性为其广泛应用于各研究领域提供了强有力的保证。 函数数值优化是遗传算法最常用的领域。1 9 7 5 年d ej o n d 删对用遗传算法解 决函数数值优化问题进行了系统论述，并提出了5 个测试遗传算法性能的测试函 数。1 9 8 9 年j o t lr k o z a 将遗传算法用于计算机自动编程，形成了遗传程序设 计。h o l l a n d 当初提出遗传算法主要是对认知系统的研究，即将遗传算法用于机 7 河海大学硕士学位论文 器学习；除此之外，遗传算法还在组合优化、智能控制、机器人学、图像处理、 模式识别等多个领域中得到研究运用。 h o l l a l l d 等提出的遗传算法现在被称为简单遗传算法( s i m p l eg e n e t i c a 1 9 0 r i t l l n l ) ，或称为基本遗传算法。但由于简单遗传算法( s g a ) 存在着早熟收 敛、局部寻优较差等不足，人们在简单遗传算法的基础上对其进行了改进，提出 了许多的改进遗传算法【4 1 4 3 1 ，以提高优化效率。本文引进了基于基本遗传算法和 加速遗传算法基础上的广义遗传算法，结合下一章介绍的高斯牛顿法，对局部寻 优能力不高的遗传算法进行改善，提出一种新的遗传算法。 2 2 遗传算法的运算流程 h o l l 锄d 创建的遗传算法是一种随机优化的概率搜索算法，他利用某种编码 技术作用于称为染色体的数串。其基本思想是模拟由这些染色体数串组成的个体 进化过程。该法通过有组织的、随机的信息交换，通过生物进化操作，主要为选 择、交叉、变异等，重新组合那些适应性好的染色体数串，得到新一代的个体， 然后在新一代个体群的基础上，在经过若干代的进化操作，最终得到全局最优解。 遗传算法模拟了自然选择和生物进化的过程及在遗传中发生的复制、交叉和 变异等现象，从初始群体出发，通过随机选择、交叉和变异操作，产生一群更适 应环境的个体，使群体进化到搜索空间更好的区域，这样每一代不断地繁衍进化， 最后收敛于一群最适应环境的个体，即求得问题的最优解。 遗传算法的基本流程如图2 1 所示。 从流程图2 1 中可以看到，首先从可行的数值区域内随机挑选一些数据作为 初始群个体，对数据进行编码，并计算每个解的目标函数，再根据适应度函数转 化成适应度。接着通过遗传算法特有的遗传算子：选择算子、交叉算子和变异算 子，进行进化操作，产生下一代编码数据，如此反复操作，直到满足终止条件为 止。此时，最后一代群体的最优个体就是待求问题的最优解。 第二章广义遗传算法 否 开始 1 l 编码 土 形成初始种群 1r 一 种群中个体适应度的评价检测 上 选择 1 l 交叉 1r 变异 解码输山最优解 图2 1 遗传算法基本流程图 2 3 遗传算法的基本原理与方法 遗传算法以群体为基础，不是以单点搜索为基础，能同时从不同点获得多个 极值，因此不易陷入局部最优。下面将讨论遗传算法的实现需要涉及到的几个主 要因素：参数编码、初始群体的设定、遗传操作，算法控制参数的设定和约束条 件的处理。 1 ) 编码 o 河海人学硕j ：学位论文 选择操作策略与编码方式无关，下面介绍几种常用的选择算子。 ( 1 ) 轮盘赌选择 轮盘赌选择方法( r d u l e t t e 、胁e e ls e l e c t i o n ) 是一种回放式随机采样方法。经典 算法中常采用这种算法，群体中每个个体就像圆盘中的扇形部分，扇面的角度和 个体的适应度值成正比，随机转动圆盘，停止时指针所在扇面对应的个体被选中。 但由于群体规模和随机操作的原因，个体实际被选中的次数与其应被选中的期望 值之间可能存在着一定的误差。 ( 2 ) 最佳保留选择 首先按轮盘赌选择方法执行遗传算法的选择操作，然后将当前群体中适应度 最高的个体完整地复制到下一代群体中。其主要优点是能够保证遗传算法终止时 的最后结果是曾经在历代群体中出现过的最高适应度的个体。 ( 3 ) 最优保存策略 在遗传算法操作中，由于选择、交叉、变异等操作的随机性，在产生一些优 良个体的同时，可能会破坏当前群体中适应度最好的个体。为避免这种情况的发 生，人们采用最优保存策略进化模型来进行优胜劣汰操作，即当前群体中适应度 最高的个体不参加交叉和变异操作，而是用其来替换本代群体中经交叉、变异等 操作后产生的适应度最低的个体。 3 ) 交叉 交叉( c r o s s o v 哪又称重组( r e c o m b i n a t i o n ) ，其模仿生物的自然进化过程，两 个同源染色体通过交配而重组，形成新的染色体，以产生新的个体或物种的手段。 在遗传运算中采用交叉运算，以较大的概率从群体中选择两个个体，相互交换两 个个体的部分基因串，从而产生继承父代基本特征的子代。交叉运算是遗传算法 区别于其他算法的重要特征，是产生新个体的主要方法。交叉算子的设计包括如 何确定交叉点位置和如何交换部分基因两个方面的内容。在交叉运算之前还须对 群体中的个体进行随机配对，交叉操作是在配对个体组中的两个个体之间进行 的。下面介绍几种适合二进制编码个体或浮点数编码个体的交叉算子。 ( 1 ) 单点交叉 单点交叉也成为简单交叉，其过程是在个体编码串中只随机设置一个交叉 点，然后在该点相互交换两个配对个体的部分染色体。图2 3 所示为单点交叉运 1 2 第二章广义遗传算法 算的示意图。 a 口口口团口l 团 = 团单点a t 口口口圈口i 口口口 ；二 b 口口口口口l 口口口b 口口口口口! 口口口 交义点 ( 2 ) 算术交叉 算术交叉( 蛳u n e t i cc r o s s o v 哪是指由两个个体的线性组合而产生出两个新 的个体。算术交叉的操作对象一般是由浮点数编码所表示的个体。 假设在两个个体一、以之间进行算术交叉，则交叉运算后产生的两个个体 为 雕三群二麓 协- ， i 露1 = 口e + ( 1 一口) e 、。 其中，口为一参数，当口是一个常数时，此时的交叉运算为均匀算术交叉，它 也可以是个由进化代数所决定的变量，此时所进行的交叉运算为非均匀算术交 叉。遗传算法的收敛性主要取决于核心操作交叉算子的收敛性。 4 ) 变异 在生物遗传和自然进化过程中，生物的某些基因由于某些偶然因素而发生 变异，从而产生有新的生物性状的新染色体。遗传算法也引入变异算子来产生新 的个体。变异运算是指将个体染色体编码串中的某些基因座上的基因值用该基因 座的其他等位基因来替换，从而生成新个体。虽然变异运算只是产生新个体的辅 助方法，但它也是必不可少的一个步骤，其决定了遗传算法的局部搜索能力，交 叉算子和变异算子相互配合，使得遗传算法能够以良好的搜索性能完成最优化问 题的寻优过程。 ( 1 ) 基本位变异 基本位变异是标准遗传算法一般采用的变异算子，该法对个体的每一个基因 座，以变异概率指定其为变异点；对制定的变异点，对其基因座做反运算或用其 他等位基因值来代替，从而产生出新一代的个体。 ( 2 ) 均匀变异 第二章广义遗传算法 体直接复制到下一代，致使遗传搜索可能陷入停滞状态。一般以的建议取值范 围为0 4 0 9 9 。变异运算是对遗传算法的改进，对交叉过程可能丢失的一些遗 传基因进行修复和补充，提高遗传算法的局部搜索性能。一般建议的取值范 围是o o o o l o 1 。群体规模( p o p u l a t i o n ) 的大小直接影响算法的收敛性和计算效 率。规模太小，容易收敛到局部最优解；规模太大，则会降低计算速度。一般经 验取值，群体规模可以取在1 0 2 0 0 之间。 乃约束条件的处理 在遗传算法中须对约束条件进行处理，根据具体问题可选择下列三种方法： 搜索空间限定法、可行解变换法和罚函数法。 ( 1 ) 搜索空间限定法 其基本思想是对遗传算法的搜索空间的大小加以限定，使得搜索空间中表 示一个个体的点与解空间中的表示一个可行解的点有一一对应的关系。对一些比 较简单的约束条件通过适当编码使搜索空间与解空间一一对应，限定搜索空间能 够提高遗传算法的效率。 ( 2 ) 可行解变换法 在个体基因型到个体表现型的变换中，增加使其满足约束条件的处理过程， 即寻找个体基因型与个体表现型的多对一变换关系，扩大搜索空间。该法对个体 的编码方法、交叉运算、变异运算无特殊要求，但运算效率下降。 ( 3 ) 罚函数法 罚函数法的基本思想是对在解空间中无对应可行解的个体计算其适应度时， 除以一个罚函数，从而降低该个体的适应度，使该个体被遗传到下一代群体中的 概率减小。这种处理方法难点在于，在考虑罚函数时，既要考虑解对约束条件不 满足的程度，又要考虑运算的效率和速度。 2 4 广义遗传算法 基本遗传算法自提出以来，由于其智能性、并行性、稳健性、全局优化性和 可操作性等一系列优点【4 5 】，已经在许多研究领域的优化中得到了广泛的运用。但 遗传算法作为一种优化方法，存在其自身的局限性： 基本遗传算法编码的不规范性及编码存在着表示的不准确性；其局部寻优能 河海大学硕士学位论文 ( o 8 0 0 3 ，1 4 2 5 1 ) ，对应的目标函数值为1 8 6 7 3 0 9 ，与s h u b 酣函数的全局最小值 1 8 6 7 3 0 9 及其对应的点( 0 8 0 0 3 ，1 4 2 5 1 ) 保持一致：而基本遗传算法在进化到第 1 0 代的时候仍未达到真值，在进化到第3 0 代的时候才与真值基本保持一致。由 此可以得出：此算法经过加速( 三代) 迭代操作，具有良好的计算收敛性和稳定性， 有利于提高算法的搜索效率，还可兼顾祖代个体间的差异。由此初步验证，广义 遗传算法能够较快地收敛到全局最优点，算法性能稳定，精度较高。 表2 - 2s h u b e r t 函数进化迭代值 基本遗传算法广义遗传算法 代数 乇 厂( 五，而) j c 2 厂( 玉，而) l旬8 5 2 21 3 7 6 117 5 2 9 9 80 8 5 2 21 3 7 6 11 7 5 2 9 9 8 2 - 0 7 9 0 01 4 0 5 218 5 5 6 2 2 一o 7 9 0 01 4 0 5 21 8 5 5 6 2 2 30 7 9 0 0 1 4 0 5 218 5 5 6 2 2 旬7 9 0 01 4 0 5 2 18 5 5 6 2 2 4_ o 7 9 0 01 4 0 5 71 8 5 6 1 0 90 8 0 2 01 4 1 0 318 6 2 0 8 6 5o 7 9 0 01 4 0 5 71 8 5 6 1 0 90 8 0 2 01 4 1 9 71 8 6 6 5 5 1 6o 7 9 0 61 4 0 5 618 5 6 2 5 40 8 0 2 01 4 2 1 01 8 6 6 9 9 2 70 7 9 0 01 4 1 2 018 6 0 9 2 8o 8 0 1 51 4 2 5 61 8 6 7 2 9 1 8o 7 9 0 61 4 3 4 71 8 6 3 1 1 7- 0 7 9 9 61 4 2 5 118 6 7 3 0 9 9o 7 9 0 61 4 3 4 71 8 6 31 2 1_ 0 8 0 0 31 4 2 5 118 6 7 3 0 9 1 0加7 9 0 01 4 2 3 9 1 8 6 4 9 1 6 _ o 8 0 0 31 4 2 5 l18 6 7 3 0 9 ( 2 ) d e j o n g 函数f 2 正( 五，而) = l o o ( # 一而) 2 + ( 1 一五) 2 其中变量一2 0 4 8 五，毛2 0 4 8 这是一个单峰值二维函数，具有全局极小点石( 1 o ，1 o ) = o o 。函数曲面见图 2 - 4 ，该函数曲面上有一条较为狭窄的山谷，传统梯度优化方法在搜索时，一般 难以进行全局优化。对于此函数分别采用基本遗传算法、混合遗传算澍4 7 1 和广义 遗传算法对该函数进行求解比较。 第二章广义遗传算法 图2 - 4 d e j o n g 函数曲面图 表2 - 3 三种算法的收敛过程 进 基本遗传算法h g a广义遗传算法 化 代 f ( x ) x lx 2 f ( x ) x l x 2 f ( x ) x lx 2 数 10 1 0 8 0 4 21 0 1 6 91 0 6 6 90 0 6 6 3 9 20 8 1 3 60 6 7 9 70 1 0 8 0 4 21 0 1 6 91 0 6 6 9 2 0 。0 0 7 9 1 30 9 6 3 50 9 3 6 50 0 0 2 0 5 91 0 3 0 71 0 5 8 90 0 0 7 9 1 3o 9 6 3 50 9 3 6 5 30 0 0 2 7 1 60 9 5 0 6o 9 5 0 6o 0 0 0 0 2 00 9 9 8 l0 9 9 5 70 0 0 2 7 1 60 9 5 0 6o 9 5 0 6 4 o 0 0 2 7 1 60 9 5 0 60 9 5 0 60 0 0 0 0 1 4o 9 9 8 70 9 9 7 00 0 0 0 0 2 41 0 0 0 l 0 9 9 8 7 5o 0 0 2 7 1 6o 9 5 0 6o 9 5 0 6o o o o o o o1 0 0 0 01 0 0 0 0o o o o o l 3o 9 9 9 31 0 0 1 1 60 0 0 2 7 1 6 0 9 5 0 6 0 9 5 0 6 0 0 0 0 0 0 01 0 0 0 01 0 0 0 00 0 0 0 0 0 01 0 0 0 0 1 0 0 0 0 70 0 0 2 7 1 60 9 5 0 6o 9 5 0 6o 0 0 0 0 0 01 0 0 0 0l ：0 0 0 00 0 0 0 0 0 01 0 0 0 01 0 0 0 0 由表2 3 可看出，基本遗传算法在第三代就出现明显的早熟收敛现象，而从 表中可看到混合遗传算法与广义遗传算法达到全局最优解时仅相差一代。由此可 见，单是广义遗传算法的求解精度及速度与混合遗传算法就基本能保持一致，且 混合遗传算法中需每代调整个体的自适应选择概率及使用单纯形法进行局部优 化，每一代的进化都非常耗时，且从编程角度考虑相对繁琐；而广义遗传算法只 1 9 舢 姗 砌 伽 o 2 河海大学硕十学位论文 需加速( 三代) 迭代操作其求解效率就能基本与h g a 一致，无论从编程角度还是 计算量的考虑，都是值得采用的算法。 2 5 本章小结 本章首先介绍遗传算法的发展过程，阐述遗传算法的基本原理、相关的主要 因素，并介绍了基本遗传算法的运算流程。在总结基本遗传算法的缺陷后，为克 服算法早熟收敛、随机漫游等缺点，对各种改进的遗传算法进行综合比较后，本 文引进了广义遗传算法【5 0 1 ，考虑隔代遗传机制，对基本遗传算法进一步完善。 广义遗传算法是是一种鲁棒性较强的随机搜索方法，是在加速遗传算法的基 础上经过改进的算法，引入的“隔代遗传”概念简明易懂，经过测试函数的求解 验证，广义遗传算法相对众多其他改进的遗传算法而言，是一种思路清晰编程较 为简便的改进遗传算法。本文将在下一章中结合高斯牛顿法，提出结合高斯牛顿 法的广义遗传算法，使其局部搜索性能进一步得到提高。 2 0 第三章结合高斯牛顿法的广义遗传算法 第三章结合高斯牛顿法的广义遗传算法 3 1 概述 所谓最优化问题，就是在研究或计算过程中，寻找一个最优的计算方案或 控制理论，使得所研究的对象能在最优的路线下达到预期的目标，其中采用的方 法就是最优化方法。 最优化方法解决待求问题一般分为以下几个步骤：( 1 ) 提出需要进行最优化 的问题，开始收集有关资料和数据；( 2 ) 建立求解最优化问题的有关数学模型， 确定变量，列出目标函数和有关约束条件；( 3 ) 分析数学模型，根据具体情况选 择合适的最优化求解方法；( 4 ) 求解方程，根据最优化算法，一般通过编制程序 在电子计算机上求得最优解；( 5 ) 最优解的验证和实施，并可以对该算法的计算 效率、收敛性及误差做综合评价。通过上述五个相互独立和互相渗透的步骤，最 终求得系统的最优解。 最优化模型的基本要素一般包括变量、约束条件和目标函数三要裂5 1 1 。变 量：指最优化问题中待确定的某些量。变量可用z = ( ，屯，) 7 表示。约束条 件：指在求最优解时对变量的某些限制，包括技术上、资源上和时间上的约束等。 列出的约束条件越接近实际系统，则所求得的系统最优解也就越接近实际最优 解。约束条件可用岛( x ) o ( 江1 ，2 ，所) 表示，扰表示约束条件数；或x 尺( r 表示可行集合) 。目标函数：最优化求解结果有一定的评价标准。目标函数就 是这种标准的数学描述，一般可用厂( x ) 来表示，即厂( z ) = 厂( 五，吃，) 。要求 目标函数为最大时可写成嘴厂( x ) ；要求最小时则可写成t 卿厂( x ) 。目标函数 可以是系统功能的函数或费用的函数。它必须在满足规定的约束条件下达到最大 或最小。 3 2 高斯牛顿法的基本原理 研究最优化问题，一般都采用向量表示法。在目标函数中的未知自变量 ，而，可以看作是刀维向量空间尺“中的一个向量x 的甩个分量，即 2 l 河海大学硕十学位论文 或 于是所描述的求极小值问题 可简记为 h 舻h 薹一! 藿；篱j ；薯l 喜 萋l 莺蓁l 霎；雾；一；当i 鬟邕馨i 妻i 黧冀扣薹i 蚕 匏竖霆鬓慧堕荔萎萎埏； 氍墼霁婪堑叁冀誉瑁鸶冀薹跫耋翼雾稀蓁馑崖雇嚣些= 墨蓠雾避箨馑， 薹；薹藿5 忸囊i 塑翮蓁勤衙抖羔霎蕈丢譬；耄茎茎萋王主善菱芝罐耄塞； 萋薹蓁薹i 謇j 二墓薹霉主薹爹垂孽三薹霎喜二j | | ；簇x ) = v w ( x ) = a 2 厂( x ) a 2 ( x )a 2 厂( x ) 研钆钆两 a 2 厂( x ) a2 ( x )a 2 厂( x ) 钆鹾阮 a 2 厂( x ) 钆瓯 a 2 厂( x ) 红钆 a 2 厂( x ) 醒 这就是，l 元函数厂( x ) 关于x 的二阶导数，称为( x ) 的h e s s i a n 矩阵。 综上所述，多元函数厂( x ) 的一阶导数是它的梯度w ( x ) ，二阶导数是它的 h e s s i a l l 矩阵v 2 厂( x ) 。在最优化问题中这是两个常用的概念。 3 2 1 引言 第三章结合i ：! ：i 斯牛顿法的广义遗传算法 彳( x ) = ，( t o ，x ) 一咒 f = 1 ，聊 f ( x ) = z ( x ) ，厶( x ) r 则得到最小二乘问题的一般表达式 i i l i n 愀x ) 一y l l 2 或 m i n f ( x ) rf ( x ) = r n j n 愀x ) 1 1 2 ( 3 3 ) 当f ( x ) 为线性向量值函数时，式( 3 3 ) 称为线性最小二乘问题；反之，则称 为非线性最小二乘问题。 3 2 2 高斯牛顿法公式推导 非线性最小二乘问题属于无约束最优化问题。非线性问题对应非线性数学模 型，即厂( x ) 是各待定参数的非线性函数，其参数必须用逐次逼近的方法处理。 考虑到其目标函数具有的特殊形式，本文将采用相对有效的方法一一 g a u s s n e w t o n 法来求解非线性最小二乘问题。 g a u s s n e 、咖n 法属梯度法，即一种梯度导向的启发式搜索算法。该算法的 实质是把非线性最小二乘问题逐次化为一系列线性最小二乘问题来迭代求解。高 斯牛顿迭代法的基本思想是使用t a y l o r 级数展开式去近似代替非线性回归模型， 然后通过多次迭代来修j 下回归系数【5 3 1 。 假设选定初始点x 。后经过迭代已求得x 。，现在考虑x m 的求法。与常用的 n e 、咖n 法的基本思想相类似，通过把f ( x ) 线性化，用线性最小二乘问题的解法 去逼近非线性最小二乘问题的解。 把f ( x ) 的第f 个分量彳( x ) 在点x 。处展成t a y l o r 表达式： 彳( x ) z ( x 。) + v ，：( x 。) r ( x x 。) f = l ，m 如果采用向量、矩阵形式表示出来，则上式可写为 f ( x ) f ( x 。) + a ( x 。) ( x x 。) ( 3 - 4 ) 其中a ( x 。) 是f ( x ) 在点x 。处的j a c o b i 矩阵，即 2 s 河海大学硕士学位论文 a ( x 。) = w ( x 。) r 既( x 。) r 甄( x 。)新( x 。) 嘶 识( x 。)甄( x 。) 挑阮 为了简便，以下记= f ( x 。) ，a 。= a ( x 。) 。 将式( 3 4 ) 代入非线性最小二乘问题的目标函数 5 ( x ) = f ( x ) 7 f ( x ) = i i f ( x ) 0 2 得到线性化后的表达式 s ( x ) 慨+ a 。( x x 洲 如设线性最小二乘问题 i i l i n 忪。p + 驯2 的解为n ，则 x i + i2k + p 女 就是目标函数式( 3 5 ) 的极小点的新的近似解。 根据定理l x 是r n j n0 a x b l l 2 极小点的充要条件是x 满足方程组a r a x = a 飞， 其中 x = 【_ ，吒】r b = 【6 i ，包】r 式( 3 - 6 ) 的极小点玑可由它的法方程组 a ：a 。p = 一a ：l 解出。如果a ：a 。是非奇异的， 式( 3 8 ) 的解可表示成 p 。= 一( a ：a 。) a ： 代入式( 3 7 ) 中得 ( 3 - 5 ) ( 3 - 6 ) ( 3 7 ) ( 3 - 8 ) ( 3 - 9 ) 第三章结合高斯牛顿法的广义遗传算法 x 。+ 。= x 。一 毖鲥丫噼触够雏阱髟萎襄掣影霎1 霎薹引毒妻薹霜萋薹型薹需鹩；蓁锚蟹裂* 誉崔 荦霎掣嘉霎氇鼋毒。凼主妻蓬借； 蓁薹l 蓬! 墅霾粥。船雾洞哺字4 孬哆一| 譬。# j 盹羹型蚕鋈巍妻室r 薹薹薹霎季 涮超芬一蓁i 层霎囊l 蚕5 l t薹b羹甭i拿i笺笺蓁蓁；。|量藿!薹!霉一霪羹；可获得初始染色体，y ：，。 c 适应度评价： 适应度函数是促进算法进化的唯一驱动力和依据。关于种群内部构造的改变 都是通过适应值来控制的，其合理性直接影响到算法的优劣。 本文建立基于排序的适应度评价函数，种群按目标函数值进行排序，适应度 仅仅取决于个体在种群中的序位，而不是实际的目标值。排序方法克服了比例适 应度计算的尺度问题，当最佳染色体选中的概率与平均选中概率的比值太小的情 况下，导致搜索带迅速变窄而产生过早收敛，再生范围被局限。 排序选择方法的主要思想是：对群体中的所有染色体按适应度评价函数值大 小进行升序排列，然后基于这个排序分配各个染色体被选中的概率。排序方法较 之比例适应度方法表现出更好的鲁棒性，是一种很好的选择方法。排序方法引入 种群均匀尺度，提供了控制选择压力( 最佳个体选中的概率与平均选中概率的比 值) 的简单有效方法。让染色体。，y m 按个体目标函数值的大小降序排列， 使得适应度强的染色体被选择作为父代的概率更大。m i c h a l e 嘶c z 提出了非线性 第三章结合高斯牛顿法的广义遗传算法 m 应度值z 与整个种群m 个染色体适应度总和( 五) 的比例，即 七= l ， # = 彳五 基于这些概率值用比例选择( 赌盘选择) 的方法来产生下一代，从而可知当 个体适应度越大，其被选中的概率也越大。该算子是一种回放式随机采样方法， 以旋转赌轮n 次为基础，每次旋转可选择出单个个体进入子代种群，从而得到子 代种群所需的n 个染色体。 ( 2 ) 交叉算子： 交叉运算采用单点交叉算子。单点交叉( o n e - p o i n tc r o s s o v e r ) 的具体执行过程 在第二章已经详细介绍，便于编码的交叉操作及与基本遗传算法和加速遗传算法 的结果比较。 ( 3 ) 变异算子： 本文采用均匀变异算子。均匀变异( u i l i f o n nm u t a t i o n ) 操作特别适用于遗传算 法的初级运行阶段，它使得搜索点可在整个搜索空间自由移动，增加群体的多样 性。其具体操作过程是：首先，依次指定个体编码串中每个基因座为变异点。然 后，对每一个变异点以变异概率p 。从对应基因值的取值范围内取一随机数来替 代原有基因值。变异点的求解参见第二章第三节公式( 2 5 ) 。 e 祖辈优秀个体保存： ( 1 ) 保存优秀染色体 将每代进化生成的染色体按适应度降序排列，取s 。( 取为常数) 个优秀染色 体，将其变量变化空间存于程序中，并将每代优秀染色体对应的遗传代数存储于 程序中，为种群染色体变化范围的更新作准备。 ( 2 ) 遗传迭代 根据( g ) 步介绍的迭代终止条件，评价种群中的最优染色体，如满足要求， 可跳出程序，输出结果；如不满足评价要求，则返回第( c ) 步，继续遗传进化迭代。 ( 3 ) 加速循环： 考虑隔代遗传的广义遗传算法，在进行加速循