（应用数学专业论文）全局优化的进化算法.pdf

摘要 进化算法是模拟生物界的进化过程而产生的一种现代优化方法，作为一种有效 的随机搜索方法，在优化方法中具有独特的优越性，有着非常重要的意义和极其广 泛的应用本文首先简述了遗传算法的基本数学理论及其应用领域然后提出了几 种改进的进化算法，并将其应用于全局优化问题，主要工作如下： 1 提出了采用均匀分布编码方式的全局优化遗传算法和正交紧致遗传算法 前一种算法采用了新的编码方式，即每个染色体都表示搜索空间中的一个多元均 匀分布区域。使得该算法以区域对区域的方式进行搜索，提高了搜索效率：后一种 算法用概率向量表示一个种群，精英个体诱导概率向量的收敛，该算法不仅简单， 而且需用的存储空间很少数值实验表明了两个算法的有效性和较高的效率 2 针对多次分组会议的最佳安排方案问题，采用矩阵编码和正交杂交算子，设 计了一个自适应的遗传算法与整数规划方法相比较，该算法简单、易于实现数值 结果也表明了该算法的数值稳定性和高效性 3 粒子群算法简单有效且参数少，但是其中的关键参数对算法的性能产生重 要影响在标准粒子群算法的基础上，针对关键参数经验设置法的局限性，提出了 一种新的粒子群算法该算法采用均匀试验设计对参数进行优化设置，数值实验表 明了算法的可行性和高效性 关键词：全局优化遗传算法组合优化粒子群算法均匀设计 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 sa i r en e w k i n d so fm o d e r no p t i m i z a t i o na l g o r i t h m st h a ta i r e i n s p i r e db yp r i n c i p l eo fn a t u r ee v o l u t i o n a sn e wk i n d so fr a n d o ms e a r c ha l g o r i t h m s ， t h e yh a v es o m ca d v a n t a g e so v 盯t l a 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 s a n da r co ft l a e g r e a ti m p o r t a n c ea n dh a v eaw i d er a n g eo fa p p l i c a t i o n s i nt h ep a p e r , f i r s t l yt h eb a s i c m a t h e m a t i c a lt h e o r ya n da p p l i c a t i o nf i e l d so ft h eg e n e t i ca l g o r i t h m sa r cs u m m a r i z e d , a n ds o l n ci m p r o v e de v o l u t i o n a r ya l g o r i t h m sf o rg l o b a lo p t i m i z a t i o na l ep r o p o s e d f o r d e t a i l , w cc o n c l u d et h e ma sf o l l o w s ： 1 f i r s t l y , ag e n e t i ca l g o r i t h mf o rg l o b a lo p t i m i z a t i o nb a s e d0 1 1u n i f o r md i s t r i b u t i o n e n c o d i n ga n d 趾o r t l a o g o n a lc o m p a c tg e n e t i ca l g o r i t h ma r cp r e s e n t e d t h ef o r m e r a l g o r i t h ma d o p t san o v e le n c o d i n gs t r a t e g y , w h i c he a c hc h r o m o s o m er e p r e s e n t sa m u l t i v a r i a t el l l l l i f o l n ld i s t r i b u t i o nr e g i o ni nt h es e a r e l as p a c e a n dt h ea l g o r i t h ms e a r c h e s t l a es p a c ei nar e g i o n - b y - r e g i o ni n a l m c l , t h u $ t h ec f f i c i e n e yi si m p r o v e d t h ep o p u l a t i o n o ft h eo r t l a o g o n a lc o m p a c tg e n e t i ca l g o r i t h mi sr e p r e s e n t e du s i n gap r o b a b i l i t yv e c t o r a n dt l a cp r o b a b i l i t yy c c t o ri sa l w a y sa d j u s t e dt o w a r dt h ec l i t i s m t h i sa l g o r i t h mu s 鹤 m u c hl e s sm e m o r ya n di sv e r ys i m p l e t h r o g ht l a cn u m e r i c a le x p c l j l n c n l s , w cf i n dt h a t 拙皓t w op r o p o s e da l g o r i t h m sa 把e f f e c t i v ea n dv c r yc f f i e i c m t 2 as e l f - a d a p t i v eg e n e t i ca l g o r i t h mf o rt h ep r o b l e mo fa s s i g n m e n tm o d e lf o r f x u i t f u ld i s e u s s i o i sp r o p o s e d o r t h o g o n a ld e s i g na n dm a t r i xe n c o d i n ga l r l u s e dt o d e s i g nt h ea l g o r i t h m c o m p a r e dt ot h em c t l a o db a s e do ni n l c g e rp r o g r a m m i n g , i ti s s i m p l ea n de a s yt oi m p l e m e n t t h ee f f i c i e n c ya n ds t a b i l i t yo ft h ea l g o r i t h ma s h o wb y t h en u m e r i c a lf e s u l t s 3 p a r t i c l es w a r l l lo p t i m i z a t i o ni ss i m p l e , e f f e c t i v ea n dh a saf e wp a r a m e t e r s ，b u t t h ek e yp a m a r c t c r sa i r eo fi m p o r t a n c 圮t ot h ee f f i c i e n c yo ft h ea l g o r i t h m b a s e do nt h e s t a n d a r dp a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h m , ai l l , wa l g o r i t h mu s i n gu l l i f o r md e s i g n t od e t e r m i n i n gp a r a m e t e r si sp r e s e n t e di nt h i sp a p e r t h ef e a s i b i l i t ya n dh i g he f f i e i c l l e y o ft l a ea l g o r i t h ma r cs h o wb yt h en l l m e r i e a lr e s u l t s k e y w o r c l s ：g l o b a lo p f i m i z a l i o n g e n e 6 c a i g o r l t l a mc o m b i d a t o r i a lo p t i m l z a f i o d p a r t i c l es w a r mo p t i m i z a t i o , , u n i f o r m1 ) e s i g l m 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电予科技大学。本人保证毕业 离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学 校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部 或部分内容，可以允许采用影印、缩印或其他复制手段保存论文。( 保密的论文在 解密后遵守此规定) 本人签名查聋日期鲨魁二2 导师签名； 日期： 丑，! 13 第一章绪论 第一章绪论 本章首先介绍了进化算法的起源和进化算法几个分支，接着讲述了遗 传算法的独有的特点，然后介绍了遗传算法的一些应用领域；最后列出了 本文的内容提要和章节安排 1 1 1 进化算法的背景 1 1 进化算法概述 自然界的生物体在遗传、变异和选择的作用下，不断地从简单到复杂、从低级 向高级进化和发展这种“生存竞争，优胜劣汰，适者生存”的进化规律引起了许多 科学家的兴趣人们发现隐藏在自然选择背后的实质是一种优化的思想1 1 1 自然界中，进化过程的发生需要4 个条件闭：( 1 ) 有能够自我繁殖的实体：( 2 ) 能 够自我繁殖的实体形成一个种群：( 3 ) 种群中的实体之间存在差异：( 4 ) 在环境中的 生存能力的差别与上述差异有关进化计算( e v o l u t i o n a r yc o m p u t a t i o n , e c ) 就是基 于这种思想而发展起来的一种通用问题求解方法它采用简单的编码技术来表示 各种复杂的结构，并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然 选择来指导学习和确定搜索的方向由于它采用种群( 即一组编码表示) 的方式组 织搜索，这使得它可以同时搜索解空间内的多个区城而且用种群组织搜索的方式 使得进化算法特别适合于大规模并行在赋予进化计算自组织、自适应、自学习等 特征的同时，优胜劣汰的自然选择和简单的遗传操作使进化计算具有不受其搜索 空间限制性条件( 如可微、连续、单峰等) 的约束及不需要其它辅助信息( 如导数) 的特点这些特点使得进化计算不仅能获得较高的效率，而且简单、易于操作、通 用性强【1 2 , 3 1 把计算机科学与进化论结合起来的尝试始于5 0 年代末，但由于缺乏一种通用 的编码方案，只能依赖变异而非交叉来产生新的基因结构，因而收效甚微6 0 年代 中期，美 m i c h i g a n 大学的j o h nh o l l a n d 等人提出了位串编码技术这种编码既适于 变异操作，又适于交叉操作，并且强调将交叉作为主要的遗传操作该算法于7 0 年 代中期正式定名为遗传算法 然而进化计算在6 0 - 7 0 年代并未受到普遍重视一是因为当时这些方法本身还 不够成熟：二是因为这些方法需要较多的计算机，而当时的计算机还不够普及而且 计算速度也跟不上要求，因此限制了它们的应用：三是当时基于符号处理的人工智 能方法正处于颠峰时期，人们难以认识到其它方法的有效性和适应性 到了8 0 年代，人们越来越清楚地认识到传统的人工智能方法的局限性，而且随 2 全局优化的进化算法 着计算机速度的提高及并行计算机的普及，进化计算对机器速度的要求己不再是 制约其发展的因索，更由于自身的不断发展及其在一些应用领域内取得的成功，进 化计算表现出良好的应用前景。进化计算在机器学习，过程控制、经济预侧，工程 优化等领域取得的成功，已引起数学、物理学、化学、生物学、计算机科学、社会 科学、经济学和工程应用等领域专家的极大兴趣自九十年代中期以来，世界上许 多国家都掀起了演化计算的研究热潮 目前，进化计算与人工神经网络、模糊系统理论一起己形成一个新的研究方向 一计算智能人工智能已从传统的基于符号处理的符号主义，向以神经网络为代表 的连接主义和以进化计算为代表的进化主义方向发展【4 1 1 1 2 进化算法的分支 较早的进化计算具有四大分支，即遗传算法( g e n e t i ca l g o r i t h m s 。g a s ) ( 由 h o l l a n d 开发1 5 】) 、进化规划( e v o l u t i o n a r yp r o g r a m m i n g ，e p ) ( 由f o g e l 等人开发1 6 j ) 、 进化策略( e v o l u t i o n a r ys a t e g y ，e s ) ( 由r e c h b e d l 和s c h w e f e l 开剔8 】) 和遗传程 序设计( g e n e t i cp r o g r a m m i n g , g p ) ( f l j g o z a 开发9 j ) 虽然这几个分支在算法实现方面 有一些细微的差别，但都是借助于生物演化的思想和原理来解决实际闻题四当然 还存在若干将上述算法的各种特点加以结合而形成的混合算法以上四个进化算 法分支的较新发展水平在m i c h a l e 、】l ，i 院l 加l 和f o g e l 1 1 l 等人的综述里有很好的介绍蚁 群算法( a n tc o l o n ya l g o r i t h m ) 是由意大利学者d 0 r i g o 等人1 1 2 ，1 3 l 于2 0 世纪9 0 年代初期 通过模拟自然界中蚂蚁集体寻径的行为而提出的一种基于种群的启发式仿生进化 系统，也是进还算法的一种在1 9 9 5 年，k e n n e d y 和e b e r h a r t 等1 1 4 ，1 5 】提出了一种新的 演化计算技术一粒子群算法( p a r t i c l es w a r mo p t i m i z a t i o n , 简称p s o ) 在本文，我们着 重讨论研究遗传算法和粒子群算法 1 2 遗传算法的特点 与传统的优化算法相比，遗传算法主要有以下几个不同之处： ( 1 ) 遗传算法不是直接作用在参变量集上，而是利用参变量集的某种编码： ( 2 ) 遗传算法不是从单个点，而是从一个点的种群开始进行搜索： ( 3 ) 遗传算法利用适应值的信息，无需导数或者其他辅助信息，当然，如果条件 允许，也可以设计利用导数或者其他辅助信息的混合遗传算法： ( 4 ) 遗传算法利用概率转移规则，而非确定性规则 遗传算法和传统的优化算法相比较，优越性主要表现在：首先，它在搜索过程 中不容易陷入局部最优，即使在所定义的适应值函数不是连续的，非规则的或者有 噪声的情况下，它也能以很大的概率找到整体最优解：其次，由于它固有的并行性， 第一章绪论 3 遗传算法非常适用于大规模并行计算机 一、全局优化 对于实际工程和科学中的许多问题。找到一个最优解的唯一可靠的方法就是 穷举法，即搜索问题的整个参变量空间然而在很多情况下，由于参变量空间太大， 以致在限定的时间内只能搜索其中极小的一部分空间一个常用的算法就是爬山 法：从某随机点出发，在选定的方向上做微小的变动，若得到更优的解，则在这个方 向上继续迭代，否则转到相反的方向上这种爬山方法在某些情况下可以得到理想 的解但是，复杂的问题在搜索空间中会出现许多峰值，加上维数的增加导致拓扑 结构的更加复杂，这时就很难再用这种方法找到最优解 遗传算法采用独特的方式，在参变量空间中进行种群搜索，由串组成的种群在 遗传算予的作用下，同时对空间中不同的区域进行采样计算，从而构成一个不断进 化的种群遗传算法的一个突出的能力就是能把注意力集中在搜索空间中期望值 最高的部分，这是遗传算法中杂交算予作用的直接结果，也正是遗传算法的杂交算 子，使得全局搜索能力与传统方法相比较有很大的优越性 为了避免陷入局部最优，在遗传算法中还引入了变异算子一方面可以帮助当 前解在附近找到更好的解，另一方面还可以保持种群的多样性，确保进化能够继续 进行 对种群进行简单的复制，杂交和变异作用是遗传算法的精髓通过保持在解空 间不同区域中的多个点的搜索，遗传算法能以很大的概率找到全局最优解 二、并行性 遗传算法按并行方式搜索一个种群数目的点，而不是单点遗传算法的并行性 表现在两个方面一方面，遗传算法是内在并行的( i n h e r e n tp a r a l l e l i s m ) ，即遗传算 法本身非常适合大规模并行最简单的并行方式是让若干台计算机各自进行独立 种群的演化计算，运行过程中可以进行或不进行通信( 独立的种群之间若有少量的 通信一般会带来更好的结果) ，等到运算结束时进行比较，选取最佳个体这种并行 方式对并行系统结构没有什么限制和要求，可以说，遗传算法适合在目前所有的并 行机或分布式系统上进行并行处理，而且对并行效率没有太大的影响另一方面， 遗传算法具有隐含并行性( i m p l i c i tp a r a l l e l i s m ) 由于遗传算法采用种群的方式组织 搜索。因而可同时搜索解空间的多个区域，并相互交流信息使用这种搜索方式，虽 然每次只执行与种群规模成比例的计算，但实质上已进行了大约o ( n 3 ) 次有效 搜索，这就使得遗传算法能以较少的计算获得较大的收益 1 3 遗传算法的主要应用领域 遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的 4 全局优化的进化算法 具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多学科遗传算法的 主要应用领域有【”i ： ( 1 ) 函数优化函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能 评价的常用算例很多人构造了各种各样的复杂形式的测试函数，人们用这些几何 特性各异的函数来评价遗传算法的性能对于一些非线性、多模型、多目标的函数 优化问题，用其它优化方法较难求解，而遗传算法却可以方便地得到较好的结果 ( 2 ) 组合优化随着问题规模的扩大，组合优化问题的搜索空间急剧扩大，有时 在目前的计算机上用枚举法很难甚至不可能得到其精确最优解对于这类复杂问 题，人们已意识到应把精力放在寻求其满意解上，而遗传算法正是寻求这种满意解 的最佳工具之一实践证明，遗传算法对于组合优化中的n p 完全问题非常有效 ( 3 ) 生产调度问题生产调度问题在许多情况下所建立起来的数学模型难以精 确求解，即使经过一些简化之后可以求解，也会因简化太多而使得求解结果与实际 相差甚远遗传算法是解决复杂调度问题的有效工具，在单件生产车间调度、流水 线生产车间调度、生产规划、任务分配等方面遗传算法都得到有效的应用 ( 4 ) 自动控制在自动控制领域中有许多与优化相关的问题，遗传算法在解决这 些问题时显示了良好的效果如利用遗传算法进行航空控制系统的优化、基于遗传 算法的模糊控制器优化设计、利用遗传算法进行人工神经网络的结构优化设计和 权值学习等 ( 5 ) 机器人智能控制。枫器人是一类复杂的难以精确建模的人工系统，遗传算法 在机器人智能控制如移动机器人路径规划、关节机器人运动轨迹规划、机器人逆 运动学求解、细胞机器人的结构优化和行动协调等方面得到研究和应用 ( 6 ) 图像处理和模式识别遗传算法可用于图象处理中的优化计算方面，如图像 恢复、图像边缘特征提取、几何形状识别等 ( 7 ) 人工生命自组织能力和自适应能力是人工生命的两大主要特征，基于遗传 算法的进化模型是研究人工生命现象的重要理论基础可以预见，遗传算法在人工 生命及复杂自适应系统的模拟与设计、复杂系统突现性理论研究中，将得到更深的 发展 ( 8 ) 遗传程序设计遗传程序设计的主要思想是使用某种编码方法，对某种结构 进行遗传操作以自动生成计算机程序虽然遗传程序设计的理论尚未成熟，但它己 经有一些成功的应用 ( 9 ) 机器学习学习能力是高级自适应系统所应具备的能力之一，基于遗传算法 的机器学习。特别是分类器系统，在许多领域得到了应用例如。基于遗传算法的机 器学习可用于调整人工神经网络的连接权，也可用于神经网络结构的优化设计 第一章绪论 1 4 本文主要工作 5 本文是作者攻读硕士学位期间在刘三阳教授的指导下完成的部分工作，主要 是关于全局优化的遗传算法和粒子群算法具体内容如下： 1 第二章主要给出了经典遗传算法的一些基本概念，基本设计方法和数学理 论等 2 第三章提出了两种改进的全局优化遗传算法以及遗传算法在组合优化中的 一个实际应用通过改变一般遗传算法的编码方式。将染色体编码为一个多元均匀 分布区域，算法能够发现离当前点较远的潜在好解，从而提高了搜索效率加快了收 敛速度：在紧致遗传算法的基础上增加精英策略和正交杂交算子，使得正交紧致遗 传算法在全局优化中使用很少的存储空间和具有更高的效率为多次分组会议的 最佳安排方案问题建立一个新的数学模型，并设计了相应的自适应遗传算法，该算 法采用矩阵编码，应用正交设计设计杂交算子 3 第四章首先介绍了粒子群算法的基本步骤和基本原理，然后在标准粒子群 算法基础上，针对当前大部分粒子群算法在关键参数设置上的局限性，利用均匀设 计方法对粒子群算法做了改进，不但保证了算法求解效率和可行性，也优化了关键 参数的取值 第二章遗传算法基础知识 第二章遗传算法基础知识 本章介绍了遗传算法一些基本术语，经典遗传算法的基本框架和 设计方法；然后讲述了经典遗传算法的数学理论：模式定理和积木块假 设以及隐合并行性 2 1 遗传算法的一些基本概念和术语及框架 2 1 1 遗传算法的基本思想 7 遗传算法是一种迭代算法，它从某一随机产生的或是特定的初始解集出发，按 照一定的操作规则，如选择、复制、交叉、变异等，不断地迭代计算以得到新一代 解集，并根据个体的适应值，按照适者生存和优胜劣汰的原则，引导搜索过程向“最 适应环境”的个体( 最优解) 逼近，逐代演化出越来越好的近似解，最终收敛到问题 的最优解或满意解 2 1 2 遗传算法的基本术语 进化代( g e n e r a t i o n ) 算法的迭代步称为进化代，或代 种群( p o p u l a t i o n ) 所求解问题的多个解的集合称为种群，或称种群、解群等常记为即) ，f 表示 其代数最初的种群即p ( o ) 一般是从问题可能潜在的解的集合中随机生成的 个体( i n d i v i d u a l ) 组成种群的每一个解称为一个个体常记为工，0 ) ，x ：( f ) ，等 种群规模( p o p u l a t i o ns i z e ) 种群内个体的数目称为种群规模，常记为p o p s i z e 一般来说，种群规模在整个 进化过程中是不变的 编码( c o d i n g ) 在使用遗传算法解决问题之前，需要将问题的解进行编码，即将问题的解通过 变换映射到基因空间，也即遗传算法的搜索空间基因空间中的点通常是字符串的 形式，最简单的是用 0 m 定义的二进制串编码问题也是遗传算法使用中的关键问 题 解码( d e c o d i n g ) 编码的逆过程末代种群中的最优个体经过解码得到的解可以作为问题的近似 最优解 8 全局优化的进化算法 染色体( c h r o m o s o m e l 经过编码后得到的代表问题的解的串称为染色体每个个体实际上是染色体 带有特征的实体 基因( g e n e ) 染色体的每一位称为基因 基因座o o c u s 、 基因所在染色体中的位置称为基因座 等位基因( a l l e l e l 同一基因座可能有的全部基因称为等位基因 基因型( g e n o t y p e ) 染色体的内部表现即基因组合的模型称为基因型，或称遗传予型 表现型( p h e n o t y p e ) 个体的外部表现即表现型染色体作为遗传物质的主要载体，其基因型决定了 个体的表现型编码即为从表现型到基因型的映射 适应值( f i t n e s s ) 个体适应环境的程度( 与最优解接近的程度) 称为适应值适应值较高的个体 将获得更多的繁殖机会 选择( s e l e c t i o n ) 指以一定的概率从种群中选择若干个体的操作一般而言选择的过程是一种 基于适应值的优胜劣汰的过程 父代( p a r e n t ) 及子代( o f f s p r i n g ) 根据某种规则来产生其下一代个体的个体称为其下一代个体的父代，产生出 的下一代个体称为它的子代 复制( r e p r o d u c t i o n ) 指从种群中选择若干个体直接插入到新一代种群中去的操作 交叉( 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 ) 指染色体的一位或者多位基因发生某种改变，从而产生出新的染色体的过程 遗传算子( g e n e t i co p e r a t o r s ) 即遗传操作，包括复制、交叉、变异和选择等 2 1 3 遗传算法基本框架 在准备应用遗传算法求解问题时，要完成以下四个主要步骤： 第二章遗传算法基础知识 9 ( 1 ) 确定表示方案( 可行解的编码方式) ： ( 2 ) 确定适应值的度量( 适应值函数的定义) ： ( 3 ) 确定控制算法的参数和变量： ( 4 ) 确定指定结果的方法和停止运行的准则 在常规的遗传算法中，表示方案是把问题的搜索空间中的每个可能的点即可 行解表示为确定长度的特征串表示方案的确定需要选择串长f 和字母规模k 二进 制串是遗传算法中最初时常用的方法在染色体串和问题的搜索空间中的点之间 选择映射有时容易实现，有时又非常困难选择一个便于遗传算法求解问题的编码 方式经常需要对问题有很深入的了解 遗传算法过程如下： b e g i n t4 - - 0 初始化p q ) 评价p o ) w h u 2 一- 1 1 暑e 1 求编码长度n ：2 一1 o ( 2 2 ) 【u 其中c 。可以取为输入参数，当前代中或者最近形代中g 的最小值的绝对值。 通常情况下，仅仅用上述的方法将目标函数值转化为适应值函数还是不够的 在进化的初期，可能会出现一些超级个体( 适应值很大的个体) ，这些个体的竞争力 很强，在若干代后将充满种群，然而它们并不是最优解，从而导致算法早熟收敛：在 进化后期，种群中的个体之间的可能差异很小，从而不利于优秀的个体进入下一代， 导致算法收敛很慢针对上面的两种情况，我们可以对适应值函数比例变换，变换 的方法有很多，在此不详细介绍，参见文献【2 3 】 2 2 4 遗传算子 在遗传算法中，遗传算子主要包括：选择算子，杂交算子和变异算子 ( 1 ) 选择算子 遗传算法的原理从本质上来说基于达尔文的自然选择学说选择算子提供了 遗传算法的驱动力如果驱动力太大，遗传搜索将过早地终止：如果驱动力太小，进 化过程将慢的难于接受通常需要在遗传搜索的早期采用较小的选择压力( 用来对 空间进行广度搜索) ，而在晚期则采用较大的选择压力( 用来限制搜索空间) 选择 1 4 全局优化的进化算法 算子将遗传搜索引导到搜索空间中有前途的区域中在过去的2 0 年中提出，验证并 比较了许多选择方式，通常采用的选择算子如下： 轮盘赌选择( r o u l e t t ew h e e ls e l e c t i o n ) ( p + a ) 选择( ( + a ) s e l e c t i o n ) 竞争选择( t o u r n a m e n ts d e c t i o n ) 稳态复制( s t e a d y s t a t er e p r o d u c t i o n ) 排序与比例变换 共享( s h a r i n g ) 这些选择算子的介绍可以参阅文献【2 0 】，这里不一一详述 ( 2 ) 杂交算子 交叉基因重组将两个父代个体的部分结构加以替换重组而生成新个体( 子个 体) 其目的是在下一代获得新优良个体，提高遗传算法的搜索能力而事实上，杂 交算子也正是遗传算法区别与其他进化算法的重要标志对于不同的编码方式，其 杂交算子的设计有所不同下面以经典遗传算法的一个杂交算子为例 二进制编码的交叉算子包括点式交叉( p o i n t a ll i o s $ o v c i ) 和均匀交( u n i f o r m c r o s s o v e r ) 等点式交叉分为单点交叉和多点交又，是在两个父代个体上随机产生一 个或多个交叉点，在间断交换两个父代个体的对应片段，从而得到两个子代个体 如： 父代个体1 0 1 1 1 0 0 1 1 1 父代个体2 1 0 1 1 0 1 0 0 0 交叉点的位置为4 ，则： 子代个体10 1 1 1 0 1 0 0 0 子代个体21 0 1 1 0 0 1 1 1 对于实数编码的遗传算法，也有许多常用的杂交算子i t 6 | ：算术杂交，混合杂交 单峰正态分布杂交等等而对于组合优化问题的遗传算法杂交算子的设计也有很 多，具体的算予需要根据问题的实际情况设计 ( 3 ) 变异算子 变异是遗传算法中保持种群多样性的一个重要途径它以一定概率选择某一 基因座，通过改变该基因座基因的值来获取新个体在二进制编码中，常常采用单 点的变异算子如： 变异前0 1 1 0 0 0 1 1 1 变异为随机选择为4 ，则变异所得的个体为：0 1 1 1 0 0 1 1 1 一般来说，不同的编码方式有不同的变异算子，不同的问题有不同的变异算 子例如实编码遗传算法有高斯变异算子和非均匀变异算子等 第二章遗传算法基础知识 2 2 d 遗传算法参数控制 c g a 的参数包括种群规模p o p s i z e ，染色体长度f 。最大进化代数m a x g e n 交叉 概率p 。和变异概率以等，这些参数对遗传算法的性能都有很重要的影响 选择较大数目的初始种群可以同时处理更多的解。因而容易找到全局最优解， 其代价是增加了每次迭代的时间，一般来说，问题的规模越大种群规模越大，问题 难度越大，种群规模越大交叉概率的选择决定了交叉操作的频率，频率越高，可以 越快收敛到最有希望的最优解区域，因此一般选取较大的交叉概率，但太高的交叉 概率也可能导致早熟现象变异概率的选取受种群大小，染色体长度等因素影响， 若选取较高的变异概率，可增加样本模式的多样性，但可能引起不稳定，通常取很 小的值染色体长度主要决定于问题求解精度的要求和问题的维数，精度越高，染 色体长度越长，维数越大，染色体长度越长最大进化代数作为一种模拟终止条件， 一般视具体问题而定针对于不同的具体问题确定最优参数是一个极其复杂的优 化问题，通常是根据经验取定参数值g r e f e n s t e t e ( 1 9 8 6 ) 将g a 的参数选取作为一个 优化问题，提出用g a 优化g a 参数的二级演化方法( m e t a e a ) 由于此法计算量过大， 且二级算法本身参数也有待优化，因此应用得很少洲 2 3 经典遗传算法的数学理论 2 3 1 模式定理( s c h e m am 咖) 1 、模式的定义 模式( s c h e m a ) 是一个描述字符串集的模板，该字符串集中的串的某些位置上 存在相似性，因此也可解释为相同的构形，它描述的是一个串的子集 定义2 3 1 ：在一个由 0 工 中字符构成的字符串中，字符木叫做通配符，它即可 以表示o ，也可以表示l ，因此它是不确定字符，而0 ，l 是确定字符 定义2 3 2 ：基于三个字符集 o 工 的字符串称为模式，其中符号“木”代表任 意字符，l l p o 或1 ，用日表示 例如，模式1 料0 描述四个字符的字符集0 0 0 0 , 1 0 1 0 1 1 0 0 , 1 1 1 0 对于二进制编码 串。当串长为z 时，共有2 个不同模式遗传算法串的运算实质为模式运算 2 、模式阶( s c h e m ao r d e r ) 和定义距( d e f i n i n gl e n g t h ) 定义2 3 3 ：模式日中确定字符的个数称为h 的模式阶( s c h e m ao r d e r ) ，记为 d ( h ) 例如0 0 0 ”1 0 ) 一4 模式阶用来反映不同模式间确定性差异，模式阶数越高，模式确定性越高，所 匹配的样本个数就越少 定义2 3 4 ：模式h 中第一个确定字符和最后一个确定字符之间的距离称为 1 6 全局优化的进化算法 定义距( d e f m i n g l e n g t h ) ，记作6 ( ) 例如6 ( 1 0 1 + 0 0 + 1 ) = 7 ，6 ( 1 ”+ ) 一0 3 、模式在遗传操作下的变化 令p ( f ) 表示第f 代中串的种群，以只( f 一1 ，2 ，m ) 表示一代中第i 个个体串 ( 1 ) 选择操作对模式的作用 假设在第t 代，种群p ( f ) 中模式h 所能配的样本数为研，记作m ( h ，f ) ，一代中 种群大小( 种群中个体的总数) 为n ，且个体两两互不相同，由于一个串是以概率 蚴。器断龆眠舯脚骱戢( f ) 脆艄，删馘脏射“ 代中的样本数为册( 日，t + 1 ) ： 帆1 ) 一盟铲 ( 2 3 ) 其中f ( h ，f ) 是模式h 所有样本的平均适应值，令种群平均适应值为于( f ) ，其中 于( f ) 。耻n ，贿： 小饵，1 ) 型丝业! ( 2 4 ) f - f t ) 现在假设模式h 的平均适应值一直等于种群平均适应值，且设高出部分c 于( f ) ，c 为 常数，则有： m ，f + 1 ) - 业丝笪幽i 肌饵，f + c ) ( 2 5 ) ，西) 假设t 一0 开始，c 保持为常值，则有：m ( 皿t + 1 ) 一m ( h ，0 ) ( 1 + c ) 可见，在选择算子作用下，平均适应值高于种群平均适应值的模式将呈指数级 增长，而平均适应值低于种群平均适应值模式将呈指数级减少 ( 2 ) 交叉操作对模式的作用 为了说明这一点可有如下示例，采用的是单点交叉情形： 彳一0 1 0 0 0 1 1 b 一1 1 1 0 0 1 0 有模式：h 一1 o ”假设杂交概率为以，模式不被破坏的概率p 苫1 - 导p 。 o 更一般地，对于任意的模式日可以计算出杂交后生存的概率p 。的下界由于当 杂交位置落在定义距长度之外时，这个模式可以生存在单点交叉情形下，日的生 存概率为，苫1 - 警掣，其中f 是染色体的长度一旦在定义长度之内的位置从 一1 ( f n 个可能的位置中被选取，则模式极易被破坏而杂交本身也是以一定的概率 以发生的，所以模式日生存的概率为： 第二章遗传算法基础知识 1 7 p ，小号半 ( 2 6 ) ( 3 ) 变异操作对模式的作用 假定串的某一位置发生改变的概率为p 。，模式h 在变异算子作用下，若要不 受破坏，则其中所有的确定位置( 为“0 ”或“1 ”的位) 必须保持不变因此模式日保 持不变概率为( 1 一以) d 假) 其中o ( h ) 为模式h 的阶数当以“1 时，模式h 在变 异算子作用下的生存概率为： p ，( 1 一p ) 。饵 ( 2 7 ) 对于很小的变异概率p 。( p 。t c 1 ) ，模式的存活概率可以近似等于l o ( h 汩。 综合( 2 5 ) ，( 2 6 ) ，( 2 7 ) 则有： 历伽册晰掣【1 _ p 。罟卅川( 2 8 ) ，( f ) 其中忽略了极小项 4 、模式定理 由式( 2 8 ) ，可以得到下面模式定理： 定理2 3 ：模式定理( s c h e m a t h e o r e m ) ：在简单遗传算子中，在选择，交叉和变异 的作用下，具有低阶，短定义距以及平均适应值高于种群平均适应值的模式在子代 中将得以指数级增长 证明：设上幽，c ，1 ，6 假) ，d ( 日) 都很小 ，- f ) 则p 。等等c t l p 。( 日) t t l 一般存在| | ，1 使得： 掣。篱- p = o ( 日黼，- ，( f ) 1 m ( h ，t + 1 ) 乏m ( 日，f ) k m ( h ，o ) k 证毕 模式定理保证了较优的模式( 遗传算法的较优解) 的样本数呈指数级增长，从 而给出了遗传算法的理论基础，其定义是深远的 2 3 2 积木块假设 具有低阶，短定义距及高适应值的模式称作积木块( b u i l d i n gb l o c k ) 正如搭积木一样，这些“好”的模式在遗传操作中，相互拼搭，结合产生适应值 更高的串，从而找到更优的可行解，这正是积木块假设所揭示的内容 积木块假设( b u i l d i n gb l o c kh y p o t h e s i s ) ：低阶，短距，高平均适应值的模式( 积 1 8 全局优化的进化算法 木块) 在遗传算子作用下，相互结合，能生成高阶，长距，高平均适应值模式，可最终 生成全局最优解 积木块假设则指出，遗传算法具备寻找到全局最优解的能力，即积木块在遗传 算子作用下，能生成高阶，长距，高平均适应值的模式，最终生成全局最优解或近似 最优解遗憾的是上述结论没有得到证明，所以称之为假设，但很多实践支持积木 块假设，在许多领域内应用都取得成功 2 3 3 隐并行性( i m p l i c tp a r a l l e l i s m ) 定理2 4 ( 隐并行性定理，i m p l i c i tp a r a l l e l i s mt h e o r e m ) 2 3 l ：设为一小正数， f ，f ( f 一1 ) + 1 ，一2 胆，贝i | c g a - - 次处理的存活概率不小于1 一且定义长度不大 于z 。的模式数为d ( 3 ) 证明见文献【2 5 】 这个关于有效模式处理数目估计非常重要，h o l l a n d 称之为遗传算法的并行性 它表明，每一代中除了仅对t g 个串的处理外，遗传算法实际上处理了大约d 伽3 ) 个 模式，从而每代只执行与种群规模成比例的计算数量，就可以同时收到并行地对大 约o ( n 3 1 个模式进行有效处理的目的，并且无须额外的存储 从上面的分析我们可以看到。在遗传算法的迭代过程中，除了定义距长度长的， 高阶模式，被变异和杂交算子破坏之外，遗传算法在处理相对数量较少的串的同时， 还内在地处理大量的模式 第三章全局优化遗传算法的改进 第三章全局优化遗传算法的改进 本文主要给出了两个改进的全局优化遗传算法及遗传算法在组合优化 中的一个应用改进的全局优化的遗传算法能在较少的计算代价下找到一 个相对精确的近似解，在求解大规模问题时也具有一定的优势 3 1 1 引言 3 1 基于均匀分布编码的全局优化遗传算法 全局优化( g l o b a lo p t i m i z a t i o n s ) 采用在感兴趣的区域内可以区分全局最优和众 多局部最优的方法全局优化问题通常是具有无约束优化的形式，即问题除了一个 最小或者最大函数之外没有其他限制1 2 0 1 一般来说，无约束优化问题可以在数学上 描述为 z r l ： m i l l ，0 ) ( 3 1 ) 其中厂0 ) 是实值函数，可行集合。是彤的子集可行集q r 4 代表了完全无 约束的情况在许多实际应用问题中，我们仅仅需要考虑q 是r “特定的子集的情况 如果存在，0 ，对于所满足属于。且与工的距离小于f 的x ，都有，0 ) 芑f ( x ) ， 则点善称作，0 ) 在q 上的局部最优解如果对于所有的x e f l 都有，o ) f ( x ) ， 则点z 称做厂o ) 在q 上的全局最优解尽管大多数实际优化问题有需要满足边界 约束，对于无约束优化问题方法的研究为进一步研究打下了基础 传统的优化算法可以粗略地分为两类：( 1 ) 确定性方法，( 2 ) 随机性方法团1 遗 传算法在那些对于传统爬山法和基于导数