（计算机应用技术专业论文）实数编码遗传算法机理分析及算法改进研究.pdf

摘要 工程和科学计算中的很多优化问题从最初的低维优化发展为高 维、大规模复杂优化，或常常带有比较复杂的约束条件，因而比较难 以求解。以遗传算法为代表的各类进化算法在求解该类复杂问题时越 来越受到重视。然而有关实数编码遗传算法( r c g a ) 的工作机理的 研究比较少，不能有效地指导算法的改进。本文研究了r c g a 的工 作机理，分析了r c g a 种群漂移的规律，提出了一些改进算法，用 高维优化和约束测试函数进行了数值实验，验证了本文算法的有效 性。具体创新性成果如下： l 、本文指出适应度函数设计存在不合理性，提出一个种子的适 应度值理论上应该和该种子到全局最优点的欧氏距离成负相关性；提 出了基本交叉算子实质上就是基于差分法的一维搜索。在进化后阶 段，当两父体种子在同一邻域内时，该搜索在整个进化过程中成为有 效搜索的可能性比较大，当两父体种子距离比较远时，成为有效搜索 的可能性逐渐减小。单重均匀或非均匀变异算子在种群空间里其变异 都不是均匀的； 2 、本文提出优势种群( 块) 的概念，通过研究优势块在种群中 种子个数的期望值增长规律提出了标准r c g a 种群漂移块式定理： 遗传算法的进化过程中，新的优势块不断出现排挤了原来的优势块直 到最后一个优势块出现不再被排挤为止。如果r c g a 各参数设置合 理，r c g a 中的新的优势块规模期望值具有近似按指数级增长的趋 势。在此基础上阐述了r c g a 的参数设置规则，分析了r c g a 提前 收敛的原因，解释了一些改进算法之所以有效的原因，结合算子作用 机制提出了r c g a 工作机理。从微观上来说，遗传算法是一种基于 差分法的邻域搜索、局部搜索和全局搜索自适应结合的算法；邻域搜 索、局部搜索和全局搜索所占比例受种群中优势块的个数以及各个优 势块种子个数的变化而变化。从宏观上来说，遗传算法是一种以一定 概率选择多个区域( 面向搜索块) 的迭代算法。优势种子邻域内种子 浓度增大有利于加快优势块收敛速度。 3 、本文提出了一种多精英保存策略遗传算法( g a e p ) ，通过求 解三个经典的连续函数优化问题与当前一些改进进化算法数值结果 对比，验证了g a e p 算法的有效性。分析了该算法的局限性并改进提 出了基于物种选择的遗传算法( g a s s ) 。通过模拟生物进化的阶段性 对g a s s 算法进行了改进，得到了改进算法( i g a s s ) 。三个算法都 通过最优种群的隔离来保持选择压力，最优种群边界的自适应收缩和 最优种群规模的不定期减小至1 保持了种群的多样性，比较好地平衡 选择压力和种群多样性，算法i g a s s 既对种群划分( 横向划分) ，又对 进化代数自适应的划分( 纵向划分) ，消除了参数( 最大进化代数) 对 均匀变异算子的步长在整个进化过程不均匀的影响，从而性能更稳 定。通过标准的高维和超高维数值实验分析了i g a s s 算法的动态性 能，并对算法i g a s s 与c e c 2 0 0 8 国际会议技术报告里提供的十个参 照算法进行比较，结果表明，i g a s s 算法适应度函数计算次数、求解 精度以及算法稳定性基本上都优越于参照算法。算法i g a s s 尤其适 合于求解变量可分离的超高维问题。 4 、本文指出以往的约束处理策略都没有很好地与精英保存策略 结合起来。通过对惩罚因子的局部分析，提出了一种与精英保存策略 相结合的惩罚函数法约束处理策略，结合i g a s s 算法提出了一种混 合算法( m g a s s ) ，算法m g a s s 将种群划分为三个子种群，此三子 种群按不同策略进化。标准的约束测试函数数值实验表明该算法性能 比较好。 关键词遗传算法，实数编码，块式理论，约束处理，高维优化问题 i i a bs t r a c t g e n e t i ca l g o r i t h m s ，u s u a l l ya d o p t t i n gr e a l c o d e d ，a so n eo ft h e i m p o r t a n tb r a n c ho fe v o l u t i o n a r ya l g o r i t h m s ，h a v eb e e nu s e dt os o l v e c o m p l i c a t e do p t i m i z a t i o np r o b l e m sm o r ea n dm o r ew i d e l y h o w e v e rt h e t h e o r e t i c a lr e s u l t so nm e c h a n i s mr e s e a r c ho fr e a l - c o d eg e n e t i ca l g o r i t h m s ( r c g a ) w a sr e l a t i v e l y 传w h i c hw a ss t u d i e da n ds e v e r a li m p r o v e d g a sw e r ep r o p o s e di nt h i sd i s s e r t a t i o n t h em a i nc o n t r i b u t i o n sa r ea s f o l l o w e s ： l 、a c t i o nm e c h a n i s mo fg e n e t i co p e r a t o r sw a sa n a l y s e d t h e r ew a sn e g a t i v ec o r r e l a t i o nb e t w e e nf i t n e e sv a l u ea n dt h e d i s t a n c eb e t w e e ng l o b a lo p t i m a ls o l u t i o na n di n d i v i d u a l s o n ep a s so f s i m p l ec r o s so p e r a t o ri sao n e d i m e n s i o n a ls e a r c hb a s e do nd i f f e r e n t i a l m e t h o di ne s s e n c e o n eg e n e r a t i o no fs i m p l ec r o s so p e r a t i o nc a nb e r e g a r d e da sac o m b i n a t i o no fe f f e c t i v en e i g h b o r h o o ds e a r c ha n dl o c a l r a n d o ms e a r c h t h ep r o p o r t i o no fn e i g h b o r h o o ds e a r c hw i l lc h a n g ew i t h t h en u m b e ro fa d v a n t a g eb l o c ka n dt h es i z eo fa d v a n t a g eb l o c ki n p o p u l a t i o n n e wi n d i v i d u a l sg e n e r a t e db ys i n g l e - ( o rm u l t i 一) u n i f o r m ( o r n o n u n i f o r m ) m u t a t i o n o p e r a t o ro c c u p i e dp r o b l e ms p a c e w i t h n o n u n i f o r md i s t r i b u t i o n e n h a n c i n gs e e d sn u m b e ro fn e i g h b o r h o o do f a d v a n t a g ei n d i v i d u a l sw i l li m p r o v e t h el o c a lc o n v e r g e n c er a t e 2 、an e w a n a l y t i c a lm e t h o do fg e n e t i cd r i f to fg e n e t i ca l g o r i t h mw i t h r e a l - c o d ew a sp r o p o s e db ys t u d y i n gt h ee x p e c t a t i o ns i z eg r o w t ho f a d v a n t a g es u b p o p u l a t i o n t h e e f f e c to fg e n e t i c o p e r a t o r o nt h e e x p e c t a t i o ns i z eo fa d v a n t a g es u b p o p u l m i o nw a se s t i m a t e dc o n c e r n e d l o c a lc h a r a c t e r i s t i c so fp r o b l e m s b l o c kt h e o r yo fr c g aw a sd e d u c e d t h a tt h ep r o c e s s i n go fr c g ai se x p r e s s e d a f t e rr a n d o ms e a r c h i n go ft h e f i r s tp h a s e ，t h es i z eo fa d v a n t a g eb l o c k si n c r e a s ea tt h ee x p o n e n tg r o w t h b u to n l yo p t i m a ls u b p o p u l a t i o nw a ss u r v i v e dw i t ht h ec r e a s i n go fa v e r a g e f i t n e s sv a l u ea n dw h o s es i z et e n d e dt oas t e a d yv a l u e t h ed i f f e r e n c e b e t w e e nb l o c kt h e o r ya n ds c h e m at h e o r yw a sc o n t r a s t e d t h e a p p r o p r i a t ep a r a m e t e rs e t t i n gw a sa n a l y z e da n dt h ep r e m a t u r i t yr e a s o n w a se x p l a i n e d f r o mt h em a c r o s c o p i cp o i n to fv i e w , r c g ai sai t e r a t i o n m e t h o dt os e l e c tm u l t i p l eb l o c k sa tad i v e r s ep r o b a b i l i t yt ot h en e x t i i i g e n e r a t i o n 3 、b a s e do nt h ea n a l y s i so fa d v a n c e dc o n v e r g e n c eb yb l o c kt h e o r y , 砀ed i s s e r t a t i o np r o p o s e dan o v e lg e n e t i ca l g o r i t h mw i t hs e v e r a le l i t i s t s p r e s e r v e dm e t h o d ( g a e p ) a f t e ra n a l y s i n go nt h el i m i t m i o n so fg a e p , g e n e t i ca l g o r i t h m sw i t hs p e i c e ss e l e c t i o n ( g a s s ) c o m ei n t ob e i n g i m p r o v e dg a s s ( i g a s s ) w a sp r o p o s e db yu s i n gs t a g ec h a r a c t e r i s t i c o f b i o l o g i c a le v o l u t i o nf o rr e f e r e n c e l o c a ls e a r c h i n g w a se r d a a n c e db y b o u n d a r ya u t o c o n t r a c t i o n o fo p t i m a ls u b p o p u l a t i o n g e n es e g r e g a t i o n w a sc a r d e do u tb yt h es i z eo fo p t i m a ls u b p o p u l m i o nd e c r e a s i n g a p e r i o d i c a l l ya n dc r o s so p e r m i o n b e t w e e no p t i m a ls u b p o p u l a t i o na n dr e s t s u b p o p u l a t i o n o p t i m i z a t i o np r o b l e m sw i t hs e p a r a b l e v a r i a b l e sw e r e d e f i n e dw h o s ep r o p e r t i e sw e r es t u d i e d i t sa n a l y z e dt h a tt h e t h r e e a l g o r i t h m s a r ee f f e c t i v ea n de s p e c i a l l ya p p r o p r i a t e f o r s o l v i n g h i g h d i m e n s i o no p t i m i z a t i o np r o b l e m sw h o s ev a r i a b l e s a r es e p a r a b l e ， w h i c hi sa p p r o v e db yn u m e r i c a le x p e r i m e n t s 4 、c o m m o nc o n s t r a i n t - h a n d l i n gt e c h n i q u e s a r es u r v e y e d ，w h i c h w e r en o tc o m b i n e dw i t h e l i t i s t p r e s e r v a t i o n s t r a t e g i e s an e w c o n s t r a i n t h a n d l i n gt e c h n i q u e s w a s p r o p o s e d c o m b i n e d e l i t i s t p r e s e r v a t i o ns t r a t e g i e sa n dp e n a l t y f u n c t i o nm e t h o d ，w h o s ep e n a l t yf a c t o r w a sd e s i g n e db yl o c a la n a l y s i s an e wm e m e t i ca l g o r i t h m st os l o v e c o n s t r a i n to p t i m i z a t i o np r o b l e m sc o m ei n t ob e i n gf r o mi g a s s s o m e d c a 一 t h er e s u l t ss h e t h a tt h e a l g o r i t h mlsnumericalt e s t sw e r em a d e h er e s u l t ss n o wm mm ea l g o r l u l i l l e f f e c t i v ea n dr o b u s t k e yw o r d s g e n e t i ca l g o r i t h m s ，r e a l c o d e d ，b l o c kt h e o r y , c o n s t r a i n t h a n d l i n g ，h i g h d i m e n s i o n a lo p t i m i z a t i o np r o b l e m s i v 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特另l j ：j i 以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名： 弋矽 1 日期：丛年上月二日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 博士学位论文第一章绪论 1 1 引言 第一章绪论 优化问题是一个古老的课题。其应用涉及工业、社会、经济、管理等各个领 域，很多实际问题进行数学建模后，可抽象为一个数值函数的优化问题。所谓优 化问题，就是在满足一定的约束条件下，寻找一组参数值，以使某些最优性度量 得到满足，即使系统的某些性能指标达到最大或最小。不失一般性，本文中所有 优化问题均以最小化问题为例。 许多工程实践中遇到的问题非常复杂，它们通常具有精确建模困难、数据有 噪声、时变等特征。即使建立出相应的数学模型，其目标函数仍具有多峰、非凸、 非光滑等特点。传统的优化方法通常需要求解目标函数的梯度( 甚至h e s s i a n 矩 阵) ，因而很难处理。如何有效地求解这些全局优化问题己经成为影响这些领域6 发展的关键因素之一。寻求一种适合此类问题的算法已成为最优化方法的一个主 要研究目标和引人注目的研究方向。 受进化论和种群遗传学的启发，一类模仿生物自然进化过程的被称为进化算 法( e v o l u t i o n a r ya l g o r i t h m s ) 的随机优化技术被提出并在解这类优化问题中显示 了优于传统优化算法的性能。二十世纪六十年代以来，进化计算作为一个新兴的 交叉学科，从无到有，从弱到强，已经成为智能计算的一个重要分支。遗传算法 ( g e n e t i ca l g o r i t h m s ) 、进化策略( e v o l u t i o ns t r a t e g i e s ) 、进化规划( e v o l u t i o n a r y p r o g r a m m i n g ) 是进化计算的三个主流分支。九十年代初，在遗传算法的基础上又 形成了一个分支，遗传规划( g e n e t i cp r o g r a m m i n g ) ，尽管它们最初是独立发展而 成。但它们有着相近的生物学背景，处理数值优化问题也比较相似。1 9 9 9 年1 0 月，进化计算领域在多特蒙德召开会议，将不同分支研究的学者聚集在一起，使 不同的分支相互认知、融合，从而形成进化计算。 运用进化算法求解函数优化问题时，实数编码由于无须编码解码，更贴近问 题实际，并且更容易与其它搜索技术结合，因而处理函数优化问题越来越多地采 用实数编码。一个函数优化问题如果不带有任何约束条件，则称之为无约束优化 问题( u n c o n s t r a i n e do p t i m i z a t i o np r o b l e m s ) ，反之，称为约束优化问题( c o n s t r a i n e d o p t i m i z a t i o np r o b l e m s ) 。本文的主要内容为实数编码遗传算法( r e a l c o d e dg e n e t i c a l g o r i t h m s ，r c g a ) 处理函数优化问题的机理、算法改进及约束处理技术等方 面的研究。 本章首先分析了遗传算法的生物学背景，回顾了遗传算法的起源和发展、算 法特点、基本结构、理论基础及应用现状，最后介绍了本文的研究内容和章节安 博士学位论文第一章绪论 排。 1 2 遗传算法的生物学背景 1 2 1 遗传变异理论 研究生物进化及生物表现出的性状导致遗传学的诞生。世问的生物从其亲代 继承特征或性状，这种生命现象称之为遗传( h e r e d i t y ) ，研究这种生命现象与机 理的科学即为遗传学( g e n e t i c s ) 。构成生物的基本结构与功能单位是细胞( c e l l ) ， 细胞中含有一种丝状化合物称为染色体。生物的所有遗传信息都在这个复杂而又 微笑的染色体中。遗传信息由其基因组成，生物的各种性状由其相应的基因决定。 基因是遗传的基本单位。细胞通过分裂具有自我复制的能力。细胞分裂时，遗传 物质( d n a ) 通过复制而转移到了新产生的细胞中，新细胞就继承了旧细胞的基 因。有性生殖生物在繁殖下一代时，两个同源染色体之间通过交叉( c r o s s o v e r ) 而 重组，亦即在两个染色体的某一相同位置处d n a 被切断，其前后两串分别交叉 组合而形成两个新的染色体。另外，复制可能以很小的概率出现出错，从而使 d n a 中的某些基因发生变异( m u t a t i o n ) 。如此这般，遗传基因或染色体在遗传过 程中由于各种各样的原因而发生变化。 1 2 2 进化论 1 8 5 9 年达尔文l l j 在其物种起源一书中根据大量考察资料详细阐述了一种 生物进化的理论。这种理论认为：生物不是从来就有的，物种是进化的，地球生 物界是一个历史有序的统一体。生物在其延续生存的过程中，逐渐适应其生存环 境，使得其品质不断得以改良，这种生命现象称为进化( e v o l u t i o n ) 。生物的进化 是以集团的形式共同进行的，这样的团体被称为群体( p o p u l a t i o n ) 。组成群体的单 个生物被称为个体( i n d i v i d u a l ) ，每个生物个体对其生存环境都有不同的适应能 力，这种能力称为个体的适应度( f i t n e s s ) 。达尔文进化论的核心是自然选择学说 ( n a t u r a ls e l e c t i o n ) 。其主要内容有四点：过度繁殖，生存斗争( 也叫生存竞争) ， 遗传和变异，适者生存。通过这种自然选择，物种将逐渐地向适应于生存 环境的方向进化( 即进化的趋势向上) ，从而产生出愈来愈适应环境的物种。 借助于模拟生物进化的“适者生存”、“优胜劣汰 过程及孟德尔的遗传理论， 通过对生物进化中的繁殖、变异、竞争和选择这四种基本形式进行模拟，人们得 到了解决优化问题的一类新方法一进化算法。 2 博士学位论文第一章绪论 1 3 遗传算法的起源与发展 早在二十世纪4 0 年代，就有学者开始研究如何利用计算机进行生物模拟技 术。二十世纪六十年代初期，h o l l a n d 2 1 在研究生物学、人类社会及控制领域中动 态系统的适应性问题时，采用简单的模拟机制在计算机上模拟复杂的适应性现 象。在实验中发现，要想得到稳定的适应性系统( r o b u s t a d a p t i v es y s t e m s ) ，一个 具有进化能力的系统是关键。在这一时期，遗传算法中的进化操作开始出现； 1 9 6 7 年，h o l l a n d 的学生b a g l e y l 3 1 在其博士论文中提出了遗传算法( g a ： g e n e t i c a l g o r i t h m ) - - 词，算法主要是为了优化游戏程序中的参数设定，遗传算法 的基本机制开始出现。他所提出的选择、重组和变异操作己与现代遗传算法中的 相应操作十分接近。他认识到，在遗传进化过程中的前期和后期，个体的选择概 率应适当地变化，因此，提出了适应值定标( s c a l i n g ) 概念。他还首次提出了遗传 算法自调整概念，即把重组和变异概率参数融于染色体编码中，从而实现参数的 自调整优化，这一思想对于后来的自适应遗传算法的发展起了重要的作用。同一 时期，h o l l a n d 许多学生的工作在遗传算法的形成过程中起了非常重大的作用， 除了b a g l e y 外，c a v i c c h i o a l 研究了基于遗传算法的模式识别问题，提出了以预 选择策略保证种群多样度的思想。w e i n b e r g t s l 研究了生物系统的计算机仿真，提 出了运用多级遗传算法来进行遗传算法参数的自优化。f o g e l 【6 7 j 等为建立人工智 能提出了求解预测问题的进化规划，并首先将其成功地应用于有限状态机的进化 中；r e c h e n b e r g t t 8 1 和s c h w e f c l 9 1 等提出了进化策略，并将其成功地应用于实值优 化问题( 例如流体力学中的弯管形状优化) 中。 1 9 7 5 年，h o l l a n d 出版了一本系统论述遗传算法和人工自适应系统的专著【。 这是遗传算法领域一个里程碑式的著作。该书对遗传算法的基本理论及方法进行 了系统的阐述，提出了著名的模式理论( s c h e m a t at h e o r e m ) 及隐并行性( i m p l i c i t p a r a l l e l i s m ) ，用以解释遗传算法的运行机理。同年，d ej o n g 在博士论文i l i j 中进 行了大量的数值实验，把模式理论和函数优化结合起来，建立d ej o n g 五函数测 试平台，并且定义了评价遗传算法收敛和动态性能的标准。 8 0 年代，h o l l a n d 教授首先将遗传算法应用于机器学习的研究i l2 1 ，并实现了 基于遗传算法的机器学习系统一分类器系统，开创了基于遗传算法的机器学习的 新概念。g o l d b e r g 在遗传算法研究中起着继往开来的作用，他在1 9 8 3 年的博士 论文中首次将遗传算法应用于实际工程问题( 煤气管道优化) ，他【1 3 l 系统地总结了 遗传算法的主要研究成果，全面地论述遗传算法的原理及其应用，奠定了现代遗 传算法的科学基础。 进入9 0 年代，以不确定性、非线性、时间不可逆为内涵，以复杂问题为研 究对象的科学新范式得到学术界的普遍认同。由于进化算法能有效地求解n p 难 3 博士学位论文第一章绪论 解问题以及非线性、多峰函数优化和多目标优化问题，从而得到了多学科的广泛 重视，某些学者在研究了遗传算法的涌现行为( e m e r g e n tb e h a v i o r ) 后声称，遗传 算法与混沌理论与分形几何一道成为人们研究非线性现象和复杂巨系统的新的 三大方法，并且将和神经网络一道成为人们认知过程的重要工具【1 4 】，并被某些国 家确定为2 1 世纪的先进计算技术 1 5 - 1 7 】。 1 4 遗传算法的基本结构及主要特点 1 4 1 遗传算法的基本结构 上世纪8 0 年代，g o l d b e r g 1 3 】对遗传算法的研究进行了归纳总结，提出了遗 传算法的基本框架，称为简单遗传算法( s i m p l eg e n e t i ca l g o r i t h m s ，s g a ) 。遗传 算法的术语借鉴于自然遗传学。和传统的搜索不同，遗传算法从一组随机产生的 初始解，称为种群( p o p u l a t i o n ) 开始搜索过程。种群的每个个体是问题的一个解称 为染色体( c h r o m o s o m e ) 。染色体是一个串符号，譬如一个二进制字符串。这些染 色体在后续迭代中不断进化，称为遗传，在每一代中用适应度( f i t n e s s ) 值来衡量 染色体的好坏，生成的下一代染色体称为后代( o f f s p r i n g ) 。后代是由前一代染色 体经过交叉( c r o s s o v e r ) 和变异( m u t a t i o n ) 生成。根据适应度值和选择算子( s e l e c t i o n ) 生成新一代群体。适应度值高的种子被选中的概率高。这样，若干代后，算法收 敛于最好的染色体。 s g a 算法各个组成部分描述如下： 1 ) 一个对参数空间编码的符号串表示； 遗传算法不对所求解问题的决策变量直接进行操作，而是对表示可行解的个 体编码( 染色体) 进行操作，因此，应用遗传算法时首先必须解决可行解的表示问 题。由于遗传算法应用的广泛性，迄今为止，人们已经提出了许多不同的表示方 法，基本上可分为二进制编码、实数编码、符号编码和树结构编码几大类。其中 树结构编码主要用于遗传规划中【1 8 1 9 1 ，遗传算法中比较常用的是二进制编码和 实数编码，对于函数优化问题，一般采用实数编码。 二进制编码有如下优点： 编码解码操作简单易行； 交叉变异等遗传操作易于实现； 符合最小字符集编码原则； 便于利用模式定理对算法进行理论分析； 实数编码有如下优点： 适合于表示范围比较大的数，便于比较大空间的遗传搜索： 适合于精度要求比较高的数值优化问题； 4 博士学位论文 第一章绪论 无须编码解码，改善了遗传算法的计算复杂性，提高了运算效率； 便于遗传算法与经典优化算法混合使用； 便于设计针对问题专门知识的遗传算子； 便于处理复杂的决策变量约束条件。 2 ) 一个评价符号串的适应度函数； 遗传算法使用个体的适应度函数对解的质量进行评价，个体的适应值越高， 相应解的质量越好，该个体被选择参与繁殖子孙的概率就越大。仅使用目标函数 值就可以获得下一步搜索信息是遗传算法的一个特点。换言之，适应度值仅与目 标函数相关。评价个体适应度值的一般过程是： ( 1 ) 对个体编码值解码，得到个体的表现型； ( 2 ) 根据个体表现型，计算出目标函数值； ( 3 ) 将目标函数值按一定的规则转换成适应度函数值。一般地，适应度函数 值总是设计成正的。 设目标函数为万适应度函数为只对于最大化问题，目标函数可以按下式 转换成适应度函数： 风x ) 可+ c i 卅加， 对于最小化问题，其映射函数为： 其x ) = g 惦撒) ； 其中g 加和g 忧分别为能满足所有的瞰) 均大于0 的一个适当的相对比较小的 或比较大的实数。 为了有效地控制选择压力，必须对个体的适应度值进行适当的扩大或缩小， 称为适应度值尺度变换( f i t n e e s ss c a l i n g ) ，设原始的适应度值函数为瞰) ，变换 后的新的适应度值函数为f 协，常用的适应度【2 0 。2 2 1 值变换技术有： ( 1 ) 线性尺度变换：，邗月+ 6 ； 系数a ，b 应满足两条件： ( i ) 使变换后种群的平均适应值应等于变换前的平均适应值； ( i i ) 变换后种群中的最大适应值等于变换前平均适应值的指定倍数。 ( 2 ) 乘幂尺度变换：f 1 = 硝 幂指数七与所求解的问题有关，并且在算法的执行过程中，必须不断地对其进行 修正，才能使尺度变换满足一定的伸缩要求。 ( 3 ) 指数尺度变换：f = e x p ( - p 足功) 即新的适应度值是原适应度值的某个指数。系数p 决定了选择的强制性。p 越小， 适应度值高的个体与其它个体的新适应度值差异比原适应度值差异增大，从而提 高了个体的选择压。 博十学位论文第一章绪论 ( 4 ) 对数尺度变换：f 1 ( 力= 6 - l o g f ( x ) b 满足；b l o g f ( x ) 目前，关于适应值变换技术和选择算子的交互作用尚无任何理论研究成果， 在实际应用时，采用哪一种变换技术被认为是一种“黑色艺术 ，完全取决于应 用者的经验和偏爱。 3 ) 一组产生成新的符号串的遗传操作：选择算子、交叉算子和变异算子 ( 1 ) 选择算子：遗传算法采用选择算子或称复制算子来模拟自然选择，对群 体中的个体进行优胜劣汰操作。就是确定如何从父代群体中按照某种规则选取哪 些个体遗传到下一代群体中的一种遗传运算。g o l d b e r g 2 3 1 研究了多种选择方法的 选择压对遗传算法搜索性能的影响。p o t t s t 2 4 1 概括了大约2 0 多种选择方法，并提 出微观进化结构和人工选择等技术来改进遗传算法的早熟收敛现象。b a c k l 2 5 】将 遗传算法中常见的选择算子归结为以下几类： 比例选择( p r o p o r t i o n a lm o d a l ) 按与个体的适应值成正比的方法确定个体的选择概率。设群体规模为肛，个 体i 适应度函数为月，则个体f 被选择进入下一代种群的概率为： ：善( 1 - 1 ) e 虽然比例选择是遗传算法的标准选择方法，但有以下缺点： ( i ) 适应度函数必须是正数，其比例实际上还与适应度值尺度变换时的参数有 关； ( i i ) 在算法早期，当存在超级个体时，很容易产生早熟收敛现象； ( i i i ) 在算法晚期，适应度值比较接近，搜索容易陷入停滞不前。 排序选择( r a n k b a s e dm o d a l ) 主要思想为：对群体中所有个体按适应度值大小排序，基于此排序来分配各 个个体被选中的概率。基于这些概率以一定规则产生下一代群体。常用的选择概 率分配方法有线性排序方法和比例选择方法等。 精英保存( e l i t e p r e s e r v a t i o n ( e p ) m o d a l ) 由于选择、变异、交叉的随机性，它们可能破坏最优个体。从而使种群发生 退化，对算法的运行效率和收敛性都产生不利影响。所以采用将适应度最好的个 体强制保存到下一代种群中。这就是精英保存策略。精英保存策略还可以推广， 即在每一代的进化过程中保留多个最优个体直接将它复制到下一代种群中，这种 方法也称稳态复制。 联赛选择( t o u r n a m e n tm o d a l ) 6 博士学位论文第一章绪论 该方法从种群中随机地选择g 个个体( g 称为联赛规模) ，其中适应值最高的 个体进入下一代种群，这一过程重复次，直到填满下一代种群。b a c k i 2 5 】推导出 联赛选择的选择概率计算公式为： 1 只= 二 ( ( ”一f + 1 ) 9 一( p f ) 9 ( 1 - 2 ) p 1 显然，改变联赛规模能调节选择压，联赛规模越大，选择压越高。选择适当的最 大期望数和联赛规模，联赛选择完全等价于排序选择。 ( 肛，九) 选择和( “+ 九) 选择 这是一类在进化策略中普遍采用的选择方法。( p 九) 选择先从p 个父代个体 中随机地选择九个个体参与重组和变异操作以生成临时种群，再从临时种群中确 定性地选择前p 个适应值较高的个体进入下一代种群。( p + 九) 选择允许“个父代 个体和九个子代个体共同竞争，确定性地选择斗个适应值较高的个体进入下一代 种群。显然，通过调节p 和九的比值可实现选择压的控制。与其它选择方法相比， ( p + 久) 选择不但可提供较强的选择压，且能确保父代种群中的最佳个体进入下一 代种群，是一种自然的精英保留选择方法。 ( 2 ) 交叉算子：交配重组是生物遗传和进化的一个主要环节。模仿这个环节， 遗传算法中也采用交叉算子来产生新的个体。遗传算法中的所谓交叉算子指对两 个相互配对的染色体按某种规则交换部分基因，从而形成两个新的个体。交叉算 子是遗传算法区别于其它进化算法的重要标志之一。 单点交叉( o n ep o i n t e rc r o s s o v e r ) 在染色体编码中随机地设定一个交叉点，将该点之前或之后的两个染色体的 部分结构进行互换，并生成两个新的个体。 两点交叉( t w op o i n t e rc r o s s o v e r ) 和多点交叉 2 6 ，2 7 ( m u l t i p o i n t e rc r o s s o v e r ) 与一点交叉不同的是，多点交叉允许随机地生成多个交叉位置。在实际应用 中，使用较多的为两点交叉。 均匀交叉( u n i f o r mc r o s s o v e r ) 均匀交叉实际上是多点交叉的扩展，两个父代个体的每一个基因是否交换取 决于随机整数k 0 ，1 的取值。例如，对于任意基因座位置，如果k = 1 ，则交换 该位置上的基因，否则，保持原有基因不变。 算术交叉( a r i t h m e t i cc r o s s o v e r ) 和启发式交叉( h e u r i s t i cc r o s s o v e r ) 两个个体的线性组合产生出两个新的个体。其操作对象一般是针对实数编码 遗传算法。其计算公式分别为： x = 名x l + ( 1 一五) x 2 ( 1 3 ) x = x l + 九( x l x 2 ) ( 1 - 4 ) 7 博士学位论文 第一章绪论 其中九为【o ，1 】中的随机数。 ( 3 ) 变异算子：在生物的遗传和进化过程中，其细胞分裂复制环节有可能因 为某些偶尔因素的影响，而产生一些复制差错，这样会导致生物的某些基因发生 变异，从而产生出新的染色体，表现出新的性状。模拟生物遗传和进化过程中的 变异环节，在遗传算法中引入变异算子来产生新的个体。遗传算法中的所谓基因 变异，是指将个体染色体编码串中某些基因位上的基因值用该基因座的其它等位 基因替换，从而形成一个新的个体。 基本位变异( s i m p l em u t a t i o n ) 基本位变异指对个体编码串中以变异概率p m 随机指定某一位或某几位上的 基因值作变异运算。 均匀变异( u n i f o r mm u t a t i o n ) 均匀变异的具体操作过程是： ( i ) 依次指定个体编码串中的每个基因位为变异点； ( i i ) 对每个变异点，以概率砌从对应基因位的取值范围内任取一随机数替代 原有基因值。 假设个体为x = ( x l ，x 2 ，x j ，砀) ，选x j 为变异位，其取值范围为阮， _ ，x u , j ，则变异点的新基因值为： x = x l ，+ 九x ( x u 一x l , j ) ( 1 - 5 ) 非均匀变异( n o n u n i f o r mm u t a t i o n ) 与均匀变异不同的是，非均匀变异不是任取一随机数来替代原有基因值，而 是对原有基因值作一个随机扰动，以扰动后的结果作为变异后该基因的新值。非 均匀变异算子可描述为： x ，= x + o ，( x c ，一x ) ) ，九 o 5 ： ( 1 - 6 ) x f = z ，一a ( t ，( x ，一x ，f ) ) ，九0 5 ； ( 1 7 ) 其中，丁为终止代数， a ( t ，y ) = y 九x ( 1 一t t ) 6( 1 8 ) 自适应变异【2 8 3 0 】 自适应变异与非一致变异类似。受模拟退火启发，变异中引入变异温度的概 念。设其适应度值经过标定后都是正值。f ( x i ) 为被变异个体的适应值，b 俄为当 前找到的最大适应值，则定义t = i m ，) 伊一为个体的变异温度。变异公式如下： 其中， x j = x ，+ a ( t ，( x u ，j x ) ) ，九 0 5 ； z ，= x _ ，一a ( t ，( x 一x l , j ) ) ，九0 5 ； 8 ( 1 9 ) ( 1 1 0 ) 博士学位论文 第一章绪论 a ( t ，y ) = y x ( 1 1 1 ) 边界变异( b o u n d a r ym u t a t i o n ) 在进行边界变异操作时，随机地取基因座的两个对应边界值取代原值。变异 公式如下： 护 黧 m 协 高斯变异( g a u s s i a nm u t a t i o n ) 高斯变异是改进遗传算法对重点搜索区域的局部搜索性能的变异操作方法。 执行该变异操作时，用符合均值为p ，方差为6 2 的正态分布随机数来替换原有基 因值。具体计算时，可以利用下式近似计算。 假设叹i = 1 ，1 2 ) 为 o ，1 】范围内均匀分布的随机数，则符合n ( 1 x ，0 2 ) 的正态分布随机数可以用下式求出： t = p + o ( - 6 ) ( 1 - 1 3 ) i x = ( x l ，j 乜u ，j ) 2 ( 1 - 1 4 ) o 电u j - x l 。j ) 6 ( 1 _ 1 5 ) 高斯变异的局部搜索能力比较强。 4 ) 一组控制参数：编码长度、种群规模，遗传算子的操作概率、终止代数、 代沟等 编码长度，：其选取与问题的求解精度有关； 种群规模u ：当取值比较小时，可以提高遗传算法的运算速度，但容易损 失种群