（计算数学专业论文）混合遗传算法（hga）的研究.pdf

摘 要 摘要 遗传算法( g e n e t i ca l g o r i t h m ，简称g a ) 本身所具有的简单、通用、稳健等特性 使得它在困难、复杂实际问题中显示出巨大的优越性，而且能在概率意义下收敛到问 题的全局最优解，但所采用的随机搜索技术却阻碍了算法的收敛速度，而且局部寻优 能力差，往往只能得到全局的次优解。传统优化算法充分利用了问题本身所提供的信 息与邻域知识，在搜索空间中从一个初始点按照某种确定的原则去寻找下一个迭代点， 搜索具有针对性，收敛速度快、局部寻优能力强。将两种算法进行有机的结合而形成 的混合遗传算法( h y b r i dg e n e t i ca l g o r i t h m ，简称h g a ) 无疑有较大的研究空间和价 值。本文对h g a 进行了研究，首先介绍了h g a 的研究现状、特点和研究方法，以早 熟现象的防止、加速g a 的收敛速率、提高通用性为主要目的，结合现有有效的成熟 的技巧设计出h g a ，又将其应用到无约束优化和约束优化中，随后给出了h g a 在某 些条件下收敛性证明，最后一章，对所设计的h ( 认进行基于c 或m a t l a b 的数值试验， 通过数值实验说明了方法的有效性。 关键词：遗传算法( g a )混合遗传算法( h g a )最速下降法 信赖域c 语言 m a t l a b ! 墅! 坠旦 m a s t e rd e g r e ed i s s e r t a t i o n a s t e d yo f h y b r i dg e n e t i c a l g o r i t h m z h a n gx i a o w e i d i r e c t e db y x i n gz h i d o n g d e p lo fm a t h ，n o r t h w e s tu n i v e r s i t y ，x l a n7 1 0 0 6 9 a b s t r a c t g e n e t i ca l g o r i t h m ( f o rs h o r t ，g ao rg a s ) ，w h i c hh a sa s i m p l e ，a l l p u r p o s e ，s u r ec h a r a c t e r , h a sm a d eg r e a ta c h i e v e m e n t si nt h es o l u t i o nt o d i f f i c u l t ，c o m p l e xp r o b l e m s ，a n dc a n c o n v e r g e n c et o t h eo o b a ln t i n i m u m h o w e v e r , r a n d o ms e a r c h t e c h n i q u e sh a n d i c a p c o n v e r g e n c es t e e po fg e n e t i ca l g o r i t h mw h i c hl i k e l yt os e e ko u tal o c a lo p t i m u ms o l u t i o nb u t ag l o b a ls u b o p t i m i z a t i o n t r a d i t i o n a lm e t h o d s ，w h i c hu t i l i z et h ep r o b l e m si n f o r m a t i o na n d c o r r e l a t i v ek n o w l e d g e ，s e e kt on e x ts o l u t i o nf r o ma ni n i t i a l i z ep o i n ti ns e a r c hs p a c ew i t h c e r t a i nd e f i n i t i o n a lc r i t e r i o n ，w i t hp u r p o s e f u ls e a r c h ，s t c e pc o n v e r g e n c ea n d e a s i l ys o l v et oa l o c a lm i n i m u m t h eh y b r i dg e n e t i ca l g o r i t h m ( f o rs h o r t h g a ) w h i c hi n c o r p o r a t et h eg a s i n t ot h eu r a d i t i o nm e t h o d sc a ns u r e l yb es t u d i e dw e l l g ai ss t u d i e di nt h et h e s i sw h i c h i n t r o d u c et h ec i r c u m s t a n c e ，c h a r a c t e r , m e t h o d s ，c o n v e r g e n c ea n d a p p l i c a t i o no fh g a w h i c hi s s i g n e do u t f o r t h ep u r p o s eo fp r e v e n t i o no f p r e m a t u r ep h e n o m e n o n ，a c c e l e r a t i o n o f c o n v e r g e n c ea n di m p r o v e m e n to fa l l - p u r p o s ec h a r a c t e r n u m e r i c a le x p e r i m e n t so fca n d m a t l a bl a n g u a g es h o wt h e s eh g a w o r kw e l li nc h a p t e r4 k e y w o r d s ： g e n e t i ca l g o r i t h mh y b r i dg e n e t i c a l g o r i t h m s t e e p e s td e s c e n tm e t h o d t r u s tr e g i o nm e t h o dc l a n g u a g e m a t l a b 西北大学学位论文知识产权说明书 西北大学学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读学 位期间论文工作的知识产权单位属于西北大学。学校有权保留并向国家有 关部门或机构送交论文的复印件和电子版。本人允许论文被查阅和借阅。 学校可以将本学位论文的全部或部分内容缡入有关数据库进行检索，可以 采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同时，本人保 证，毕业后结合学位论文研究课题再撰写的文章一律注明作者单位为西北 大学。 保密论文 学位论文指导教师签名：盈墨丝 妇年；r 弓1 5 9 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工作及 取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，本 论文不包含其他人已经发表或撰写过的研究成果，也不包含为获得西北大 学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对 本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：维i 趣伟 ii 7 c r d f 年汐月弓日 第一章弓 言 第章引言 1 1 遗传算法( g e n e t i ca i g o ri t h i n ) 的简介 我4 1 自然界充满了奇迹，而生命的繁衍生息则是这些奇迹中的奇迹。生命是脆弱的， 生命也是顽强的。从远古时代单细胞开始，历经环境变迁的磨难，生命经过了从低级到 高级、从简单到复杂的演化之路，不但延续下来，而且产生了人类这样有思维、有智力 的高级生命体。人类找到了最佳结构与形式，它不仅仅可以被动的适应环境，更重要的 是它能够通过学习、模拟与创造，不断提高自己的适应环境的能力。 在人类的历史上，通过学习与模拟来增强自己适应能力的例子不胜枚举。模拟飞禽， 人类可以翱翔天空；模拟游鱼，人类可以横渡海洋；模拟昆虫，人类可以纵观千里；模 拟大脑，人类创造了影响世秀发展的计算机。人类的模拟能力并不仅仅局限于自然现象 和其它生命体。自从2 0 世纪后半叶以来，人类正将其模拟的范围延伸向人类自身。遗 传算法是其中一个典型的代表“。 从六十年代开始，密切根大学教授h o l l a n d 开始研究自然和人工系统的自适应行为， 在这些研究中，他试图发展一种用于创造通用程序和机器的理论，通用程序和机器具有 适应任意环境的能力，他意识到用群体方法搜索以及选择、交换等等操作策略的重要性。 在六十年代中期至七十年代末期，基于语言智能和逻辑数学智能的传统人工智能十分 兴盛，而基于自然进化的思想则遭到怀疑和反对，h o l l a n d 及其数位博士生仍坚持了这 一方向的研究。b a g l e y 发明“遗传算法”一词并发表了第一篇有关遗传算法应用的论文， 在他开创性的博士论文中采用双倍体编码，发展了与目前类似的复制、交换、突变、显 性、倒位等基因操作，他还敏锐地察觉到防止早熟收敛的机理，并发展了自组织遗传算 法的概念。与此同对，r o s e n - b e r g 在他的博士论文中进行了单细胞生物群体的计算机仿 真研究，对以后函数优化的研究颇有启发，并发展了自适应交换策略。c a v i c c h i o 在1 9 7 0 年研究了基于遗传算法的子程序选择和模式识别问题，在模式识别问题上，采用整数编 码，检索空间很大，他提出了以预选择策略保证群体多样性，对遗传算法参数进行中心 控制的方法。同年，w e i n b e r g 研究了生物体的计算机仿真，他的贡献在于提出运用多层 遗传算法来进行遗传算法的参数自优化。1 9 6 8 至1 9 7 1 年，h o l l a n d 提出了重要的模式理 论，建议采用二进制编码，与前面几位博士不同，h o l l a n d 首次采用二迸制编码来研究 函数优化问题，并指出了运用g r a y 码的一些优点，他研究了从生物系统引申出的各种 不同的选择和配对策略。1 9 7 2 年，f r a n t z 的博士论文中研究了许多新的问题，如基因非 线性( 异位显性) 现象，基因迁移操作及多点交叉操作等，由于没有设计出诸如g a - - 1 西北大学硕士学位论文 d e c e p t i o n 之类合适的非线性优化问题，实验结果并不具备说服力。这年，h o l l a n d 的 模式理论也渐趋成熟，但在编码策略上出现了至今仍执争论的二派，一派根据模式定理 建议用尽量少的符号编码，一派以数值优化计算的方便和精度为准采用一个基因一个参 数的方法，并把相应的基因操作改造成适合实数操作的形式，b o s w o r t h ，z o o 和z e i g l e r 是后者的开创者。1 9 7 5 年竖立了遗传算法发展史上的两块里程碑，一是h o l l a n d 出版了 经典著作“a d a p t a t i o n i n n a t u l e a n d a ! l i f i c i a l s y s t e m ”，该书是作者十几年问许多思想及 其实现的结晶，详细阐述了遗传算法的理论，并为其奠定了数学基础，发展了一整套模 拟生物自适应系统的理论；二是d e j o n g 完成了具有指导意义的博士论文“a n a n a l y s i s o f t h e b e h a v i o r o f a c l a s so f g e n e t i c a d a p t i v e s y s t e m ”，他深入领会了模式定理并做了大量 严格的计算实验，给出了明确的结论，还建立了著名的d e j o n g 五函数测试平台，定义 了性能评价标准并以函数优化为例，对遗传算法的六种方案的性能及机理进行了详细 实验和分析，他的工作成为后继者的范例并为以后的广泛应用奠定了坚实的基础。为克 服d e j o n g 的轮盘赌( 随机) 选择操作中的随机误差，b r i n d l e 于1 9 8 1 年在她的博士论文 中研究了六种复制策略。 进入八十年代，随着以符号系统模仿人类智能的传统人工智能暂时陷入困境，神经 网络、机器学习和遗传算法等从生物系统底层模拟智能的研究重新复活并获得繁荣。 g o l d b e r g 在遗传算法研究中起着继往开来的作用，他在1 9 8 3 年的博士论文中第一次把 遗传算法用于实际的工程系统煤气管道的优化，从此，遗传算法的理论研究更为深入 和丰富，应用研究更为广泛和完善，自1 9 8 5 年起，遗传算法及其应用国际会议每二年 召开一次，有关人工智能的会议和刊物上大多有遗传算法的专题，g o l d b e r g 的课本及其 他学者的专著的出版有力地推动了遗传算法的传播嗍。 进入九十年代，以不确定性、非线性、时间不可逆为内涵，以复杂问题为对象的科 学新范式得到学术界普遍认同，如广义进化综合理论，由于遗传算法能有效地求解属于 n p c 类型的组合优化问题及非线性多模型、多目标的函数优化问题，从而得到了多学科 的广泛重视，一些学者也认识到求解复杂问题最优解是不现实的，故而寻求满意解，而 遗传算法是最佳工具之一，生物进化的历史比任何数学证明都强有力，问题是遗传算法 在吸收遗传学、进化论及分子生物学最新成果和在实验得到证明和证伪的同时本身也在 进化。 遗传算法是一类模拟生物进化过程与机制求解问题的自适应人工智能技术，是模拟 自然界生物进化过程的一类自组织、自适应的全局优化算法。它的核心思想源于这样的 2 张晓伟，混合遗传算法的研究 基本认识：从简单到复杂、从低级到高级的生物进化过程本身是一个自然、并行发生的、 稳健的优化过程，这一优化过程的目标是对环境的适应性，而生物种群通过“优胜劣汰” 及遗传变异来达到进化的目的。依达尔文的自然选择与盂德尔的遗传变异理论，生物的 进化是通过繁殖、变异、竞争和选择这四种基本形式来实现的。如果把待解决的问题描 述作为对某个目标函数的全局优化，则g a 求解问题的基本作法是：把待优化的目标函 数解释作生物种群对环境的适应性，把优化变量对应作生物种群的个体，而由当前种群 出发，利用合适的复制、杂交、变异与选择操作生成新的一代种群，重复这一过程，直 至获得合乎要求的种群或规定的进化时限。由于具有鲜明的生物背景和对任何函数类 ( 特别可以无表达式) 可用等突出特点，g a 自8 0 年代中期以来引起人工智能领域的普 遍关注，并被广泛应用于机器学习、人工神经网络训练、程序自动生成、专家系统的知 识库维护等一系列超大规模、高度非线性、不连续、极多峰函数的优化。9 0 年代以来， 对该类算法的研究日趋成为计算机科学、信息科学与最优化领域研究的热点。在g a 中， 待优化的问题通常被转化为某个合适的适应值函数( f i t n e s sf u n c t i o n ) 的极大化，而代 替作用于原优化变量本身，g a 通常作用于原问题变量的某个有限长离散编码( 常为定 长二进制字符串) ，通常称之为个体。个体全体组成的集会称为个体空间。一对个体常 称之为母体。母体空间是由所有母体组成的集合。种群( p o p u l a t i o n ) 规模在迭代过程 中一般是固定的，设其为j 则任意个个体组成的集合即为一个种群。o a 的具体迭 代过程，或等价地，由当前种群生成新一代种群的方法通常由一系列遗传操作( 算子) 决定。这些算子是对自然演化中种群进化机制的类比与模拟。常见的有选择( 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 ) 等。选择算予是种群空间到母体空间的随机映射， 它按照某种准则或概率分布从当前种群中选取那些好的个体组成不同的母体以供生成 新的个体，最常用的选择算子是与个体适应值成比例的所谓比例选择( p r o p o r t i o n a l s e l e c t i o n ) 及r a n k i n g - - b a s e d 选择等。 杂交算子是母体空间到个体空间的随机映射， 它的作用方式是：随机地确定一个或多个向量位置为杂交点，由此将一对母体的两个个 体分为有限个截断，再以概率只( 称为杂交概率) 替换相应截断得到新的个体。依杂交 点个数的多少，杂交算子可分为单点杂交、两点杂交和多点杂交等。多点杂交的极限形 式则称为均匀杂交。 变异算子是个体空间到个体空间的随机映射，其作用方式是：独 立地以概率( 称为变当概率) 改变个体每个分量( 基因) 的取值以产生新的个体。若 用丽表示第f 代种群，赠标准g a 的迭代过程可描述为： s t e p1 ：( 初始化) 确定选择算子只，种群规模 r ，交叉概率，变异概率只和终 3 西北大学硕十学位论文 止原则，令f = o ，随机产生初始种群x ( o ) - - x ，( o ) ，x ：( 0 ) ，x ( 0 ) ： s t e p 2 ：( 个体评价) 计算或估价x ( 1 ) 中个体x ；( f l 的适应度f i t n e s s ： s t e p 3 ：( 选择) 运用选择算子只从当前种群置o ) 中选取m ( j ! l f n ) 对母体； s t e p 4 ：( 交叉) 独立地对所选i f 对母体实施杂交生成m 个中间个体； s t e p5 ：( 变异) 独立地对j l f 个中间个体进行变异得到2 i f 个候选个体； s t e p6 ：( 选择) 从肘个候选个体中依适应度选出个个体组成t + 1 代新种群 x ( f + 1 ) = x l o + 1 ) ，x2 ( f + 1 ) ，x p + 1 ) ) ； s t e p 7 ：( 终止检验) 若满足终止原则，则停止；否则“+ 并返回s t e p2 。 圈1 1 标准g a 的迭代过程 从以上描述可以看出，与通常优化技术中的搜索方法不同，g a 作为一种自适应的 随机搜索方法，其搜索方式是由当前种群所提供的信息，而不是由单一的方向或结构来 决定：同时，它将多个个体作为可能的解并考虑搜索空间全局范围内的抽样，如此导致 其能以更大的可能性收敛到全局最优解。由于这些特性，g a 能够成功地用于求解众多 不问的复杂而困难的优化问题( 包括非数值优化问题) 。2 瑚“”“”。 理论方面的代表性定理是h o l l a n d 提出的模式定理以及由此产生的积木块假设与隐 含并行性的分析。国内外学者大都以定理和假设解释g a 的搜索机制，而用隐含并行性 解释g a 的有效性性。徐宗本等人从公理化模型出发、在严密的数学论证的基础上，清 楚的刻画各个遗传算子的搜索能力而且清楚的刻画了各个遗传操作的合作机制。v o s c 、 l i e p i n s o 用两个确定型矩阵算子分别描述选择操作和繁殖操作，通过研究两个的不动点 的存在性与稳定性来讨论g a 的渐进行为。k o e h l e r 、b h a t t a c h a r y y a 和k o e h l e r 、w r i 曲t 4 张晓伟，混台遗传算法的研究 和v o s e “3 文献都围绕这一方法作了较为深入的研究，但相应的非线性算子只能对几个特 别的遗传算子加以确定，相应的迭代是否收敛到问题的全局最优解并不清楚。c e r f 等采 用摄动理论和m a r k o v 链，对g a 的渐进收敛特征进行分析，得出了g a 运行及全局收 敛性的一般性结论。q j 和p a l m i e r i 对浮点数编码的遗传算法，在基于连续空间中群体规 模为无穷大这一假设下进行了严密的分析。李书全等采用泛函分析理论证明了g a 的收 敛性。在g a 收敛速度和复杂性上的研究国内外很少，但是，该方面的工作都围绕三方 面展开：收敛速度估计、迭代次数估计和时间复杂性估计”“州。 由于遗传算法理论研究要求应用完全不同于传统优化算法的分析与研究方法。有关 遗传算法的己有研究丈都集中于算法的实现、改进与应用方面，而相关的基础理论研究 远落后于算法发展。虽然近年来有关g a 的渐近行为分析受到愈来愈广泛的注意，但已 有的讲究都是就g a 的某一特定实现，或在某一相对弱的意义下讨论算法的收敛性( 或 在某一特定度量下研究其收敛速度) 均具有相当局限性。可以说，到目前为止，还没有 一套完整的理论可以准确、全面地阐明一般g a 的收敛性，从而对其在大量应用中所表 现出的全局优化能力作了理论解释；也还没有找到一个恰当的度嚣与论证方法精确刻画 g a 在不同实现下的收敛速变，从而对g a 的各种改进作出统一、公正的评判。这种一 般数学理论基础的缺乏正致命地限制着g a 的进一步推广、改进与应用。 n f l ( n o f r e e l u n c h ) 定理的出现使一些学者对g a 的有用性、有效性产生质疑， 但其不合理的假设和对简单g a 的分析来否定一般g a 的做法并未减弱人们对g a 的研 究热潮。所有的工作主要围绕两个主题展开：其一，扩大g a 的应用领域、模拟自然进 化原理与机制、模拟生物智能的生成过程并用以求解问题。其= ，在应用领域使之更加 有效，结合数学、生物、计算机技术等各个领域的原理与技巧，使所设计的g a 有预期 的性态和效果m 嘲n 0 1 嘲。 1 2 混合遗传算法( h y b r i d g a ) 研究现状 混合遗传算法作为遗传算法的一个研究方面，不但具有遗传算法的特点，而且，由 于融入特定领域知识而具有自己特有的性质，它的研究主要从两个方面进行： 1 理论研究；编码、算予及算法的设计( 文献1 1 8 1 ，l a e t i t av e r m e u l e nj o u r d a n 等人的 聚类思想；文献【4 1 】，乐慧车，等的投影遗传算法；文献【7 】，e s h e l m a nl 和s c h a f f e r j 实数编码遗传算法) ，收敛性的证明( 文献f 5 】，李书全等人的遗传算法的随机泛函 分析；文献 2 2 1 ，解伟等人的收敛性研究；文献0 8 1 ，f ux u f a n g 等人的遗传算法的 5 西北大学硕士学位论文 代数模型) ，收敛速度的估计( 文献【2 4 】，何琳等的收敛性分析及收敛速度估计) ，等 等。j 】【删一。 2 应用研究；在这方厩的研究遍及各个领域，研究的结果很多，表现出混合遗传算法 的优越性1 7 姗蚓。 理论研究是个难点，收敛性的证明和收敛速度的估计的研究很少，徐宗本等人希望 能从鞅理论解决遗传算法完全意义上的收敛性。收敛速度的研究是在最简单的算法下 得出一些结果，而这些结果对实际的指导意义不大“”“。虽然( 混合) 遗传算法的研 究有喜有忧，但是它的应用价值已显示出巨大的优越性，使得它成为求解困难问题的一 个重要方法。 1 3 的特点及研究方法 h g a 作为一种特殊的g a ，除了g a 具有的特点外，因为它溶进了传统算法充分利 用问题本身所提供的信息与邻域知识，所以又具有本身的特点。 h g a 具有以下特点： ( 1 ) h g a 不是直接作用在参变量集上，而是利用参变量的某种编码； ( 2 ) h g a 不是从单个点开始搜索，而是一个群体，即多个点的集合； ( 3 ) h g a 不仅使用目标函数值( 适应度) 这一信息，而且利用导数等其它信息； ( 4 ) h g a 不仅利用概率转移规则，而且使用局部优化方法的确定性原则； ( 5 ) h g a 在随机优化和传统优化算法之间架起了桥梁，打破了g a 理论研究要 求应用完全不同于传统优化算法的分析与研究方法的局面，拓宽了g a 研究 的数学工具和研究领域。 尽管传统的遗传算法是稳健的，但是就任何一个特殊领域而言，遗传算法一般不是 最成功的最优化算法，它们往往比不上专门处理该领域阿题的算法。 h g a 的研究方法： ( 1 ) 以早熟现象的防止、加速g a 的收敛速率、提高g a 通用性为主要目的、结 合现有有效的、成熟的技巧针对某类问题设计出g a 。 ( 2 ) 针对某类传统优化方法，分析其优缺点，对g a 进行设计然后融入其中，以 克服或改善其缺点，扩大它的应用范围。 ( 3 ) 根据g a 和传统优化方法的数学理论来研究新方法的收敛性，进而改善算法。 ( 4 ) 对算法进行基于c 或m a t l a b 的数值试验，分析结果，改善算法或改进m a t l a b 6 遗传算法工具箱。 张晓伟，混合遗传算法的研究 7 第二二章h g a 算法议计及其应用 第二章t t g a 算法设计及其应刖 2 1 混合策略 混合专j 领域知识和局部搜索算法到遗传算法通常有以下途径： ( 1 ) 采用传统优化方法的编码：在混合算法中采用传统优化算法的编码技术，这个 原则的好处：第一，适应值的计算往往是个相当耗时的过程，如果传统优化算法擅长解 释它的编码，那么就将这种译码技术应用到h g a 中以节省时| 1 = l j ，同时保证了包含在传 统优化算法编码中的有关知识将保持下来，第二，保证了混合遗传算法对实际应用人员 感至0 更自然。 ( 2 ) 吸收传统优化算法的优点：在编码、解码的过程、繁殖操作中溶合专门的领域 知识；在遗传算法的执行步骤中增加局部搜索步。一般的说，是将局部搜索算法产生的 解添加到h g a 到初始种群中设计出特有的繁殖算予，当然这种局部搜索算法一般应该 具有快速收敛、及算法复杂性不高、所使用的的辅助信息容易从问题中获得的特点。 2 2h 淑在无约束优化中的应用 无约束优化因为没有约柬条件，所以遗传算法很容易与其溶合，这是因为，遗传算 子的随机操作不会受约束条件的干扰；算法实现容易，编程简单。 本节没有特殊说明均考虑如下形式的无约束最优化闻题( 即带有简单约束条件) ： 蛳1 1 1f ( x ) * = r a m x 一缸，工l ，工。) 7 ，h i 珐，d f i s i ，t , 1 ，1 墨f s 拜，口是自变量的定义 域。，( x ) 是目标函数而且可微。 2 21 基于最速下降法( s t e e p e s td e s c e n tm e t h o d ) 的h g 本节提出的混合遗传算法，采用的方法是将两种变异算子进行组合，目的在于：第 一，尽可能用较少的搜索代数找到问题最优解，同时又要防止算法陷入局部最优。第二， 尽可能在可接受的代数中提高最优解的精确度，保证算法有较好的平均适应值和最优个 体。 为了算法叙述的方便，现作一些蜕明： ( 1 ) 有关算法的几个符号。 j l f ：每代种群的个数。 ! ! 里堕：塑宣垫生苎堡塑里堕； ：中州种群的个数。 w ：0 到之间随机整数集。 己：变异概率。 f | ：集合缈的阶。即中元素的个数。 g e n ：算法执行的当前代数。 m a x g e n ：算法执行的最大代数。 f i t n e s s ，( 工) ：适应度函数。 ( 2 ) 有关算法的几个概念特定内容。 ( i ) 编码格式：实数编码。即x ( 工l ，一，以，x n ) 的染色体编码是 z 1 卫2 x 善 。 ( j i ) 适应度函数：定义f i t n e s s ，( x ) = 一，( x ) 。 ( i i i ) 变异算予：随机点变异和最速下降法点变异。 ( i ) 随机点变异：对每一个个体善。x ：x i 耳。以概率r 对每一个等位基因工，进 行随机变异，即毛一薯，墨( 峨，l 】) 是随机数。 ( i i ) 最速下降法点变异：对每一个个体工。善：x 。x 。，由最速下降法求出 x x 一g ，其譬是，( x ) 在点x 处的梯度。a 膏是按照w o l f e 原则确定的不精确一维 搜索步长。 ( i v ) 依划分： 将中间种群分成子种群i 和子种群i i 定义： i = 盖fi 1 j fs n ，f 硭 l i = x fi1 s f s 万，f ) 现将算法描述如下： 随机产生初始种群的m 个个体，然后以轮盘赌原则选择产生n ( n 2 m ) 个个 体形成中阈种群，将中间种群依划分成两部分：予种群i 和子种群j j ，分别进行随 机点变异和最速下降法点变异，然后按适应度由高到低对中间种群进行排序，前m 个 个体以概率1 复制到下一代中，形成新一代种群。重复以上过程，直到满足终止条件为 止。 下面给出算法步骤： 算法2 2 1 1 9 西北大学硕：匕学位论文 s t e p1 ：初始化参数肼，t iwl ，m a x g e n ， l ，并令g p 以；0 。 s t e p2 ：初始化种群。随机产生膳个个体。 s t e p3 ：如果g e n m a x g e n ，则停止并输出结果，否则转s t e p4 。 s t e p4 ：产生中间种群。以轮盘赌原则选择产生n ( n 2 m ) 个个体形成中间种 群。 s t e p5 ：依矽划分种群。对子种群l 和子种群i i ，分别进行随机点变异和最速下降 法点变异。 s t e p6 ：排序。按适应度由高刳低进行排序。 s t e p7 ：产生新一代种群。中间种群前m 个个体以概率1 复制到下一代中，形成新 一代种群。并且g 蜘+ + 。转s t e p 3 。 下面给出算法的流程图： 豳2 2 1 基丁最速下降法的h g a 流程图 1 0 张晓伟，混合遗传算法的研兜 2 2 2 基于牛顿法( n e w t o nm e t h o d ) 的h g a 我们知道最速下降法其实并不是“最速”下降的，当迭代点靠近最优解时，搜索的 方向成“锯齿”形，但是在最优解的附近，目标函数的形态和二次函数非常接近“8 “， 因此我们可以将牛顿法融入到遗传算法中以期望可以增强算法的局部寻优能力，而在牛 顿法中，要求解一个g 吼一g 。的方程，这个的计算量是很大的，当然可以用g a 去求 解，于是去求解： r a i n 慨仃+ g t l l 其中，q = v 2 ，瓴) ，g 。一v 瓴) 算法2 2 2 1 s t e p1 ：初始化参数，并令g e n = o 。 s t e p2 ：初始化种群。随机产生m 个个体。 s t e p3 ：如果g e n2m a x g e n ，则停止并输出结果，否则转s t e p4 。 s t e p4 ：交叉、变异操作形成中间种群。 s t e p5 ：产生新代种群。中问种群前m 个个体以概率1 复制到下一代中，形成新 一代种群。并且g 吼+ + 。转s t e p3 。 如果假设q 正定，可以用d f p 校正公式n 2 m ”： 吨+ 旁一面h d , t h 去逼近何1 ，其中，g r 一+ ，一，7 1 一+ 。一g k 。 算法2 2 2 2 s t e p1 ：初始化参数，并令g e n ：o 。 s t e p2 ：初始化种群。随机产生肼个个体。 s t e p3 ：如果g 鲫m a x g e n ，则停止并输出结果，否则转s t e p 4 。 s t e p4 ：产生中间种群。以轮盘赌原则选择产生( n 2 m ) 个个体形成中间种 群。 s t e p5 ：排序。按适应度由高到低进行排序。 s t e p6 ：以当前最优解一为初始点进行牛顿法迭代： 给定：，日。 两北大学侦l 学位论文 ( j 叠 + l 一工 y 置g 女+ l g 啦+ 岳一而h y y t h d yy 爿y x t 一x k o k hk g k 如果，( + 1 ) f ( x k ) ，则x k + 1 = x k ，否则，一x k + 1 。 s t e p7 ：产生新一代种群。中间种群前j i f 个个体以概率1 复制到下一代中，形成新 一代种群。并且g e n + + 。转s t e p 3 。 2 2 3 基于信赖域法( t r u s tr e g i o nm e t h o d ) 的h g a 首先给出了一个信赖域方法( t r u s t r e g i o n m e t h o d ) 不能收敛到全局最优点的例子， 说明信赖域方法对多峰值优化问题的求解有一定的困难，将随机优化遗传算法( g e n e t i c a l g o r i t h m ) 与其结合给出了两种算法。 对于无约束优化问题： r a i n ，( 善) ( 2 231 ) j h 其二次模型为：靠p ) = ，( ) + 仃+ 三盯7 g 。仃 ( 2 2 3 2 ) 其中巩= v f ( x 。) ，g 。= v 2 f ( x 。) 。- 8 1 f 。i i 取为”i i ：。 信赖域法的基本思想是基于目标函数f ( x 。) 的二次模型( 2 2 3 2 ) ，当o r 充分小时， q 。( 仃) 能较好的逼近，( 屯) ，那么对口的大小加以限制，在此限制下求玑( 仃) 的极小点， 即求 m i n q p ) s t ( 2 2 3 3 ) 忙i i 。s k 的极小点吼，其中为一正数，然后令工“= + 吼作为( 2 2 3 1 ) 的极小点的新的 逼近，如果k 选得“合理”，z “将比如更接近最优解，用 。象来反映吼( 驴) 的逼 近程度， 一1 ，则逼近越好，用此来调照丸。其中4 = f ( x ) 一f ( x 。+ o r 。) ，却。= f ( x ) 一日i ( 口i ) 。 下面是信赖域方法的一般算法： 张晓伟，混合遗传算法的研究 算法2 2 3 1 s t e p l ：给定工i ，h 1 ，f ，并令k = 1 。 s t e p 2 ：计算占。，g 。，若j k 。8 f ，停 s t e p3 ：计算问题( 2 2 3 _ 3 ) 的极小值点吼。 s t e p 4 ：计算f i x t + 吼) 和咯。 s t e p 5 ：若 0 7 5 且枷。l ：= k ，令以。= 2 以：否则， 令h + 1 = h t 。 s t e p 6 ：若s0 ，令 + 1 = h ，否则令屯+ l = 吒+ 吼。 s t e p 7 ：k + + ，转s t e p 2 。 信赖域法的优点在于可以简单的用它来代替线性搜索，而且能够解决f 1 题( 2 2 3 1 ) 的h e s s e 阵不正定和为b 鞍点等困难，但是，这种二次模型有时并不充分近似于原来的 目标函数，因而在搜索方向上，常无法找到一个有满意下降值的迭代点或收敛到局部最 优解。 为了说明信赖域这个缺点，我们给出一个例子。 例2 2 3 1 m i n ，o ) = 一j 3 1 2 x2 3 9 x 一3 9 3 x2 + 9 x + 5 , i f 3 3 x 2 j - 2 2 工s - 1 1 x 0 0 s 上 答易牧让，这是一个次迁j 霎口j 徽幽效( 图2 2 3 1 ) ，碉两个极小值点- 5 7 3 2 1 ，和 一3 2 、一个极大值点- 2 2 6 7 9 、一个鞍点0 ，最优解为5 7 3 2 1 ，m a i n ，o ) = - - 2 1 3 9 2 3 。见 图2 2 3 1 ，圈2 2 3 2 。 我们令x l = - - i , 。= 1 ，e 2 l o 。；g 。2 6 j + 9 = 3 ，g 。= 6 ；求鼋1 ( 盯) = 3 p + 三) 2 一三， s t 。s1 ，得玛= 一丢；f ( x 1 + o 1 ) = 一三，l = 1 ； ：= l ，善：= o ：i 1 9 2 1 1 = 0 ，) ，则 h + 1 暑算t ，否贝4 ，k i z i “。 s t e p7 ：产生新一代种群。中间种群前j i f 个个体以概率1 复制到下一代中，形成新 一代种群。并且g e n + + 。转s t e p 3 。 2 3h g a 在约束优化中的应用 用g a 不能直接去求解约束优化问题，需要做一些处理，一般是将约束条件进行处 理：约束优化转化成无约束优化问题或设计出有效的繁殖算予，从而设计出h g a 。 fg j ( 工) s 0 ，j - 1 2 ，口 t t x ) 一o ，七一口+ 1 ，m ( 2 3 1 ) l 口f5 j s b i ，i 一1 , 2 ，n 其中，x 一 工，z ：，工。彤，( 2 3 1 ) 中不等式分别称为：不等式约束：等式 约束；域约束。对于域约束4 ，s 工，s b i ，我们将其考虑成无约束优化问题( 见2 2 ) 。 髅0k 2 q 翟：m 眩s z ， l 以( x ) t ， - + 1 ， 。 2 3 1 约束条件的处理 1 5 西北大学坝i 学位论文 ( 1 ) 抛弃不可行解方法： 方法是将所产生的不可行解抛弃掉，重复产生后代直到可行个体的出现。当然约束 条件多，可行域小时浚方法效率低下。 ( 2 ) 基于智能编码的方法： 是通过特殊的编码方式是只有可行解才能表现出来。这种方法需要利用有关问题域 约束条件的结构知识，通常在组合优化中使用，在约束连续优化中一般很难无法得到可 行域的准确信息，所以这种方法受到了很大限制。 ( 3 ) 修补方法： 该方法是通过设计与所求解的问题的相关的修补算予，将不可行解修补为可行解。 对约束优化问题，典型的修补策略是：对不可行解，在它与某个可行解的连线上随机抽 样产生可行解作为其“修补”。同样有类似于( 2 ) 中出现的问题。 ( 4 ) 罚函数思想： 一般地，经惩罚后新的目标函数如下形式： 眦，k + 。x ，溪； 其中，s 一 x i g ( x ) 5 0 , i l ，q ；h t ( x ) - o , k t q + l ，m a 在大多数罚函数类方法中，罚函数p e n a l t y f ( x ) 都是在衡量每个约束条件违反程度的一 组度量 ，( x ) 。 俨，1 o ；野h ：q 苗兰m 常用的有以下几种： 静态罚函数法： p e n 4 l t y f ( x ) = m f ( x ) 对笫，个约束条件建立f 个不同的约束违反水平，然后针对不同的水平确定罚因子 m f ，违反水平越高，罚因子m f 取值越大。这些因子在整个进化过程中是保持不变的。 该方法的缺点是：罚因子太多；罚因子确定困难；罚因子的静态性。 动态罚函数法： p e n a l t y f ( x ) = ( c f ) 。( x ) 1 6 张晓伟混台遗传算法的研究 随着进化代数的增加，该方法使得罚因子对不可行个体的惩罚力度增大。其中，t 为 进化代数，一般c = 0 5 ，a = j b = 2 。优点是：参数少且与约束无关，方法便于实施： 缺点：罚因子设置困难。 退火罚函数法： 彤朋i i y f ( x ) 2 高荟( x ) 该方法是基于模拟退火算法的思想，其中t 为进化代数，f ( f ) 是模拟退火温度， ( f ) 一0 ，从而一十* o 一+ * ) ，其增大速率取决于冷却降温模式的选择，该方法 i t l 需要选择初始温度( 0 ) ，终结温度g ，以及冷却降温模式，标准设置为：s ( 0 ) = l ，= 1 0 ，s ( f + 1 ) = o 1 e ( f ) 。缺点：方法对初始温度( 0 ) 以及冷却降温模式比较敏感且两 个参数不容易确定。 分化罚函数法： p e n a l l y f ( x ) = m 乃( x ) + 掷，x ) 该方法的基本思想是：在保证任何可行个体优于不可行个体的前提下进行优化工 作，将可能获得好的结果。其中，m 是常数，t 为进化代数，z ( t ，x ) 是一个适应性调整 项，以保证当前群体x ( f ) 任何可行个体优于不可行个体，一般定义为： 讹耻b o ；剿删一，募：州跏m 荛删，篇 l葺gnx0)x x “) 憎，矗 一 其中，s - x i g f ( x ) s 0 , 1 1 ，- 一q ；h i ( x ) 一0 , k q + 1 ，册) 缺点：膨的选择。 ( 5 ) d c p m ”方法： 该方法称之为直接比较一比例方法( d i r e c tc o m p a r i s o n p r o p o r t i o n a lm e t h o d ) ，好处 在予避免了罚因子的选择；考虑了不可行的个体。方法的基本思想如下： g a 的一个最大的优点是对目标函数的形态要求不高，目标函数仅仅是用来对种群 中的个体进行某种原则的变换。所以罚函数可以是不可微的形式或者不必要显式的写 出。因此，经惩罚修改后的f ( x ) 只要求有一种修改原则就行了。 在约束优化中还有一种现象，如图2 3 1 ，我们假设问题的全局最优解在x ，处达到， 在当前代中，有可行解x ，和不可行解x ，两个个体，如果用以前的罚函数方法，x ，进 西北大学硕 j