（电力系统及其自动化专业论文）混合优化算法及其在同步相量测量单元最优配置中的应用.pdf

a b s t r a c t w 池t h ee n l a r g e m e n to fp o w e rs y s t e ms c a l e ，i ti sm o l ea n dm o r ei m p o r t a n ta n d e x i g e n tt oa c c e s st on e t w o r k i n f o r m a t i o nt i m e l y t h ep h a s o rm e a s u r e m e n t su n i t ( p m u ) i sap o w e r f u lt o o li nl a r g ep o w e rs y s t e mm o n i t o r i n ga n dc o n t r 0 1 i ti sc a p a b l eo f m e a s u r i n gt h es y n c h r o n i z e dv o l t a g ea sw e l la sa l li n c i d e n tc u r r e n tp h a s o r sa tt h eb u s e s w h e r et h e s ea r el o c a t e di np o w e rs y s t e m s f o rr e c e n ty e a r s ，t h ea p p l i c a t i o nr e s e a r c ho f p m uh a sb e e nf u r t h e r i n gg r a d u a l l ya n dc o n t e n t si n c l u d et h ep r e c i s i o ni m p r o v e m e n t o fs t a t ee s t i m a t i o n ，t r a n s i e n ts t a b i l i t yc o n t r o la n dp l a c e m e n to fp m uf o rc o m p l e t e n e t w o r ko b s e r v a b i l i t y f o rs t a t ee s t i m a t i o n p u r p o s e ，d r a gp h a d k ee x p l o r e d t h ep o s s i b i l i t yo f p r o v i d i n ga l ls y s t e mn o d e sw i t hp m u s h o w e v e rt h er e l a t i v e l yh i 曲c o s tb o t ho n p m u sa n dt h e i rc o m m u n i c a t i o nf a c i l i t i e sp r e v e n t st h ea d o p t i o no fs u c has o l u t i o na t t h ep r e s e n tt i m e t h e r e f o r e ，i ti si m p o r t a n tt oi n v e s t i g a t ew h e r ea n dh o wm a n yp m u s s h o u l db ei m p l e m e n t e df i r s ti no r d e rt om a k en e t w o r ka c h i e v eo b s e r v a b l ew i t hl e a s t p m u s t h ep r o b l e mi sw h a tw ec a l l e do p t i m a lp m up l a c e m e n t ( o p p ) i nt h i s p a p e r , s e v e r a le m e r g i n gi n t e l l i g e n to p t i m i z a t i o nm e t h o d sa r ef u r t h e r a n a l y z e d ，b a s e do nt h ec u r r e n tr e s e a r c hs t a t u so fn e t w o r ko b s e r v a b i l i t yo ft h ep o w e r s y s t e m s oan e wh y b r i do p t i m i z a t i o nm e t h o dw h i c hi so r i g i n a t e df r o mp a r t i c l e s w a r mo p t i m i z a t i o n ( p s o ) a n ds i m u l a t e da n n e a l i n g ( s a ) i sd e s i g n e dt oo b t a i nb e t t e r p e r f o r m a n c eo nt h e o p ei nt h eh y b r i da l g o r i t h m , t h em e c h a n i s mo fs i m u l a t e d a n n e a l i n g ( s a ) i si n v o l v e di n t oo r i g i n a lp 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 ) t op r e v e n t t h em e t h o df r o mp r e m a t u r ec o n v e r g e n c e ；c r o s s o v e ra n dm u t a t i o no p e r a t o r sa r e a p p l i e dt o i n c r e a s et h ed i v e r s i t yo ft h es w a r m t h ep r o p o s e dm e t h o dk e e p st h e a d v a n t a g eo fp s o t of i n dt h eo p t i m u mr e s u l tq u i c k l y , a n di ss t i l ls i m p l et oi m p l e m e n t , a n dc a ni m p r o v et h ea b i l i t yo f j u m p i n go u to fl o c a lo p t i m u mr e s u l t s t od e a lw i t ht h ec o n s t r a i n t s ，a ni m p r o v e dh e u r i s t i cr e p a r a t i o ns t r a t e g yi s d e v e l o p e da n di tc a na v o i dg e n e r a t i n gt o om a n ys i m i l a rs o l u t i o n s i na d d i t i o n ，i nt h i s p a p e ras p e e d yn e t w o r ko b s e r v a b i l i t ya n a l y s i sm e t h o db a s e do nn o d a la d j a c e n tm a t r i x i sp u tf o r w a r d i td o e sn o tn e e dt oc o s tag r e a td e a lo fc a l c u l a t i o nt oj u d g et h e o b s e r v a b i l i t yo fn e t w o r kl i k ef o r m e rm e t h o d s t h ee f f i c i e n c yo fp r o g r a mi si m p r o v e d g r e a t l y t h es i m u l a t i o nr e s u l t so ns e v e r a lt y p i c a li e e et e s t i n ge x a m p l e ss h o wt h a tt h e h y b r i do p t i m i z a t i o nm e t h o di se f f e c t i v ea n de f f i c i e n ti nt h eo p e p h a s o rm e a s u r e m e n tu n i t ( p m u ) ，o p t i m a lp m up l a c e m e n t ( o p p ) ， o b s e r v a b i l i t ya n a l y s i s ，h y b r i do p t i m i z a t i o nm e t h o d 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得叁盗蓉鲎或其他教育机构的学位或证 书丽使用过的材料。与我一露工作的同志对本研究所做麓任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：主建蜩 签字啜期：叼年f 旁彩蜀 学位论文版权使用授权书 本学位论文作者完全了解墨逮盘堂有关保留、使用学位论文的规定。 特授权鑫鲞基茎一可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫攒等复制手段保存、汇编以供查阅和借麟。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：主耋扣片 导师签名： 签字只期：弘哆年? 月“日 天中 签字网期： 9 _ 7 年7 月爨 第一章绪论 第一章绪论 1 1 同步相量测量单元( p m u ) 综述 1 1 1p m u 的产生和发展 在过去的几十年里，世界上许多国家的区域互联电网都曾发生过大停电事故 【l 】，给社会生活和经济发展带来了巨大的冲击。随着全球电力市场化浪潮的兴 起，电网运行的条件和环境日益复杂，电网安全稳定问题日渐突出。这也导致近 年来全世界大停电事故的发生频率和严重程度都有加重的趋势。为了应对电力市 场化给电网运行带来的严峻考验，电力系统迫切需要有新的技术手段来加强电网 的动态安全监控能力，提高电网安全稳定水平。近年来，基于同步相量测量技术 的广域测量系统在电力系统中的应用日渐增纠2 4 1 ，为上述问题的解决提供了新 的技术手段。广域测量系统中的相量测量单元( p h 勰o rm e a s u r e m e n tu n i t ，简称 p m u ) 利用g p s 系统的高精度授时信号，能实现对电力系统各个节点动态数据的 同步采集。其在电力系统中的广泛应用不仅为解决电网安全稳定问题，提高电网 动态安全水平和防止大停电事故提供了新的技术途径；同时p 刖装置采集的同 步数据也为电力系统在线应用领域中的分析、控制功能的研究开发提供了新的数 据源。同步相量测量技术及在此基础之上的广域测量系统已成为电力系统中一个 非常活跃的研究领域。 相角对于电力系统具有重要意义，因此，世界上许多国家的电力公司构和高 校投入了大量的人力和物力，开发、研制相量测量装置( p m u ) 在稳态稳定预测、 控制和自适应失步保护中的应用。 早期的相角测量方法是将交流电压波形送到控制中心进行比较显示，不确定 的延时，造成这种方法的测量精度太低。1 9 8 0 年，加拿大人g m i s s o u t 首次采用 无线电导航定位系统作为同步时钟进行相角测量；1 9 8 1 年又采用卫星系统g o e s ( g e o s t a t i o n a r yo p e r a t i o n a le n v i r o n m e n ts a t e l l i t e s ) 提供的时间作为同步时钟。1 9 8 1 年，瑞士人r b o n a n o m i 采用无线电广播授时，其时间作为同步时钟信号进行相 角测量，并首次展望了相角的应用前景。1 9 8 3 年，美国人a gp h a d k e 采用无线 电广播授时的时间作为同步时钟，提出了用递推的离散傅立叶变换( d f t ) 求解电 压相角的方法；由于同步时钟精度低，后采用冗余的办法来提高测量的精度。 电力系统实时相角测量长期未能实现的根本原因在于电力系统地域辽阔。采 第一章绪论 用常规的方法和技术难以实现。电磁波虽是以光速3 0 万千米秒传播，但是对工 频信号( 5 0 h z ) 而言，每传播1 0 0 千米相角就滞后6 。，采用直接将交流信号传送 的办法，误差太大。采用同步时钟进行相角测量时，对于5 0 h z 的工频信号来讲 l m s 的同步时钟误差将会带来1 8 。的相位偏差。过去由于时钟精度低，再加上 通讯技术和计算机技术水平的限制，阻碍了这个问题的解决。美国的全球定位系 统g p s ( g l o b a lp o s i t i o ns y s t e m ) 出现，为相角测量提供了时钟精度上的保证。 美国是从6 0 年代开始进行空中定位研究，1 9 7 4 年基于g p s 概念的全球定位 系统开始正式研制，又叫做导航卫星测时和测距，分为民用和军用。1 9 8 5 年进 入民用领域，1 9 9 3 年次系统正式建成。由于其采用了扩频和伪码技术，抗干扰 能力极强，可靠性高，容易使用。对于5 0 h z 的工频信号来说其相位的同步误差 不超过0 0 1 8 。因此，现有相角测量装置都选g p s 作为同步时钟。1 9 9 0 年，a g p h a d k e 研制了基于g p s 时钟的同步相角测量装置，并将其应用于b p a 的两个变 电站之间的连线上。1 9 9 0 年，法国也研制了基于g p s 时钟的同步相角测量装置， 并将测量电压相量和基于电压相量的控制作为法国电网防止崩溃的措施。 1 1 2p m u 的功能 近年来基于g p s 技术的同步相量测量装置p m u 在国内外电力系统中已经开 始应用。 ( 1 ) 基于相量测量的电力系统状态估计确定。 电力系统的状态相量反映了系统运行的行为及状态，同时掌握电网各节点之 间的电压、电流和相位关系，可帮助调度人员进行合理的发电量及负荷调度，以 便采取有针对性、切实可行的稳定措施。传统的状态估计是根据各个厂站的遥测 量以及当前运行电网的拓扑结构，利用非线性迭代法求得电力系统的状态量( 主 要是母线电压相量) 。此法存在计算时间长、实时性差，在某些情况下迭代不易 收敛或不收敛，遥测值的非同步等缺点，给状态估计带来较大的误差。借助于同 步相量测量，可以得到电网上各点的正序电压和电流，从而实现各分站的电压电 流同时测量，无需估计状态矢量，只要用一个常规矩阵乘以测量矢量即得到一个 估计结果，是线性估计：这种确定电力系统状态的优点是：实时性强、在现代通 讯技术的支持下，可在2 - 5 h z 更新一次状态；对于频率为0 2 h z 的系统动态现象 ( 如低频振荡) ，调度中心可以实时观察到，为调度员正确决策提供依据。 ( 2 ) 基于同步相量测量技术的潮流计算1 5 】 同步相量测量单元( p m u ) 能够提供电力系统节点电压相量的直接测量，从而 改变了潮流计算的条件。对于不同的测量精度和不同的配置，可以采用不同的方 式将p m u 的测量结果应用于潮流计算。 2 第一章绪论 ( 3 ) 基于相量测量的暂态稳定性预测和控制【6 】 系统的设计、运行保护都直接或间接受到系统不稳定因数的影响，所以确定 系统的不稳定条件、控制不稳定因数对现代电网十分有利。传统的稳定性分析方 法是对系统动态方程直接积分。由于状态矩阵维数多、运算量大，故只能采用简 化模型进行离线计算，很难做到实时的稳定分析。引入同步相角测量p m u 可以 提高保护和控制系统能够对功率振荡的反应，提高对暂态振荡预测的能力。可以 监测实时暂态情况，跟踪一个数据窗内的状态变量和它们的求导量，应用合理的 简化模型计算未来一段时间内的振荡结果，基本可以预测未来几秒内的系统状 态。利用基于g p s 同步时钟的相量测量单元来测量系统在暂态过程中各节点电 压相位、各发电机转子角度、转速，从而预测系统未来的摆动情况。当预测到系 统将失去暂态稳定时，按预定的方案对系统进行解列控制或作出切机控制决策， 以保持系统暂态稳态性，防止系统崩溃和瓦解。 ( 4 ) 基于相量测量的输电线路故障定位【7 】 对于高压输电线路故障的快速、准确、可靠定位，国内外进行了广泛深入的 研究，己形成单端、多端、阻抗行波解析等各种定位方法。基于g p s 同步时钟 的输电线路故障定位利用故障时测量电流、电压相量对故障进行分析计算实时求 出测量点到故障点的距离。 ( 5 ) 基于相量测量的自适应失步保护【8 】 当电力系统同步运行破坏而发生失步振荡时，基于相量测量可使保护和控制 系统的反应速度更快，并能实时预测系统振荡的性质。随着大电网的出现，失步 的因素众多，失步保护的整定值越来越困难，而电压相量是含有较多信息的反映 系统状态的输入量，这些输入量能够较全面地反映系统的状态，并经分析之后才 能正确决定系统的解列与否。自适应失步保护就是依据这一原理开发的，它能根 据各p m u 送来的值及电网结构的变化，自行调整定值和动作方程，以满足新工 况下的系统安全稳定的要求。这种基于相量测量的自适应失步保护在国外已进入 实用阶段，根据我国电力系统快速发展的国情，相量测量技术的应用是大有可为 的。 ( 6 ) 实时相角集中监控系统【9 】 相角是反映系统稳定性最直接的状态变量，建立全系统的实时相角集中监视 系统，并结合其他状态量，给调度员提供预防故障的措施或减少事故影响的补救 办法，根据相角信息可采取紧急措施( 如切机、甩负荷、解列等) ，防止系统的崩 溃。 ( 7 ) 动态录波 相角测量系统是通过通信网把相角测量装置连在一起，若系统受到扰动时 第一章绪论 ( 如低频振荡或故障冲击等) ，一台相角测量装置的录波启动，会通过通信网使整 个系统的相角测量装置启动录波，其录波数据对分析系统在故障过程中的动态行 为非常有意义。 ( 8 ) 灵活输电系统( f a c t s ) 灵活输电系统的快速动作能加强电力系统的暂态稳定，而将相角测量装置的 实时相角送到f a c t s 中，可简化其控制算法，使其得到更加灵活的控制。 ( 9 ) 阻尼控制 要抑制低频振荡，保持系统的动态稳定，首先必须对低频振荡的模式等有深 入的了解。传统的经典低频振荡分析方法是特征值分析法，只能适用于离线分析。 而电力系统的振荡模式总是随着运行条件的改变而变化，离线获得的结果并不能 保证在线计算的精确性。文献【l o 】基于p m u 的广域量测数据进行了低频振荡模 式及其在线识别方法的研究。文献 1 0 】讨论了机电振荡模式的在线评估，利用 p m u 采集的系统动态数据来识别系统正常运行时的振荡主频率和阻尼。文献【1 1 】 提出了基于广域测量的低频振荡在线动态跟踪的改进p r o n y 算法，用样本矩阵奇 异值分布的特征来识别降阶信号模式。所提方法在原始信号中有大量噪声的情况 下，仍表现出了较好的性能。 ( 1 0 ) e g 压稳定 传统的保持电压稳定的方法如低压减载和基于单一母线上电网戴维南等效 评估方法等的共同特点在于其分析数据都是本地静态量测值。而近年发展起来的 基于p m u 直接量测值的电压稳定分析方法与这些传统的方法相比，由于其使用 了基于p m u 量测的广域动态数据，因而有着明显的优越性，具体体现在以下两 点：( 1 ) p m u 直接量测值的更新频率远快于传统的本地静态数据，这样就消除 了传统方法中固有的延时问题；( 2 ) 直接使用p m u 量测值进行分析，可以避免在 使用经过状态估计得到的数据时，可能存在的误差重叠带来的数值不精确问题。 同步相量监测技术在电力系统中还有很多其它方面的的应用前景。如同步相 量测量技术还可以在输电线的差动保护，发电机自适应低频减载，负荷建模及负 荷特性分析，中长期动态过程分析等领域发挥其特有的重要的作用。可以说， g p s 技术和相量测量技术的结合标志着电力系统动态安全监测和实时控制时代 的来临，这将使电力系统的运行监测与控制及电力系统的安全稳定水平提高到一 个前所未有的新高度。 研究电力系统同步相量测量的原理和方法具有重要意义。同步相量测量涉及 到电力系统的监视、控制和保护等诸多领域，将推动电力系统控制和保护利用同 步相量测量实现新方法和新原理。同步相量测量系统使调度中心的e m s 功能从 稳态向动态转变，给大电力系统的全局稳定和恢复控制开辟了一条新的研究方 4 第一章绪论 向。 1 2p m u 最优配置综述 随着电网互联程度的不断提高和电网结构日益复杂，提高电力系统的安全稳 定性显得更加重要。在这种情况下，及时获取电网信息，并对系统动态行为进行 实时监控变得更为迫切。过去，由于电网规模大、结构复杂，以及技术水平等因 素的制约，获取电网的实时信息非常困难。直到g l o b a lp o s i t i o n i n gs y s t e m ( g p s ) 技术广泛应用和现代通信技术迅速发展后，才使得广域同步实时测量成为可能。 基于g p s 时钟同步技术的同步相量测量装置既可以广域同步测量母线电压相量 和线路电流相量，还可以测量发电机的转速与功角【1 2 1 。只要将p m u 分别安装于 不同地点，并将其测量的信息通过通信网络，实时送到调度中心，运行人员就能 够实时监视到整个系统的静态、动态运行状况，并可以利用这些实时信息实现闭 环稳定控制l l 引。 根据p h a d k e 的建议，在所有的变电站都安装p m u ，可以大大改善电力系统 的监控水平【1 4 】。但由于目前p m u 价格昂贵，这样做会增加一次性投资，所以分 阶段安装p m u 比较现实。首先选择一些地点安装一定数量的p m u ，达到全系 统电压矢量可观的目的，然后待经济条件允许时，再逐步增加安装地点，以提高 测量冗余度。p m u 的安装地点选择涉及到组合优化的问题，可归纳为：在保证 系统可观的前提下，通过优化p m u 的安装地点，使p m u 的安装数量最少。 文献【1 6 】在遗传算法优化过程中引入了进化参数衰减因子，构造出一种新的 自适应遗传算法，该算法能够同时根据个体适应度和进化时间的变化自动调整交 叉与变异概率，从而提高了算法的全局收敛性，克服了算法早熟，保持了解的多 样性，加快了寻优速度。 文献 1 6 采用改进的粒子群算法( e p s o ) 进行求解。提出了在闭合解空间中引 入降维的方法，以构造一种改进的粒子群算法。通过不断降低粒子所在空间的维 数即p m u 的数量，寻找出不同维数空间中的最优粒子，最终实现了p m u 数量 增加过程中的最优配置。 在以系统状态完全可观测为目标的p m u 配置研究方面， 文献 1 7 】提出了 对半搜索和模拟退火( s i m u l a t e da n n e a l i n g ，s a ) 法相结合的p m u 最优配置方 法，可以保证得到最优解，但由于此方法的计算量过大，影响了其在较大规模系 统中的应用。文献【l8 】提出了一种非支配分类遗传算法来寻找p m u 最优配置问 题的一组p a r e t o 最优解，该文首次将配置过程分为预处理阶段和动态配置阶段， 缩小了搜索空间。文献 1 9 】发展了基于增广关联矩阵的可观测性拓扑分析方法， 第一章绪论 并应用禁忌搜索方法求解p m u 最优配置问题。以上3 种方法均采用启发式算 法的计算结果作为计算初值，其共同的缺点是启发式配置原则过于简单，计算结 果较差。 k i s e o nc h o 分别采用改进的模拟退火法、直接组合法( d i r e c tc o m b i n a t i o n ) 和禁忌搜索法( t a b us e a r c h ) 硼：究此问剧2 0 】。由于改进的模拟退火法只是针对不 同的解集合对算法的初始温度及冷却过程等方面进行了改进，在本质上并没有摆 脱模拟退火法收敛慢的弱点。直接组合法可大大减小搜索空间，从而避免了模拟 退火法的计算时间长的问题，但需要根据不同的问题制定相应的启发性规则。禁 忌搜索法通过在算法中定义一个禁忌列表来记录历史搜索结果，来保证不发生重 复搜索，以减小搜索空间，加快搜索速度。但该算法对初始解有较强的依赖性， 而且禁忌列表的长度对算法性能有显著影响。若列表长度过短，会造成重复搜索， 从而导致算法收敛太慢。若列表长度过长，会造成算法早熟。 1 3 本文所做的工作 如前所述，以系统完全可观测为目标的p m u 最优配置问题是非常复杂的一 个大规模、非线性、带约束的组合优化问题。本文在以往系统可观测性分析和现 代优化算法研究的基础上，根据p m u 最优配置问题的特点，设计了一种新的混 合优化算法较好地解决这一问题。 本论文的主要工作包括如下几个方面： ( 1 ) 阅读大量的中外文献，加以比较和分析，得出自己对粒子群算法( p s o ) 模拟退火算法( s a ) 和遗传算法( g a ) 的理解，并分析了各自的优点缺点，为 设计新的混合算法奠定了基础。 ( 2 ) 深入研究了以p m u 量测量为基础的系统可观测性分析，实现了对系统可观 测性的快速准确判断，解决了影响处理这一问题的关键环节。 ( 3 ) 设计了一种新的混合优化算法，以粒子群算法为主体，同时引入交叉、变 异操作，模拟退火机制被引入算法中以控制粒子的更新，从而避免了粒子群优化 算法易陷入局部极值点的缺点。另外，在处理解的约束问题时，采用了一种基于 概率的启发式修补策略，避免修复后的解局部特征过于单一。 6 第二章现代优化计算方法介绍 第二章现代优化计算方法介绍 现代优化算法包括遗传算法( g e n e t i ca l g o r i t h m s ) 、模拟退火( s i m u l a t e d a n n e a l i n g ) 、禁忌搜索( t a b us e a r c h ) 神经网络( n e u r a ln e t w o r k s ) 以及粒子群算 法( p a r t i c l es w a r mo p t i m i z a t i o n ) 等算法。这些算法涉及生物进化、人工智能、 数学和物理科学、神经系统等概念，都是以一定的直观基础而构造的算法。当人 们不满足常规算法求解复杂问题时，现代优化算法开始体现其作用。现代优化算 法自2 0 世纪8 0 年代初兴起，至今发展迅速。 2 1 遗传算法 2 1 1 遗传算法的基本理论 近年来，随着人工智能应用领域的不断扩大，传统的基于符号处理机制的人 工智能算法在知识表示、信息处理和解决组合爆炸等方面遇到的困难越来越明 显，于是人们开始致力于研究一些能够处理当前难题的新型算法。1 9 7 5 年h o l l a n d 受生物进化论的启发出版了他的第一本关于遗传算法( g e n e t i ca l g o r i t h m s ，简称 g a ) 的专著，同年d ej o n g 的博士论文a na n a l y s i so f b e h a v i o ro f ac l a s so f g e n e f i c a d a p t i v es y s t e m 发表，它们一起被公认为是遗传算法的基础。g a 是基于“适者 生存的一种高度并行、随机和自适应的优化算法，它将问题的求解表示成“染 色体”的适者生存过程，通过“染色体”群的一代代不断进化，包括复制、交叉 和变异等操作，最终收敛到“最适应环境”的个体，从而求得问题的最优解或满 意解。目前，随着计算机技术的发展，g a 越来越得到人们的重视，并在机器学 习、模式识别、图像处理、神经网络、优化控制、组合优化等领域得到了广泛的 应用。 1 遗传算法的一般结构 遗传算法从一组随机产生的初始解( 称为“种群”) 开始搜索过程。种群中 的每个个体是问题的一个解，称为“染色体( c h r o m o s o m e ) ”。染色体是一串符号， 比如一个二进制字串。这些染色体在后续迭代中不断进化，称为遗传。在每一代 中用“适应值( f i m 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 ) 运算形 成的。新一代形成中，根据适应值的大小选择部分后代，淘汰部分后代，从而保 7 第二章现代优化计算方法介绍 持种群大小是常数。适应值高的染色体被选取中的概率较高。这样，经过若干代 之后，算法收敛于最好的染色体，它很可能就是问题的最优解或次优解重组包 括杂交和变异来获得后代实际上，遗传算法中有两类运算，遗传运算：杂交 和变异；进化运算：选择。 遗传运算模拟了基因在每一代中创造新后代的繁殖过程，进化运算则是种群 逐代更新的过程。以上描述和h o l l a n d 的原始描述有些不同，原始描述是选择双 亲来进行重组。杂交是最主要的遗传运算，它同时对两个染色体操作，组合二者 的特性产生新的后代。杂交的最简单方法是在双亲( 两个父辈的个体) 的染色体上 随机地选一个断点，将断点的右段互相交换，从而形成两个新的后代。这种方法 对于二进制表示最为合适。遗传算法的性能在很大程度上取决于采用的杂交运算 的性能。 杂交率( 记为p c ) 定义为各代中交叉产生的后代数与种群中的个体数( 通常记 为p o p 的比。它将参加杂交运算的染色体个数的期望值控制为 。s i z e ) p c * p o p s i z e 较高的杂交率可达到更大的空间，从而降低停在非最优解上的机会；但是这个比 率太高，会因搜索不必要的空间而耗费大量的计算时间。变异则是一种基本运算， 它在染色体上自发地产生随机的变化。一种简单的变异方法是替换一个或多个基 因。在遗传算法中，变异可以提供初始种群中不含有的基因，或找回选择过程中 丢失的基因，为种群提供新的内容。 变异率( 记为v m ) 为种群中变异基因数在总基因数中的百分比。变异率控制 了新基因导入种群的比例。若变异率太低，一些有用的基因就不能进入选择：若 太高，即随机的变化太多，那么后代就可能失去从双亲继承下来的好特性，这样 算法就会失去从过去的搜索中学习的能力。 遗传算法在几个基本方面不同于传统优化方法。g o i d b e r g 总结如下几点 ( 1 ) 遗传算法运算的是解集的编码，而不是解集本身。 ( 2 ) 遗传算法的嵌于解的一个种群，而不是单个解。 ( 3 ) 遗传算法只使用报酬信息( 适应值函数) ，而不使用导数或其他辅助知识。 ( 4 ) 遗传算法采用概率的，而不是确定的状态转移规则。 2 设计遗传算法的基本原则 在设计遗传算法时，通常要考虑到以下的一些原则： 1 ) 适用性原! i l t j 一个算法地适用性，是指该算法所能适用的问题种类，它取决于 算法所需的限制与假定。如优化问题的约束不同，则相应的处理方式也不同。 2 ) 可靠性原则：一个算法的可靠性，是指算法对所设计的问题，以适当的精度求 解大多数问题的能力，即对大多数问题能提供可靠的解。 3 ) 收敛性原则：遗传算法的收敛性通常指能否以概率收敛到全局最优解。在收敛 第二章现代优化计算方法介绍 的前提下，我们当然希望算法具有较高的收敛速度。 4 ) 稳定性原则：遗传算法的稳定性是指算法对其控制参数及问题数据的敏感度。 如果算法对其控制参数或问题的数据十分敏感，则依据它们取值的不同，将可能 产生不同的结果，甚至过早地收敛到某一局部最优解。这当然不是我们所希望的。 5 ) 生物类比性：因为遗传算法的设计思想是基于生物演化过程的，那些在生物界 被认为是行之有效的方法及操作可以通过类比的方法引入到算法之中，有时会带 来好的结果。 3 设计遗传算法的基本步骤 在设计遗传算法时，通常按以下的基本步骤进行： 1 ) 确定编码方案：遗传算法求解问题不是直接作用在问题的解空间上，而是利用 解的某种编码表示。选择何种编码表示有时将对算法的性能、效率等产生很大的 影响。 2 ) 确定适应函数：适应值是对解的质量的一种度量，它通常依赖于解的行为与环 境( 即种群) 的关系。一般以目标函数或费用函数的形式来表示。解的适应值是演 化过程中进行选择的唯一依据。 3 ) 选择策略的确定：优胜劣汰的选择机制使得适应值大的解有较高的存活概率， 这是遗传算法与一般搜索算法的主要区别之一。不同的选择策略对算法的性能也 有较大的影响。 4 ) 控制参数的选取：控制参数主要包括种群的规模、算法执行的最大代数、执行 不同遗传操作的概率以及一些辅助性的控制参数。 5 ) 遗传算子的设计：遗传算法中的遗传算子，主要包括繁殖( r e p r o d u c t i o n ) 、杂交 ( c r o s s o v e r ) 、变异( m u t a t i o n ) 以及其它高级操作。 6 ) 确定算法的终止准则：由于遗传算法没有利用目标函数的梯度等信息，所以在 演化过程中，无法确定个体在解空间的位置，从而无法用传统的方法来判定算法 的收敛与否以终止算法。常用的办法是预先规定一个最大的演化代数或算法在连 续多少代以后解的适应值没有什么明显的改进时，即终止。 7 ) 编程上机运行：完成上述工作以后，即可以按照演化计算的算法结构编程来进 行问题求解。由于遗传算法的随机性和不确定性等特点，通常要多运行几次才能 得到可靠的解。应该注意上述各基本步骤是密切相关的，编码方案与遗传算子的 设计等是同步考虑的，有时甚至需要上机运行与算法设计交替进行。 4 编码表示 设计遗传算法的一个重要步骤是对所解问题的变量进行编码表示，编码表示 方案的选取很大程度上依赖于问题的性质及遗传算子的设计。下面是遗传算法中 常使用的编码表示方案： 9 第二章现代优化计算方法介绍 二进制编码 二进制编码( b i n a r ye n c o d i n g ) 即是将原问题的解空间映射到位串空间b = o ，1 ) 上，然后在位串空间上进行遗传操作，结果再通过解码过程还原成其表现 型以进行适应值的评估。很多数值和非数值问题都可以用二进制编码以应用遗传 算法。 采用二迸制编码有如下优点： ( 1 ) z 进制编码类似于生物染色体的组成，从而算法易于用生物遗传理论来 解释并使得遗传操作如杂交、变异等很容易实现。 ( 2 ) 可以证明采用二进制编码时，算法处理的模式数最多目前二进制编码是 遗传算法采用最多的一种方法。 实数编码 为了克服二进制编码的缺点，对于问题的变量是实向量的情形，可以直接采 用实进制进行编码。这样，便可直接在解的表现型上进行遗传操作，从而便于引 入与问题领域相关的启发式信息以增加遗传算法的搜索能力。 对实数编码的情形，从理论上讲，二进制编码下的各种遗传操作同样可以使 用，因为在机器中实数也采用二进制表示的。但实际应用时却很少使用这些基于 内部点操作的算子，而是针对实进制编码的特性引入其它一些遗传算子。试验 证明，对于大部分数值优化问题，通过一些专门设计的遗传算子的引入，采用实 数编码比采用二进制编码时算法的平均效率高。 结构式编码 对很多问题其更自然的表示是树或图的形式。这时采用其它形式的编码可能 是很困难的。这种将问题的解表示成树或图的形式的编码称为结构式编码。对于 这样的问题我们需要非常谨慎地设计遗传算子以使得不产生或少产生非法的后 代，对结构式编码要讨论其通用的遗传算子是很困难的，一般是具体问题具体分 析，因为遗传算子是直接在解的表现型上进行操作，这样使得我们比较容易加入 与领域有关的知识后得到一些启发式信息。 5 适应性的度量 自然界中，个体的适应值即为它繁殖的能力，它将直接关系到其后代的数量。 在演化计算中，适应函数是用来区分群体中个体好坏的标准，是算法演化过程的 驱动力，是进行自然选择的唯一依据。改变种群内部结构的操作皆以通过适应值 加以控制。 演化计算中度量适应性的方法有很多种。可以用目标函数的形式给出，也可 用目标函数变换的方式来定义。在协同演化( c o e v o l u t i o n ) 时，适应值则通常由某 一对策与群体中相佐的对策进行抗衡的获利来确定。个体在种群中的存活量和繁 l o 第二章现代优化计算方法介绍 殖量也可以作为适应值的一种量度，这各量度方式常在人工生命的研究中使用。 我们设计演化算法中经常用到的两种适应性度量。 原始适应函数 原始适应函数是问题求解目标的直接表示，通常采用问题的目标函数作为个 体的适应性下面度量。如在求解极值问题时，即为问题的原始适应函数。而对于 很多非数值优化问题，我们也可以将其转化为求某个目标函数的极值问题如设 计和训练神经网络时，我们可将网络的实际输出与期望输出之差的平方和，作为 问题的目标函数，则原问题成为寻找一个网络使目标函数达到最小。 对于一个问题，定义原始适应函数的方法可能不止一种，选择要尽量反映问 题本身整体的特性，而不能只追求片面的目标，这一点对用演化计算求解非数值 问题时，成为重要，而且往往也是比较困难的。 标准适应函数 因为原始适应函数反映问题的最初求解目标。因此会出现两种情形，一是极 小情形即原始适应值越小个体性能越好；另一种是极大化情形即原始适应值越大 个体性能越好。但是演化计算中的某些选择策略衬如基于适应值比例的选择策略) 则要求适应函数是非负的，而且适应值越大表明个体的性能越好。这是常常需要 原始适应函数作为一个适当的变换以转化成标准的度量方式，即皆化为极大化情 形，并且适应值非负。 6 选择策略 选择策略对算法性能的影响会起到举足轻重的作用。不同的选择策略将导致 不同的选择压力，即下一代中父代个体的复制数目的不同分配关系。较大的选择 压力使最优个体具有较高的复制数目，从而使得算法收敛速度较快，但也较容易 出现过早收敛现象。相对而言，较小的选择压力一般能使群体保持足够的多样性， 从而增大了算法收敛到全局最优的概率，但算法的收敛速度一般较慢。 下面是遗传算法中较常用到的几种选择策略。 1 ) 转盘式选择( r o u l e t t ew h e e ls e l e c t i o n ) 这种选择策略在遗传算法中使用的最多，它是先计算个体的相对适应值记为 ， 上l ，记为仍，然后根据选择概率 只，i = l ，2 ，n ) ，把一个圆盘分成n 份， 石 其中第i 扇形的中心角为2 万n 。在进行选择时，可以假想转动一下圆盘，若某参 照点落入到第i 个扇形内，则选择个体i 这种选择策略可以如下实现：先生成一 个【o ，t 】内的随机数r 。若风+ a + + 陬l r 表示解空间到实数的映射，t 为模拟退火算法( s a ) 过程中温度的控制参数，假定l ( s ，f ) 存在邻域以及相应解的 产生机制，坟i ) ，f 0 ) 分别为对应于解i ，j 的目标函数值。由解i 过渡到解j 的接受概率 用以下的m e t r o p o l i s 准则确定( 式2 1 ) ： i l ，厂( f ) f u ) 尸( ) = 尸( 7 专) 2 1 e x p 4 譬鸥，厂( f ) 舢) ( 2 - 1 ) 【 2 2 5 温度参数的控制 温度参数是模拟退火算法中最关键的参数之一。主要包括起始温度的选取、 温度的下降方法和停止温度的确定等。 1 起始温度的选取 根据文献 2 2 】，在实际计算中，起始温度一般采用一个估计值为t o = k 8 ，k 为充分大的数。其中，万= m a x f ( j ) j d - m i n f ( j ) l j d ) 。实际计算中，可 以选k = 1 0 ，2 0 ，1 0 0 等试验值。 2 温度下降方法 实际中可以采用的温度下降方法包括： ( 1 ) t k + 。= 叱，七o ，其中0 1 0 ，则s g 函数将趋近于0 。因此，文献【3 3 】中取为6 0 ，此时s g 的函数范围为 0 0 0 2 5 - - 0 9 9 7 5 ，这表明随着，( f ) 的增加，s g 函数将逐渐减少，但最低将达到 0 0 0 2 5 ，从而保证算法仍能够有能力发生变化。而文献【3 4 】中1 】k 则为4 ，此时 s g 函数的范围为0 0 1 8 - 0 9 8 2 ，从而使得算法能以较大的概率发生变化。 第三章改进的粒子群算法 第三章改进的粒子群算法 在p s o 算法不断应用的过程中，认识到粒子群算法在函数优化等领域所蕴含 的广阔应用前景，在e b e r h a r t 和k e n n e d y 之后很多学者都进行了这方面的研究。 目前，在标准p s o 算法的基础上，己经出现了各种有意义的改进p s o 算法， 例如自适应p s o 算法、协同p s o 算法、混合p s o 算法等等，下面介绍几种改进的 粒子群算法。 3 1s u p e r v i s o r - s