（电力系统及其自动化专业论文）粒子群优化算法及其在电力系统优化运行中的应用.pdf

a b s t r a c t a tp r e s e n t , t h et o t a li n s t a l l e dc a p a c i t yo ft h ep o w e rs y s t e mi nc h i n ah a sa l r e a d y r a n k e dt h es e c o n dp l a c ei nt h ew o r l d t h e r e f o r e i th a sb e e no n eo ft h eh o tf o c u s e s c o n c e r n e db yt h es c h o l a r st om a k es h o r t - t i m eg e n e r a t i o np l a n sa n dc o s to p t i m i z a t i o no f p o w e rs y s t e mu n d e rt h ec o n d i t i o no fc u r r e n tt e c h n i q u ee q u i p m e n t sa n dn o r m a li n d u s t r y l e v e l ，w h i c hi st op r o p e r l yd i s t r i b u t et h ea s s i g n m e n ta m o n gt h eg e n e r a t i n gu n i t ss oa st 0 a v o i dm a s sw a s t eo ft h ee n e r g yc a u s e db yt h eu n n e c e s s a r yo n - o f fa n dt h ei d l i n go ft h e m a c h i n e s o nt h eo t h e rh a n d ，w i t ht h er a p i dd e v e l o p m e n to fn a t i o n a le c o n o m ya n dt h e i n c r e a s i n gp o w e rd e m a n d ，t h ee c o n o m i c a lo p e r a t i o no f t h ep o w e rn e t w o r k sg e t sm o r ea n d m o r ea t t e n t i o n s w h i l e 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 sc o n s i d e r e de f f e c t i v et o g u a r a n t e et h es a f e t ya n dt h ee c o n o m i c a lo p e r a t i o no fp o w e rs y s t e m m a k i n gr a t i o n a l o p t i m i z a t i o nt ot h er e a c t i v ec o m p o n e n tn o to n l yc a ni m p r o v et h ev o l t a g el e v e lo ft h e s y s t e m so p e r a t i o n ，b u ta l s oc a l ld e c r e a s et h ea c t i v ea n dt h er e a c t i v en e t w o r kl o s so f p o w e r s y s t e ma n dm a k ei t so p e r a t i o nm o r ee f f e c t i v e i nt h i sp 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 ra n a l y z e d ， b a s e d0 1 1t h ec u r r e n tr e s e a r c hs t a t u so ft h eu n i tc o m m i t m e n to fp o w e rs y s t e ma n dt h e r e a c t i v e p o w e ro p t i m i z a t i o n o fd i s t r i b u t i o n s y s t e m t h e n t h ep a r t i c l es w a r m o p t i m i z a t i o n ( p s o ) w h i c hh a sb e t t e rs e a r c he f f i c i e n c ya n dc o n v e r g e n c ep r o p e r t y i s s e l e c t e dt ob em o d i f i e d m o r e o v e r ，n e ws o l u t i o n sa r es u g g e s t e d ，w h i c ha r eb a s e do nt h e m o d i f i e dp a r t i c l es w a r mo p t i m i z a t i o n ( m p s o ) a n da i m i n ga tt h eu n i tc o m m i t m e n to f p o w e rs y s t e ma n dt h er e a c t i v ep o w e ro p t i m i z a t i o no fd i s t r i b u t i o ns y s t e m i ns u m ，t h e w o r ki nt h i sp a p e rc o m p r i s e st h et w op a r t sa sf o l l o w s ： 1 t h ea l g o r i t h mo fm o d i f yp a r t i c l es w a r mo p t i m i z a t i o n ( m p s o ) w h i c hb a s e so n t h em e t h o do f i n e r t i aw e i g h ti sa t t e m p t e d ，a n dal o to f d i s c u s s i o ni sm a d eo nt h es e l e c t i n g p r i n c i p l eo fc o r r e l a t e dp a r a m e t e r st oe f f e c t i v e l yo v e r c o m et h ep r e m a t u r i t yp r o b l e mo f p a r t i c l es w a r mo p t i m i z a t i o na n dt oi m p r o v et h eo p t i m i z a t i o np r o p e r t yo fi t t h e s ea r e t e s t e db yt h eo p t i m i z i n gs i t u a t i o n so fs o m et y p i c a lc o m p l i c a t e df u n c t i o n s ，a n df u r t h e r d i s c u s s i o ni sm a d eo nh o wt h es a m p l i n go fe v e r yp a r a m e t e ro ft h ea l g o r i t h ma f f e c t st h e o p t i m i z i n gp r o c e s s 2 a i m i n g a tt h eu n i tc o m m i t m e n to fp o w e rs y s t e ma n dt h er e a c t i v ep o w e r o p t i m i z a t i o no fd i s t r i b u t i o ns y s t e m ，n e ws o l u t i o n sa r es u g g e s t e dw h i c ha r eb a s e do i lt h e m o d i f i e dp a r t i c l es w a r mo p t i m i z a t i o n0 m s o ) t h r o u g ht h ec o m p a r i s o no fi t s o p t i m i z i n gr e s u l tw i t ht h eo t h e rr e s u l t sb yo t h e ri 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 s ，t h e f e a s i b i l i t ya n dv a l i d i t yo ft h ep a r t i c l es w a r mo p t i m i z a t i o n & s o ) i sv a l i d a t e d ，a tt h e a s p e c to ft h eu n i tc o m m i t m e n to fp o w e rs y s t e ma n dt h er e a c t i v ep o w e ro p t i m i z a t i o no f d i s t r i b u t i o ns y s t e m a tt h es a m et i m e t l a ta l s ot e s t i f i e st h ee f f e c t i v e n e s so ft h ei n e r t i a w e i g h tm e t h o do ns o l v i n gt h ep r c m a t u f i t yp r o b l e r ao fp a r t i c l es w a r mo p t i m i z a t i o n o s c o k e yw o r d s ：p o w e r s y s t e m ，d i s t r i b u t i o ns y s t e m ，u n i tc o m m i t m e n t , r e a c t i v ep o w e r o p t i m i z a t i o n ，p a r t i c l es w a r mo p t i m i z a t i o n i r 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰 写过的研究成果，也不包含为获得丕鲞盘堂或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示了谢意。 学位论文作者签名：写专嬲签字日期：1 。6 年工月2 3 日 学位论文版权使用授权书 本学位论文作者完全了解墨注盘堂有关保留、使用学位论文的规定。特 授权鑫洼盘茎可以将学位论文的全部或部分内容编入有关数据库进行检索，并 采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有 关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：多蜕，导师签名：、邑7 多孕 签字日期：知。厶年2 - 月n 日签字日期：二d d6 年上月2 3b 天津大学硕士学位论文第一章绪论 i i 本文课题及其研究背景 第一章绪论 电力系统是由发电、输电、变电、配电和用电等设备和技术组成的一个将一次 能源转换为电能的统一系统【”。 中国发电总装机容量已突破4 亿k w ，居世界第二位。根据国家发改委最新统计数 据，我国水电装机容量已超过1 亿k l p ，占总装机容量2 5 ，火电约占7 2 ，核电以及其 他能源发电约占3 左右。据了解，我国电力工业自1 8 8 2 年起步。到1 9 4 9 年。装机容 量仅为1 8 5 万k w ，新中国成立后，我国电力工业步入高速发展期，5 5 年间装机容量增 长迸2 1 0 倍，目前，我国在建的电力项目约3 3 8 亿妍。预计到2 0 0 6 年底，全国电力装 机将超过5 亿k w ，2 0 1 5 年有望突破1 0 亿k w ，超过美国，成为世界第一电力大国。 我国的火力发电厂以燃煤为主，燃油、燃气机组容量目前尚不足5 。火力发电 厂的锅炉效率一般为8 0 9 4 ，汽轮机的能量转换效率一般为3 0 4 8 ，发电机的 效率一般高于9 5 ，大型发电机的效率高于9 8 5 。综合考虑，现阶段我国全国发电 煤的平均效果大概为3 5 左右。同时火力发电厂本身也是用电大户，拥有很多附属机 构，其自用电率高达5 1 0 。发电厂真正供出的电量要扣除其厂用电。按供电量算 出的煤耗称为供电煤耗，按供电煤耗算出的效率称为供电效率，也称为净效率，目 前我国仅仅为3 2 2 左右。与国家标准和国外先进水平差距依然很大【2 】。 要改善上述情况，除了改造现有火电厂减少能耗、以大容量临界机组替代中小 机组和大量发展热电联产以外，最主要的就是在现有技术水平和设备情况下，做好 短期发电计划和成本优化，恰当地在机组间分配负荷，以避免不必要的起停机和机 组空转所带来的巨大能耗。这就是本文所关注的问题之一。 另一方面，随着国民经济的迅速发展和用电量的增加，电网的经济运行也日益 受到重视。配电系统无功优化是电力系统安全经济运行的一个重要方面，对无功的 合理优化不仅仅可以提高系统运行的电压水平，而且可以降低系统的有功网损和无 功网损，提高电力系统的运行效率。 目前，我国配电电网存在供电能力不足、网架结构薄弱、供电可靠性较差、城 网线损率偏高等问题。同样，电网的电压合格率也不能令人满意，个别城市2 2 0 v 电 天津大学硕士学位论文 第一章绪论 网用户电压甚至达不到1 8 0 7 ，其原因主要有：电力负荷中异步电动机和中小容量变压 器占有很大比重，其消耗的无功功率约占全国无功负荷的8 0 9 0 ；管理上欠严格， 有些电网的自然功率因数过低，而有些电网的功率因数过高；电网结构不合理，导 线截面太小和无功潮流不合理等。配电系统无功优化问题是本文所关注的另一个热 点问题。 1 2 本文课题的研究概况 本文所提出的电力系统机组组合优化问题和配电系统无功优化问题，同属于电 力系统优化运行的范畴。 电力系统优化运行具有以下特点：( 1 ) 不确定因素较多：配电网络规划受国家 政策调整、社会经济发展、人口变动及环境变化等因素的影响，电力系统的发展条 件也在不断变化，规划期越长，条件、参数也就越难确定；( 2 ) 涉及的部门较多：配 电网络规划涉及到电力公司、城市规划、城市环保等各个部门。( 3 ) 规模庞大，计 算复杂。从数学上讲，电力系统优化运行是动态、多目标、多约束、非线性、非连 续、混合整数规划问题；一般的数学优化算法对于此类问题没有很好的解决办法。 现阶段对于电力系统优化运行的求解方法大致有以下三种：经典的数学优化方 法，启发式优化方法和智能优化算法 3 j 。 ( 一) 、经典的数学优化方法 由于需要解决问题自身的非线性，所以非线性规划法( n o n l i n e a rp r o g r a m m i n g ) 最先被应用到电力系统优化运行中非线性规划是处理具有非线性特征优化问题最 直接的方法，这种方法的数学模型建立比较直观，物理概念清晰，计算精度较高。然 而，非线性规划方法不同程度存在计算量大、内存需求量大、收敛性差、稳定性不 好、对不等式的处理存在一定困难等问题，其应用受到了一定限制。 随着研究的深入，研究人员发现可以采用局部线性化的方法，通过将非线性目 标函数和安全约束逐次线性化来对问题进行求解。他们将目标函数中的零次项和二 次项线性化，将配电系统规划视为对线性化的数学模型的求解。线性规划法的优点 是计算迅速，收敛可靠，便于处理各种约束，能满足实时调度对计算速度的要求，但优 化精度较差。 当前占主导地位的是混合整数规划法，就是先确定整数变量，再与线性规划法 协调处理连续变量。它解决了前述方法中没有解决的离散变量的精确处理问题，其 数学模型也比较准确地体现了电力系统优化运行的实际情况。例如，可采用混合整 2 天津大学硕士学位论文 第一章绪论 数规划法来求解无功优化问题，将混合规划法分解为整数规划和线性规划两个子问 题，减少了求解规模。混合整数规划法在工程应用中更趋于合理性，但计算时闻较长， 且其解的结果与初值的选取有关f 4 】。 ( 二) 、启发式优化方法 数学优化方法用数学优化模型描述电力系统优化运行问题，理论上可以保证解 的最优性，但通常电力系统规模很大，如果再考虑多阶段规划及本身众多的因素，此 问题将成为一个规模巨大的优化难题，单靠数学优化技术是无法解决的。启发式方 法不同于纯数学优化方法，它是以直观分析为依据的算法，而且同规划及运行人员 的经验相结合。相对于数学方法能够更为准确地实际模拟电力行为。 ( 三) 、智能优化算法 智能优化算法兴起于2 0 世纪8 0 年代初期，是一种解决组合优化问题的智能技术， 主要包括模拟退火( s i m u l a t e da n n e a l l i n g ，s a ) 、遗传算法( g e n e t i ca l g o r i t h m ，g a ) 、 禁忌搜索( t a b us e a r c h ，t s ) 、粒子群优化算法( p 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 ) 、 蚁群优化算法( a n tc o l o n y0 p t i m i z a i t o n n ，a c o ) 、混沌优化方法( c h a o t i co p t i m i z a t i o n a l g o r i t h m ，c o a ) 、人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k s ，a n n ) 等。 虽然上述智能优化算法在电力系统优化运行上有了很大的进展，但是单个智能 优化算法都还存在这样或那样的问题或不足。为了解决此问题，改进的智能算法和 混合智能算法应运而生，在解决配电网络优化闯题上有了进一步的突破。 1 3 本文所做的工作 如前所述，电力系统优化运行中的机组组合优化问题和配电系统无功优化问题 都是非常复杂的大规模、非线性、多目标、多约束的组合优化难题。 本文在以往电力系统优化运行研究的基础上，根据机组组合优化问题和配电系 统无功优化问题的特点，采用改进的智能p s o 优化算法研究了机组组合优化问题和配 电系统无功优化问题，主要的工作如下； ( 1 ) 、受s h i 和e b e r h a r t 等提出的惯性权重方法的启发，本文尝试了一种基于惯 性权重方法的改进粒子群优化( p s o ) 算法，并讨论了相关参数的选取原则，使之 能有效地克服了粒子群算法容易陷入局部收敛的问题，提高了粒子群算法的优化性 能。通过几个典型复杂函数的优化情况进行了验证，并进一步讨论了算法中各系数 的取值对于优化过程的影响。 ( 2 ) 、分析了电力系统机组组合问题，提出考虑阀点效应的电力系统机组组合 天津大学硕士学位论文第一章绪论 优化问题的数学模型，采用基于惯性权重法改进的p s o 优化算法对其进行优化计算， 并与采用其他智能优化算法得出优化结果进行比较分析，从而验证了基于惯性权重 法改进的p s o 优化算法的优良收敛性能。 ( 3 ) 、分析了配电系统无功优化问题以及常用的优化方法，提出采用基于惯性 权重法改进的p s o 优化算法来解决配电系统无功优化问题，并将优化结果与采用原 始p s o 优化算法的优化结果相比较，进一步验证了惯性权重法对于解决p s o 优化算法 容易陷入局部晟优问题的有效性，同时探讨了惯性权重的选取对于优化收敛过程的 影响。 本文的第一章介绍了课题的研究背景和意义，以及论文的主要工作的章节安排： 第二章对几种常用的智能优化算法进行了介绍；第三章分析了电力系统机组组合优 化问题，并提出采用基于惯性权重法的改进p s o 优化算法对电力系统机组组合优化 问题进行优化；第四章节分析了配电系统无功优化问题，并采用基于惯性权重法的 改进p s o 优化算法对其进行优化；第五章对全文进行总结。 4 天津大学硕士学位论文 第二章智能优化算_ ；去简介 2 1 粒子群优化算法 第二章智能优化算法简介 2 1 1 粒子群优化算法的产生 粒子群优化( p a r t i c l es w a r mo p t i m i z c r ，p s o ) 算法是一种基于群体智能( s w a r m i n t e l l i g e n c e ) 方法的演化计算( e v o l u t i o n a r yc o m p u t a t i o n ) 技术，是一种基于群体的 优化工具( 5 】。首先系统初始化为一组随机解，然后通过迭代寻求最优解。但是p s o 算法并没有遗传算法所涉及到的交叉、变异操作，而是通过粒子在解空间中跟随当 前最优粒子进行搜索。与同为基于群体的优化工具的遗传算法相比较，p s o 算法的 优势在于算法简单、容易实现，同时也具备了深刻的智能背景；既适合科学研究又 符合工程应用的要求。因此，p s o 算法一经提出，立刻引起了各方的广泛关注，并 在短短的几年时间里涌现出大量优秀研究成果，形成了一个研究热点。 p s o 算法最早是m k e n n e d y 和e b e r h a r t 受到人工生命( a r t i f i c i a ll i f e ) 的研究结果 启发于1 9 9 5 年提出的，其基本概念源于对鸟群捕食行为的研究同。最初是为了在二 维几何空间图形中优化模拟乌群不可预测的运动。p s 0 算法从这种模型中得到启示并 用于解决优化问题。p s o 算法中，每个优化问题的潜在解都是搜索空间中的一只鸟， 称之为“粒子”。所有的粒子都有个由目标函数决定的适应值( f i t n e s sv a l u e ) ， 每个粒子都由一个两维的速度变量决定各自飞翔的方向和距离。然后粒子们就追随 当前的最优粒子在解空间中搜索。p s o 算法初始化为一群随机粒子( 随机解) ，然后 通过迭代找到最优解。在每一次迭代中粒子通过跟踪两个极值来更新自己。第一 个极值就是粒子本身所经历的最优解，这个解被称为个体极值。另个极值是整个 种群目前所经历的最优解，这个极值被称为全局极值。另外也可以只选取整个种群 中的一部分作为粒子的邻居，在所有邻居中的极值被称为局部极值。由于认识到p s 0 算法在函数优化等领域所蕴含的广阔的应用前景，于是在k e n n e d y 和e b e r h a r t 之后依 然还有很多学者都进行了这方面的研究。目前。多种p s o 改进算法已广泛应用于函 数优化，神经网络训练，模式分类、模糊系统控制以及其他的应用领域【”】。 天津大学硕士学位论文 第二章智能优化算法简介 2 1 2 粒子群优化算法的基本原理 粒子群优化算法是基于群体的演化算法，其思想来源于人工生命和演化计算理 论。r e y n o l d s 对鸟群飞行的研究发现，鸟仅仅是追踪它有限数量的邻居，但最终的整 体结果是整个鸟群好像在一个中心的控制之下，即复杂的全局行为是由简单规则的 相互作用引起的。p s o 算法源于对鸟群捕食行为的研究，一群鸟在随机搜寻食物， 如果这个区域里只有一块食物，那么找到食物的最简单有效的策略就是搜寻目前离 食物最近的鸟所在的区域。p s o 算法就是从这种模型中得到启示而产生的，并用于 解决优化问题。另外，人们通常是以自己及他人的经验作为决策的依据，这就构成 了p s o 的一个基本概念。p s o 求解优化问题时，问题的解对应于搜索空间中一只鸟 的位置，称这些鸟为“粒子。( p a r t i c l e ) 或“主体”( a g e n t ) 。每个粒子都有自己的 位置和速度( 决定飞行的方向和距离) ，还有一个由被优化函数决定的适应值。各个 粒子记忆、追随当前的最优粒子，在解空间中搜索。每次迭代的过程不是完全随机 的，如果找到较好解，将会以此为依据来寻找下一个解。令p s o 初始化为一群随机 粒子( 随机解) ，在每一次迭代中，粒子通过跟踪两个“极值”来更新自己：第一个 就是粒子本身所找到的最好解，叫做个体极值点( 用p b e s t 表示其位置) ，全局p s o 中的另一个极值点是整个种群目前找到的最好解。称为全局极值点( 用g b e s t 表示其 位置) ，而局部p s o 不用整个种群而是用其中一部分作为粒子的邻居，所有邻居中的 最好解就是局部极值点( 用l b e s t 表示其位置) 。在找到这两个最好解后，粒子根据如 下的式( 2 1 ) 和式( 2 2 ) 来更新自己的速度和位置。粒子f 的信息可以用d 维向量表 示，位置表示为x ，= o j l x m ，石) 7 ，速度为v ，= ( v n ，v n ，v ，d ) 7 ，其他向量类似 则速度和位置更新方程为 v 譬= v 嘉+ c l 朋，甜j ( p 五b 甜嘉一x 刍) + ，11 、 c ：删；( 驴删；一z 二) j 。k 。+ l = x 。k 。+ v 譬1 ( 2 2 ) v ：是粒子i 在第k 次迭代中第d 维的速度：q ，岛是加速系数( 或称学习因子) ， 分别调节向全局最好粒子和个体最好粒子方向飞行的最大步长，若太小，则粒子可能 远离目标区域，若太大则会导致突然向目标区域飞去，或飞过目标区域1 9 l 。合适的 c ，岛可以加快收敛且不易陷入局部最优，通常令c t = c ：= 2 0 ：r a n d ，r a n d 2 是 o ， 1 之间的随机数；善：是粒子f 在第t 次迭代中第d 维的当前位置；p b e s t 刍是粒子，在 第k 次迭代中第d 维的个体极值点的位置( 即坐标) ；g b e s t d 是整个群在第d 维的全 局极值点的位置。为防止粒子远离搜索空间，粒子的每一维速度都会被钳位在 6 天津大学硕士学位论文第二章智能优化算法简介 卜。，+ v 。一】之间，。太大，粒子将飞离最好解：v 。一太小，将会陷入局部最 优。假设将搜索空间的第d 维定义为区间 - v 。一，+ v 。一】，则通常l y d 。= b 。， o 1 s k 1 0 ，每一维都用相同的设置方法。基本p s o 的流程可以描述为： s t e p l ：初始化 初始搜索点的位置x ? 及其速度v ? 通常是在允许的范围内随机产生的，每个粒子 的p b e s t 坐标设置为其当前位置，且计算出其相应的个体极值( 即个体极值点的适应 度值) ，而全局极值( 即全局极值点的适应度值) 就是个体极值中最好的，并将g b e s t 设 置为最佳粒子的当前位置。 s t e p 2 ：评价每一个粒子 计算每一个粒子的适应度值，如果其性能好于该粒子当前的个体极值，则将 p 6 e s t 设置为该粒子的位置，且更新个体极值。如果所有粒子的个体极值中最好的 优于当前的全局极值，则将g b e s t 设置为该粒子的位置，且更新全局极值。 s t e p 3 = 粒子的更新； 用式( 2 - 1 ) 和式( 2 2 ) 对每一个粒子的速度和位置进行更新。 s t e p 4 ：检验是否符合结束条件 如果当前的迭代次数达到了预先设定的最大次数( 或达到最小错误要求) ，则停 止迭代，输出最优解，否则转至l j s t e p 2 。 p s o 中并没有许多需要调节的参数，下面列出了这些参数以及经验设置：粒子 数( 种群大小) ：一般取2 0 4 0 ，对于大部分的问题，1 0 个粒子已经足够取得好的 结果，对于比较难的问题或者特定类别的问题，粒子数可以取到1 0 0 或2 0 0 。粒子的 长度d ( 空间维数) ：这是由优化问题决定的，就是问题解的长度。粒子的坐标范围： 由优化问题决定，每一维可以设定不同的范围。最大速度v 。决定粒子在一个循环 中最大的移动距离，通常设定为粒子的范围宽度。学习因子岛和“通常等于2 ，不过 在文献中也有其他的取值，但是一般e 。等于岛并且范围在0 和4 之间。终止条件；设 定最大循环数以及最小偏差要求，这个终止条件由具体的问题确定【1 0 1 。 2 1 3 粒子群优化算法的改进措施 p s o 收敛快，效率高，但也存在着精度较低，易发散等缺点。p s o 在寻优过程 中，由于所有的粒子都向最优解的方向飞去，所以粒子易于趋向同一化( 失去了多样 性) ，使得后期收敛速度明显变慢，并且所能达到的精度也比g a 低i 1 。若加速系数、 最大速度等参数设置的太大，粒子群可能错过最优解，造成算法不收敛。对此，很 天津大学硕士学位论文第二章智能优化算法简介 多学者对如何提高p s o 算法的性能作了大量的研究，并提出了许多改进措施，大致 有以下几种： 惯性权重( i n e r t i aw e i g h t ) 法 s h i 等提出了惯性权重的方法，粒子更新方程为 = 聊占托叫( p b e s t 占一工占) + ( 2 - 3 ) c 2r a n d ；( 驴e 肼：一) x=+vk+l(2-4) 上式运用惯性权重来控制前面的速度对当前速度的影响。s h i 等研究发现，较大 的w 可以加强p s o 的全局搜索能力，而较小的m ，能加强局部搜索能力。基本的p s 0 可以看作w = 1 ，因此在迭代后期缺少局部搜索能力。若将w 设置为从0 9 n 0 4 的线 性下降，使得p s o 在开始时探索较大的区域，较快地定位最优解的大致位置，随着w 逐渐减小，粒子速度减慢，开始精细的局部搜索( 这里w 类似于模拟退火中的温度参 数) 。该方法加快了收敛速度，提高了p s o 算法的性能。通常，权重系数w 由下式来 确定 w = 一w i n _ s x 一- - w r a m i t e r ( 2 5 ) l t e ，t w ，w 一分别是w 的最大值和最小值；i t e r ，妇，f 。分别是当前迭代次数和最大 迭代次数【1 2 l 。 压缩因子( c o n s tf i c t i o nf a c t o r ) 法 c i e r c 在研究p s o 的时候发现压缩因子有助于确保p s 0 算法收敛的特点，这种方法 的速度更新方程为 吲哗怕誓耐哆盯占一) + ( 2 - 6 ) c 2 ，绷磁( 驴甜一) ) 其中，z = 2 4 2 一妒一形2 4 力“2 i 为压缩因子，妒= c l + c 2 ，并且 4 。约束因子 法控制系统行为最终收敛，且可以有效搜索不同区域，该方法能得到高质量的解【”1 。 选择法 a n g e l i n e 于1 9 9 8 年借鉴进化计算的选择概念，将其引入p s o 算法。通过比较各个 粒子的适应值，淘汰差的粒子，而将具有较高适应值的粒子进行复制以产生等数额 的粒子来提高算法的收敛性。l o v b j e r g 等人进一步将进化算法中的交叉操作引入p s o 算法，交叉型p s o 与传统的p s o 模型的惟一区别在于粒子群在进行速度和位置的更 8 天津大学硕士学位论文第二章智能优化算法简介 新后还要进行交叉操作，并用产生的后代粒子取代双亲粒子。实验表明，与传统的 p s o 及传统的遗传算法相比，交叉p s o 搜索速度快，收敛精度高【m 峙】。 邻域法 s u g a n t h a n 于1 9 9 9 年提出了带有邻域操作的p s o 模型在该模型中，用每个粒子所 定义的当前邻域极值代替粒子群的当前全局极值。在优化的初始阶段，将邻域定义 为每个粒子自身，随着迭代次数的增加，将邻域范围逐步扩展到包含所有粒子，则 此时的邻域极值即为全局极值【1 6 1 。 拉伸法 p a r s o p o u l o s 和p l a g i a n a k o s 于2 0 0 1 年提出将拉伸技术用于p s o 最小化问题求解， 以避免陷入局部最小值的优化，这种模型称为s p s o s p s o 模型在检测到局部最优 后，立即对优化的函数进行拉伸变形操作，从而减小陷入局部最小的概率【1 7 1 。 p s o 算法是一个新的基于群体智能的进化算法，其研究远没有像遗传算法和模 拟退火算法那样深入，在理论上并不能保证能够得到最优解。p s o 算法在进行优化 问题的求解时应用范围有限，尤其对离散的组合优化问题，其理论建模还处于起步阶 段。p s o 算法中的一些参数，如学习因子c f ，c ：、惯性权重w 以及粒子个数往往根据 有限的应用经验确定，并不具有广泛的适应性。因此将p s o 与进化算法、模糊系统、 神经网络以及一些优化技术结合，根据不同的优化闯题建立相应的p s o 模型是p s o 算法当前的研究重点。 2 2 遗传算法 2 2 1 遗传算法的产生 近年来，随着人工智能应用领域的不断扩大，传统的基于符号处理机制的人工 智能法在知识表示、信息处理和解决组合爆炸等方面所遇到的困难越来越明显，于 是人们开始致力于研究一些能够处理当前难题的新型算法。1 9 7 5 年，j 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 ) 。g a 是基于“适者 生存”的一种高度并行、随机和自适应的优化算法，它将问题的求解表示成“染色 体”的适者生存过程，通过“染色体”群的一代代不断进化，包括复制、交叉和变 异等操作，最终收敛到“最适应环境”的个体，从而求得问题的最优解或满意解。 目前，随着计算机技术的发展，g a 越来越得到人们的重视，并在机器学习、模式识 别、图像处理、神经网络、优化控制、组合优化等领域得到了广泛的应用。 天津大学硕士学位论文第二章智能优化算法简介 2 2 2 遗传算法的基本原理 遗传编码；按照遗传算法的工作流程，当用遗传算法求解问题时，必须在目标 问题实际表示与遗传算法的染色体位串结构之间建立联系，即确定编码和解码运算。 由于遗传算法计算过程的鲁棒性，它对编码的要求并不苛刻。然而，编码的策略或 方法对于遗传算予，尤其是对交叉和变异算子的功能和设计有很大的影响。问题编 码一般应满足完备性、健全性和非冗余性三个原则，完备性是指问题空间中的所有 点都能成为g a 编码空间中点的表现型：健全性是指g a 编码空间中的染色体位串必须 对应问题空间中的某一潜在解；非冗余性是指染色体和潜在解必须一一对应。按照 遗传算法的模式定理，d ej o n g 进一步提出了较为客观明确的编码评估准则，称之为 编码原理。具体可以概述为有意义建筑模块编码规则和最小字符集编码规则，前者 表示编码应当易于生成与所求问题相关的短距和低阶的建筑模块；后者表示编码应 采用最小字符集使问题得到自然、简单的表示和描述。目前的编码方式有二进制编 码，大字符集编码、序列编码、实数编码、树编码以及乱序编码等许多方式f 炉聊。 评价函数：遗传算法将问题空间表示为染色体位串空间，为了执行适者生存的 原则，必须对个体染色体的适应性进行评价。因此，评价函数( 适应函数f i t n e s s f u n c t i o n ) 就构成了个体的生存环境。根据个体的适应值，就可以决定它在此环境下 的生存能力。若用s l 表示位串空间，s l 上的适应值函数可表示为厂( 。) ：s 寸震+ ，其 中盂+ 表示非负实数集合对最小值优化闯题，一般建立如下适应函数( 曲和目标 函数9 0 ) 的对应关系： 俐= 叩莩蔷钾一 ( 2 ，) 其中，c 。可以是个输入值或是理论上的最大值，或是到当前所有代或最近 k 代中g ( x ) 的最大值，此时c 。随着进化代数会有变化。对于最大化问题，一般采用 下述方法； 删= p 吖专，豁枷“ ( 2 - 8 ) 其中，c 。既可以是特定的输入值，也可以是当前所有代或最近k 代中g ( 砷的最 小值。 遗传操作：标准遗传算法的操作一般都包括选择( s e l e c t i o n ，或复制 r e p r o d u c t i o n ) 、交叉( c r o s s o v e r ，或重组r e c o m b i n a t i o n ) 和变异( m u t a t i o n ) 三种基 本形式，他们构成了遗传算法的核心，是模拟自然选择以及遗传过程中发生的繁殖、 1 0 天津大学硕士学位论文 第二章智能优化算法简介 交叉和突变现象的载体。 选择：即从当前群体中选择适应值高的个体以生成交配池( m a t i n gp 0 0 1 ) 的过 程。目前，主要有适应值比例选择( f i t n e s s - p r o p o r t i o n a t es e l e c t i o n ) 、b o t l z m a n 选择， 排序选择( r a n ks e l e c t i o n ) 、联赛选择( m u r n a m e n ts e l e c t i o n ) 等形式。为了防止由于 选择误差，或者交叉和变异的破坏作用而导致当前群体的最佳个体在下一代的丢失， d cj o n g 提出了精英选择( e l i t i s t s e l e c t i o n 。o r e l i t i s m ) 策略，另外，在机器学习等领 域中，h o l l a n d 等专家提出了稳态选择方法( s t e a d y s t a t es e l e c t i o n ) 1 舢- 1 9 。 交叉：是进化算法中遗传算法具备的原始性的独有特征。g a 交叉算子是模仿自 然界有性繁殖的基因重组过程，其作用在于将原有的优良基因遗传给下一代个体， 并生成包含更复杂基因结构的新个体。通常使用的交叉方式有一点交叉、两点交叉、 多点交叉、一致交叉等几种形式。交叉操作一般分为以下几个步骤： 从交配池中随机取出要交配的一对个体； 根据染色体长度l ，对要交配的一对个体，随机选取 1 ，l - 1 中一个或多个基因 位置作为交叉点。 根据交叉概率以( o s p 。1 ) 进行交叉操作，配对个体在交叉点处相互交换各自 的部分内容，从而形成颓的一对个体。 变异：模拟自然界生物进化中染色体上某位基因发生的突变现象，从而改变染 色体的结构和物理性状。在遗传算法中，变异算子通过按照变异概率随机反转某 位等位基因的二进制字符值来实现。对于给定的染色体位串s = q a ：吼新个体 ，= a 。a ：口：。的具体产生过程如下： d ( p 卅= 1 。：薪a i e 1 ，2 ，l ) ( 2 9 ) 其中，x r 【o 。1 】，是对应于每一个基因位产生的均匀随机变量。为了保证个体 变异后不会与其父体产生太大的差异，变异概率一般取值较小，以保证种群发展的 稳定。 在进化的整个过程中，交叉操作是主要的基因重组和群体更迭的手段，变异操 作的作用是第二位的，变异算子仅仅充当背景性的角色( b a c k 铲o l l n dr o l e ) 。针对具 体问题以及为了便于对进化过程实施控制，在标准变异算子的基础上，又引入了其 他类型的变异算子，比如：特定有效位变异、变异概率自适应调整、面向领域知识 的位变异等，使得遗传算法的应用范围和应用效果得到较好的改善。 群体设定以及终止循环的条件 根据模式定理。群体规模对遗传算法的性能影响很大种群规摸越大，遗传算 天津大学硕士学位论文第二章智能优化算法简介 子所处理的模式就越多，算法陷入局部解的危险性就越小，因此，从保持种群的多 样性以防止陷入局部解的角度考虑，种群规模应较大。但是，种群过大会带来相应 的问题。一方面，种群越大，个体的适应度评价计算量也会随之增加，从而影响算 法的效率；另一方面，种群过大，随着进化代数的增加，会使少量适应度很高的个 体被大量地复制而生存下来，而大多数个体被淘汰，从而影响个体的竞争。对此问 题，已有一些学者进行了较深入的研究和分析，并得出了一些初步理论分析结果， g o l d b e r g 证明了使用二值编码的遗传算法时，群体中最优个体数目与编码的字符编 码长度的关系，但在大多数情况下，种群规模的大小是很难进行计算，从理论上讲 不同的解题过程应该有不同的最佳种群规模 2 0 l 。 关于g a 迭代过程如何终止，般采用设定最大代数的方法。首先该方法简单易 行但不准确；其次，可以根据群体的收敛程度来判断，通过计算种群中的基因多样 性测度，即所有基因位的相似性程度来进行控制；第三，根据算法的离线性能和在 线性能的变化判定；最后，在采用精英保留选择策略的情况下，按每代最佳个体的 适应值的变化情况确定。 综上所述，标准遗传算法的基本流程如图2 - 1 所示； l 染色体解码 2 ) 计算目标函数值 3 ) 函数值向适应值映射 4 、适应值调整 三个基本算子： 1 选择算子 2 交叉算子 3 变异算子 其他高级算子 确定实际问题参数集 对参数集进行编码 初始化群体p ( 0 评价群体 y e s 塑足停止堡：= 叫丝塞，l in o 遗传操作 图2 - 1 标准遗传算法的基本流程 天津大学硕士学位论文 第二章智能优化算法简介 2 2 3