（基础数学专业论文）一类基于区域分裂的演化算法及应用.pdf

一类基于区域分裂的演化算法及应用 摘要 区域分裂法的基本思想是将定义在复杂的大区域上的问题分解 成若干小区域上的问题分别求解，然后通过迭代得到整个区域上的 解，该方法能分解大型问题为小型问题、复杂区域问题为简单区域问 题。 演化算法在求解函数优化问题很有效。长期以来演化算法在应用 中主要存在两大缺陷：一是对某些问题演化算法求解速度太慢；二是 演化算法容易产生早熟现象，而且对于单峰函数优化问题，目前的演 化算法还没有鲁棒性。有研究表明用杂交算子求解实数优化问题时可 以得到较好的结果。日前对实数函数优化问题的研究中，很多人致力 于研究如何找到一个有效的杂交算子。 本文介绍了演化算法的基本结构和研究现状，给出了演化算法的 基本结构，介绍了各种杂交算子，分析了他们的优点和缺陷，详细分 析了g t 算子及带子空间的g t 算法的性能。将g t 多父体杂交算子 进行改造，应用于求解非线性方程组，提出了求解非线性方程组的 g t 算法。 分析了常微分方程边值问题及其数值解法、有限元方法和区域分 裂法的基本原理，给出了利用区域分裂法、有限元方法在小区域上离 散一维常微分方程边值问题具体过程，给出了基于区域分裂和有限元 离散的求解常微分方程边值问题的演化算法。 给出了郭涛算法求解非线性方程组的算例以及利用区域分裂法、 有限元法和郭涛算法求解常微分方程边值问题的算例并对结果进行 高校教师在职硕士学位论文 了分析。 本文改进了求解非线性方程组的g t 算法。该算法可以在演化过 程中自适应调整搜索空间和种群从而加快收敛，并以它为基础提出了 一类新的求解常微分方程边值问题的数值解的演化算法。 关键词：郭涛交叉算子，非线性方程组，区域分裂法，有限元法，收敛 一类基于区域分裂的演化算法及应用 - m a b s t r a c t d o m a i nd e c o m p o s i t i o nm e t h o di sa ne f f e c t i v en u m e r i c a l m e t h o df o rp a r t i a ld i f f e r e n t i a le q u a t i o n s u s i n gi t ，w ec a l l d i v i d et h ec o m p l e xa n dl a r g ea r e ai n t os o m es m a l la r e a sa n d g e ts o l u t i o n so nt h e mr e s p e c t i v e l y ，t h e nt h er e a ls o l u t i o no n t h ew h o l ea r e ac a nb eg a i n e dt h r o u g hi t e r a t i o no fp r e c e d i n g s o l u ti o n sw eh a v eg o t t h ism e t h o dc a nt r a n s f o r ml a r g ep r o b l e m i n t os m a l lo n ea n dc a nc h a n g ec o m p l e xa r e ai n t os i m p l eo n e w h e ni tc o m e st of u n c t i o n so p t i m i z a t i o n ，e v o l u t i o n a r y a l g o r i t h m sp e r f o r mf a i l yw e l l ：b u t t h e r ea l s oe x i s ts o m e l i m i t a t i o n so fi t s a p p l i c a t i o n s ：f i r s t l y ，e v o l u t i o n a r y a l g o r i t h m si st o os l o wf o rs o l v i n gc e r t a i np r o b l e m s ：s e c o n d l y ， itisa p tt or u ni n t ol o c a lo p ti m aa n dh a v en or o b u s t n e s sf o r f u n c t i o no p t i m i z a t i o np r o b l e m sw i t hs i n g l ep e a k h o w e v e r ，s o m e r e s e a r c h e ss h o w e dt h a tb e t t e rr e s u l t sf o rf u n c t i o n o p t i m i z a t i o n c a nb eg e tt h r o u g hc r o s s o v e ro p e r a t o r s s o r e c e n t l ym a n yr e s e a r c h e r st r yt h e i rb e s tt os e a r c he f f e c t i v e c r o s s o v e ro p e r a t o r s i nt h i sp a p e r ，w ei n t r o d u c et h eb a s i cs t r u c t u r ea n dc u r r e n t d e v e l o p m e n to fe v o l u t i o n a r ya l g o r i t h m s a n da n a l y z et h e i r a d v a n t a g e sa n dd i s a d v a n t a g e s e s p e c i a l l y ，w ea n a l y z eg u o t a o c r o s s o v e ro p e r a t o r ，i m p r o v ei ta n dp u tf o r w a r dan e wa l g o r i t h m f o rn o n l i n e a re q u a t i o n ss e t w ea l s oi n t r o d u c et h eb o u n d a r y p r o b l e m so fo r d i n a r yd i f f e r e n t i a le q u a t i o na n ds o m ep o p u l a r n u m e r i c a lm e t h o d sf o ri t ，a n dt h ep r i n c i p l eo ff i n i t ee l e m e n t m e t h o da n dd o m a i nd e c o m p o s i t i o nm e t h o d f u r t h e r m o r e ，t oo n e d i m e n s i o nb o u n d a r yp r o b l e mo fo r d i n a r yd i f f e r e n t i a le q u a t i o n ， w ep r e s e n tt h ed i s c r e t i z a t i o np r o c e d u r ea n ds p e c i f i ca l g o r i t h m t a k i n ga d v a n t a g eo fd o m a i nd e c o m p o s i t i o nm e t h o da s s o c i a t e d w i t hf i n i t ee l e m e n tm e t h o d i nt h en u m e r i c a le x p e r i m e n tp a r t ，w ep r e s e n tt a b l e sa n d g r a p h so fs e v e r a lt y p i c a le x a m p l e sw eh a v ec o m p u t e d a n a l y s i s f o rt h e s er e s u l t si sg i v e n ，t o o t h eg r e a tc o n t r i b u t i o no ft h i sp a p e ri st h a tw ei m p r o v et h e g u o t a oa l g o r i t h m ，w h i c hm a k e ss e a r c hs p a c ea n dp o p u l a t i o n s e l f - r e g u l a ti n g o nt h ee v o l u ti o n a r y p r o c e s s i no r d e rt o a c c e l e r a t ec o n v e r g e n c et oe x a c ts o l u t i o n b a s e do nt h i s i m p r o v e dg u o t a oa l g o r i t h m , w ep u tf o r w a r da nn e we v o l u t i o n a r y a l g o r i t h mf o rb o u n d a r yp r o b l e m so fo r d i n a r yd i f f e r e n t i a l e q u a t i o n k e y w o r d s ：g u o t a oc r o s s o v e ro p e r a t o r ，n o n li n e a re q u a ti o n ss e t ， d o m a i nd e c o m p o s i t i o nm e t h o d ，f i n i t ee l e m e n tm e t h o d ，c o n v e r g e n c e 一类基于区域分裂的演化算法及应用 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本 论文不合任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名匀占宠二口。o 年1 二月仙日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 研究生在校攻读学位期间论文工作的知识产权单位属湖南师范大学。 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权湖南师范大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 本学位论文属于 i 、保密口，在年解密后适用本授权书。 2 、不保密口。 ( 请在以上相应方框内打“ ”) 作者签名- 匀占究日期：二。d o 年十；月札日 导师签名：亏专b 日期励( ，年l 月以一日 一类基于区域分裂的演化算法及应用1 1 1 引言 l 绪论 演化算法自出现以后，由于其原理的简洁性，演化的随机性，计 算的并行性，特别是具有自组织、自学习、自优化等智能特征，逐渐 被应用到各个领域。演化算法在函数优化、组合优化、自适应控制、 模式识别、机器学习、人工生命、生物工程、管理决策等方面得到广 泛的应用1 1 j 【2 l 【3 】【4 】闭嘲，特别对于一些大型的复杂的非线性系统，演化 算法表现出了比传统搜索和优化方法更加优越的性能。 区域分裂法是求解偏微分方程数值解的新方法。区域分裂法的基 本思想是将定义在复杂的大区域上的问题分解成若干小区域上的问 题分别求解，然后通过迭代得到整个区域上的解，能有效地节省内存 和计算时间，特别适合于并行计算。该方法能分解大型问题为小型问 题、复杂区域问题为简单区域问题、串行问题为并行问题，已成为计 算大型科学与工程问题的重要方法。 1 2 研究背景和研究现状 演化算法在求解函数优化问题很有效，因此对求解函数优化问题 的演化算法进行研究具有重要的理论意义和实用价值。单目标函数优 化是目前研究得较多的一个领域忉- 【n 1 。但是，长期以来演化算法在应 用中主要存在两大缺陷：一是对某些问题演化算法求解速度太慢；二 是演化算法容易产生早熟现象，而且对于单峰函数优化问题，目前的 高校教师在墼亟堂位论文 演化算法还没有鲁棒性。如果函数有多个峰，则可归为多峰函数优化 问题。多峰函数优化问题在保持算法的收敛性之外还要保持解的多样 性。目前研究中主要采用变异、n i c h i n g 策略和s h a r i n g 函数模式等 1 1 2 1 1 3 1 1 1 4 1 。在文献中用得最多的s h a r i n g 函数模式虽然可以用来保持解 的多样性，但也使评估函数发生变化，影响了结果的准确性，因此有 必要解决这两者之间的矛盾。此外，也有研究将演化算法与其他算法 相结合以提高效率，主要采用l e m 、b o a 和人工免疫系统等【1 5 】【1 6 1 1 7 1 。 有研究表明用杂交算子求解实数优化问题时可以得到较好的结 果【4 9 1 【5 0 】f 5 1 1 5 2 。因此，目前对实数函数优化问题的研究中，很多人致 力于研究如何找到一个有效的杂交算子，而它们都有各自的优缺点。 尤其是g t 多父体杂交算子，它不仅具有求解带不等式约束的非线性 的且有复杂场景的函数优化问题的能力，而且也具有搜索的遍历性与 收敛的单调性等特点【1 8 1 。 区域分裂法是适应并行计算机的工作原理的偏微分方程数值解 法，能够借助并行计算机求解规模巨大的工程问题。我国康立山教授 在八十年代初就提出以s c h w a r z 交替法为基础的异步并行算法，并出 版专著1 9 1 。康立山凹】【2 1 1 与唐维伯 2 2 1 应用解的渐近展开，论证了矩形 域上p o i s s i o n 方程的s c h w a r z 交替法的收敛速度与重叠域的关系； e l l i o n z 3 1 应用极值原理论证了一般域上的二阶椭圆形方程的 s c h w a r z 交替法的收敛速度与重叠域的关系。基于混乱松弛法，康立 山提出s c h w a r z 异步并行算法，吕涮冽使用l i o n s 的投影解释给出异 步并行算法较为严格的收敛性证明。目前，所研究的区域分裂方法主 一类基于区域分裂的演化算法及应用 要有：不重叠型、重叠型、虚拟型和多水平型区域分裂法。近十多年 来，已从各个不同角度将区域分裂法应用于求解偏微分方程1 2 5 】【3 0 】。 常微分方程的数值求解已有很长的历史，涌现了很多好算法，如 e u l e r 的单步格式，a d a m s 多步法，r u n g e k u t t a 法，g e a r 方法等【3 1 - 3 5 1 。 这些算法都属于差分方法一类，它们使用了t a y l o r 展开作为基本工 具，即都是在连续可微的函数空间c 中研究，为了得到一定的精度， 往往要求解有很强的光滑性。但目前，利用区域分裂法和有限元方法 结合演化算法求解常微分方程边值问题还未看到有相关文献。 1 3 论文的主要工作 本文介绍了演化算法的基本结构和研究现状，分析了区域分裂法 的基本原理，并将g t 多父体杂交算子进行改造，应用于求解非线性 方程组，在此基础上结合区域分裂法和有限元法求解常微分方程边值 问题。将求解区域分裂成有重叠的小区域，利用有限元进行离散，组 集总矩阵，处理边界条件形成的方程组，再利用郭涛算法求解所形成 的线性或非线性方程组。充分利用了演化算法求解函数优化问题的能 力，以及搜索的遍历性与收敛的单调性等特点。通过实验，证实这种 方法比普通的求解方法具有优越性。首先，我们得到了一种求解常微 分方程边值问题的新方法；其次，利用这种新方法求解得到的结果具 有一定的精度，收敛性比较好。 本文的创新之处：提出了求解非线性方程组的g t 算法。该算法 可以在演化过程中自适应调整搜索空间和种群从而加快收敛，并以它 为基础提出了一类新的求解常微分方程边值问题的数值解的演化算 法。 1 4 论文结构 第一章介绍了论文的研究背景，分析了演化算法和区域分裂法 的研究现状，讲述了论文的主要工作和结构。 第二章首先给出了演化算法的基本结构，主要介绍了各种杂交 算子，分析了他们的优缺点，同时详细介绍和分析了g t 算子及带子 空间的g t 算法的性能。 第三章分析了g t 算法的特点，分析了求解非线性方程组的传 统方法的缺陷，7 提出了求解非线性方程组的g t 算法。 第四章分析了常微分方程边值问题及其数值解法、有限元方法 和区域分裂法的基本原理和求解过程，详细介绍了结合区域分裂法、 有限元法、g t 算法求解的算法。给出了郭涛算法求解非线性方程组 的两个算例以及利用区域分裂法、有限元法和郭涛算法求解常微分方 程边值问题的两个算例并对结果进行了分析。 第五章对全文进行了总结，给出了下一步研究的方向和目标。 一类基于区域分裂的演化算法及应用 2 1 演化算法简介 2 演化算法 最优化理论与算法是一个重要的数学分支，它所研究的问题是讨 论在众多的方案中什么样的方案最优以及怎样找出最优方案，这类问 题普遍存在。长期以来，人们对最优化问题进行了探讨和研究，并随 着历史的发展不断深入。目前，最优化理论和算法在实际应用中正在 发挥越来越大的作用。而其中演化算法是模拟自然界生物演化过程产 生的随机优化策略和技术，目前它已发展成为具有广阔应用前景的研 究方向，已经很好地应用于许多工程应用领域，显示了解决高度复杂 和非线性问题的特别能力。它具有强劲的稳健性，简单，通用，适用 于并行处理，并具有自组织、自适应、自学习等智能特征，适应范围 非常广泛。演化算法的优势在于： ( 1 ) 在指定变量空间搜索求解，具有全局性特点，避免传统数 值方法的局部性。 ( 2 ) 高度的适应性和并行性。 演化算法是用计算机来模拟大自然的演化过程，特别是生命的进 化过程来求解复杂问题的一类计算模型。下面给出了演化算法的基本 流程。 演化算法： t ：= o ： 高校教师在职硕士学位论文 随机初始化种群p ( f ) = 毛，x 2 , - - , ) ； 计算p ( f ) 中个体的适应性； w h i l e ( 不满足停止准则) d o 由p ( f ) 通过遗传操作形成新的种群p ( f ) ； 由p ，( f ) 通过选择操作形成新一代种群p 0 + 1 ) ； 计算p ( f + 1 ) 中个体的适应性； t ：- - t + 1 ： ) 输出p i f ) ； ) 其中t 表示演化代数，p ( f ) 表示第t 代种群，n 为群体的规模，墨 为组成群体的个体，表示问题的一个可能解。 模拟生命进化过程的上述演化算法实质上是一种并行随机算法 ( p a r a l l e ls t o c h a s t i ca l g o r i t h m ) ，可以将算法描述为迭代过程： p ( t + 1 ) - s e p ( f ) 一s 凹口p ( f ) ，t - 0 , 1 , 2 , ，其中p ( o ) 表示初始种群，s 表示选择算子，g 表示遗传算子，遗传算子可以认为是种群进化的内 因，它直接作用于个体的基因型上产生新的个体；选择算子是进化的 外因，它与个体的评价函数( 适应函数) 相关，代表环境对个体的影 响( 适者生存，不适者淘汰) 。总的来说，演化算法主要由七个部分 组成：个体的编码表示、初始化种群、适应函数、遗传操作、选择策 略、算法控制参数和算法终止条件。其中遗传操作与选择策略是影响 演化算法优劣的关键部分，而交叉算子是遗传操作中最主要的遗传算 子，对种群的搜索性能起着重要的作用。 2 2 杂交算子介绍与分析： 杂交算子是演化算法中最具特色的算子，它通过交换和重组父体 的基因信息得到后代个体来不断地探索新的搜索空间。传统的杂交算 子中，受到生物界的自然规律给人的启示，往往将参与杂交的父体个 数设置为2 ，比如常见的混合杂交算子b l x ( 8 l e n dc r o s s o v e r ) ，仿真二 进制杂交算子s b x ( s i m u l a t e db i n a r yc r o s s o v e r ) 等。而t s u t s u ia n dj a i n 首先提出了两种多父体杂交算子：扫描杂交( s c a n n i n gc r o s s o v e r ) 和 对角线杂交( d i a g o n a lc r o s s o v e r ) 。这两种方法是分别将均匀杂交和 单点杂交进行扩展，实验结果显示这两种方法得到的结果优于用两个 父体得到的结果。另外，m u h l e n b e i na n dv o i g t 提出了基因池( g e n e p 0 0 1 ) 的方法：基因池由若干个事先选好的个体组成，基因池重组算 子就是组合池中所有个体的基因。除了用于二进制编码的函数优化问 题外，人们还提出了一些针对实数编码的杂交算子：比如，单纯形杂 交算子s p x ( s i m p l e xc r o s s o v e r ) 就是对父体进行单纯形组合，而k i t a e ta 1 提出的单峰正态分布式杂交算子u n d x ( u n i m o d a ln o r m a l d i s t r i b u t e dc r o s s o v e r ) 则提高了所产生后代的多样性。下面对一些 常用的杂交算子进行介绍。 高校教师在职硕士学位论文 2 2 1b l x 算子 混合杂交算子b l x ( b l c n dc r o s s o v e r ) 首先是由g o l d b e r g 于1 9 9 1 年提出的p q 。但我们从b l x 的特性中不难发现产生的两个后代个体 之间的差异完全依赖于父代的两个个体间的差异，这样就导致了当算 法开始时，由于个体之间的差异较大，使得它们的后代也具有多样性； 但当算法快收敛时，产生的后代就集中于有限的区域，因此有可能导 致过早收敛。另外，b l x 算子中只有两个父体参加重组，因此算子 的遍历性有很大的局限性。后来，人们提出的a r i t h m e t i c 重组算子、 i n t e r m e d i a t e 重组算子以及e x t e n d e d 重组算子等都与b l x 相类似。 2 2 2s b x 算子 仿真二进制杂交算子s b x ( s i m u l a t e db i n a r yc r o s s o v e r ) 首先是由 d e b 和他的学生于1 9 9 5 年提出的阳。对于两个父体z 1 ( f ) 和z ：( f ) ，用 s b x 算子得到的两个后代为： z l ( ) 一0 5 【( 1 + 芦) 五( r ) + ( 1 一p ) z 。( f ) 】 z 2 ( f + 1 ) - o 5 【( 1 一声) z 1 ( f ) + ( 1 + 户) z 2 ( f ) 】 其中，卢的值由下述表达式决定： p 一 ( 2 u 。) 石如果qe o 5 ( 南卜则 其中，7 是一个非负的实数，是自定义的一个参数。，7 越大意味 着越靠近父体的点越有可能被选中成为子代个体，反之则反。 一类基于区域分裂的演化算法及应用 2 2 3s p x 算子 单纯形杂交算子s p x ( s i m p l e xc r o s s o v e r ) 首先是由t s u t s u i 等于 1 9 9 9 年提出的p s l 。多父体单纯形杂交算子使用n + 1 个父体向量 ( 五，i o a ，一) 重组产生后代，这( n + 1 ) 个向量形成彤中的一个单纯 形。将单纯形沿各个方向瓴一o ) 以一定的比例扩张( 其中d 是n + 1 个 向量的中心) ，从扩张后的单纯形中随机地取一点即为一个后代。例 如，如图2 1 所示，我们考虑二维空间中的3 个向量，x o ) ，工( 舶，石( 3 为 3 个向量，这3 个向量形成一个单纯形，把这个单纯形以比例( 1 + 占) 向 外扩张 (p称为扩张比率) ，令 9 1 3 ( x 4 - x ( 2 ) + x ( 3 ) ，y u ) t ( 1 + 占) ，) 一o ) ( ，- 1 , 2 , 3 ) ， 由 y 0 ) ，y ( 2 1 ，y ( 3 ) 产生一个新单纯形，在新单纯形中随机地取一点z ， z 1 q d y o ) + 七2 a y 萄+ 如吵( 3 ) + d ，其中毛，k 2 ，k 3 为 o ，1 】中的3 个随机数， 满足白+ k 2 + 如- i ，z 即为一个三父体单纯形杂交算子产生的后代。 单纯形搜索法是将单纯形中各顶点的信息加以交流来迭代寻优，这与 g a 的杂交算子杂交父代信息极为类似，比较传统g a 的杂交算子， 单纯形搜索法具有方向性，所以寻优速度较g a 的杂交算子要快，且 若能求解则较为准确。 y ( 2 ) 图2 1 二维三父体单纯形杂交 高校教师在职硕士学位论文 2 2 4g t 多父体杂交算子 g t 多父体杂交算子 3 9 1 与单纯形杂交算子类似，但它引入了子空 间的概念，并且将父体组合的空间从传统意义上的【o ，1 1 范围扩展为 【一0 5 ，1 5 】，因此大大扩展了搜索的范围，也得到更好的结果。g t 多 父体杂交算子可以这样描述： 石( f + 1 ) 。善口t 五( f ) ，其中a i 满足条件荟吩。1 ，一o 5 s 口r s l 5 。 从g t 多父体杂交算子的表达式中可以看出，虽然他采用子空间 的方式进行描述，但实际上在算法中并没有真正采用子空间搜索法， 而是一种多父体重组算法。该算子只是随机地从子空间中找一个个 体，这样做的话有时会遗漏掉子空间中较好的解，从而影响搜索的效 果和效率。如果是随机地从子空间中选取多个个体，然后用其中最好 的个体替代当代群体中最差的个体的话，其搜索效果将会更好。 一个非线性规划问题( n l p ) 可以一般性地表示如下： 求m i n f ( x ，l ，) 满足条件 旺，y ) - 0 ，f - 1 ，2 ，白 g i 一( x , y ) s 0 ，f 二协一，k 2 ( 2 1 ) x xs x 。 y t s y s r 其中z 表示一个p 维的实型向量，y 表示一个q 维的整型向量， 并且x e x 7 n x “间取值，r ：庄r t n r , 间取值，目标函数，僻，y ) 、 等式约束岛( x ，l ，) 和不等式约束毋( x ，y ) 一般都是非线性函数，并且都 一类基于区域分裂的演化算法及应用1 1 包含了实型和整型变量。记d 一 ( z ，v ) 4 x 7s x s x 。，y 1s y s p ) 。 因为采用的是实数编码，因此对适应函数中的在实数范围内取值的整 型y 代以“取整函数i n t ( y ) ”，这里i n t ( y ) 定义如下：i n t ( y ) = y 的整数 部分，面无需对算法做任何改变。这一改进，大大地提高了算法的通 用性，而又不产生任何误差。 引入z = ( x ，y ) ，z e d ，其中 d = ( x ，r ) - i x i x x 。，一sy s r ，x e r p , y e r 2 ) 记- 仨踹嬲妇和一叁 定义布尔型函数b e t t e r ： r ( z 1 ) f ( z 2 ) ) f a l s e 另外记d 中m 个点( x ，巧) ，_ j = 1 ，2 ，m 所张成的子空间为： 矿- ( z ，功。i ( x ，聊- 薹吨( 五，x ) 其中吩满足条件吩- 1 , 一0 5 s a is 1 5 综合上述情况，自适应子空间搜索算法可描述如下： b e g i n 初始化p - z 1 ，z 2 , - - - , z ) ；z i d + t 暑o ： - a r g m n f 瓴) ； 高校教师在职硕士学鱼迨塞 z - a r g y 亿) ； _ 孵j w h i l e 不满足结束条件d o 从p 中随机选取膨个点z l ，z 2 ，形成子空间y ； 从y 中随机选取s 个点z 1 ，z 2 ，乙； z 一a r g m ! n f ( z 。) ； 一，o i f b e t t e r ( z ，z 删) t h e nz ：- z ； t - t + 1 ： - a r g 擞f 阮) z 删一哪拖f ( z j ) j l j 一 e n d w h i l e 输出f ，p ，( p ) ； e n d 其中n 为群体p 的大小，m 1 为子空间v 的维数( 如果张成v 的m 个向量线性无关的话) ，t 为迭代次数。乙耐- a r g 燃f 隅) 表示 j i h 把互( f - 1 , 2 , ，n ) 中使，( z ) 最小的那个变量( 个体) 记作z 晰。 算法可简记为一阶随机差分方程组( 齐次m a r k o v 链) ： p ( f + 1 ) - s e l e c t i o n ( m u t a t i o n ( r e c o m b i n a t i o n p ( t ) ) ) t 一0 ，1 2 根据文献【4 0 】，该算法依概率1 收敛。 参数选取如下： ( 1 ) n 的选取，可根据问题的维数n 与场景的复杂性而定，当 n 较大且场景复杂时，n 可取大些，反之，则取小些，一般取 2 0 s ns 1 5 0 ； 一类基于区域分裂的演化算法及应旦 ( 2 ) m 的选取，根据经验取m - 7 、8 、9 或1 0 较合适。 ( 3 ) 子空间的新个体的生成：算法采用随机子空间中的随机搜索 ( 多父体重组) 策略，特别是子空间中随机搜索的非凸性，即 。著记，善q 。5 s q 鲥5 算法采用了深化计算中的群体搜索策略，保证了搜索空间的全局 性。使算法搜索的子空间可覆盖多父体的凸组合空间，保证了随机搜 索的遍历性，即解空间中不存在算法搜索不到的死角。 采用了劣汰策略，每次只把群体中适应最差( 目标函数值最大) 的个体淘汰出局，淘汰压力最小，既保证了群体的多样性，也保证了 适应性最好( 目标函数值最小) 的个体不会被淘汰。这种群体下山策 略，保证了整个群体最后集体达到最深的谷底，当最优解不唯一时， 算法可能1 次同时找到多个最优解。 本章小结 本章介绍了演化算法的基本结构，分析了不同的杂交算子，最后 详细分析了g t 多父体杂交算子，它不仅具有求解带不等式约束的非 线性的且有复杂场景的函数优化问题的能力，而且也具有搜索的遍历 性与收敛的单调性等特点。 高校教师在职硕士学位论文 3 用郭涛算法求解非线性方程组 对方程数与变量数一致的非线性方程组，传统数值解法具有较 快的、与迭代初值有关的局部收敛性。如牛顿法具有局部平方收敛性， 是一种非常有效的局部搜索迭代算法。由于收敛的局部性，对于一些 强非线性方程，传统数值解法容易导致求解失败，有效性较低。因此， 研究针对强非线性方程组效率高的方法是一个较有意义的问题。 郭涛算法是演化算法中的一支。实践证明郭涛算法在求解优化问 题时有着很多的优点，如它算法简单、计算效率高、可以同时找到多 个最优解( 如果问题有多个解的话) 等。郭涛算法的特点为： ( i ) 采用了演化算法中的群体搜索策略，保证了搜索空间的全局 性，有利于搜索问题的最优解。 ( 2 ) 采用了随机子空间的随机搜索，并采用多父体杂交和非凸子 空间搜索策略，保证了随机搜索的遍历性。 ( 3 ) 采用了“劣汰策略”，每次只淘汰群体中最坏的个体，淘汰 压力小，从而保证了群体的多样性。同时，这样的策略也可以保证上 一个群体的最好个体始终完好无缺地在下一个群体中出现。而这样做 就可以保证算法依概率1 收敛到全局最优解。 ( 4 ) 算法采用的是群体下山策略，保证了整个群体最后集体登上 最高峰( 深谷) 。当最优解不惟一时，该算法还可能一次同时找到多 个最优解。 一类基于区域分裂的演化算法及应用 3 1问题描述 我们考虑以下形式的非线性方程组 f 五；瓴，x 2 ，吒) = 0 ，2 = “，x 2 ，吒) = 0 i l = 瓴，x 2 ，毛) = 0 常用的求解非线性方程组的方法包括：二分法，牛顿法，拟牛顿 法，试位法，割线法等。均存在着严重的局限性，如牛顿法，必须已 知根的存在区间且不能区分根与奇点，即使在较小的求根区间内，当 ，o ) 。0 或，o ) 0 时，方法失效1 4 1 1 ，另一方面计算过程中，求导数花 的计算时间较多；拟牛顿法是改进牛顿法中有代表性的一种方法，其 核心思想是用计算函数值代替计算导数。牛顿法及其改进方法具有很 高的收敛速度，但对初始值的选取十分敏感，选取不当将导致迭代解 不收敛或收敛到一个毫无关系的解，对于性态较差的非线性方程组收 敛效果很差。 另外一种思想是将非线性方程组转化为优化问题，常用的非线性 数值优化方法均可以用到非线性方程组的求解中。但由于这些算法也 有初始点敏感、局部收敛等局限性1 。 为便于用郭涛算法求解，先将上述问题转化为一个函数优化问 题。即构造与之等价的优化问题： m i n f ) ；川；“x 2 ，) s t 薯 # ，卅( i = 1 ，2 ，2 n ) 高校教师在职硕士学位论文 为了讨论方便，假设非线性方程组在区域 【砰，】k ，z 】x 。【，】有唯一解，显然，体) 一0 k l 酵一巧) ，则将该分量的上界设为 一- k 2 4 ( 巧一) 。要求七2 妇k l 2 ) 种群调整：在搜索范围调整以后，有些个体的分量可能超出了 可行区域。我们对种群进行了修补。对于那些不在新的搜索范围之内 的分量用搜索范围内的随机数进行替代。 3 ) 还有一种改进策略是在进行分量统计之前首先将种群按照从 好到坏的顺序排列，在实验中我们得知效果更好。如果种群大，进行 排序需要花费时间，因此，我们还是采用前面的策略。 本章小结 本章首先介绍了求解非线性方程组的传统方法如牛顿法等对初 始值的选取十分敏感的局限性，然后介绍了演化算法的优点，提出了 求解非线性方程组的动态调整搜索范围和种群的郭涛算法。 一类基于区域分裂的演化算法及应用 4 基于区域分裂的常微两点边值问题的演化算法 4 1 常微分边值问题及其数值方法简介 本文所讨论的常微分方程边值问题 一0 0 弦，) + g 弦一，o ) ，口 工 o ，当口一0 ，或芦。o 称为齐 次的，否则为非齐次。 问题( 4 1 ) 有着很广泛的应用闱，例如在力学方面，他们的数值 解有着独特的意义。其数值求解方法主要有：试射法( 打靶法) ，差 分法，谱方法和有限元法 3 3 , 4 6 。对问题( 4 1 ) 及其边值条件( 4 2 ) ， 本文采用有限元方法来离散。 高校教师在职硕士学位论文 4 2 有限元法 4 2 1 有限元方法简介 有限元法是用简单方法解决复杂问题的范例。冯康院士曾归纳其 要点为：“化整为零，裁弯取直，以简驭繁，化难于易。”其基础是变 分原理及剖分插值。一方面，有限元法以一种大范围、全过程的数学 分析即变分原理为出发点，而不是从大自然规律的局部的、瞬时的数 学描述即微分方程出发，因此它是传统的r i t z - g a l e r k i n 方法的变 形，与经典的差分方法不同。另一方面，有限元法又采用了分片多项 式逼近来实现离散化过程，它依赖于由小支集基函数构成的有限维子 空间，其离散化代数方程组的系数矩阵高度稀疏，这又与传统的 r i t z - g a l e r k i n 方法不同，而可看作是差分方法的变种。有限元法正 是这两类方法相结合而进一步发展的结果。它具有广泛的适用性，特 别适合几何与物理条件比较复杂的问题，且便于程序标准化，从而适 于工程应用。 由于有限元法有上述优越性，它自6 0 年代以来已作为一种独立的 数值计算方法获得了迅速发展和广泛应用。 4 2 2 插值系数有限元法 有限元法可用来求解非线性问题，具有与求解线性问题相同的好 精度。但是形成的代数方程组复杂，数值求解非线性方程组时，用 n e w t o n 法的迭代过程中要多次对不同的值“i 计算切矩阵，工作量巨 大。z l a m a l ( 1 9 8 1 ) 等在讨论半线性热传问题时曾提出了一个简化的 近似方法，设 一类基于区域分裂的演化算法及应用 h f ( u ) - 工( z ) ， ，) j - l 为f 的分片m 次插值多项式。现在用f ( u ) 的插值厶， 。) 直接代 替复杂的f ( u ) ，得盈j u e s 6 的新方程( 称为插值系数有限元法) 。 ( d u ，三咖) + 瓴，( u ) ，d 1 0 ，力，v s o h ( 3 1 ) 若魂( j 一1 ，2 ，o oo ) 是有限元的基，e h u 一办u ，可得方程组 - 1 ( d 驴f ，上m ) 【，+ ，o i ) f f ) ) 一( g ，谚) ， i - 1 , 2 , ， ( 3 2 ) 一 。 i - 1 或写为矩阵形式： k u + m d i a g 妒) ) - b ，u 一 【，也，巩r 这使离散和求解方程组都得到了简化。 很长时间里，人们不知道插值系数有限元法的逼近精度到底如 何。z l a m a l 在讨论热传问题及线性元时，假定有限元的最大 模m a x l o ) i 关于i i l 一致有界，证明了最佳误差估计一1 1 - o ( h 2 ) ， 近年陈传淼教授进一步证明，对拟一致剖分网格，m 次插值系数有限 元法仍有最佳阶误差一j | | d 伪”1 ) ，而且还进一步证明，经典有限 元的超收敛结果对插值系数有限元法仍然保持m 。也正是基于此，对 于非线性常微分方程两点边值问题，其非线性项我们采用插值系数有 限元法进行离散。 高校教师在职硕士学位论文 4 3 区域分裂法 4 3 1 区域分裂法介绍 区域分裂法【2 1 1 ，有的书上也称区域分解法【镐】，它是基于s c h w a r z 交替法思想和理论发展起来的。区域分裂法就是把计算区域q 分为若 干子域： - u q ；，子域q 。的形状尽可能规则，于是原问题的求解 i - ! 就转化为在子域上求解。区域分裂法特别受到关注是因为它具有其他 方法无以比拟的优越性： l 、它把大问题化为若干小问题，缩小计算规模。 2 、子区域形状如果规则，其上允许使用熟知的快速算法，如快 速f o u r i e r 变换( f f t ) ，谱方法等。或者已经有解这类规则问题的高 效率软件备用。 3 、允许使用局部拟一致网格，无须用整体拟一致网格，甚至各 子域可以用不同离散方法进行计算，这对于形态极不规则的问题，区 域分裂法可以灵活处理。 4 、允许在不同子域选用不同的数学模型，以便整体模型更适合 于工程物理实际情况。 5 、算法是高度并行的，即计算的主要步骤是在各子域内独立进 行的。 6 、对对称区域有更简单的区域分裂算法。 将区域q 分裂为m 2 ) 个子区域q ，( ，m 一仙2 ，m ) ) 之和， 一类基于区域分裂的演化算法及应用 即q ；u q ，。我们约定：对每一j e m ，q ，的边界为r ，u t ，其中 j 1 f ；c r ，称为q j 的拟边界，它是足够光滑的，且 肺坍 - a = u ( r ；n q ，) ，o ，n r j - f i - i 1 若满足上述条件，s 一算法可叙述如下： 格式i ：任给一初始猜测o 以( q ) ，y 时t - o , l 2 ，作品一系列如) 孑， 它们是下述问题集之解： p 口“- ，于q l 内， 1 口柳+ 1 - h “于卜q 1 上， l “删l 脚 a u 棚“一厂于q 2 内， 2 “小2 - “删于阶q 2 上， b 腑2 i 嘲 i i 耽。i “u a 。u 。n t