（运筹学与控制论专业论文）进化算法及其在组合优化中的应用.pdf

摘要 进化算法在诸多领域内有着广泛的应用尤其在计算机科学中，一些难解的 优化问题，例如n p 一完全问题和多目标决策问题，采用传统优化方法往往不能有效 求解 首先，本文提出一种求解带度约束最小生成树问题的进化算法该问题是n p 一 完全问题，算法采用厅，0 r 编码表示问题的解，为了增强算法的搜索能力，特别设 计了两个新的遗传算子参与进化，算子避免了产生不可行解此外，设计了两个局 部搜索算子和算法相结合来进一步提高解的质量因此，算法表现出较强的搜索能 力数值实验表明算法适用于求解该问题，理论分析表明算法以概率1 收敛到全局 最优解；其次，研究了多目标决策的最小生成树问题算法仍然采用伢盯打编码 表示问题的解，设计了两个不必考虑度约束的遗传算子数值实验表明算法非常有 效，理论分析表明算法以概率1 收敛到全局最优解 关键词：进化算法最小生成树度约束多目标决策 a b s t r a c t e v o l u t i o n a r ya l g o r i t h m sh a v ew i d ea p p l i c a t i o n si nm a n yf i e l d s ，e s p e c i a l l yi nt h e c o m p u t e rs c i e n c e f o rs o m eh a r do p t i m i z a t i o np r o b l e m s ，s u c ha ss o m en p * c o m p l e t e p r o b l e m sa n dm u l t i - c r i t e r i ap r o b l e m sw h i c hc a nr i o tb es o l v e de f f i c i e n t l yb yc l a s s i c a l o p t i m i z a t i o na l g o r i t h m s f i r s t l y , an e we v o l u t i o n a r ya l g o r i t h mf o rd e g r e e c o n s t r a i n e dm i n i m u ms p a n n i n g t r e ep r o b l e m ，w h i c hi sa nn p c o m p l e t ep r o b l e m ，i sp r o p o s e d p r t l f e r e n c o d i n g m e t h o di s a d o p t e dt oe n c o d et h es o l u t i o n so ft h ep r o b l e m t oe n h a n c et h ea l g o r i t h m ，t w on e w g e n e t i co p e r a t o r s a r e s p e c i f i c a l l yd e s i g n e d ，w h i c h c a na v o i d p r o d u c i n g i n f e a s i b l e s o l u t i o n s i na d d i t i o n ，t w on o v e ll o c a ls e a r c ho p e r a t o r sa r ed e s i g n e da n dc o m b i n e di n t o t h ea l g o r i t h mt of u r t h e ri m p r o v et h eq u a l i t yo fs o l u t i o n s a sar e s u l t ，t h e p r o p o s e d e v o l u t i o n a r ya l g o r i t h m c a n e f f i c i e n t l ye x p l o r e t h es e a r c h s p a c e f u r t h e r m o r e ，t h e p r o p o s e da l g o r i t h mi sp r o v e dt oc o n v e r g et og l o b a lo p t i m a ls o l u t i o nw i t hp r o b a b i l i t y o n e t h en u m e r i c a le x p e r i m e n t sa l s oi n d i c a t et h ep r o p o s e da l g o r i t h mi se f f e c t i v ef o rt h e t e s tp r o b l e m s s e c o n d l nan o v e le v o l u t i o n a r ya l g o r i t h mf o rt h em u l t i c r i t e r i am i n i m u m s p a n n i n gt r e ep r o b l e m i sp r e s e n t e d w ea l s oa d o p tp r t l f e re n c o d i n gm e t h o dt or e p r e s e n t t h es o l u t i o n so ft h ep r o b l e m 。t w on e we f f i c i e n tg e n e t i co p e r a t o r sa r ed e s i g n e dw i t h o u t c o n s i d e r i n gd e g r e e c o n s t r a i n t s t h eg l o b a lc o n v e r g e n c e o ft h e a l g o r i t h m w i t h p r o b a b i l i t yo n e i sp r o v e d t h en 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 et h ee f f i c i e n c yo ft h i s a l g o r i t h m k e yw o r d s ：e v o l u t i o n a r ya l g o r i t h m s ，m i n i m u ms p a n n i n gt r e ed e g r e e - c o n s t r a i n e d ， m u l t i - c r i t e r i a 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果：也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名 留勇 f i 期： 0 。弓7 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文：学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其他复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本人签名 导师签名 i 髫勇 兰簦圣 f ：i 期： 。0 3 f i 期：矗口矽亏，吕 第一章绪论 1 i 引言 大自然是人类获得灵感的源泉在人类历史上，通过学习与模拟生物界来求解 实际问题的成功例子不胜枚举模拟飞禽，人类可以邀游天空：模拟游鱼。人类可以 横渡海洋：模拟昆虫，人类可以纵观千里：模拟大脑，人类创造了影响世界发展的计 算机自从2 0 世纪后半叶以来，人类正在将模拟和学习的范围延伸向人类自身我 们知道，自然界所提供的答案是经过漫长的自适应进化过程而获得的结果我们可 以模拟这一过程而不仅仅是结果来解决一些较为复杂的问题“，我们不必非常明 确的描述问题的全部特征，只需要根据自然法则来产生新的更好解 进化算法正是基于上述思想而发展起来的一种通用的问题求解方法它采用 简单的编码技术来表示多种复杂结构，并且通过对一组编码表示进行简单的遗传 操作和优胜劣汰的自然选择来指导搜索方向由于它采用种群的方式组织搜索，使 得它可以同时搜索解空间内的多个区域，而且用种群组搜索的方式使得进化算法 特别适合于大规模并行计算 1 2 进化算法的主要特点 进化算法是一种仿生优化算法，它与传统的算法有很多不同之处，其最主要的 特点体现在以下四个方面： 1 ) 进化算法的操作对象是一组可行解，而非单个可行解：搜索轨道 有多条而非单条，因而具有良好的并行性 2 ) 进化算法只需要利用目标的取值信息，而无需梯度等高价值信息，因而适 用于任何大规模、高度非线性的不连续多峰函数的优化，以及无解析表达 式的目标函数的优化，具有很强的通用性： 3 ) 进化算法择优机制是一种“软”选择，加上其良好的并行性，使得它具有 良好的全局优化性和稳健性 4 ) 进化算法操作的可行解集通常是经过编码的，目标函数解释为编码化个体 ( 可行解) 的适应值，因而具有良好的可操作性和简单性 1 3 进化算法的发髓与现状 由于藏所其有鲍本质并行性，自组织秘适应性，以及优胜劣汰的自然选择 和麓单麴遗传搡髂，使锝进他冀法具誊不受搜索空辩j 限制性条件f 如霹微、连 续、荤蜂、多峰等) 的约柬及不需嚣其它辅瀚信惠( 如导数) 的特点，游纯冀法已 经成功的应用到许多难戳利用传统的方法进行求解的复袈问题之中，从聪成 为一拿雩| 入注嚣翁磷突方国+ 稷豢德溪d o r t m u n d 大学提供豹一份硬究报舞， 进化算法已经在1 6 个太领域2 5 0 多个小领域中获褥了应用唑籽前祷数种以进 能舞瀵为主题熬髫黪会议在遂器各地定麓程牙p “。凌在跫经逡敝鼹转关予进 化簿法的新杂志：“e v o l u t i o n a r yc o m p u t a t i o n ”( 由m i tp r e s s 出舨，1 9 9 3 年觎千1 ) 籀“i e e et r a n s a c t i o n so ne v o l u t i o n a r yc o m p u t a t i o n ”( i e e e 汇刊，1 9 9 7 年剑于q ) ， 丽且一些戮际蛙麓涮瞧竟穗出敝戳遂纯算法为主憨靛专瑙l 爵涮舞多 ，某些学耆 通过对进他算法的自现行为研究殿声称，谶化算法将与混搴醢理论和分形凡何 遂成为天蠢j 磺究线牲瑗象嚣菱杂匿系绞憋囊豹三大方法，势鼗耨黢耱经瓣缮 一道成为人们研究认知过程的重鼗工其弘b 1 目前，进位簿法的研究主要集中 在以下方磁： 逮住辣法酶基础理论研究爨献模援篷锡避化_ i 妻程避行闻遂求解敬褥成 功以来，人们就试图对其进稃煺论分析以解释它为什么有效鲻前关予进 俄算法基磷理沦鹣磷究在三方灏邂褥麓，宅餐燕：s c h e m a 理谂及荬撂广 与深入，进化算法的马氏链分桁 1 5 ，进化算法的收敛理论i 1 5 i 。 遂诧冀法设诗与巍露策嬉逡纯冀法豹设计霹执行策雅趣禽编码方法、 选择枫制、杂交与变界枧锚、执行策略的设计与改进其中执彳予策略包含 进化豁法鄹模擞退火鹅部优化方法韵缡合，跌及并行遂化算法的设计”1 进化舞法奁神经两络、模颧系统和税潞擘习枣的疲蘑避位箨法蠢缀广 泛应阁于前向神经网络、径向享卓经网络、k o h o n e n 特征映射及r e c u r r e n t 网络等各耱人工褥经辩终静诞练与设计孛。进豫算法毽袋凌懿瓣予模獭系 统的激属函数形状与黔数优化以及推遐规鲥的选取+ 进化簿法在机器擀霹 系统上熬瘦绸瞧十分潘跃m j 。 进仇算法在多霹标优他中黥成稻雾嚣棘徒识润憨不瓣予革强标优亿蠲 题那样通常只商确定的解，其解往往是一个集，我们称其为p a r e t o 解集 传统谨纯方法缀难我蘩全舔p a r e t o 瓣鞭逢稼舞法壶予英操撵鼹象是一缝 可行解，因稀执行一次就能找到多个p a r e t o 解蟊前遂优算法猩多目标优 讫孛露经驳褥了攘多妊粒结暴”6 - 2 0 t 。 l 。4 本文熬主簧工作与魂容安捺 本文蓦先磷宠避化簿法：其次蛰对送耽嚣法豹瘦弱，酝究了进 皂爨法在一个 绑台优化阀题以及多嗣标优化闻题中的应用本文的工作主要包搔： 1 1 进化算法在单目标优化m 题中的应用我们以网络拓扑结构优化设计问题 为铡磷究了遗像葬法在萃蚕标伉纯淘瑟串熬瘦糯。露缀籀羚缩糖设诗嚣 要求解带度约束的最小生成树问题，它熙n p - 完全问题本文设计了求解该 润题静避仡箕法。算法采鞠纾g f r 编弼表示溺戆豹释，络台编粥设诗了溪 个新的遗传算予，算子能避免产生大量不可行解，从而提高了算法的搜索 效率数篷实验裘弱算法适会该润蘧，臻论分撰表明篓法戳援搴1l | 芟敛予 全局最优解 2 进位算法在多瓣拣决繁闷莲中鹃瘫慝。我锭鞋多彭昧爨终掘羚络兹设计瓣 题为例研究了谶化算法在多目标决策问题中的威用多嗣标网络拓扑结构 设诗魄攀嚣标嘲络辐羚结构设诗矍必爨壤蘑又实曩，它鼹要综会考虑多个 相互矛盾的目标来求解进化算法由于箕本质并行性适于求解多目标决 策问题。本文提崽了一令毙找到更好的p a r e t o 麟嶷的进化算法。数值实验 表明算法非常商效，理论分析表明算法以概率1 收敛于p a r e t o 解集 本文的内容安摊如下： 在本章给如了进化算法的简单介绍之后，猩接下来的第二章，详细描述了避 化算法的主要分棱、基本原理、设计方法以及纂本理论研究第聂章介绍了网络拓 扑结构优化河磁，对进化算法在上述领域的应用作了迸一步研究，给出了一个新的 进化算法并且诚明了其收敛性。第四章对多目标秘络拓扑结构优化问题，提出了能 找到更好的p a r e t o 解的谶亿算法理论分析表弼簿法戳穰率1i | 芟敛螽瑟总结了众 灾 第二章进化算法 进化算法是一种仿生优化算法，它是从某个初始种群出发，不断重复 执行遗传操作的过程，使得种群进化越来越接近于某个目标本章首先介 绍进化算法的基本概念以及四大分枝，然后具体讨论进化算法的设计问 题，最后介绍了进化算法已有的基础理论研究 2 1 进化算法基本概念 假设我们考虑的是如下一个优化问题： m a x f ( x ) l x e x ( 2 1 ) 这里，是x 上的一个正值函数，即对任意x e x ，f ( x 卜0 z 是问题的解空间，即问 题的所以可能解全体它可以是一个有限集合( 如组合优化问题) ，也可以是实空间 r “的一个子集( 如连续优化问题) 进化计算在求解问题时是从多个解开始的，然后通过一定的法则进行逐步进 化产生新的解这多个解的集合称为一个种群( p o p u l a t i o n ，或者称为群体、解群、 居群) ，记为p ( t ) 这里t 表示迭代步，或者称为进化代一般的，p ( f ) 中的元素个数在 整个进化过程中是不变的，我们把它称为群体的规模，记为p o ) 中的元素称为个 体( i n d i v i d u a l ) 或者染色体( c h r o m o s o m e ) ，记为x 1 ( f ) ，z 2 ( f ) ，等在进行进化时，要 选择当前解进行交配以产生新解，这些当前解称为新解的父辈( p a r e n t ，或者称为 父亲、父体等) ，产生的新解称为后代解( o f f s p r i n g ，或者称为儿子、后代等) 进化算法常常要对问题的解进行编码，即通过变换将石映射到另一空间x 。 ( 称为基因空间) 这个变换f ：z - * x 。，要求是可逆的，f 。1 称为解码变换通常， z 。中的点是字符串的形式，假设x 。- 0 ，1 ) ，即x 。是长度为，的二进制串全体，则 一个长度为f 的二进制串称为一个染色体染色体的每一位称为基因( g e n e ) ，基因 的取值称为等位基因( a l l e l e ) ，基因所在染色体中的位置称为基因位( 1 0 c u s ) x 。 中的点x 称为基因型( g e n e t y p e ) ，f _ 1 0 ) 称为x 的表现型( p h e n o t y p e ) 在对进化算 法进行理论分析时，常常用到下面概念： 定义2 1 ( 通配符)在一个由空间 0 ，1 ，+ ) 表示所有的字符串中，字符+ 称为通 配符+ 可以表示0 或者1 它们是不确定字符，而o 和1 是确定字符 定义2 2 ( 丰莫式( s c h e m a ) )一个由空间 o ，1 ，+ 中的字符构成的字符串中称为 一个模式，记做h 模式中可以含有通配符 例如：h = 0 十1 0 一 0 0 1 0 0 ，0 0 1 0 1 ，0 1 1 0 0 ，0 1 1 0 1 h t 0 1 1 1 0 = 0 1 1 1 m 定义2 3 ( 模式阶( s c h e m ao r d e r ) ) 模式中确定字符的个数称为模式阶记做 o ( h ) 侈4 如：h 一0 1 + 0 1 + ，则o ( h ) = 4 定义2 4 ( 定义距)模式中第一个确定字符( 从左数) 的位置到最后一个确定 字符的位置间的距离称为定义距记为6 ( h ) 例如：h = 0 1 ，0 1 + ，贝u 6 ( h 1 = 5 一l = 4 定义2 5 ( h a m m i n g 距离) 两个不含通配符的模式i 和，z f n 不同对应位的 个数称为h a m m i n g 距离记做h ( i ，) 例如：h 1 = 1 0 0 0 0 ，日2 0 1 1 1 1 ，则h ( 1 ，2 ) 一5 2 2 进化算法的主要分枝 进化算法有四大分枝：遗传算法( g e n e t i ca l g o r i t h m ，简称g a ) ，进化策略 ( e v o l u t i o ns t r a t e g y ，简称e s ) ，进化规划( e v o l u t i o n a r yp r o g r a m m i n g ，简称e p ) ， 遗传规划( g e n e t i cp r o g r a m m i n g ，简称g p ) 虽然这几个分枝在算法的实现方面有细 微的差别，但是它们具有一个共同的特点，那就是它们都借助生物进化的思想和原 理来解决实际问题算法2 1 描述了进化算法的一般框架 算法2 i t l l ( 进化算法框架) 步1 ：生成初始种群( i n i t i a lp o p u l a t i o n ) p ( t ) 一“，x ；) ，t - 0 ，n 称为种群规模 步2 ：计算种群中个# # - ( i n d i v i d u a l ) 的适应值( f i t n e s s ) 步3 ：按某种规则从p ( f ) 中选择一个子种群p o ) c p ( f ) 作为父代( p a r e n t s ) ，用进 化算子( c r o s s o v e r 、r e c o m b i n a t i o n 、m u t a t i o n 、s e l e c t i o n 等，作用于p ( f ) 得到 下一代种群p ( t + 1 ) ，t t + 1 步4 ：若终止条件成立，则停否则，转步2 f 蠢我拜1 分羽奔缁进纯算法髂死个分鼗 2 2 。1 遗转算法 把汁算枫辩学与遴纯论结台起来的尝试开始于2 0 世纪5 0 年 弋术，瞧出予缺乏 通川的编码方案，人们只能依赖变异丽不是杂交来产生新的鏊因结构，因而收效甚 微判2 ( ) 世纪6 ( ) 年代中期，美固的m i c h i g a n 大学的j o h nh o l l a n d 在a s f r a s e r 和 j b r e m e r m a n n 等工作靛鼙麓上箍出了位窜编码技术，这萃孛缡褥蘸逶合交舅又逶 合杂交操作，并且他强调将杂交作为主要的遗传操作随后，j h o l l a n d 将该算法用 二l ：自然豹久王系统毂鑫适应 亍为豹磺突之中，劳于1 9 7 5 年惑舨其野割蛙的著传 a d t t p t a t i o n i nn a t u r a la n da r t i f i c i a is y s t e m s1 1 4 后柬，j h o l l a n d 与他的 学生们烽该算法加以推广并应用到优化及机器学习等问题中，丽且疆式定名为遗 传算法( ( ；e n e t i ca l g o r i t h m ，简称g a ) 遗传算法的通麓编码技术及简单有效的遗传 操作作为其广泛的应用和成功奠定了撼础【1 5 1 l l a n d 静遗传棼法逮常壤嚣态麓单逮嫠算法( 蓠记s g a ) ，s g a 魏搡 睾怼象跫一 群二谶制串( 称为染色体、个体) 即种群( p o p u l a r i o n ) 这里每个染色体都对于与问 题叠勺一个勰+ 从拐始葶枣群出发，采用基于适应馕比铡的选择策咯在当魏种群中选择 个体，使用杂交( c r o s s o v e r ) 和变异( m u t a t i o n ) 来产生下一代种群如此一代代进 化f 去，直到满足期望的终止条件算法2 2 描述了简单遗传算法 算法2 叠q ( 简单遗传算法) 步l ：随机生成初始辞群p 一磷，z ； ，f - 0 黠尹( f ) 申每个点进行编碣徉霸 染色钵旁列移；，醵 ，其孛秘每令0 和1 爨砖基n ( g e n e o r b i t ) ， 步2 ：计算适应值 步3 ：按某种规则从p ( ) 中选择一个子种群p ( f ) c p o ) 作为父代( p a r e n t s ) ，j 带杂 交( c r o s s o v e r ) 侔瘸于尹。f ) 铎餐一些麝代( o f f s p r i n 酹，菇痿变异( m u t a t i o n ) 作 用于每个后代产生摩代集o 计算。申每个詹代的适成值 步4 ：用选择算予( s e l e c t i o n ) 在p ( f ) u o 中选择交下一代辩群联f + 1 ) ，t 。t + 1 。 步5 ：若终止条件成立，则停否则，转步3 波渡洼黎弱是：嚣藏懿遗传雾法不毒羼缀- 7 二遴铡缡强h 6 1 z 。m i c h a l e w i c z 将不同的编码策略( 即不同的数据结构) 与遗传算法进行了结含【1 1 2 2 2 进化策略 霞2 f 匿纪6 0 年代扔，稽棒工盐大学酶1 r e c h e n b e r g 和h 。p s c h w e f e l 等在遂幸亍 城溺实验辩，窿予在设计孛撼逑撩蒋形谈翡参鼗滚瑷餍搀绞麴方法避抒撬 毫，飘瓣 镶翻裁蠲生貔变舞瓣瑟憋寒瓣搬豹羧变参鼗蠖势盈联褥了羧好懿效聚。隧矮，经镪 露这秘方法避嚣了深入熬研究黧发震，掰戏了邀誊艺箨法瓣鬟一个分棱避能麓 赂( e v o t u ti o ns t r a t e g y ，简称e s ) h “。 避 幺繁蟋主瑟可分为三耪：弘+ 1 ) 避化繁踞，伽+ 匀进纯策酶和鳓柚避纯策 昭它稻的毙较冕下袭 袭i a 兰释避纯薰旗晓较 避毒艺菠骆撂辩与遗传簿法g 萄鞠不藏之处在予：翁先，凇篙要避行二避剿缡鹊， 薅e s 妻接袋庵“遽测缓鼹( 戏称浮蠡数缡礤) ：冀次，g a 潋杂交必主蘩进化冀予，蕊 s 以变器为主娶避化箕予；簸囊，g a 蹰针对麴是离散傀豫问题，嬲弱主要耱辩数德 谯髂离题( 连续阏瑟) 。 缓樽注纛的楚，簸然避俄繁酶主爨霸予黎解数值後纯润瑟，毽爱逐年寒，逡传算 法瞧i 歼戆果鼹浮患数缡璐撩零寒黎黧数壤虢铯趣题醛窥鑫a 戆檄夏渗透爨缀傻褥 宅畿没鸯擐骥显靛器隈 2 。2 0 进识嫂怒 遴豫蕊熊( e v o l u t i o n a r yp r o g r a m m i n g ，e p ) 的方法簸裙愚蠢0 + j 。f o g e t 蒋谯2 0 髓跷巷。年代提掇静i 鞠。能稍在入工智能豹磷窥巾发魏智麓行为都是罄其宥颈测籁 掰簸环璇熬状态，著按黧蹬定懿鬻酥捧爨适应懿疆鹰能力。逛裁黎中，穗翻将攘缀 环凌援述袋漆鸯羧字符爨审豹蟹会缀残黥露羧予燕耀纛转换为：葱撵棂撼囊兹鼹 察到戆蒋合涝烈髂绻礁激芝土获致最大敬牧益，这摄收益熟诗葵爨按照疆蟪中糨蘩 蹬蕊的下一个符念鬣预先定义好昀效益隧轹来确定瓣。避健娥烈中鬻臻露隈歌杰 商动聿咒( f i n i t es t a t em a c h i n e ，简称f 跚) 泉表辩这样静策龌这样，问联便成为： 魏籍设诗爨一令谢熬戆f s m ? l ，j f o r g e l 繁嵇麓避纯戆瓣惩对群怒氍避行逶缳 以获褥较好鹣f s m 。魏稻将致方法瘟鬻到数搽诊羲、模式谖髑帮分裳激及控潮系统 熬投诗等趣之甑并馥褥了较鬈熬结果 删+ 瑟絮，d f o g e l 氆疑予避纯策潞方法 瓣遂纯燃越进行了教震，菸鼹到数壤饯亿及褪经戆络戆训练簿翊鼷之中l 拍瑚l ， 避镬二瓶划的算法籀遴如舞法2 3 算法2 0 f 2 2 l !瞧窒垒垂丝丝叁警丝篁塞：璧垡基鎏星基煞堡垒垡堡童墼堡缝 ( 避耗麓蜊箕法) 步1 ：随机生成初始种群p ( t ) = “，；) ，t * o ， 一0 步2 ：计算适应值 步3 ：对每个个体按照定义在其上的一个函数值采确定一个分布按照此分布 对令体透行雯异得巅麓砖群 步4 ：在新种群申随机选取k 个个体( kc n ) ，将其中最好的个体被八下一代种 君善尹扫1 ) 中，辩兰裾+ 1 步5 ：若h n ，转步3 否则t t t + t ，n 。0 步6 ：若终止务件成立，则停否则，转步2 。 避化规划和遗传算法稻范：p 对解无限制，箍g a 需簧二逶帚编码：e p 无杂交算 予，而( ；a 需要杂交：e p 随着解越来越逼近最优解，其变辩的程度越来越小，即变拌概 率越寒越士，露( 、盎豹变算概率不交。 进化规划和进化策略相比：e s 采用重组算予( r e c o m b i n a t i o n ) ，而e p 不采用：e p 豹选择方法实际上是随枫竞赛法( s t o c h a s t i es e l e c t i o nv i at o u r n a m e n t ) ，丽e s 足种确定性的方法 2 , 2 4 遗传规划 遗传褒矧( ；e n e t i cp r o g r a m m i n g ，篱称g p ) 懿懑怨是蠢s t a n f o r d 大学貔 j r - k o z a 在2 0 世纪9 0 年代初提出的，并于1 9 9 2 年出版专著“g e n e t i c p r o g r a m m i n g ”，1 9 9 4 年又出舨了第二卷【2 7 捌其主要毯螅是为了接计算枫能够鑫动 进行程序设计，即只需簧明确的告诉计算机要解决的问题。而不需要告诉它如何去 做，它采用遗传算法的基本思想，但是它采用了更为灵活的表冰方式分层结构 来表示解空闯这些分层结构的时结赢是闰冠静原始变蓉，孛漓结熹蓟是缝合这些 原始变量的函数这样的每一个分层结构对应于问题的一个解，也可以理解为求解 浚闽越熬一个诗算捉操_ 亭遗传援剡秘是傻蒡l 一些遗健操终动态魏改变这些结擒 以获褥解决该问题的可行的计算机程序因此遗传规划也被称为遗传程序设计 2 3 进化算法的设计 2 3 。l 进化算法设计的綦本原则和步骤 在设计进化算法时，通常要考虑以下原则： 逶弱孛耋琢爨：令算法瓣逶用筏，是撂该算法j 舞缝逶痰熬润嚣秘类，玄取决 j i 簿法所需要的限制与假定如优化问题的约束不同，则处理的方式也不同 2 可鬟性琢则：一个算法的可靠性，是指簿法对掰设计的润题，以遥当的精度 求晰人多数问题的能力因为进化算法的结采带有一定的随机性和不确定性，所以 设计算法时，应该经过大量样本的检验以确定算法是否可靠 3 收敛性原则：进化算法的收敛性通常是指能否以概率1 收敛到全局最优解 在收敛的前提下，我们希望算法有较高的收敛速度评价进化算法收敛速度的方法 之一是比较有限时间段内算法所求解到达的精度 4 稳定性原则：进化算法的稳定性是指算法对其控制参数及问题数据的敏感 度如果算法对其控制参数或者问题数据十分敏感，那么依据它们取值的不同，算 法的结果也不同，甚至过早收敛到局部最优 在设计进化算法时，通常按照以下基本步骤进行： 1 确定编码方案：进化算法求解问题往往不会直接作用于问题的解空间上，而 是利用解的某种编码表示编码的表示对算法的性能和效率有很大影响另外编码 应该要保证编码空间的所有点要能够映射为原问题空间的解，否则会产生不可行 编码从而浪费计算时间和空间：原问题空间的所有解要能够成为编码空间的所有 点，否则可能丢失可行解甚至最优解 2 确定适应函数：适应值是对解的质量的一种度量一般用目标函数或者费用 函数的形式来表示解的适应值是进化过程中进行选择的唯一依据 3 确定选择策略：优胜劣汰的选择机制使得适应值大的解有较高的存活概率， 这是进化算法和一般搜索方法的主要区别之一不同的选择策略对算法的性能有 较大的影响 4 控制参数的选取：控制参数主要包括种群规模，进化最大代数，执行不同进 化算子的概率以及其它辅助性的控制参数 5 进化算子的设计：进化算法的进化算子，主要包含繁殖( r e p r o d u c t i o n ) ，杂 交( c r o s s o v e r ) ，变异( m u t a t e ) 以及其它高级操作 6 终止准则的确定：由于进化算法没有利用目标函数的梯度等信息，所以在进 化过程中无法确定个体在解空间的位置从而无法用传统的方法来判定算法的收 敛与否常用的方法是预先规定一个最大的进化代数，或者在连续多少代以后解的 质量没有明显的改善时，算法终止 7 编程上机测试：完成上述工作以后，就可以按照进化算法的算法结构来进行 上机模拟，由于进化算法的不确定性，通常要多运行几次才能得到可靠的解 值得注意的是：上述各个步骤是紧密相关的，编码方案和进化算子的设计是同 步考虑的，有时甚至需要和上机测试交替进行 2 3 2 进化算法的编码设计 设计进化算法的一个重要步骤是对解空间的点进行编码，编码方案的选取很大 程度上依赖于问题的性质和进化算子的设计下面介绍一些常用的编码表示方案， 相应的进化算子在下一小节介绍 二进制编码设f ( x 1 是月维实数空间r ”到正实数r + 的函数对于x e r “可 以与一个长度为f 的二进制对应，于是求解m i n f ( x ) 的问题可以转化为求解 m i n f ( x ) ：x e b 。 o ，l ，其中，( x ) 一s ( f ( e 。( x ) ) ) ，e 楚r 8 到摩7 的编鹤映鸯| 。s 是 r + 到r + 的煺函数。通谨采用的二进铡缡码映射为固体长度z 的二进制编码。二进制 编鹧称为个体，长度，的二述制编码全体称为个体空间二迸制编码可以是实数的 j 进制表示，她可以是按照某种规则进行的二进制编码，但是要求二进制编码和实 凝之闻一一对应 例如，变毓x 的定义域b ，其要求的精度为s ，则区问 a ，b 分成歪少 ，f o s ，拿等长小区闼，藤每个小区瓣用一个二避铡串表示。计算满足 2 - ttf ( 6 一“1 t2 f i 0 串长f 这样，计算中的任何一个二进制串都对应于 a ，b 中的 个点j e 解码过程如下：首先，将二进制串p 。岛- b 。) 依照下式转化为一个十进 捌数， l - i x 。酗2然后计算对应变羹z = n + x + 西b 当变蒙不止一个分萤辩，可 以羽+ 各个分羹分别编避，然爱台共戏个长枣解码时，分别缀撂对斑靛子串进行 解码即可 ：进制编码易于进行进化操作，丽且采用二进制编码时，算法处理的模式数目 最多键是+ 二二进涮编鹞的码长需要预先估计，魏票太长剐影豌计算效率，太短羽会 漏掉可行解而且二进制编码w 能有较大的h a m m i n g 距离，例如7 和8 的二进制编 露；分潮为f ) l11 和1 0 0 0 ，剩冀法扶7 改进到8 必须改变艨骞豹缎这将影响进化冀法 的搜索效率，下面的g r a y 编码可以克服该缺点 g r a y 编码是将二进制编码通过一个变换得到的编码设有二进制串 ( b t _ l l ，。6 ，) ，对应的g r a y 编码为( n 。a 。n 。，) ，则它们之间的转换如下两式 如聚k = l ； 女l i 果k 1 钆。酗( m 州2 ) 例眠二迸制串1 1 0 1 0 1 1 对应的g r a y 编码串为1 0 1 1 1 1 0 实数编码是为了克n - - - 进制编码的缺点，对予问题的变量是实空间的向量， 盔禳采稻卡滋制进行编筠，这祥，便弼激壹接在解空黼静表现垄上逡行逶耗搽释。 山便于引入启发式的方法来增强搜索能力【1 , 2 9 1 近年来，进化算法在求解高维或者 复杂傻讫翔簇辩，大多都采蠲实数编鼹。 有序串编码广泛应用于组合优化问题 3 0 - 3 5 1 例如4 个城市的旅行商 姐r w e l i n gs a l e s m a np r o b l e m ，简称t s p ) 阐题编码 1 234 就是个有序串编 码，它表示商入旅行的路径为从城市l 出发，曾先到达城市2 ，然后由城市2 滋发到 达地汁了3 ，再i j - i 城市3 出发到达城市4 ，最后由城市4 阐到城市1 用进化算法求解有 穿闷遂时，传统瀚送纯算子可麓产生 法兹纛代，霞藏其算予瓣要仔缀夔设计 结构式编码很多问题的表现形式是树或者图这时采用其它形式的编码是 列善淄难敬毒錾这秘润题静嬲表示成为 对或者强豹形式熬编鹈称为缀构式缡码。这 样的u j 题1 莆蛾找i l 硎i 常谨懊的设计进化算予，而且对于结构式编码缺乏通用的迸 纯舞子，一般需要鬟俸阕题其俸分褥本文豹工俸奎要集孛在结梅式编码鹣泼避滚 及相应进化算子的设计，我们将在下两章详细描述 2 3 3 进化算法的适应值度量 进化算法的适应值度鬣方法育很多种可以用瞬标函数的形式给出，也可以用 目标函数变换的方式来定义例如求解问题( 2 。1 ) 时，可以瓶接采用f ( x ) 作为原始 适应函数，也可以将，标准纯，定义，。扛) 一，一矗。其中元。为嚣始适应醛 数f ( x ) 的个下界，如果，。未知，则可以用当前种群中或者到目| j i 为止的各代进 化中f ( x ) 数最小夔来找骜 但是在设计进化算法时，种群规模一般都比较小，和实际问题的规模相麓甚远 因此，一旦种群中出现了越级个体，即它的适应值邀远超过神群的平均适废值，则 按照眈例遮择时，该个体校快会在群体中占有绝对犬的眈倒从丙羚致算法过旱酶 收敛到一个局部最优点，因此这时需要减小个体之间的差异然而。在进化的最后 除蔽，耱群各个令嚣抟差器邑经狠小，在进化瓣速发会减馒，建了麓抉浚敛。瘦该敖 大个体之删的差异 为了嬲决这诱个问题，我们需要将适应值函数尺度化。设适应值函数为，扛) ，我 们用如下不同的方法来尺度化： 1 。线性尺度化设7 b ) t n + ，+ 6 ，其中。，b 烧适当驰常数，莠且满足 i i ，o ) 和灭x ) 平均适应值相同 i i i m a x 灭x ) 一c a v e r a g e ( f ( x ) ) ，c 1 2 ，2 】 2 幂函数法 设7 t f ( 0 8 a ，o 3 。指数法 设孙) e x p ( ；- ，缸) ) 多，o 例如： 设f o ) - 2 0 0 , ，2 ) - 8 , f ( 3 ) - 7 ，4 ) 一6 ，令7 b ) - t e o o i 鹏，则掇到 7 ( 1 ) 一2 , 7 1 ，7 ( 2 ) 一1 0 4 , f ( 3 ) - 1 0 3 6 ，狱4 ) 。1 0 3 0 这样个体之间的慧异明显减少了 2 3 4 进仡冀法的选择策略 选择繁漆对逶讫算法鼢往麓有举是轻黧觞俸焉。不阕韵选择策貉会导致不丽噩奄 选择压力较大的选择压力使得最优个体有较高的复制数目，从而使得算法收敛速 度较快，但是容易出现过早收敛：而较小的选择压力能保持种群的多样性，增大了 算法收敛到全局最优的概率，但是算法的收敛速度较慢 f 面介绍进化算法常用的几种选择策略： 轮盘赌选择 该方法在进化算法中使用得最多【3 2 j 3 2 它先计算个体的相 女一l 刘适应值p ，一 罗 在选择时，生成一个 0 ，1 的随机数，如果罗p 。t rs 罗p 。， 一 ：i i蔚 则选择个体k ，此处假没p = 0 这种方法类似于轮盘赌中的转盘因而得名 保留最佳个体选择( e l i t i s te l e c t i o n )陔方法将算法到目| i 为止最好的个体 保尉，不参加进化，直接保留到下一代种群 期望值方法( e x p e c t e dv a l u es e l e c t i o n ) 该方法首先求出每个个体在下一代 n g 二存的期望数，m ，： ( y ，n ) ：如果第i 个个体被选择参加进化则其在下一代生 篇。 存的期望数减去0 5 ：然后将第i 个个体复制i m ，i 份，其小数部分作为选择概率再参 加选择：一旦一个个体的生存期望数降低到o 或者小于0 ，则浚个体被淘汰 排序选择法( r a n k - b a s e ds e l e c t i o n )该方法按照个体的适应值大小给个体 排队，每个个体分配一个选择概率，适应值大的选择概率大，然后按照轮盘赌的方 式或者一个一个贝努力实验进行选择 联赛选择法( t o u r n a m e n ts e l e c t i o n )该方法从种群中任意选择一定数目 ( 预先给定) 的个体( 通常称为竞赛规模) ，然后从中选择适应值最大的个体，重复前两 步直到选择出预定数目的个体 排挤法( c r o w d i n g )该方法首先给定排挤参数c f ( 自然数) ，从种群中随机 选择c f 个个体( 新的后代不包含在内) ，然后从c f 个个体中丢掉与新后代的 h u n n l i n g 距离最短的一个 2 3 5 进化算子 本节我们仅介绍文献【1 1 中有关二进制编码和实数编码表示下杂交和变异算子 的设汁有关结构式编码的进化算子我们在下一章讨论 对于二进制编码，常用的进化算子如下： 1 点式杂交( p o i n t a lc r o s s o v e r ) 点式杂交分为单点杂交和多点杂交单点杂 交随机的在父代上选择一个杂交点，然后交换两个串的对应予串多点杂交则是一 次随机生成多个杂交点，然后间断交换对应子串单点杂交和两点杂交算子如图 2 1 所示 囊一龟r 。c 毒艄t ， - - 、l l o 1 麓： 、s 蛾， i + l k 二 1 1 _ ；： j l _l | | 翻2 1 单点杂交和两点杂交示意翻 2 一致杂交( u n i f o r mc r o s s o v e r )电称为均匀杂交其过程是：先随机的产生 一个帮父事有等长翁二避铡宰，茭中0 表示不交换，l 表示交换该二逶割率称为杂 交模板( t e m p l a t e ) ：然后根据该模板对两父串施行杂交，所得两个新串为后代串 例如： 父审 l ：1l00l01 1l0 0 父串2 ： 1010lll00l0 揍投 ：i0 00l01lll 1 后代串 l ：1l001010010 后代串2 ： l0l0ll lll00 3 位点变异以一定的概率p 。将父串中的某个随机选取使置的值进行取反 即如果怒0 则变成l ，如果是1 则变成0 。 4 。j c 壹换交髯敬一定翡獠率p 。麓梳选择父串孛豹两个彼嚣，交换两个位凝 的值 5 。攮入交舅 以一定缎羧搴p 。隧援选择父串孛懿个位嚣k ；，菇夔凝选撵 父串中的另一个位置k ，将第女俄的值移到k ：位之后 对予实数编码，其进化算子和二进制缡码完全不同常用的算子如下为了方便 叙述，我们假设解向量怒一维的，并且每个分萋都在有黻区简上定义，例如：假设 s ；v l , v ：，) 是一个鳃| 趣量，则有唯k ，甄l l 一1 , - - - m 反之对经侮满足v ；i ；点】 的向量s 。- ：，v ：，v ：) 都是问题的解设两个父解向量分别为s 一如。，v ：，) 和 f 一“i ，“2 ，“。) 1 离散杂交在父解向量中选取一部分分掇，然后交换这些分量以形成后代 秘如选取第女个分量戬鬣的所有分量剐两个嚣 弋分箱为 d l d 1 ，v 2 ，h i “，“。) 。2 肆i ，嚣2 ，t t ，h ，珞l ，v m ) 湿然，通过离散杂交产生的后代，其分量仍然在其定义域之内 2 。辣术杂交在父解向量中选取部分分爨，例如选取第个分量以后的熙 艮穗 麓 t ! !堕窒坠兰丝丝叁童堡垒塞! 丝些塞鋈墨星垒丝坌垡些呈墼蜜些 彳分也然后生成，t k 个( 0 , 1 ) 区i u j 的随机数a 。，a 。，两个后