（计算机应用技术专业论文）进化算法研究及其在电力无功优化中的应用.pdf

摘要 在工程实践和科学研究中存在大量优化问题，而这些问题大多是带有约束条 件，且有时优化目标不止一个。由于问题自身的复杂性，传统的优化方法已经难 以独立解决。进化算法作为一种基于群体搜索的全局优化算法，十分适合于求解 约束优化问题和多目标优化问题。因此，进化优化研究受到国内外研究者们越来 越多的关注，成为目前进化计算领域研究的热点。 本文旨在通过对进化算法进行深入研究和探索，面向带约束的多目标优化问 题设计高效的进化算法。研究算法的同时注重算法的应用，将进化策略算法应用 于电力系统无功优化，并通过实验进行分析。具体而言，本文的工作主要有以下 两个方面： ( 1 ) 进化计算在求解带约束优化问题时，首要问题是对约束的处理。在对现 有主要的适于多目标优化问题的约束处理方法进行比较分析的基础上，结合不可 行个体修正和保留策略的优点，采用随机选择( 修正、保留) 和折半查找方法， 提出了一种基于随机折半修正策略的约束处理方法，并选取7 个标准测试函数进 行实验。实验结果和分析表明，与d e b 等提出的求解多目标约束优化问题的约束 支配方法相比，该算法在保持同等最优解集( 逼近性和分布性) 的情况下，优化 效率提高了3 0 。 ( 2 ) 在数学上，电力系统无功优化是典型的非线性规划问题，具有非线性、不 连续、不确定因素较多等特点。为了更好地解决此问题，将带排序策略的进化策 略应用于电力系统无功优化，并在编码方法，进化终止判据方面作了改进，从而 有效的提高了无功优化求解效率，并选取i e e e 1 4 和i e e e 11 8 节点系统进行实 验。实验结果和分析表明，与i e e e 1 4 和i e e e 1 1 8 节点系统初始网损相比，该 算法获得的网损值分别降低了4 4 3 和4 3 。 本文通过对进化约束优化算法研究，设计了基于折半修正策略的多目标约束 优化算法；同时将带随机排序策略的进化策略应用于电力系统无功优化。这些工 作对进化优化的研究有着重要的理论价值和实用价值。 关键词：进化算法，约束多目标优化，进化策略，电力无功优化 a b s t r ac t i ti sc o m m o nt of a c eal o to fo p t i m i z a t i o np r o b l e m si nt h er e a lw o r l d u s u a l l y ， t h e s ep r o b l e m sa r eo f t e nc o n s t r a i n e d ，a n dt h en u m b e ro fo p t i m i z i n go b j e c t i v ei sm o r e t h a no n e d u et oi t s c o m p l e x i t y ，m a n yt r a d i t i o n a lm e t h o d sa r eh a r dt os o l v et h e s e p r o b l e m si n d e p e n d e n t l y a sr o b u s te v o l u t i o n a r ya l g o r i t h m sb a s e do np o p u l a t i o na r e v e r yp r o m i s i n g t os o l v et h ec 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 t h e r e f o r e ，t h e r e s e a r c ho ne v o l u t i o n a r yo p t i m i z a t i o nh a sr e c e i v e dm o r ea n dm o r ea t t e n t i o n si n s o l v i n go p t i m i z a t i o np r o b l e m s o nt h eo n eh a n d ，t h ea i mo ft h i sd i s s e r t a t i o ni st oe x p l o r et h et h e o r i e sa n d m e c h a n i s m so fe v o l u t i o n a r ya l g o r i t h m sa n dt o d e s i g ne f f e c t i v ea l g o r i t h m sa n d s t r a t e g i e s f o rm u k i o b j e c t i v ec o n s t r a i n e do p t i m i z a t i o n o nt h eo t h e rh a n dt h e e v o l u t i o n a r ys t r a t e g ya l g o r i t h mi sa p p l i e dt ot h er e a c t i v ep o w e ro p t i m i z a t i o np r o b l e m t h ed e t a i l e dm a i nw o r k sa r ed e s c r i b e di nt h ef o l l o w i n g ： ( 1 ) d u r i n gs o l v i n gt h ec o n s t r a i n e dm 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 sw i t h e v o l u t i o n a r ya l g o r i t h m s ，c o n s t r a i n th a n d l i n gi sap r i n c i p a lp r o b l e m a n a l y z i n gt h e e x i s t i n gc o n s t r a i n th a n d l i n gm e t h o d s ，an o v e lc o n s t r a i n th a n d l i n gs t r a t e g yb a s e do n i n f e a s i b l ei n d i v i d u a ls t o c h a s t i cb i n a r y - m o d i f i c a t i o ni sp r o p o s e di nt h ed i s s e r t a t i o n i t s k e yp o i n tl i e si nm o d i f y i n gr a n d o m l yi n f e a s i b l ei n d i v i d u a li n t of e a s i b l eo n ea c c o r d i n g t o p r e d e f m e dm o d i f i c a t i o n r a t e d u r i n ge v o l u t i o n a r yo p t i m i z a t i o n f i n a l l y , t h e p r o p o s e ds t r a t e g y i s a p p l i e d t ot h ec o n s t r a i n e d m u l t i - o b j e c t i v eo p t i m i z a t i o n e v o l u t i o n a r ya l g o r i t h m ，a n dt h e nt h ea l g o r i t h mi st e s t e do n7b e n c h m a r kp r o b l e m sa n d t h ec o m p a r i s o nb e t w e e no u rs t r a t e g ya n dd e b sc o n s t r a i n e d - d o m i n a t i o np r i n c i p l e d e m o n s t r a t e st h a to u rs t r a t e g yo p t i m i z e s3 0 f a s t e rt h a nd e b si nt h ec i r c u m s t a n c e s t op r e s e r v ee q u i v a l e n td i s t r i b u t i o na n dc o n v e r g e n c eo f t h es o l u t i o n sf o u n d o ) i nm a t h e m a t i c s ，t h er e a c t i v ep o w e ro p t i m i z a t i o ni sat y p i c a ln o n l i n e a ra n d d i s c r e t eo p t i m i z a t i o np r o b l e m t h i sd i s s e r t a t i o np r e s e n t sa na l g o r i t h mf o rs o l v i n gi t t h r o u g ht h ea p p l i c a t i o no f e v o l u t i o ns t r a t e g y ( e s ) w i t hs t o c h a s t i cr a n k i n g i no r d e rt o b e t t e ri m p r o v et h eo p t i m i z a t i o np e r f o r m a n c ea n dp r a c t i c a l i t y ，t h ec o d i n gm e t h o df o r i n t e g e rd a t ao ft r a n s f o r m e rt a pp o s i t i o ni sd e s i g n e dd e l i b e r a t e l ya n dt h es e l f - a d a p t i v e o p t i m i z a t i o nt e r m i n a t i o nc o n d i t b nb a s e do nv a r i a n c ei sa l s op r e s e n t e d n ep r o p o s e d m e t h o dh a sb e e nt e s t e du n d e rs i m u l a t e dc o n d i t i o n so ni e e e 14a n di e e e 1 18b u s 、，i s y s t e m s t h eo p t i m a l r e a c t i v ep o w e rr e s u l t so b t a i n e du s i n gi m p r o v e de sa r e c o m p a r e dw i t h i n i t i a l p o w e r1 0 s s i t i ss h o w nt h a to u rs t r a t e g yc a nd e c r e a s e r e s p e c t i v e l yn e a r l y4 4 3 a n d4 3 o f i n i t i a l l o s s t os u mu p ，an o v e lc o n s t r a i n th a n d l i n gs t r a t e g yb a s e do ni n f e a s i b l ei n d i v i d u a l s t o c h a s t i cb i n a r y m o d i f i c a t i o ni sp r e s e n t e df o rs l o 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 n p r o b l e m s a tt h es a m et i m ee v o l u t i o n a r ys t r a t e g yw i t hs t o c h a s t i cr a n k i n gi sa p p l i e d t or e a c t i v ep o w e ro p t i m i z a t i o n t h ea b o v e a c h i e v e m e n tw i l lb eh e l p f u lf o rt h e d e v e l o p m e n to fe v o l u t i o n a r ya l g o r i t h ma n di t sa p p l i c a t i o n k e yw o r d s ：e v o l u t i o n a r ya l g o r i t h m s ，c o n s t r a i n e dm u l t i - o b j e c t i v eo p t i m i z a t i o n , e v o l u t i o n a r ys r a t e g y ，r e a c t i v ep o w e ro p t i m i z a t i o n 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。本论文除了文中特别加以标注和致谢的内容外，不包含其他人或其他机 构已经发表或撰写过的研究成果，也不包含为获得南京信息工程大学或其他教育 机构的学位或证书而使用过的材料。其他同志对本研究所做的贡献均已在论文中 作了声明并表示谢意。 学位论文作者签名：签字日期： 山掣。 关于论文使用授权的说明 南京信息工程大学、国家图书馆、中国学术期刊( 光盘版) 杂志社、中国科 学技术信息研究所的中国学位论文全文数据库有权保留本人所送交学位论文 的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文，并通过网 络向社会提供信息服务。本人电子文档的内容和纸质论文的内容相一致。除在保 密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全 部或部分内容。论文的公布( 包括刊登) 授权南京信息工程大学研究生部办理。 口公开口保密( 年月) ( 保密的学位论文在解密后应遵守此协议) 学位论文作者 指导教师签名 签字日期：皇兰堡至鱼旦望旦 签字日期：型丝生! i 第一章绪论 进化算法( e v o l u t i o n a r ya l g o r i t h m s ，简称e a s ) 是基于达尔文( d a r w i n ) 的进化论，在 计算机上模拟生物进化机制而发展起来的，它将问题的求解表示成染色体的适者生存过程， 通过染色体的一代代进化，最终收敛到最适应环境的个体( 即问题的最优解或近似最优解) 。 它具有高度并行性、自组织、自学习与自适应等特征，为解决复杂问题提供了一种新途径。 近年来，进化算法成功应用于机器学习、过程控制和工程优化等领域，引起了计算机科学及 工程应用等领域的学者们的极大兴趣。自2 0 世纪8 0 年代中期以来，世界上许多国家都掀起了 进化算法的研究热潮。 本章首先介绍课题的研究背景及意义；然后给出本文的主要研究内容及组织安排；最后 是本章小结。 1 1 论文研究背景 1 1 1 进化算法研究背景 1 8 5 9 年，达尔文创立的进化论，作为生物界以及人类文明史上的一个里程碑，促进了 科学技术的发展。按照达尔文的进化论，地球上的每一物种从诞生开始就进入了漫长的进化 历程，生物种群从低级、简单逐渐进化到高级、复杂。各种生物要生存下来，都要经历“物 竟天择，适者生存”的过程。根据孟德尔( m e n d e l ) 和摩根( m o r g a n ) 的遗传学理论，遗 传物质是作为一种指令密码封装在每一个细胞中，并以基因的形式排列在染色体上，每个基 因有特殊的位置并控制生物的某些特性。不同的基因组合产生的个体对环境的适应性不一 样，通过基因杂交和突变可以产生对环境适应的后代。经过优胜劣汰的自然选择，适应度值 高的基因结构得以保存下来，从而逐渐形成了经典的遗传学染色体理论，揭示了遗传和变异 的基本规律。 大多数高级生物是以自然选择和有性繁殖这两种基本过程实现进化发展的：自然选择决 定了生物种群中哪些个体能够存活并繁殖，有性繁殖保证了生物后代基因中的杂交和重红 从而使得群体的进化比其他方式更加快速而有效。自然界的生物进化是一个不断循环的过 程，在这一过程中，生物群体也就不断进化和完善。可见，生物进化过程本质上是一个优化 过程，除了进化过程的最终结果，我们可以利用这一过程本身去解决一些较为复杂的问慝 这样，我们不必非常明确地描述问题的全部特征，只需要根据自然法则来产生新的更好解。 进入2 0 世纪6 0 年代以来，生物学的进化论被推广应用于工程技术领域，形成一种新型 1 的计算方法一进化算法。它采用简单的编码技术来表示各种复杂的结构，并通过对一组编码 表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。由于它采用 种群的方式组织搜索，可以同时搜索解空间内的多个区域。而且基于群体搜索的方式使得进 化算法特别适合求解大规模并行计算问题。进化算法在具有自组织、自适应和自学习等特征 同时，优胜劣汰的自然选择和简单的遗传操作使得它具有不受其搜索空间限制性条件( 如可 微、连续等) 的约束，也不需要其他的辅助信息( 如导数) 的特点。这些崭新的特点使得进 化算法不仅能够获得较高的优化效率而且具有简单、易操作和通用性的特性。 通常，进化算法包括遗传算法( g e n e t i c a l g o r i t h m ，简称g a s ) 、进化规划( e v o l u t i o n a r y p r o g r a m m i n g ，简称e p ) 和进化策略( e v o l u t i o n a r ys t r a t e g y ，简称e s ) 三个分支。它们在进 化原则上是一致的，但是在实施进化的手段上却各有特点，互不相同。进化算法作为一类启 发式搜索算法，已被成功应用于多目标优化领域，发展成为一个比较热门的研究方向进化 多目标优化( e v o l u t i o n a r ym u l t i - o b j e c t i v eo p t i m i z a t i o n ，简称e m o ) 。1 9 8 5 年，s c h a f f e r 提出 了第一种多目标进化算法；向量评估遗传算法( v e c t o r - v a l u a t e dg e n e t i ca l g o d t h m s ，简称 v e g a ) 【，被看作是进化算法求解多目标优化问题的开创性算法。从上个世纪9 0 年代中后 期开始，国际上掀起了e m o 的研究热潮，各国学者们相继提出了许多不同的进化多目标优 化算法。1 9 9 3 年，f o n s e n o a 和f l e m i n g 提出了以p a r c t o ( p a r e t o - o p t i m a ls e t ) 排序为基础的 多目标进化算法【2 j ( m u l t i - o b j e c t i v eg e n e f i c a l g o r i t h m s ，简称m o g a ) ，s r i n i v a s 和d e b 提出 了非支配排序遗传算法【3 】( n o n - d o m i n a t e ds o r t i n gg e n e f i c a l g o f i t h m ，简称n s g a ) ，1 9 9 3 年， h o r n 和n a f p l i o t i s 等基于p a r e t o 支配关系，提出了小生境p a r e t o 遗传算法 4 1 ( n i c h e dp a r e t o g e n e t i c a l g o r i t h m ，简称n p g a ) 算法，这些算法习惯上被称为第一代进化多目标优化算法。 这些化算法以非支配排序的选择和保持共享函数的多样性为主要特点。 从1 9 9 9 年到2 0 0 3 年，以精英保留机制为特征的第二代进化多目标优化算法相继被提出： 1 9 9 9 年，z i t z l e r 和1 1 1 i e l e 提出了强p a r e t o 进化算法翻( s t r e n g t h p a r e t o e v o l u t i o n a r y a l g o r i t h m ， 简称s p e a ) 。该方法使精英保留机制在进化多目标优化领域流行起来。随后，2 0 0 1 年针对 其存在的不足对s p e a 进行了改进，提出了s p e a 2 t 6 】。2 0 0 0 年，k n o w l e s 和c o m e r 提出p a r e t o 种群进化策略1 7 j ( p a r e t o a r c h i v e d e v o l u t i o n s t r a t e g y ，简称p a e s ) ，随后提出了改进的p a r e t o 包络选择算法嘲( p a r e t oe n v e l o p e - b a s e ds e l e c t i o na l g o r i t h m ，简称p e s a ) 和p e s a - i i p j ，d e b 等在n s g a 基础匕提出n s g a - i o j 。2 0 0 1 年翻d 黜黜了n p g a 的改撒n p o a n 棚 胞0 0 3 年以来，进化多目标优化前沿领域的研究呈现出新的特点。各种新的概念、机制 和策略 1 2 1 开始引入到e m o 中。l a u m a l n n s 和d e b t 培】提出t s - p a r e t o ，b r o c k o f f 和z i t z l e r 1 4 1 提出了 部分占优，a l f r e d o 和c o e l l o 等【1 5 】提出了p a r e t o i 刍适应占优。d e b 和s a x e n a 用主分量分析【1 6 1 、 相关熵主分量分析【1 7 l 等方法结合进化计算来解决高维多目标优化问题。随着进化算法理论研 2 究的不断深入和应用领域的不断拓广，进化算法必将取得更大的成功。 虽然多目标优化方面进展很快，但对处理多目标优化问题中约束条件的研究较少，并主 要集中在惩罚函数、约束支配和不可行个体的修正方法等方耐塘】。惩罚函数法是求解约束优 化问题最常用的方法，但是其存在着一定的缺陷，其中最为关键的缺陷是惩罚系数的合理设 置十分复杂，往往需要多次试验来不断进行调整并且与问题相关。其次，比较有效的约束处 理策略是d e b 等人提出的约束支配策略0 9 ，此策略认为可行解一定优于不可行解，实际上 是一种过惩罚策略，因此存在明显的不足之处。耿焕同在文献刚中，通过对不可行解精英保 留，并结合随机排序方法，给出了一种新的随机排序选择策略处理多目标优化问题中的约藕 现有的这些约束处理技术都存在各自的缺陷，往往只能适用于某一类问题的求解，难以推广。 本文通过对现有主要的适于多目标优化问题的约束处理方法进行比较分析的基础上结 合不可行个体修正和保留策略的优点，采用随机选择( 修正、保留) 和折半查找算法，提出 了一种基于随机折半修正策略的约束处理方法，即在优化过程中，设定修正率，随机地将违 反约束的个体通过折半修正策略转化成可行个体。为验证算法的有效性，我们选取了7 个标 准测试函数进行实验。 1 1 2 无功优化研究背景 电力工业是国民经济的重要基础行业，其安全经济运行对社会生产和生活具有十分重要 的作用。无功优化是保证电力系统安全稳定运行的重要手段之，在满足电网安全运行约束 条件下有效的电压控制和合理的无功补偿能够提高电压水平、改善电压，从而改善电力系 统的运行性能，而通过合理选择最佳补偿点及补偿容量，可以避免无功电源建设的盲目性， 对原有的无功配置进行评价和修正可降低电网有功损耗和电压损耗。 近年来我国电网建设保持高速增长势头，截止至2 0 0 9 年，我国电力装机总容量突破8 7 4 亿千瓦，电网规模超过美国，跃居世界第一位。电网线路损失率从2 0 0 2 年底的7 5 2 下降 到2 0 0 9 年的6 4 4 ，虽然网损有所降低，但是依然造成巨大浪费。随着电力系统的迅猛发 展，电网规模日趋庞大，结构日益复杂，负荷需求不断增长，电力系统经常运行在稳定极限 和重负荷条件下，电压稳定问题在电力系统运行中已显得日趋严重。如何在现有基础上充分 利用系统无功资源，保证系统的安全稳定运行，降低网损，提高供电质量，已成为电力部门 面临的实际问题，也是电力科学研究的重要课题之一。 电力系统中的电压是电能质量的重要指标。因此保证电压质量是电力系统规划设计和运 行管理的重要任务。电力系统的无功补偿与无功平衡是保证电压质量的基本条伟系统内无 功分布合理与否直接影响着电力系统的安全与稳定，并与经济效益直接挂钩。一方面，如果 系统内无功不足，将导致电压水平下降，系统的功率损耗和能量损耗加大，当电力系统发生 3 扰动时，有可能使电压低于临界电压，用电设备不能正常运行，严重时产生电压崩溃，进而 导致灾难性事故。1 9 7 0 年美国纽约大停电、1 9 8 3 年瑞典大停电和1 9 8 7 年东京大停电都是典 型的由于高峰负荷时无功不足而造成电压崩溃进而导致系统瓦解的事故。另一方面，系统内 无功过剩会导致系统电压过高，危害系统和设备的安全。另外，系统内无功的不合理流动， 会导致线路压降增大、线路损耗增加、供电的经济性下降。 总之，有效无功电源控制和合理的无功补偿不仅能有效地降低网络损耗改善电压质量 和保证系统电压的稳定性，而且能提高电力系统运行的经济性、安全性和稳定性，进而充分 发挥电能的经济效益。 在数学上，电力系统无功优化是典型的非线性规划问题具有非线性、不连续、不确定 因素较多等特点，其操作变量既有连续变量( 如：发电机机端电压和无功出力) ，又有离 散变量( 如；有载调压变压器分接头档位，补偿电抗器和电容器的投切组数) ，从而使得无 功优化求解十分复杂。n j c a r p e n f i e r 在上个世纪6 0 年代初首先提出了电力系统最优潮流概念 后，电力系统潮流优化问题在理论上和实际应用上都已经有了很大发展而无功优化问题是 潮流优化中的一个重要组成部分，属于非线性规划问题，其优化方法的发展与数学规划方法 的发展过程是密不可分的。几十年来国内外的很多专家学者对此开展了大量的研究工作提 出了刁黟i 肮化算法这些算法经归纳可以分为传统数学优化算法和智能优化算法两大类。 传统数学优化方法主要有：线性规划法( l i n e a rp r o g r a m m i n g ，简称l p ) 阱】、非线性规 划法( n o l i n e a rp r o g r a m m i n g ，简翻q l p ) 口2 1 和混合整数规划法嘲。传统数学优化方法从一 个初始解开始寻优，能否实现全局最优与初始点的选取密切相关，只有初始点离全局最优点 较近时，才可能达到真正的最优，否则产生的解只能是次优解，甚至是不可行解。 智能优化算法主要有：进化规划 2 4 1 、遗传算法口5 一、模拟退火算法鲫、粒子群搜索算 法口叼、禁忌搜索法【2 9 1 、差分进化印1 等。智能算法以其独特的优点和机制为解决复杂优化问 题提供了新的思路和手段，广泛应用于当前传统的数学优化方法难以求解的大规模非线性优 化问题中。在一定程度上提高了计算的收敛性和速度，弥补了数学优化方法的不足。 r u n a r s s o n 和y a o 在对目标函数值和约束违反程度关系分析的基础上，通过比较概率p 避免了 权重系数的选择，提出了随机排序方法p 1 1 ，该方法适用范围广，是目前较为经典的约束处理 技术 本章以r u n a r s s o n 和y a o 的工作为基础，我们提出将带随机排序策略的进化策略应用于电 力系统无功优化，并选取i e e e - 1 4 和i e e e - 1 1 8 节点系统进行仿真分析。 1 2 本文研究内容 大多数工程实践和科学研究问题都是多目标优化问题，存在多个彼此冲突的目标。由于 4 问题自身的不同特点，运筹学中的传统方法已难以独立解决。进化算法作为一种基于群体搜 索的智能优化方法，鲁棒性强且具有全局搜索能力，十分适合求解约束优化问题。 本文旨在通过对进化算法进行深入研究和探索，面向带约束的多目标优化问题设计高效 的进化算法策略；面向电力系统无功优化问题，把进化策略算法应用于电力系统无功优化， 并通过实验进行分析。具体而言，本文的工作主要有以下两个方面： ( 1 ) 针对多目标约束优化，通过对现有主要的适于多耳标优化问题的约束处理方法进行 比较分析的基础上，结合不可行个体修正和保留策略的优点，采用随机选择( 修正、保留) 和折半查找算法，提出了一种基于随机折半修正策略的约束处理方法并选取7 个标准测试 函数进行实验。实验结果和分析表明，与d e b 等人提出的n s g a - i i 相比，该算法在保持同 等最优解集( 逼近性和分布性) 的情况下，优化效率有明显提高； ( 2 ) 在数学上，电力系统无功优化是典型的非线性规划问题，具有非线性、不连续、不 确定因素较多等特点。传统数学优化方法对这些问题的优化能力有隅所获得的解也不令人 满意。针对此问题，借鉴x y a o 等人提出的随机排序策略思想，将进化策略算法应用于电力 系统无功优化，并选取i e e e - 1 4 和i e e e 1 1 8 节点系统进行实验。实验结果和分析表明，与 i e e e - 1 4 和i e e e 一1 1 8 节点系统初始网损相比，该算法获得的网损值有明显降低。 1 3 本论文组织安排 本论文其余各章节的组织如下：第二章主要介绍单目标优化、多目标优化算法及约束处 理技术；第三章主要介绍电力无功优化的相关概念，并介绍了用以解决无功优化问题的算法， 最后给出了无功优化数学模型；第四章以多目标优化为基础，提出了随机折半修正策略的多 目标约束优化算法，并选取标准测试函数对算法进行实验以验证算法的有效性第五章介绍 进化策略算法在电力系统无功优化中的应用，并选取了2 个i e e e 节点系统进行试验以验证 算法的有效性；第六章是总结与展望，总结本论文的工作，并展望了下一步研究内容。 1 4 本章小结 本章首先简要介绍了进化算法及无功优化问题的研究背景和本论文的研究立足点，然后 介绍了本论文的研究内容，最后介绍了本论文的组织安排。 s 第二章进化算法研究 大多数工程实践和科学研究问题都是多目标优化问题，存在多个彼此冲突的目标，如何 获取这些问题的最优解，一直都是学术界和工程界关注的焦点问题。由于问题自身的不同特 点，运筹学中的传统方法已难以独立解决。进化算法( e v o l u t i o n a r ya l g o r i t h m s ，简称e a s ) 作为一种基于群体搜索的全局优化算法，十分适合求解约束优化问题。因此，利用进化算法 求解这些问题已越来越受到国内外研究者们的关注。 本章首先对进化算法进行概述；然后分别介绍进化单目标约束优化、进化多目标优化和 约束处理机制；最后是本章小结。 2 1 进化算法概述 2 1 1 进化算法框架 进化算法是以达尔文的进化论思想为基础，通过模拟生物自然选择与自然进化的随机搜 索算法。生物进化是通过繁殖、变异、竞争和选择实现的，而进化算法则主要通过选择、重 组和变异这三种操作实现优化问题的求解或近似求解凹。图2 1 给出了进化算法基本框架： 图2 1 进化算法基本框架 其中，r 、m 、s 分别表示重组算子、变异算子、选择算子。 2 1 2 进化算法特征 进化算法作为基于群体搜索的智能优化算法具有如下特征 6 ( 1 ) 有指导搜索 进化算法的搜索策略，既不是盲目式搜索，也不是穷举式的全面搜索，它是有指导的搜 索。指导进化算法执行搜索的依据是适应度，也就是它的目标函数。在适应度的驱动下，使 进化算法逐步逼近目标值。 ( 2 ) 适应搜索 进化算法在搜索过程中，借助重组、变异、选择等操作，体现“物竞天择，适者生存” 的自然选择规律，无需添加任何额外的操作，就能使群体的品质不断得到改进，具有自适应 环境的能力。 ( 3 ) 渐进式寻优 进化算法从随机产生的初始可行解出发，不断迭代，在迭代过程中个体的适应度值和群 体的平均适应度值不断得到改进，最终可得到一个或几个较高适应度的个体，求得问题的最 优解或近似最优解，这是一个逐渐寻优的过程。 ( 4 ) 并行式搜索 进化算法每一代进化都是针对一个进化群体，而不是单个个体。因此，进化算法是一种 并行式算法，大大提高了优化效率。 ( 5 ) 黑箱式结构 进化算法根据所解决问题的特征，用码串表达问题及选择适应度，一旦完成这两项工作， 其余的重组、变异、选择等操作可按照固定的方式进行。进化计算所要研究的是输入输出的 关系，并不深究造成这种关系的原因，因此便于处理因果关系不明确的问题。 ( 6 ) 全局最优解 进化算法采用了多点并行搜索的方式，通过产生新个体来扩大搜索范围，搜索时在整个 搜索区域的不同部分同时进行，因此避免了早熟现象，使得搜索得到的解是全局最优解或者 全局近似最优解。 由上述可以看出，与传统优化方法相比，进化算法有如下优势： ( 1 ) 进化算法与初始群体无关，而传统优化方法则依赖于初始解。 ( 2 ) 进化操作是概率性的，而非确定性的，在搜索过程中不容易陷入局部最优，即使在 所定义的适应值函数是不连续的、非规则的或有噪声的情况下，也能以很大的概率找到全局 最优解或近似最优解。 ( 3 ) 进化算法固有的并行性，使得进化结果不局限于单值解，非常适合于求解复杂的多 目标问题。 ( 4 ) 进化算法采用自然进化机制来表示复杂的现象，充分利用适应值函数而不需要其它 先验知识，能够快速可靠地解决传统方法难以解决的问题。 7 ( 5 ) 进化算法容易介入到已有的模型中，并且具有可扩展行，易于其它优化技术混合。 进化算法也存在一些不足p 3 】： ( 1 ) 进化算法中的参数，如进化代数、重组概率、变异概率、种群规模等，往往是根据 经验设定，且在一定程度上与问题本身有关： ( 2 ) 进化算法的收敛问题，尽管在理论研究上已经取得了一定成果，但在实际求解问题 时收敛性的判定缺乏理论指导。 进化算法可成功地用于优化问题的求解，而现实世界中的优化问题往往都带有约束且不 止一个优化目标，甚至是相互冲突的。下面将对进化单目约束标优化、进化多目标优化进行 介绍 2 2 进化单目标约束优化问题的定义 为与多目标优化问题相区分，特定义单目标约束优化问题。不失一般性，以最小化为例， 单目标约束优化问题可形式化描述为： m i n 厂( 功，x = ( 五，毛，) r ”( 2 - 1 ) 其中，f ( x ) 为目标函数，x s n f ，s c r 为1 3 维的搜索空间，常数向量l 和u 表示其 边界，定义为： x t 坼，f = 1 ，2 ，刀( 2 - 2 ) f 为可行域，满足1 1 1 个附加的线性或非线性约束( m 0 ) ： f = x rlg ，( x ) o ，h a x ) = o ，1 j f g ，l k p ( 2 - 3 ) 其中，q 为不等式约束的数目，p 为等式约束的数目。对于一个不等式约束在可行区域 f 的某一点x 处满足g ，( 功= 0 ( 1 g ) ，则称该约束在点x 处是活跃的( a c t i v e ) 因此， 所有等式约束在可行解区域f 内都是活跃的。 2 3 进化多目标优化 与传统优化方法相比，进化算法更适合求解多目标优化问题。首先，进化算法具有隐含 的并行处理能力，每次运行都能获得多个有效解。其次，进化算法对p a r e t o 前沿的形状和连 续性不敏感，能很好地逼近非凸或不连续的p a r e t o 前沿。本节部分首先讨论多目标优化问题 定义并给出几个重要的定义。 8 2 3 1 进化多目标优化问题的定义 在多目标优化中，对于不同的子目标函数可能有不同的优化目标，有的可能是最小化目 标函数，也可能是最大化目标函数，也可能是最小化部分子目标函数，而最大化其它子目标 函数。 为了处理方便，一般将各子目标优化函数统一转化为最小化或者最大化目标函数不失 一般性，以最小化目标函数为例，多目标优化问题定义如下： m i ny = f ( x ) = ( f d x ) ，五( 功，z ( 功) 7 s j 吕( x ) o ( i = 1 ，2 ，q ) ( 2 - 4 ) h j ( x ) = o ( j = 1 ，2 ，力 其中，r 表示目标函数个数；炉( x l ，x 2 ，舄) 表示r 维决策空间x 中的一个决策向量， f ( x ) 定义了r 个决策空间向目标空间的映射函数，锨) ( 1 鳓为第k 个目标函数，舀( x ) 鲥i 1 ， 2 ，q ) 定义了q 个不等式约束，h i ( x ) = 0 ( j _ l ，2 ，p ) 定义了p 个等式约束。 由于多目标优化所得到的解是一个集合，通常称为p a r c t o 解集，在此基础上给出几个重 要定义： 定义1 1 可行解 对于某个x x ，如果x 满足( 2 - 4 ) 式则为可行解。 定义1 2 可行解集合 由x 中所有可行解组成的集合称为可行解集合。 定义1 3p a r e t o 支配( p a r e t od o m i n a t e ) 决策向量x 。e x p a r e t o 支配决策向量x v e x ，记为x u - x v ，当且仅当： ( 1 ) v i ( 1 ，2 ，) 满足厂( 毛) 厂( 矗) ( 2 ) 3 j ( 1 ，2 ，) 满足厂( 毛) 厂( ) ( 2 5 ) 此时，也称决策向量x v p a r e t o 劣于决策向量) 【1 。若决策向量) ( | l 与决策向量x v 不存在p a r e t o 支配关系，则称它们非支配( n o n - d o m i n a t e d ) 。 定义1 4p a r e t o 最优解( p a r e t oo p t i m a l i t y ) 决策向量吒x 称为x 上的p a r e t o 最优解，当且仅当1 甄x 使得毛 吒 定义1 5p a r e t o 最优解集( p a r e t oo p t i m a ls e t ) 对于给定的多目标优化问题f ( x ) ，p a r e t o 最优解集p 定义为： p = 吒x 1 1 孤x ， 毛) ( 2 - 6 ) 9 定义1 6p a r e t o 前沿( p a r e t of r o n t ) 对于给定的多目标优化问题( x ) 和p a r e t o 最优解集p ，p a r e t o 前沿p f 定义为： p f = “= ( 屯) i 吒p ) ( 2 7 ) 显然，p a r e t o 前沿是p a r e t o 最优解集在目标空间中的像。以最小化两目标为例，如图2 2 所示，阴影区域表示搜索区域，表示目标，粗实线表示最优前沿，实心点a ，b ，c ， d ，e 分布在最优前沿上，是p a r e t o 最优解，阴影区域内空心点都不在最优前沿上，不是最 优解，它们受支配于最优前沿上个体。 辱 图抛两目标p a r e t o 最优前沿 定义1 7 凸集和凹集 设s 是一个凸集，若x l ，x 2 s ，则x e s 。其中x = o x i + ( 1 - o ) x 2 ，o 卿s l ( 2 - 8 ) 也就是说，如果一个集合中任意两点的连线上点仍在该集合中，则该集合为凸集，否则 为凹集。图2 3 和2 - 4 所示分别为凸集和凹集。 图2 - 3 凸集 1 0 图纠凹集 从上述定义中可以看到，多目标优化的解是一个集合而不是单个解，且解集要满足逼近 性和分布性两个条件鲫。 因此，多目标优化与单目标优化的主要区别体现在 ( 1 ) 优化目标的区别：多目标优化需同时满足逼近性和分布性；单目标优化只要满足逼 近性即可； ( 2 ) 搜索空间的区别：多目标优化不仅需要考虑决策空间，还需要考虑目标空间；单目 标优化只需考虑决策空间； ( 3 ) 人工限制的区别：现实世界中的优化问题往往都具有多个目标，以前的研究者通过 人工限制方式将其转换为单目标优化问题，而多目标优化则可以不需要人工限制的介入。 2 3 2 进化多目标优化的传统方法 按照使用问题先验知识的程度，传统方法可分为如下四类p 】： ( 1 ) 不使用先验知识的方法，即搜索前后都不使用先验知讽 ( 2 ) 搜索后使用先验知识的方法，即找到最优解集后再按先验知识选择； ( 3 ) 搜索前使用先验知识的方法，即按先验知识搜索最优解集； ( 4 ) 交互方法，即搜索过程中使用先验知识。 目前，具有代表性的传统方法有： ( 1 ) 聚集函数法 在处理多目标优化问题时，最直接的方法就是聚集函数法【3 5 ，3 们。这种方法是将被优化的 所有子目标组合或聚集为单个目标，从而将多目标优化问题转换为单目标优化问题。例如， 假设有r 个子目标，对r 个子目标的优化问题可以转化为单目标优化问_ 题= - 二 m i n c o ，, f , c x ) ( f = l ，2 ，) ( 2 - 9 ) 其中，c o i ( 妣0 ) 为第i 个子目标的权重系数，且一般有： 哆=1(2-10) i