（计算数学专业论文）基于最优保存和自适应性的混合遗传算法.pdf

摘要 本文共分三章。第一章阐述了遗传算法的基本构成，特别说明 了三个基本的遗传算子和算法控制参数的选取。第二章描述了简单 遗传算法的过程，最优保存遗传算法和自适应性遗传算法及它们各 自的模式定理。第三章提出了基于最侥保存和自适应性的混合遗传 算法，对它进行了详细的描述，同时对算法的有效性和稳定性及 的选取作了阐述，另外还给出了混合算法的模式定理和此算法的一 奉露程序，最后通过数值例子对上述三类遗传算法和此混合遗传算 法的性能作了比较说明。 a b s t r a c t t h ear t ic 1 ec o n s is tso ft h r e e c h a p t e rs c h a p t e ro n e e x p o u n d st h eb as ic c o m p o s i t i o n0 f g e n e t i c a l 9 0 r i t h m e s p e c i a l1 y f o rt h r e ef u n d a m e n t a l g e n e t i co p e r a t o r sa n d t h e s e i e c t i o f to fa i g o r i t h mc o a tr o lp a r a m e t e r c h a p t e rt w on a t r a t e s t h ep r o c e s8o fs i m p l eg e n e t i c a i g o r i t h m ，o p t i m u mm a i n t a i n i n g s i m p l eg e n e t i c a 1 g o r i t h m a n d a d a p t i r e o e n e t i c a 1 9 0 r i t h m i n c l u d i n g t h e irs c h e m a t h e o r e m c h a p t e rt h r e ep r o p o s e st h e h y b r i dg e n e t i ca 1 9 0 r i t h m w h i c hisb a s e do no p t i m u m m a i n t a i n i n g a n d a d a p t i v e ，a n dg i r ei t ad e t a i l e d d e s c r i p t i o n ；m e a n w h i l e t h is c h a p t e ra l s o e x p l a i n st h ee f f e c t i v e n e s sa n ds t a b i l i t y o ft h e a l g o r t i t h ma n dt h es e l e c t i o no f 入t t h is c h a p t e ra 1s o s e tsf o r t ht h e s c h e m at h e o r e mo ft h e h y b r i da l g o r i t h ma n da c e r t a i n p a r t o ft h e p r o g r a m m i n g t h ea r t i c l ee n d sw i t ht h e c o m p a r a t i v ei 1 1 u s t r a t i o ho ft h ea b o v e - m e a t i o n e dt h r e eo c h e r i c a l g o r i t h ma n dh y b r i dg e n e t i ca l g o r i t h m t h r o u g ht h en u m e r i c a l v a 】l i e 致谢 本文是在导师孙方裕副教授的悉心指导下完成的，在此谨致以 衷心的感谢! 在三年多的学习过程中，也得到了王兴华教授、郑士 明教授、江金生教授、韩丹夫教授和程晓良副教授的关心和指导 在此向各位老师致以诚挚的谢意! 同时也深深地感谢我的同学和朋 友们，在学习过程中，他们给予了许多关心、支持和帮助。最后还 要衷心地感谢东方通信的庄凌博士，对我本文的完成提出了许多宝 贵的意见和建议。 基于最优保存和自适应性的混合遗传算法 前言 遗传算法( 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 等创立的，来源于进化论和群体遗传学，原先用于模拟自然系统的 自适应现象，后来被引向了广泛的工程问题。遗传算法发展成一种 自适应启发式概率性迭代式全局搜索算法，利用简单的编码技术和 繁殖机制来表现繁杂的现象，从而解决非常困难的问题，特别是由 于它不受搜索空间的限制性假设的约束，不必要求诸如连续性、导 数存在和单峰等假设，以及其固有的可并行性和高效率，正引起越 来越多的研究及应用热潮。八十年代以来，随着计算机的迅猛发展， 遗传算法在许多方面得到了广泛的应用，如自动控割n ，引、计算机 科学、机器人学1 、模式识别6 1 、工程设计和神经网络i s , 9 t 1 叫 等领域。 遗传算法中需要选择的参数主要有串长l ，群体规模大小n ， 复制概率p r 、交换概率p c 以及变异概率p m 等，这些参数对遗传 算法的性能影响很大，根据p r 、p c 、p m 的可变性，常用的遗传算 法一般有以下三种：简单遗传算法( s i m p l eg e n e t i ca l g o r i t h m ， s g a ) 或称标准遗传算法( c a n o n i e a ig e n e t i ca l g o r i t h m ，c g a ) 、 最优保存简单遗传算法( o p t i m u mm a i n t a i n i n gs i m p l eo c n e t i c a l g o r i t h m ，o m s g a ) 和自适应遗传算法( a d a p t i r e g e n e t i c a 1 9 0 r it h m ，a 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 ) ， 基于最优保存和自适应性的混合遗传算法 对它进行了简单的分析，给出了它的模式定理。该混合算法中，由 于入t 的可变性及入t 的选取总是偏向于o m s g a 和a g a 中好的一面， 克服了最优保存遗传算法和自适应遗传算法性能的缺陷性一面，而 使本混合算法的性能更稳定，搜索效能也更佳。最后通过例子比较， 也说明了此混合算法的有效性和稳健性。 基于最优保存和自适应性的混合遣传算法 第一章综 述 1 1 介绍 本世纪五十年代中期创立了仿生学，许多科学家从生物中寻求 新的用于人造系统的灵感。一些科学家分别独立地从生物进化的机 理中发展出适合于现实世界复杂问题优化的模拟进化算法 ( s i m u l a t e de v o l u t i o n a r yo p t i m i z a t i o n ) ，主要有h o lr a n d 【t 1 2 1 ， b r e m e r m a n n ”1 等创立的遗传算法，r e c h e n b e r g l l 4 1 和s c h w e f e l m 等 创立的进化策略以及f o g e l n 引，o w e n s ，w a ls h 【1 7 1 等创立的进化规划， 同时代还有一些生物学家f r a s e r n 引，b a r i c e l l i 19 1 等做了生物系统 进化的计算机仿真，很遗憾他们没有引入到人工系统。遗传算法、 进化策略及进化规划均来源于达尔文的进化论，但三者侧重的进化 层次不同，其中遗传算法的研究最为深入、持久、应用面也最广。 h o l l a n d 的功绩在于开发一种既可描述交换也可描述突变的编 码技术一二进制编码技术，这是最早的遗传算法，文献中现在把它 称为简单遗传算法( s i m p l eg e n e t i c m g o r it h r a ，s g a ) 或称标准遗 传算法( c a n o n i c a lg e n e t i ca l g o r i t h m ，c g a ) 。 1 2 遗传算法的构成 遗传算法一般由四个部分组成：编码机制、适应值函数、遗传 算子、控制参数。 1 2 1 编码机制这是的基础。g a 不是对研究对象直接进 行讨论，而是通过某种编码机制把对象统一赋予由特定符号( 字母) 按一定顺序排成的串。正如研究生物遗传，是从染色体着手，染色 基于最优保存和自适应性的混合遗传算法 体则是由基因排成的串。对一般问题的解决，s g a 通常呆用二迸制 编码，字符集由0 与1 组成，码为二元串。对较繁杂的问题，g a 自然可不受此限制，如对旅行商问题或其他复杂问题心0 | ，就可采 用实数编码。目前，使用实数编码、浮点数编码的研究也不少。由 于浮点数编码有精度高、便于大空间搜索等优点，正越来越受到重 视2 1 2 引，m i c h a l e w l c a 【2 3 ，2 4 1 比较了这两种编码的优缺点。最近q i 和 p a l m i e r i n 钉对浮点编码的遗传算法进行了严密的数学分析，用 m a r k o v 链建模，进行了全局收敛性分析。另外，k o z a 吨62 7 1 还发展 了用计算机来编码，从而开创了新的应用领域。 串的集合构成总体规模，个体就是串。对g a 的码可以有十分 广泛的理解。在优化问题中，一个串对应于一个可能解；在分类问 题中，串可解释为一个规则，即串的前半部为输入或前件，后半部 为输出或后件、结论，等等。 1 2 2 适应值函数也称适合度函数优胜劣败是自然进化的原 则。优、劣要有标准。在g a 中，用适应值函数来描述每一个个体 的适宜( 优劣) 程度。对优化问题，适应值函数一般就是目标函数。 引进适应值函数的目的在于可根据其适应值对个体进行性能评估、 比较，定出优劣程度。 1 2 3 遗传算子最基本的遗传算子有三种：选择、交换、突 变。 ( 1 ) 选择算子也称复制算子。它的作用在于根据个体的优劣 程度决定它在下一代是被淘汰还是被复制。一般地说，通过选择， 基于最优保存和自适应性的混合通传算法 将使适应值大即优良的个体有较大的生存机会，而适应值小即低劣 的个体继续生存的机会也较小。有很多方式可以实现有效的选择， s g a 采用按比例选择的模式，即适应值为f i 的个体以f i f k 的概 率继续生存，其中分母为父代中所有个体适应值之和。复制的主要 思想是串的复制概率正比于其适应值。 发展各种复制操作的目的是为了避免基因缺失，提高全局收敛 性和效率。目前为止发展的主要复制操作类型见表1 。复制操作策 略与编码方式无关。 表1复制操作 序号名称特点 研究者 1回敖武随机采样选择误差较大d e j 。n g 【2 引，b r i n d l c 圳 ( 轻盘赌选择) 2无回放武随机采样 降低选择误差，复制数 f ( f + 1 )d e j o n g 【2 盯，b r i n d l e 【2 9 1 操作不方便 3确定式采样选择误差更小，操作简易 b r i n d l e f 2 田 4 柔性分段式复睾j有效防止基因缺失但需要选择有关参数y u a f 3 0 】 5自适应柔性分段武群体自适应变化，提高搜索效翠 y u n 【3 0 ) 动态群体采样 6无回放式余数随机误差较小b r i n d l e 【2 判b o o k e r f 3 1 】 采样 7 均匀排列与适合度的大小差异程度正负无关b a c k 【3 2 l 8 穗态复制保留父代中的一些高适合度串s y s w c f d a l 3 ” 基于最优保存和自适应性的混台遗传算法 如果只有选择算子，g a 不会有什么新意。因为后代的群体不 会超出初始群体即第一代的范围。因此还需要一些更合理的其它算 子，常用的有交换算子和突变算子。 ( 2 ) 交换算子( 又称杂交算子) 有多种形式，最简单的是单点 交换，这也是s g a 通常使用的一种，肆从群体中随机取出两个字符 串，设串长为l ，随机确定交叉点，它在1 至l - 1 间的正整数取值。 于是，将两个串的右半段互换再重新连接得到两个新串。其它的还 有z - 点交换、多点交换，等等。 交换操作的作用是组合出新的个体，在串空间进行有效搜索， 同时必须降低对有效模式的破坏概率。交换操作是g a 区别于其它 进化算法的重要特征。目前发展的主要交换策略见表2 。 基于最优保存和自适应性的混合遣传算法 表2选择操作 q i 和p a l m i e r i 1 研究了采用实数编码的标准g a 中均匀交换的 行为，证明交换操作能把群体保持在合适区域内的同时能搜索新的 解空间。 ( 3 ) 变异算子或称突变算子当交换操作产生的后代，其适合 度不再比它们的前辈好又未到金局最优解时，就会发生早熟收敛， 早熟收敛的根源是发生了有效基因缺失h ，这时，为克服这种情 况，还必须依赖于突变。突变算子是改变字符串的某个位置上的字 符。在s g a 二进制编码中，即为0 与l 互换：0 突变为1 ，1 突变 为0 。一般认为，突变算子重要性次于交换算子，它在g a 中的作 基于最优保存和自适应性的混合遗传算法 用是第二位的，但其作用也不能忽视。例如，若在其个位置上，初 始群体所有串都为0 ，但最侥怒在这个位置上却取1 ，于是仅通过 交换达不到的，而突变则可做到。目前发展的主要突变操作见表3 。 表3突变操作 另外，许多高级基因操作得到了研究，如显性操作 3 4 1 、倒位 操作b 4 ”1 、分离和易位操作m 1 、增加和缺失操作n 2 一蚓以及迁移操 作n 2 1 。这些基因操作大都来源于群体遗传学，目前应用尚少，其 机理及作用有待进一步深入研究，借鉴群体遗传学中有关高级基因 操作的最新成果有益于该项研究。 1 2 4 控制参数在g a 的实际操作中时，需适当确定某些参数 基于最优保存和自适应性的混台遗传算法 的值以提高选优的效果，这些参数主要有： ( 1 ) 串长：字符串所含字符的个数。在一般的g a 中，这一长度 为常数，记为l ； ( 2 ) 群体规模：每一代群体的大小，即所包含字符串的个数， 记为n 。群体规模影响到遗传算法的最终性能和效率。当规模太小 时，由于群体对大部分超平面只给出了不充分的样本量，所以得到 的结果一般不佳。大的群体更有希望包含出自大量超平面的代表， 从而可以阻止过早收敛到局部最优解；然而群体越大，每一代需要 的计算量也就越多，这有可能导致一个无法接受的慢收敛率。一般 群体规模的变化范围是从10 到1 6 0 ，增量为t 0 。 ( 3 ) 遗传算法执行的最大代数目，记为m ，即最多执行到m 代， 遗传算法即停止。 ( 4 ) 复制率也称选择率，即施行复制算子的概率，记为p r ；复 制就是根据适应值从群体中选择串进行拷贝的过程。一旦一个串被 选择，则将这个串的拷贝放入在一个新的暂时群体，以便进行交换 和突变。当完成了n 次复制后，整个暂时群体就被填满了。 ( 5 ) 交换率也称杂交率，即施行交换算子的概率，记为p c ；交 换率控制交换算子应用的频率，在每代新的群体中，有p c * n 个串 ( 取偶数个整串) 实行交换。交换率越高，群体中串的更新越快。 如果交换率过高，相对选择能够产生的改进而言，商性能的串被破 坏得要更快。如果交换率过低，搜索会由于太小的探查率而可能停 滞不前。一般地，交换算子的概率从0 2 5 变化到1 0 0 ，增量为0 0 5 。 基于最优保存和自适应性的混合遗传算法 ( 6 ) 突变率也称变异搴，印施行突变算子的概率，记为p r o ；突 变是增加群体多榉性的搜索箨子，每次选择之后，群体中每个串的 每一位以概率等于突变率糯进行随祝改变，跌雨每代大约发生 p m * n * l 次突变。一个低水平的突变率足以防止整个群体中任一给 定位保持永远收敛到单一憋值。商水平的突变率产生的实质是随机 搜索。突变率一般的取信是从0 0 窝1 o 。 基于最优保存和自适应性的混台遗传算法 第二章简单遗传算法、最优保存遗传算法和自适应遗传算法 2 i 简单遗传算法 考虑一函数优化问题：f f i a x f ( x ) ；x q cr “) ，其中f ：q c r “ 一r 1 ，输入一自变量，便知道相应的函数值。这是一个黑箱问题， 没有函数在连续性等方面的任何信息。 遗传算法把该问题中的自变量当作生物体，将其转化为由基因 构成的染色体，亦即串，相应的函数值定义为适合度，未知函数为 环境，生物体的目标是进化成具有最佳适合度的基因型。用简单遗 传算法求解上述函数优化问题的步骤可描述如下： s t e pl 选择编码策略。在s g a 中一般采用二迸制编码表达实数， 每个二进制位即为一基因，若一维参数x a ，b 】，则 x a + 娶( b _ a ) 其忆为第i 个基目o s t e p2 定义串的适合度函数j = f ( x ) ： s t e p3 选择群体规模n 等遗传参数及终止准则； s t e p4 随机产生n 个串构成初始群体； s t e p5 计算群体中每一个体的适合度，由串解码所得的解越好， 则适合度越高； s t e p6 对每一个体，依据其适应值赋一复制概率p r ，第i 个个体 被复制的概率为p r ；= 掣； ( x ) 基于最优保存和自适应性的混合遗传算法 s t e p7 根据p r i 复制个体； s t e p8 以交换概率p c 对个体进行杂交； s t e p9 以突变概率p m 对个体进行变异； s t e p 10 跳至s t e p7 ，直至产生n 个新个体，转至下一代； s t e p1 1 从s t e p5 开始重复进行，直到满足某一性能指标或规定的 遗传代数。 上述遗传过程描述了最简单的进化模型，s t e p7 至s t e p9 进 行了三种最基本的基因操作，复制实施了适者生存的原则；交换的 作用是组合父代中有价值的信息，产生新的后代，以实现高效搜索； 突变的作用是保持群体中基因的多样性。 图l 描述了上一操作过程的流程。图中g e n 代表遗传( 迭代) 的代次，亦即标明已产生群体的代次数目，n 表示群体拥有的个体 数目，i 表示已处理个体的累计数，当累计数i 等于群体个数n ， 说明这一代的个体已全部处理完毕，需要转入下一代群体。 基于最优保存和臼适应性的混合遗传算法 图1 基本遗传算法流程图 基于最优保存和自适应性的混合遗传算法 2 2 最优保存简单遗传算法和自适应遗传算法 传统的基于模式定理的对全局收敛性的定性分析认为简单遗传 算法是全局收敛的。这一结论主要是根据h o il a n d 的模式定理的定 性分析”，事实上，这一结论普遍受到怀疑和争论。近几年，在遗 传算法全局收敛性的分析方面取得了突破，运用的数学工具是齐次 有限马尔科夫链，g o l d b e r g 和s e g r e s t 4 1 首先使用马尔科夫链分 析了遗传算法，e i b e n 5 1 等用马尔科夫链证明了保留最优个体 ( e l i t i s t ) 的g a 的概率性全局收敛，r u d o l p h 4 6 1 用齐次有限马尔 科夫链证明了带有复制、交换、突变操作的标准遗传算法收敛不到 全局最优解，建议改变复制策略以达到全局收敛。s r i n i v a s “7 1 等 提出具有比例复制和自适应交换及突变操作的遗传算法即自适应遗 传算法( a d a p t i v eg e n e t i ch l g o r i t h m ，h g h ) ，运用模式定理说明 了其搜索的有效性和高效性。恽为民等8 1 应用有限马尔科夫链分 析了最优保存遗传算法的全局收敛性，引用它证明了自适应遗传算 法的全局收敛性。 s g a 能发现全局最优解，但不能保证每次都收敛于全局最优解。 s g a 有全空间搜索的能力，不能实现全局收敛的原因是s g a 发现的 最优解不能保持。要实现遗传算法全局收敛的基本思想是把发现的 最优解保存下来。 最优保存遗传算法( o p t i m u mm a i n t a i n i n gs i m p t e6 e a e i c a i g o r i t h m ，o m s g a ) 是一种常用的实现全局收敛的策略，其操作主 要是在s g a 的基础上进行最优保存( e 1 i t is t 选择) ，即以概率l 基于最优保存和自适应性的混台遗传算法 保留父代中最佳个体到子代。其余的操作过程和策略与s g a 基本一 样。h o l1 a n d 提出的模式定理，同样适合于o m s g a 。 定理1 1 2 t4 6 n h ( t + 1 ) m ( ，) 等( t 一等肛 ( 一胁p 式中各符号的描述见式。 自适应遗传算法( a g a ) 也是实现全局收敛的好方法，其操作策 略与简单遗传算法的不同之处是：自适应操作的交换概率p c 和突 变概率p m 不象s g a 一样，在初始时一确定而后就永远不变。它们 随个体的适合度自适应地变化，即p c 和p m 会随着代的延续而相应 地改变，并且是由个体的适应值来确定。p c 和p m 自适应变化如下： p c ：l k t ( 。一f 1 ) “，一厂) ，摩厂 【k ，f ， p m = j z ( 一) ( ，一一，) ，f f 【七4，厂 厂 o k 】，k 2 ，k 3 ，k 4 1 0 其中 。，是s - 前代中的最大适合度，是当前代中的平均适合度， 厂是用于交换的二个串中较大的适合度，是突变串的适合度。 当，= 厂。时，p c - o ；当f = f 。时，p m = o ，因此，任意代中的 最优串都能保存。 s r i n v a s 还得到了在平均适应值之上，具有某一模式h 的a g a 模式定理。 基于最优保存和自适应性的混合遗传算法 定删4 7 m 升静筹) 卜篙厂 上式中各符号描述如下： h ：某一模式 夕：当前代群体的平均适应值 五：当前代具有模式h 的个体的平均适应值 f ：当前代中的最大适应值 m ( ，) ：当前代为t ，具有模式h 的个体的期望数 ，( ) ：模式h 的长度 o ( ) ：模式h 的阶 l ：二进制的长度 基于最优保存和自适应性的混台遗传算法 第三章混合遗传算法 3 1 混合遗传算法的描述 3 1 1 最优保存遗传算法和自适应遗传算法的比较 最优保存简单遗传算法和自适应遗传算法都能保证算法的全局 收敛性，比较二者，它们均有自己的侧重点：( i ) o m s g a 比a g a 在群 体平均性能的提高上来得好，但较a g a 容易陷入局部最优解；( 2 ) a g a 不易陷入局部最优解，但为计算p c 、p m 的值，增加了相应的计算 量。具体地讲： ( 1 ) 最优保存简单遗传算法中的参数p c 、p m 在搜索一开始时就 已选定，而后不随代的延续而交化。在算法的开始阶段，群体规模 的平均性能一般都不高，这就需要有恰当的p c 和p m ，使得整个群 体的性能有普遍的提高。但随着代的延续，群体规模的平均性能的 提高，如果再是同样值的p c 和p r a ( 不论是较高还是较低的p c 、p m 值) ，其搜索效能就会有一定的影响。这样，算法的开始阶段和最 后的阶段、较高的p c 、p m 值和较低的p c 、就构成了一对矛盾。 所以为缓解这对矛盾，我们总是采用适中的p c 和p m 值，来达到二 者的平衡，但这样做总是以延长算法的代次为代价的。o m s g a 的特 点之一是：在算法的开始阶段，群体平均性能的提高总是比较快。 ( 2 ) 自适应遗传算法中的参数p c 、p m 是随个体适应性的变化而 改变，p c 和p m 自适应变化见( ) 式。从式孛可看出，一旦k ；，k 。，k ，k 。 确定后，在平均适应值附近的个体，其杂交和突变的概率几乎等于 k 。，k ，和k ：，k 。，也就是说，随着代的廷续，在平均适应值附近的个 基于最优保存和自适应性的混合遗传算法 体，实行杂交和突变操作的概率几乎是不变的，虽然它们的适应值 在提高。另外，高适应值的个体相对于平均适应值附近的个体，其 p c 和p m 值总是较小的，而小于平均适应值的个体总是以固定的p c 和p m 进行杂交和突变，这一方面是为保证群体中好的个体，不中 断地传到下一代，另一方面使用小于平均适应值的个体来搜索包含 全局最优解区域的空间，以防止g a 停留在一个局部最优解，这就 保证a g a 不易陷入局部最优解。 此外，在g a 搜索过程的初始阶段，群体中常常有极少的个体 相对于大多数个体而言适应性非常好，如果这时按通常的选择规则 ( p i = f i z f j ) ，这几个非常好的个体就会控制选择过程，这种情 厂 况就会导致过早地收敛；在搜索过程的后期，群体中可能还存在足 够多的多样性，然而群体的平均适应值可能会接近群体中的最优适 应值，如果不改变这种情况，在后继代中具有平均适应值的个体和 最好的个体就几乎得到相同的复制数目，故群体这时实际上不存在 竞争，这将会减慢算法的收敛速度。为解决上述二个问题，我们在 算法的开始和后期阶段，可以采取线性比例、幂比例或指数比例的 方法来减小和扩大个体间适应值的差距，这样处理的好处是，一方 面，在算法开始阶段，保证限制非常好的个体的复制数目，以免其 很快控制整个群体；另一方面，在算法后期阶段，可以保证让非常 好的个体保持多的复制机会，增加算法效能。 3 1 2 混合遗传算法的提出 基予最侥曝毒和蠹适成性蟾德各遗传算法 我们提出的基于最优保存和蠹适应浚的混合遗传算法( h y b r i d g e n e t ica i g o r i t h m ，i i g a ) ，采取的方法是把这两种遗法进行混合， 敢各自的长处，鄹的是尽可能用较少的搜索代数找到问题的最挠 解，醒时既要防止算法罄入慧部最优，又要保 歪算法有较好鹩平均 遥应值和最佳适应值个体。熊体的操作是，在执行遗传算法的时候， 把当前代( 设拦前代为第t 代) 的n 个个体随机分成两个相对独立 媳子群体：一个子群体含毒fx ：t 辩3 个个体( f 天。t 列表示取天。+ 辩 的整数，下简) ，另一个予群体含有( n - f 天，+ n 】) 个个体。为以后 叙述方便，简称入，为第t 代的划分系数，入：必须满足： 0 丸。1；o ，1 ，挞 我们把其中曲n i - - f 入。t 鞭】个个体施行最优保存遗传算法，其余 的l q 2 = ( 1 一【入，* l q 】) 个个体施行自适应遗传算法。这二种算法各自 经过复铋、杂交和突变后，独立产生n 1 个个体彝h 2 个个体。霭后， 蒜把这n i + n 2 = n 个个体滠台作为群体敲下一代，并确定新的划分系 数入，根据入。把这新的n 个个体分成二个子群体，如此循环反 复，直至满足算法终止条件。 3 。1 。3 混舍遗传算法戢过程措邃 上述混合遗传算潦的操作过程可描述如下： 1 、 选择编码策略。编码策略可以有二进制编码和实数编码等。 2 、定义串的适合度遵数f x ) * j f f f x ) ) 。 适合魔函数是舀标萄数的映射，它筏含了对求解问题的所有 信息。 基于最伉保存和自适应性的混合遗传算法 3 、选取群体的规模n 、最优保存算法的杂交概率p c 和突变概率 p m ；自适应算法中的量。，k 。，k j 和k ；的值，终止条件，遗传代 次等。 4 、随机产生n 个个体，构成初始群体。 5 、根据划分系数入。的值，随机把群体n 划分成两个子群体：n 1 = 【入+ n 和_ n 2 = ( n 一【九，+ n 】) 6 、对这两个子群体分别实行最优保存算法和自适应算法， 6 1 对n 1 个个体实行最优保存遗传算法产生下一代子群体。 其中的杂交概率和突变概率分别为p c 和p m ，并且以概率l 保留 当前代中最佳个体至下一代。 6 2 对n 2 个个体实行自适应遗传算法产生下一代子群体。其 中的杂交概率和突变概率由以下公式给出： p ，c ：肌厂m 一，) “，一一夕) 七3 p tf n = ：( ，一，) 7 ( ，m “一，) i 膏4 0 k l ，k 2 ，k 3 ，k 4 1 0 ，f 兰， 一 。 ? ，f f 一 ，f l 其中丘；是子群体n 2 当前代中的最大适合度，夕是子群体n 2 当前 代中的平均适合度，厂f 是用于交换的二个串中较大的适合度，是 基于最佳保存和自适应性的混合遗传算法 突变串的适合度。 7 、 由6 i 和6 2 产生的新子群体进行混合，构成新的群体n 作 为过程5 的下一代。 8 、确定入。+ ，的值，置入。= 入。小 9 、重复过程5 至过程8 ，直到满足某一性能指标或规定的遗传代 数。 用图2 可以描述上述过程的流程。 基于最优保存和自适应性的混合遗传算法 l 选择编码策略、 i 算法相关的参数 图2混合遗传算法流程图 一2 2 基于最优保存和自适应性的混合遗传算法 3 2 混合遗传算法的浅析 从上一节描述的混合算法中，我们可以看出，由过程5 到过 程8 ，我们采用的是g a 最基本的三个操作策略：复制、选择和突 变，并且由过程6 1 和6 2 中可得到：每一代的最优个体，在下 一代中都以概率l 得到了保存，引用文献e i b e n 4 5 1 和r u d 0 1 p h h 6 1 的结论，我们可知此算法是全局收敛的。事实上，当划分系数入 ；0 时，此混合算法即为自适应遗传算法； - 3 入。；l 时，此混合 算法即为最优保存遗传算法。我们可以把此混合算法看作是对 o m s g a 和a g a 的一种扩充。从上面的混合算法中，我们还可以看出， 虽然种群的群体规模n 在算法执行的过程中没有改变，但如果当 划分系数入，随算法的执行而改变时，相对独立的o m s g a 和a g a ， 他们的子群体规模 l 和n 2 是随入，的改变而变化的，所以此混合 算法隐含着：虽然种群的总规模没有改变，但实际参与算法的子 群规模随代的延续而在变化。 - 类似于第二章的模式定理，对本文的混合算法，参照图2 的 算法流程，我们可以对平均适应值之上，第t + l 代具有模式h 的 个体作如下估计。以下各式中用到的符号描述如下： h ：某一模式 ： l , - ：当前代群体n 的平均适应值 7 ，一：当前代群体n ，具有模式h 的个体的平均适应值 一：当前代群体n 中的最大适应值 基于最优保存和自适应性的混合遗传算法 “( ，) ：群体n ，在t 代具有模式h 的个体的期望数 m ) ：模式h 的长度 ( ) ( 厅) ：模式 的阶 l ：二进制串的长度 【l j 对子群体n 2 来说，由足理2 的式，前后连续二代有如 下估计成立： m 驰咖斟一等岛装等卅“篆等厂 ( 2 ) 对子群体n 1 来说，由定理l 的式，前后连续二代有如 下估计成立： n , h ( i 圳堋，等( 卜器改1 - 舻们 ( 3 ) 考察总群体n 和子群体n 2 ，由于按入t 的划分是随机的， 从概率的角度来讲，子群体n 2 中的五：、元 与总群体n 中的元、 五，一有：五：“五、五孙z 五而子群体n 2 中的厂：与总群体n 中的厶m 畎， 始终有- ，二v h 瓢厶一， 故豁渊 割汁瓮掣硎a ，又由于 ( j ：一一， ：) ( 厶一元) ”。“。 器觚： l 所以( 1 一器觚) ( 1 - k z a ) ( 1 一等b ) ( 1 一 女：b ) 。此外，子群体n 2 中的彤( ，) 与总群体n 中的n n f ，) 也，有彬r ，) ； 基予最绕保露孝自适成性妁混合遗传算法 ( 1 一 t ，n ”f ，) 。 周样地对予群体n 1 来说，有 ( ，) zx 。n “( ，) 、只。“元及氏，* k 。 综合以上( 1 ) ( 2 ) ( 3 ) ，对总群体n 的连续二代来说，有 娥川剐静+ 1 ) 删”驴等( t 一等玖t 哦) f ) l 扪+ 等等胁h ( 1 - k 2 a ) f ) f 们 训，等( 卜等p ) ”舻 ”桫等( t 一器硒) ( 1 确矿都 上武鼹跨筹代入，静可汉褥裂本混合箨法戆模式定理。 定理3 对平均适应值之上，具有模式h 的个体，前后二代的 数鬟有如下估计： m 驴n 等( t 磐熊) ( t 刊h ”引瑚，等( 卜咎甓豢m 后z 铙券厂； 由武可潋看出，警灭。= l 时，n i = n ，帮为h o l l a n d 挺密的模 式定理：当入。= 0 时，n 2 = n ，即为s r i n i v a s 提出的模式定理。 3 。3 入：的选取 3 3 1 蔑个定义 为叙述和例子说明的需要，我们引逊二个概念：离线性能和在 线慨能。规定在sl 的函数f 定义了一个响应面，饶化函数f 的对 基予最谯撂存和鑫适威娃妁混合遣传算法 程就是在这个响应面上利用菜种搜索策略以确定s 上其有高性能曲 点。当求函数f 的极小值( 极大值) 时，通常定义点x 的性能值t l ( x ) 为：u ( x ) = f ( x ) e 其中c 为输入参数。这个变换保证，不管f ( x ) 的特征如何， 性能t l ( x ) 盼值总是正的。 定义1 【4 叩在函数f 的响应面上，搜索算法“的在线性能 承，t ) 定义蔻 u f ( c c ，t ) = a v e 。( “f ( t ) ) ，t = 0 ，1 ，2 ，m 其中u ，( t ) 是在代次t 所得到的性能值。在线性能表示算法直 到当藏为止鳇代次内得到麴所有性能鳇平均德。 定义2 4 璐在函数f 的响应面上，搜索算法a 的离线性能 昕( a ，r ) 定义为 农寤，t ) = a v e b f t ) ) ，t = 0 ，1 ，2 ，挺 其中u 4 ，( t ) 是在代次【o ，t 】内最伉的性能值。离线性能表示算 法执行中得到的最佳性能值的平均值。 定义3 鼹n ( t ) 袭示第t 代适应镳在在线性能之下曲个体数； n ( t ) 表示第t 代适应值在里超尘王掣之上的个体数。 定义n i t ) 与群体规模n 的比值为p ( t ) ；n ( t ) 与群体规模n 的 比值为p ( t ) ，即p ( t ) = n ( t ) n ；( t ) = n ( t ) n 。 3 。3 ，2 入。懿选激 在本混合算法中，x 。的选取院较重要，一般地，x 。的取值 墓于最优保存和自适应性的混合遗传算法 可分二类：一类是入：一旦选定不会随算法的执行而改变。此类混 合算法处理问题比较单一，通常入。可取；、昙、；或其他值即可。 另一类是入。随算法的执行而改变，即入。动态地变动。入。可 按以下四种情况取值： ( 1 ) 当d ( t ) 0 ，6 时，入。按式石+ - = ；+ ；【，) 取值。t = 0 ，i ，2 ( 2 ) 当p + ( t ) 0 2 时， 。按式七+ 一三卢( ，) 取值。t = 0 ，l ，2 ( 3 ) 当条件( 1 ) ( 2 ) 都不满足时，入。按式 元+ t2 ；+ 云( 卢( ，) + p ( ，) ) 取值。t - - o ，1 ，2 ( 4 ) 当条件( 1 ) ( 2 ) 都满足时，在算法的开始阶段，入。的取值 以( 1 ) 为准；在算法的后期阶段，入。的取值以( 2 ) 为准；其他阶段 入。按武九+ - = 十；( 卢( ，) 一3 卢( ，) ) ( t = o ，l ，2 ) 取值。因为在算法开 始阶段，我们主要关心的是个体的在线性能，而在算法后期阶段， 我们关心约是个体的离线性能，而在算法的其他阶段，我们希望 二者兼顾。 3 4 混合算法与o m s g a 、a c , a 的性能说明 我们说，o m s g a 和a g a 都具有算法的全局收敛性，它们最终都 能解决某类问题。但是，由于问题的预先不可知性： ( 1 ) 对某些阅题的解决，用o m s & a 比周a g a 相对来得好些，雨 我们可能采用了a g a ；而对另一些问题，用a g a 比用o m s g a 可能来 基于最优保存和自适应性的混合遗传算法 得更好，丙我们采用了o m s g a 。 ( 2 ) 我们就算采用了较好的o m s g a 或a g a 来解决问题，但这种 较好的o m s g a 或a g a 也不是绝对不变的。换句话说，随着算法代次 的延续，算法o m s g a 和a g a 的好坏也是在相对改变的。 上述( 1 ) ( 2 ) 二点都显示了o m s g a 和a g a 性能的缺陷性一面。正 基于此，我们说，我们提出的本混合算法，由于九的可变性及入。 的选取总是偏向于o m s g a 和a g a 中好的一面，本混合算法的性能显 得更稳定，搜索效能也更佳。 3 5 数值例子 3 5 1 混奢算法与$ g k 、o l d s g t 的离线和在线性能比较 例子1 ：考虑测试函数f 1 的极小值 j f 1 ：，( j ) = 弓，一5 1 2 s x , 5 1 2 j = l 我们给出三种遗传算法的数值试验( s g a 、o m s g a 和本混合遗 传算法) ，从定量的角度比较这三种算法的在线和离线性能。为说 明问题的需要，我们给出的算法参数基本一样。由于所求函数为 极小值，故运用遗传算法可以：( 1 ) 在复制时，我们把复制概率反 比于其适应值、最优保存采取适应值最小的一个个体保存到下一 代。或者：( 2 ) 把f 1 函数通过简单转换，变成求极大值问题。这 二种方法是一致的。 算法r 1 ：简单遗传算法 由三个基本遗传算子组成： 基于最徒保存和自适应性的混合遗传算法 1 、赌盘选择； 2 、一点杂交算子； 3 、简单变异算子。 几个参数：n = 5 0 p c = 0 6p r o = 0 0 1 算法r 2 ：最优保存遗传算法 以概率1 保留当前代中最佳个体至下一代，其余参数同 算法r 1 。 算法r 3 ：本文的混合遗传算法 1 、o m s g a 的算子及参数与算法r 2 2 、a g a 中的k i = k 3 = 0 6 ，k 2 = o 0 1 ，k 4 = 0 0 2 3 、入。可变 以上三种算法最后的执行效果如图3 和图4 。 萋予最魏保存和鸯适霞佳薛遥台遗俦算法 e 。6 0 5 0 4 0 3 0 2 0 1 0 0 1 2 04 0 6 08 01 0 0 1 2 01 4 0 图3 算法r 1 、r 2 和r 3 的离线性能比较 0 2 0 4 06 0 8 0 1 0 0t 2 0 1 4 0 图4 算法r 1 、r 2 和r 3 的在线性能比较 一3 0 一 技 如 8 6 4 2 o t 基于最优保存和自适应性的混合遗传算法 从中可以看出，对于测试函数f 1 ，算法r 3 的在线和离线性 能都比算法r 2 、r l 有明显提高。 3 5 2 混合算法与a g 的最大适应值和平均适应值的比较 例子2 ：考虑以下二个同类函数的极大值，两函数的图形如图5 和 图6 。 f 2 ：厂：( z ) = j s i n ( 1 0 石j ) + 3 o其中1 0 x 2 o f 3 ：，( j t ，工：) = 工r s i n ( 4 7 r 工t ) + 了：s i n ( 2 0 x 工：) + 1 9 5 其中一3 0 x l 1 2 1 ，4 1 x 2 5 8 乓56 脏删 ， ， 1 5 i 一1- o 5 图5 函数f 2 的图形 一3 1 11 53 基 最觉保存和自适应性的混合遗传耸珐 图6 函数f 3 的图形 【1 ) 对于函数f 2 ，采用二进制编码，通过变换 r = 一lo + j 两3，把区间卜1 0 ，2 o 】映射至二进制串 ( 0 0 0 0 0 0 0 0 0 0 0 0 0 0 d o o o 0 0 0 0 ) ( 1 “1 1 1 1 1 1 1 i 1 1 1 l i u l l ) 如串x7 = ( 10 0 0 10 1 i 1 0 1 1o l0 1 0 0 0 1 1 1 ) 2 = 2 2 8 8 9 6 7 则表示的值为x 一1 - o + 2 2 8 8 9 6 7 百订可可 = o 6 3 7 1 9 7 图7 给出了o m s g a 和此混合算法的最佳适应值性能比较。其中 算法r 1 ：最优保存遗传算法 群体规模；= 6 0 ，杂交概率p c = o 4 ，变异概率p m = o 0 2 算法r 2 ：本文的混合遗传算法 l 、o m s g a 的参数同r l 基于最侥保存和自适应性的混台遗传算法 5 4 5 4 3 5 3 2 5 2 2 、a g a 中的k l = k 3 = o 4 ，k 2 = o 0 1 ，k 4 = o 0 2 5 3 、入t 可变 执行代次 02 04 06 0 l o o 1 4 0 1 8 0 圈7 算法l 【1 和r 2 的最大适应值比较 ( 2 ) 对函数f 3 ，我们采用的是二进制编码，取群体规模q = 8 0 。 算法r 1 自适应遗传算法 a g a 中的k l = o 5 ，k 3 一o 6 ，k 2 = 0 0 15 ，k 4 = o 0 2 算法r 2 此混合遗传算法 1 、o m s g a 中p c = o 5