（管理科学与工程专业论文）基于多种群的遗传算法研究.pdf

山东师范火学硕士学位论文 中文摘要 动态优化和多目标优化是实际应用和优化中的常见问题，传统的求解方法常 常难以求解目标函数不连续、复杂高维等类问题，同时每次只能求得一个解。基 于此，论文选择动态优化算法和多目标优化算法为研究对象，研究求解这些问题 的进化计算方法。这两类进化计算方法中，存在一个共同的特点就是非常注重保 持种群的多样性，从而实现对动态优化问题中解的跟踪和多目标优化问题中多个 具有代表性p a r e t o 解的保持和进一步优化。为此，采用基于多种群的方式保持种 群的多样性，并且不同种群采用不同的进化机制，从而实现对问题的求解。论文 的研究内容包括以下几个方面： ( 1 )对进化算法进行简单回顾，然后综述了遗传算法的起源、进化算子、 进化过程和有关理论分析，特别对动态优化问题和多目标优化问题的研究现状进 行了分析。 ( 2 )提出了一种新的求解动态优化问题的多种群遗传算法，该算法采用 了两个独立且不同进化机制的多种群方式同时进化，并在检查点进行个体的迁 移，从而缓解了群体多样性与群体收敛的矛盾。实验表明该算法全局搜索能力强、 优化速度快，在动态变化的环境中具有较强的适应能力，具有较好的优化效果。 ( 3 )根据求解多目标优化问题的一般要求，结合当前多目标进化算法的 研究状况，从增强和保持种群的多样性角度出发，采用多种群的结构，提出了一 种基于多种群和，占优的多目标遗传算法，在算法中采用占优的策略更新外部 种群。实验表明，该算法能够求解各种不同类型的多目标进化优化问题，能够保 持p a r e t o 解的均匀分布。 关键词：遗传算法；多种群；动态环境；多目标优化； 分类号：t p l 8 山东师范大学硕士学位论文 a b s t r a c t m a n ya p p l i c a t i o n s a r ed y n a m o i co p t i m i z a t i o np r o b l e m sa n dm u l t i o b j e c t i v e p r o b l e m si np r a c t i c e h o w e v e r , t r a d i t i o n a lm a t h e m a t i c a lm e t h o d s c a n td e a l w i t h p r o b l e m sw h i c ha r eg e n e r a l l yu n c o n t i n u o u s ，d e r i v a t i v e - f r e ea n ds oo n ，a n de a c hr u n c a l lo n l yf i n do n es o l u t i o n t h e r e f o r e ，e v o l u t i o n a r ya l g o r i t h m sa r es t u d i e di nt h i s p a p e rt os o l v ed y n a m o i co p t i m i z a t i o np r o b l e m sa n dm u l t i - o b j e c t i v ep r o b l e m s t h e s e a l g o r i t h m sa l lp a ya t t e n t i o n st od i v e r s i t yr e s e r v a t i o no fm e i rp o p u l a t i o n s s ot h e a l g o r i t h m sc a nt r a c et h em o v i n go p t i m ai nd y n a m i ce n v i r o n m e n to rf i n dt h ed i v e r s e p a r e t os o l u t i o n si nm u l t i - o b j e c t i v eo p t i m i z a t i o np r o b l e m s m u l t i p l ep o p u l a t i o n sa r e e m p l o y e di nt h i sp a p e rt ok e e pp o p u l a t i o nd i v e r s i t ya n dt h e s ep o p u l a t i o n se v o l v ei n d i f f e r e n tw a y s t h em a i nr e s e a r c ht o p i c sa n dc o n t r i b u t i o n sa r ea sf o l l o w s ： ( 1 ) e v o l u t i o n a r ya l g o r i t h m sa r er e v i e w e df i r s t l ya n dt h e ng e n e t i ca l g o r i t h m i s d e t a i l e d ，i n c l u d i n gt h e i ro r i g i n ，o p e r a t o r s ，e v o l u t i o n a r yp r o c e s sa n dr e l a t e dt h e o r i e s t h ep r o g r e s so fd y n a m o i co p t i m i z a t i o np r o b l e m sa n dm u l t i o b j e c t i v ep r o b l e m sa r e a n a l y z e ds p e c i a l l y ( 2 ) am u l t i p o p u l a t i o ng e n e t i ca l g o r i t h m ( m p g a ) i sp r o p o s e df o rs o l v i n g d y n a m o i co p t i m i z a t i o np r o b l e m s t h ep r o p o s e da l g o r i t h me m p l o y st w op o p u l a t i o n s w i t hd i f f e r e n te v o l u t i o n a r yp r o c e s sa n de x c h a n g e st h e i rb e s ti n d i v i d u a l sa tc h e c k p o i n t m p g ac a nc o n v e r g e n c ef a s ta n dt r a c et h em o v i n go p t i m ai nd y n a m i ce n v i r o n m e n t ( 3 ) a f t e rs t u d y i n gt h en a t u r eo fm u l t i - o b j e c t i v eo p t i m i z a t i o na n di t s r e s e a r c h p r o g r e s s ，am 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 m b a s e do nm u l t i - p o p u l a t i o na n d e - d o m i n a n c ei s p r o p o s e d s i m u l a t i o ne x p e r i m e n t s o ns e v e r a l m u l t i - o b j e c t i v e o p t i m i z a t i o nb e n c h m a r k sd e m o n s t r a t et h a tt h ep r o p o s e da l g o r i t h mc a ns o l v ev a r i o u s m u l t i o b j e c t i v eo p t i m i z a t i o np r o b l e m sa n dk e e pd i v e r s i t yo ft h ep a r e t os o l u t i o n s k e y w o r d s ： g e n e t i c a l g o r i t h m ；m u l t i p o p u l a t i o n ；d y n a m i c e n v i r o n m e n t ； m u l t i - o b j e c t i v eo p t i m i z a t i o n c l a s s i f i c a t i o n ：t p18 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得( 注：如 没有其他需要特别声明的，本栏可空) 或其他教育机构的学位或证书使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示谢意。 学位论文作套印产 新擗 学位论文版权使用授权书 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权堂撞可以将学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在 解密后适用本授权书) 学位论文储签名撵1 幸唧 签字日期2 0 0 歹年6 月够日 导师签 签字吼2 。勺年历产 山东师范大学硕士学位论文 第一章绪论 本章首先介绍了以遗传算法为代表的进化计算相对传统计算方法的优势；其 次介绍了几种具有代表性的进化算法，包括微粒群优化算法、蚁群优化算法和文 化算法等；最后，介绍了论文的研究背景、研究内容、创新点和论文组织结构。 1 1 引言 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 是由美国密歇根大学的j o h nh o l l a n d 教授 和他的同事与学生最早开始研究和应用的，特别是1 9 7 5 年，j o h nh o l l a n d 教授出 版了其开创性的著作( ( a d a p t a t i o ni nn a t u r a la n da r t i f i c i a ls y s t e m s ) ) ，遗传算法得 到广泛的研究和应用【m 】。遗传算法是一种借鉴生物界自然选择和进化机制发展 起来的高度并行、随机、自适应搜索算法。简而言之，它使用了群体搜索技术， 将种群( p o p u l a t i o n ) 代表一组问题解，通过对当前种群施加选择( 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 ) 等一系列遗传算子( o p e r a t o r ) ，从而产生新一代种群， 并逐步使种群进化到包含近似最优解的状态 】。由于其思想简单、易于实现以 及表现出来的健壮性，遗传算法赢得了许多应用领域，特别是近年来在问题求解、 优化和搜索、机器学习、智能控制、模式识别和人工生命等领域取得了许多令人 鼓舞的成就【5 j 。 遗传算法之所以得到广泛研究和应用，是因为它与传统的搜索和优化方法存 在以下区别： ( 1 ) 自组织、自适应和自学习性( 智能性) 。在编码方案、适应度函数及遗 传算子确定后，遗传算法将利用进化过程中获得的信息自行组织搜索，同时，适 应度大的个体具有较高的生存概率，而这种自组织和自适应特征使得遗传算法具 有能根据环境变化来自动发现环境的特性和规律的能力。 ( 2 ) 遗传算法的本质并行性。遗传算法按并行方式搜索一个种群数目的点， 而不是单点。一是遗传算法的内在并行| 生( 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 ) ，由于遗传算法采用种群 的方式组织搜索，因而可以同时搜索解空间内的多个区域，并相互交流。 ( 3 ) 遗传算法不需要求导或其他辅助知识，而只需要影响搜索方向的目标函 数和相应的适应度函数。 ( 4 ) 遗传算法强调概率转换规则，而不是确定的转换规则。 ( 5 ) 遗传算法可以更加直接地应用。 ( 6 ) 遗传算法对给定的问题，可以产生许多潜在解，最终选择可以由使用者 确定。 山东师范大学硕士学位论文 此外，g a 在机理方面具有搜索过程和优化机制等属性，数学方面的性质可 通过模式定理和构造积木块假设等加以分析讨论，m a r k o v 链也是分析遗传算法 的一个有效工具6 1 。 1 2 进化计算简介 自1 9 7 5 年j o h nh o l l a n d 提出遗传算法以来，基于生物进化的算法得到了深 入广泛研究，并取得了许多重要成就和应用，但进化计算( e v o l u t i o n a r y c o m p u t a t i o n ，e c ) 、进化算法( e v o l u t i o n a r ya l g o r i t h m ，e a ) 、基于进化的算法 ( e v o l u t i o n a r y b a s e da l g o r i t h m ) 的定义和内涵并没有形成一个统一的定义。 文献 7 将进化算法定义为模拟自然生物进化和种群社会行为的随机搜索算 法。这样的例子包括蚂蚁寻找食物的最短路径，鸟群迁徙寻找目的地等，包括遗 传算法、m e m e t i ca l g o r i t h m 、微粒群优化算法( 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 ) 、 蚁群优化算法( a n tc o l o n yo p t i m i z a t i o n ，a c o ) 等。同时，将进化算法( e v o l u t i o n a r y a l g o r i t h m ，g a ) 和基于进化的算法( e v o l u t i o n a r y b a s e da l g o r i t h m ) 等同起来。 蔡自兴、徐光佑在其著作中指出，进化计算是指一类以达尔文生物进化论为 依据来设计、控制和优化人工系统的技术和方法的总称，包括遗传算法、进化策 略( e v o l u t i o n a r ys 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 ) h 1 。 它们遵循相同的指导思想，其共同的理论基础是生物进化论，但彼此存在一定的 差别。三种方法统称为进化计算，而把相应的算法称为进化算法。 在本文中，认为进化算法和基于进化的算法是等同的，并且包含所有模拟生 物进化的算法，为此对几种典型方法进行简单介绍( 遗传算法将在第二章介绍) 。 1 2 1 微粒群优化算法 p s o 是由k e n n e d y 和e b e r h a r t 提出的，主要模拟飞向未知目的地迁徙候鸟 的社会行为 9 - 1 0 】。在p s o 中，每个解对应鸟群中的一只鸟，也被称为粒子 ( p a r t i d e ) 。粒子类似g a 中的染色体，但p s o 的进化过程中不产生新的粒子， 每个粒子只是进化自身的社会行为，并朝着未知的目标前进。 实际上，p s o 模拟了一些能够在飞行中信息交流的鸟，每只鸟处于一个特定 的位置，通过相互交流，它们能够识别出处于最佳位置的鸟。相应地，每只鸟能 够以基于当前位置的速率朝着处于最佳位置的鸟飞行。每只鸟再在新的局部位置 继续搜索，重复上述过程一直到到达期望的目的地。值得注意的是，在整个过程 中，涉及到了鸟类之间的交互和智能，鸟类既能够借鉴自身经验( 局部搜索) ， 也能够借鉴其他鸟的经验( 全局搜索) ，从而实现其目标。 p s o 优化过程如下：首先初始化n 个随机粒子，第i 个粒子由其位置决定， 是s 维空间的一个点，s 是变量的个数。整个过程中，每个粒子监视三个值：当 2 山东师范大学硕十学位论文 前值、以前最优值和飞行速率。这三个值分别表示如下： 当前值：x i - ( x i i ，x i 2 ，x i s ) 以前最优值：p i = ( p i i ，m ，p i s ) 飞行速率： v i = ( v i i ，v i 2 ，v i s ) 在每一循环过程中，最佳粒子( g ) 的位置( p g ) 被作为全部粒子的最佳适应度， 相应地，每个粒子更新其速率以追随最佳粒子。速率更新方式如下： n e wv i = c o c u r r e n t v i + e l r a n d ( ) ( p i x i ) + c 2 r a n d ( ) ( p g x i ) 其中，c l 和c 2 是正的常数，称为学习因子，一般c 1 = c 2 = 2 ；r a n d ( ) 和r a n d ( ) 是 o ，1 上的随机函数；是惯性权重，用于控制以前速率的历史对当前速率的 影响，用于平衡全局搜索和局部搜索。当其在 1 4 0 5 】时，全局搜索随着时间线 性下降，因此，全局搜索以较大值开始，然后随着时间而下降以支持局部搜索超 过全局搜索。第二项是认知分量，代表粒子的局部搜索，比较当前位置与其以前 的最佳位置；第三项是社会分量，代表粒子之间的社会性合作，比较粒子的当前 位置与最佳位置。 然后，粒子使用新的速率更新其位置，且更新之后，粒子就飞向最佳位置： n e wp o s i t i o nx i = c u r r e n tp o s i t i o nx i + n e wv i v i 麟v i - v i n a x 其中，v 。桃是速率变化的上界。 1 2 2 蚁群优化算法 a c o 是由d o r i g o 等于1 9 9 1 年基于蚂蚁觅食寻找最短路径的启发而提出的， 与p s o 类似，a c o 不是在遗传基因上演化，而是在社会行为方面进行演化【l 卜1 2 j 。 a c o 是一种基于信息素( p h e r o m o n e ) 的间接通信方式，蚂蚁释放信息素，并且 能够感知这种物质，并以此指导自己的运动方向。信息素是可积累和挥发的物质， 其浓度随时间而变化，是一种正反馈现象：当某一路径上走过的蚂蚁越多，则后 来者选择该路径的概率就越大。 a c o 的表示：每只蚂蚁用s 个变量表示，每个变量i 具有n i 个选择项，值 为l i j ，相关信息素的积累值为“j ) ，其中i = 1 ，2 ，s ，j = l ，2 ，n i 。因此，一个蚂 蚁由描述其所选择路径的s 个值组成，即一只蚂蚁可表示为l l i ，1 2 j ，1 s j 。 在a c o 中，从随机生成m 只蚂蚁( 随机解) 开始，一只蚂蚁k ( k - 1 ，2 ，m ) 代表一个赎予了值的解串，并根据目标函数对其加以评价。相应地，信息素的积 累如下： 下i j ( t ) = p l ：i j ( t - 1 ) + a c i j t = 1 , 2 ，t 其中，t 是迭代次数；q j ( t ) 是t 时刻修改后的信息素；f i j ( t 1 ) 是t 1 时刻修改 后的信息素；t i 是信息素的变化值；p 是挥发因子，在( o ，1 ) ，避免受历史信 山东师范大学硕上学位论文 息素的影响太大，而出现早熟现象。信息素的变化量定义如下： 氓j ：号p 。毋m s k i f o p n 明1 h 话幽明b y a n tk 智【0 o t h e r w i s e 其中，r 是常数，信息素回报因子；f i t n e s s k 是第k 只蚂蚁的目标函数值。一 旦信息素的值被更新，下一次迭代将通过改变蚂蚁的行走路径开始，因此，蚂蚁 将以一定的概率随机更新每个变量的值。概率定义如下： 以如，= 嶷裂品 其中，p i j ( k ，t ) 为蚂蚁k 在第t 步迭代中为变量i 选中l i j 的概率；x i j ( t ) 为第t 步 迭代中与1 i j 相关的信息素浓度；m 为选择某个选项的启发式因子，表明选择l i j 对蚂蚁k 的贡献，该启发式因子与问题特征有关，每个l i j 有固定值。仅、p 为指 数参数，指示信息素集中或启发式因子的相对重要性，均大于0 ，可通过实验法 得到。 a c o 已被应用于t s p 、二次分配、作业调度、图表着色问题、电话网络和 数据通信网络的路由优化以及机器人建模和优化等，已显示出它在求解复杂优化 问题特别是离散优化问题方面的优势，是一种很有前途的计算智能方法。 1 2 3 文化算法 在人类社会的进化过程中，进化不仅受到微观层次的基因影响，而且受到宏 观层次的文化影响。而在当前的进化算法中，g a 、e s 、e p 等均只模拟了微观层 次的基因影响，因而，存在收敛速度慢、容易出现局部最优等问题。在人类社会 中，文化可以被看作是信息的载体，可以被社会所有成员全面地接受，并用于指 导每个社会成员的各种行为。当前，对文化的认识包括： d u r h a m 将文化定义为一种通过符号编码表示概念的系统，使得这些概念 可以在种群内部或不同群体之间传播和继承。 r e n f r e w 则认为人类在历史进化的过程中逐步建立了一套获取、编码和传 播文化信息的能力。所有这些能力的关键因素是分类的能力，并通过符 号表示，是对个体过去经验或对未来预测的符号化，这种能力人类特有 并区别于其它物种的能力。正是这种能力使人类能够形成、积累和传递 文化信息，并通过文化信息加快和约束进化的速度和方向。 文化算法这是受到上述启示而发展的。r o b e r tg r e y n o l d s 和x i d o n gj i n 在文 献 1 3 1 4 描述了一种文化算法，这种方法模拟了人类社会的进化过程。不同于其 它进化计算方法，在文化算法中，包含有两个进化空间：一个是由在进化过程中 由获取的经验和知识组成的信仰空间( b e l i e fs p a c e ) ；另一个是由具体个体组成 4 山东师范大学硕上学位论文 的群体空间( p o p u l a t i o ns p a c e ) 。这两个空间通过特定的通信协议( c o m m u n i c a t i o n p r o t o c 0 1 ) 进行信息的交流。 文化算法是一种计算框架，对种群空间和信仰空间可以采用不同的表示方法 和算法，从而形成多种不同的算法。文化算法能够具有较高的效率和收敛速度， 有两个方面的原因：( 1 ) 通过在性能上增加约束对种群施加了选择压力；( 2 ) 维 护了与个体分离的性能历史。 目前，文化算法的研究刚刚开始，开始用于约束优化、多目标优化、数据挖 掘、语义网络和动态环境优化等。 1 3 论文研究内容 动态优化和多目标优化是实际应用和优化中的常见问题，传统的求解方法常 常难以处理存在不连续、不规则等特征的目标函数。为此，论文选择动态优化和 多目标优化为研究对象，研究求解这些问题的方法。这两类方法中，存在一个共 同的特点就是非常注重保持种群的多样性，从而实现对动态优化问题中解的跟踪 和多目标优化问题中多个具有代表性p a r e t o 解的保持和迸一步优化。为此，采用 基于多种群的方式保持种群的多样性，并且不同种群采用不同的进化机制，从而 实现对问题的求解。论文的研究内容包括以下几个方面： ( 1 )对进化算法进行简单回顾，然后分析了进化算法的内涵、特点和几 种典型的进化算法，包括微粒群优化算法、蚁群优化算法和文化算法等。 ( 2 )综述了遗传算法的相关概念、算子、过程和有关理论，特别对动态 优化问题和多目标优化问题的研究现状进行了分析。 ( 3 ) 提出了一种新的求解动态优化问题的多种群遗传算法，该算法采用 两个不同种群方法，分别进行进化，并在检查点进行个体的迁移，从而缓解了群 体多样性与群体收敛的矛盾。该算法全局搜索能力强、优化速度快，在动态变化 的环境中具有较强的适应能力，具有较好的优化效果。 ( 4 )根据求解多目标优化问题时一般要求，结合当前多目标优化算法的 研究状况，从增强和保持种群的多样性角度出发，采用多种群的方式，提出了一 种基于多种群和占优的多目标遗传算法，同时算法中采用占优的策略更新外 部种群。 1 4 论文创新点 论文创新点包括以下3 个： ( 1 )提出了一种新的求解动态优化问题的多种群遗传算法，该算法采用 了两个独立且不同进化机制的多种群方式同时进化，并在检查点进行个体的迁 移，从而缓解了群体多样性与群体收敛的矛盾。该算法全局搜索能力强、优化速 山东师范大学硕士学位论文 度快，在动态变化的环境中具有更强的适应能力，具有较好的优化效果。 ( 2 )根据求解多目标优化问题时一般要求，结合当前多目标优化算法的 研究状况，从增强和保持种群的多样性角度出发，采用多种群的方式，提出了一 种基于多种群和占优的多目标遗传算法，在算法中采用占优的策略更新外部 种群。 ( 3 )从优化问题的特征出发，分析了求解动态优化问题和多目标优化问 题的共同特征，指出维持种群的多样性是求解的关键，并设计了维持种群多样性 的多种群结构。 1 5 论文组织 论文共分为5 章，各章的内容和组织如下： 第一章首先对进化算法进行简单回顾，然后分析了进化算法的内涵、特点和 几种典型的进化算法，包括微粒群优化算法、蚁群优化算法和文化算法等，最后 介绍了论文的研究内容、创新点和组织。 第二章全面综述了遗传算法的相关概念以及选择算子、交叉算子、变异算子、 进化过程，并分析了遗传算法有关理论。综述了动态优化问题和多目标优化问题 的国内外研究现状。 第三章，提出了一种新的求解动态优化问题的多种群遗传算法，对算法原理 和过程进行了全面的描述，包括算法的多种群结构设计、算法流程图、算法描述 和仿真实验等。 第四章从分析求解多目标优化问题的一般要求，结合当前多目标优化算法的 研究状况，基于增强和保持种群的多样性方法，采用多种群的方式，提出了一种 基于多种群和占优的多目标遗传算法，介绍了算法的多种群结构设计、算法流 程图、算法描述和仿真实验等。 第五章对论文进行了总结，并指出了进一步研究方向。 6 山东师范人学硕= l ：学位论文 第二章遗传算法研究进展 近3 0 年以来，由于遗传算法求解复杂优化问题的巨大潜力及其在各个领域 应用的成功，这种算法受到了广泛的关注和研究。g a 是模拟自然界生物进化过 程与机制求解问题的一类自组织和自适应的人工智能技术，已广泛应用于计算机 科学、人工智能、信息技术及工程实践等诸多方面。 本章主要介绍了遗传算法的产生、遗传算法基本原理和方法、遗传算法的基 本理论、动态优化问题和多目标优化问题的研究现状。 2 1 遗传算法概述 2 1 1 遗传算法的产生 生命科学与工程等其他科学的相互交叉、相互渗透和相互促进是近代科学技 术发展的一个显著特点，而遗传算法的蓬勃发展正体现了科学发展的这一特征和 趋势。遗传算法是一类借鉴生物界自然选择和自然遗传机理的随机化搜索算法， 是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。直到1 9 7 5 年， 由美国m i c h i g a n 大学的j h o l l a n d 教授提出了具体的遗传算法思想【l a j 。j h o l l a n d 教授和他的研究小组围绕遗传算法进行研究的宗旨有两个：( 一) 抽取和解释自 然系统的自适应过程；( 二) 设计具有自然系统机理的人工系统。 遗传算法覆盖了三个主要研究领域：基本遗传算法的研究；用遗传算法进行 优化；带有分类系统的机器学习。它的主要特点是简单、通用、鲁棒性强，适用 于并行分布处理，应用范围广。 2 1 2 标准遗传算法( s g a ) h o l l a n d 的遗传算法常被称为标准遗传算法( s t a n d a r dg e n e t i ca l g o r i t h m ，简称 s g a ) ，s g a 的操作对象是一群二进制串( 称为染色体、个体) ，即种群 ( p o p u l m i o n ) ；这里每个染色体都对应于一个问题的解。从初始种群出发，采用 基于适应度比例的选择策略在当前种群中选择个体，使用交叉( c r o s s o v e r ) 和变 异( m u t a t i o n ) 操作来产生下一代种群。如此一代一代的进化下去，直到满足期 望的终止条件【5 j 。 s g a 的基本思想是从代表问题可能潜在解集的一个种群开始的，而一个种 群则由经过基因编码( g e n ec o d i n g ) 的一定数目的个体( i n d i v i d u a l ) 组成。每 个个体是带有特征的实体，称作染色体( c h r o m o s o m e ) 。染色体作为遗传物质的 7 m 东师范大学碗学位论文 主要载体，即多个基因的集合，决定了个体性状的外部表现。因此，在一开始需 要实现从表现型到基因型的映射即编码工作。初始种群产生后，按照适者生存、 优胜劣汰的原理，逐代( g e n e r a t i o n ) 演化产生出越来越好的近似解。在每一代， 根据问题域中个体的适应度( f i t n e s s ) 大小挑选( s e l e c t i o n ) 个体，并借助于自 然遗传学的遗传算子( g e n e t i co p e r a t o r s ) 进行组合、交叉( c r o s s o v e r ) 和变异 ( m u t a t i o n ) ，产生出代表新的解集的种群。这个过程将导致种群像自然进化一 样的后代比前代更加适应于环境，末代种群中的最优个体经过解码( d e c o d i n g ) ， 可以作为问题的近似最优解。图21 表示了标准遗传算法的过程。 问题域( 表现域) 图2 1 标准遗传算法的执行过程 标准遗传算法中包含了5 个基本要素： 参数编码； 初始群体的设定； 适应度函数的设定； 遗传操作设计； 山东师范大学硕上学位论文 控制参数设定( 主要是指群体大小和使用遗传操作的概率等) 。 而遗传操作中主要包括选择操作、交叉操作、变异操作。具体内容会在下面 章节中做详细的介绍。 2 1 3 遗传算法的特点 遗传算法具有十分顽强的鲁棒性，这是因为比起普通的优化搜索方法，它采 用了许多独特的方法和技术。归纳起来，主要有以下几个方面t ( 1 ) 遗传算法的处理对象不是参数本身，而是对参数集进行了编码的个体。 此编码操作，使得遗传算法可直接对结构对象进行操作。如：集合、序列、矩阵、 树、图、链表等，甚至三维结构形式的对象。 ( 2 ) 许多传统搜索方法都是单点搜索算法，即通过一些变动规则，使问题 的解从搜索空间中的当前解移动到另一解。相反，遗传算法是采用同时处理群体 中多个个体的方法，即同时对搜索空间中多个解进行评估。更形象地说，遗传算 法是并行的爬多座山。这一特点使遗传算法具有较好的全局搜索能力，减少了限 于局部最优解的风险，且易于并行化。 ( 3 ) 在标准遗传算法中，基本上不用搜索空间的知识或其他辅助信息，而 仅用适应度函数值来评估个体，并在此基础上进行遗传操作。需要指出的是，遗 传算法的适应度函数不仅不受连续可微的约束，而且其定义域是可以任意设定 的。 ( 4 ) 遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导它的 搜索方向。 上述这些具有特色的技术和方法使得遗传算法使用简单、鲁棒性强、易于并 行化，从而应用范围更广。 2 2 遗传算法基本原理和方法 2 2 1 遗传算法的数学描述 以标准遗传算法为例来说明一般遗传算法的数学描述。s g a 可被定义为一 个8 元组【6 l ： s g a = ( c j e po i 列，o ，rp ，t 、) 式中d 个体编码方法。s g a 使用固定长度的二进制符号串来表示群体中 的个体，其等位基因由二值符号集 o ，l 所组成，编码长度用l 表示。 b 个体适应度评价函数。以x 表示一个决策变量，即群体中的一个个体， f 【x ) 表示个体x 的适应度。 p 俨初始群体。 9 山东师范大学硕士学位论文 一群体规模。s g a 群体规模恒定，一般用n 表示群体中个体的数目。 中一选择算子。s g a 使用比例选择算子。 厂一交叉算子。s g a 使用单点交叉算子，交叉概率为心。 矽一变异算子。s g a 使用位均匀变异算子，变异概率为厶，第t 代个体x 的变异概率记为厶陇砂。 孓一遗传算法终止条件。s g a 实用r 作为终止进化代数。 遗传算法的具体运算过程如图2 2 所示【l o 】： 2 2 2 编码技术 图2 2 遗传算法运算过程 我们已知道，遗传算法主要是通过遗传操作对群体中具有某种结构形式的个 体施加结构重组处理，从而不断地搜索出群体中个体间的结构相似性，形成并优 化积木块以逐渐逼近最优解p 6 】。 2 2 2 1 编码( 译码) 评估规范和编码原理 定义2 1 ：由问题空间向g a 空间的映射称作编码( c o d i n g ) ，而由g a 空间 向问题空间的映射称作译码( d e c o d i n g ) 。 评估编码策略常采用以下3 个规范【1 1 】： 完备性( c o m p l e t e n e s s ) ：问题空间中的所有点( 候选解) 都能用g a 空间中 的点( 染色体) 表示 健全性( s o u n d n e s s ) ：g a 空间中的染色体能对应所有问题空间中的候选解。 非冗余性( n o n r e d u n d a n c e ) ：染色体和候选解一一对应。 应该注意的是，严格满足上述规范的编码方式和提高遗传算法的效率并无关 1 0 山东师范大学硕士学位论文 系。在有些场合，允许生成致死基因的编码，虽然这会导致冗余的搜索，但总的 计算量可能反而减少，从而可以更有效地找出最优解。 2 2 2 2 具体编码技术 1 一维染色体编码 所谓一维染色体编码是指搜索空间的参数转换到遗传空间后，其相应的基因 呈一维排列构成染色体。如： a , b ，c ，d ) 或 1 ，2 ，3 ，4 ) 。 一维染色体编码中最常用的符号集是二值符号集 o ，1 。基于此符号集的个 体称二值码串。二值编码是目前遗传算法中常用的编码方法，它具有以下的特点： ( 1 ) 简单易行； ( 2 ) 符合最小字符集编码原则； ( 3 ) 便于用模式定理进行分析，因为模式定理就是以二值编码为基础的。 但是，二值编码具有一定的映射误差，特别是它不能直接反映出所求问题的 本身结构特征，因此很难满足生成具有意义的积木块原则。目前，在一维编码以 后出现了许多新方法，其中包括实数表示、格雷码【1 2 】等。 2 多参数映射编码 在优化问题求解中常常会碰到多参数优化问题，对此类问题的遗传算法常采 用多参数编码。其基本思想是把每个参数先进行二值编码得到子串，再把这些子 串连成一个完整的染色体。 001 x l 010 日f 0 00 f 这是一个1 2 位二进制码串，其中包括3 个子串分别对应于x ，0 i ，咖f 。 一般来讲，多参数映射编码中的每一个子串对应各自的编码参数，所以可以 有不同串长度和不同的最大值和最小值。 3 离散化( d i s c r e t i z a t i o n ) 前述的多参数映射编码中曾提到t c ，2 1 到 u m i n ，u 。眦 的映射操作。实际 上，这是一种离散化操作，即将取值于 u m i n ，u 一 范围的实参数以长度为1 的二 进制码量化。在许多优化问题中，尤其是优化控制问题中，优化的不仅是一个控 制参数，而是一个连续的控制函数。在用遗传算法求解此类问题时，需要把问题 缩小成有限参数的形式后再对参数编码，即进行离散化。 4 可变染色体长度编码 在自然界生物进化过程中，越是高等生物其染色体越长，换句话说，生物进 化过程中，染色体的长度不是固定不变的。g o l d b e r g 等提出的一种称为 山东师范人学硕士学位论文 m e s s y g a 1 3 1 ( m g a ) 的遗传算法的编码方法就融进了这种机制。 m g a 有别于s g a ，它可以较好的克服s g a 对于非线性问题处理的弱点。 主要有以下几个特点： ( 1 ) 染色体长度可变； ( 2 ) 允许过剩制定( o v e r s p e c i f y ) 和缺省制定( u n d e r s p e c i f y ) ； ( 3 ) 基于切断( c u t ) 和拼接( s p l i c e ) 操作的交叉处理； ( 4 )分为二阶段的处理，即原始( p r i m o r d i a l ) 阶段和并立或对接 ( j u x i a p o s i t a t i o n a l ) 阶段。 父代1 111 1 11111专 子代1 111 1 000 父代2 00 000o l o00- - ) 子代2 00000o l l11111 切断 拼接 需要指出的是m g a 与s g a 不同，不一定要把所有的信息都用基因表现出 来，因此染色体的长度或表示个体的表的长度是可变的。 5 二维染色体编码 在许多应用场合，问题的解呈二维或多维的表示。此时，若采用一维染色体 编码则很不方便，尤其是交叉操作很不直观。这种场合宜采用二维、多维编码。 例如在图像恢复中的应用。采用二维染色体编码所对应的交叉操作也不同于一般 的交叉操作，这里可采用纵横交叉和窗口交叉的方式。 6 树结构编码 上述若干编码方式有其相应的缺点： ( 1 ) 个体的表示很难反映求解问题的本身结构或者层次； ( 2 ) 需要特定的编码和译码技术，把问题的解表示成合适的形式； ( 3 ) 不易表示高层次知识及相应的学习系统。 在实际应用中，许多问题本身可以采用结构描述。比如：人工智能中知识获 取和提炼采用的语义网络；神经网络中神经元连接状态表示图等。因此，可直接 把问题的结构表示作为染色体来处理，从而省去编码和译码操作【1 4 】。 这里先介绍对树进行的4 个操作： 0 【l ：父子分割 1 2 2 ：父子合并 d l ：兄弟分割 d 2 ：兄弟合并 1 2 山东师范人学硕1 ：学位论文 2 2 3 适应度函数 纨睾汆 九“蛆矛 7 太v 个兰公 八弧。八 图2 2 仅p 操作 在遗传算法中，适应度函数用来评价群体中个体( 问题的解) 的优劣程度。 一般情况下，适应度越高的个体越好，适应度越低的个体越差。在遗传算法的设 计中，经常用到两种适应度函数：原始适应度函数和标准适应度函数。 原始适应度函数是指采用问题的目标函数作为适应度函数，它经常用于极大 值求解问题。然而在许多问题中，求解目标更多地表示为某个函数的极小值求解， 这时需要把极小值问题转化为标准的形式，即转化为极大化情形且适应度值非 负。它有以下三种转化形式： rc 一一f ( x ) l ( 1 ) f i x ) = i o l = f “黝 = _ 当j ( x ) 0 其它 当( x ) + 1 0 其它 其中：f 【x ) 是适应度函数；_ ( x ) 是问题的目标函数；c 一可以是一个合适的 输入值，也可以是k 代进化过程中“( x ) 的最大值或当前群体中j ( x ) 的最大值； c 胁可以是合适的输入值，或者是当前一代或前k 代中口( x ) 的最小值。 在应用比例选择时，遗传算法早期群体中出现的超级个体( 适应度远远超过 1 3 山东师范人学硕士学位论文 群体平均适应度的个体) 会由于在群体中过多地复制，而导致早熟收敛；而且在 遗传算法的后期群体平均适应度与最优实验值太过接近时，会导致停滞现象。 处理遗传算法早熟和停滞问题的一个措施就是对适应度函数进行比例变换。 目前常用的适应度函数的比例变换方法主要有三种： ( 1 )线性比例变换：f ( x ) = 0 【职) + p ( 2 ) 幂比例变换：f ( x ) = f i x ) 伍 ( 3 ) 指数比例变换：f i x ) = e x p 一p f f x ) 】 其中：f i x ) 是进行比例变换后的适应度函数；f 【x ) 是未经变换的适应度函数； 0 【，d 是系数。 上述三种i ：l f f l j 变换中，指数比例既可以让非常好的染色体串保持多的复制机 会，同时又限制了其复制数目以免其很快控制整个群体，而且也提高了相近染色 体串之间的竞争性。系数决定了选择的强制性，其值越小，选择强制就越趋向于 那些适应度高的染色体串，因此指数比例变换较为常用。 2 2 4 遗传操作 遗传操作是模拟生物基因遗传的操作。在遗传算法中，通过编码组成初始群 体后，遗传操作的任务就是对群体中的个体按照它们对环境适应的程度( 适应度 评估) 施加一定的操作，从而实现优胜劣汰的进化过程。从优化搜索的角度而言， 遗传操作可使问题的解，一代又一代地优化，并逼近最优解。 遗传算法遗传操作包括以下三个基本遗传算子( g e n e t i co p e r a t o r ) ：1 选择 ( s e l e c t i o n ) ；2 交叉( c r o s s o v e r ) ；3 变异( m u t a t i o n ) 。这三个遗传算子有如下 特点： ( 1 ) 这三个遗传算子的操作都是在随机扰动情况下进行的。 ( 2 ) 遗传操作的效果和上述三个遗传算子所取的操作概率、编码方式、群 体大小、初始群体以及适应度函数的设定密切相关。 ( 3 )三个基本遗传算子的操作方法或操作策略随具体求解问题的不同而 异。 2 241 选择算子 从群体中选择优胜的个体，淘汰劣质个体的操