（计算数学专业论文）一类结合传统优化算法的混合遗传算法.pdf

西北人学硕士学位论文 摘要 遗传算法( g e n e t i ca l g o r i t h m ，简称g a ) 是一种新兴的演化算法。该算法 具有设计简单、容易实现和全局优化能力较强等的优点，因而应用广泛。 传统优化算法能够充分利用问题本身所提供的信息与邻域知识，在搜索空间 中从一个初始点按照某种确定的原则去寻找下一个迭代点，搜索过程具有针对 性，而且收敛速度快、局部寻优能力强。 本文设计出一类结合传统优化算法的混合遗传算法。主要工作概述如下： 首先，由于基本遗传算法随机性较强，使其存在易产生早熟现象、陷入局部 极值点、局部寻优能力差、进化后期收敛慢等缺点。本文正是针对这些问题，提 出将遗传算法和传统的优化算法相结合，给出一类混合遗传算法；其次，对算法 的收敛性进行了理论分析和数值试验，通过在相关的测试函数( t e s tf u n c t i o n ) 的数值试验结果中表现出了令人满意的优化性能，说明了算法的有效性；最后又 将该类混合遗传算法应用到无约束优化问题和约束问题中。 关键词：混合遗传算法，割线法，修正牛顿法，负曲率方向，约束优化问题 两北大学硕士学位论文 o n ek i n do fh y b r i dg e n e t i ca l g o r i t h mc o m b i n e dw i t ht r a d i t i o n a l o p t i m i z a t i o n a b s t r a c t g e n e t i ca l g o r i t h m ( g 砷i san e we v o l u t i o n a r ya l g o r i t h m t h ea l g o r i t h mi s s i m p l e ，e a s yt oi m p l e m e n ta n dh a ss t r o n g g l o b a lo p t i m i z a t i o nc a p a b i l i t y , aw i d e r r a n g eo fa p p l i c a t i o n s t r a d i t i o n a lo p t i m i z a t i o na l g o r i t h mc a nt a k ef u l la d v a n t a g eo ft h ei n f o r m a t i o no f t h ep r o b l e m sp r o v i d e db yt h en e i g h b o r h o o dk n o w l e d g e ，i na c c o r d a n c ew i t ht h e c e r t a i np r i n c i p l e st of i n dt h en e x ti t e r a t i o nf r o ma l li n i t i a lp o i n ti nt h es e a r c hs p a c e ，t h e s e a r c hp r o c e s si st a r g e t e d ，r a p i dc o n v e r g e n c e ，a n dh a sa d v a n t a g e so fs t r o n gl o c a l o p t i m i z a t i o n i nt h i sp a p e r , id e s i g nak i n do fh y b r i dg e n e t i ca l g o r i t h mb a s eo nt r a d i t i o n a l o p t i m i z a t i o na l g o r i t h m m a j o rw o r ks u m m a r i z e da sf o l l o w s ： f i r s t l y , b e c a u s eo ft h es t r o n gr a n d o m n e s s ，s t a n d a r dg e n e t i ca l g o r i t h me a s i l y p r o d u c es h o r t c o m i n g s ，s u c ha sp r e m a t u r ep h e n o m e n o n 、al o c a lm a x i m u m 、t h ep o o r l o c a lo p t i m i z a t i o na n dl a t ee v o l u t i o n a r yc o n v e r g e n c ei ss l o w i nl i g h to ft h e s ep r o b l e m t h i sp a p e rc o m b i n et h eg e n e t i ca l g o r i t h ma n dt h et r a d i t i o n a lo p t i m i z a t i o na l g o r i t h m ，a k i n do fh y b r i dg e n e t i ca l g o r i t h m s ( h g a ) b a s e do nt h et r a d i t i o n a lo p t i m i z a t i o ni s p r o p o s e d ；s e c o n d l y , t h i sp a p e rc o m p l e t et h e t h e o r e t i c a la n a l y s i sa n dn u m e r i c a l e x p e r i m e n t sf o rt h ec o n v e r g e n c eo ft h ea l g o r i t h m ，t h r o u g ht h er e l e v a n tt e s tf u n c t i o n ， t h er e s u l t so fn u m e r i c a le x p e r i m e n t sd e m o n s t r a t es a t i s f a c t o r yo p t i m a lp e r f o r m a n c e a n dt h ee f f e c t i v e n e s so ft h ea l g o r i t h m ；f i n a l l yt h ek i n do fh y b r i dg e n e t i ca l g o r i t h m a p p l i e dt ot h eu n c o n s t r a i n e da n d c o n s t r a i n e do p t i m i z a t i o np r o b l e m k e yw o r d s ：h y b r i dg e n e t i ca l g o r i t h m ；s e c a n tm e t h o d ；n e w t o n sl a wr e v i s i o n ； n e g a t i v ec u r v a t u r ed i r e c t i o n ；c o n s t r a i n e do p t i m i z a t i o n i l 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版。 本人允许论文被查阅和借阅。本人授权西北大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。同时授权中国科学技术信息研 究所等机构将本学位论文收录到中国学位论文全文数据库或其它 相关数据库。 保密论文待解密后适用本声明。 学位论文作者签名：牟指导教师签名： 2 耐年月j 中日2 溺年乡月j 中日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果。据我所知，除了文中特别加以标注和致谢的地方外，本论文不包含其他人已经 发表或撰写过的研究成果，也不包含为获得西北大学或其它教育机构的学位或证书而 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签名： 五军 i 2 。豸年6 月f 午日 西北人学硕士学位论文 第一章引言 1 1 遗传算法( g e n e t i ca i g o ri t h m ) 的起源与发展 大自然是开启人类智慧的老师。大自然中蕴藏着很多深刻的道理，是我们解 决各种问题的源泉。生物在自然界中的生存繁衍，显示出了其对自然环境的优异 自适应能力。从远古时代单细胞开始，生命经过了从低级到高级、从简单到复杂 的演化之路，历经环境变迁的磨难，不但延续了下来而且产生了人类这种有思维、 有智力的高级生命体。人类找到了生命的最佳结构与形式，它不仅可以被动地适 应环境，更重要的是它能够通过学习、模仿与创造，不断提高自己适应环境的能 力。 现代科学理论研究与实践中存在着大量与优化、自适应相关的问题，但除了 一些简单的情况之外，人们对于大型复杂系统的优化和自适应问题仍然无能为 力。然而，自然界中的生物却在这方面表现出了其优异的能力，他们能够以优胜 劣汰、适者生存的自然进化规则生存和繁衍，并逐步产生出对其生存环境适应性 很高的优良品种。遗传算法正是借鉴生物的自然选择和遗传进化机制而开发出的 一种全局优化自适应概率搜索算法n 2 7 1 。 从2 0 世纪6 0 年代开始，美国密西根大学的h o l l a n d 教授就认识到了生物的 遗传和自然进化现象与人工自适应系统的相识关系。他提出在研究和设计人工自 适应系统时，可以借鉴生物遗传机制，以群体的方法进行自适应搜索，并且充分 认识到了交叉、变异等运算策略在自适应系统中的重要性。然而，“遗传算法 词的首次出现却是在h o l l a n d 的学生b a g l e y 于1 9 6 7 年发表的博士论文1 中， 而且此篇博士论文也是在遗传算法应用方面的第一篇论文。其中，他首次在个体 编码上采用了双倍体的编码方式，发展了与目前相类似的复制、交叉、变异、显 形、倒位等基因操作。同时，他还明锐地意识到了在遗传算法执行中的不同阶段 可以使用不同的选择概率，这将有利于防止遗传算法的早熟现象，从而创立了自 适应遗传算法的概念。1 9 7 5 年，h o l l a n d 出版了经典著作自然系统和人工系统 的自适应( a d a p t a t i o ni nn a t u r ea n da r t i f i c i a ls y s t e m ) h 1 ，该书是第一 本系统论述遗传算法和人工自适应的专著，详细阐述了遗传算法的基本理论和方 法，并提出了对遗传算法的理论研究和发展极为重要的模式定理( s c h e m a 西北大学硕十学位论文 t h e o r e m ) ，这一理论首次确认了结构重组遗传操作对于获得隐并行性的重要性， 为其后的发展奠定了数学基础。同年，d e j o n g 完成了具有指导意义的博士论文 “a na n a l y s i so ft h eb e h a v i o ro fac l a s so fg e n e t i ca d a p t i v es y s t e m 州5 1 ， 将h o l l a n d 的模式理论与他的计算实验结合起来，设计了遗传算法执行策略和性 能评价指标，他挑选的5 个专门用于遗传算法数值实验的函数至今仍被频繁使 用，而他提出的在线( o n - li n e ) 和离线( o f f - 1i n e ) 指标则仍是目前衡量算法优化 性能的主要手段。可以认为，d e j o n g 所作的研究工作是遗传算法发展过程中的 一个里程碑。 进入8 0 年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研 究都成了十分热门的课题。1 9 8 5 年，在美国召开了第一届遗传算法国际会议 ( i n t e r n a t i o n a lc o n f e r e n c eo ng e n e t i c a l g o r i t h m s ，i c g a ) ，并且成立国际遗传算 法学会( i n t e r n a t i o n a ls o c i e t yo fg e n e t i ca l g o r i t h m s ，i s g a ) ，以后每两年举行一 次。1 9 8 9 年，h o l l a n d 的学生d e g o l d b e r g 出版了专著搜索、优化和机器学 习中的遗传算法1 。该书总结了遗传算法研究的主要成果，对遗传算法及其应 用作了全面而系统的论述。可以说这本书奠定了现代遗传算法的科学基础，它的 出版有力地推动了遗传算法的传播。同年，美国斯坦福大学的k o z a 基于自然选 择原则创造性地提出了用层次化的计算机程序来表达问题的遗传程序设计 ( g e n e t i cp r o g r a m m i n g , g p ) 方法，成功地解决了许多问题。 1 9 9 1 年，l d a v i s 编辑出版了遗传算法手册( h a n d b o o ko fg e n e t i c a l g o r i t h m s ) n 们，其中包括了遗传算法在工程技术和社会生活中的大量应用实例。 1 9 9 2 年，k o z a 发表了他的专著遗传程序设计：基于自然选择法则的计算机程序 设计”口9 1 。1 9 9 4 年，他又出版了遗传程序设计，第二册：可重用程序的自动 发现陋1 深化了遗传程序设计的研究，使程序设计自动化展现了新局面。目前， 关于遗传算法研究的热潮仍在持续，越来越多的从事不同领域的研究人员已经或 正在置身于有关遗传算法的研究或应用之中。 1 2 遗传算法的特点及应用 遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法，与传统的优 化算法相比，主要有以下特点n ： 2 西= i k 人学硕士学位论文 1 。遗传算法以决策变量的编码作为运算对象。使得我们可以借鉴生物学中 的染色体和基因的概念，可以模仿自然界生物的遗传和进化机理，也使得我们能 够方便的应用遗传操作算子。特别是对一些无数值概念或很难有数值概念，而只 有代码概念的优化间题，编码处理方式更显示出了其独持的优越性。 2 遗传算法直接以适应度作为搜索信怠，并不需要问题导数等与问题直接 相关的信息，容易形成通用算法程序，极大地扩大了应用范围。 3 遗传算法属于一种自适应概率搜索技术，其选择、交叉、变异等运算都 是以种概率的方式来进行的，从而增加了其搜索过程的灵活性。虽然这概率特 性也会使群体中产生一些适应度不高的个体但随着进化过程的进行新的群体 中总会更多地产生出许多更优良的个体，实践和理论都已证明了在一定条件下遗 传算法总是以概率1 收敛到阀题的最优解。 4 遗传算法同时使用多个搜索点的搜索信息，具有隐含并行性。这是遗传 算法与传统优化算法的最大区别。传统的优化算法往往是从单个初始点开始搜索 过程，所提供的搜索信息毕竟不多，导致搜索效率往往不高，有时甚至使搜索过 程陷于局部最优解而停滞不前。而遗传算法则是从由很多个体所组成的一个初始 群体开始最优解的搜索过程，对这个群体所进行的一系列的遗传操作，产生出薪 一代的群体，在这之中包括了很多群体信息，所以实际上相当于搜索了更多的点， 覆盖面大，利于全蜀择优。这是遗传算法所特有的一种隐含特性。最焉，由予它 固有的并行性，遗传算法非常适用于大规模并行计算机。 正是基于遗传算法的这些优越性，使得它目前已经在最优化、组合优化、生 产调度阕题、自动控制、机器学习、数据挖掘和并行处理等领域乜9 “2 一胡得到了 越来越广泛的应用。 本文章节安排如下： 第一章介绍遗传算法的背景、特点和在现实问题中的应用。 第二章余绍遗传算法的基本原理，以及标准遗传算法的具体实现过程，并且 还讨论了遗传算法的缺点和不足。 第三、四章针对标准遗传算法的一些缺点提出了一类结合传统优化算法的混 合遗传算法，详细地阐述了混合遗传算法的思想、具体实现过程和该类遗传算法 气 孤北大学硕二学位论文 的理论分析，并通过数值实验对比发现，新的混合遗传算法的性能有着较显著的 提高。同时用m a t l a b6 5 编译软件编写的应用程序形象地演示该算法收敛过程。 第五章将混合遗传算法的思想拓震到约束闽题的处理上，设计出一种求解约 束问题的混合遗传算法。 第六章总结全文，并提出了进一步需娄解决的问题。 4 鬻j l ：大学磷士学位论文 第= 章遗传算法 2 。 遗传算法的基本原理 遗传算法是由美国密蹰根大学h o l l a n d 畸6 1 教授在1 9 6 9 年提出，后经归纳总 结，形成一类新兴的模拟进化算法，该算法的核心思想是模拟生物进化过程中优 胜劣汰规则与群体内部染色体信息交换辍| 制，从露处理人工自适应系统中的一系 列复杂问题。在遗传算法中，优化问题的所有参数( p a r a m e t e r ) 或者称之为决策 变量都被编码( c o d i n g ) ，形成一个有限长的字符串，称之为染色体( c h r o m o s o m e ) 或个体( i n d i v i d u a l ) 。每个个体都对应于优化问题的一个可行解 ( f e a s i b l es o l u t i o n ) 。一组个体组成代( g e n e r a t i o n ) 种群( p o p u l a t i o n ) ，它描述了遗 传算法的搜索空闻。优毒艺闷题的西标函数作为种群所处的环境，目标函数筐经过 一定的修正后作为个体对环境的适应度( f i t n e s s ) 。搜索时先随机产生一定数量的 经编码后的祖先个体构成最原始的种群。再从这些原始种群开始，模拟进化过程， 运用优胜劣汰原则，先将个体解码( d e c o d i n g ) ，把被编码的参数还原成实际参数， 然盾利用目标函数计算其适应度，再通过选择( s e l e c t i o n ) 将适应度高的个体保留 下来，组成新的种群，最后荐利用交叉( c r o s s o v e r ) 、变异( m u t a t i o n ) 等手段使这些 新的种群的优良特性褥以遗传和保留到下一代。如此“选择一交叉一变异一再选 择 地不断重复，使各代种群的优良基因成分逐渐积累，种群的平均适应度和最 优个体适应度不断上升，直到迭代过程趋于收敛。 图1 1 中表示了遗传算法的循环执行过程： 兰：。严 一胡 爹) 丝翁每 图1 1 5 渗一 2 0 屯一咚。 薅j 艺大学硕士学位论文 在图中，左上圆圈表示初始种群，其包含5 个不同的个体；过对初始种 群依据优胜劣汰规则进行选择操作，形成了具有过渡性质的中间种群。例如提高 初始种群中相对优良个体1 、2 的繁殖机会，同时淘汰掉较差的个体4 、5 ；再 依据交叉概率进行交叉操作，形成新的中间种群。例如，个体2 和个体3 交叉繁 殖出新的个体6 和7 ；再对此种群依据变异概率执行变异，例如个体1 发生变 异，生成新个体9 ；这样就形成了下一代的种群，再通过循环上述四步操作，最 终寻找到最优良的个体。 2 2 标准遗传算法 遗传算法是基于对自然界中生物遗传与进化机理的模仿的种通用性的算 法，很多学者针对不同的阀题设计斑了许多由不同的编码方法和不溺的遗传算子 所构成的各种不同的遗传算法。但其中应用最广泛的是凼g o l d b e r g 总结出的一 种统一的最基本的遗传算法一标准遗传算法班引( s t a n d a r dg e n e t i ca l g o r i t h m s ， s g a ) 或简单遗传算法( s i m p l eg e n e t i c a l g o r i t h m s ，s g a ) 。其具有操作简单，容易 理解的特点，是其他一些遗传算法的基础和雏形，为其他各种遗传算法提供了一 个基本框架。基本遗传算法只使用比例选择算子、单点交叉算子和基本位变异舞 子这三种基本遗传算子畸1 瓢3 1 。 标准遗传算法的具体步骤啷： 对于求解一个复杂系统的优化趣题，我们首先要作好以下准备工作： 确定决策变量及其各种约柬条件，即确定出个体的表现型和问题的解空 间； 然后确定建立优化模型，即确定出目标函数的类型( 是求目标函数的最大 值还是求目标函数的最小值? ) 及其数学描述形式或量化方法； 确定表示可行解的染色体编码方法，也即确定出个体的基因型x 及遗传 算法的搜索空间。将问题的搜索空间中每个可能的点通过某种编码方式表示为确 定长度的二进制串，即染色体； 确定出由目标函数， ) 到个体适应度f ( x ) 的转换规则； 下面我们就可按下述步骤来构造求解该问题的标准遗传算法。 6 1 ，确定遗传算法的有关运行参数，即确定出群体规模m ，杂交概率只、变 异概率只和最大叠代次数t 。 2 ，种群初始化，即在定义域内随机选择肘个染色体组成初始群体i ) ， 并令k 净0o 3 ，计算i ) 中每个染色体x 的适应值f 僻) ； 4 ，从叉 ) 中利用选择算子得到中间种群i 1 1 0 f ) ； 5 ，i u i i f ) 中的每个染色体以e 概率参加交叉，得到x o ) ； ，、一- l z l 6 ，i 2 ( f ) 中每个基因以概率露参与变异运算得到叉o + 1 ) ； 7 ，若不满足预先设定的终止标准则转3 ；否则输出结果。 标准遗传算法的运算过程示意囫2 _ 之如下： 图心 7 西北大学碗士学位论文 2 3 遗传算法的缺点 基本遗传算法由于其运算简单和解块问题的鲁棒性而被广泛应用到众多的 领域。应用实践表明，s g a 在应用中也击出现一些不尽如意的阔题。这些问题 中最主要的是它易产生早熟现象、陷入局部极值点、进化后期收敛慢、局部寻优 能力较差、计算精度较低等缺点。 出现这些缺点的主要原医往往是由于： 种群中出现了某些超级个体，随着模拟生物演化过程的进行，这些个体的 基因物质很快占据种群的统治地位，导致种群中由于缺乏新鲜的基因物质而不能 找到全局最优值； 它的另一个主要原因是由于遗传算法中选择及杂交变异等算子的作用，使 得一些优秀的基因片段过早丢失，从而限制了搜索范围，使得搜索灵能猩局部范 围内找到最优值，而不能得到满意的全局最优值； 另外，短的、低阶、平均之上的模式在遗传算法的后续代中将按几何数数 增长n 们。其直接的结果是：遗传算法以短的、低阶、平均之上的模式的杂交和变 异等操作过程探求了搜索空闻，造成相近模式的基因种群越来越多而且相近模式 的适应值相差不大，最终使种群腑适应度变诧不大，产生新的优值个体就困难。 由于经典的遗传算法存在缺陷，因此许多学者在实践过程中从不同的角度对 基本遗传算法进行了改进，混合遗传算法正是其众多改进方法之一，它能够币同 程度地提高遗传算法翁运行效率和求解质量豫朋州。 8 西北大学硕上学位论文 第三章一类结合传统优化算法的混合遗传算法 3 1 引言 遗传算法是一种通用而有效的求解复杂化化问题的方法，然而，单用简单的 遗传算法在许多情况下并不是十分有效，容易产生早熟现象以及局部寻优能力较 差等问题，于是提出了多种混合遗传算法( h g a ) 。混合遗传算法作为遗传算法的 一个研究方面，既具有一般遗传算法的特点，同时它又融入了特定领域的知识。 混合遗传算法的分类： 首先，混合遗传算法依据被“混合的对象上可分为两类： 将现代优化方法和标准g a 结合。例如，m a h e f o u d n 7 3 提出的遗传模拟退火 算法；文献 1 8 1 提出的基于爬山法和遗传算法的联合搜索算法等； 将传统优化算法与标准g a 结合。例如：文献 1 9 1 提出了一种结合最速下 降法的h g a 。 其次，混合遗传算法依据结合方式的不同可分为直线型结合和相互融合的方 式两类。 对于无约束非线性规划问题， m i n 厂僻) ( 3 1 ) 蚝丑、 石；“，z ：，) r ，魄；皿，o i i s ；，互】，1 c ig n 。q 是自变量的定义 域，f ( x ) 是目标函数且可微。 我们常用的经典方法有最速下降法、共轭梯度法、牛顿法以及割线法。其中 牛顿法的收敛速度较快，达n - ：阶收敛。但其缺点也较明显：它需要我们计算目 标函数f ( x ) 的h e s s i a n 矩阵的逆。同时，牛顿法为2 阶收敛的，割线法的收敛 阶为1 + 一1 6 1 8 ，虽然割线法的收敛速度不如牛顿法那样快，但在函数赋值 构成主要计算量的算法中，割线法每步只需要一次新的函数赋值，而牛顿算法中 的每步却需要两次函数赋值。牛顿法的收敛效率为压，而割线法的收敛效率 1 6 1 8 ，所有它的收敛效率要强于牛顿法，详见文献 2 0 1 。其迭代格式如下： 9 两北大学硕士学位论文 jr。+t。jr。一厂cy。，_ji了i：i】 ( 3 1 1 ) 然而，割线法和牛顿法一样，它们都具有局部收敛性强，对初始点依赖性强 等缺点。 3 2 一种基于割线法的混合遗传算法 3 2 1 混合遗传算法的的思想 结合遗传算法全局收敛性强的优点和割线法局部收敛速度快的特点，参考文 献 2 、 2 0 ，构成一种新的基于割线法的混合遗传算法( h y b r i dg e n e t i ca l g o r i t h m ， 简称h g a ) 。在新的混合算法中，两种算法有条件地交替进行，使其从某一代中 横向来看利用了遗传算法的竞争机制，同时从纵向地发展来看，又引入了割线法 迭代的思想。这样既能保证算法具有全局收敛性的优势，又加强了标准遗传算法 的局部搜索能力，提高搜索效率。 3 2 2 算法设计描述 ( 1 ) 编码方式 我们知道在遗传算法的实现过程中，对于一些多维、高精度要求的连续函数 进行优化时，使用二进制编码首先会存在连续函数离散化时的离散误差；其次， 对于二进制个体编码串的长度控制困难：若长度太短，则精度可能达不到要求； 若太长，虽然能提高精度，但会使遗传算法的搜索空间急剧增大，从而影响遗传 算法的运行性能。本文所设计的混合遗传算法( h g a ) 采用的编码方式是实数编 码。即x = o 。z ：x 。) 的染色体编码是x 1 ，z ：，石。这种编码方式在h g a 中具 有显著的优点：求解精度高，便于较大空间的遗传搜索；便于与经典优化方 法的混合使用。 ( 2 ) 适应度函数的计算 遗传算法在运行时，是由其个体适应度函数值( f i t n e s sf u n c t i o n ) 的大小来 决定其优劣程度和遗传到下一代的概率。个体适应度越大，该个体被遗传到下一 代的概率也越大；反之亦然。本文在选择算子设计时采用比例选择算子，该算子 要求所有个体适应度都是非负数，为了满足这一要求，对目标函数作下列变换： 1 0 西北大学硕士学位论文 删2 0 c - 吖僻x 善怒三乏 2 式中，c m a x 为一个适当地相对比较大的数，可以取自进化到当前代为止的 最大目标函数值。 ( 3 ) 选择算子 比例选择算子实际上是一种有退还随机选择，也称作赌盘( r o u l e t t ew h e e l ) 选择，其具体过程可参见文献乜1 。但由于是其操作带有很大的随机性，所以有时 这种方法所带来的误差也比较大，甚至有可能连适应度较高的个体也无法选中。 这样就会大大降低整个算法的运行效率和收敛速度。为此，我们引进最优保存策 略的思想，即父代适应度最高的个体不参与交叉、变异、割线算子作用的过程， 而直接用它替换掉子代中最差的个体。 ( 4 ) 交叉算子 实数编码中，算术交叉算子是应用最广泛的一种算子，本文也将采用这种方 式。该算子的表述如下： 假设两个体x 。和x ：之间进行算术交叉，则交叉运算后所产生出的两个新个 体是 脬x ；谜2 + 0 - a ) 兄 ( 3 2 2 ) l x ；一硝1 + ( 1 一a ) x 2 上式中，口是在【0 ，1 】之间的参数，它可以是一个常数，也可以是由进化代 数所决定的变量，本文选择为【o ，1 】的随机数。 ( 5 ) 变异算子，本文采用变异算子为均匀变异操作。其描述如下： 假设有一个个体x x 。z ：稚x 。，若坼为变异点，其取值范围为【u ， u k 】，在该点对个体x 进行均匀变异操作后，可到一个新的个体 x x l x ：以x 。，其中变异点的新基因值是： x 。一【，：。+ ，( 【，纛一( ，急) ( 3 2 3 ) 在遗传算法的初期运行阶段，均匀变异使得搜索点可以在整个搜索空间内自 由移动，从而可以增加群体的多样性，是算法能够处理更多的模式，有效地降低 两北大学硕士学位论文 早熟的概率。 ( 6 ) 割线算子 将父代群体经过上述遗传算子运算后得到的群体称之为子代群体，再把对应 的父代个体与子代个体按照割线法迭代( 3 1 1 ) 式进行迭代，得到孙代个体，组 成孙代群体。最后比较相应得子代个体与孙代个体的适应度大小，取其最大者为 下一次进化的父代个体。特别是在进化的中后期，就会有越来越多的个体在最优 解的周围，其割线收敛速度得到充分地发挥。 3 2 3 算法1 的框架 步1 ( 初始化) 确定种群规模，交叉概率，变异概率己；设置终止进化 准则；随即生成个个体作为初始父代种群x ( o ) ；置f ：薯0 。 步2 ( 个体评价) 计算或估计x ( t ) 中各个个体的适应度； 步3 ( 种群进化) 3 1 选择( 母体) 从x o ) 中运用比例选择算子选择出眺j 对母体。 3 2 交叉对所选择的眈j 对母体，依概率执行算术交叉，形成个中间 个体。 3 3 变异对个中间个体分别独立依概率己执行变异，形成子代群体y ( t ) 。 步4 ( 割线迭代) 对应父代个体和子代个体通过( 3 1 1 ) 式进行迭代，形成 个孙代个体，若孙代个体的适应度大于子代个体，即用孙代个体修tg ( t ) 。 步5 ( 最优保存) 用x ( t ) 中适应度最大个体取代r ( t ) 中适应度最差个体。 步6 ( 终止检验) 如以满足终止准则，则输出y o ) 中具有最大适应度的个体 作为最优解，终止计算；否则，置f 暑t + 1 ，x ( t ) 1r ( t ) 并转步2 。 3 3 算法的收敛性分析 3 3 1 遗传算法一般模型的收敛性 本节内容主要参考文献为 2 5 1 1 2 6 2 7 1 2 西北大学硕士学位论文 设s = d y 为个体空间，d 为等位基因，用e = s 肼为种群空间，一般用 x ，y ，z 或x ，k ，z ，表示个体( 染色体编码) ，x 一( x 。，x ：，a ，x ) 等表示种群， x ( t ) 表示第t 代种群，相应地，x t o ) ( is ) 表示第t 代种群第i 个个体。显然 仁( f ) 为状态空间s 上的m 盯k o v 。 定义1 设e 为t 时刻种群x o ) 中所包含的个体的适应值的最大值，厂为适 应值函数f ( x ) 在所有可能的个体所组成的集合中所取的最大值，若只满足： l i m p ( f t 一，) = 1 则称算法收敛到最优解。 定义2 设映射f ：s _ r + 为适应值函数，则记全局最优解集为 m ；忸；v y e s ，僻) ， 定义3 称口为满意解集，若 f ( x ) 乏f ( y ) v xe b ，】，岳曰 从以上定义可以看出满意解集口中每一个个体的适应值均大于满意解之外 的个体适应值。显然最优解集m 为满意解集，并且是所有满意解集之交，即是 最小满意解集。 定义4 称乍o ) j 概率弱收敛到全局最优解，若 l i m p 每( t ) n m 一驴 一1 记作孑g ) 一m ( p 形) 。 定义5 称扛o ) 概率强收敛到全局最优解，若 l i m p 仁( t ) c m 一1 记作i “) 一m f 尸5 ) 。 若在定义4 、定义5 中，我们用满意解集b 代替最小解集m ，这时分别称为 在对应意义下弱( 强) 收敛到满意解集。如果扛o ) 对于任意满意解集是收敛的， 1 3 西北大学硕士学位论文 则必收敛剑全局最优解集。 下面我们参照文献【2 6 】给出扛( f ) 概率弱( 强) 收敛到满意解集的定理。 记口：。p 每o + 1 ) ab = 妒x ( t ) n b 一妒 钟= 尸仁+ 1 ) n b 一妒现) n b 。妒 则有以下定理。 定理1 若仁? ，伽? 满足 1 善( 1 - 一硝) g 舰禹一。 则仁p ) j 概率弱收敛到满意解集b ，即 舰尸每( f ) n 曰一驴j 。1 为了给出概率强收敛的定理，记 口- - 。b = p 每o + 1 ) n b 一x ( t ) n s c ； 苈一p 鼽+ 1 ) n 曰c , j b 妒, x ( t ) n n c 一妒 声。一p 仁p + 1 ) n 曰一妒 定理2 若仁： ，# ：j 满足 ( 1 ) 砉( 1 一苈) 一 ( 2 ) 脚南2 。 则仁o ) j 概率强收敛到满意解集曰，即 l i m p 仁( , ) cb ；1 在文献1 2 6 1 q b 已给出匕述两个定理的证明讨稗。 3 3 2 我们给出一类混合遗传算法的收敛性结果。 1 4 西北大学硕上学位论文 为了得到算法的的依概率收敛性，我们引入文献【2 5 】中的如f 一个定理： 定理3 杰出者选择遗传算法种群序列仁o ) ，f 苫o 是有限齐次m a r k o v 链。 定理4 算法1 所产生的m a r k o v 链序列忙( f ) ，f o 以概率1 收敛到满意种群 集m 的子集m ： 肘；。铲，佤，y n ) ；y ue m 即 l i i n p 仁o ) m ：x ( o ) = x ；1 f 。 证明：因算法1 为杰出者选择遗传算法，故算法1 所严生的柙群j 予夕u 每( f ) ，f o j 是有限齐次m a r k o v 链，且转移概率为 p 仁，哥 ip 扛o + 1 ) ；哥i o ) ；i 则p 仁，哥 有如下性质： ( 1 ) 当x ，y e m ：时，p 伍，】， 0 ，p r ，x 0 ，即x 1 仲y 一一- o l 。一一 ( 2 ) 当x e m o ，哥硭m ：时，p 扛，哥j ，0 ，即菊一哥 于是m ：为正常返的非周期的不可约闭集，s m ；为非正常返的状态集。于 是 熙p 融瓣) i _ 眯而篙 于是 ! i m p 仁( t ) e m o x ( o ) = x 一1 t - - i * o t ， 。 所以从卜诛证明可知此类混合遗传算法以概率1 收敛到最优点集。 3 4 数值仿真实验 通过两个实例来说明算法1 的有效性和可行性。 例1 ：m a x f ( x ) ；工s i n ( 1 0 z z ) + 1 0 x - l 2 】 这是一个简单的多峰值问题( 如图3 - 1 所示) ，理论分析和数值计算表明传 统优化算法很可能得到局部最优解。最优点是1 8 5 0 5 ，最优值是，麟= 2 8 5 0 2 7 4 。 1 5 西北大学硕士学位论文 xs i n ( 1 0 ix 1 + 1 匝 图3 1 例1 的函数图 f i g u r e 3 - 1t h ei m a g eo ft h ee x a m p l e1 例2 ：c a m e l i 垂i 数【2 1 】( 六驼峰函数) 的最优化问题： 1 m i n f ( x ) t ( 4 2 h ；+ 妻z f ) 工；+ z l x 2 + ( 一4 + 4 x 2 ) z ；。 这是一个处处可导的函数( 如图3 2 所示) ，存在6 个局部极小点。最优点是 ( - 0 8 9 8 ，0 7 1 2 6 ) 和( 0 0 8 9 8 ，- 0 7 1 2 6 ) ，最优值是凡。一一1 0 3 1 6 2 8 。 z = ( 4 21 + x 2 + 1 o 3 + x 4 ) + x 2 + x y 叶4 “t y 2 ) y 2 图3 2 例2 的函数图 f i g u r e 3 2t h ei m a g eo ft h ee x a m p l e2 2 1 6 2 0 8 6 4 2 0 2 2 西北大学硕士学位论文 首先，笔者依据所提出的混合遗传算法，在t u r b oc 2 0 环境下，对例1 、例 2 编制了c 语言程序进行数值试验，实验次数为5 0 次。其实验结果如下表： 参数s g ah g a 最优点最优值 n m a x g e n t 厂r m a x g e nt t 函2 01 8 5 0 52 8 5 0 2 7 45 54 4 72 0 数 5 01 8 5 0 52 8 5 0 2 7 42 4 05 0 1 6 57 6 1 1 0 01 8 5 0 52 8 5 0 2 7 43 8 78 2 3 0 01 0 0 函 2 0 ( 0 0 8 9 8 ，- 0 7 1 2 6 ) 1 0 3 1 6 2 8 1 2 0 1 8 7 98 6 数 5 0 ( 0 0 8 9 8 ，- 0 7 1 2 6 ) 1 0 3 1 6 2 84 2 03 0 2 8 01 0 0 2 1 0 0( 0 0 8 9 8 ，m 7 1 2 6 )1 0 3 1 6 2 8 7 3 31 0 0 5 7 01 0 0 注：根据c a m e l 函数的偶性，表中只给出一个最优点。 其中，遗传算法部分参数设置为：种群规模n ；交叉概率p c = 0 4 ；变异概率 p m = 0 0 5 ( 依据反复试验所得的经验取值) ；m a x g e n 表示平均最大代数；t 表示数 据实验次数；t 表示得到最优解的次数 3 5 小结 本章设计了一种基于割线法的混合遗传算法，本算法利用遗传算法和割线法 各自的特点，以使得遗传算法的局部搜索能力有所改善，搜索效率大大提高。通 过数值实验结果表明，混合遗传算法的能够用更少的迭代次数找到最优解，同时 算法的稳定性也较为可靠。文中参数的设定可以参考文献【2 2 】进行适当调整，来 保证种群的多样性。 1 7 西北大学硕士学位论文 第四章融合修正牛顿法的混合遗传算法 4 1 引言 为了改善遗传算法的搜索性能，将修正牛顿法融入到遗传算法之中，而负曲 率方向法是修正牛顿法的又一种类型，所以本章分别提出融合g o l d f e l d 修正牛顿 法和负曲率方向法的混合遗传算法，即算法2 和算法3 。数值结果表明，两种新 算法收敛速度和收敛精度均优于标准遗传算法。 4 2 一种融合6 0 i d f e i d 修正牛顿法的混合遗传算法 4 2 1 算法思想： 新算法结合遗传算法的全局搜索能力和修正牛顿法的局部搜索能力，并通过 自适应因子来调节两者的使用频率。首先通过遗传算法的概率寻优规则指导其搜 索方向，主要起到全局优化的作用，使其能够很快地找到最优点的附近或者次优 点；再通过较高频率地使用修正牛顿法作为其变异算子进行迭代，充分利用了修 正牛顿法的局部搜索能力和运行效率来寻优。在混合遗传算法中全局搜索和局部 搜索以自适应因子取值的大小作为概率交替进行互为补充，最终达到全局优化的 目的。 4 2 2 算法的数学描述 ( 1 ) 编码方式：为了便于较大空间的遗传搜索，易与经典优化方法的混合使 用而采用实数编码的方式，即x ；o ，x ：x 。) 的染色体编码是而，z ：，。 ( 2 ) 适应度函数的确定：参照( 3 2 1 ) 式。 ( 3 ) 选择算子：以轮盘赌原则来进行选择，同时结合最优个体保存策略，详 见文献【2 】。 ( 4 ) 交叉算子：实施算术交叉，即( 3 2 2 ) 式。 ( 5 ) 变异算子：均匀变异和g o l d f c l d 等提出的修正牛顿法变异，以概率，7 的大 小执行g o l d f c l d 等提出的修正牛顿法。，7 为自适应因子，可取为：r 一t t ，其目 的是为了整个算法在初期较多运行均匀变异，保证种群的多样性，避免早熟现象， 1 8 西北大学硕士学位论文 而到了一定阶段“有意识”地提高修正牛顿法变异的使用频率，加强局部搜索能 力。 i ) 均匀变异，即( 3 2 3 ) 式。 j h i ) g o l d f e l d 等提出的修正牛顿法变异。 在牛顿法中，当h e s s e 矩阵q 不正定时，目标函数f ( x ) 的二次模型不一定 有极小点，甚至没有平稳点，二次模型是无界的。为了克服这些困难，g o l d f c l d 等人( 1 9 6 6 ) 提出一种修正牛顿法3 ，这种算法将h e s s e 矩阵g k 改为g k + 唯， 其中1 ，。 0 ，使得g 七+ 咋，正定，从而保证了迭代过程中数值的稳定性。这个具 体的算法过程如下： 给定初始点x 。e r “，第k 步迭代为 令瓦一瓯+ ，其中 唯10 ，如果q 正定； ，七 0 ，( 按( 4 2 3 ) 式计算收) ，否则。 计算玩的c h o l e s k y 分解，瓦一厶见 ( 4 2 1 ) 解瓦d 一一g 。得畋。 令而+ 。一以+ 以。 上述算法中的y 。应按模稍微大于q 的最负的特征值，按照g i l l 和m u 玎a y 的修 改c h o l e s k y 分解算法得到g t + e l d l r ，如果e 一0