（应用数学专业论文）抛物型方程反问题的遗传算法.pdf

摘要 在自然科学与工程技术领域中有许多问题都可以用偏微分方程来描述，研 究偏微分方程的数值解是解决上述问题的有力工具。偏微分方程反问题由于其 源于各种实际背景以及研究领域的广阔性、多学科性等特点，使得其在理论研 究和实际应用方面都有重要意义，己成为一门专门的学科。国内外有很多学者 在这个领域进行研究，并利用各种数值方法和最新的研究结果来解决各种偏微 分方程反问题。但反问题在h a d a m a r d 意义下是不适定的，主要表现在解不连续 依赖于数据，也就是当方程右端项有微小变化时，所求得的近似解与真实值之 间相差非常大，即不稳定。由于反问题的非适定性与非线性，使得它的理论与 求解都比正问题要困难得多，而且涉及面广。目前国内外有许多求解反问题的 方法，例如选择法、拟解法、以及t i k h o n o v 正则化等，p s t ( 脉冲普技术) 与扰 动方法也是求解此类问题的数值方法，但这些方法都各有不足之处。为此本文 提出利用遗传算法求解反问题的新方法。 遗传算法是一种模拟自然界生物进化的搜索算法，由于它的简单易行、鲁 棒性强，尤其是其不需要专门的领域知识而仅用适应度函数作评价来指导搜索 过程，从而使它的应用范围极为广泛，并且己在众多领域得到了实际应用，取 得了许多令人瞩目的成果，引起了广大学者和工程人员的关注。但遗传算法是 一种新兴的技术，正处于发展期，虽然在应用领域获得了丰收，但其理论基础 还较薄弱，有许多地方需要研究和发展充实。本文对遗传算法理论与应用进行 了一些研究工作，在对传统遗传算法的基本结构和基本流程的研究分析基础上， 对传统遗传算法作了一些改进：扩展了传统遗传算法的群体概念，根据生物学 上的“大量繁殖，生存竞争 的原理，细分了原来传统遗传算法的单一群体概 念，提出了根据遗传的不同阶段分为两个不同的群体竞争群体和适应性群 体。在此基础上，提出相关的遗传算子繁殖因子，由此改进了传统遗传算 法计算模型，并将其用在抛物型方程反问题的求解中，通过数值模拟表明，用 改进后的遗传算法求得的近似值与真实解之间具有很小的误差，达到很理想的 程度，证明在实际应用中是可行的，这将对反问题的研究产生十分重要的意义。 关键字：反问题，抛物型方程，遗传算法，竞争群体，适应性群体，繁殖因子 a b s t r a c t t h e r ea r em a n yp r o b l e m sc a nb ed e s c r i b e db yt h ed i f f e r e n t i a le q u a t i o ni n t h e n a t u r a ls c i e n c ea n de n g i n e e r i n gt e c h n o l o g yf i e l d s t u d y i n gt h en u m e r i cs o l u t i o no f t h e s ep a r t i a ld i f f e r e n t i a le q u a t i o n si sas t r o n gt o o lf o r s o l v i n gt h e s ep r o b l e m s i n v e r s e p r o b l e mo fp a r t i a ld i f f e r e n t i a le q u a t i o ni sa ni n t e r d i s c i p l i n a r ya n df r o n t i e rs c i e n c e i t h a sg r e a ts i g n i f i c a n c en o to n l yi nt h e o r yb u ta l s oi np r a c t i c e h o wt os o l v et h ei n v e r s e p r o b l e mo fp a r t i a ld i f f e r e n t i a le q u a t i o nh a sb e e nb e c o m eas p e c i a lc o u r s ea n dm a n v f o r e i g n e r sa n dr e s e a r c h e ss t u d y i n gi nt h i sf i e l d a l lk i n d so fn u m e r i c a lm e t h o d sa n d t h el a s ts t u d y i n gs o l u t i o n sa r eu s e dt os o l v et h ei n v e r s ep r o b l e m t h e s ei n v e r s e p r o b l e m sa r et h ei l l - p o s e di nt h es e n s eo fh a d a m a r d a n dt h e yr e p r e s e n tp r i m a r i l yt h a t s o l u t i o nd o e sn o td e p e n dc o n t i n u o u s l yo nt h ed a t ai e t h ee r r o rb e t w e e nt h es o l v e d a p p r o x i m a t i o na n dt h et r u ev a l u ei sv e r yb i gw h e nt h e r ei sas m a l lc h a n g ei nt h er i g h t t e r m ，t h a ti su n s t a b l e t h et h e o r ya n dt h es o l v i n gs o l u t i o no ft h ei n v e r s ep r o b l e ma r e m o r ed i f f i c u l tt h a nt h o s eo ft h ed i r e c tp r o b l e ma n db er e l a t e dw i t hm a n y m e t h o d sf o r s o l v i n gi n v e r s ep r o b l e mi sn o n l i n e a ra n di l l - p o s e d n o w , t h e r ea r em a n ym e t h o d sf o r s o l v i n gi n v e r s ep r o b l e ma th o m ea n da b r o a d ，s u c ha ss e l e c tm e t h o d ，p a r a s o l u t i o n m e t h o d ，a n dt i k h o n o vr e g u l a r i z a t i o nm e t h o d ，p s ta n dd i s t u r bm e t h o da r ea l s o n u m e r i c a lm e t h o d sf o rs o l v i n gt h i sk i n do fp r o b l e m s b u te a c ho ft h e s em e t h o d sh a s i t ss h o r t a g e s ot h i sa r t i c l ep u t sf o r w a r dan e wm e t h o df o rs o l v i n gi n v e r s e p r o b l e m t h eg e n e t i ca l g o r i t h mi sak i n do f s e a r c h i n gm e t h o dw h i c hs i m u l a t e st h en a t u r a l e v o l u t i o n i ti s s i m p l ea n de a s yt oi m p l e m e n t ，e s p e c i a l l yi td on o tn e e dt h es p e c i a l f i e l dk n o w l e d g e ，s oi th a sb e e nu s i n gi nv e r yb r o a df i e l d s n o wt h eg e n e t i ca l g o r i t h m h a sg o tal o to ff r u i t sa n dm o r es c h o l a r sb e g i nt o p a ya t t e n t i o nt oi t t h eg e n e t i c a l g o r i t h mi ss t i l lan e wt e c h n o l o g yb e i n gi nt h ed e v e l o p m e n t d e s p i t ei t ss u c c e s si ns o m a n yd o m a i n s ，i t st h e o r e t i c a lg r o u n d w o r ki sw e a k t h e r ea r es t i l ll o t so fp r o b l e m st o s t u d ya n dd e v e l o p t h i sp a p e rh a sd o n es o m ew o r ki nt h er e s e a r c h i n go ft h e o r ya n d a p p l i c a t i o no ft h eg e n e t i ca l g o r i t h m b a s e do nt h es t u d yo ft h eb a s i cs t r u c t u r eo ft h e g e n e t i ca l g o r i t h m ，s o m ei m p r o v e m e n ti sg i v e n ：t w on e wc o n c e p t ，a d a p t i v ep o p u l a t i o n l i a n dc o m p e t i n gp o p u l a t i o n a l la b o v ed o n e ，t h ep a p e r g i v e saf l e w 丘锄e w o r ko ft h e g e n e t i ca j g o f i t h m 。p r o p a g a t eg e n e i nt h i s p a p e rt h ei n v e r s ep r o b l e mo fp a r a b o l i c f u n c t i o ni ss o l v e db yt h eu s a g eo ft h eg e n e t i c a l g o r i t h m s t h et e s tr e s u l ti n d i c a t e st h a t t h ee r r o rb e t w e e nt h et r u es o l u t i o na n dt h ea p p r o x i m a t i o no b t a i n e df o mt h eg e n e t i c a l g o r i t h m si sv e r ys m a l l ，a n dc a nr e a c ha p e r f e c te x t e n t a sar e s u l t ，i ti sf e a s i b l ei nt h e p r a c t i c ea p p l i c a t i o n t h i sw i l lp l a ya ni m p o r t a n tr o l e i nt h es t u d yo ft h ei n v e r s e p r o b l e m k e yw o r d s ：i n v e r s ep r o b l e m ；p a r a b 。l i ce q u a t i o n ；g e n e t i ca l g o r i t h m ；c 。m p e t i n g p o p u l a t i o n ；a d a p t i v ep o p u l a t i o n ；p r o p a g a t eg e n e i i i 独创性：声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 期：型堡：! 坌：i1 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即学校有权 保留、送交论文的复印件，允许论文被查阅和借阅：学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：锛洚 导师签名：日期：v 沙子izd 1 傅啦：i 武汉理工大学硕士学位论文 第1 章绪论 1 1 偏微分方程的相关概念 由于反问题是相对于正问题而言的，在此有必要说明一下正问题偏微 分方程的相关概念。事实上微分方程是描述与刻画物理过程、系统状态、社会 与生物现象的有力工具【i 】。应用科学、物理、工程领域中的许多问题可以建立 偏微分方程的数学模型。包含多个自变量的微分方程称为偏微分方程( p a r t i a l d i f f e r e n t i a le q u a t i o n ) ，简称p d e 。一个偏微分方程的表示如下： a o 。4 - b o 捌+ c w = 厂b ，y ，o ；，yj 这里彳，b ，c 是常数，称为拟线。i 生( q u a s i l i n e a r ) 数。 偏微分方程的求解问题是一个十分复杂的问题。除了少数几种特殊情况外， 要求出它的精确解是十分困难的。随着科学技术的发展，近几十年来，其近似 解法在理论上和方法上都有很大的发展，而且在各个领域的应用也愈来愈广泛。 在偏微分方程的数值解法中，最常用的方法是有限差分法和有限元法。 有限差分法的基本思想是用离散的、只含有限个未知数的差分方程( 线性代 数方程组) 去近似代替连续变量的微分方程及边界条件，并把相应的差分方程解 作为微分方程的近似解；有限元法是在古典r i t z - - - g a l e r k i n 变分方法的基础上， 利用分片插值多项式作工具，迅速发展起来的一种数值方法，它特别适用于区 域比较复杂的边值问题。 1 2 反问题的基本概念及研究意义 “要想探求自然界的奥秘在于解微分方程”( 牛顿) ，这种由“原因”推得“结 果”的过程无疑在人类认识自然与改造自然界中起到了重要作用。一般而言， 研究微分方程的中心任务是寻找满足定解问题初、边值条件的微分方程的解， 这就是所谓的微分方程的正问题。微分方程的反问题是指由“果”反推“因”， 武汉理工大学硕士学位论文 即己知或部分己知微分方程的解反求方程中的未知部分【2 】。按照j b k e l l e r 的 提法，若在两个问题中，一个问题的表述或处理涉及到或包含了另一个问题的 全部或部分的知识，称其中一个为正问题，另一个为反问题。就偏微分方程而 言，l e v e m e t i v e 给反问题如下定义：“偏微分方程的反问题是指从偏微分方程解 的某些泛函去确定偏微分方程的系数或右端项”。 例如，工程中的最优与定向设计是按照设计的要求确定参数或形状；遥测 与遥感技术是通过接收( 反射) 回波信息去判断人们感兴趣的物体形状与参数： 地球物理勘探中的反问题就是借助于在地球表面接收到的主动场或被动场的数 据，经过处理，判断地层的结构。这都是属于由“果”推“因”的范畴。数学 中的所有领域几乎都可以推出反问题。 今天许多反问题具有巨大的经济效益和社会效益，且具有较大的难度，因 而吸引了大量的地学家，物理学家和数学家的注意，不少学科领域的权威专家 把反问题列为本学科的发展方向和学术前沿。由于反问题的非适定性、非线性， 使得它的理论与求解都较正问题困难的多，很多问题有待解决，而且涉及知识 面广，牵扯到偏微分方程、常微分方程、数学分析、非线性泛函、变分法、最 优化方法及物体热力学等一系歹t j f , n 识，这就使得反问题的研究遇到了前所未有 的难题。“反问题的发生，发展又一次说明了实践是数学的根本源泉。它的发展 与面临的形式受科学发展的总的潮流的控制与影响。”由实践中提炼出的“反问 题”这一方向必将在广大数学工作者、自然科学工作者及工程技术人员的共同 努力下结合历史的成果开拓出一个崭新的学科领域。反问题的重要性就在于它 的广泛应用性。 1 3 反问题实例 例1 1在地质勘探中，通常根据地球表面测量到的数据，对发生在地球内 部的地质异常所在位置、形状和某些参数加以确定。此反问题是：在地球表面测 量到点x 处所受引力竖直分量式工g ) 的数值，据此确定地面下深度为h 的异常 区域质量密度： p = p ( x )( o x 1 ) 的变化情况。 2 武汉理工大学硕士学位论文 小 _ j l 上专x 0 x l 若p g ) a x 表示x 处“体积元 的质量，g x ) 2 + 办2 是点x 到测量仪 器的距离，根据牛顿万有引力定律，质量p g ) 缸对点x 的引力坚直分量为： 蜕g ，2y 龋c o s 0 = ：y 蒲y 是引力常数 于是，此问题转化为有关质量密度p g ) 的积分方程： 六g ) 2y 。办了i i ：斯 。x ， 例1 2r a d o n 变换最引人注目的应用是在医学成像上，开发出了计算机x 射线断层摄像( c o m p u t e rt o m o g r a p h y ) 技术，简称c t 。假设一固定平面穿过人的 身体，截面上点g ，y ) 的身体密度p g ，j ，) ，三是此平面内任意直线，将一束x 射 线沿三的方向射入人的身体，并测量这束x 射线穿过人体后的衰减程度。 如图，若引入参数g ，万) 对直线l 参数化，则x 射线l 啪用复数表示为： s e 万+ i u e 艿c 其中“，s r ，万0 万) 3 武汉理工大学硕士学位论文 l n i ( o o ) = - y ；。p ( s p 缅+ 讹协伽 x 射线强度，的衰减为： 上式沿三方向线积分得： d i = 一y p l d u 其中y 为一常数 l n ， ) ：一y b k f u e i 8 l t l , t 如果p 是紧支柱函数，x 射线强度的衰减为： l n i ( o o ) - - 一y d 舻砌m 称线积分e p g p 5 + f 材p 坩地为p 的r a d o n 变换，记作 0 p k ，6 ) 一e p g e 够+ f “乜 s r , 8 【0 ，万) 正问题是己知p 计算r a d o n 变换r p 。反问题是己知r a d o n 变换尺p ( 即不 同方向线积分测量值) ，求密度p ，医学c t 检查是r a d o n 变换的反问题。 例1 3 a b e l 积分方程：设一质点沿曲线：f ：x = 吵) 由点p 。，下落到点p 。， 质点仅受到重力m g 的作用。 正问题是当曲线1 1 给定，求质点由点p 。下落到点p 。所用时间t 。反问题是 通过测量质点从位于不同高度h 的点p 。下落到点p 。所用时间的数据，设法求曲 线1 1 。 y 办 p0 4 武汉理工大学硕士学位论文 由能量守恒定律： e + 【厂= 2 m y + 删秒= c 。珊，= ，啦 则有： 车=v=429(h-y)at 从点p 。下落到点p 。所用时间为： 丁= 丁( ) = 等= r 令 ) ：析干歹万，厂q ) ：r ( h v 西 得到a b e l 积分方程： h 0 当s ( h ) 通过测量变为已知，上述反问题转化为关于未知函数矽) 的a b e l 积分方程的求解问题。 更为重要的是a b e l 积分方程也应用在地震学中，人们通过测量地震波的传 播时间，利用a b e l 积分方程可以确定地球的速度分布。 例1 4 热传导方程的初始条件反问题 一维热传导方程为： o u ( x , t ) ：0 2 u ( x , t ) 0 o ) 表示点x 在时刻r 的位移，它满足波动方程： 边界条件： 刖掣= 掣o 0 ( 1 - 6 ) 则边值问题( 1 5 ) ( 1 6 ) 的解为：v ( x ，t ) - - u ( x 物c o s 研+ 6 s i n 积】当且仅当“g ) 和 t f f 满足s t u r m l i o u v i l l e 特征值问题： “”b ) + 万2 p g 必g ) = 0 0 0 定义 脚：主掣h ) z ， “u j = l p 是正则策略，且忙。i i c ( a ) 。当万一0 时，如果口p ) 专。爿f 上t 0 ， 则口= 口p ) 叫做允许的。但实际中，z ，“) 较难以计算，所以t i k h o n o v 构造 了等价性质算法，避开了奇异系。 t i k h o n o v 正则化方法是把求第一类方程彳a z 础= a u j 问题的解转化为求 t i k h o n o v 泛函 厶( z ) ：= l l a z u 2 + 口l | z | | 2 x x 的最小值。 t i k h o n o v 泛函厶有唯一的最小值，而此最小值就是第二类方程 舷叩+ a a z 哪= a u 艿的唯一解，其中口是正则化参数，所以求解反问题转化 为求第二类方程的解，但此法中口要事先给出，如果不能正确给出口，就不能 正确求得正则解。l a n d w e b e r ：迭代方法也是正则化方法的一种，但需要反复求 解正问题，而且口也需要事先给出。m o r o z o v 不一致原理是也是基于t i k h o n o v 正则化方法的一种算法，此法中正则化参数可以根据忡z 哪一材占= 万式后验给 出。 1 4 武汉理工大学硕士学位论文 第3 章遗传算法 当前科学技术正进入多学科互相交叉、互相渗透、互相影响的时代，生命 科学与工程科学的交叉、渗透和相互促进是其中一个典型例子，也是近代科学 技术发展的一个显著特点。遗传算法1 2 2 2 5 l 的蓬勃发展正体现了科学发展的这一 特点和趋势。 遗传算法( g e n e t i ca l g o r i t h m - g a ) ，是模拟达尔文的遗传选择和自然淘汰的 生物进化过程的计算模型。 制造机器智能一直是人类的梦想。人工智能技术的出现，就是人们得到的 成果。但是，近年来，随着人工智能应用领域的不断拓广，传统的基于符号处 理机制的人工智能方法在知识表示、处理模式信息及解决组合爆炸等方面所碰 到的问题已变得越来越突出，这些困难甚至使某些学者对强人工智能提出了强 烈批判，对人工智能的可能性提出了质疑【1 5 叫7 1 。 众所周知，在人工智能领域中，有不少问题需要在复杂而庞大的搜索空间 中寻找最优解或准优解。像规划问题等组合优化问题就是典型的例子。在求解 此类问题时，若不能利用问题的固有知识来缩小搜索空间则会产生搜索的组合 爆炸。因此，研究能在搜索过程中自动获得和积累有关搜索空间的知识，并能 自适应地控制搜索过程，从而得到最优解或准优解的通用搜索算法一直是令人 瞩目的课题。遗传算法就是在这种背景下产生并经实践证明特别有效的算法。 作为一种通用的问题求解方法，遗传算法采用简单的编码技术来表示各种复杂 的结构并通过对一组编码进行简单的遗传操作和优胜劣汰的自然选择来指导学 习和确定搜索的方向。 由于遗传算法在机器学习、过程控制、经济预测、工程优化等领域取得的 成功，已引起了包括数学、物理学、化学、计算机科学、社会科学、经济学及 工程应用领域科学家们的极大兴趣。自8 0 年代中期以来，世界上许多国家都掀 起了遗传算法方面的研究热潮，甚至新的一轮日本计算机发展规划r w c 计 戈l j ( r e a lw 6 r i dc o m p u t i n gp r o g r a m ) 也把遗传算法作为它的主要支撑技术之一，以 进行信息的集成、学习和组织等。 当前，遗传算法已表现出了良好的应用前景，据德国d o r t m u n d 大学1 9 9 3 武汉理工大学硕士学位论文 年的一份研究报告报道，根据不完全统计，遗传算法己在1 6 个大领域2 5 0 多个 小领域获得了应用1 8 】。另外，遗传算法的研究内容也十分广泛，如算法的设计 和分析，其理论基础及在各个领域的应用等等。可以预测，随着遗传算法理论 研究的不断深入和应用领域的不断拓广，遗传算法必将取得更大的成功。 3 1 遗传算法的生物学基础 生命自从在地球上诞生以来，就开始了漫长的进化历程，低级、简单的生 物类型渐渐发展成为高级、复杂的生物类型。生物进化的原因自古至今有着各 种不同的解释，其中被人们广泛接受的是达尔文的自然选择学说。 自然选择学说认为，生物要生存下去，就必须进行生存斗争。生存斗争包 括种内斗争、种间斗争以及生物跟无机环境之间的斗争三个方面。在生存斗争 中，。具有有利变异的个体容易存活下来，并且有更多的机会将有利变异传给下 一代；具有不利变异的个体就容易被淘汰，产生后代的机会也少得多。因此， 凡是在生存斗争中获胜的个体都是对环境适应性比较强的。达尔文把这种在生 存斗争中适者生存，不适者淘汰的过程叫做自然选择。自然选择学说表明，遗 传和变异是决定生物进化的内在因素。遗传是指父代与子代之间，在性状上存 在的相似现象。变异是指父代与子代之间，以及子代的个体之间，在性状上或 多或少地存在的差异现象。在生物体内，遗传和变异的关系十分密切。一个生 物体的遗传性状往往会发生变异，而变异的性状有的可以遗传。遗传能使生物 的性状不断地传送给后代，因此保持了物种的特性。变异能够使生物的性状发 生改变，从而适应新的环境而不断地向前发展。 生物的各项生命活动都有它的物质基础，生物的遗传与变异也这样。根据 现代细胞学和遗传学的研究得知，遗传物质的主要载体是染色体( c h r o m o s o m e ) ， 染色体主要是由d n a ( 脱氧核糖核酸) 和蛋白质组成，其中d n a 又是最主要的 遗传物质。现代分子水平的遗传学的研究又进一步证明，基因( g e n e ) 是有遗传效 应的片断，它储存着遗传信息，可以准确地复制，也能够发生突变，并可以通 过控制蛋白质的合成而控制生物的性状。生物体自身通过对基因的复制 ( r e p r o d u c t i o n ) 和交叉( c r o s s o v e r ) ，即基因分离、基因自由组合和基因连锁互换的 操作使其性状的遗传得到选择和控制。同时，通过基因重组、基因变异和染色 体在结构和数量上的变异产生丰富多彩的变异现象。需要指出的是，根据达尔 1 6 武汉理工大学硕士学位论文 文进化论，多种多样的生物之所以能够适应环境而得以生存进化，是和上述的 遗传和变异生命现象分不开的。生物的遗传特性，使生物界的物种能够保持相 对的稳定；生物的变异特性，使生物个体产生新的性状，以至于形成了新的物 种，推动了生物的进化和发展。 3 2 遗传算法的发展历史 遗传算法研究的兴起是在八十年代末和九十年代初期，但它的历史起源可 追溯到六十年代初期。 遗传算法的创始人是美国密西根大学教授j o h n h h o l l a n d ，他在二十世纪五 十年代末期开始研究自然界的自适应现象，并希望能够将自然界的进化方法用 于实现求解复杂问题的自动程序设计【2 6 1 。在这些研究中，他试图发展一种用于 创造通用程序和机器的理论【3 引，使其具有适应任意环境的能力。他意识到用群 体方法搜索以及选择、交换等等操作策略的重要性。在六十年代中期至七十年 代末期，基于语言智能和逻辑数学智能的传统人工智能十分兴盛，而基于自然 进化的思想则遭到怀疑和反对，h o l l a n d 及其数位博士生仍坚持了这一方向的研 究。b a g l e y 发明“遗传算法”一词【4 0 j 并发表了第一篇有关遗传算法应用的论文， 在他开创性的博士论文中采用双倍体编码，发展了与目前类似的复制、交换、 突变、显性、倒位等基因操作，他还敏锐地察觉到防止早熟收敛的机理，并发 展了自组织遗传算法的概念。与此同时，r o s e n b e r g 在他的博士论文中进行了 单细胞生物群体的计算机仿真研究，对以后函数优化的研究颇有启发，并发展 了自适应交换策略。c a v i c o h i o 在19 7 0 年研究