毕业论文外文翻译扩展的粒子群算法与经典优化算法的比较： 一个关于静止同步补偿器放置问题的案例研究

1、 本科毕业设计（论文）外文翻译译文 题 目： 扩展粒子群算法与经典 算法的比较 学生姓名： 院 （系）： 理学院 专业班级： 指导教师： 完成时间： 文献名称（中文） 扩展的粒子群算法与经典优化算法的比较： 一个关于静止同步补偿器放置问题的案例研究 文献名称（外文） Comparison of Enhanced-PSO and Classical Optimization Methods: a case study for STATCOM placement Yamille 哈利和罗纳德德尔 起止页码：1-31 出版日期（期刊号）：2013,7,13 出版单位：中国科学出版社概要这篇论文证实了

2、一种扩展的粒子群优化算法用于一个动力系统中解决柔性交流输电系统设备的优化配置问题的有效性。在进行关于静止同步补偿器设备优化配置的一项简单且符合实际的案例研究中，就稳态和经济指标而言，粒子群优化算法的性能可以和经典优化算法相比较。这篇论文也谈及了在文章中易于被忽视的概念和细节，因为优化算法的选择在很大程度依赖于这些概念和细节。关键词：柔性交流输电系统，经典优化，奔德斯分解，分支定界，进化，计算技术，粒子群优化、简介柔性交流输电系统的优化配置概念还处在一个相对早期的调查阶段。目前还没有一个被普遍接受的方法，许多研究人员都声称他们的方法比其他人的方法更好。鉴于在这个领域中不同方法之间的一个比较，特别

3、是在经典方法和准启发式方法之间，判断哪一种方法性能最好已经变得很困难，因为每一种研究方法集中于不同的问题方程、系统规模大小以及操作条件。这篇论文为经典算法和准启发式算法的性能比较提供了一个共同的背景。特别是在奔德斯分解算法，分支定界算法(B&B)和扩展的粒子群优化算法，而粒子群优化方法被证实比其它的准启发式技术更加有效。一项基于稳态和经济指标的简单且符合实际的优化静止同步补偿器配置(一种柔性交流输电系统设备)的案例研究被用来作为一个诠释的例子它更重要的表明这篇论文不是为了寻找某种特定问题的一种解决办法，而是为了阐述古典确定性方法和准启发式技术之间的差别以及对在文章中易于被忽视的优化过程

4、的重要细节作出评论：离散优化问题，理解性凸性假设条件下(不仅仅应用于目标函数),关于局部最优与全局最优问题的探讨(一种给定的目标函数)。这篇论文接下来的部分如下：优化背景(第二部分)，不应该被忽视的概念和问题(第三部分)，问题描述(第四部分)，优化算法(第五部分)，模拟结果(第六部分)，结束性评语(第七部分)。、背 景优化技术常被用来解决能够主要被分成两组的柔性交流输电系统设备的优化配置问题：组成了主要的进化计算技术的经典方法和准启发式算法，第三种可选择的方法，例如模态方法也可以考虑。然而，这些方法主要是基于技术的可行性而不是去寻找最优化解决办法。A、经典优化技术在论文中，这个问题应用了两类经

5、典优化方法：(1)混合型整数线性规划和(2)混合型非整数线性规划。一方面，混合型整数线性规划就像名称所说的那样需要的条件就是所有的变量是整数。这样，这种方法只能和直流功率流结合在一起使用。解决混合型线性整数方程问题的主要算法是奔德斯分解算法，分支定界法和格莫瑞流割算法。另一方面，混合型非线性整数方程需要考虑到目标函数和约束条件的使用。这样，交流功率流就可以用于这个案例。解决混合型非整数线性规划问题被利用的最为广泛的算法是奔德斯算法。不幸的是，依赖系统参数的问题的规模和非凸性是可能引起收敛问题的关键。B、准启发式技术计算技能的基础技术，例如遗传学算法(GA)、粒子群优化算法(PSO)、模拟退火算

6、法(SA)、禁忌搜索算法(TS)和进化规划算法(EP)都是可以选择用来解决优化问题的方法。候选解决方案在一定人口的个体中起着重要作用，最佳费用函数决定了解的存在条件。人类进化就发生了，经过生物和社会运营商的反复应用，就取得了最佳方案 通常，欧洲学分转换系统很适合解决混合型非整数线性规划，然而这些方法的可扩 展性需要进一步的验证。、优化方法：概念和问题A、离散优化问题一种常见的错误观念就是从优化的角度来说柔性交流输电系统设备的优化配置问题并不具有挑战性，因为这是一个离线问题。一些人认为这个解决方案就像同时安排一定数量的计算机并让它们运行一样简单。成功的关键在于找到所有可能的解决方案，那么最优方案

7、肯定在已找到的方案中取得。事实是甚至当一种解决办法在理论上可能对任何一个系统起作用时，而在实践 中随着系统规模的扩大和目标函数变得更加复杂(瞬态性能是评价计算密集型的)，找到问题的解决方案所需要的计算量会增加得非常迅速。如果也需要满足 N-1 或 N-2的可能性规则，或者增加系统的随机因素和不确定性因素，仅仅评估案例的数量也会变得难以估量。因此，对应用到系统规划问题中的优化算法进行研究，例如柔性交流输电系统的配置问题就变得非常重要。B、凸性假设 就目标函数而言，凸性是被主要分析的概念：如果目标函数是严格凸的，那么就可以确保有一个唯一最优解。 图 3-1 全局极值与局部极值 这一特点是可取的，但

8、是在动力系统中几乎就没有发生。大多数情况下，目标函数的图形类似于图形(3-1.b)中的函数。结果是梯度下降法往往受到局部极值的限制。在这些 情形下，必须考虑到采用往搜索算法中加入随机因素的特殊办法。 凸性假设问题也可应用到可行域中。例如在线性规划问题中，如果可行域就像下图3-2.a(图形 3-2.b 与图形 3-2.a 作为对比)中一样是凸集，那么就可以找到最优解(用单纯形法或者内点法)。 图 3-2 可 行 域 的 凸 性 最糟糕的情况出现在图 3-2.c 中，在图 3-2.c 中，可行域由有上下界的决策变量所确 定的有限区域的几个分散的白色小区域组成 。分别为变量和变量 :(黑色区域) 把

9、技术约束问题强加到动力系统中时，论文后面所展示的图形类型很具有代表性 。在这种情形下，优化算法应该有有效的效益勘探机制 ，以便能够快速找到可行方案 。因此，在不可行域中只耗费最小的计算量。C、全局优化另一个方面，在论文中容易被忽视的就是对全局变量和局部变量的探讨。与通常观点不同的是，这个主题跟应用到动力系统中的不同目标函数中的值并没有关系。文中指出对于一个给定的目标函数问题可能有唯一的最优解，这样局部最优解也是全局最优解(图 3-1.a)或者这个问题也有多个局部最优解和一个全局最优解。在后者图 3-1.b 中第一个白色星号表示 a 到 b 区间上的最小值，第二个白色星号表示b 到c 区间上的最

10、小值。黑色星号表示在整个 a 到 d 区间上的全局最小值。这样看来似乎前面介绍的概念都是多余的，然而，一旦一种优化算法能够提供了一个解决方案，但在通常情况下，都不能保证这种优化算法的性能。证实全局最优解能够取得仅仅是在线性规划问题这种特殊的条件下。就混合型非整数线性规划问题而言，如果没有局部极值条件的限制，能够找出全局最优解的每一种算法的性能需要分别加以研究。 、问 题 描 述需要解决的问题由一个 45 路公交系统中大量卫星部件的优化配置(车牌号)和额定功率(机械震荡分析)组成。而这些问题只是巴西电网中的一部分(图 4-1)。 图 4-1 在巴西电力系统中 45 路公共汽车部分路线图 主要目标

11、是在电力系统中以最低费用使得母线电压偏差最小化，选择这个客观标准和特殊的电力系统的原因是：(1)电力系统不是很大，因此进行详细地搜索能够找到全局最优解。(2)问题有一个减少的、分散的和非凸性可行域。(3)如果瞬态分析也包括在内的话，稳态标准仅仅被用来避免不符合要求的点。A、目标函数考察两个目标：(1)使在系统中的电压偏差最小。(2)使费用最低。这样在(4-1)和(4-3)中定义两个变量 J1和 J 2 . 在(4-1)中 J1是电压偏差的度量指标。在总线 k 中，在(4-1)中 J1 是电压偏差的度量指标在总线 k 中是各个电压值，N 是总线数目。 总费用函数 由两个部分组成：在系统中被组装的

12、每个部件的固定费用和与每个 部件大小相关的线性函数形成的可变费用。 （4-2） 在(4-2)中， M 表示待分配部件的数目， C f 是每个部件的固定费用Cv 是每次机器运行的费用。 由于 C f >>Cv , 在目标函数中，能够很方便地将最佳费用函数的每个术语规范化。 （3） 在(4-3)中， J 2是费用度量单位， M max 是待配置卫星部件的最大数目。 多元目标优化问题现在能够使用由度量 J1 和 J 2 的加权和组成的总的目标函数 J 来定义。如(4-4)中 （4） 每个度量的权值被调整用来反映每个目标的相对重要性。考虑到 J1 和 J 2 的最大量级，指定权值 w1 和

13、 w2 的值分别为1 , 0.5, 以便两个变量有相同的重要性。B、决策变量决策变量是静止同步补偿器部件和它的大小的参数 ，这些变量被放在如下的一个向量当中： （5） 在(4-5)中，ë p (其中 p=1.M )是静止同步补偿器部件 p 的参数，决策变量的每个分量都是整数， xi Z2 M .C、约束性在这个问题中，关于电力系统的特点和所需的电压档有几个约束性条件。在这种特殊条件下，在搜索区间中都有一个对应的约束性条件。因为发电机总线有稳压器调节电压，所以省略了它们的搜索过程。 (1) 总线数目被限制在1, 2, 3.N .(2) 只有一个部件可以在每个总线连接。 (3) 部件的数

14、目：1 M 5 . (4) 每个部件的大小： 0ç p 250MVA . (5) 所需的电压档需要另外 N 个定义的限制性条件： 0.95 Vk 1.05 不满足上述约束条件的每一种解决方案都被认为是不可行 V. 优化算法在一个45型总线系统中，对于大量柔性输电系统部件的最优化配置，充分发展了三种算法，把他们进行比较有：奔德斯分解算法、分支定界法、 扩展的粒子群优化算法。A、奔德斯分解算法这个方法分别由两个连续阶段的两套决策组成。在第一个决策阶段，延迟的一些约束条件被用来减少原(主)问题的复杂性；在第二个阶段，在找到第一个决策变量后 ，影响有不确定初始值的决策变量的一些参数是已知的和

15、固定的。这样，第二个问题就是如何减少复杂性和变量的数目。就静止同步补偿器配置问题而言 ，主要问题是考虑可分别由寻找最优解的位置的子向量和最优解大小的子向量组成的决策向量。不同的约束性条件被描述如下：(1)第一阶段：静止同步补偿器受到了延迟约束，无功率的限制放宽了这些设备的电源解决方案流 。每个STATCOM的控制器的参考电压值被设置为1.0标幺值 ，目标函数对应的电压偏差度量定义如(4-1)所示。(2)第二阶段：为了确定设备的位置 ，约束集仅被局限于取每个部件大小的最大值，目标函数包括了如(4-4)所示的电压偏差度量和成本度量。B、分支定界法分支定解法是一种通过评估所有可能解的子集来寻找一个最

16、优解决方案的经典算法。算法的主要步骤如182122：(1)分支：可行方案集被分割成更简单的子集。在每一次迭代中，选择最可能的一个子集，并作出努力内找到它的最佳可行的解决方案.(2)定界：该算法所得最优目标值的上限和下限，在每个阶段只有一个上限u，对应的目标值之间的所有可行的解决方案已经出现第一次最小值。 (3)修剪：如果在某个阶段，出现了子集中的一个下界比当前上界更大的集，那么就在算法中修剪(丢弃)这个集。分支、定界、修剪这些步骤重复进行，直到找到了最优解。对于这个特殊问题，目标函数作了如(4-4)中的定义，分支策略与深度优先搜索相对应：对于可行位置的每个子集，将分支进行分割成更小的子区间以逐

17、步确定静止同步补偿器的大小间隔。通过丢弃尽可能多的子区间，分支法和定界法有利于减少搜索次数，直到取得最优解。为了找到可行位置的特定子集，在下一个阶段，选择另一个可行位置的子集。重复这个过程直到包括了所有的可行位置。C、扩展的粒子群算法 (1) 典型粒子群算法的制定粒子群算法认为每一个粒子都代表问题的一种潜在解决方案，这样，粒子就如(4-5)所定义的那样。通过使用如(4-4)所定义的适当函数来评估使得每一个粒子和群的最佳位置待定的解决方案的性能。在迭代过程中，每一个粒子的位置都是由(5-1)、(5-2)所确定。 (7) 每个粒子的速度取决于个体和群体的关系。 (8)在(5-2)中，wi 是0到1

18、之间的正数，c1和 c2 分别是认知和社会加速常数，rand1和 rand 2分别是0到1之间均匀分布的随机数。最后， pi 是被找到的跟粒子相关的个 体的最佳位置，在粒子群中， pg 是被找到的全局最佳位置。 为了避免群之间的差异性，对于超空间问题的每一维数的一个最大速度被定义为 vmax .此外 ，尽管优化问题中包括了 整数变量 ，还是使用了 整数型粒子群优化算法 里粒子的位置被四舍五入到最接近的整数22。 表5-1 粒子群算法参数参数最优化解惯性常数( wi )线性递减(0.9 到 0.1)个别加速常数( c1 )2.5社会加速常数( c2 )1.5vmax 是总线位置9vmax 是静止

19、同步补偿器的大小50 (2) 扩展的粒子群算法为了某种特别应用，在前部分，被描述的典型粒子群优化算法通过扩展以促进问题的多维空间的搜索1。在每一个个体中，额外的逻辑都是由以下规则定义的：(1) 如果相关粒子的最佳位置和群的最佳位置都是可行的解决方案 ，那么可以按照(5-2)所示更新执行速度。(2) 如果还没有找到粒子的一种解决方案，那么最好依赖社会知识 。执行速度的更新方程代入： (9) 在这里， c 是一个单一的加速常数： c=c1 +c2 , rand 是一个0到1之间均匀分布的随机数。(1)如果没有找到任何一个粒子的可行方案( gbest 和 pbest 的值都是不可行的)，那么每个粒子

20、的速度就可以通过使用如图(10)所表示的最大速度的随机值来更新。 (10) 在(5-4)中， rh 是一个0到1之间均匀分布的随机数， vmax (h) 是 h 维问题超空间中的最大速度。 、模拟结果A、 穷举搜索 为了确定全局最优解，在图4-1中对于每一个案件通过运行功率流解决方案来进行穷举搜索以解决电力系统 M 型静止同步补偿器的最优化配置问题。解决方案表明需要满足在区域IV-C中的约束性条件的设备数目是两个，并且计算量对应37196250功率流。这个问题的可行区域被缩小了，而且变成分散和非凸性区域 。由于整个可行区域超过了三维空间，所以不可能画出整个可行域。然而为了说明用途，图6-1表明

21、就算是在最好的情况下 ，也要考虑总线的所有可能位置以及对于250 MVA的静止同步补偿器的每一个部件大小的最大值。 图6-1 1号部件的位置总线数目 超过问题多维空间的可行域(白色区域)图6-1. 就总的案例数而言，图6-2表明了可行域占有的百分比。 图6-2 (a)可行位置占所有可能组合的百分比 (b)可行解决方案占所有问题的多维空间的百分比 图6-3 电压档和静止同步补偿器部件 在设备被优化配置以后，所有的电压都是在上下5%的预定偏差范围。此外，电压偏差度量 J1 .B、经典算法与启发式算法表二概括了经典算法与扩展的粒子群的整体性能数据。为了评估每一种算法的性能，所考虑到的参数都是有利于找

22、到算法的全局最优解和它所需要的计算量。 表6-1 算法的性能 45号总线系统参数奔德斯算法分支定界法扩展的粒子群算法总线 1 大小 1(伏安)(378, 75)(378, 67)(378, 75)总线 2 大小 2(伏安)(433, 92)(430, 150)(433, 92)目标函数值0.91741.01700.9174电压偏差度量0.18240.18190.1824时间(秒)18.611846666功率流63.0952,1152,000 鉴于这些算法能够找到最优解，扩展的粒子群算法和奔德斯算法能够找到全局最优解。另一方面，分支定界仅局限于用来寻找局部最小值。就计算量而言，奔德斯分解算法的函

23、数评估适合值是扩展的粒子群算法的31.5倍。随着计算时间的增加，然而，这些算法仅仅是穷举算法所需要的总的计算量的一小部分，子群算法分别是0.17%、0.005%.、结 论论文把应用到电力系统中的柔性交流输电系统的最优化配置问题的三种优化算法进行了对比：奔德斯分解算法、分支定界算法和启发式技术的粒子群算法，而且这些算法被证实比解决这一类型问题的其它进化计算技术更加有效。文中着重强调了易于被忽视的优化过程的各个方面：可行域的收敛性问题：为了某种应用，减少了可行域的范围，并使得可行域变得分散和非凸性。因此，在文中特别考虑了优化算法的搜索能力。全局最优化：直到现在还未能证实利用启发式算法能够寻求最优解

24、，为了对正在考虑中的最优化静止同步补偿器配置问题的稳态和经济指标进行研究，论文通过使用简单且符合实际的案例对这个方面进行了分析。为了找到这个问题的全局最优解，文中对45型总线系统使用了穷举算法，因此，利用不同优化算法获得的结果的性能可以被评估。经典算法和启发式算法：就这些算法寻找最优解和它们的计算量的性能而言，经典算法、奔德斯分解算法以及分支定界法都可以和扩展的粒子群算法相媲美。奔德斯分解算法和扩展的粒子群算法能够寻找最优解，然而分支定界法仅局限于寻找一个局部最优点。跟以上所有的算法比起来，功率流的计算量比较小(穷举搜索算法比起来)，但是由于奔德斯分解算法比扩展的粒子群算法多花费30.5%的计

25、算量，因此，将它们进行比较肯定有利于启发式算法。前面的结果验证了扩展的粒子群算法在用于一个电力系统中解决柔性交流输电系统设备的优化配置这类特殊问题有效性。然而，最后的结论是到目前还没有普遍适用于其它情形的优化算法。算法的选择依赖于所要研究的问题，在当对于某种特殊问题选择一种优化算法时，这篇论文对应该考虑的不同方面作出了特别的努力。AbstractThis paper validates the effectiveness of an enhanced particle swarm optimizer (Enhanced-PSO) method in solving the problem of

26、 optimal allocation of FACTS devices in a power system. The performance of the Enhanced-PSO method is compared with classical optimization approaches using a simple but realistic case study of optimal allocation of STATCOM devices, considering steady state and economic criteria. This paper also disc

27、usses the concepts and details about the optimization process that tend to be overlooked in the literature since the selection of an optimization algorithm highly depends on them.Index Terms FACTS devices, classical optimization, Bendersdecomposition, branch and bound, evolutionary computation techn

28、iques, particle swarm optimization.I. INTRODUCTION THE topic of optimal allocation of FACTS (Flexible AC Transmission System) devices is still in a relatively early stage of investigation. Currently, there is no widelyaccepted method and many researchers claim their methods to be “better” than other

29、s. Considering the present state-of-the-art in this area, a comparison of different methods, particularly between classical and metaheuristic approaches, has been difficult because each study focuses on different problem formulations, system sizes and operating conditions. This paper provides a comm

30、on background for comparing the performance of classical and metaheuristic optimization algorithms. In particular between Benders decomposition and Branch-and-bound (B&B) and the Enhanced-PSO method, which has been proven to be more effective than other metaheuristic optimization techniques 1. A

31、 simple but realistic case study of optimal STATCOM allocation (a type of FACTS device), based on steady state and economic criteria, is used as an illustrative example. It is important to note that the focus of this paper is not to find a solution to the particular problem, but rather to illustrate

32、 the differences between classical deterministic approaches and metaheuristic techniques and to comment on important details about the optimization process that tend to be overlooked in the literature: optimization of offline problems, understanding convexity assumptions (that do not apply only to t

33、he objective function), and the discussion about local versus global optimality (for a given objective function).The following sections of this paper provide: an optimization background (section II), concepts and issues that should not be disregarded (section III), a problem description(section IV),

34、 optimization algorithms (section V), simulation results (section VI), and concluding remarks (section VII).II. BACKGROUNDThe optimization techniques used to solve the optimal allocation of FACTS devices can be decomposed into two primary groups: classical approaches and metaheuristicalgorithms, con

35、sisting of mainly evolutionary computation techniques (ECTs). A third group of alternative methods, such as modal analysis, may also be considered. However, these methods are primarily based on technical feasibility rather than on finding optimal solutions.A. Classical Optimization Techniques In the

36、 literature, two classes of classical optimization methodologies have been ap-plied to this problem: (i) Mixed Integer Linear Programming (MILP) 2-4 and (ii) Mixed Integer Non-Linear Programming (MINLP) 5-7. On the one hand, the MILP formulation, as the name indicates, requires the relation -ships b

37、etween all variables to be linear. Thus, this approach can be only used togther with DC power flow only. The main algorithms for solving the MILP problem are Benders Decomposition 2, Branch and Bound (B&B), and Gomory cuts 3, 4. On the other hand, the MINLP formulation allows for the use of a no

38、n-linear objective function and constraints, thus, AC power flow can be used in this case. The algorithm most widely utilized for solving the MINLP problem is Benders Decomposition 5- 7. Unfortunately, the size and non-convexity of the problem, which depend on the system parameters, are critical iss

39、ues that may cause convergence problems.B. Metaheuristic Techniques Computational intelligence based techniques, such as Genetic Algorithm (GA)5,6, 8-11, Particle Swarm Optimization (PSO) 12-14, Simulated Annealing (SA) 8, 15, Tabu Search (TS) 14, 15, and Evolutionary Programming (EP)16,17,are alter

40、native methods for solving complex optimization problems. Candidate solutions play the role of individuals in a population and the cost function determines the environment where the solutions exist. Evolution of the population then takes place and, after the repeated application of biological orsoci

41、al operators, the optimal solution is reached. In general ECTs perform well in MINLP problems.However the scalability of these methods requires further investigation. III. OPTIMIZATION: CONCEPTS AND ISSUESA. Optimization of offline problemsA common misperception is the belief that the problem of opt

42、imal allocation of FACTS devices is not challenging from the optimization perspective because it is an offline problem. Some presume that the solution is as simple as arranging a number of computers in parallel and letting them run, for as long as it takes , until all possible solutions are found an

43、d the best one selected among them. The fact is that, even when this approach is theoretically possible to perform for any system, in practice the number of calculations required to find the solutions to the problem can grow extremely fast as the size of the system increases and the objective functi

44、on becomes more sophisticated (evaluation of transient performance is computationally intensive). If it is also required to satisfy the N-1 or N-2 contingency criteria, or add stochastic components and uncertainties to the system , the number of cases to evaluate simply becomes uncountable. Therefor

45、e, the study of optimization algorithms applied to system planning problems, such as the problem of FACTS allocation is not trivial.B. Convexity assumptions The concept of convexity is mostly analyzed in the case of the objective function: if the function is strictly convex a unique optimal solution

46、 is guaranteed (Fig. 1.a).f(x) (a) g(x) (b) a b a c d Fig. 1: Global versus local minima This characteristic is most desirable but it rarely occurs in power system problems. Most of the time the plot of the objective function resembles the function in Fig. 1.b. As a result, gradient descent algorith

47、ms are prone to getting trapped in local valleys (local minima). In these cases, special mechanisms , such as injecting randomness to the search, must be considered. The convexity assumption also applies to the feasible region. For example, in the case of linear programming problems, the optimum can

48、 be found (either by simplexmethod or interior point method) if the feasible region is a convex set , as shown in Fig. 2.a (as opposed to Fig, 2.b) 18.var2 var2 var2(A) (B) (C) Var1 var1 var1 Fig. 2: Convexity of the feasible region A worst case is presented in Fig. 2.c. where the feasible region co

49、nsists of several small areas (white) scattered among the area limited by the upper and lower bounds of the decision variables, var1 and var2 (black area). This type of feasible region , as shown later in the paper , is typical when technical constraints are imposed in the power system . The optimization algorithms in this case should have effi