（运筹学与控制论专业论文）多目标遗传算法应用的研究.pdf

中文摘要 多目标优化问题一直是科学和工程研究领域的一个难题和热点问题，在遗传 算法应用到这一领域以前，已经产生了许多经典的方法，经典方法在处理大维数、 多模念等复杂问题上存在许多不足。多目标遗传算法具有处理大的问题空间的能 力，在一次进化过程中可以得到多个可行解曲面，对问题域的先验知识没有要求， 对函数定义域的凸性不敏感，这正是经典算法所不具备的。所以，应用遗传算法 求解多目标优化问题，是这一领域的发展趋势。 本文在广泛深入地查阅国内外文献的基础上，对遗传算法及其面向多目标优 化问题的基础理论和基本方法进行了深入的理论研究和实验分析，主要内容如 下： 1 系统、详尽的介绍了遗传算法的一般流程和基本理论、方法，以及面向 多目标优化问题的遗传算法的基本理论方法。对经典的方法进行了分析和比较， 指出了经典方法的应用范围、成功实例、不足之处。 2 提出了一种新的多目标遗传算法。针对随机权重多目标遗传算法提出了 三点改进： ( 1 ) 精华保留，从临时p a r e t o 解集中选出札。个拥挤距离最大的个 体作为精华保留，从而使当前周围个体密度小的p a r e t o 解占优，对保持种群的多 样性有利；( 2 ) 采用追踪权值的方法，记录下选择过程中选出的个体所对应的权 重；( 3 ) 产生一部分固定的权值用于选择操作，找出当前拥挤距离最大的p a r e t o 解， 在其对应的权值附近产生一些权值用于选择操作，从而使p a r e t o 解在p a r e t o 前沿 的分布更均匀。实验结果表明，新的算法具有更好效果。 3 简要回顾了递阶优化问题的发展历史，归纳总结了递阶优化问题的特点， 论述了递阶优化问题的研究现状。 4 针对现有方法求解一种上层为o 一1 变量，下层为多目标的两层决策问题 的不足，提出了一种更符合实际决策过程的新方法，旨在为上、下决策者在二者 的偏好之间给出一定数量的最优解；并且针对该问题设计了一种多种群协同进化 的遗传算法。通过多个子种群同时进化，每个子种群对应的下层目标函数的偏好 不同，在进化的过程中采用一定的信息交换原则，使求解基于不同偏好最优解的 过程在整个群体的一次进化过程中实现。文中给出的算例说明了算法的有效性。 关键词：多目标遗传算法随机权重方法拥挤距离两层决策。一1 规划 a b s t r a c t u s i n ge v o l u t i o n a r ya l g o r i t h m s ( e a s ) t os o l v eg l o b a lo p t i m i z a t i o np r o b l e m s ，i e e v o l u t i o n a r yo p t i m i z a t i o n ( e o ) ，i sa l w a y st h em o s ti m p o r t a n tr e s e a r c ha n da p p l i c a - t i o nd o m a i no fe a s a l t h o u g hh a v i n gb e e ns u c c e s s f u l l ya p p l i e di nm a n yp r a c t i c a l p r o b l e m s ，e a sn o to n l yl a c ks t e a d yt h e o r e t i c a lf o u n d a t i o n s ，b u te x p o s em a n ys h o r t c o - m i n g si np r a c t i c a la p p l i c a t i o n s 1 w ei n t r o d u c er e l a t e db i o l o g yk n o w l e d g ea n dg i v eab r i e f r e v i e wo f t h ed e v e l o p m e n th i s t o r yo f e a s t h e nw ec o n c l u d et h em a i nc h a r a c t e r so f e a sa n ds m nu pt h e p r e s e n ts i t u a t i o no f t h et h e o r i e sa n da p p l i c a t i o n so f e a s 2 t h i sp a p e rp r o v i d e san e wm u l t i - o b j e c t i v eg e n e t i ca i g o r i t h mt h a ti m p r o v e so n t h er a n d o mw e i g h tm u l t i - o b j e c t i v eg e n e t i ca l g o r i t h mf r o mt h r e ep a r t sa sf o l l o w ： ( 1 ) r e s e r v i n ge l i t e c h o o s i n g 眠“i n d i v i d u a l sw h o s ec r o w d i n gd i s t a n c e sa r et h e m o s to n e sf r o mt e m p o r a r yp a r e t os o l u t i o ns e ta st h ee l i t et or e s e r v e t h e r e f o r e t h e p a r e t os o l u t i o nw h o s ei n d i v i d u a ld e n s i t yi ss m a l la r o u n dc u r r e n t l yi sb e a e rt h a nt h e o t h e r s ，t h a ti sp r o f i tf o rh o l d i n gt h ev a r i e t yo ft h eg e n u sg r o u p ；( 2 ) a p p l y i n gt i l e m e t h o do f t r a c i n gw e i g h tt or e c o r dt h ew e i g h t sa c c o r d i n gt ot h ei n d i v i d u a l sc h o s e ni n t h ec h o o s i n gp r o g r e s s ；( 3 ) g e n e r a t i n gm e m b e r so ff i x e dw e i g h t st oc h o o s et h e o p e r a t i o na n df i n do u tt h ep a r e t os o l u t i o nw h o s ec r o w d i n gd i s t a n c ei st h eb i g g e s t t h e ng e n e r a t i n gs o m ew e i g h t sa r o u n dt h ew e i g h ta c c o r d i n gt os u c hs o l u t i o nt oc h o o s e t h eo p e r a t i o na n dm a k et h ep a r e t os o l u t i o nt od i s t r i b u t ei nt h ep a r e t of o r m e re d g e m o r eu n i f o r m l y t h er e s u l to ft h et e s ts h o w st h a tt h en e wa l g o r i t h mh a st h eb e r e r e f f e c t 3 w eg i v eab r i e fr e v i e wo nt h ed e v e l o p m e n th i s t o r yo fh i e r a r c h i c a lo p t i m a l s y s t e m s ，t h e nw ec o n c l u d et h em a i nc h a r a c t e r so fh i e r a r c h i c a lo p t i m a ls y s t e m s ，s t a t e t h es u r v e yo f h i e r a r c h i c a lo p t i m a ls y s t e m s 4 t o w a r d st h es h o r t a g eo ft h ep r e s e n tm e t h o d st h a ts o l v et h es i t u a t i o nw h e r e t h e r ea r eu p p e rl e v e l0 - ld e c i s i o nv a r i a b l e sa n dl o w e rl e v e lm u l t i o b j e c t i v ef u n c t i o n s ， w ep r o p o s ea n e wm e t h o dw h i c ha c c o r dw i t i lt h ea c t u a ld e m a n d s i nt h i sp a p e r , w e d i s c u s s e dt h es i t u a t i o nw h e r et h e r ea r eu p p e rl e v e l0 - 1d e c i s i o nv a r i a b l e sa n dl o w e r l e v e lm u l t i o b j e c t i v ef u n c t i o n s ，w h i c hl e a d st oc e r t a i na n a o u n to fo p t i m a lv a l u e s b e t w e e np r e f e r e n c e so ft h eu p p e ra n dl o w e rl e v e ld e c i s i o nm a k e r s w ef u r t h e r c o n s t r u c tam u l t i p o p u l a t i o nc o e v o l u t i o ng e n e t i ca l g o r i t h m m u l t i p l es u b p o p u l a t i o n e v o l v es i m u l t a n e o u s l y t h ep r e f e r e n c e so ft h el o w e rl e v e lo b j e c t i v ef u n c t i o n so fe a c h s u b p o p u l a t i o na r ed i f f e r e n ta n dw e u s et h ei n f o r m a t i o ne x c h a n g i n gp f i n c i p l et os o l v e t h eo p t i m a lv a l u e si nd i f f e r e n tp r e f e r e n c e si no n ep r o c e s so ft h ee v o l u t i o ni nt h e w h o l ep o p u l a t i o n t h ee x a m p l e si no u rp a p e rs h o wt h ee f f i c i e n c yo f t h i sa l g o r i t h m k e y w o r d s ：m u l t i o b j e c t i v e ，g e n e t i ca l g o r i t h m s ，r a n d o m w e i g h ta p p r o a c h c r o w d i n gd i s t a n c e ，b i l e v e ld e c i s i o n ，0 - 1p r o g r a m m i n g 独创性声明 本人声明所里交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得墨壅盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：起蔷串 签字日期：彬 年莎月7 日 学位论文版权使用授权书 本学位论文作者完全了解墨凄盘茎有关保留、使用学位论文的规定。 特授权盘鲞盘茔可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名 走南 签字同期：动口f 年舌月7 日 导师签名： 祝地 签字日期：羽扩多年乡月1 日 天津大学硕士学位论文 第一章序言 1 1 遗传算法的理论与应用简介 遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种白适应 全局搜索算法。它最早是由美国m i e h i g a n 大学的h o l l a n d 教授提出，起源于6 0 年代对自然和人工自适应系统的研究【1 】。h o l l a n d 创建的遗传算法是利用某种编 码技术作用于称为染色体的二进制数串，其基本思想是由模拟的这些串组成的 群体的进化过程。遗传算法通过有组织但是随机的交换来重新组合那些适应性 好的串，在每一代中，利用上一代串结构中适应性好的位和段来产生一个新的 串的群体；作为额外添加，偶尔也要在串结构中尝试用新的位和段来替换原来 的部分。它可以利用已有的信息来搜索那些有希望改善解质量的串。遗传算法 通过作用于染色体上的基因，寻求好的染色体来求解问题。与自然界相似，遗 传算法对求解问题的本身一无所知，它需要的仅是对算法所产生的每个染色体 进行评价，并基于适应值来选择染色体，使适应值好的染色体比适应值差的染 色体有更多的繁殖机会。遗传算法通过模拟这尔文“优胜劣汰、适者生存”的 原理及利好的结构；通过模拟孟德尔遗传变异理论在迭代过程中保持已有的结 构，同时寻找更好的结构。 7 0 年代d e j o n g 基于遗传算法的思想在计算机上进行了大量的纯数值函数 优化计算实验1 2 l 。在一系列研究工作的基础上，8 0 年代由g o l d b e r g 进行归纳总 结，形成了遗传算法的基础框架【3 】。 由于内在的的自学习性、并行性、稳定性等强大优点，遗传算法在包括数 值优化、组合优化、自动控制、模式识别和人工生命等众多的领域得到了广泛 的应用，并显示出了强大的能力。 1 2 多目标遗传算法的发展过程及研究现状 多目标优化问题一直是科学和工程研究领域的一个难题和热点问题，不仅 因为许多工程问题本身就是一个多目标优化问题，而且在多目标优化领域内还 存在着许多尚未解决的难题。遗传算法应用于单目标问题之后的2 0 多年以后， 多目标遗传算法逐渐成为研究热点。l o 几年来出现了许多基于进化方法的多目 多目标遗传算法逐渐成为研究热点。l o 几年来出现了许多基于进化方法的多目 天津大学硕士学位论文 标优化技术。遗传算法的思想在多目标优化问题中的首次应用可以追溯到1 9 6 7 年，在r o s e n b e r g 的研究中提出了模拟单细胞有机物的化学遗传特性中采用多 属性研究方法 4 1 。虽然在他的研究中最终只应用了单一属性方法，正是他的研 究开创了这个领域的研究，然而，遗传算法真正应用于多目标优化领域是在9 0 年代初期最早出现的。 遗传算法的操作需要适应度值的信息，那么，对于多目标优化问题来说最 直接的方法就是采用加权的方法将各个目标函数整合成一个单目标优化问题。 从概念上讲，权重和方法可以看作是将多目标优化中采用的方法向遗传算法进 行扩展。陔方法给每个目标函数分配权重，然后将加权目标组合为单一目标函 数。事实上，在遗传算法中使用的权重和方法与在传统多目标优化算法中使用 的权重和方法在本质上有很大不同。在多目标优化中，权重和方法用来获得妥 协解。使算法运行的唯一要求是合适的权重向量，但是对于给定问题，通常很 难获得一组合适的权重。在遗传算法中，最初权重和方法用来是遗传搜索向着 p a r e t o 前沿进行。随着进化的进行，权重适应性的重薪调整。因此并不一定需 要良好的权重向量来是遗传算法运行。另外，权重和方法在传统多目标优化中 的缺点也可以被遗传算法基于种群搜索和进化搜索的力量削弱。最近提出了三 种权重设置的方法：固定权重方法、随机权重方法和适应性权重方法p 】。固定 权重方法可以看作是对传统标量化方法的模仿，而随机权重方法和适应性权重 方法用来更全面的利用遗传算法的搜索能力。m u r a t a ，i s h i b u c h i 和t a n a k a 提出 了一种随机权重方法( r a n d o m - w e i g h ta p p r o a c h ) 来获得目标是p a r e t o 前沿面的 可变搜索方向f 6 j 】。存在两种目标空间中有代表性的搜索行为：固定方向搜索和 多方向搜索。固定权重方法使遗传算法有向着目标空间中一个固定点所在的区 域进行采样的趋势，而随机权重方法则使遗传算法具有可变搜索方向，即在整 个p a r e t o 前沿面上进行均匀采样的能力。但是这种方法忽略了每代的p a r e t o 解 中可能获得的信息，难以找到所有目标函数在某种程度上较好的协调解，并且 由于选择过程中的每一步都随机给出权重，使其难以生成分布较广且均匀的 p a r e t o 最优解。 目标规划法中决策者必须确定他理想中的每个目标函数所能达到的目标 值，然后将这些值作为附加的约束整合进问题中，对其进行优化就是最小化理 想的目标值和目标函数值之间的绝对偏差。此法适用于目标函数是线性的或者 是部分线性的情况，对于非线性的情况它可能不太适用。1 9 9 2 年w i e n k ee ta 1 使 用目标规划法和遗传算法结合来解决核物理学中的问题。 早期的多目标遗传算法一般都是遗传算法和一些经典的多目标优化技术的 结合产物，它们普遍效率不高、局限性大、鲁棒性差。之后出现了基于多种群 天津大学硕士学位论文 的v e g a 、基于字典序的方法、基于搏弈论的方法等等，这些方法的特点是实 用性差、解的精度不高、不能保证求得最优解。 目前多目标遗传算法的研究热点是采用p 盯e t o 机制的多目标优化技术，包 括：m o g a 、n s g a 、n s g a i i 、n p g a 、s p e a 等等。 m o g a 由f o n s e c a 和f l e m i n g 于1 9 9 3 年提出 8 1 ，主要思想是个体排序的序 号由当前种群中支配它的个体的数量来决定。m o g a 在多目标优化领域得到了 广泛的应用。 非支配排序遗传算法_ n s g a 是由s f i m v 踮和d e b 于1 9 9 3 年提出的。算 法是基于对个体的几层分级实现的【9 】，n s g a 在现实问题的求解中得到了广泛 的应用。但是，n s g a 本身存在许多不足之处，使得它在处理高维、多模态等 问题时，难以得到满意的结果。n s g a 存在的主要问题是：1 ) 计算复杂性较高 为o ( m n 3 ) ，当处理大种群问题时，计算代价十分大，尤其是当种群在每代都需 要进行排序时，这种消耗则更明显；2 ) 缺乏精英策略，最近的研究表明【l “】， 精英策略可以明显的改善遗传算法的收敛特性，同时可以避免丢失进化过程中 取得的最优解；3 ) 需要特别指定共享半径。共享可以确保种群的多样性， 但是对于共享半径的取值仍然是一个很难确定的问题。文献 1 2 】虽然尝试采用 动态参数调整，但是仍然没有摆脱共享半径参数的选择过程。2 0 0 0 年，d c b 对 n s g a 算法进行改进，得到了n s g a - i i 算法i ”】，使运算速度和算法的鲁棒性进 一步提高。为了标定分级快速非胜出排序后同级中不同元素的适应值，也为使 准p a r e t o 域中的元素能扩展到整个p a r e t o 域，并尽可能均匀遍布，文献【1 3 】提 出了拥挤距离的概念，采用拥挤距离比较算子代替需要计算复杂的共享参数的 适值共享方法。 1 3 两层决策理论及其发展概要 随着人类社会的发展，实际问题的规模越来越大，结构越来越复杂，涉及对 问题做出决策的人越来越多，从而形成了一类具有多人参与的、呈递阶结构的决 策系统。因此，研究这类系统既具有理论意义又具有实际应用价值。 迄今为止，己有大量的文献研究有关大系统的理论及其应用。尽管至今尚无 一个公认的大系统定义，但众多学者公认大系统具有若干特性 1 4 。1 ”，诸如高维、 多层次、多目标等。 一般而言，高一级决策者自上而下地对下一级决策者行使某种控制、引导权， 而下一级决策者在这一前提下，亦可以在其管理范围内行使一定的决策权，这种 决策权处于从属地位。另外，在这种多层次决策系统中，每一级都有自己的目标 天津大学硕士学位论文 函数，而越高层机构的目标越重要、越权威、越具有全局性，因此最终的决策结 果往往是寻求使各层决策机构之间达到某种协调的方案，在这一方案下，既可使 最高层决策结构的目标达到“最优”，也可使作为上级决策“约束”的较低层决 策的目标在从属位置上相应达到“最优”，即下层决策以上层决策变量为参数， 我们称具有以上基本特征的决策问题为多层决策问题，有些文献又成为多层规划 问题、多层优化问题、具有主从策略的优化问题 1 6 1 。 具有主从递阶结构的决策问题最初是由v o ns t a c k l b e r g 于1 9 5 2 年在研究 市场经济问题时提出的，因此，主从递阶决策问题也被称为s t a c k e l b e r g 问题。 这一方面的早期工作主要是从对策论的角度来研究的。随着各种颇具特色的研 究成果逐渐增多，此类问题受到人们越来越多的关注，人们一方面逐步认识到 这一问题的重要意义，另一方面也迫切感到对这类问题寻求有效的求解技术。 实际中，很多决策问题都是由多个具有层次性的决策组成，这些决策者具 有相对的独立性，即上层决策者( u d m ) 只是通过自己的决策去指导( 或引导) 下层决策者( l d m ) ，不直接干涉下层的决策；而下层决策者只需把上层的决 策作为参数或约束，他可以在自己的决策范围内自由地决策。如果组成这种上、 下层关系不止一个时，这样的系统为多层决策系统1 1 7 d g ；如果只有一个上、下 层关系时，这样的系统为两层决策系统。由此可见，两层决策系统虽然是多层 决策系统的特殊形式，但它是最基本的形式，可以认为多层系统由多个两层系 统复合而成。因此，研究两层决策系统对多层决策系统具有典型性，故而本文 重点研究两层决策系统。 目前人们对连续型两层决策问题的研究已取得了不少成果1 1 9 1 ，对含整数型 两层决策问题，由于问题求解困难，研究成果甚少【2 0 ，2 l 2 ”。采用s t a c k e l b e 堆正向 主从策略的上层含有o l 变量下层是多目标的非线性两层规划问题是一类特殊 的多层多目标规划问题，文献 2 3 用k u h n t u c k e r 条件将问题单层化，再利用分 枝定界的方法进行运算，显然该方法对于大规模的问题是不适用的。 1 4 本文所作的工作的内容及安排 论文的第二章对遗传算法及多目标遗传算法的发展和基本概念作了介绍， 对算法的应用方法作了简要说明。并且介绍了一些常用的经典多目标遗传算法。 第三章提出了一种新的多目标遗传算法，并通过五个测试函数证明了该算 法比其他两种经典算法得到的非支配解收敛性更好，分布得更均匀。 第四章介绍了多层决策系统的特点，解决两层决策问题的基本算法及多目 标两层决策。提出了一种解决上层含o 一1 变量、下层为多目标的两层决策问题 天津大学硕士学位论文 的新方法一多种群协同进化遗传算法，多个子群体同时进化，每个子群体对 应的下层目标函数的偏好系数不同，在进化的过程中采用一定的信息交换原则， 使求解基于不同偏好的最优解集的过程在整个群体单次模拟运算中实现。 天津大学硕士学位论文 第二章遗传算法概述 电子计算机问世以来，生物模拟便构成了计算机科学的一个组成部分。其 目的之一便是从研究生物系统出发，探索产生基本认知行为的微观机理，然后 设计具有生物智能的机器或模拟系统以解决复杂问题。如遗传算法、神经网络 和细胞自动机等都是从不同角度模拟生物系统而发展起来的研究方向。 遗传算法( g e n e t i ca l g o r i t h m s - - 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 年代，几个科学家进行的“人工进化系统”的研 究，形成了遗传算法的雏形，如“适者生存”的仿自然法则，基于种群的设计 方案，自然选择和变异操作的加入，生物染色体编码的抽象处理等。即j 6 0 年代初期，柏林工业大学的r e c h e n b e r g 和s 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 。他们将此方法应用到数据诊断、模式识别和分类及控制系统的设计等 问题中，取得了较好的结果。后来又借助进化策略的方法发展了进化规划，并 用于数值优化及神经网络的训练等问题中。 6 0 年代中期，h o l l a n d 在f r a s e r 和b r e m e r m a r m 等人工算法的基础上提出了 位串编码技术，改变了先前只能依赖变异来产生新的基因结构的状况，使编码 既适用于变异操作，又适用于交叉操作，并且强调将交叉作为主要的遗传操作。 天津大学硕士学位论文 随后，h o l l a n d 将该算法用于自然和人工系统的自适应行为的研究中，并于1 9 7 5 年出版了其开创性著作“a d a p t a t i o n i 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 等人将该算法加以推广，应用到优化及机器学习等问题中，并正式定名 为遗传算法。 遗传算法的通用编码技术和简单有效的遗传操作为其广泛、成功地应用奠 定了基础。h o l l a n d 早期有关遗传算法的许多概念一直沿用至今，可见他对算法 的贡献之大。他认为遗传算法本质上是适应算法，应用最多的是系统最优化的 研究。 2 0 余年来，遗传算法的应用无论是用来解决实际问题还是建模，其范围不 断扩展，这主要依赖于遗传算法本身的逐渐成熟。近年来，许多冠以“遗传算 法”的研究与h o l l a n d 最初提出的算法已少有雷同之处，不同的遗传基因表达 方式，不同的交叉和变异算子，特殊算子的引用，以及不同的再生和选择方法， 但这些改进方法产生的灵感都来自大自然的生物进化，可以归为一个“算法簇”。 人们用进化计算( 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 4 年6 月，i e e e 召开第一届“进化计算”国际学术会议， 以后每年召开一次。从1 9 9 9 年开始，i e e e 神经网络委员会与进化规划( e p ) 的年会合并为进化计算国际会议，每年召开一次。【3 8 】 专集和杂志方面，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 ne v o l u t i o n a r y c o m p u t a t i o n 杂志。美国m i t 出版社从1 9 9 3 年开始出版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 l l i v e s 检索网站( h t t p ：w w w a i c n r l n a v y m i l g a l i s t ) 等等。 这些众多的研究单位和频繁的国际学术活动集中反映了遗传算法的学术意 天津大学硕士学位论文 义和应用价值。遗传算法已成为一个多学科、多领域的重要研究方向。 2 2 遗传算法基础2 o i 2 2 1 遗传算法的基本原理 达尔文的自然选择学说认为，生物要生存下去，就必须进行生存斗争。在 生存斗争中，具有有利变异的个体就容易存活下来，并且有更多的机会将有利 变异传给后代，而具有不利变异的个体就容易被淘汰，产生后代的机会也少得 多。因此，凡是在生存斗争中获胜的个体都是对环境适应性比较强的，遗传和 变异是决定生物进化的内在因素。遗传是指父代和子代之问，在性状上存在的 相似现象。变异是指父代和子代之间，以及子代的个体之间，在性状上或多或 少地存在的差异现象。遗传能使生物的性状不断地传给后代，因此保持了物种 的特性，变异能够使生物的性状发生改变，从而适应新的环境而不断地向前发 展。生物进化的基本过程为：以初始的群体为起点，经过竞争后，一部分群体 被淘汰而无法再进入这个循环，而另一部分则成为新的群体。优胜劣汰在这个 过程中起着非常重要的作用。种群通过婚配的作用产生子代群体。进化的过程 中，可能会因为变异而产生新的个体。综合变异的作用，子代群体成长为新的 群体而取代旧的群体。在新的一个循环中新的群体将替代旧的群体而成为循环 的开始，从而使生物群体不断向前进化。 2 2 2 遗传算法的基本术语 生物的遗传物质的主要载体是染色体，d n a 是其中最主要的遗传物质，而 基因又是控制生物性状的遗传物质的功能单位和结构单位。一定数量的基因组 成染色体，染色体中基因的位置称作基因座( 1 0 c u s ) ，而基因所取的值又叫做等 位基因( a l l e l e s ) 。基因和基因座决定了染色体的特征，也就决定了生物个体的 性状。此外，染色体有两种相应的表示模式，即基因型( g e n et y p e ) 和表现型 ( p h e n o t y p e ) 。所谓表现型是指生物个体所表现出来的性状，而基因型指与表 现型密切相关的基因组成。同一种基因型的生物个体在不同的环境条件下可以 有不同的表现型，因此表现型是基因型与环境条件相互作用的结果。在遗传算 法中，染色体对应的是数据和数组，在标准遗传算法中，这通常是由一维的串 结构数据来表现的。串上各个位置对应上述的基因座，而各位置上所取的值对 应上述的等位基因。遗传算法处理的是染色体，或者叫基因个体( i n d i v i d u a l ) 。 一定数量的个体组成了群体( p o p u l a t i o n ) ，也叫种群。群体中个体的数目称为 天津大学硕士学位论文 群体的大小( p o p u l a t i o ns i z e ) 也叫群体规模。而各个体对应环境的适应程度叫 做适应值( f i t n e s s ) 。决定以一定的概率从群体中选取若干对个体的操作称为选 择：而把两个染色体换组的操作称交叉，又称重组；突然让遗传因以一定概率 变化的操作称为变异。 选择、交叉及变异操作对于实现遗传算法是十分重要的。执行遗传算法时 包含两个必需的数据转换操作，一个是表现型到基因型的转换，另一个是基因 型到表现型的转换。前者是把搜索空间中的参数或解转换成遗传空间中的染色 体或个体，此过程称为编码操作( 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 ) 是遗传算法的三个主要操作 算子，它们构成了所谓的遗传操作，使遗传算法具有了其它传统方法所没有的 特性。遗传算法的基本流程如下图所示： 图2 一l 遗传算法是包含如下一些要素的集合体：( 1 ) 参数编码；( 2 ) 初始群体的 设定；( 3 ) 适应值函数的设计；( 4 ) 遗传操作设计；( 5 ) 控制参数的设定( 主要 是指群体大小和使用遗传操作的交叉概率、变异概率等) ；( 6 ) 算法终止法则 的确定。这六个要素构成了遗传算法的核心内容。 ( 1 ) 编码 天津大学硕士学位论文 由于遗传算法不能直接处理解空间的解数据，因此我们必须通过编码将他 们表示成遗传空间的由基因按一定结构组成的染色体或个体。这一转换就叫做 编码，也可以称作( 问题的) 表示( r e p r e s e n t a t i o n ) 。 一般来讲，由于遗传算法的鲁棒性，它对编码的要求并不苛刻。然而，编 码的策略或方法对于遗传操作，尤其是对于交叉操作的功能有很大影响。在很 多情况下，编码形式也就决定了交叉操作，编码问题往往称作编码一交叉问题。 因此，作为遗传算法流程中第一步的编码技术是遗传算法中需要认真考虑的方 面，它将直接影响到优化结果和算法的计算效率。 标准遗传算法( s g a ) 采用的是二进制编码方案，因为它符合d e j o n g 的编 码原理【3 们。但二进制编码易引起精度和效率的冲突。为得到高精度最优解，个 体的二进制编码串就要保持相当的长度，从而造成计算量的迅速增加。要保证 计算效率，又不得不缩短编码长度，从而造成解的精度受限。因此，对于较复 杂的解空间，一般采用十进制编码方案【4 1 1 或实数编码方案，这种编码方案比 较直观，不需解码过程。 ( 2 ) 生成初始群体 由于遗传算法的群体性操作的需要，所以我们必须为遗传算法操作准备一 个由若干初始解组成的初始群体。群体规模的确定受遗传操作中选择的影响很 大。群体规模越大，遗传操作所处理的模式就越多，生成有意义的最优解的机 会就越高。换句话说，群体规模越大，群体中个体的多样性越高，算法陷入局 部解的危险就越小。但是，群体规模越大，则其适应值评估次数越大，所以计 算量也越大，从而影响计算效率。所以，从考虑群体规模不能太大也不能太小。 在实际应用中群体个数的取值范围一般为几十个至几百个。 ( 3 ) 适应值函数 遗传算法在随机搜索中基本上不用外部信息，仅用基于目标函数的适应值 函数为依据。遗传算法的目标函数不受连续可微的约束且定义域可以为任意集 合。在具体应用中，适应值函数的设计要结合求解问题本身的要求而定。需要 强调的是，适应值函数评估是选择操作的依据。适应值函数设计直接影响到遗 传算法的性能。一般而言，适应值函数是由目标函数变换而成的。对目标函数 值域的某种映射变换成为适应值的尺度变换。 目前遗传算法中常用的适应值函数有以下几种：按比例的适应值分配；基 于排序的适应值分配：等机会变换；非单调适应值变换。需要注意的是，只有 对整个群体的目标函数，才能计算出经过变换后的适应值，对单个个体计算适 应值是没有意义的。( 如下图所示) 天津大学硕士学位论文 补箨邀糍氍 图2 2 ( 4 ) 选择操作( 复制操作) 选择或复制操作的目的是为了从当前群体中选出优良的个体，使它们有机 会作为父代为下一代繁衍子代。选择操作算子作用是判断个体优良与否，标准 就是个体各自的适应值的大小。个体适应值越大，其被选中的机会就越大。个 体适应值越小，其被选中的机会就越小。 目前常用的选择算子有：适应值比例选择算子，它又叫赌轮选择；排序选 择算子；联赛选择算子；随机遍历选择算子；正态几何选择算子和基于对约束 判断的选择算子。 ( 5 ) 交叉操作( 重组操作) 在自然界生物进化过程中起核心作用的是生物遗传基因的重组( 加上变 异) 。同样，遗传算法中起核心作用的是遗传操作的交叉算子。通过交叉操作， 遗传算法的搜索能力得以飞跃提高。以事先给定的交叉概率p 在选择出的n 个 个体中任意选择两个个体进行交叉操作，产生两个新的个体，重复此过程直到 所有要求交叉( 重组) 的个体交叉完毕。交叉是两个染色体之间随机交换信息 的。 目前常用的交叉算子有：由二进制编码引申而来的的单点交叉、多点交叉 和均匀交叉；针对实数编码的算术交叉和启发式交叉等等。 ( 6 ) 变异操作 变异操作的基本内容是对群体中个体串的某些基因座上的基因值按一定变 异概率作变动。就基于 o ，1 ) 的二进制编码串而言，变异操作就是把某些基因 座上的值取反，即0 变l 或1 变0 ，而变异位置是随机选择的。对于实数编码 而言，变异算子是在基因根据算子，在取值范围内随机取值，然后替换该基因 座上的原值个体。 目前常用的变异算子有：对二进制编码的o - 1 变异；对实数编码的正态变 异：均匀变异：边界变异等。 在遗传算法的结构中引入突然变异的目的在于：第一，使遗传算法具有跳 天津大学硕士学位论文 出局部，实现全局随机搜索的功能；第二，维持群体的多样性，避免出现早熟 收敛问题。 变异和交叉既有一定联系，又有不同之处。交叉与局部的搜索手段相对应， 而突然变异可以说是全局探索手段。变异和交叉之间，有互补的一面，也有有 竞争的一面。二者的结合是算法在局部搜索和全局搜索两方面能够做到兼顾。 ( 7 ) 遗传算法的终止法则 遗传算法的终止法则应根据不同的问题采用不同的法则。文【4 2 】把这些法则 归纳为四种。第一类方法就是给定一个最大的遗传代数m a x g e n ，算法迭代代 数在达到m a x g e n 时停止。第二类方法是给定问题一个下界l b ，当进化中达到 要求的偏差度s 时，算法终止。第三类方法则有一定的自适应性：当观察到最 优解己经连续k 代没有进化到一个更好的解时，算法终止。 最后一类是多种终止规则的组合，如第一类和第三类规则的组合。 由于生物的进化过程到目前为止还没有一个明确的终结方向。因此也就没 有一个适用于各类问题的通用终止法则，对于具体问题应通过比较再确定所要 选用的算法终止法则。 2 2 4 遗传算法的收敛性2 4 l 遗传算法的基础理论主要以收敛性分析为主。对算法收敛性的分析主要分 为基于随机过程的研究和基于模式理论的研究。这里简要给出基于随机过程的 收敛定理。 在遗传算法的进化过程中，个体集合一代一代的变化过程作为一个随机过 程来加以考察，并可利用m a r k o v 链来对进化过程进行理论分析，从而得到遗 传算法收敛性方面的重要结论。 这里先定义几个随机过程中的术语。 定义1 设随机过程( x ( 胛) ，玎门 只能取可列个值i = i o , ， ，并且满足条 件：对于任意n 及f o ，t ，如果p x ( o ) = i 0x ( 1 ) = ，x ( n ) = ) 0 必有： p x ( n + 1 ) = l 。n 。l x ( o ) = l ox ( 1 ) = ，x ( n ) = ) = p x ( n + 1 ) = + 。l x ( n ) = ) 则称 x ( ) ，n 0 ) 为时间状态离散的m a r k o v 链，简称m a r k o v 链。 定义2 称p x ( n ) = _ ，l x ( m ) = f ，r t m 为m a r k o v 连的转移矩阵，记为 g ( m ，n ) 。 p 0 ( m ，挖) 具有下面两