（计算机应用技术专业论文）改进的遗传算法及其在多目标优化中的应用研究(1).pdf

摘要遗传算法是模拟生物界的进化过程而产生的一种现代优化算法，作为一种有效的随机搜索方法，在优化方法中具有独特的优越性，有着非常重要的理论意义和广泛的应用领域。传统优化方法对目标函数解析性质要求较高，进化算法不需要目标函数的导数信息，具有隐式并行性，所以常用于一些复杂的、大规模的、非线性、不可微的求解优化问题。本文介绍了遗传算法的发展概况。通过实例分析了基本遗传算法的实现步骤；对遗传算法的理论基础进行介绍分析讨论，包括模式定理，积木块假说，内在并行性，w a l s h 模式变换和欺骗问题等；对典型和近期发表文章所提出的一些改进策略作了总结和分析比较；提出了对遗传操作算子的改进策略，在具体问题中结合相应的特点再作相应的改进，通过线性规划问题、网络路径优化问题和典型的n p 难一t s p 问题等算例的验证，结果表明，算法是有效的，能得到较好的结果，同时也提高了算法的效率。多目标优化问题一直是科学和工程研究领域的一个难点和热点问题，在遗传算法应用到这一领域以前，已经产生了许多经典的方法，但在处理一些大型、复杂问题上存在着不足，遗传算法正好能弥补这个不足。在具体问题上，遗传算法与多目标优化问题的结合中最关键的问题是如何在种群中通过多个目标来评价个体的好坏。本文引入了堆排序机制，并应用到问题的求解过程中，通过两个算例的模拟，结果表明，该算法能求出比较合理的p a r c t o 最优解集，表明了其有效性。关键词：遗传算法；d i j k s t r a 算法：p a r e t o 最优解；多目标优化a b s t r a c tg e n e t i ca l g o r i t h m sa r en e wk 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 r ei 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 ea d v a n t a g e so v e rt h 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 eo ft h eg 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 t h 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 su s u a l l yh a v es t r i c tl i m i t a t i o no nt h ef u n c t i o n ss u c ha st h e i rd i f f e r e n t i a b i l i t y , h o w e v e r ，e v o l u t i o n a r ya l g o r i t h m sd on o tr e q u i r et h ed i f f e r e n t i a b i l i t yo ft h ef u n c t i o n sa n dh a v ep a r a l l e lp r o p e r t y , t h e r e f o r e ，t h e ya r eo f t e nb eu s e dt os o l v es o m ec o m p l e x ，l a r g es c a l e ，n o n l i n e a ra r i dn o t l - d i f f e r e n t i a b l eo p t i m i z a t i o np r o b l e m s t h i sp a p e ri n t r o d u c e st h eg e n e r a ls i t u a t i o no fg e n e t i ca l g o r i t h m sa n da n a l y z e st h ei m p l e m e n t a t i o ns t e p s ：d i s c u s s e st h et h e o r yf o u n d a t i o na b o u tg e n e t i ca l g o r i t h m s ，i n c l u d i n gs c h e m at h e o r e m ，b u i l d i n gb l o c kh y p o t h e s i s ，i m p l i c i tp a r a l l e l i s m ，t h et r a n s f o r mo fw a l s hs c h e m aa n dd e c e p t i v ep r o b l e me t c ：s u m su ps o m et y p i c a la n dl a t e s ti m p r o v e m e n t ss t r a t e ：g i e s ak i n do fg e n e r a li m p r o v e m e n ti no p e r a t o r so fg e n e t i ca l g o r i t h mi sp r e s e n t e d ，c o m b i n i n gs o m ec o n c r e t ef e a t u r e s ，s u c ha sn o n l i n e a rp r o g r a m m i n g n e t w o r k sp a t ho p t i m i z a t i o na n dt s pp r o b l e m s i m u l a t i o nr e s u l t ss h o wt h ei m p r o v e da l g o r i t h m sa r ef e a s i b l e ，a n de n h a n c et h ee f f i c i e n c ya tt h es a m et i m e m u l t i o b j e c t i v eo p t i m i z a t i o nh a sb e e nad i f f i c u l tp r o b l e ma n df o c u sf o rr e s e a r c hi nf i e l d so fs c i e n c ea n de n g i n e e r i n g t h e r ea l r e a d yh a v eal o to fc l a s s i c a lm e t h o d sf o rs o l v i n gm 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 sb e f o r ee v o l u t i o n a r ya l g o r i t h m sw e r ei n t r o d u c e d c l a s s i c a lm u l t i o b j e c t i v eo p t i m i z a t i o nm e t h o d sh a v eb e e nt h o r o u g h l yd e v e l o p e d ，b u tt h e r ea r es t i l ll o t so fs h o r t c o m i n g si ns o l v i n gh i 曲d i m e n s i o na n dl a r g e s c a l ep r o b l e m s ，w h i c hc a nb e ，s o l v e db yg a s t os o m ec o n c r e t ep r o b l e m s ，t h ek e yi s s u ei nc o m b i n i n gg e n e t i ca l g o r i t h mw i t hm u l t i - o b j e c t i v eo p t i m i z a t i o ni sh o wt og r a d eai n d i v i d u a li nap o p u l a t i o nb ym u l t i o b j e c t s t h i sp a p e rp r e s e n t sc o n e - s o r t i n gc o n c e p ta n da p p l i e si tt op r a c t i c a lp r o b l e m sp r o c e s s i n g ，t h es i m u l a t i o nr e s u l t si n d i c a t et h ei m p r o v e da l g o r i t h m sc a nf i g u r eo u tt h ep a r e t o o p t i m a ls o l u t i o ns e t ，a n ds h o wt h ea l g o r i t h m sa r ep r a c t i c a l k e yw o r d s ：g e n e t i ca l g o r i t h m ，d i j k s t r aa l g o r i t h m ，p a r e t o - o p t i m a ls o l u t i o n 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 n2独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他入已经发表或撰写过的研究成果，也不包含为获得云挂王些盘堂或其他教育机构的! 敞骧证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。学位论文作者签名：咒夸譬签字日期：d 年7 月c ) u 目学位论文版权使用授权书本学位论文作者完全了解丞i 耋互些盍堂有关保留、使用学位论文的规定。特授权丞洼王些太堂可以将学位论文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。( 保密的学位论文在解密后适用本授权说明)学位论文作者签名：；琦廖导师签名：签字日期：盯年阴汐日签字r 期：时年，月) 口日学位论文的主要创新点一、本文在总结现有的一些对基本遗传算法的改进策略的基础上，对遗传操作算子提出了一些改进的策略，通过相关算例验证了其有效性。其中的网络最短路径算例构造了一个相对通用的平台。在求解t s p 的算例中，结合d i j k s t r a 算法，提出了启发邻接矩阵算子，应用到算例中能使问题得到更好的结果。三、在多目标优化问题中，在r w g a 的基础上，引入了堆排序概念，有利于种群中的优秀个体的选择，通过算例，能较好的求出问题的p a r e t o 解。第一章引言第一章引言1 1 论文课题研究的目的和意义遗传算法是生命科学与工程科学互相交叉、互相渗透的产物。遗传算法的产生是受启发于自然界的生物从低级到高级，从简单到复杂这样一个漫长的进化过程。其遵循的原则就是达尔文的进化论，优胜劣汰、适者生存；其本质是一种求解问题的高度并行性全局搜索算法。它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求的最优解。人们对遗传算法兴趣的日益增长有两个背景：其一是工程领域，特别是人工智能与控制领域，不断涌现出超大规模的非线性系统，在这些系统的研究中存在着大量的经典优化方法所不能有效求解的优化问题；其二，遗传算法本身就是一种模拟自然演化的学习过程的求解问题方法，它能以独立的或与其他方法相结合的形式用于智能机器学习系统的设计中。经过近1 0 余年的努力，遗传算法不论是在应用上、算法设计上，还是在基础理论上，均取得了长足的发展，已成为信息科学、计算机科学、运筹学和应用数学等诸多学科所共同关注的热点研究领域1 2 。多目标优化是实践中广泛存在的一种优化问题，它的理论研究已经取得了一些进展，但是在算法上还不太成熟。一种求解方法是将各个目标加权，从而将多目标问题转化为单目标问题。但加权法有以下缺点：1 不同性质的目标之问单位不一致，不易做比较；2 各目标加权值具有较大的盲目性；3 各目标之间相互制约往往存在互相矛盾的目标，致使加权目标函数的拓扑结构变得十分复杂。另一种方法是求多目标规划问题的非劣解( p a r e t o 意义下的最优解) ，供决策者从中选择。1 9 8 5 年，s c a f f e r 提出了第一个多目标遗传算法【3 l ，从而开创了用遗传算法求解多目标规划的先河，以后逐渐出现了许多多目标遗传算法。有代表性的算法有，f o n s e c a 等人提出的基于排序选择的“多目标遗传算法( m o g a ) ”，h o m等人提出的基于小生镜( n i c h e ) 技术的“小生镜p a r e t o 遗传算法”。如阿表示多个目标之间的关系，在算法实践中就成为一个难点，但同时它也是重点p 4 1 。g o l d b e r g 等提出一种p a r e t o 排序算法娜“，其困难是计算量较大，效率较低，而且采用这种方法难以体现出遗传算法较其它算法的优越性和模式定理在遗传算法设计中的原则性、指导性意义。第一章引吉1 2 本文所做的工作本文主要对遗传算法的改进、应用实例和多目标优化问题作的探讨和研究。具体工作如。卜i ：1 、总结遗传算法的发展历程和发展趋势，透析基本遗传算法的具体描述、运算过程和实现技术，分析遗传算法的研究内容、应用领域和最新进展。2 、从遗传操作算子出发，对基本遗传算法提出一些可行的改进策略，给出文本和类语言的具体描述，并对一些典型的算例进行仿真，在对t s p 问题的仿真中，与d i j k s t r a 算法( 启发邻接矩阵算子) 相结合。验证了算法的有效性，并具有较高的效率。3 、介绍多目标优化的基本概念、现状和特点，对传统的多目标优化方法进行总结并分析其优点和存在的局限性。引用堆排序机制，并应用到多目标优化的求解的算例中，证明该改进算法是有效的。第一二章遗传算法理论概述第二章遗传算法理论概述遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机化的搜索算法，是在2 0 世纪6 0 年代末至7 0 年代初期，主要由美国m i e h i g a n 大学的j o h nh o i1 a n d 与其同事、学生们研究形成的一个较为完整的理论和方法。在随后的近3 0 年的不断发展中，取得了丰硕的应用成果和理论研究的进展。随着生命科学与工程科学的相互交叉、相互渗透和相互作用的发展，并逐渐成为科学技术发展的一个显著的特点，遗传算法的蓬勃发展j 下代表着这一发展趋势和顺应了科技发展的需求。遗传算法尤其使用于处理传统搜索方法难以解决的复杂和非线性问题，可广泛应用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域，是2 1 世纪有关智能计算中的关键技术和研究热点。2 1 生物进化与遗传2 1 1 生物进化地球上的生物都是经过长期进化而不断形成的，主要表现为：不断繁殖、生存竞争、适者生存、遗传与变异这几种现象。生物上下代之间传递着遗传信息的物质，称作遗传物质。绝大多数生物的遗传物质是d n a ，由于细胞里的d n a 大部分在染色体上，因此，遗传物质的主要载体为染色体。而基因是控制生物遗传的物质单元，它是遗传效应的d n a 片段。脱氧核苷酸在染色体上的排列顺序代表着遗传信息。遗传的规律有分离规律，自由组合规律两种。而生物的变异有三种来源：基因重组，基因突变，染色体变异。关于进化理论的一般特性已广为人们所接受吼1 进化过程发生在染色体上，而不是发生在它们所编码的生物体上。2 自然选择把染色体以及由它们所译成的结构的表现联系在一起，那些适应性好的个体的染色体经常比差的个体的染色体有更多的繁殖机会。3 变异可以使生物体子代的染色体不同于父代染色体。通过结合两个父代染色体中的物质，重组过程可以在子代中产生有很大差异的染色体。4 有关产生个体的信息包含在个体所携带的染色体的集合及染色体编码结构之中，这些个体会能很好的适应环境。自然界生物体通过自身的演化能使问题得到完好的解决。计算机科学家为了某个算法可能耗费数月以至数年的努力，而生物体通过演化和自然选择这种第二章遗传算法理论概述非定向机制达至0 了目的。遗传算法就是借助生物进化的规律，通过繁殖，遗传，变异，竞争，实现优胜劣汰，一步一步的逼近问题最优解。因此，遗传算法又称为进化计算。2 1 2 生物进化与遗传算法及基本概念遗传算法对生物进化模型的模拟：假没对自然界中的一群人的一个种群进行操作，第一步的选择以现实世界中的优胜劣汰现象为背景；第二步的重组交叉则相当于人类的结婚和生育；第三步的变异则与自然界中偶然发生的变异是一致的。人类偶然出现的返祖现象便是一种变异。由于包含着对模式的操作，遗传算法不断的产生出更加优良的个体，正如人类向前进化一样。所采用的遗传操作都与生物尤其是人类的进化过程相对应。由于遗传算法是自然遗传学和计算机科学相互结合渗透而成的新的计算方法，所以遗传算法中经常使用有关自然进化中的一些基础用语。下面介绍一些对遗传算法的学习和理解有重要意义的相关术语”。染色体( c h r o m o s o m e )生物细胞中含有的一种微小的丝状化合物。它是遗传物质的主要载体，由多个遗传因子一一基因组成。脱氧核糖核酸( d n a )控制并决定着生物遗传性状的染色体中的主要部分。遗传因子( g e n e )是控制生物性状的遗传物质的功能单位和结构单位，复数个基因就是染色体。基因座( 1 0 c u s )遗传基因在染色体中所占的位置。个体( 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 it n e s s )各个体对环境的适应程度叫做适应度。表现型( p h e n o t y p e )指生物个体所表现出来的性状。基因型( g e n e t y p e )指与表现型密切相关的基因组成。2 2 遗传算法的基本思想遗传算法是从代表问题可能潜在的一个种群开始的，而一个种群则由经过基因编码的一定数目的个体组成。每个个体实际上就是染色体带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的组合，其内部表现是某种基因组合，它决定了个体的性状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的4第一二章遗传尊法理论概述映射即编码工作。出于仿照基因编码的工作很复杂，往往需要进行简化，如二进制编码。初始代种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近似解。在每一代，根据问题域中个体的适应度大小挑选个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的群体。这个过程将导致种群象自然进化一样的后生代种群比前代更加适应环境，末代种群中的最优个体经过解码，可以作为问题近似最优解。遗传算法采纳了自然进化模型，如选择、交叉、变异等等。计算开始时，一定数目n 个个体( 父个体1 、父个体2 、父个体3 、父个体4 、) 即种群随机的初始化，并计算每个个体的适应度函数，第一代也即初始代产生了。如果不满足优化准则，开始产生新一代的计算。为了产生下一代，按照适应度选择个体，父代要求基因重组( 交叉) 而产生子代。所有的子代按一定概率变异。然后子代的适应度又被重新计算，子代被插入到种群种将父代取而代之，构成新的代( 予个体1 、子个体2 、子个体3 、子个体4 ) 。这一过程循环执行，直到满足优化准则为止。2 3 遗传算法基本要素g a 通常包含5 个基本要素：1 、参数编码：g a 是采用问题参数的编码集进行工作的，而不是采用问题参数本身，通常选择二进制编码。2 、初始种群设定：g a 随机产生一个出n 个染色体组成的初始种群( p o p u l a t i o n ) ，也可根据一定的限制条件来产生。种群规模是指种群中所含染色体的数目。3 、适值度函数的设定：适值度函数是用来区分种群中个体好坏的标准，是进行选择的唯一依据。目前主要通过目标函数映射成适值度函数。4 、遗传操作设计：遗传算子是模拟生物基因遗传的操作，遗传操作的任务是对种群的个体按照它们对环境的适应的程度施加一定的算子，从而实现优胜劣汰的进化过程。遗传基本算子包括：选择算子，交叉算子，变异算子和其他高级遗传算子。5 、控制参数设定：在g a 的应用中，要首先给定一组控制参数：种群规模，杂交率，变异率，进化代数等。第一二章遗传算法理论概述2 4 遗传算法的研究概况2 4 1 遗传算法研究概述遗传算法研究的兴起是在8 0 年代末和9 0 年代初期，但它的历史起源可追溯到6 0 年代。1 9 6 7 年，b a g l e y 在他的论文中首次提出了遗传算法( g e n e t i ca l g o r i t h m ) 这一术语，并讨论了遗传算法在自动博弈中的应用。他所提出的包括选择、交叉和变异的操作己与目前遗传算法中的相应操作十分接近，尤其是他对选择操作做了十分有意义的研究。他认识到，在遗传进化过程的前期和后期，选择概率应合适地变动。为此，他引入了适应度定标( s c a l i n g ) 概念，这是目前遗传算法中常用的技术【”。同时，他也首次提出了遗传算法自我调整概念，即把交叉和变异的概率融于染色体本身的编码中，实现算法自我调整优化。第个把遗传算法用于函数优化的是h o l l s t i e n 。1 9 7 1 年他在论文计算机控制系统中的人工遗传自适应方法中阐述了遗传算法用于数字反馈控制的方法【1 。1 9 7 5 年在遗传算法研究的历史上是十分重要的一年。这一年，h o l l a n d出版了他的著名专著自然系统和人工系统的适配f 1 1 j 。该书系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极为重要的模式理论( s c h e m a t at h e o r y ) 。该理论首次确定了结构重组遗传操作对于获得内在并行性的重要性。同年d e j o n g 完成了他的重要论文遗传自适应系统的行为分析 1 1 1o 他在浚论文中所做的研究工作可看作是遗传算法发展进程中的一个里程碑，这是因为他把h o l l a n d 的模式理论与他的计算实验结合起来。尽管d e j o n g 和h o l l s t i e n 一样主要侧重于函数优化的应用研究，但他将选择、交叉和变异操作进步完善和系统化，同时又提出了诸如代沟( g e n e r a t i o ng a p ) 等新的遗传操作技术。可以认为，d e j o n g 的研究工作为遗传算法及其应用打下了坚实的基础。进入8 0 年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。尤其是遗传算法的应用研究显得格外活跃，不但它的应用领域扩大，而且利用遗传算法进行优化和规则学习的能力也显著提高，同时产业应用方面的研究也在摸索之中。此外一些新的理论和方法在应用研究中亦得到了迅速的发展，这些无疑都给遗传算法增添了新的活力。2 4 2 遗传算法研究的新动向随着应用领域的不断发展，遗传算法的研究出现了几个引人注目的新动向：1 基于遗传算法的机器学习( g e n e t i cb a s em a c h i n el e a r n i n g ) ，这一新的研究课题把遗传算法从历来离散的搜索空间的优化搜索算法扩展到具有独特的规第二章遗传算法理论概述则生成功能的崭新的机器学习算法。这一新的学习机箭对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望。2 遗传算法正目益和神经网络、模糊推理以及浞沌理论等其它智能计算方法相互渗透和结合。这对开拓2 1 世纪中新的智能计算技术将具有重要的意义。3 并行处理的遗传算法的研究十分活跃。这一研究不仅对遗传算法本目的发展，而且对于新一代智能计算机体系结构的研究都是十分重要的。4 遗传算法和另一个称为人工生命的崭新研究领域正不断渗透。所谓人工生命即是用计算机模拟自然界丰富多彩的生命现象，其中生物的自适应、进化和免疫等现象是人工生命的重要研究对象。两遗传算法在这方面将会发挥一定的作用。5 遗传算法和进化规划( e v a l u a t i o np r o g r a m m i n g ，e p ) 以及进化策略( e v 0 1 u t i o ns t r a t e g y ，e s ) 等进化计算理论日益结合。e p 和e s 几乎是和遗传算法同时独立发展起来的，同遗传算法一样，它们也是模拟自然界生物进化枫制的智能计算方法，既同遗传算法具有相同之处，也有各自的特点。目前，这三者之问的比较研究和彼此结合的探讨正形成热点。6 遗传算法在数据挖掘( d a t am i n i n g ) 领域中的应用。数据挖掘是揭示存在于数据里的模式及数据间的关系的学科，它强调对大量观测到的数据库的处理。它是涉及数据库管理，人工智能，机器学习，模式识别，统计学，及数据可视化等学科的边缘学科。数据挖掘中常用的技术有人工神经网络、遗传算法、决策树、近邻算法和规则推导等。目前众多的学者研究如何有效地利用遗传算法方法来实现数据搜索。随着遗传算法研究和应用的不断深入和发展，一系列以遗传算法为主题的国际会议十分活跃。从1 9 8 5 年开始，国际遗传算法会议，即i c g a ( i n t e r n a t i o n a lc o n f e r e n c eo ng e n e t i ca l g o r i t h m ) 每两年举行一次。在欧洲，从1 9 9 0 年也开始每隔一年举办一次类似的会议，即p p s n ( p a r a u e lp r o b l e ms o l v i n gf r o mn a t u r e )会议。除了遗传算法外，大部分有关e s 和e p 的学术论文也出现在p p s n 中。另外，以遗传算法的理论基础为中心的学术会议有f o g a ( f o u n d a t i o no fg e n e t i ca l g o r i t h m ) 。它也是从1 9 9 0 年开始，隔年召开一次。这些国际学术会议论文集中反映了遗传算法近些年来的最新发展和最新动向。第二章基本遗传算法第三章基本遗传算法3 1 简单函数优化实例考虑下列一元函数求最大值问题【8 l ：，( z ) ；x s i n ( 1 0 j r x ) + 2 0x 一1 ，2 ( 3 - 1 )由于， ) 在区间【一1 ，2 】上可微，我们首先用微分法求取f ( x ) 的最大值。， ) 2s i n ( 1 0 n ? x ) + 1 0 w x c o s ( 1 0 g x ) = 0( 3 - 2 )即t a n ( 1 0 s r z ) = 一1 0 厅x( 3 3 )上式的解有无穷多个：铲等蝎扣mx 0 = 0( 3 - 4 )铲等螺，f = 坤，a式中s ，( i = 1 , 2 ，a 及f = 一1 ，一2 ，a ) 是一接近于0 的实数递减序列。当l 为奇数时，x i 对应局部极大值点，i 为偶数时，x 对应局部极小值点a显然z 。，即为区间 一1 ，2 内的最大值点：x 1 9 = 3 7 2 0 + = 1 8 5 + s 1 9( 3 - 5 )此时，函数最大值，0 。，) 比，( 1 8 5 ) = 3 8 5 稍大。下面用遗传算法的基本操作步骤解决上述简单函数的最优化问题。3 1 1 编码变量x 作为实数，可以视为遗传算法的表现型形式。从表现型到基因型的映射称为编码。通常采用二进制编码形式，将某个变量值代表的个体表示为一个( 0 ，1 ) 二进制串。当然，串长取决于求解的精度。如果设定求解精确到6 位小数，由于区间长度为2 一( 一1 ) = 3 ，必须将闭区间 _ l ，2 分为3 1 0 6 等份。因为2 0 9 7 1 5 2= 2 “ 表示实数值0 6 3 7 1 9 7 。x ；( 1 0 0 0 1 0 111 0 11 0 1 0 1 0 0 0 11 d 2 = 2 2 8 8 9 6 7x 一，o + 2 z s s 9 a 7 高= o s s 7 研二进制串 与 ，则分别表示区间的两个端点值一1 和2 。3 1 2 产生初始种群一个个体由串长为2 2 的随机产生的二进制串组成染色体的基因码，我 f a l以产生一定数目的个体组成种群，种群的大小( 规模) 即是指种群中的个体数目。3 1 3 计算适应度对于个体的适应度计算，考虑到本例目标函数在定义域内均大于o ，而且是求函数最大值，所以就引用目标函数作为适应度函数：，0 ) = ， )( 3 - 8 )这里二进制串s 对应变量x 的值。例如，有三个个体的二进制串为：s 12 s ，= ( 0 0 0 0 0 0 1 “0 0 0 0 0 0 0 0 1 0 0 0 0 5 32 分别对应于变量值工i = 0 6 3 7 1 9 7 ，戈2 0 9 5 8 9 7 3 ，x 3 = 1 6 2 7 8 8 8 ，个体适应度计算如下：f ( s 。) = 厂 ，) = 2 5 8 6 3 4 5，0 ：) - ，2 ) = 1 0 7 8 8 7 8f ( s 3 ) = f ( x 3 ) i3 2 5 0 6 5 0显然，三个个体中而的适应度最大，s ，为最佳个体。9第三章基本遗传算法3 1 4 遗传操作下面介绍交叉和变异这两个遗传操作是如何工作的。交叉操作：经过选择操作的两个个体，首先执行单点交叉，如：s 2 = 0 0 0 0 00 1i1 0 0 0 0 0 0 0 0 1 0 0 0 0 )5 3 2 随机选择一个交叉点，例如第5 位与第6 位之间的位置，交叉后产生新的子个体：s 2 _ 如2 这两个子个体的适应度分别为：厂0 2 ) = f ( - o 9 9 8 1 1 3 ) 1 9 4 0 8 6 5f ( s 3 ) - f ( 1 6 6 6 0 2 8 ) a3 4 5 9 2 4 5由上可知，个体屯的适应度比其两个父个体的适应度高。变异操作：假设已经以一小概率选择了s ，的第5 个遗传因子( 即第5 位) 变异，遗传因子由原来的0 变为l ，产生新的个体为s ，= ，计算该个体的适应度：f ( s 。) = ，( 1 7 2 1 6 3 8 ) = 0 9 1 7 7 4 3 ，发现个体的适应度比其父个体的适应度减少了，但是如果选择第1 0 个遗传因子变异，产生新的个体s ，”= ，f ( s 3 ”) = ，( 1 ，6 3 0 8 1 8 ) = 3 3 4 3 5 5 5 ，又发现个体s 3 ”的适应度比其父个体的适应度改善了。表3 - 1 模拟世代的种群中最佳个体的演变情况( 15 0 代终止)世代数个体的二进制串工适应度11 0 0 0 1 11 0 0 0 0 1 0 i1 0 0 0 111 l1 8 3 1 6 2 43 5 3 4 8 0 640 0 0 0 0 1 1 0 1 1 0 0 0 1 0 1 0 0 1 “11 8 4 2 4 1 63 7 9 0 3 6 271 1 1 0 i 0 1 0 1 1 1 0 0 1 1 1 0 0 1 1 1 11 8 5 4 8 6 03 8 3 3 2 8 01 l0 l 1 0 1 0 1 0 1 1 1 0 0 1 1 1 0 0 1 1 1 l1 8 5 4 8 6 03 8 3 3 2 8 61 71 0 l o l o l l l l l l 0 1 0 0 1 l l l1 8 4 7 5 3 63 8 4 2 0 0 41 80 0 0 0 l l l 0 1 1 1 1 1 1 0 1 0 0 1 1 1 11 8 4 7 5 5 43 8 4 2 1 0 23 4l i 0 0 0 0 1 1 0 1 1 l 1 0 1 1 0 0 1 1 1 l1 8 5 3 2 9 03 8 4 3 4 0 24 0l l o l 0 0 1 0 0 0 1 0 0 0 1 1 0 0 1 1 1 l1 8 4 8 4 4 33 8 4 6 2 3 25 4】0 0 0 1 1 0 1 i 0 1 0 0 0 1 1 0 0 1 1 1 8 4 8 6 9 93 ，8 4 7 1 5 57 10 1 0 0 儿o l l 0 0 0 1 0 1 1 0 0 1 1 l l1 8 5 0 8 9 73 8 5 0 1 6 28 91 1 0 1 0 0 1 1 1 1 1 1 0 0 1 1 0 0 1 1 1 11 8 5 0 5 4 93 8 5 0 2 7 41 5 01 1 0 1 0 0 1 1 1 1 1 1 0 0 1 1 0 0 1 1 1 11 8 5 0 5 4 93 8 5 0 2 7 41 0第三章基本遗传算法3 1 5 模拟结果设定种群大小为5 0 ，交叉概率p 。= o 2 5 ，变异概率p 。= o 0 1 ，按照上述的基本遗传算法( s i m p l eg e n e t i ca l g o r it h m ，s g a ) ，在运行到8 9 代时获得最佳个体：s 。；2 石= 1 8 5 0 5 4 9 ，f ( x 。，) ，3 8 5 0 2 7 4 这个个体对应的解与微分法预计最优解的情况最吻合，最大函数值比3 8 5 略大，可以作为问题的近似最优解。表3 一l列出了模拟世代的种群中最佳个体的演变情况。3 ，2 编码h o l l a n d 提出的遗传算法是采用二进制编码来表象个体的遗传基因型的，它使用的编码符号由二进制符号0 和1 组成的，因此实际的遗传基因型是一个二进制符号串，其优点在于编码、解码操作简单，交叉、变异等遗传操作便于实现，而且便于利用模式定理进行理论分析等；其缺点在于，不便于反映所求问题的特定知识，对于一些连续函数的优化问题等，也出于遗传算法的随机特性而使得其局部搜索能力较差，对于一些多维、高精度要求的连续函数优化，二进制编码存在着连续函数离散化时的映射误差，个体编码串较短时，可能达不到精度要求；而个体编码串的长度较长时，虽然提高精度，但却会使算法的性能降低。后来许多学者对遗传算法的编码进行了多种改进，例如，为提高遗传算法局部搜索能力，提出了格雷码( g r e yc o d e ) 编码；为改善遗传算法的计算复杂性、提高运算效率，提出了浮点数编码、符号编码方法等。为便于利用求解问题的专门知识，便于相关近似算法之间的混合使用，提出了符号编码法；此外还有多参数级联编码和交叉编码方法，近年来，随着生物计算理论研究的兴起，有人提出b n a 编码法，并在模糊控制器优化中的应用中取得了较好的效果。理论上，编码应该适合要解决的问题，而不是简单的描述问题。b a l a k r i s h m a n等较全面地讨论了不同编码方法的一组特性，针对一类特别的应用，为设计和选择编码方法提供了指南，主要有以下九个特性：1 完全性( c o m p l e t e n e s s )原则上，分布在所有问题域的解都有可能被构造出来。2 封闭性( c l o s u r e )每个基因编码对应一个可接受的个体，封闭性保证系统从不产生的无效的个体。3 紧致性( c o m p a c t n e s s ) 若两种基因编码g l 和9 2 都被解码成相同的个体，若g l 比9 2 占的空间少，就认为9 1 比9 2 紧致。4 可扩展性( s c a l a b i l i t y ) 对于具体问题，编码的大小确定了解码的时间，第三章基本遗传算法两者存在一定的函数关系，若增加一种表现型，作为基因型的编码大小也做出相应的增加。5 多重性( m u l t i p l ic i t y ) 多个基因型解码成一个表现型，即从基因型到相应的表现型空间是多对的关系，这是基因的多重性。若相同的基因型被解码成不同的表现型，这是表现型多重性。6 个体可塑性( f l e x i b i l i t y ) 决定表现型与相应给定基因型是受环境影响的。7 模块性( m o d u l a r i t y ) 若表现型的构成中有多个重复的结构，在基因型编码中这种重复是可以避免的。8 冗余性( r e d u n d a n c y ) 冗余性能够提高可靠性和鲁棒性( r o b u s t n e s s ) 。9 复杂性( c o m p e x i t y ) 包括基因型的结构复杂性，解码复杂性计算时空复杂性( 基因解码、适应值、再生等) 。3 3 适应度函数及其尺度变换遗传算法在进化搜索中基本不利用外部信息，仅以适应度函数( f i t n e s sf u n c t i o n ) 为依据，利用种群中每个个体的适应度值来进行搜索。因此适应度函数的选取至关重要，直接影响到遗传算法的收敛速度以及能否找到最优解。一般而言，适应度函数是由目标函数转换而成的。对目标函数值域的某种映射变换称为适应度的尺度变换。3 3 1 几种常见的适应度函数适应度函数基本上有以下三种：1 直接以待求解的目标函数转化为适应度函数，即：若目标函数为最大化问题f i t ( f ( x ) ) = f ( x )( 3 - 9 )若目标函数为最小化问题f i t ( f o ) ) 一， )( 3 - 1 0 )这种适应度函数简单直观，但存在两个问题，其一是可能不满足常用的赌轮选择中概率非负的要求；其二是某些待求解的函数在函数值分布上相差很大，由此得到的平均适应度可能不利于体现种群的平均性能，影响算法的性能。2 若目标函数为最小化问题，则尉f ( ，( x ) ) = f ：“a ，- 其f ( 他x ) ，。m “( 3 一1 1 )其中c 。，为，0 ) 的最大估计。第三章基本遗传算法若目标函数为最大值问题，则州m ) ) = 搓巍| n ，“功”m m式中c 。为f ( x ) 的最小值估计。这种方法是对第一种方法的改进，值预先估计困难、不可能精确的问题。3 若目标函数为最小问题( 3 1 2 )可称为“界限构造法”，但有时存在界限f i t ( f ( x ) ) ；志，c = 。，c + ，( 工) z 。若目标函数为最大化问题f i t ( f ( x ) ) t 而1 ，c o c 一，似) z 。这种方法与第二种方法类似，c 为目标函数界限的保守估计值。3 3 2 适应度函数的作用( 3 一1 3 )( 3 - 1 4 )在选择操作是会出现以下问题：1 在遗传进化的初期，通常会产生一些超常的个体，若按照比例选择法，这些异常个体因竞争力太突出而控制了选择过程，影响算法的全局优化性能。2 在遗传进化的后期，即算法接近收敛时，由于种群中个体适应度差异较小，继续的优化潜能降低，可能获得某个局部最优解。上面两种情况下，适应度函数值的分布对遗传搜索而言是极不合理的，所以适应度函数的设计是遗传算法设计的一个重要方面。3 3 3 适应度函数的设计通常，适应度函数设计主要满足以下条件：1 单值、连续、非负、最大化这个条件是很容易理解和实现的。2 合理、一致性要求适应度值反映对应解的优劣程度，这个条件的表达往往比较难以衡量。3 计算量小适应度函数设计应尽可能简单，这样可以减少计算时间和空间上的复杂性，降低计算成本。4 通用性强适应度对某类具体问题，应尽可能通用，最好无需使用者改变适应度函数中的参数。从目前而言这个条件应该是不属于强要求。第三章基本遗传算法3 3 4 适应度函数的尺度变换常用的尺度变换方法有以下几种：1 线性变换法假设原适应度函数为，变换后的适应度含函数为，则线性变换可用下式表示：f t = a ，f + pt 3 - 1 5 j上式中的系数确定方法有多种，但要满足以下条件：( 1 ) 原适应度的平均值要等于定标后的适应度平均值，以保证适应度为平均值的个体在下一代的期望复制数为l ，即：f ? 。g = f 。gt 3 1 6 0( 2 ) 变换后的适应度最大值应等于原适应度平均值的指定倍数，以控制适应度最大的个体在下一代中的复制数。试验表明，指定倍数c 。可在1 o 一2 0 范围内。即根据上述条件可确定线性比例的系数：，= c m ，。( 3 一1 7 )。：! 生二! 坚竖f m x - - f 。82 幂函数变换法变换公式为：，一，b ：坠 鱼型垒，( 3 - 1 8 )f 一f 。( 3 1 9 )上式中的幂指数七与所求的最优化问题有关，结合一些试验进行一定程度的精细变换才能获得较好的结果。3 指数变换法变换公式为：f 一e 一町( 3 - 2 0 )这种变换方法的基本思想来源于模拟退火过程( s i m u l a t e da n n e a l i n g ，s a ) ，其中的系数决定了复制的强制性，其值越小，复制的强制性就越趋向于那些具有最大适应度的个体。3 4 遗传操作遗传操作是模拟生物基因遗传的操作。在遗传算法中，通过编码组成初始群体后，遗传操作的任务就是对群体的个体按照它们对环境适应的程度( 适应度评1 4第三章基本遗传算法估) 施加一定的操作，从而实现优胜劣汰的进化过程。从优化搜索的角度而言，遗传操作可使问题的解，一代又一代地优化，并逼近最优解。遗传算法的遗传操作包括以下三个基本遗传算予( g e n e t jco p e r a l o r ) ：l 、选择( 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 ) 这三个遗传算子的操作都是在随机扰动情况下进行的。换句话说，遗传操作是随机化操作，因此，群体中个体向最优解迁移的规则是随机的。需要强调的是，这种随机化操作和传统的随机搜索方法是有区别的。遗传操作进行的是高效有向的搜索而不