（应用数学专业论文）改进遗传算法的研究.pdf

： f - _ 乒譬辞争； ，。，、0：。 纛，一ij 士= u明明 本人郑重声明：此处所提交的硕士学位论文改进遗传算法的研究，是本人 在华北电力大学攻读硕士学位期间，在导师指导下进行的研究工作和取得的研究成 果。据本人所知，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经 发表或撰写过的研究成果，也不包含为获得华北电力大学或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 躲复临期：丑川r 关于学位论文使用授权的说明 本人完全了解华北电力大学有关保留、使用学位论文的规定，即：学校有权 保管、并向有关部门送交学位论文的原件与复印件；学校可以采用影印、缩印或 其它复制手段复制并保存学位论文；学校可允许学位论文被查阅或借阅；学校 可以学术交流为目的，复制赠送和交换学位论文；同意学校可以用不同方式在不同 媒体上发表、传播学位论文的全部或部分内容。 ( 涉密的学位论文在解密后遵守此规定) 作者签名： 日期：斗砂，r 日期：丑啦t 。，r i - h 华北电力人学硕士学位论文摘要 摘要 遗传算法是模拟自然界生物进化机制的概率性搜索算法，可以处理传统搜索方 法难以解决的非线性问题。但是经典遗传算法存在局部收敛、收敛速度慢等缺点， 这使得经典遗传算法有时很难找到全局最优解。本文针对经典遗传算法中所存在的 这些缺点，采用阶段式的适应度函数、基于竞争机制的交叉方式和仿粒子群变异操 作，使得遗传算法的收敛速率、全局收敛概率都得到了较大提高。最后将改进的遗 传算法应用于电厂机组负荷分配问题，进一步证实了本文改进遗传算法的实用性和 有效性。 关键词：遗传算法，适应度，交叉操作，仿粒子群变异 a b s t r a c t g e n e t i ca l g o r i t h mi sap r o b a b i l i s t i cs e a r c ha l g o r i t h mw h i c hs i m u l a t e st h ee v o l u t i o n m e t h o di nn a t u r e i tc a ns o l v en o n l i n e a rp r o b l e m sw h i c ha r ed i f f i c u l tt os o l v eb y t r a d i t i o n a ls e a r c hm e t h o d s b u tt h ec l a s s i c a lg e n e t i ca l g o r i t h mh a ss o m ed e f i c i e n c y f o r e x a m p l e ，t h ea l g o r i t h mo f t e no b t a i n sa l o c a lo p t i m a ls o l u t i o n ，c o n v e r g e n c es l o w l ya n ds o o n s oas t a g e df i t n e s sf u n c t i o n ，ac r o s s o v e ro p e r a t i o nt h a tb a s e do nt h em e c h a n i s mo f c o m p e t i t i o na n d i m i t a t i o np a r t i c l es w a r mo p e r a t i o na r ep r o p o s e di nt h i sp a p e r t h en e w a l g o r i t h mo b v i o u s l yi m p r o v e st h ec o n v e r g e n c es p e e da n dt h eg l o b a lc o n v e r g e n c e p r o b a b i l i t y f i n a l l y , t h ei m p r o v e dg e n e t i ca l g o r i t h mi sa p p l i e dt ol o a da l l o c a t i o np o w e r g e n e r a t i n gu n i t sm o d e l ，a n dt h e np r o v e si t sp r a c t i c a b i l i t ya n dv a l i d i t y d o u m i n g - x i n ( a p p l i e dm a t h e m a t i c s ) d i r e c t e db yp r o f z h a n gg u o l i k e yw o r d s ：g e n e t i ca l g o r i t h m ，f i t n e s s ，c r o s s o v e ro p e r a t i o n ，i m i t a t i o np a r t i c l e s w a r mo p e r a t i o n 口 o 华北电力人学硕+ 学位论文目录 目录 中文摘要 英文摘要 第一章引言! 1 1 1 选题背景及其意义1 1 2 国内外研究动态1 1 3 课题研究内容3 1 4 论文的组织结构3 第二章传统遗传算法4 2 1 遗传算法理论基础4 2 2 遗传算法的特点及应用4 2 2 1 遗传算法的特点4 2 2 2 遗传算法的应用5 2 3 遗传算法的描述6 2 3 1 编码7 2 3 2 群体设定7 2 3 3 遗传算子8 2 3 4 终止循环的条件8 2 4 遗传算法的流程9 第三章遗传算法的改进11 3 1 一般自适应遗传算法11 3 2 改进的遗传算法1 3 3 2 1 适应度函数的改进1 4 3 2 2 交叉方式的改进1 4 3 2 3 变异方式的改进l5 3 3 算法步骤1 6 华北电力人学硕士学位论文目录 3 4 仿真实验17 3 4 1 测试函数一1 7 3 4 2 实验参数设定2 2 3 4 3 实验结果2 5 3 4 4 结果分析2 9 3 5 本章小结3 0 第四章基于遗传算法的电厂机组负荷分配3 1 4 1 电厂机组负荷分配模型3 1 4 2 改进的遗传算法设计3 2 4 2 1 模型改进3 2 4 2 2 算法描述3 2 4 2 3 算法流程3 4 4 3 电厂机组负荷分配优化计算实例及结果分析3 4 4 4 本章小结3 6 第五章结论3 7 参考文献3 8 致谢4 1 在学期间发表的学术论文和参加的科研情况4 2 簟， 口 华北电力大学硕+ 学位论文 1 1 选题背景及其意义 第一章引言 当前科学技术正进入多学科互相交叉、互相渗透、互相影响的时代，生命科学 与工程科学的交叉、渗透和相互促进是其中一个典型例子，也是近代科学技术发展 的一个显著特点。遗传算法的蓬勃发展正体现了科学发展的这一特点和趋势。 众所周知，在人工智能领域中，有不少问题需要在复杂而庞大的搜索空间中寻 找最优解或准优解，像组合优化问题就是典型的例子。在求解此类问题时，若不能 利用问题的固有知识来缩小搜索空间则会产生搜索的组合爆炸。因此，研究能在搜 索过程中自动获得和积累有关搜索空间的知识，并能自适应地控制搜索过程，从而 得到最优解或准优解的通用搜索算法一直是令人瞩目的课题。遗传算法就是在这种 背景下产生并经实践证明特别有效的算法。 遗传算法( g e n e t i c a l g o r i t h m ，g a ) 是近年来迅速发展起来的一种全新的随机搜 索优化算法，其基本思想是基于d a r w i n 的进化论和m e n d e l 的遗传学说。该算法由 h o l l a n d 及其学生于1 9 7 5 年创建。此后，遗传算法的研究引起了国内外学者的关注。 作为一种通用的问题求解方法，遗传算法采用简单的编码技术来表示各种复杂的结 构并通过对一组编码进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确 定搜索的方向。 近年来，遗传算法已被成功地应用于交通运输、经济管理、工业设计等不同领 域，解决了许多问题。例如，电力市场无功优化、流水车间调度、图像处理、作业 数据挖掘、车间调度、机器调度以及设备布局设计等【2 。3 1 。 但是传统的g a 存在很多问题，如：( 1 ) 编码问题：对于不同问题，编码选择不 当，可能导致积木块假设不成立而使g a 很难收敛到最优解。( 2 ) 早熟收敛：指群体 过早失去多样性而收敛到局部最优解。( 3 ) 进化时间长：进化过程中产生大量数据， 计算量大、时间长。( 4 ) 参数选择问题：目前参数选择是根据经验来确定，缺乏理论 依据。因此研究如何改进遗传算法提高运算效率，避免上述问题已经成为当前算法 研究的热点【1 4 , 1 5 j 。 1 2 国内外研究动态 1 9 6 7 年，h o l l a n d 的学生b a g l e y 在博士论文中首次提出“遗传算法 ( g e n e t i ca l g o r i t h m ) ”一词。此后，h o l l a n d 指导学生完成了多篇有关遗传算法研究的 论文。1 9 7 1 年，h o l l s t i e n 在他的博士论文中首次把遗传算法用于函数优化。1 9 7 5 l 华北电力火学硕十学位论文 年是遗传算法研究历史上十分重要的一年。这一年h 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 ) ) 1 1 6 】，这是第一本系统论述遗传算法的 专著，因此有人把1 9 7 5 年作为遗传算法的诞生年。h o l l a n d 在该书中系统地阐述了 遗传算法的基本理论和方法，并提出了对遗传算法理论研究和发展极其重要的模式 理论。该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。同年， d ej o n g 完成了他的博士论文( a na n a l y s i so f t h eb e h a v i o ro f ac l a s so f g e n e t i ca d a p t i v e s y s t e m s ) ) 1 1 7 】。该论文所做的研究工作，可看作是遗传算法发展进程中的一个罩程碑， 这是因为他把h o l l a n d 的模式理论与他的计算实验结合起来。尽管d ej o n g 和 h o l l s t i e n 一样主要侧重于函数优化的应用研究，但他将选择、交叉和变异操作进一 步完善和系统化，同时又提出了诸如代沟等新的遗传操作技术。1 9 8 9 年，h o l l a n d 的学生g 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 na n dm a c h i n e l e a m i n g ) i s 】。该书总结了遗传算法研究的主要成果，并对遗传算法及其应用作了 全面而系统的论述。另外，g o l d b e r g 等人在文献【1 9 】中还指出对于高精度要求的函 数，二迸制编码过于冗长，相对实数编码会消耗更多的时间，此外二进制编码还存 在“海明悬崖问题”( 即两个相距较近的数的二进制编码的海明距离会很大，不能正 常地反映两个数的实际距离) 。针对这个问题j i n g 和y a n g 提出了格雷编码来解决海 明悬崖问题【2 们，这样虽然会增加算法的运行时间，但是使算法的稳定性得到了很大 的提高。杨晓华等又提出了格雷码加速遗传算法用来解非线性极大极小问题【2 。在 早期实数编码的交叉操作研究中w r i g h t 提出的启发式交叉( h e u r i s t i cc r o s s o v e r h x ) 是两个父代生成一个子代个体，并且这个子代个体偏向较好父代个体吲；d e b 和 a g r a w a l 提出了一种连续搜索空间上的拟二进制编码交叉，这种方法是模拟二进制 编码单点交叉用两个父代生成两个子代【2 习：t s u t s u i 针对多峰函数提出了单纯形交叉 方法，该方法在低维函数中采用3 个父代，在高维函数中采用4 个父代进行交叉【2 4 】； m i c h a l e w i c z 提出了均匀算术交叉和非均匀算术交叉【2 5 】；e s h e l m a n 和s c h a f f e r 提出 了一种基于两个父代个体的混合交叉操作【2 q ；d e b 等提出了一种父代中心交叉操作 ( p a r e n tc e n t r i cc r o s s o v e ro p e r a t o r , p c x ) 并很好的应用在了实数编码遗传算法【2 7 】。在 变异操作的研究中，m i c h a l e w i c z 提出了均匀变异和非均匀变异1 2 5 1 ，其中的非均匀 变异是实数编码遗传算法中应用最广的变异方法之一；h i n t e r d i n g 提出利用高斯分 布进行变异操作【2 8 1 ；m a k i n e n ，p e r i a u x ，t o i v a n e n 提出了m p t m 变异( m a k i n e n ，p e f i a u x a n dt o i v a n e nm u t a t i o n ) 用以解决空气动力学和电磁学的优化问题【2 9 1 。 在改进交叉概率和变异概率方面，s r i n v i v a s 等提出来自适应遗传算法，它的基 本思想是根据个体适应度的集中程度来确定交叉概率和变异概率【3 0 】：李敏强等提出 了基于阶段进化的自适应策略的遗传算法，该算法将整个进化阶段划分为三个阶 段，基于不同阶段的进化特点及要求采取不同的自适应策略川。 2 华北电力大学硕士学位论文 1 3 课题研究内容 虽然遗传算法解决优化问题具有概念简单、容易实现等优点，但是基本遗传算 法在解决问题时仍然有不足之处，例如计算时间长，出现“早熟”、或者是收敛速度 慢甚至是不收敛，所以进一步改进遗传算法来提高计算效率是很重要的。 虽然二进制编码方法具有编码解码操作简单易行、交叉变异等遗传操作便于实 现、符合最小字符集编码原则和便于利用模式定理对算法进行理论分析等诸多优 点，常常被用于经典的遗传算法中，但越来越多的研究表明实数编码方法在数值优 化方面具有更高的精度和运算效率，较大地改善了遗传算法的计算复杂性，因此本 课题主要研究对实数编码遗传算法的改进。采用实数编码不仅可以避免对个体进行 多次的二进制编码、解码，而且对于一些多维、高精度要求的连续函数优化问题， 使用二进制编码来表示个体将会带来一些不利，例如，二进制编码存在着连续函数 离散化时的映射误差，不便于反映所求问题的特定知识【引1 。 本课题研究内容主要有以下几点： ( 1 ) 分析遗传算法的原理与特点； ( 2 ) 针对遗传算法所存在的问题，对适应度函数、交叉和变异的方式进行改进； ( 3 ) 用经典测试函数测试改进的遗传算法，并且与其他遗传算法进行比较； ( 4 ) 将改进的遗传算法应用到电厂机组负荷分配问题中，进一步证明改进算法 的有效性。 1 4 论文的组织结构 本文第一章介绍了遗传算法的背景和意义，指出了本文课题的研究内容；第二 章对遗传算法的基本思想，遗传算法的特征，遗传算子，运算流程做了详细的介绍； 第三章介绍了遗传算法中的自适应技术，概述了一般的自适应遗传算法，进而对遗 传算法适应度函数，交叉方式和变异方式进行了改进，之后利用经典测试函数检验 本文改进的遗传算法，并且与经典遗传算法和一般自适应遗传算法进行比较分析： 第四章将本文改进的遗传算法应用到求解电厂机组负荷分配问题中，通过该实例进 一步证明了改进遗传算法的实用性和有效性；最后结论部分对整篇文章做出总结。 3 华北电力大学硕十学位论文 2 1 遗传算法理论基础 第二章传统遗传算法 遗传算法的基本思想是基于d a r w i n 进化论和m e n d e l 的遗传学说的。d a r w i n 进 化论最重要的是适者生存原理，它认为每一物种在发展中越来越适应环境，物种每 个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境 变化时，只有那些能适应环境的个体特征才能保留下来。m e n d e l 遗传学说最重要的 是基因遗传原理，它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体 内，每个基因有特殊的位置并控制某种特殊性质，每个基因产生的个体对环境具有 某种适应性，基因突变和基因杂交可以产生更适应于环境的后代，经过存优去劣的 自然淘汰，适应性高的基因结构得以保存下来。综上所述，生物的进化是一个奇妙 的优化过程，它通过选择淘汰，突然变异，基因遗传等规律产生适应环境变化的优 良物种。 遗传算法是根据生物进化思想而启发得出的一种全局优化算法，它利用自然选 择和进化思想在高维空间中寻优，它不一定能寻得最优点，但是它可以找到更优点。 因此g a 可能会暂时停留在某些非最优点上，直到变异发生使它跃居到另一个更优 点上。g a 寻优过程的一个重要特点是它始终保持整个种群的进化，这样即使某个 体在某时刻丧失了有用的特征，这种特征也会被其他个体所保留并延续发展下去。 由于仅需知道目标函数的信息，而不需要其连续可微等要求，因而具有广泛的适应 性。同时它又是一种采用启发性知识的智能搜索算法，所以往往能在搜索空间高度 复杂的问题上取得比其他算法更好的效果【3 2 , 3 3 】。 2 2 遗传算法的特点及应用 2 2 1 遗传算法的特点 遗传算法是进化算法中产生最早、影响最大、应用也比较广泛的一个研究方向 和领域，它不仅包括了进化算法的基本形式和全部优点，同时还具备若干独特的性 能： ( 1 ) 遗传算法从问题解的集合开始嫂索，而不是从单个解开始。这是遗传算法 与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的，容易 陷入局部最优解。遗传算法从串集开始搜索，覆盖面大，利于全局择优。 ( 2 ) 在求解问题时，遗传算法首先要选择编码方式，它直接处理的对象是参数 4 华北电力人学硕十学位论文 的编码集而不是问题的基本参数本身，搜索过程既不受优化函数连续性的约束，也 没有要求优化函数的导数必须存在。通过优良染色体基因的重组，遗传算法可以有 效地处理传统上非常复杂的优化函数求解问题。在所求解问题为非连续、多峰以及 有噪声的情况下，能够以很大的概率收敛到最优解或者满意解，因而具有较好的全 局求解能力。 ( 3 ) 遗传算法有较强的容错能力。遗传算法的初始串集本身就带有大量与最优 解甚远的信息，通过选择、交叉、变异操作能迅速排除与最优解相差极大的串。这 是一个强烈的滤波过程，并且是一个并行滤波机制。因此，遗传算法具有很高的容 错能力。 ( 4 ) 对函数性态的要求较小，针对某一问题的遗传算法经简单修改即可适应于 其它问题，或者加入特定问题的领域知识，或者与已有算法相结合，能够较好地解 决复杂问题，因而具有较好的普适性和易扩充性。 ( 5 ) 遗传算法的基本思想简单，运行方式和实现步骤规范，便于具体使用。在 求解时使用特定问题的信息较少，容易形成通用算法程序。由于遗传算法使用适应 值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需 适应值和串编码等通用信息，故几乎可处理任何问题。 ( 6 ) 遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。 这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉 体现了最优解的产生，变异体现了全局最优解的覆盖。 ( 7 ) 若遗传算法在每一代对群体规模为的个体进行操作，实际上处理了大约 o ( 3 ) 个模式，具有很高的并行性，因而具有显著地搜索效率。 尽管如此，早期遗传算法也有不足：一是容易过早收敛，这样就会使其它个体 中的有效基因不能得到有效复制，最终丢失；二是在进化后期染色体之间的差别极 小，整个种群进化停滞不前，搜索效率较低，这样就会导致搜索到的结果不是全局 最优解。 2 2 2 遗传算法的应用 由于遗传算法的适用性强，所以在多种领域都有实际应用，展示了它的潜力和 宽广前景，其主要应用在以下几个方面【】： ( 1 ) 函数优化：函数优化是g a 算法的经典应用领域，也是对遗传算法进行性 能评价的常用算例； ( 2 ) 组合优化：随问题规模的扩大，组合优化问题的搜索空间也急剧扩大，有 5 华北电力火学硕士学位论文 时在目前条件下无法求出精确最优解，只能寻找满意解。实践证明，遗传算法对组 合优化问题中的n p 完全问题非常有效。例如，遗传算法已在求解旅行商问题、背 包问题、装箱问题、图形划分问题等方面得到了成功的运用； ( 3 ) 电力系统：8 0 年代后期以来，遗传算法逐渐在电力系统中得到应用。它不 仅成功地解决了电力系统的经济运行、电网规划、故障诊断、潮流计算等领域的优 化问题，而且在电机、变压器等电磁设备设计中有广泛的应用； ( 4 ) 遗传神经网络：神经网络的应用也r 益广泛，但是它存在一些缺陷，如学 习效率不高、学习过程收敛于局部解等问题。结合遗传算法进行人工神经网络的设 计和训练，就能克服这些困难，显著提高系统性能； 另外，很多专家学者将g a 应用于各自所从事的工程领域，比如v l s i 设计、 运输规划、设备布局、土木工程、生物工程等，对解决具体实践问题起到了极大地 促进作用。 2 3 遗传算法的描述【l 】 i m a x f ( x ) j f x r ( 2 一1 ) i r u 其中，x = 【，艺，】r 为决策变量，厂( x ) 为目标函数，x 尺，尺u 为约束条件， 【，是基本空间，尺是u 的一个子集。满足约束的解x 称为可行解，集合r 表示所有 6 华北电力大学硕士学位论文 满足约束条件的解组成的集合，称为可行解集合。由于目标函数和约束条件的复杂 性限制，很多情况下不可能或没必要求出其精确最优解，因而有时人们的目的只是 求出其近似解或满意解。 遗传算法把问题的解表示成“染色体 ，在算法中它是以某种编码形成的串。 并且，在执行遗传算法之前，给出一群“染色体 ，也即是假设解。然后，把这些 假设解置于问题的“环境 中，并按适者生存的原则，从中选择出较适应环境的 “染色体”进行复制，再通过交叉、变异过程产生更适应环境的新一代“染色体” 群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体上，它 就是问题的最优解。 2 3 1 编码 遗传算法的编码是指把一个问题的可行解从其解空间转换到遗传算法所能处 理的搜索空间的转换方法。解码则是由遗传算法解空间向问题空间的转换。目前主 要的编码方法有：二进制编码、格雷码、浮点数编码、多参数级联编码、多参数交 叉编码【3 4 1 。问题编码一般应满足以下3 个原则： ( 1 ) 完备性：问题空间中所有点( 可行解) 都能成为g a 解码空间中的点( 染 色体位串) 的表现型。 ( 2 ) 健全性：g a 编码空间中的染色体位串必须对应问题空间中的某一潜在解。 ( 3 ) 非冗余性：染色体和潜在解必须一一对应。 在某些情况下，为了提高遗传算法的运行效率，允许生成包含致死基因的编码 位串，它们对应于优化问题的非可行解。虽然这会导致冗余或者无效搜索，但可能 有助于生成全局最优解所对应的个体。 按照遗传算法的模式定理，d ej o n g 进一步提出了较为客观明确的编码评估标 准，称之为编码原理。具体可以概括为两条原则： ( 1 ) 有意义建筑模块编码原则：编码应当易于生成与所求问题相关的短距和低 阶的建筑模块。 ( 2 ) 最小字符集编码规则：编码应采用最小字符集以使问题得到自然、简单的 表示和描述。 2 3 2 群体设定 遗传算法与传统随机类搜索算法的最大区别之一，在于它的整个算法是在解得 群体上进行的。j 下是这一特点使g a 具有了搜索过程的并行性、全局性和鲁棒性。 7 华北电力人学硕士学位论文 所以群体的设定对整个g a 的运行性能具有基础性的决定作用。 群体规模越大，群体中个体的多样性越高，算法陷入局部解得危险就越小，但 是随着群体规模增大，计算量也显著增加。若群体规模太小，使遗传算法的搜索空 间受到限制，则可能产生未成熟收敛的现象。 2 3 3 遗传算子 标准遗传算法包括三个基本操作：选择、交叉和变异。它们构成了遗传算法强 大的搜索核心，是模拟自然选择以及遗传过程中发生的繁殖、杂交和突变现象的主 要载体。遗传算法利用遗传算子产生新一代群体来实现群体进化，算子的设计是遗 传策略的主要组成部分，也是调整和控制进化过程的基本工具【3 5 羽】。 ( 1 ) 选择 选择即从当前群体中选择适应值高的个体以生成交配池的过程。目前，主要有 适应值比例选择、b o l t z m a n n 选择、排序选择、联赛选择等形式。为了防止由于选 择误差或者交叉和变异的破坏作用而导致当前群体的最佳个体在下一代的丢失，d o j o n g 提出了精英选择策略。 ( 2 ) 交叉 g a 交叉算子是模仿自然界有性繁殖的基因重组过程，其作用在于将原有的优良 基因遗传给下一代个体，并生成包含更复杂基因结构的新个体。交叉操作一般分为 以下几个步骤： 1 ) 从交配池中随机取出要交配的一对个体； 2 ) 根据交叉概率成实施交叉操作，配对个体在交叉位置处，相互交换各自的部 分内容，从而形成新的一对个体。 ( 3 ) 变异 变异操作模拟自然界生物体进化中染色体上某位基因发生的突变现象，从而改 变染色体的结构和物理性状。在遗传算法中，变异算子通过变异概率以随机选取某 个染色体上的某位基因进行突变。 2 3 4 终止循环的条件 遗传算法中终止循环的准则，一般依据问题的不同有不同的确定方式。例如， 可以采用以下的准则之一作为判断条件： ( 1 ) 种群中个体的最大适应度超过预先设定值； 8 华北电力大学硕+ 学位论文 ( 2 ) 种群中个体的平均适应度超过预先设定值； ( 3 ) 世代数超过预先设定值。 2 4 遗传算法的流程 我们通常采用的遗传算法的工作流程和结构形式是g o l d b e r g 在天然气管道控制 优化应用中首先提出的，一般称为经典遗传算法( c l a s s i c a lg a ，c g a ) 或者标准遗传 算法( s t a n d a r dg a ，s g a ) 。 图2 - 1经典遗传算法的基本流程图 经典遗传算法的基本流程和结构如图( 2 1 ) 所示。 遗传算法的运行过程为一个典型的迭代过程，其必须完成的工作内容和基本步 骤如下： 1 ) 选择编码策略，把参数集合x 和域转化为位串结构空间s ； 9 华北电力人学硕+ 学位论文 2 ) 定义适应值函数f ( x ) ； 3 ) 确定遗传策略，包括选择群体大小，选择、交叉、变异方法，以及确定交 叉概率以、变异概率、等遗传参数； 4 ) 随机初始化生成群体p ； 5 ) 计算群体中个体位串解码后的适应值f ( x ) ； 6 ) 按照遗传策略，运用选择、交叉和变异算子作用于群体，形成下一代群体； 7 ) 判断群体性能是否满足某一指标，或者已完成预定迭代次数，不满足则返回 步骤6 ) ，或者修改遗传策略再返回步骤6 ) 。 1 0 华北电力大学硕士学位论文 第三章遗传算法的改进 3 1 一般自适应遗传算法 经典遗传算法( c g a ) 采用的都是固定参数，由于遗传算法从本质上说是一种动 态自适应的进化过程，因此固定的参数设置则是对遗传算法性能的一种局限和束 缚。经典遗传算法在进化过程中，各遗传算子的参数保持不变。由于在进化后期， 种群内个体的多样性大幅度减小，适应值接近，因此选择操作的选择压力可能不够， 致使算法接近随机搜索状态。首先，由于交叉、变异在产生新型基因的同时存在着 破坏当前优良基因的概率，使进化过程中存在最优个体的概率遗失而使算法收敛于 局部最优。其次，在算法搜索后期由于种群内个体接近，多样度低，使算法收敛速 度降低而影响了优化效率，同时可能导致算法收敛于局部最优解。因此，用一类固 定的操作及其参数来控制搜索过程显然是不妥的。 针对c g a 存在的这些问题，s r i n v i v a s 等人提出自适应遗传算法( a d a p t i v eg a ， a g a ) ，即交叉概率以和变异概率p 。能够随适应度自动改变，遗传算法的参数中交 叉概率p ，和变异概率p 。的选择是影响遗传算法行为和性能的关键所在，直接影响 算法的收敛性，p ，越大，新个体产生的速度就越快。然而，陴过大时遗传模式被破 坏的可能性也越大，使得具有高适应度的个体结构很快就会被破坏；但是如果以过 小，会使搜索过程缓慢，以至停滞不前。对于变异概率p 。，如果p 。过小，就不易 产生新的个体结构；如果p 。取值过大，那么遗传算法就变成了纯粹的随机搜索算法。 当种群中每个个体的适应度趋于一致或趋于局部最优时，使二者增加，而当种群适 应度比较分散时，使二者减小，同时对适应度高于群体平均适应度的个体，采用较 低的交叉和变异概率，使性能优良的个体进入下一代，而低于平均适应度的个体， 采用较高的交叉和变异概率，使性能较差的个体被淘汰。因此，自适应的阢和p 。能 够提供相对某个解的最佳p ，和p 。自适应遗传算法在保持群体多样性的同时，保 证遗传算法的收敛性【3 8 4 0 1 。自适应遗传算法由于改进了各遗传算子的参数，使得算 法能够适应于种群进化的各个阶段的特征，使得算法的优化效率和解的质量得到提 高。 本文中使用的经典遗传算法、一般自适应算法和改进的遗传算法全部都采用实 数编码，实数编码具有如下的优点： ( 1 ) 适合于遗传算法中表示范围较大的数； ( 2 ) 便于较大空间的遗传搜索； 华北电力人学硕士学位论文 ( 3 ) 提高了遗传算法的精度要求； ( 4 ) 改善了遗传算法的计算复杂性，提高了运算效率； ( 5 ) 可以避免二进制编码进行交叉破坏个体连续的可能性、避免二进制编码的 海明悬崖等问题【 。 一般实数编码的自适应算法步骤如下【4 1 l ： s t e p l 初始化生成随机种群p = 工雄= l ，2 ，) ，其中是种群规模，每一个染色体 x i 可以表示成，l 维向量，即，= ( ，z ，) ； s t e p 2 计算每个个体的适应度大小； s t e p 3 如果满足算法终止的条件，则停止迭代并且给出最优解，否则进入下一步。 s t e p 4 进行遗传操作： ， 1 ) 选择：根据每个个体的适应度，采用比例选择法，根据公式只= ，l 计算每个 石 七= 1 个体被选择的概率，其中五为第k 个个体的适应度； 2 ) 交叉：将选择出来的个体按照两两组合，计算交叉概率 见2驴与掣a 厶 协。， 见i f 六曙 其中f 为两个待交叉个体中适应度大的个体的适应度，正懵，厶。分别是群体适应度 的平均值和群体中最优个体的适应度，以。，见：为最大和最小交叉概率并且满足 0 见2 见i l 。 交叉操作如下：根据交叉概率见随机选择父代个体，进行两两组合，假设 一= ( 而i ，z )( 3 2 ) x 7 = ( 彳，)( 3 3 ) 为待交叉的两个父代个体，通过算术交叉生成两个新的子代个体： 。= ( 一i 。，- n g w g * 9 。删) ( 3 4 ) = ( 州，。一，。) ( 3 5 ) 1 9 华北电力大学硕士学位论文 其中 x 。i 。= 口+ ( 1 一口) ，聊【l ，刀】，口( o ，1 ) 一= ( 1 一口) 吒+ t ，m 【l ，刀】，口( o ，1 ) 3 ) 变异：首先计算每个个体的变异概率 ： 。一! ! 型二掣丘曙 【- 正嗜 ( 3 - 6 ) ( 3 - 7 ) ( 3 8 ) 其中厂是个体适应度值，：为最大和最小变异概率并且满足o ： p m 。 o 留 p 。1 u 其中厶为上一代最优解所对应的函数值，f 为当前代数，f 为预先设置好的最大迭 代次数。 3 2 2 交叉方式的改进 g a 交叉算子是模仿自然界有性繁殖的基因重组过程，在该过程中群体的个体 品质得以提高。直观来讲，选择算子将原有的优良基因遗传给下一代个体，而交叉 算子则可以生成包含更多优良基因的新个体。交叉方式的设计，一般与所求问题的 特征有关。通常需要考虑如下因素【4 3 4 4 】： ( 1 ) 必须保证优良基因能够在下一代中有一定的遗传和继承的机会： ( 2 ) 必须保证通过交叉操作存在一定的生成优良基因的机会； 1 4 华北电力人学硕士学位论文 ( 3 ) 交叉方式的设计与问题编码紧密相关，必须结合编码的结构来设计高效的 交叉算子。 针对以上三点指导因素，本文改进的交叉操作是先在交叉前产生三个服从均匀 分布的随机数a ( o ，1 ) 、6 ，c ( 一l ，1 ) ，然后假设一，x 2 是要交叉的两个父代，个体变 量为n 维，则一，工2 可以表示成一= ( 爿，e ) ，x 2 = ( 彳，) ，其中 x ；【口，6 ，】，f = l ，2 ；= l ，2 ，刀，设定a 1 = ( ：，：，：) ， a 2 = ( ；，；，：) 为位 移变量，其中a ；= m i n ( 彩一a ) ，( 岛一# ) ) ，( f = l ，2 ；j = l ，2 ，订) ，最后进行两次操作得： x ：= x ，+ 6 。，( 3 - 1 2 ) l ， t x 2 工+ c 长x i n c w ：a x i ： a x 二鼍i 口a h ) x i i 仔 i x 2 “=2 + ( 1 一 r 、。 x l x 2 ，一一r ，工z 一9 分别为两次操作所产生的子代，从这4 个子代中选取适应度大的两 个保留到下一代。通过这种操作可以有效的避免两个数值相近的个体进行“近亲繁 殖”( 数值相近的个体若只进行公式( 3 1 3 ) 的操作会导致种群多样性快速下降) ，同时 由于6 ，c 的选取，生成的x l x 2 是两个彼此之间相互独立的个体，由公式( 3 1 3 ) 决定 的后代还可以使子代遗传父代的某些有用因素。同时由于公式( 3 1 2 ) 的位移调整， 使得公式( 3 1 3 ) 生成的后代比一般的算术交叉产生后代的范围得到扩大，提高算法 的搜索范围，避免搜索陷入一个局部区域而出现“早熟”。最后再引入竞争机制在这 四个后代中选出两个最好后代个体，这样在保证多样性的同时可以加快收敛的速 度。 3 2 3 变异方式的改进 粒子群算法( p a r t i c l es w a r mo p e r a t i o n ，p s o ) 是由美国普渡大学的k e n n e d y 和 e b e r h a r t 于1 9 9 5 年提出的一种集群优化算法，它是受鸟群和鱼群群体运动的行为方 式启发而提出的一种具有代表性的群集智能方法。粒子群算法从待优化问题可能解 的一个子集开始，每个可能解都是搜索空间中的一个“粒子，该子集称为“粒子 群”。所有的粒子都有一个由被优化的函数决定的适应度，每个粒子还有一个速度 决定他们飞翔的方向和距离，粒子群就追随当前最优粒子在解空间中通过反复迭代 找到最优解。在每一次迭代中，粒子通过跟踪两个“极值来更新自己。第一个就 是粒子本身所找到的最优解，这个解叫做个体极值；另一个极值是整个种群目前找 到的最优解，这个极值是全局极值。由于粒子群算法概念简单，实现容易，短短几 年时间，就获得了很大的发展，并在一些领域得到应用。 变异即对群体中个体的某些基因作出变动。变异的目的有两个，一个是使遗传 1 5 华北电力人学硕+ 学位论文 算法具有局部的随机搜索能力，另一个是保持群体的多样性。变异在g a 中的作用 是第二位，与交叉算子相比，当变异概率较小时，在进化初期模式存活概率比较高； 在进化稳定期，与交叉算子下的模式存活概率基本相同；当变异概率比较大时，变 异算子作用下模式的存活概率比交叉算子下要小的多【l 】。 为了更好的满足变异的两个目的，本文将遗传算法的变异操作按照粒子群的原 理进行改进，将粒子跟踪的两个“极值”变换成遗传算法中的参数。其中将个体极 值替换为遗传算法中个体的取值范围的上界，再将全局极值替换为当前遗传算法寻 找到的最优个体。具体操作如下： 假设个体= ( ，蔓，z ) 的第歹个分量x ：为待变异分量，变异之后的分量为 。变异操作依据方程o = w e ；+ q r , ( b j - g ) + c , r 2 f x j 一) ，若矽州 哆则矽删= 吃，其中a i ，巧为分量的上下界，为前一代最优个体 的第_ ，个分量，w 为加权系数，c i ，c 2 是两个正常数，；，乞是两个o l 区间的服从均匀 分布的随机数。参照文献 4 5 1 e e 的论述，本文取w = 0 7 2 9 8 ，c i = c 2 = 1 4 9 4 4 5 。 3 3 算法步骤 s t e p l 采用实数编码产生初始种群，在函数定义域内按照均匀分布随机产生个个体 ，) ( 扛l ，2 ，) ，设定最大进化代数设为t ： 兰彳 一 s t e p 2 计算每个个体的函数值，之后根据歹= - ! = l 计算种群函数的平均值，最后按 照本文设定的适应度函数，即公式( 3 9 ) 计算当前种群中每个个体的适应度。 s t e p 3 最优保存策略，结合文献【8 】本文将最优保存策略算法做如下修改：第一步计 算每个个体的函数值，然后排序，找出最优解，最差解；第二步若上一代最 优解的函数值比当前最优解的函数值大，则用上一代的最优解替换当前最优 解；若上一代的最优解函数值小，则用上一代的最优解替换当前中的最差解； s t e p 4 根据每个个体的适应度，采用比例选择法。通过公式( 3 9 ) 进行的转换，使得 在进化前期原本函数值小的个体将有更大的概率被选择，保持了种群的多样 性； s t e p 5 按照公式( 3 - 1 ) 计算交叉概率，然后在种群中按照交叉概率随机选择父代个体， 然后应用本文改进的交叉操作进行交叉，最后通过竞争选取两个最好的个体作 1 6 华北电力人学硕十学位论文 为子代个体； s t e p 6 依据公式( 3 8 ) 计算变异概率，选定变异个体，将选定的个体依照本文采用的 拟粒子群变异方法进行变异操作； s t e p 7 满足迭代次数即停止，否则代数加l ，转入s t e p 2 。 3 4 仿真实验 3 4 1 测试函数 为了验证改进遗传算法的效果，选用以卜七个典型幽数迓仃测试： ( 1 ) 问题异 片：仨嚣品2 j 2 _ 翥2 1 2 , 51 2 1 仔 【五，艺，毛【一 g ，为单峰二次函数，当( _ ，x 2 ，) = ( 0 ，0 ，o ) 时有全局最小值o ；为了方便编程将问 题日转化为求全局最大值，得到问题耳： f ： ：嚣篡倒5 1 2 1 2 , 51 2 喇 【五，屯，屯卜 ( 2 ) 问题昱 罡： = 翁豇呱1 0 嬲卜2 一 p 函麴图像为! 1 7 华北电力大学硕七学位论文 图3 - 1 函数石图像 由函数图像可以看出五是一维连续且含三角函数的多峰函数，其中当x ：1 8 5 0 5 时，全局最大值为3 8 5 0 3 ： ( 3 ) 问题忍( s e h u f f e r lf u n c t i o n ) 函数图像为： 忍：mm皇i彳+荨毗5【西舻(50(彳+毫)n)+lo】(3-16)1 。 【五，恐卜0 , 1 0 】 1 0 图3 - 2 函数9 3 图像 9 3 是s c h a f f e r 函数，由函数图像可以看出当( 1 ，x 2 ) = ( o ，o ) 时有全局最小值0 。为 了方便编程将问题只转化为求全局最大值，得到问题碍： 1 8 8 6 4 2 o o ， ( 4 ) 问题只 函数图像为： 华北电力大学硕十学位论文 f m a x f 3 = l o - t g + ) n 2 5 s i n 2 ( 5 0 ( g + z ) 仉1 ) + 1 o 】 【玉，毛【一1 0 ，1 0 】 只：b 三一 0 8 0 6 0 4 0 2 0 1 0 垃 0 加 x ， 图3 - 3 函数9 4 图像 为了方便观察最小值，此函数在卜