（运筹学与控制论专业论文）求解弧路径问题的遗传算法研究.pdf

中文摘要 车辆弧路径问题产生于现实生活中的交通运输服务系统，有着广泛的 应用，近年来逐渐成为研究的热点。由于它是n p 一难问题，精确算法的求 解时间呈指数增长，因此无法处理大规模的问题，而现有的启发式算法虽 然求解时间较短，但往往存在解质量效率低下的缺点。随着遗传算法的发 展，它已被应用到这一问题的求解。已有结果表明，遗传算法可以很好地 兼顾运算效率和解质量效率这两方面的要求，在解决车辆弧路径问题上具 有很好的发展前途。 本文在广泛深入地查阅国内外文献的基础上，对遗传算法的基础理论 和方法进行了深入的理论研究，并应用遗传算法对车辆弧路径问题进行了 实验分析，主要内容如下： 1 系统、详尽的介绍了遗传算法的一般流程和基本理论、方法。 2 简要介绍了弧路径问题及其起源和发展历史，归纳总结了其求解方 法。在现有的算法基础上，提出了一种新的遗传算法来解决以车辆服务成 本为目标的弧路径问题。新算法采用了改进的局部搜索技术，并对现有算 法的其他部件做了一些调整。通过对多个实例的计算证明了该算法对大多 数问题具有更好的效果。 关键词：遗传算法弧路径问题m e m e t i c 算法局部搜索 a b s t r a c t d e r i v e df r o mt h et r a n s p o r t a t i o ns e r v i c es y s t e mi n r e a ll i f e ，a r cr o u t i n g p r o b l e mh a v ef o u n di t sa p p l i c a t i o ni nm a n yf i e l d s ，a n di s n o wb e c o m i n gt h e f o c u so fm a n yr e l e v a n ts t u d i e s s i n c ei ti san p - h a r dp r o b l e m , t h et i m ee x a c t a l g o t i t h mn e e d si ns o l v i n g i tu s u a l l yi n c r e a s e se x p o n e n t i a l l y t h u si ti si n c a p a b l e o fd e a l i n gw i t hm a s s i v ep r o b l e m s i nc o m p a r i s o nw i t he x a c ta l g o t i t h m ，t h e h e u r i s t i ca l g o r i t h mm a yt a k e sl e s st i m e ，h o w e v e r , i ti sa l s od e f i c i e n ti nt e r m so f t h ee f f i c i e n c ya n dq u a l i t yo ft h es o l u t i o n w i t ht h ed e v e l o p m e n to fg e n e t i c a l g o r i t h m s ，i th a sa l r e a d yb e e na p p l i e dt ot h es o l u t i o no fs u c hap r o b l e m g e n e t i ca l g o r i t h m st u r n e do u tt ob ea ne f f e c t i v es t r a t e g yw i t hf u l lc o n s i d e r a t i o n t ob o t ht h ee f f i c i e n c yo fc o m p u t a t i o na n dt h eq u a l i t yo fs o l u t i o n a n dt h e r e w o u l db eg r e a tp r o s p e c tf o rg e n e t i ca l g o r i t h m si ng i v i n gs o l u t i o n st oa r c r o u t i n gp r o b l e m b a s e do ne x t e n s i v ea n dt h o r o u g hr e a d i n go ft h el i t e r a t u r eb o t ha th o m ea n d a b r o a d ，t h i st h e s i sm a k e sa ni n - d e p t ht h e o r e t i c a ls t u d yo nt h ef u n d a m e n t a l t h e o r i e sa n dm e t h o d so fg e n e t i ca l g o r i t h m sa n dd o e sa ne x p e r i m e n t a la n a l y s i s o ft h ea p p l i c a t i o no fg e n e t i ca l g o r i t h m si ns o l v i n ga r cr o u t i n gp r o b l e m t h eg i s t i sa sf o l l o w s ： 1 as y s t e m a t i ca n dd e t a i l e di n t r o d u c t i o no ft h eg e n e r a lp r o c e d u r e ， f u n d a m e n t a lt h e o r i e sa n dm e t h o d so fg e n e t i ca l g o r i t h m s 。 2 ab r i e fi n t r o d u c t i o no ft h eo r i g i na n dh i s t o r yo fe v o l u t i o no fa r cr o u t i n g p r o b l e m as u m m a r i z a t i o no f t h es o l u t i o no ft h i sp r o b l e mw i l la l s ob ep r e s e n t e d a i m i n ga tl o w e r i n gt h ec o s to fc a rs e r v i c e ，t h et h e s i sw i l lt h e np u tf o r w a r da n e wg e n e t i ca l g o r i t h m st ot a c k l ea l er o u t i n gp r o b l e m t h en e wa l g o r i t h mn o t o n l ya d o p t e dt h ei m p r o v e dl o c a ls e a r c ht e c h n i q u e ，b u tm a d es o m ea d j u s t m e n t s t os o m eo t h e rs e c t i o n so ft h ec u r r e n ta l g o r i t h m f i n a l l y , t h ec o m p u t a t i o no f m a n ye x a m p l e sw i l lp r o v et h ee f f e c t i v e n e s so ft h i sa l g o r i t h mi ns o l v i n gm o s to f t h er e l e v a n tp r o b l e m s k e yw o r d s ：g e n e t i ca l g o r i t h m s m e m e t i ca l g o t i t h m a r cr o u t i n gp r o b l e m l o c a ls e a r c h 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得鑫鲞盘堂或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名孝s 付民签字日期：卵莎年厂月夕日 学位论文版权使用授权书 本学位论文作者完全了解苤鲞盘堂有关保留、使用学位论文的规定。 特授权叁盗盘鲎可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：蕞- 砷民 签字日期：川年月夕日 导师签名：每胡 签字日期：髟年月弓日 第一章绪论 第一章绪论 1 1 遗传算法的理论与应用简介 遗传算法( g e n e t i ca l g o r i t h m , g a s ) 是模拟生物在自然环境中的遗传和进化过 程而形成的一种自适应全局搜索算法。它最早是由美国m i c h i g a n 大学的h o l l a n d 教授提出，起源于6 0 年代对自然和人工自适应系统的研究【l 】。h o l l a n d 创建的遗 传算法是利用某种编码技术作用于称为染色体的二进制数串，其基本思想是由模 拟的这些串组成的群体的进化过程。遗传算法通过有组织但是随机的交换来重新 组合那些适应性好的串，在每一代中，利用上一代串结构中适应性好的位和段来 产生一个新的串的群体；作为额外添加，偶尔也要在串结构中尝试用新的位和段 来替换原来的部分。它可以利用已有的信息来搜索那些有希望改善解质量的串。 遗传算法通过作用于染色体上的基因，寻求好的染色体来求解问题。与自 然界相似，遗传算法对求解问题的本身一无所知，它需要的仅是对算法所产生的 每个染色体进行评价，并基于适应值来选择染色体，使适应值好的染色体比适应 值差的染色体有更多的繁殖机会。遗传算法通过模拟达尔文“优胜劣汰、适者生 存”的原理及利好的结构；通过模拟孟德尔遗传变异理论在迭代过程中保持已有 的结构，同时寻找更好的结构。 7 0 年代d e j o n g 基于遗传算法的思想在计算机上进行了大量的纯数值函数 优化计算实验【2 】。在一系列研究工作的基础上，8 0 年代由g o l d b e r g 进行归纳总 结，形成了遗传算法的基础框架【3 】o 由于内在的的自学习性、并行性、稳定性等强大优点，遗传算法在包括数 值优化、组合优化、自动控制、模式识别和人工生命等众多的领域得到了广泛的 应用，并显示出了强大的能力。 1 2 弧路径问题及其发展概要 弧路径问题是一类特殊的车辆路径问题( v r p , v e h i c l er o u t i n gp r o b l e m ) 。车 辆路径问题是经典的组合优化问题，其基本内容为：对于给定的交通网络，为一 第一章绪论 个车队中的车辆确定行驶路径来完成某种服务，并达到某种目标的最优化。这里 的目标包括最小化车队总的行驶路程，最小化总的服务时间等。事实上，在具体 实践中存在两种基本的车辆路径问题，即顶点路径( n o d er o u t i n g ) 和本文涉及的 弧路径( a r cr o u t i n g ) 问题。对前者，车辆的服务对象分布在网络的顶点上，而后 者的服务对象则是网络的整条边或弧。顶点路径问题通常被用来描述出现在供应 链系统中使用运输车队完成货物的交货和或提货业务的模型，业已得到了很广 泛的研究【4 】。与此相反，弧路径自从正式提出以来嘲，尽管也有非常重要的应用 背景和价值，但是并没有立即得到非常广泛的研究。 在弧路径问题中，当假定车辆的容量无限且网络中的每条边都需要服务时， 就得到了著名的“中国邮递员问题”( c p p , c h i n e s ep o s t m a np r o b l e m ) 6 7 】，该问题存 在多项式算法。当网络中只有部分边需要服务时，就得到“乡村邮递员”( 1 冲p ， r u r a lp o s t m a np r o b l e m ) 问题，它已是n p 一难问题【6 ，7 】。进一步，当考虑更为现实 的约束条件，亦即车辆的容量为有限时，就得到了所谓的容量约束弧路径问题 ( c a r p , c a p a c i t a t e da r cr o u t i n gp r o b l e m ) 。由于它以r p p 为特例，因此它也是n p 难的。 c a r p 广泛存在于市政管理和服务系统中，其典型的应用例子除了冬季交 通道路维护外，常见的还有用车队进行市政垃圾和工业废物回收，交通道路的清 扫和洒水，邮政投寄邮件掣5 。 由于c 址冲的应用领域和问题多与人们的日常生活息息相关，无时无刻不 在，因此对它进行的研究，并提供有效的解法，具有重要的经济价值和社会意义， 可以为市政管理部门提高管理决策水平，进一步提高服务质量提供帮助。因此， 近年来，c a r p 的研究逐渐成为热点。2 0 0 0 年第一本相关专著出版 7 1 ，同时大量 相关论文在各种国际杂志上发表。最近“c o m p u t e r sa n do p e r a t i o n sr e s e a r c h ”杂志 还专门对c a r p 问题作了专刊来报道最新研究进展【8 】。 1 3 本文所做的工作及安排 本文针对m e m e t i c 算法求解车辆弧路径问题，对现有的变异算子进行了改进， 在此基础上设计了求解e c a r p 问题的遗传算法。用文献中的算例进行了数值试 验，并与文献中的结果进行比较，试验结果表明我们所提出的算法是有效的。 2 第一章绪论 论文的第二章介绍了遗传算法的发展和基本概念，展示了算法的基本操作流 程并介绍了几种常见的遗传算法。 论文的第三章介绍了弧路径问题的起源和研究情况，给出了对弧路径问题的 一种最新的有效的m e m e t i c 算法( m ) ，并提出了对该算法的一点改进。通过对 多个实例的计算证明了经过改进的m a 算法的有效性和高效率性。 第二章 遗传算法简介 第二章遗传算法简介 电子计算机问世以来，生物模拟便构成了计算机科学的一个组成部分。其目 的之一便是从研究生物系统出发，探索产生基本认知行为的微观机理，然后设计 具有生物智能的机器或模拟系统以解决复杂问题。如遗传算法、神经网络和细胞 自动机等都是从不同角度模拟生物系统而发展起来的研究方向。 遗传算法( g e n e t i ca l g o r i t h m , g a s ) 是一种模拟自然界生物进化过程的全局随 机搜索算法，由美国m i c h i g a n 大学的h o l l a n d 教授于6 0 年代首先提出。它将计 算机科学与进化论的思想结合起来，依据达尔文“优胜劣汰，适者生存”的原则， 通过模拟自然界中生物群体由低级到高级，由简单到复杂的生物进化过程，最终 逐渐逼近问题的最优解或准最优解。遗传算法作为一种有效的全局搜索方法，因 具有较好的普遍适用性和易扩充性；基本思想简单，便于具体使用；具有很高的并 行性等优点而得到广泛的应用，并产生了大量的成功案例。 2 1 遗传算法的产生与发展 早在2 0 世纪5 0 年代和6 0 年代，几个科学家进行的“人工进化系统”的研究， 就形成了遗传算法的雏形。其中包括“适者生存”的仿自然法则，自然选择和变异 操作的加入，基于群体的设计方案生物染色体编码的抽象处理等e 1 0 。 6 0 年代初期，柏林工业大学的i n g or e c h e n b e r g 和h a n s p a u ls c h w e f e l 等人 在进行风洞实验时，利用生物变异的思想来随机改变参数值，获得了较好的结果。 他们对这种方法进行深入研究，逐渐形成了进化计算的一个分支进化策略 ”( e s ) 。 也是在2 0 世纪6 0 年代，f o g e l 等人在设计有限状态自动机( f s m ) 时提出 ，了进化规划( e p ) ，他们借用进化的思想对一组f s m 进行进化，获得了较好的 f s m 。他们后来将此方法应用到数据诊断、模式识别和分类及控制系统的设计等 问题中，都取得了较好的结果。此方法逐渐发展为进化计算的另一个分支进化 规划( e p ) t 1 1 1 2 1 。 4 第二章遗传算法简介 1 9 6 2 年，h o l l a n d 提出了位串编码技术，此技术改变了先前只能依赖变异 来产生新的基因结构的状况，使编码既适用于变异操作，又适用于交叉操作，并 且强调将交叉作为主要的遗传操作。1 9 6 7 年，h o l l a n d 的学生j d b a g l e y 通过对 跳棋游戏参数的研究，在其博士论文中首次提出“遗传算法”一词。1 9 7 5 年， h o l l a n d 出版了专著自然与人工系统中的适应性行为( a d a p t a t i o ni n n a t u r a la n d a r t i f i c i a ls y s t e m s ) 。以后，h o l l a n d 等人将其应用于适应性系统模拟、函数优化： 机器学习、自动控制等领域，并正式定名为遗传算法。 1 9 7 5 年以后，遗传算法的基本理论得到了丰富和发展。g o l d b e r g 、d a v i s 、 g r e f e n s t e t t e 、b a u e r 、s f i n i v a s 和p a t n a i k 等大批研究人员对遗传算法理论的基本 框架和遗传算子进行了构建和改进。1 9 8 9 年，d a v i dg o l d b e r g 出版了第一本遗传 算法的教科书g e n e t i ca l g o r i t h m si ns e a r c h , o p t i m i z a t i o n a n dm a c h i n el e a r n i n g 。 2 0 余年来，遗传算法的发展日益成熟，许多学者提出了各种不同的遗传基 因表达方式，不同的交叉和变异算子以及不同的再生和选择方法。这些改进方法 产生的灵感都来自于大自然的生物进化过程，可归为同一个“算法簇”。人们把这 个遗传“算法簇”称为进化计算( e v o l u t i o n a r yc o m p u t a t i o n ) 。它基本分为四个分支： 遗传算法( g a ) 、进化规划( e p ) 、进化策略( e s ) 和遗传规划( g p ) 。 随着遗传算法研究和应用的不断深入与扩展，世界范围的遗传算法学术会议 也开始举办。主要有从1 9 8 5 年开始在美国隔年召开的遗传算法国际会议( i c g a ) 和之后的遗传和进化国际会议( g e c c o ) ，从1 9 9 0 年开始在欧洲隔年举办的并 行问题自然算法会议( p p s n ) 和之后隔年一次的遗传算法理论基础学术会议 ( f o g a ) ，从1 9 9 6 年6 月开始之后每年召开一次的“进化计算”国际学术会议 ( i e e ei c e c ) 。从1 9 9 9 年开始，i e e e 神经网络委员会与进化规划( e p ) 的年 会合并为进化计算国际会议，每年召开一次。 关于遗传算法的专集和杂志也陆续出版。1 9 9 4 年1 月，i e e e 神经网络委 。员会出版了第一本“进化计算”专集。1 9 9 7 年，该委员会创办了i e e et r a n s a c t i o no n e v o l u t i o n a r yc o m p u t a t i o n 杂志。从1 9 9 3 年开始美国m i t 出版社开始出版 e v o l u t i o n a r yc o m p u t a t i o n 和a d a p t i v eb e h a v i o r 杂志。世界上第一本关于人工智能 研究的杂志a it r e n d s 于1 9 9 3 年更名为c r i t i c a lt e c h n o l o g yt r e n d s 。并在更名启事 第二章遗传算法简介 中讲到“遗传算法、自适应系统、细胞自动机、混沌理论和人工智能一样，都 是对今后十年的计算机技术有重大影响的关键技术”。随着国际互联网的发展和 普及应用，遗传算法的有关研究单位建立了大量的专题g a 网站，其中最为著名 的是由美国海军人工智能应用研究中心建立的g a a r c h i v e s 检索网站 ( h t t p ：w w w a i c n r l n a r y m i l g a l i s t ) 。 这些众多的研究单位和频繁的国际学术活动集中反映了遗传算法的学术意 义和应用价值。遗传算法已成为一个多学科、多领域的重要研究方向。 2 2 遗传算法的基础 1 3 - 1 8 】 2 2 1 遗传算法的基本原理 达尔文的自然选择学说认为，生物要生存下去，就必须进行生存斗争。在生 存斗争中，具有有利变异的个体就容易存活下来，并且有更多的机会将有利变异 传给后代，而具有不利变异的个体就容易被淘汰，产生后代的机会也少得多。因 此，凡是在生存斗争中获胜的个体都是对环境适应性比较强的，遗传和变异是决 定生物进化的内在因素。遗传是指父代和子代之间，在性状上存在的相似现象。 变异是指父代和子代之间，以及子代的个体之间，在性状上或多或少地存在的差 异现象。遗传能使生物的性状不断地传给后代，因此保持了物种的特性，变异能 够使生物的性状发生改变，从而适应新的环境而不断地向前发展。生物进化的基 本过程为：以初始的群体为起点，经过竞争后，一部分群体被淘汰而无法再进入 这个循环，而另一部分则成为新的群体。优胜劣汰在这个过程中起着非常重要的 作用。群体通过婚配的作用产生子代群体。进化的过程中，可能会因为变异而产 生新的个体。综合变异的作用，子代群体成长为新的群体而取代旧的群体。在新 的一个循环中新的群体将替代旧的群体而成为循环的开始，从而使生物群体不断 向前进化。 2 2 2 遗传算法的基本术语 由于遗传算法研究与应用尚在不断发展中，有关术语的应用尚未完全取得 统一。为了在下面研究中做到准确、清晰、规范地描述，本文中采用的术语及其 6 第二章遗传算法简介 含义解释如下： 个体( i n d i v i d u a l ) ：g a 所处理的基本对象、结构。 群体( p o p u l a t i o n ) ：个体的集合。 位串( b i ts t r i n g ) ：个体的表示形式。对应于遗传学中的染色体。基因 ( g e n e ) ：位串中的元素，表示不同的特征。对应于生物学中的遗传 物质单位，以d n a 序列形式把遗传信息译成编码。 基因型( g e n o t y p e ) ：也称遗传型，指用基因组定义遗传特征和表现。 对应于g a 中的位串。 表现型( p h e n o t y p e ) ：生物体的基因型在特定环境下的表现特性。对 应于g a 中的位串解码后的参数。 基因位( 1 0 c u s ) ：某一基因在染色体中的位置。 等位基因( a l l e l e ) ：表示基因的特征值，即相同基因位的基因取值。 适应值( f i t n e s s ) ：某一个体对于环境的适应程度，或者在环境压力下 的生存能力，取决于遗传特性。 复制或选择( r e p r o d u c t i o no rs e l e c t i o n ) ：在有限资源空间上的排他性 竞争。 交叉或重组( c r o s s o v e ro rr e c o m b i n a t i o n ) ：一级位串或者染色体上对 应基因段的交换。 变异( m u t a t i o n ) - 位串或染色体水平上的基因变化，可以遗传给子代 个体。 遗传( h e r e d i t y ) ：父代个体通过有性方式向子代个体的特征传递过程。 编码( c o d i n g ) ：把问题空间中的参数转换成遗传空间中的个体。即从 表现型到基因型的转换。 解码( d e c o d i n g ) ：编码的相反操作。即从基因型到表现型的转换。 2 2 3 遗传算法的基本操作 遗传算法是一群体体型操作，该操作以群体中的所有个体为对象。选择 ( 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 ) 是遗传算法的三个主要操作 算子，它们构成了所谓的遗传操作，使遗传算法具有了其它传统方法所没有的特 性。遗传算法的基本流程如下图所示： 7 第二章遗传算法简介 图2 1 遗传算法是包含如下一些要素的集合体：( 1 ) 参数编码；( 2 ) 初始群体的设 定；( 3 ) 适应值函数的设计；( 4 ) 遗传操作设计；( 5 ) 控制参数的设定( 主要是 指群体大小和使用遗传操作的交叉概率、变异概率等) ；( 6 ) 算法终止法则的确 定。这六个要素构成了遗传算法的核心内容。 ( 1 ) 参数编码 按照遗传算法的工作流程，求解时必须在目标问题实际表示和遗传算法的 染色体间建立联系，即确定编码和解码运算。 由于遗传算法计算的鲁棒性，它对编码的要求并不苛刻。实际上，大多数 问题都采用h o l l a n d 建议的二进制编码设计，因为它最为实用并符合d ej o n g 的 编码原理【2 1 吼2 们。然而，在很多情况下，编码形式也就决定了交叉操作，编码问 题往往被称作编码一交叉问题。因此，作为遗传算法流程中第一步的编码技术是 一个值得认真研究的问题，很多专家提出了各种编码方法。 非二进制编码中具有代表性的是十进制编码方案【2 1 1 和实数编码方案嘲。在 采用g a 求解t s p 类问题时限2 2 】，用序列编码更为合理、自然。由此可见非二进 第二章遗传算法简介 制编码往往结合问题的具体形式，一方面可简化编码解码过程，另一方面可以在 遗传操作中采用非传统操作算子，或者与其它搜索算法相结合。 ( 2 ) 初始化群体 遗传算法是群体性的操作，因此必须具备一个由若干初始解构成的初始群 体。初始群体中的个体一般是随机产生的。群体规模n 越大，群体中个体的多样 性越高，g a 搜索的质量可以得到改进，但是计算量也随之增加；群体规模太小， 则可能产生早熟收敛。因此群体规模不宣太大也不宜太小。在不具有关于问题解 空间的先验知识的情况下，很难判定最优解的数量及其在可行解空间中的分布情 况。因此我们往往希望在问题解空间均匀采样，随机生成一定数目的个体( 为群 体规模的2 倍) ，然后从中挑出较好的个体构成初始群体。 ( 3 ) 适应度函数 遗传算法将问题空间表示为染色体位串空间，为了执行适者生存的原则， 必须对个体位串的适应性进行评价。因此，适应函数( f i t n e s sf u n c t i o n ) 就构成 了个体的生存环境。根据个体的适应值，就可决定它在此环境下的生存能力。一 般来说，好的染色体位串结构具有比较高的适应函数值，即可以获得较高的评价， 具有较强的生存能力。 由于适应值是群体中个体生存机会选择的惟一确定性指标，所以适应函数 的形式直接决定着群体的进化行为。为了能够直接将适应函数与群体中的个体优 劣度量相联系，在遗传算法中适应值规定为非负，并且在任何情况下总是希望越 大越好。 一般而言，适应值函数是由目标函数变换而成的。需要注意的是，只有对 整个群体的目标函数变换，才能计算出经过变换后的适应值，对单个个体计算适 应值无意义。 目前遗传算法中常用的适应值函数有以下几种：按比例的适应值分配；基 于排序的适应值分配；等机会变换；非单调适应值变换。需要注意的是，只有对 整个群体的目标函数，才能计算出经过变换后的适应值，对单个个体计算适应值 是没有意义的。( 如下图所示) 9 第二章遗传算法简介 计锋适绒埴 辫仇f 1 嫁蕊数傻群体运酶傻 令转1 麴坛r c t 数值崎 体1 适成值 令协2 瓣振滚数傻夸似透如偾 令体n 疆振蕊数傻 个体n 透娩值 图2 2 ( 4 ) 遗传算子 标准遗传算法的操作算子一般都包括选择、交叉、变异三种基本形式，它 们构成了遗传算法具备强大搜索能力的核心。 1 ) 选择( 复制) 选择即从当前群体中选择适应值高的个体以形成下一代群体的过程。发展 各种选择算子的目的是为了避免基因缺失，提高全局收敛性和效率。目前，常用 的选择有：适应值比例选择( 轮盘赌选择) ；排序选择；联赛选择；稳态选择；随机 遍历选择和精英选择策略【2 】。 需要注意的是，选择算子只是从当前群体中选择较好的个体形成交配池， 其本身并没有产生新的个体。 2 ) 交叉( 重组) g a 交叉算子是模仿自然界有性繁殖的基因重组过程，其作用在于将原有 的优良基因遗传给下一代个体，并生成包含更多基因结构的新个体。交叉操作一 般分为以下三个步骤：首先从交配池中随机选出要交配的一对个体；然后根据位 串长度l ，在要交配的一对个体中分别随机选i i g 1 ，l - 1 】中的一个或多个整数k 作为交叉位置；最质根据交叉概率实施交叉操作，相互交换交叉位置中的内容， 从而形成新的一对个体。 采用二进制编码、实数编码和自然数编码所用的交叉策略不样，目前通 常使用的遗传算子包括适用于二进制编码的一点交叉、两点交叉、多点交叉、一 l o 第二章遗传算法简介 致交叉；适用于自然数编码的部分匹配交叉、顺序交叉、圈交叉和启发式交叉和 适用于实数编码的算术交叉等。 3 ) 变异 在群体进化的整个过程中，交叉操作是主要的基因重组和群体更迭的手段， 变异操作的作用是第二位的，仅仅充当背景性的角色。但变异却是不可或缺的。 当交叉算子产生的后代的适应度不再比前辈好又未达到最优解，就会产生成熟前 收敛或早熟收敛，发生这种情况的根源是发生了有效基因缺失，这时，为了克服 这种情况，只有信赖于变异。一方面，变异算子可以使群体进化过程中丢失的等 位基因信息得以恢复，以保持群体中的个体差异性，防止发生成熟前收敛；另一 方面，当群体规模较大时，在交叉操作基础上引入适度的变异，也能够提高遗传 算法的局部搜索效率。 变异操作模拟自然界生物体进化中的突变现象，从而改变染色体的结构和 物理性状。常规变异的效果是不明显又很慢的，目前发展的主要变异算子有：基 于二进制编码的常规位变异、有效基因变异、自适应有效基因变异、概率自调整 变异和基于实数编码的均匀变异、非均匀变异、零变异等。 另外，许多高级遗传算子得到了研究，如显性算子、倒位算子、分离和易 位牌子、增加和缺失算子以及迁移算子等。这些遗传算子来源于群体遗传学，目 前应用尚少，机理及其表现有待进一步的深入研究。 ( 5 ) 控制参数和选择 在遗传算法的运行过程中，存在着对其性能产生重大影响的一组参数。主 要参数包括群体规模n ，交叉概率见以及变异概率p 。许多学者进行了大量实 验研究，给出了最优参数建议( d ej o n g 2 1 ，g r e f e n s t e t t e 2 3 1 ，s c h a f f e r 2 4 1 ) 。 1 ) 群体规模刀：大群体含有较多模式，为遗传算法提供了足够的模式采样 容量，可以改进g a 搜索的质量，防止成熟前收敛。但大群体增加了个体适应性 评价的计算量，从而使收敛速度降低。一般情况下专家建议n = 2 0 2 0 0 。 2 ) 交叉概率p 。：交叉概率控制着交叉算子的应用频率，交叉概率越高，群 第二章遗传算法简介 体中新结构的引入越快，已获得的优良基因结构的丢失速度也相应升高。而交叉 概率太低则可能导致搜索阻滞。一般取p c = 0 6 0 1 o o 。 3 ) 变异概率p 。：变异操作是保持群体多样性的有效手段，变异概率太小， 可能使某些基因位过早丢失的信息无法恢复；而变异概率过高，则遗传搜索将变 成随机搜索。一般取p 。= o 0 0 5 0 0 1 。 实际上，上述参数与问题的类型有着直接的关系，不存在一组适用于所有问 题的最佳参数值，在实际问题中应根据需要改变上述参数值以获得最佳结果。 ( 6 ) 终止循环的条件 由于遗传算法具有较大的随机性，这里根据几条启发式的终止条件瞄】，给 定参数s 、五、x 、y 和四种终止条件。 a 计算每代群体中染色体适应度的方差，当方差小于s 时，可认为算法收敛； b 计算每代群体适应度均值，当均值与最佳染色体适应度的比值大于五时， 可认为算法收敛； c 记录每代最佳染色体，若某染色体连续保持最佳达到x 代，可终止算法。 d 由于计算时间和机器容量都是有限的，代数不能无限长，故迭代次数达 到规定值y 时，可停止计算。 2 2 4 遗传算法的收敛性【2 6 】 遗传算法的基础理论主要以收敛性分析为主。对算法收敛性的分析主要分为 基于随机过程的研究和机遇模式理论的研究。这里简要给出基于随机过程的收敛 定理。 在遗传算法的进化过程中，个体集合一代一代的变化过程作为一个随机过程 来加以考察，并可利用m a r k o v 链来对进化过程进行理论分析，从而得到遗传算 法收敛性方面的重要结论。 这里先定义几个随机过程中的术语。 第二章遗传算法简介 定义1 设随机过程 x 仰) ，刀以) 只能取可列个值，= 乇，) ，并且满足条件： 对于任意刀及乇，厶，如果p x ( o ) = o ，x o ) = ，石( ，1 ) = ) 0 有尸 石( 咒+ 1 ) = 厶+ fi x ( o ) = 乇，x ( 1 ) = f 1 ，x ( n ) = ) = p x ( n + 1 ) = + li x ( n ) = ) 则称 z ( 行) ，n 0 ) 为时间状态离散的m a r k o v 链，简称m a r k o v 链。 定义2 称p x ( n ) = ，lx ( m ) = f ，；i m ) 为m a r k o v 连的转移矩阵，记为 0 ( m ，n ) 。 弓( ，l ，聆) 具有下面两条性质：( 1 ) 弓( m ，聆) o ；( 2 ) “p ，y ( m , n ) o = l 定义3 对于m a r k o v 链，如果 弓( 聊，r e + 1 ) = p x ( ，l + 1 ) = 歹i x ( m ) = f ) = p 扩( f ，) 即从状态i 出发转移到状态，的转移概率与时间起点m 无关，则称这类 m a r k o v 链为其次m a r k o v 链。 定义4 对于其次m a r k o v 连，称弓为一步转移概率，全部弓( f ，j ，) 所组成 的一个矩阵p = ( b ) 称为一步转移概率矩阵，或称为随机矩阵。 为了简单起见，我们只对基本遗传算法的收敛性进行分析。基本遗传算法可 描述为一个齐次的m a r k o v 链p = p ( f ) ，f 0 ) ，因为基本遗传算法的选择、交叉、 变异操作都是独立随机进行的，新群体仅与其父代群体及遗传算子有关，而与其 父代群体之前的各代群体无关，即群体无后效性，并且各代群体之间的转移概率 与时间起点无关。 定理1 【2 刀基本遗传算法收敛于最优解的概率小于l 。 证明：将群体的各种可能状态，分解为包括最优个体的状态厶和不包括最优 个体的状态厶： i = s ou 厶( j f dn 厶= ) ( 2 - 1 ) 需要证明进a 1 0 的稳定概率小于l 。 用反证法，假设基本遗传算法能收敛于最优解的概率等于1 ，则进入厶状态 第二章遗传算法简介 的稳定概率等于0 ，即 u m p ( 厶) = 0 f + ( 2 2 ) 在某些遗传算法的进化过程中，群体从某一状态i i 经过选择交叉和变异算 子的连续作用而转变为状态，。这三种遗传算子的转移概率分别是s 扩，勺， m 盯，他们可分别构成相应的随机矩阵s = ) ，c = c ：f ，) m 三 m 扩) ，则遗传算 法的群体状态变换矩阵为：r = s c m = 魄) 。 由于s ，c ，m 都是随机矩阵，并且，l ，= 掣u ( 1 - p 。) 1 - 州棚( h ( i ，_ ，) 为状 态i 和状态之间的海明距离) ，容易得证勺 0 ，即r 是正定的。 在t 时刻，群体是状态的概率0 ( f ) 为： e ( f ) = 只( o ) 巧 ( = o ，1 ，2 ，- 一 ( 2 3 ) f 由齐次m a r k o v 链的性质可知，p j ( t ) 的稳定概率的分布和初始概率分布无 关，即有 弓( ) = 鼻( o o ) 勺 o f e ， ( 2 4 ) 注意到上式中的状态j i ，e p j 也可能是，。中的一个状态，从而可知 l i m 尸 只e i 。) 0 f + ( 2 5 ) 上式与式( 2 2 ) 的假设相矛盾，从而定理得证。 显然，对于这种收敛于最优解的概率小于l 的基本遗传算法，其应用可靠性 就值得怀疑。从理论上来说，仍希望遗传算法能够保证收敛于最优解，这就需要 对基本遗传算法进行改进，如果使用精英保留的策略就可以达到这个要求。 定理2 【2 8 1 用精英保留的策略的遗传算法能收敛于最优解的概率为l 证明：考察这样所组成的个体集合p + ( f ) = ( 彳( f ) ，尸( f ) ) ，其中a ( t ) 是当前群体 中适应值最高的个体。这一个体集合的状态转移规则是； ( 1 ) 根据定理1 中的状态转移矩阵尺，由p ( t ) 产生p ( t + 1 ) ( 2 ) a ( t + 1 ) 是从上一代群体中和本代群体中挑选出的一个具有最大适应值 1 4 第二章遗传算法简介 的个体，即a ( t + 1 ) = m a x a ( t ) ，4 ) ( a o 是群体p o + 1 ) 中适应值最高的个体) ，这 样所构造出的随机过程p + ( f ) ，t o 仍然是一个齐次m a r k o v 链，即有 尸+ o ) = p + ( 0 ) ( r + ) 假设个体集合状态中包括有最优解的状态为厶，则该随机过程的状态转移概 率为： 瞎 0( v i ，w i o ) ( 2 6 ) 哆= 0 ( v i i o ，v j 碧i o ) ( 2 - 7 ) 即从任何状态向含有最优解的状态转移的概率大于0 ，而从含有最优解的状 态向不含最优解的状态转移的概率等于0 。此时，对于v i ，v j 芒厶，下式都成 立： 菇一o o 专o o ) ( 2 8 ) f ( ) = o ( j 圣i o ) ( 2 - 9 ) 亦即个体集合收敛于不含有最优解的状态的概率为0 。换言之，算法总能以 概率1 搜索到最优解。 2 2 5 遗传算法的基本特性2 9 , 3 0 , 3 1 】 ( 1 ) 自组织、自适应性：应用遗传算法求解问题时，在编码方案、适应值 函数及遗传算子确定后，算法将利用进化过程中获得的信息进行组织搜索。基于 自然的选择策略为：适者生存。因此适应值大的个体具有较高的生存概率，再通 过交叉和基因突变等遗传操作，就可能产生更适应环境的后代。遗传算法的这种 自组织、自适应特征，使它具有能根据进化过程中解的变化来自动发现解空间的 特性和规律的能力。 ( 2 ) 并行性：遗传算法的本质并行性表现在两个方面：一是遗传计算是内 在并行的，即其可让一定数量的计算机各自进行独立群体的遗传计算，等运算结 束后才进行通信比较，选取最优个体：二是遗传算法的内含并行性。由于遗传算 法采用群体的方式组织搜索，因而可同时搜索解空间的多个区域，并相互交流信 第二章遗传算法简介 息。使用这种搜索方式，虽然每次只执行与群体规模成比例的计算，但本质 上己进行了d ( 3 ) 次有效搜索，这就使遗传算法能以较少的计算获得较大的收 益。 ( 3 ) 过程性：遗传计算通过自然选择和遗传操作等自组织行为来增强群体 的适应性。在这个过程中，算法本身无法判断个体处在解空间的位置，因此需要 人为干预( 即事先确定终止准则) 才能终止。 ( 4 ) 多解性：遗传算法的另一基本特征是采用群体的方式组织搜索。它从 多个点出发，通过这些点的内部结构的调整和重组来形成新的点，因而每次都将 提供多个近似解。 ( 5 ) 不确定性：遗传算法的不确定性是伴随其随机性而来的。遗传算法的 主要步骤都含有随机因素。从而在算法的进化过程中，事件发生与否带有很大的 不确定性。 ( 6 ) 非定向性：自然选择和生殖过程这种非定向机制是遗传算法的关键。 它没有确定的迭代方程，而是用调整群体内部结构的方法来增强其对环境的适应 性，以使得问题得到解决。 ( 7 ) 内在学习性：遗传算法的个体学习方式是通过改变个体的基因结构来 提高自己的适应值。 ( 8 ) 统计性：遗传计算的群体方式决定它是一个统计过程。在每一代，都 要进行统计，以确定个体的优劣并推动进化的进行。 ( 9 ) 稳健性：由于遗传算法利用个体的适应值推动群体的进化，而不管求 解问题本身的结构特性，因而在用遗传算法求解不同问题时，只需要设计相应的 适应值函数，而无须修改算法的其它部分。同时，因为遗传算法具有自适应性， 算法在效率和利益之间的权衡使得它能适用于不同的环境并取得较好的效果。 ( 1 0 ) 整体优化性：遗传算法能同时在解空间的多个区域内进行搜索，并且 能以较大的概率跳出局部最优，以找出全局最优解。 1 6 第二章遗传算法简介 2 3 遗传算法的应用【3 1 】 遗传算法提供了一种求解系统优化问题的通用框架，它不依赖于问题的具体 领域，对问题的种类有很强的适应性，所以广泛应用于很多学科。遗传算法的应 用领域主要有： ( 1 ) 函数优化 函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用 算例。很多人构造出了各种各样的复杂形式的测试函数，有连续函数也有离散函 数，