（应用数学专业论文）混合交叉策略遗传算法及其应用研究.pdf

华北电力大学硕士学位论文摘要 摘要 本文基于拉普拉斯交叉和幂函数变异，给出了一类新的混合交叉策略的遗传算 法( h l c p m ) 。通过引入可行种群和不可行种群并在后代保留临时可行解和不可行 解，使其混合交叉，保证了种群多样性。选取新的交叉和变异算子，即拉普拉斯交 叉( l c ) 算子和幂函数变异( p m ) 算子，重新产生子代个体，提高全局搜索能力。 通过对带有边界约束的函数优化问题进行数值计算，实验结果表明，新算法是有效 的，其搜索到高性能解的能力较经典遗传算法( s g a ) 有明显提高，且算法稳定性 有所增强。针对联营体交易模式的电力市场，将新算法应用到i s o 优化问题的求解 过程中，通过对i e e e 标准1 1 节点系统进行实际计算，结果表明所提算法是可行和 有效的。 关键词：遗传算法，混合交叉，函数优化，电力市场，i s o 优化问题 a bs t r a c t an e wh y b r i dc r o s s o v e rg e n e t i ca l g o r i t h m ( n a m e dh l c p m ) i sp r o p o s e di nt h i s p a p e rb a s e do nt h el a p l a c ec r o s s o v e ra n dp o w e rm u t a t i o n i nt h eh l c p m ，t w ok i n d so f p o p u l a t i o nw i t hf e a s i b l ea n di n f e a s i b l ea r es y n c h r o n o u s l yi n t r o d u c e di nt h eg e n e t i c p r o c e s s ，a n dt h eh y b r i dc r o s s o v e ra n dm u t a t i o na r er e s p e c t i v e l yb a s e do nl a p l a c e o p e r a t o ra n dp o w e ro p e r a t o r t h en u m e r i c a le x a m p l e sw i t h10c l a s s i c a lt e s tp r o b l e m s d e m o n s t r a t et h a tt h es t a b i l i t yo fa l g o r i t h ma n dt h ea b i l i t yo fg l o b a ls e a r c hf o rt h e h l c p ma leb e t t e rt h a nt h es a m p l eg e n e t i ca l g o r i t h m ( s g a ) a sa na p p l i c a t i o n ，t h e m a t h e m a t i c a lp r o g r a m m i n gw i t hc o n s t r a i n e db yi e e e11 - b u ss y s t e mf o rt h ei n d e p e n d e n t s y s t e mo p e r a t i o n ( i s o ) i np o o l - b a s e de l e c t r i c i t ym a r k e t si ss o l v e db yh l c p m ，a n dt h e s o l u t i o nr e s u l ts h o w st h ef e a s i b i l i t ya n dv a l i d i t yo ft h ea l g o r i t h m t i a nx 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 m ax i n s h u n k e yw o r d s ：g e n e t i ca l g o r i t h m ，h y b r i dc r o s s o v e r ，f u n c t i o no p t i m i z a t i o n ， e l e c t r i c i t ym a r k e t ，i s oo p t i m i z a t i o np r o b l e m 华北电力大学硕士学位论文摘要 摘要 本文基于拉普拉斯交叉和幂函数变异，给出了一类新的混合交叉策略的遗传算 法( h l c p m ) 。通过引入可行种群和不可行种群并在后代保留临时可行解和不可行 解，使其混合交叉，保证了种群多样性。选取新的交叉和变异算子，即拉普拉斯交 叉( l c ) 算子和幂函数变异( p m ) 算子，重新产生子代个体，提高全局搜索能力。 通过对带有边界约束的函数优化问题进行数值计算，实验结果表明，新算法是有效 的，其搜索到高性能解的能力较经典遗传算法( s g a ) 有明显提高，且算法稳定性 有所增强。针对联营体交易模式的电力市场，将新算法应用到i s o 优化问题的求解 过程中，通过对i e e e 标准1 1 节点系统进行实际计算，结果表明所提算法是可行和 有效的。 关键词：遗传算法，混合交叉，函数优化，电力市场，i s o 优化问题 a bs t r a c t an e wh y b r i dc r o s s o v e rg e n e t i ca l g o r i t h m ( n a m e dh l c p m ) i sp r o p o s e di nt h i s p a p e rb a s e do nt h el a p l a c ec r o s s o v e ra n dp o w e r m u t a t i o n i nt h eh l c p m ，t w ok i n d so f p o p u l a t i o nw i t hf e a s i b l ea n di n f e a s i b l ea r es y n c h r o n o u s l yi n t r o d u c e di nt h eg e n e t i c p r o c e s s ，a n dt h eh y b r i dc r o s s o v e ra n dm u t a t i o na r er e s p e c t i v e l yb a s e do nl a p l a c e o p e r a t o ra n dp o w e ro p e r a t o r t h en u m e r i c a le x a m p l e sw i t h10c l a s s i c a lt e s tp r o b l e m s d e m o n s t r a t et h a tt h es t a b i l i t yo fa l g o r i t h ma n dt h ea b i l i t yo fg l o b a ls e a r c hf o rt h e h l c p ma leb e t t e rt h a nt h es a m p l eg e n e t i ca l g o r i t h m ( s g a ) a sa na p p l i c a t i o n ，t h e m a t h e m a t i c a lp r o g r a m m i n gw i t hc o n s t r a i n e db yi e e e11 - b u ss y s t e mf o rt h ei n d e p e n d e n t s y s t e mo p e r a t i o n ( i s o ) i np o o l - b a s e de l e c t r i c i t ym a r k e t si ss o l v e db yh l c p m ，a n dt h e s o l u t i o nr e s u l ts h o w st h ef e a s i b i l i t ya n dv a l i d i t yo ft h ea l g o r i t h m t i a nx 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 m ax i n s h u n k e yw o r d s ：g e n e t i ca l g o r i t h m ，h y b r i dc r o s s o v e r ，f u n c t i o no p t i m i z a t i o n ， e l e c t r i c i t ym a r k e t ，i s oo p t i m i z a t i o np r o b l e m 声明尸明 本人郑重声明：此处所提交的硕士学位论文混合交叉策略遗传算法及其应用研 究，是本人在华北电力大学攻读硕士学位期间，在导师指导下进行的研究工作和取得 的研究成果。据本人所知，除了文中特别加以标注和致谢之处外，论文中不包含其他人 已经发表或撰写过的研究成果，也不包含为获得华北电力大学或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 学位论文作者签名：日期： 关于学位论文使用授权的说明 本人完全了解华北电力大学有关保留、使用学位论文的规定，即：学校有权保管、 并向有关部门送交学位论文的原件与复印件；学校可以采用影印、缩印或其它复制手 段复制并保存学位论文；学校可允许学位论文被查阅或借阅；学校可以学术交流为 目的，复制赠送和交换学位论文；同意学校可以用不同方式在不同媒体上发表、传播 学位论文的全部或部分内容。 ( 涉密的学位论文在解密后遵守此规定) 作者签名： 日期： 导师签名： 日期： 华北电力大学硕士学位论文 1 1 课题研究背景和意义 第一章绪论 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 是由美国m i c h i g a n 大学j o h nh o l l a n d 教授 等人于2 0 世纪6 0 年代末创建的。它来源于达尔文的进化论和孟德尔、摩根的遗传 学理论n _ 1 ，通过模拟生物的进化机制来构造人工系统。它是一种自适应全局性搜索 算法，具有强鲁棒性及通用优化能力口，。 遗传算法属于自下而上的优化方法，它从改变基因的配置来实现问题的整体优 化，不包含待解决问题所持有的形态h 1 。类似于生物的进化过程，遗传算法处理的 是变量集合的编码而非变量本身。它仅利用适应度函数的信息，不需要函数满足某 些特定的数学性质( 如连续、可微等) ，在用概率规则来搜索解空间时可以在若干起 始点并行地进行，能够有效的进行全局寻优哺1 。传统遗传算法虽操作简单，但存在 易早熟和局部收敛性差等问题h 1 。随着研究的不断进行，众多学者相继发现许多新的 改进算法阳7 引，如改进交叉和变异概率、改进遗传算子、混合策略遗传算法，使得 该算法得到了更广泛的应用。 随着经济、科技和社会的不断发展，人们遇到的各种问题越来越复杂，在诸多 实际应用领域，如工程设计四1 、生物工程n 们、人工智能n l l 2 1 3 3 、计算机科学n 4 1 等， 都迫切需要求解全局最优化问题的有效方法。函数优化问题是遗传算法的经典应用 领域，也是对遗传算法性能进行评价的最常用算例。传统的优化算法是一种试探性 的寻优方法，但一般对函数要求较高，当目标函数比较复杂时，求出最优解很困难， 有时甚至会得不到最优解。与传统的启发式优化搜索算法( 爬山方法、模拟退火方 法、蒙特卡罗方法等) 相比，遗传算法的本质特征在于群体搜索策略和简单的遗传 算子n 钉。近年来新出现的人工智能技术( 如神经网络、混沌理沦、遗传算法等) 已越 来越多地应用于电力工业领域。“厂网分开后的发电企业都将面临制定和实施一 套合理有效的报价策略问题，合理的报价策略能使其最大限度地回避风险、增加收 益n 氐1 7 1 。由此i s o 优化问题具有广泛的应用背景，其求解也具有极为重要的应用价 值。 1 2 遗传算法的发展历程和研究现状 遗传算法是借鉴生物在自然环境中的遗传和进化过程而发展起来的一种全局 优化概率搜索算法n8 1 。自然界中，生物的进化过程隐含着自然优化的机制，复杂的 生物种群在自身繁衍的过程中不断的进化。达尔文的自然选择学说认为，生物进化 华北电力大学硕士学位论文 的动力和机制在于自然选择，生物要生存下去，就必须进行生存斗争。在生存斗 争中有利于生存的个体具有更多的生存机会，其后代也多，反之就少。遗传和变异 是决定生物进化的内在因素，生物的遗传特性使生物界的物种能保持相对的稳定； 变异特性使生物个体产生新的性状，形成新的物种，推动生物的进化和发展乜1 。现 代生物学将遗传和进化作为生物学的主要研究对象，人们还没有完全揭开它们的奥 秘，既不完全掌握其机制，也不完全清楚染色体编码和译码过程的细节，更不完全 了解其控制方式。 遗传算法研究的兴起是在2 0 世纪8 0 年代末和9 0 年代初期，但它的历史起源 可追溯到6 0 年代n 引。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 9 7 5 年在遗传算法研究的历史上是十分重要的一年。这一年，h o l l a n d 出版了他的 著名专著自然系统和人工系统的适配。该书系统地阐述了遗传算法的基本理论 和方法，并提出了对遗传算法的理论研究和发展极为重要的模式理论( s c h e m a t a t h e o r y ) 。该理论首次确认了结构重组遗传操作对于获得内在并行性的重要性。同年， d ej o n g 完成了他的重要论文遗传自适应系统的行为分析。他在该论文中所做的 研究工作可看作是遗传算法发展进程中的一个里程碑，这是因为他把h o l l a n d 的模 式理论与他的计算实验结合起来。尽管d ej 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 ej o n g 的研究工作为遗 传算法及其应用打下了坚实的基础。 进入8 0 年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究 都成了十分热门的课题心。尤其是遗传算法的应用研究显得格外活跃，不但它的应 用领域扩大，而且利用遗传算法进行优化和规则学习的能力也显著提高，同时对产 业应用方面的研究也在摸索之中。此外，一些新的理论和方法在应用研究中也得到 了迅速的发展，这些无疑都给遗传算法增添了新的活力。人们对遗传算法的兴趣同 益增长源于两个特定的背景n 1 ：一是工程领域，特别是人工智能和控制领域，不断 涌现出超大规模的非线性系统。在这些系统的研究中存在着大量的经典优化方法所 2 华北电力大学硕士学位论文 不能有效求解的优化问题，诸如神经网络连接权重及网络拓扑结构的优化、知识库 的维护与更新、模糊系统中模糊规则的选取及隶属函数的确定等等。二是遗传算法 是一种模拟自然演化这一学习过程的求解问题方法，它能以独立的或与其它方法结 合使用的形式设计智能机器学习系统。 现在对遗传算法的理论研究和应用研究仍然十分活跃，国内外有关遗传算法的 研究热潮方兴未艾口副。众多的研究单位和频繁的国际学术活动集中反映了遗传算法 的学术意义和应用价值。目前，还没有一种通用的方法能根据要解决的问题自动地 设置高效的控制参数，只能根据经验和多次运行遗传算法的结果进行人工设置和修 正。大部分研究机构主要集中于研究遗传算法和进化算法作为优化问题通用求解算 法的一系列问题h 1 。国外对于遗传算法的研究已经处于应用阶段。在应用方面有优 化问题方面的巡回推销员( t s p ) 问题，在规则学习方面有基于遗传的机器学习系 统、分类器系统、逐次决策问题系统等。我国有关遗传算法、进化计算的研究，一 直处于不断上升的时期。近年来，遗传算法、进化计算的应用在许多领域取得了令 人瞩目的成果。发表在学术刊物上的相关文章也在逐年上升。武汉大学刘勇、康立 山等出版了非数值并行计算一遗传算法，陈国良、王煦法等出版了遗传算法 及其应用，周明、孙树栋等出版了遗传算法原理及其应用。目前，西北工业大 学的遗传算法原理与应用项目是在国家计划、国家自然科学基金和教育部优秀青年 教师基金的支持下进行的，取得了丰硕的研究成果，极大地促进了国内在遗传算法 研究与应用领域的发展。北京师范大学以方福康教授为首的研究集体一直专注于对 遗传算法与复杂适应系统的研究。 传统的优化方法主要有三种n 引：枚举法、启发式算法和搜索算法。枚举算法在 空间较大时，求解效率较低甚至无法求解。启发式算法虽求解效率高，但对每一个 需求解的问题必须找出其特有的启发式规则，这个启发式规则一般不具通用性。搜 索算法虽保证不了一定能得到最优解，但若适当地利用一些启发知识，就可以在近 似解的质量和效率上达到较好的平衡。 随着问题种类的不同及问题规模的扩大，遗传算法为我们提供了一种能以有限 的代价来解决搜索和优化问题的通用方法。它与传统的优化方法的主要区别在于： 遗传算法具有自组织、自适应和自学习性，本质并行性以及它仅仅需要影响搜索方 向的目标函数和相应的适应度函数等。经过学者们不断深入的研究，遗传算法在 基础理论和算法设计及应用方面均得到了突破性发展，已经成为计算机科学、信息 科学、应用数学、运筹学等诸多学科所共同关注的热点研究领域心引。 遗传操作是遗传算法的关键操作步骤，研究和改进遗传操作有着重要的作用。 算法参数主要包括种群规模、交叉概率p 和变异概率e 。文献 1 9 指出，种群规 华北电力火学硕士学位论文 模一般取在2 0 到1 2 0 之间，交叉概率p 一般取在0 4 0 到0 9 9 之间，变异概率只 一般取在0 0 0 0 l 到0 0 1 之间。遗传算子中的选择、交叉和变异也分别有着不同的 方式：选择主要有适应值比例选择、排序选择、联赛选择、精英选择等；交叉主要 有算术交叉、混合交叉等；变异主要有随机变异、非均匀变异、均匀变异等o 。文 献 2 3 在大量资料基础上声明了参数环境对遗传算法的性z 日, 匕i - - 和结果是至关重要的。 h d a v i d 指出交叉算子在遗传算法中起关键作用，是产生新个体的主要方式，它使 得亲代的优良特性在后代能够继承下来。变异算子主要用于改善算法局部搜索能力 和维持种群多样性，防止过早收敛的现象。参数选择直接影响算法性能，因而合理 的选择参数是应用遗传算法所要解决的关键问题之一。文献 2 4 中提及h o l l a n d 模 式定理建议采用二进制编码，这得到许多学者的支持。常用的编码方式有二进制编 码和实数编码等。实数编码相对于二进制编码不存在编码和解码过程，能够大大提 高解的精度和运算速度，稳定性较高，便于大空间搜索，但也存在收敛速度慢和易 出现早熟现象的问题。文献 2 5 在分析传统遗传操作机制存在缺陷的基础上，提出 了一种改进遗传算法( r i g a ) ，重点研究了实数编码的自适应变焦变异算子。文献 中设计的自适应变焦变异算子的作用在于使适应度较大的个体在较小的范围内变 异，而适应度较小的个体在较大的范围内变异。这种改进算法的优点是对最优个体 缩小了其变异范围，同时对适应度较小的个体增大了其变异范围以及变异概率，从 而有效的避免了算法收敛至局部最优，以保证群体中个体的多样性。 传统遗传算法的局部搜索能力差，单用简单的遗传算法在许多情况下不十分有 效，因此一般对遗传算法进行适当的改进或将遗传算法与传统的、基于问题知识的 启发式搜索技术相结合( 即混合遗传算法) 来解决此问题，其基本思想是运用启发式 方法作局部优化，采用遗传算法作全局最优点的探索。混合遗传算法的基本思想乜础 是：对于每个新产生的后代在其进入下一代群体之前应用局部优化技术( 如爬山法， 模拟退火法等) ，使之移动到最近的局部最优点。在混合遗传算法中，运用启发式 方法作局部优化，采用遗传算法作全局最优点的探索。由于遗传算法与传统优化方 法的互补性，混合遗传算法通常比单一算法性能优越，这也使得混合遗传算法成为 近年来研究的主要方向。文献 2 7 提出了求解非线性方程组的一种新算法，即将非 线性方程组的数值求解问题转化为最优化问题，再利用浮点遗传算法全局群体搜索 能力及起始搜索速度快的特点，快速得到接近精确解的较优解，之后将其作为拟牛 顿法迭代的初始值，利用其局部寻优能力非常强的特点，快速迭代至精确解。每种 算法在解决某类问题时都有着自身的优势，我们受到混合思想的启发，在本课题研 究中拟采用混合交叉策略遗传算法，应该能够得到良好的效果。 自适应遗传算法是根据个体适应度集中程度来确定交叉概率和变异概率的。自 适应遗传算法的提出，从一定程度上改善了基本遗传算法易早熟、局部搜索能力差 4 华北电力大学硕士学位论文 等缺点。文献 2 8 针对遗传算法在全局优化问题中容易出现早熟和收敛速度慢的问 题，根据群体适应值的分布特点，启发性地提出了一种新的基于小生境的自适应遗 传算法( a n g a ) 。采用一种新的适应值计算方法，引入了一个自适应的常数c m 根据群体中各个个体的适应值分布情况加以启发，通过自适应调整g i n ，以适时改 变群体适应值的分布，优化了各个个体被选择的概率。同时采用了小生境技术，并 对交叉和变异位置引入了自适应的非均匀选择机制。采用典型的全局优化测试函数 进行验证，实验结果表明该方法能够明显地改善全局寻优能力，并大大加快了收敛 速度。文献 2 9 针对标准遗传算法在实际应用中存在的早熟问题，设计了标准遗传 算法的一种改进形式即模糊自适应遗传算法。该算法利用种群的方差和熵来衡量种 群多样性，并根据每代种群的方差和熵设计模糊推理系统来自适应地控制交叉概率 和变异概率。通过多峰函数优化问题的仿真实验，表明了该模糊自适应遗传算法的 可行性和有效性。 1 3 本课题主要工作 1 )使用混合交叉策略提出一种新的遗传算法 科学研究和生产生活中许多问题都可以转化为求解一个带约束条件的函数优 化问题。遗传算法与许多基于梯度的优化算法比较，具有不需要目标函数和约束条 件可微，且能收敛到多个全局最优解的优点。因此，它成为一种约束优化问题求解的 有力工具。为了避免惩罚策略中选取惩罚因子的困难，也为了使约束优化问题简单 化，针对目前的约束处理方法中存在的问题，本文引入可行种群和不可行种群并在 每代保留固定规模的临时可行解和不可行解，将可行解和不可行解进行混合交叉， 在增强种群多样性的同时对问题的解空间进行搜索。本课题采用新的交叉和变异算 子，即拉普拉斯交叉( l c ) 算子和幂函数变异( p m ) 算子。同时，采用遗传修复 策略，对可行和不可行个体分别定义不同的评价函数并以轮盘赌的方法进行选择操 作。对带有边界约束的函数优化问题进行仿真实验，结果表明新的混合交叉策略遗 传算法对于大部分算例收敛概率较高，收敛速度较快，是一种可行的算法。 2 1将混合交叉策略遗传算法应用到求解i s o 优化问题中 目前，世界各国的电力市场交易模式大致可分为：电力联营模式( p o w e rp 0 0 1 ) 和双边交易模式( b i l a t e r a lt r a d e ) 两种。其中，电力联营模式是我国电力市场的主 要交易模式。在联营体模式中，必须成立独立的电网运行机构，又称为独立系统操 作员( i n d e p e n d e n ts y s t e mo p e r a t o r ，简记i s o ) ，对电网进行调度、运行，并且要 求该机构与所有市场成员没有利益关系。电网运行机构根据市场报价制定交易计 划，计算系统的边际电价、输电电价、辅助服务电价。在此背景下，i s o 优化问题 华北电力火学硕士学位论文 的求解有着重要的研究意义和应用价值。本文将混合交叉策略遗传算法应用于对 i s o 优化问题的求解当中，以实际算例验证了算法的可行性和应用有效性。 6 华北电力大学硕七学位论文 第二章传统遗传算法 2 1 遗传算法的基本特征 遗传算法将“适者生存，优胜劣汰”的生物进化原理n 卫1 引入到待优化参数组成 的编码串优化群体中，按照特定的适应值及一系列遗传操作对每个个体进行筛选， 从而使适应性高的个体被保留下来，组成新的群体。新群体包含了上一代的大量的 有用信息，并且引入了新的优于上一代的个体。这样周而复始，群体中各个体适应 值不断提高，直至满足一定的极限条件。此时，群体中适应值最高的个体即为待优 化参数的最优解。正是由于遗传算法这一独特的工作原理，使得它能够在复杂空间 进行全局优化搜索，并具有较强的鲁棒性。另外，遗传算法还具有计算简单以及功 能性强的特点，对于搜索空间它没有其它算法要求的连续、可微等限制性约定。 从数学角度看，遗传算法实质上是一种搜索寻优技术。它从某一初始群体出发， 遵照一定的操作规则，不断迭代计算，逐步逼近最优解。这种搜索技术，有如下特 点： 1 ) 智能式搜索。遗传算法的搜索策略，既不是盲目式的乱搜索，也不是穷举式 的全面搜索，它是有指导的搜索。指导遗传算法执行搜索的依据是适应度，也就是 它的目标函数。利用适应度，使遗传算法逐步逼近目标值。 2 ) 渐进式优化。遗传算法利用选择、交叉、变异等操作，使新一代的结果优越 于旧一代，通过不断迭代，逐渐得出最优的结果，它是一种反复迭代的寻优过程。 3 ) 全局最优解。遗传算法由于采用交叉、变异等操作，产生新的个体，扩大了 搜索范围，使得搜索得到的优化结果是全局最优解而不是局部最优解。对于多峰函 数而言，假若搜索范围过于狭窄，有可能误以为低峰便是最优解，但是实际上遗传 算法也有达到最高峰的可能。 4 ) 黑箱式结构。遗传算法根据所解决问题的特性，进行编码和适应度选择。一 旦完成字符串和适应度的表达，其余的选择、交叉、变异等操作都可以按常规手续 执行。个体的编码如同输入，适应度如同输出。遗传算法从某种意义上讲是一种只 考虑输入与输出关系的黑箱问题，它只研究输入与输出的数量关系，并不深究造成 这种关系的原因。 5 ) 通用性强。传统的优化算法，需要将所解决的问题用数学式子表示出来，常 常要求解该数学函数的一阶导数或二阶导数。采用遗传算法，只用编码及适应度表 示问题，并不要求明确的数学方程及导数表达式。因此，遗传算法通用性强，可应 7 华北电力大学硕十学位论文 用于离散问题及函数关系不明确的复杂问题。有人称遗传算法是一种框架型算法， 它只有一些简单的原则要求，在实施过程中可以赋予更多的含义。 6 ) 并行式算法。遗传算法是从代表问题可能潜在解集的一个种群开始的，而一 个种群则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特 征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其基因型是某种 基因组合，它决定了个体形状的外部表现。因此，在一开始需要实现从表现型到基 因型的映射即编码工作。初始种群产生后，按照“适者生存，优胜劣汰的原理， 逐代演化产生出越来越好的近似解。在每一代，根据问题域中个体的适应度大小选 择个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新解集 的种群。这个过程导致种群像自然进化一样，后代种群比前代更加适应环境，末代 种群中的最优个体通过解码，可以作为问题的近似最优解。 遗传算法采纳了自然进化模型，如选择、交叉、变异等等。算法计算开始时， 规模为的种群随机的初始化，计算种群中每个个体的适应度，第一代即初始代产 生。如果不满足优化准则，开始产生新一代的计算。为了产生下一代，按照适应度 选择个体，父代要求基因重组( 交叉) 而产生子代。所有的子代按一定概率进行变 异。然后子代的适应度被重新计算，子代被插入到种群中取代父代，构成新的一代。 此过程循环执行，直到满足优化准则为止。 单一种群的遗传算法很强大，可以很好的解决相当广泛的问题。但采用多种群 即有子种群的算法往往会获得更好的结果。每个子种群像单种群遗传算法一样独立 的演算若干代后，在子种群之间进行个体交换。这种多种群遗传算法更加贴近于自 然中种族的进化，称为并行遗传算法( p g a ) 啼1 。 2 2 遗传算法的基本描述 2 2 1 遗传算法的基本流程 遗传算法在整个进化过程中的遗传操作是随机的，但它所呈现出的特性并不是 完全随机搜索，它能有效利用历史信息来推测下一代期望性能有所提高的寻优点 集。这样一代一代地不断进化，最后收敛到一个最适应环境的个体上，求得问题的 最优解。遗传算法所涉及的五大要素：参数编码、初始种群的设定、适应度函数的 设计、遗传操作的设计和控制参数的设定。 遗传算法的运行过程为一个典型的迭代过程，其工作内容和基本步骤为： 1 ) 选择编码策略，把参数集合x 和域转换为串结构空间s ： 2 ) 定义适应度函数f ( x ) ； r 华北电力大学硕士学位论文 3 ) 确定遗传策略，包括选择群体大小、选择、交叉、变异方式，以及确定 交叉概率只、变异概率只等遗传参数； 4 1 随机初始化生成群体p ； 5 ) 计算种群中个体位串解码后的适应度函数值( x ) ； 6 ) 按照遗传策略，运用选择、交叉、变异算子作用于群体，形成下一代群体； 7 ) 判断群体性能是否满足某一指标，或者已完成预定迭代次数，不满足则返 回步骤6 ) ，或者修改遗传策略再返回步骤6 ) 。 i 编码 i 上 i 群体p i 2 2 2 遗传编码 图2 一l遗传算法基本流程 9 华北电力大学硕士学位论文 遗传算法中进化过程是建立在编码机制基础上的，编码对于算法的性能如搜索 能力和种群多样性等影响很大。h o l l a n d 提出的遗传算法是采用二进制编码来表现 个体的遗传基因型的，其优点在于编码、解码操作简单，交叉、变异等遗传操作便 于实现；其缺点在于，不便于反映所求问题的特定知识，对于一些连续函数的优化 问题等，也由于遗传算法的随机特性而使得其局部搜索能力较差；对于一些多维、 高精度要求的连续函数优化，二进制编码存在着连续函数离散化时的映射误差。个 体编码串较短时，可能达不到精度要求；而个体编码串的长度较长时，虽然能提高 精度，但却会使得算法的搜索空间急剧扩大。如果个体编码串特别长时，会造成遗 传算法的性能降低。诸多学者对遗传算法的编码方法进行了多种改进，如，为提高 遗传算法局部搜索能力，提出了格雷码编码；为改善遗传算法的计算复杂性、提高 运算效率，提出了实数编码、符号编码方法等。 问题编码一般应满足以下3 个原则n ： 1 ) 完备性( c o m p l e t e n e s s ) ：可行解集合中的所有点( 可行解) 都能成为g a 编码空间中的点( 染色体位串) 的表现型。 2 )健全性( s o u n d n e s s ) ：g a 编码空间中的染色体位串必须对应可行解集合 中的某一潜在解。 3 ) 非冗余性( n o n r e d u n d a n c y ) ：染色体和潜在解必须一一对应。 按照遗传算法的模式定理，d ej o n g 进一步提出了较为客观明确的编码评估准 则，称之为编码原理口们。具体可以概括为两条规则： 1 )有意义建筑模块编码规则：编码应当易于生成与所求问题相关的短距和低 阶的建筑模块( b u i l d i n gb l o c k s ) 。 2 )最小字符集编码规则：编码应采用最小字符集以使问题得到自然、简单的 表示和描述。 总的说来，这些编码方法可以分为三大类：二进制编码方法、实数编码方法、 符号编码方法。下面对前两种编码进行介绍。 2 2 2 1 二进制编码 二进制编码应用范围非常广泛，是最基础的编码方式。二进制编码是将原问题 的解映射成为组成的位串，然后在位串空间上进行遗传操作。结果通过解码过程还 原成其解空间的解，再进行适应值的计算。二进制编码方法有如下优点n 0 1 ： 1 ) 编码、译码操作简单易行。 2 ) 交叉、变异等遗传操作便于实现。 1 0 华北电力大学硕士学位论文 3 ) 符合最小字符集编码原则。 4 ) 便于利用模式定理对算法进行理论分析。 二进制编码除以上优点外，当应用于遗传算法中时也存在一些缺点，如二进制 编码方法占用内存多、实现不灵活和译码运算量相对大的缺点，难以应用于求解较 大规模的多参数优化问题，也难以在较小内存的计算机上实现。 2 2 2 2 实数编码 为改进二进制编码在解决某些问题时存在搜索能力和种群多样性不够理想的 缺点，提出个体的实数编码方法。实数编码方法，是指个体的每个基因值用某一范 围内的一个实数来表示，个体的编码长度等于其决策变量的个数。实数编码使用决 策变量的真实值，也叫做真值编码方法，在执行上，遗传空间就是问题空间，染色 体的基因直接反映问题的规律和特性。 与二进制型遗传算法相比，其显著的特点在于个体表示形式的直接有效性和交 叉、变异操作方法的多样性，因此，具有以下优点口h3 幻： 1 ) 适合精度要求较高的遗传算法。 2 )适合在遗传算法中表示范围较大的数。 3 )便于大空间的遗传搜索。 4 ) 改善遗传算法的计算复杂性，提高运行效率。 5 )便于遗传算法与经典优化方法的混合使用。 6 )便于设计针对问题的专门知识的知识型遗传算子。 7 )便于处理复杂的决策变量约束条件。 2 2 3 适应度函数 遗传算法仅以适应度函数( f i t n e s sf u n c t i o n ) 为依据，利用种群中每个个体的适 应度值来进行搜索。一般而言，适应度函数是由目标函数变换而成的，它的选取直 接影响到遗传算法的收敛速度以及能否找到最优解。 2 2 3 1 常见的适应度函数 适应度函数( 评价函数) 基本上有以下三种： 1 ) 直接以待求解的目标函数g ( x ) 的转化为适应度函数f ( x ) ，即： 若目标函数为最大化问题，则 f ( x ) = g ( x ) ( 2 1 ) 1 1 华北电力大学硕十学位论文 若目标函数为最小化问题，则 f ( x ) = 一g ( x ) ( 2 - 2 ) 这个适应度函数简单直观，但存在两个问题，一是可能不满足常用的轮盘赌选择中 概率非负的要求；二是某些代求解的函数在函数值分布上相差很大，因此得到的平 均适应度可能不利于体现种群的评价性能，影响算法的性能。 2 ) 若目标函数为最小化问题，则 似) = 。譬嚣卜 ( 2 _ 3 ) 其中，c 0 为厂( 工) 的最大估计值。 若目标函数为最大化问题，则 m ) = g ( 功一篇p l 陋4 ， 其中，c , m 为厂( x ) 的最小估计值。 这种方法是对第一种方法的改进，可以称为“界限构造法，但有时存在界限 值预先估计困难、不可能精确的p - j 题。 3 ) 若目标函数为最小化问题，则 厂( x ) 2 了；：丽1 c o ，c + g ( 工) o ( 2 - 5 ) 若目标函数为最大化问题，则 厂( 工) 2 丁；：丽1 ，c o ，c g ( x ) o ( 2 - 6 ) 这种方法与第二种方法类似，c 为目标函数界限的保守估计值。 2 2 3 2 适应度函数的作用 适应度函数的设计是遗传算法设计的一个重要方面，设计不当可能在选择操作 时出现以下遗传算法的欺骗问题n 引： 华北电力人学硕士学位论文 1 ) 在遗传进化的初期，通常会产生一些超常个体，若按照比例选择法，这些 异常个体因竞争力太突出而控制了选择过程，影响算法的全局优化性能。 2 ) 在遗传进化的后期，即算法接近收敛时，由于种群中个体适应度差异较小 时，继续优化的潜能降低，可能获得某个局部最优解。 2 2 3 3 适应度函数的设计 适应度函数的设计主要满足以下条件d 1 ： 1 )单值、连续、非负、最大化条件：易理解和实现。 2 )合理、一致性：要求适应度值反映对应解的优劣程度，这个条件的达成往 往比较难以衡量。 3 )计算量小：适应度函数设计应尽可能简单，这样可以减少计算时间和空间 复杂度，降低计算成本。 4 )通用性强：适应度对某类具体问题，应尽可能通用，最好无需使用者改变 适应度函数中的参数。从目前而言，此条件应该是不属于强要求。 2 2 3 4 适应度函数的尺度变换 常用的尺度变换方法有以下几种n 9 1 ： 1 ) 线性变换法 假设原适应度函数为厂，变换后的适应度函数为厂，则线性变换可用下式表示： f 。= a f + ( 2 - 7 ) 上式中的系数确定方法有多种，但要满足以下条件： a ) 原适应度的平均值要等于定标后的适应度平均值，以保证适应度为平均值 的个体在下一代的期望复制数为l ，即 f o 喈= 厶 ( 2 - 8 ) b )变换后的适应度最大值应等于原适应度平均值的指定倍数，以控制适应度 最大的个体在下一代中的复制数，即： f 。哪= c f o 曙 ( 2 9 ) 其中，指定倍数c 可在1 0 2 0 范围内。对于群体规模大小为5 0 10 0 个个体的情况， 一般取c = 1 2 2 。此条件保证了群体中最好个体能期望复制c 倍到新一代群体中。 系数口、可按线性比例确定： 华北电力大学硕士学位论文 口：! 里二! 选( 2 1 0 )口= 2l z l u ) 厶。一z 喈 口：堕二竺五! 立( 2 11 ) l 一无嗜 线性变换法变换了适应度之间的差距，保持了种群内的多样性，并且计算简便，易 于实现。如果群体内某些个体适应度远远低于平均值时，有可能出现变换后适应度 值为负的情况，为此，考虑到保证最小适应度值非负的条件，进行如下变换： 口：塑l( 2 1 2 ) 喂一 血 = 麓 2 ) 幂函数变换法 幂函数变换时新的适应度是原适应度的某个指定乘幂。公式为： f = f ( 2 1 4 ) 其中，幂指数k 与所求解的问题有关，且在算法的执行过程中需要不断对其进行修 正才能使尺度变换满足一定的伸缩要求。 3 ) 指数变换法 变换公式为： f = p a f ( 2 - 1 5 ) 其中，系数口决定了选择的强制性，口越小，复制的强制就越趋向于那些具有最大 适应度的个体。此变换方法的基本思想来源于模拟退火过程。 2 2 4 遗传算子 基本遗传算法的操作算子一般包括选择、交叉和变异三种基本形式，它们构成 了遗传算法具备强大搜索能力的核心，是模拟自然选择以及遗传过程中发生的繁 殖、杂交和突变现象的主要载体。 遗传算法利用遗传算子产生新一代群体来实现群体进化，算子的设计是遗传策 略的主要组成部分，也是调整和控制进化过程的基本工具。 2 2 4 1 选择 1 4 华北电力大学硕士学位论文 选择即从当前种群中选择适应值高的个体以生产交配池的过程。选择过程的第 一步是计算适应度。在被选集中每个个体具有一个选择概率，这个选择概率取决于 种群中个体的适应度及其分布。主要有适应值比例选择、b o l t z m a n n 选择、排序选 择、锦标赛选择、精英选择策略。川等。 1 ) 适应值比例选择 适应值比例选择是最基本的选择方式，其中每个个体被选择的期望数量与其适 应值和群体平均适应值的比例有关，通常采用轮盘赌方式实现。这种方式首先计算 每个个体的适应值，然后计算出此适应值在群体适应值总和中所占的比例，表示该 个体在选择过程中被选中的概率。选择过程体现了生物进化过程中“适者生存，优 胜劣汰 的思想，并且保证优良基因遗传给下一代个体。本文采用轮盘赌的方式来 进行选择操作。 对于给定的规模为咒的群体p = 和。，口：，口。) ，个体吩p 的适应值为f ( a ，) ，其 选择概率为： 见( 口，) ：善生，j ：1 ，2 ， f ( a i ) 该式决定种群中个体的概率分布。经过选择操作生成用于繁殖的交配池， 种群中个体生存的期望数目为： p ( a t 7 ) = 甩。只( 哆) ，= 1 ，2 ，n ( 2 1 6 ) 其中父代 ( 2 1 7 ) 当种群中个体适应值的差异非常大时，最佳个体与最差个体被选择的概率之比 也将按指数增长。最佳个体在下一代的生存机会将显著增加，而最差个体的生存机 会将被剥夺。当前种群中的最佳个体将快速充满整个群体，导致群体的多样性迅速 降低，g a 也就过早地丧失了进化能力。这是适应值比例选择容易出现的问题。 2 )排序选择 排序选择方式是将群体中个体按其适应值大4 , 1 1 i 页序排成一个序列，然后将事先 设计好的序列概率分配给每个个体n 1 3 屯3 5 3 6 1 。排序选择与个体的适应值的绝对值无 直接关系，仅与个体间适应值相对大小有关。它不利用个体适应值绝对值的信息， 可以避免群体进化过程的适应值标度变换。排序选择概率比较容易控制，在实际计 算过程中经常采用，特别是适用于动态调整选择概率，根据进化效果适时改变群体 选择压力。 3 ) 联赛选择 华北电力大学硕士学位论文 联赛选择的基本思想是从当前群体中随机选择一定数量的个体，将其中适应值 最大的个体保存在下一代。反复执行该过程，直到下一代个体数量达到预定的群体 规模。联赛规模用q 表示，也称q 一联赛选择。联赛选择与个体的适应值有间接关系， 注重适应值大小的比较。根据大量实验总结，联赛规模