（计算数学专业论文）改进的实数编码遗传算法解微分方程数值解.pdfVIP

四川火学硕士学位论文 改进的实数编码遗传算法解微分方程数值解 计算数学专业 研究生彭灵翔指导教师胡兵 摘要 遗传算法是模拟自然界生物进化过程的计算模型，从二十世纪六十 年代以来得到了迅速发展和应用。本文论述了遗传算法的基本原理，描 述了基本遗传算法的运行过程。针对二进制编码的遗传算法存在编码误 差，以及收敛速度较慢的不足；实数编码精度高，适合于复杂大空间搜 索，但易使遗传算法在搜索后期效率低下和收敛速度慢的问题；提出了 一种改进的实数编码的遗传算法。 文中提出的改进的算法，采取实数编码解决了二进制编码的遗传算 法存在编码误差，采用确定性排名选择算子，数值杂交算子，多重高期 变异算子，最佳个体保留策略和移民与灭绝算子，大大加快了收敛速度， 并在理论上证明了算法的收敛性；将其应用到解适定的二阶两点边值问 题的数值解，数值例子表明该方法适用于线性和非线性问题：同时为了 缩短解二阶两点边值问题的遗传算法运算时间，提出了逐次由粗到细划 分求解区域，反复多次使用改进的实数编码遗传算法求解二阶两点边值 问题的快速算法，由于每次优化的变量不多，所以运算时间大幅减少， 这种方法能有效的解决一次性编程计算求解区域内多个点处的数值解 时的费时问题，而且便于并行计算。最后将该方法推广到求解拉普拉斯 方程和泊松方程的数值解，数值例子证明该方法的有效性。为工程领域 求解微分方程的数值解提供了种可行的新途径。 关键词：遗传算法，实数编码，两点边值问题，有限差分，微分方程 数值解 四川大学璜士学位论文 i m p r o v e r e a l - c o d e dg e n e t i ca l g o r i t h ms o l v i n gn u m e r i c a l s o l u t i o no fd i f f e r e n t i a le q u a t i o n m a j o r ：c o m p u t a t i o n a lm a t h g r a d u a l ：l i n g x i a n gp e n g a b s t r a c t a d v i s o r ：p r o f b i n gh u g e n e t i ca l g o r i t h mi sac o m p u t a t i o n a lm o d e lw h i c hs i m u l a t e st h en a t u r e e v o l u t i o np r o c e d u r e s s i n c e19 6 0 s ，g ah a sb e e nr a p i d l yd e v e l o p e di nt h e o r ya n d a p p l i c a t i o n t h ep a p e rd i s c u s s e st h eb a s i cp r i n c i p l ea n dp r o c e s so fb a s i cg e n e t i c a l g o r i t h m ，a n da d d r e s st h ep r o b l e mo fb i n a r yc o d i n ge r r o ra n ds l o wc o n v e r g e n c e r a t e ，a n dr e a lc o d e dg e n e t i ca l g o r i t h ms u i t e dc o m p l e xg r e a tr e s e a r c hs p a c eb u ty e ti t h a st h ep r o b l e mo fi n e f f i c i e n c ya n ds l o w l yc o n v e r g i n gi nt h el a t e rp e r i o d a n i m p r o v e dr e a lc o d e dg e n e t i ca l g o r i t h mi sp r o p o s e d i t sm a i no p e r a t o r si n c l u d ed e t e r m i n i s t i cr a n k i n gs e l e c t i n go p e r a t o r , n u m e r i c a l c r o s so p e r a t o r , m u l t i p l eg a u s sm u t a t i o no p e r a t o r , a d o p t i n ge l i t e st ok e e pt h et a c t i c s a n di m m i g r a t i o na n dd e p o p u l a t i o no p e r a t or t h e i m p r o v e dr e a l c o d e dg e n e t i c a l g o r i t h m ，w h i c h c a nq u i c k e nt h e c o n v e r g e n c ev e l o c i t y a n db e p r o v e d t h e c o n v e r g e n c et h e o r e t i c a l l y ，c a n b e a p p l i e dt o s u i t a b l es e c o n d o r d e r t w o - p o i n t b o u n d a r y v a l u ep r o b l e m sn u m e r i c a ls o l u t i o na n dl i n e a ra n dn o n l i n e a rp r o b l e m sa s w e l l t oa c c e l e r a t et h er u n n i n gs p e e d ，o t h e rr a p i dm e t h o dw h i c hu s i n gr e a lc o d e d g e n e t i ca l g o r i t h m c a ns o l v et h en u m e r i c a ls o l u t i o no ft h es e c o n d - o r d e rt w o p o i n t ， 塑型查兰曼主兰垡丝苎一一 b o u n d a r y - v a l u ep r o b l e m ，i sp r o p o d t h em e t h o d sa p p l yt o i m p r o v er e a l c o d e d a l g o r i t h mm a n yt i m e sw h i c hs u c c e s s i v ea l l o c a t i o nt h ec a l c u l a t i o na r e af r o m c o a i r s e t of i n e i tr e d u c e st h er u n n i n gt i m ef o rt h ev a r i a b l e sw h i c h a g e n t l a r g e e a c ht i m e a n de a s yt oc o m ei n t ob e i n gp a r a l l e la l g o r i t h m a n dt h en e wm e t h o d ，w h o s e a v a i l a b i l 姆c a l lb ep r o v e db yn u m e r i c a le x a m p l e s ，c a nb ea p p l i e dt on u m e r i c a l s o l u t i o no fl a p l a c ee q u a t i o na n dp o i s s o ne q u a t i o n t h er e a l - c o d e dg e n e t i ca l g o r i t h m d r o v i d e san e wa v m l a b l em e t h o dt os o l v en u m e r i c a ls o l u t i o no f d i f f e r e n t i a le q u a t i o n f o rt h ee n g i n e e r i n gf i e l d k e y w o r d ：g e n e t i ca l g o r i t h m ，r e a l c o d e d ，t w op o i n tb o u n d a r yp r o b l e m ，d i f f e r e n t i a l e q u a t i o n ，n u m e r i c a ls o l u t i o n 3 四川大学硕士学位论文 声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得四川大学或其他教育机 构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡 献均已在论文中作了明确的说明并表示谢意。 本学位论文成果是本人在四川大学读书期间在导师指导下取得的，论文成 果归四川大学所有，特此声明。 指导教师( 学生( 签名 四川大学磺士学位论文 引言 遗传算法( g e n e t i ca l g o r i t h m ，简称g a ) 由美国m i c h i g a n 大学的h o l l a n d 教 授于1 9 7 5 年首先提出的，是模拟达尔文的遗传选择和自然淘汰的生物进化论的 计算模型。它模拟了自然选择和生命遗传中发生的复制、交叉和变异等现象， 从任一初始种群出发，通过随机选择、交叉和变异操作，产生一群更适应环境 的个体，使群体进化到搜索空间中越来越好的区域，这样一代又一代地不断繁 衍进化，最后收敛到一群最适应环境的个体，得到问题最优解。它作为一种有 效的全局并行优化搜索工具，具有简单、通用、鲁棒性强和适于并行分布处理 的特点。 遗传算法提供了一种求解复杂系统优化的通用框架，不依赖于问题具体的 领域，对各种问题有很强的鲁棒性，所以广泛应用于许多学科”。近十年来， 遗传算法得到迅速发展。且前遗传算法在生物技术和生物学、化学和化学工 程、计算机辅助设计、物理学和数据分析、动态处理、建模与模拟、医学与医 学工程、微电子学、模式识别、人工智能、生产调度、机器人学、丌矿工程、 屯信学、售货服务系统等领域得到了应用，成为求解全局优化问题的有力工具。 在最初的遗传算法是基于二进制串的，类似于生物染色体结构，易于用生 物遗传理论解释，各种遗传操作易于实现，而且算法处理的模式最多。但是二 迸制编码不能直接反映问题固有的结构特征，个体长度大，占用计算机内存多， 在进行数值优化时精度不高，且稳定性不如实数编码。在具体问题中，直接采 用解空间的形式进行编码的实数编码遗传算法，可以直接在解的表现型上进行 遗传操作，从而易于引入特定领域的启发式信息，可以取得比二进制编码更高 的效率，在现代优化理论和神经网络应用中具有重要意义。在求解连续参数优 化问题时，实数编码的遗传算法比二进制编码的遗传算法的收敛速度快且精度 高，因此2 0 世纪9 0 年代以后，基于实数编码的遗传算法得到越来越多的重视和 发展【2 q 】各国学者分别提出了自己的改进算法并使之应用于各个领域。 尽管实数编码精度高，适合于复杂大空间搜索，实数编码遗传算法存在搜 索后期效率低和易形成未成熟收敛的情况。本文提出了一种改进的实数编码遗 传算法，采用确定性排名选择算子，数值杂交算子，币态性变异算子，并增加 个灭绝与移民算子，在理论上证明了其收敛性，将其应用到求解二阶两点边 塑型奎耋曼主竺堡堡苎 值问题的数值解，该方法适用于线性和非线性问题的求解，数值例子验明了该 方法的有效性；同时为加快算法运算速度，还提出一种可节约时间的利用实数编 码遗传算法解二阶两点边值问题的数值解的快速算法：最后将改进的实数编码 遗传算法推广到求拉普拉斯方程和泊松方程的数值解。 本文结构如下： 1 、遗传算法简述 2 、基本遗传算法 3 、改进的实数编码遗传算法 4 、数编码遗传算法解二阶两点边值问题的数值解 5 ，实数编码遗传算法解拉普拉斯和泊松方程的数值解 四川大学硕士学位论文 第一章遗传算法概述 遗传算法( g e n e t i c a l g o r i t h m ，简称g a ) 起源于对生物系统所进行的计算 机模拟系统。美国m i c h i g a n 大学的h o l l a n d 教授及其学生受到生物模拟技术的 启发，创造出了一种基于生物遗传和进化机制的适合于复杂系统优化的自适应 概率优化技术遗传算法。1 9 6 7 年，h o l l a n d 的学生b a g l e y 在其博士论文中 首次提出了“遗传算法”一词，他发展了复制、交叉、变异、显性、倒立等遗传 算子。h o l l a n d 教授用遗传算法的思想对自然和人工自适应系统进行了研究，提 出了遗传算法的基本定理模式定理( s c h e m a t h e o r e m ) ，并于1 9 7 5 年出版 了第一本系统论述遗传算法和人工自适应系统的专著 a d a p t a t i o n i nn a t u r a la n d a r t i f i c i a ls y s t e m s 。2 0 世纪8 0 年代，h o l l a n d 教授实现了第一个基于遗传算法 的机器学习系统，开创了遗传算法的机器学习的新概念。1 9 7 5 年，d ej o n g 基 于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算试验，建立了 遗传算法的工作框架，得到了一些重要且具有指导意义的结论。1 9 8 9 年， g o l d b e r g 出版了g e n e t i ca l g o r i t h mi ns e a r c h o p t i m i z a t i o na n dm a c h i n e l e a r n i n g ) 一书，系统地总结了遗传算法的主要研究成果，全面完整地论述了 遗传算法的基本原理及其应用。1 9 9 1 年，d a v i s 出版了( ( h a n d b o o ko fg e n e d e a l g o f i t h m s 一书，介绍了遗传算法在科学计算、工程技术和社会经济中的大 量实例。 从遗传算法的整个发展过程来看，2 0 世纪7 0 年代是兴起阶段，2 0 世纪8 0 年代是发展阶段，2 0 世纪9 0 年代是高潮阶段。遗传算法作为一种实用，高效、 鲁棒性强的优化技术，发展极为迅速，已引起了国内外学者的高度重视。 1 1 遗传算法的基本术语 由于遗传算法是自然遗传学和计算机科学相互结合渗透而成的新的计算方 法，因此遗传算法经常使用自然进化有关的一些基本术语。 生物的遗传物质的主要载体是染色体，d n a 是其中最主要的遗传物质，而 基因( g e n e ) 又是控制生物性状的遗传物质的功能单位和结合单位。偶数个基 因组成染色体，染色体中的基因的位置称为基因座( l o c u s ) ，而基因所取的值 叫做等位基因( a l l e l e ) 。基因和基因座决定了染色体的特征，也就决定了生物 塑业查兰堡主兰焦丝苎 个体的性质状态。染色体有两种相应的表示模式，即基因型和表现型。所谓表 现型，是指生物个体所表现出来的性质状态，而基因型是指与表现型密切相关 的基因组成。同一种基因型的生物个体在不同的环境条件下可以有不同的表现 型，因此表现型是基因型与环境条件相互作用的结果。在遗传算法中，染色体 对应的数据或数组，在标准的遗传算法中，通常是由一维的串结构数据表现的。 串上各个位簧对应上述的基因座，而各位置上所取的值对应上述的等位基因。 遗传算法处理的是染色体，或者叫基因型个体。一定数量的个体组成群体，也 叫集团。群体中个体的数目称为种群的大小，也叫群体规模。而各个个体对环 境的适应程度叫适应度。执行遗传算法时包含两个必要的数据转换操作，一个 是表现型到基因型的转换，它把搜索空间中的参数或解转换成遗传空间中的染 色体或个体，此过程称为编码操作；另一个是基因型到表现型的转换，它是前 者的一个相反操作，称为译码操作。下表为自然遗传学和遗传算法中使用基本 术语的对应关系。 自然遗传学遗传算法 染色体( c h r o m o s o m e ) 解的编码( 数据、数组、位串) 基因( g e n e )解中每一分量的特征( 特性、个性、位) 等位基因( a i l e l e )特性值 基因座( l o c u s )串中位置 基因型( g e n o t y p e )结构 表现型( p h e n o t y p e ) 参数集、解码结构、候选解 遗传隐匿1 f 线性 个体( i n d i v i d u a l ) 解 适者生存 在算法停止时，最优目标值的解有最人的 可能被留卜 适应性( f i t n e s s )适j 毒! 度函数值 群体( p o p u l a t i o n )选定的一组解( 其中解的个数为群体的规 模) 复胄j j ( r e p m d u c t i o n )根据适应函数值选取的一组解 杂交( c r o s s o v e r ) 通过杂交原则产生- - f t 新解的过程 变异( m u t a t i o n )编码的某一个分量发生变化的过程 4 四川大学磺士学位论文 1 2 遗传算法的基本原理 现在，我们引用上面的术语来更好地描述遗传算法的基本原理。遗传算法 是从代表问题可能潜在的一个种群开始，而一个种群则由经过基因编码的一定 数目的个体组成，每个个体实际上是染色体带有特征的实体。染色体作为遗传 物质的主要载体，即多个基因的集合，其内部表现是某种基因组合决定的，它 决定了个体的外部表现，如黑头发的特征是由染色体中控制这特征的某种基 因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。 由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码。初始种 群产生之后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近 似解。在每一代，根据问题域中的个体的适应度大小挑选个体，并借助自然遗 传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。这个过程 将导致种群像自然进化一样的后生代种群比前代更适应于环境，术代种群中的 最优个体经过解码，可以作为近似最优解。 遗传算法以群体为基础，不是以单点搜索为基础，能同时从不同点获得多 个极值，因此不易陷入局部最优；遗传算法是对问题变量的编码集进行操作， 而不是变量本身，有效地避免了对变量的微分操作运算：遗传算法只是利用目 标函数来区分群体中的个体的好坏而不必对其进行过多的附加操作。 1 3 遗传算法的特点 遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机搜索算法。它 与传统的算法不同，大多数古典的优化算法是基于一个单一的度量函数( 评估 函数) 的梯度或较高次统计，以产生一个确定的试验解序列；遗传算法不依赖 于梯度信息，而是通过模拟自然进化过程来搜索最优解，它利用某种编码技术。 作用于被称为染色体的数字串，模拟由这些串组成的群体的进化过程。遗传算 法通过有组织的，随机的信息交换来重新组合那些数字串，生成新的串的群体。 遗传算法的特点： ( 1 ) 遗传算法处理的是待求问题变量的编码，而不是变量的本身，也就是 说遗传操作是在给定群体中的每个个体数字串上进行。 婴型盔竺堡! ：兰竺堡苎 ( 2 ) 遗传算法使用概率规则而不是确定性规则指导搜索，只要一个适应度 函数值，而不必要求其他辅助信息，谙如连续性、导数存在和单峰等，因而具 有极好的鲁棒性和广泛的适应性。 ( 3 ) 遗传算法通过控制群体中n 个数字串，能处理各代中大量的模式， 在每一代中被处理的模式数目大概是n 3 ，这一切都是在群体中并行进行的，也 就是说，遗传算法同时搜索解空间中许多个点而不是一个点，因而能够快速全 局收敛。遗传算法这种隐含的并行性是它区别于其他优化方法最主要的因素。 ( 4 ) 遗传算法像撒网一样，在变量空间中进行寻优，由n 个数字串组成 的群体在遗传因子的作用下，同时对空间中不同的区域进行充分搜索，从而构 成一个不断优化的群体序列。遗传算法是通过保持在解空间不同区域中各个点 的搜索。而不是盲目地穷举或瞎碰，故相对其他优化方法而吉遗传算法能以 很大的概率找到优化问题的全局最优解。 遗传算法作为一种优化方法，它存在自身的局限性： ( 1 ) 编码不规范及编码存在表示的不准确性。 ( 2 ) 单一的遗传算法编码不能全面地将优化问题的约束表示出来。考虑约 束的一个方法就是对不可行解采用阀值，这样，计算的时间必然增加。 ( 3 ) 遗传算法通常的效率比其它传统的优化方法低。 ( 4 ) 遗传算法容易出现过早收敛。 ( 5 ) 遗传算法对算法的精度、可信度、计算复杂性等方面，还没有有效的 定量分析方法。 1 4 遗传算法与传统方法的比较 对于一个求函数最大值的优化问题，一般可描述为带约束条件的数学规划 模型： f m a x，( x ) j j x r ( 1 ) 【 r c u 式中，x = b ，x 2 ，l ，】7 为决策变量，厂( x ) 为目标函数，u 为基本空间， r 是u 的一个子集。满足约束条件的解称为e u r 解，集合r 表示由所有满足约 6 璺型盔竺曼主竺堡丝苎 柬条件的解组成的一个集合，称为可行解集合。 对于上述最优化问题，目标函数和约束条件种类很多，有的是线性的，有 的是非线性的；有的连续的，有的是离散的；有的是单峰值得，有的是多峰值 得。随着研究的深入，人们逐渐认识到在很多复杂情况下要想完全精确求出其 最优解是不可能的，也是不现实的，因而求出其近似最优解或满意解是人们主 要研究的问题之一。 对于类似上述最优化问题，求最优解或近似最优解的传统方法主要有解析 法，随机法和穷举法。解析法主要包括爬山法间接法。随机法主要包括导向随 机方法和盲目随机方法。而穷举法主要包括完全穷举法、回溯法、动态规划法 和限界剪枝法。 对( 1 ) 类问题可以利用遗传算法求解。雨对于求解此类问题，遗传算法于 一般传统方法有着本质的区别。图1 1 所示传统方法和遗传算法对比示意图。 传统算法 起始于单个点 遗传算法 起始于群体 幽1 1 传统算法和遗传算法对比 1 、遗传算法与启发式算法的比较 启发式算法是指通过寻求一种能产生可行解的启发规则，找到问题的一个 最优解或近似最优解。该方法求解问题的效率较高，但是它对每一个所求的问 题必须找到其特有的启发规则，这个启发规则一般无通用性，不适用于其它问 7 竖业查兰堡圭兰垒堡苎 题。但遗传算法采用的不是确定性规则，而是强调利用概率转换规则来引导搜 索过程。 2 、遗传算法与爬山法的比较 爬山法是直接法、梯度法和h e s s i a n 法的通称。爬山法首先在最优解可能 存在的地方选择一个初始点，然后通过分析目标函数的特性，由初始点移到一 个新的点，然后再继续这个过程。爬山法的搜索过程是确定的，它通过产生一 系列的点收敛到最优解( 有时是局部最优解) ，而遗传算法的搜索过程是随机的， 它产生一系列随机种群序列。二者的主要差异可以归纳为如下两点： ( 1 ) 、爬山法的初始点仅有一个，有决策者给出；遗传算法的初始点有多 个，是随机产生的。 ( 2 ) 、通过分析目标函数的特性可知，爬山法由上一点产生一个新的点： 遗传算法通过遗传操作，在当前的种群中通过杂交、变异和选择产生下一代种 群。对同一优化问题，遗传算法所使用的机时比爬山法所花费的机时要多。但 遗传算法可以处理一些爬山法所不能解决的复杂的优化问题。 3 、遗传算法与穷举法的比较 穷举法就是对解空间内的所有可行解进行搜索，但是通常的穷举法并不是 完全穷举法，即不是对所有解进行尝试，而是有选择地尝试，如动态规划法， 限界剪枝法。对于特定的问题，穷举法有时也表现出很好的性能。但一般情况 下，对于完全穷举法，方法简单易行，但求解效率太低；对于动态规划法，限 界剪枝法，则鲁棒性不强。相比较而言，遗传算法具有较高的搜索能力和较强 的鲁棒性。 4 、遗传算法与盲目随机法的比较 与上述的搜索方法相比，盲目随机搜索法有所改进，但它的搜索效率仍然 不高。一般而言，只有解在搜索空间中形成紧致分布时，它的搜索才有效。而 遗传算法作为导向随机搜索方法，是对一个被编码的参数空间进行高效搜索。 通过上面的探讨，能看到遗传算法与更多的传统优化方法在本质上有着不 同之处，主要有四点不同： ( 1 ) 遗传算法搜索种群中的点是并行的，而不是单点。 ( 2 ) 遗传算法不需要辅助信息或辅助知识，只需要影响搜索方向的目标函 数和相对应的适应度。 ( 3 ) 遗传算法使用概率变换规则而不是确定的变换规则。 8 四川大学项士学位论文 ( 4 ) 遗传算法工作使用编码参数集，而不是自身的参数集。 1 5 遗传算法的应用 遗传算法提供了一种求解复杂系统优化的通用框架，它不依赖于问题具体 的领域，对问题的种类有很强的鲁棒性，所以广泛应用于许多学科。近十年来， 遗传算法得到迅速发展。目前，遗传算法在生物技术和生物学、化学和化学工 程、计算机辅助设计、物理学和数据分析、动态处理、建模与模拟、医学与医 学工程、微电子学、模式识别、人工智能、生产调度、机器人学、开矿工程、 电信学、售货服务系统等领域得到了应用，成为求解全局优化问题的有力工具 之一。 9 四川大学磺士学位论文 第二章基本遗传算法 h o l l a n d 创建的遗传算法是一种概率搜索算法，它利用某种编码技术作用于 称为染色体的数串，其基本思想是模拟由这些串组成的个体进化过程。该算法 通过有组织，然而是随机的信息交换，重新组合那些适应性好的串。在每一代 中，利用上一代串结构中适应性好的位和段来生成一个新的串的群体：作为额 外增添，偶尔也要再在串结构中尝试用新的位和段来替代原来的部分。 遗传算法是一类随机优化算法，它可以有效地利用已有的信息处理来搜索 那些有希望改善解质量的串。类似于自然进化，遗传算法通过作用于染色体上 的基因，寻找好的染色体来求解问题。与自然界相似，遗传算法对待求解问题 本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于 适应度值来改变染色体，使适应性好的染色体比适应性差的染色体有更多的繁 殖机会。 2 i 遗传算法的运行过程 遗传算法模拟了自然选择和遗传中发生的复制、交叉和变异等现象，从任 一初始种群出发，通过随机选择、交叉和变异操作，产生一群更适应环境的个 体，使群体进化到搜索空间中越来越好的区域，这样一代又一代地不断繁衍进 化，最后收敛到一群最适应环境的个体，得到问题最优解。 2 1 1 完整的遗传算法的运算流程 遗传算法的一般步骤如图2 1 所示。 完整的遗传算法运算流程可以用图2 2 来描述。 由图2 2 中可以看出使用上述三种遗传算子( 选择算子、杂交算子和变异 算子) 的遗传算法的主要运算过程如下： ( 1 ) 编码：解空间中的解数据工，作为遗传算法的表现型形式。从表现 型到基因型的映射叫编码。遗传算法在进行搜索之前先将解空阳j 的 数据表示成遗传空阃的基因型串结构数据，这些串数据的不同组合 望! ! ! 查堂堡主兰堡丝苎 构成了不同的点。 ( 2 ) 初始群体的生成：随机产生j v 个初始串结构数据，每个串结构数据 称为一个个体，个体构成了一个群体。遗传算法以这个串结构 作为初始点开始迭代。设簧进化代数计算器t4 - - - 0 ；设置最大进化代 数t ；随机生成的膨个个体作为初始种群p ( o ) 。 ( 3 ) 适应度值评价检测：适应度函数表明个体或解的优劣性。对于不同 的问题，适应度函数的定义方式不同。根掘具体问题，计算群体p ( t ) 中个体的适应度。 ( 4 ) 选择：将选择算子作用于群体。 ( 5 ) 杂交：将杂交算子作用于群体。 ( 6 ) 变异：将变异算子作用于群体。 群体p ( t ) 经过选择、杂交、变异运算后得到下代群体p ( t + 1 ) 。 ( 7 ) 终止条件判断：若f t ，则 以进化过程中所得到的具有最大适应度的个体作为最优解输出；终 止计算。 从遗传算法运算流程可以看出，进化操作过程简单，容易理解，它给其他 各种遗传算法提供了一个基本框架。 一个简单的遗传算法被g o l d b e r g m 来进行轮廓描述并用来举例说明遗传算 法的基本组成。f 代种群用变量p ( t ) 表示，初始种群p ( o ) 是随机设计的，简单 遗传算法的伪代码描述如下： p r o c e d u r eg a b e g i n t - - o ； i n i t i a l i z ep ( t ) ； e v a l u a t e p ( t ) ； w h i l en o tf i n i s h e dd o b e g i n t = t + l ： s e l e c tp ( t ) f r o mp ( t - 1 ) ； r e p r o d u c ep a i r si np ( t ) ； e v a l u a t ep ( t ) ； e n d e n d 四川大学硬上擘位论文 2 1 2 遗传算法的基本操作 遗传算法有三个基本搡作：选择、杂交和变异。 ( 1 ) 选择。选择的目的是为了从当前群体中选出优良的个体，使它们有机会 作为父代为下一代繁殖子孙。根据各个个体的适应度值，按照一定的规 则或方法从上一代群体中选择一些优良的个体遗传到下一代群体中。遗 传算法通过选择运算体现这一思想，进行选择的原则是适应性强的个体 为下一代贡献一个或多个后代的概率大。这样就体现了达尔文的适者生 存原则。 ( 2 ) 杂交。杂交操作是遗传算法最主要的遗传操作。通过杂交操作可以得到 新一代个体，新个体组合了父辈个体的特性。将群体中各个个体随机搭 配成对，对每个个体，以某个概率交换它们之蒯的部分染色体。杂交 体现了信息交换的思想 ( 3 ) 变异。变异操作是在随机群体中选择一个个体，对于选中的个体以一定 的概率随机改变串结构数据中的某个串的值，即对群体中的每一个个体， 以某一概率改变某一个后某一些基因座上的基因值为其他的等位基因。 同生物界一样，遗传算法中变异发生的概率很低。交异为新的个体的产 生提供了机会。 2 四川大学焉士掌位论文 1 1 0 0 1 0 1 0 1 0 1 0 1 1 0 11 1 0 1 杂交l 1 1 0 0 1 0 1 0 1 0 1 1 0 0 1 1 1 1 0 1 o 1 0 1 1 0 l l1 0 1 1 0 1 1 1 0 1 0 肝 0 0 1 l 1 0 1 0 1 0 1 0 1 1 0 0 0 1 ? 0 0 1 l 0 0 1 0 1 0 |变异i _ l i 0 0 1 1 1 0 | 0 1 0 l !li l1 0 0 1 0 1 0 l o 选掸 l o 0 1 1 1 0 1 0 0 11 0 0 1 0 1 0 1 0 1 0 11 0 0 0 】 译码1 h 赌岔 ，一主、 ( 角i i ! ，) t 一一 适心值计算 囝2 1 遗传算法的一股步骤 3 四川大掌磺士学位论文 圈2 3 遗传算法的基本流程 船z 2 遗传算法运算泷程 1 4 四川大掌硬十学位论文 2 2 基本遗传算法 基本遗传算法( 也叫标准遗传算法或简单遗传算法，s i m p l eg e n e t i c a l g o r i t h m 简称s g a ) 是一种群体型操作，该操作以群体中所有个体为对象， 只使用基本遗传算子：选择算子、杂交算子和变异算子。其遗传进化操作简单， 容易理解，是其他一些遗传算法的基础。它不仅给各种遗传算法提供了一个基 本框架，同时也具有一定的使用价值。 2 2 1 基本遗传算法的数学模型 基本遗传算法可表示为：8 g a = ( c ，e ，最，m ，o ，r 甲，t ) 其中：c 个体的编码方法； e 个体适应度评价函数； 只初始种群 凹种群的大小 中选择算子 r 杂交算子 甲变异算子 r 遗传运算终止条件 图2 3 所示为基本遗传算法的流程图。 2 2 2 基本遗传算法的步骤 l 、染色体编码 基本遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位 基因由二值 o ，1 ) 所组成，仞始种群中各个个体的基因可用均匀分布的随机数 来表示。例如：x = 1 0 0 0 1 1 1 0 0 0 1 1 0 1 就可以表示一个个体，该个体的染色体长 度是”= 1 4 。 ( 1 ) 编码：设某一参数的取值范围为： u ，1 ，我们用长度为k 的二进 制编码符号来表示该参数，则它总共产生了2 种不同的编码，可使参数编码时 的对应关系为： 四川大学磺士学位论文 0 0 0 0 0 0 0 0 0 0 0 l0 0 l o = 2 u + 2 8 h 1 1 1 1 1 1 1 1 1 i i i l1 1 1 1 = 2 - - l _ 其中，万= 警。 ( 2 ) 解码：假设某一个体的编码为瓯玩一，瓯2 l6 2 岛，则对应的解码公式为： z ：u i + ( 圭彬爵鲁 2 、个体适应度的检测评估 基本遗传算法按与个体适应度成正比的概率来决定当前群体中各个个体遗 传到下一代群体中的机会多少。为了正确估计这个概率，要求所有个体的适应 度必须为非负数。所以，根据不同种类的问题，需要预先确定好由目标函数值 到个体适应度之间的转换规律，特别是要预先确定当目标函数值为负数时的处 理方法。例如，可选取一个适当大的i f 数c ，使得个体的适应度为目标函数值 加上正数c 。 3 、遗传算子 基本遗传算法适用下列三种遗传算子： ( 1 ) 选择运算使用比例选择算子。比例选择因子是利用比例于各个适应度 的概率决定其子孙的遗传可能性。若设种群数为m ，个体f 的适应度，则个 体被选取的概率为 异：乒 z k 二一j k * l 当个体选择的概率给定后，产生 o ，1 之间的均匀随机数来决定哪个个体参 加交配。若个体的选择概率大，则被多次选中，它的遗传基因就会在种群中扩 大；若个体的选择概率小，则被淘汰。 婴型查兰曼主兰丝丝苎 ( 2 ) 杂交运算使用单点杂交算子。只有一个杂交点位置，任意挑选经过选 择操作厚重群中两个个体作为杂交对象，随机产生一个杂交点位置，两个个体 在杂交点位置互换部分基因码，形成两个个体，如图2 4 所示 父个体1 l 1 1 1 0 1 0 1 ：0 1 0 1 1 0 i 单点杂交 i i t l o t 0 11 0 1 0 0 0 1 l 子个体1 父个体2 f 0 1 1 1 1 0 1o 1 0 0 0 l 叫l0 1 1 1 1 0 10 1 0 1 1 0 l 子个体2 图2 4 单点杂交示意图 ( 3 ) 变异运算使用基本位变异算子或均匀变异算子。为了避免闯题过早收 敛，对于二进制的基因码组成的个体种群，实现基因码的小概率翻转，即0 变 为1 ，而l 变为0 ，如图2 5 所示。 晖ollltol o l o l l o i l 覃 豳2 5 变异操作求意魁 4 、基本遗传算法的运行参数 基本遗传算法有下列4 个运行参数需要预先设定，即m ，r ，只。 膨为种群大小，即群体中含有个体的数量，一般取为2 0 ：i 0 0 ； r 为遗传算法的终止进化代数，一般取为1 0 0 ：5 0 0 ； 尸为杂交概率，一般取为0 4 ：0 9 9 ： 只为变异概率，一般取为0 0 0 0 1 ：0 1 。 7 四川大掌硕士学位论文 第三章改进的实数编码遗传算法 遗传算法是模拟生物进化论的计算模型，是一种有效的全局并行优化搜索 工具，具有简单、通用、鲁棒性强和适于并行分布处理的特点。最初的遗传算 法是基于二进制串的，类似于生物染色体结构，可用生物遗传理论来解释，各 种遗传操作易于实现，算法处理的模式多。但是二进制编码不能直接反映问题 固有的结构特征，个体长度大，占用计算机内存多，数值优化时精度不高，且 稳定性不如实数编码。实数编码是指个体的每个基因值用某一范围内的一个实 数来表示，个体的编码长度等于其决策变量的个数( 因为这种编码方法使用的 是决策变量的真实值，所以也叫真值编码方法) 。例如，若某一个优化问题含有 n 个变量，x ( i = l ，2 ，n ) 每个变量都有其对应的上下限 u 1 m m ，u 1 。 则x = 1 2 ， 5 3 ，3 6 ，4 7 ，】就表示一个体的基因型。其对应的表现型为x = 1 2 ，5 3 ， 3 5 ，4 7 ，】1 。实数编码是遗传算法中在解决连续参数优化问题时普遍使用 的一种编码方式，具有较高的精度，在表示连续渐变问题方面具有优势，不存 在海明悬崖问题。在具体问题中，直接采用解空间的形式进行编码，可在解的 表现型上进行遗传操作，从而引入特定领域的启发式信息，取得比二进制编码 更高的效率。尽管实数编码精度高，适合于复杂大空自j 搜索，但易使遗传算法在 搜索后期效率低下和收敛速度慢。如何加快实数编码遗传算法的收敛速度，这 在优化理论和实际应用中具有重要意义。本文在群体规模确定的情况下，设计 出由排名选择算子、数值杂交算子、正念变异算子、灭绝和移民算子并采用最 佳个体保留策略的改迸的实数编码的遗传算法。能有效地提高收敛速度。 3 1 改进的实数编码逮传算法 一般遗传算法的主要步骤如下： ( 1 ) 随机产生一个由确定长度的特征字符串组成的初始群体； ( 2 ) 对该字符串群体迭代的执行下面的步( a ) 和( b ) ，直到满足停止标准：( a ) 计算群体中每个个体字符串的适应值：( b ) 应用复制、交叉和变异等遗传算子 产生下一代群体。 ( 3 ) 把在后代中出现的最好的个体字符串指定为遗传算法的执行结果，这 璺! ! ! 查竺堡主堂丝丝苎 个结果可以表示问题的一个解。 我们提出改进的实数编码的遗传算法如下： ( 1 ) 初始种群：用实数编码随机产生在约束条件中的。个染色体。 ( 2 ) 适应度计算：根据设计的适应度函数分别计算出初始种群中各个染色 体的适应度。并从大至l j d , 迸行适应度排序。 ( 3 ) 选择算子：基本遗传算法采取赌轮选择算子，但是在个体不太多时， 依据产生的随机数有可能会出现不正确地反映个体适应度的选择，既存在统计 误差，也就是说，适应度高的个体有可能被淘汰，适应度低的个体也有可能被 选择，为克服这种误差。选用确定性比例选择( d e t e r m i n i s t i cs e l e c t i o n ) 。 先计算出保留的染色体个数m 。：n px x r a t e ，剩下的染色体n p 一脚将排名在 。前的个体按下面计算公式计算概率，进行赌轮选择复制进入交配池，并把 它们作为父本进行数值杂交。保留下来的染色体加上通过比例选择算子进入交 配池然后算术杂交产生的新的染色体再次形成个数为的染色体。因此，所有 个体按适应度大小排序，选择概率和适应度无直接关系，仅与序号有关，这样 能有效地为下一代种群提供优秀的个体，并且在实际运算中能节约些运算时间。 只= 掣 即是染色体的适应度排序的序号。 厶， ( 4 ) 杂交算子： 杂交操作的目的是组合染色体中的数值信息，同时增大种群的离散程度， 以产生新的搜索空间。杂交过程采用算术杂交如下： z l ( f ) = a ( i ) p j ( i ) + ( 1 一窃( f ) ) 只( 1 ) z + l ( f ) = ( 1 一口( f ) ) 尸，( f ) + 口( f ) 只( f ) 础) ：丢f 1 + t a n h f 生1 1 ，茎 loj 只和最是从交配池中耿的两个父代染色体，z 和z 。是通过杂交过程产生的 子代染色体，口是杂交权数，i t 、盯为随机数。 ( 5 ) 变异算子： 为了防止早熟现缘，引入变异算子，使参数发生偶尔变动来维持种群的多 样性。变异过程采用正态性变异，公式如下： z ? = z j ( ，) + d m f f ) 四川大学硬士学位论文 m ( i ) = e x i f - ( i 厂- 0 2 ) 1 i n ，1 ，n 。 z 。指通过杂交后的第，个子代染色体，z ? 指通过变异后的第，个子代染色 体，肼是变异高斯函数，d 是随机数。 ( 6 ) 终止准则：满足一定的终止准则。 另外，还设计最佳个体保留算子和灭绝与移民算子。最佳个体保留算子是 把有最好适应度的染色体群作为种子传到下一代。灭绝与移民算孑在当交配池 中的染色体几乎是一样时，或者最佳个体的适应度在一定代数内的增幅小于门 槛