1、 基于改进离散粒子群算法的机组组合优化 方法 0 引言 实际的日常生活中或在处理工程问题的过程中，人们经常遇到在某个问题有多个解决方案可供选择的情况下，如何根据自身所提出的某些性能的要求，从多个可供选择的方案中选择一个可行方案，使所要求的性能指标达到最大或最小，这就是优化问题 1。如工程设计中怎样选择参数，使得设计即满足要求又能降低成本 ;资源分配中，怎样的分配方案既能满足各个方面的基本要求，又能获得好的经济效益等。 优化是个古老的课题， 早在 17世纪，英国 Newton 和德国 Leibnitz创立的微积分就蕴含了优化的内容。而法国数学家 Cauchy 则首次采用梯度下降法解决无约束优化问
2、题，后来针对约束优化问题又提出了 Lagrange 乘数法。人们关于优化问题的研究工作，随着历史的发展不断深入，优化理论和算法迅速发展形成一门新的学科。二十世纪八十年代以来，一些新颖的优化算法得到了迅速发展。人工神经网络 (ANN)在一定程度上模拟了人脑的组织结构 2-4;遗传算法 (GA)借鉴了自然界优胜劣汰的进化思想 5, 6;蚁群优化算法 (ACO)受启发于自然界蚂蚁的寻径方式 7;模拟退火 (SA)思路源于物理学中固体物质的退火过程 8, 9;禁忌搜索 (TS)模拟了人类有记忆过程的智力过程 。 这些算法有个共同点 :都是通过模拟或揭示某些自然界的现象和过程得到发展，在优化领域，有人称
3、之为智能优化算法 (Intelligent Optimization Algorithms)。 本文研究的粒子群优化算法 （ Particle Swarm Optimization， PSO），是在 1995年由美国社会心理学家 Kennedy 和电气工程师 Eberhart共同提出的 10-12，其基本思想是受他们早期对鸟类群体行为研究结果的启发，并利用了生物学家 Frank Heppner 的生物群体 模型 。 PSO 算法从诞生起，就引起了国内外学者的广泛关注，并掀起了该方法的研究热潮，并在短短几年时间里涌现出大量的研究成果，己经在函数优化、神经网络设计、分类、模式识别、信号处理、机器人
4、技术等应用领域取得了成功应用。该算法目前己被“国际演化计算会议”(Conference of Evolutionary Computation， CEC)列为讨论专题之一。 PSO 算法在电力系统中的应用研究起步较晚，最近几年它在电力系统领域中逐渐显示出广阔的应用前景，己开始引起电力科学工作者的关注和研究兴趣。如何充分发挥 PSO 算法的优势来解决电力系统的有关难题，已成为一个新的研究热点。 1 优化算法基础 1.1 最优化问题 最优化问题是寻找最小值（最大值问题 可转化为需求最小值）的问题。最优化问题根据其目标函数、约束函数的性质以及优化变量的取值等可以分成许多类型，每一种类型的最优化问题根
5、据其性质的不同都有其特定的求解方法。不失一般性，最小化问题可定义为 : m i n ( ). . | ( ) 0 , 1 , 2 , , tfXs t X S X g X i m （ 1.1） 其中， ()fX为目标函数， ()tgX为约束函数， S 为约束域， X 为 n 维优化变量。通常，对 ( ) 0tgX 的 的约束和等式约束可转换 ( ) 0tgX的约束。 当 ()fX， ()tgX为线性函数，且 0X 时，上述最优化问题即为线性规划问题，其求解方法有成熟的单纯形法和 Karmarc 方法。 当 ()fX， ()tgX中至少有一个函数为非线性函数时，上述问题即为非线性规划问题。非线性
6、规划问题相当复杂，其求解方法多种多样，但到目前仍然没有一种有效的适合所有问题的方法。 当优化变量 X 仅取整数值时，上述问题即为整数规划问题，特别是当 X 仅能取 0 或 1时，上述问题即为 0-1整数规划问题。由于整数规划问题属于组合优化范畴，其计算量随变量维数的增长而指数增长，所以存在着“维数灾难”问题。 当 ( ) 0 , ( 1, 2 , , )g X i m )所限制的约束空间为整个 n 维欧式空间，即 nR 时，上述最优化问题为无约束优化问题。 非线性规划问题 (包括无约束优化问题和约束优化问题 )，由于函数的非线性，使得问题的求解变得十分困难，特别是当目标函数在约束域内存在多峰值
7、时。常见的求解非线性规划问题的优化方法，其求解结果与初值的选择关系很大，也就是说，一般的约束或无约束非线性优化方法均是求目标函数在约束域内的近似极值点，而非真正的最小点。总的说来，求最优解或近似最优解的方法主要有三种 :枚举法、启发式算法和搜索算法。 （ 1）枚举法。枚举出可行解空间内的所有可行解，以求出精确最优解。对于连续问题，该方法要求先对其进行离散化处理，这样就有可能产生离散误差而永远达不到最优解。另外，当枚举空间比较大时 ，该方法的求解效率比较低。 （ 2）启发式算法。寻求一种能产生可行解的启发式规则，以找到一个最优解或近似最优解。该方法的求解效率虽然比较高，但对每一个需要求解的问题都
8、必须找出其特有的启发式规则，这种启发式规则无通用性，不适用于其他问题。 （ 3）搜索算法。寻找一种搜索算法，该算法在可行解空间的一个子空间内进行搜索操作，以找到问题的最优解或近似最优解。该方法虽然保证不了一定能够得到问题的最优解，但若适当地利用一些启发知识，就可近似地使解的质量和求解效率达到一种较好的平衡。 搜索算法可分为两大类 :平行搜索法和序贯搜 索法。作平行搜索时，需要计算目标函数值的自变量节点位置在事先一起选定。而作序贯搜索法时则根据前一轮计算得到的目标函数值的情况用以确定下一轮计算目标函数值的自变量节点位置，因此它带有迭代性。搜索算法又可分确定性搜索法和随机性搜索法两种。确定性搜索算
9、法在寻优过程中，一个搜索点到另一个搜索点转移有确定的转移方法和转移关系，因而其过程可再现，其不足在于寻优结果与初值有关，初值选取不当往往有可能使搜索永远达不到最优点。随机性算法在算法执行过程中加入随机性 (因为真正理论意义下的随机数是不可能由计算机产生的，所以实际上用 的是伪随机数 )，需计算算法输出结果的概率平均值。随机算法往往比确定性算法计算时间少，但它的准确率略微降低。 1.2 局部优化算法 定义 1.1 如果存在 *BXB ，使得对 XB有： *( ) ( ),Bf X f X X B （ 1.2） 成立，其中 nB S R ， S 为由约束函数限定的搜索空 间，则称 *BX 为 ()
10、fX在 B 内的局部极小点， *()bfX 为局部极小值。 常见的优化方法大多为局部优化方法，都是从一个给定的初始点 0XS 开始，依据一定的方法寻找下一个使得目标函数得到改善的更好解，直至满足某种停止准则。成熟的局部优化方法很多，如 Newron-Raphson 法、共扼梯度法、 Fleteher-Reeves 法、 Polar-Ribiere 法、Davidon-Fleteher-Power(DFP)法、 Broyden-Fletcher-Goldfarb-Shsnn(BFGS)方法等，还有专门为求解最小二乘问题而发展的 Leven-berg-Marquardt(LM)算法。所有这些局部优
11、化算法都是针对无约束优化问题而提出的，而且对目标函数均有一定的解析性质要求，如 Newton-RaPhson法要求目标函数连续可微，同时要求其一阶导数连续。 1.3 全局优化算法 定义 1.2 如果存在 *XS ，使得对 XS有： *( ) ( ),f X f X X S （ 1.3） 成立，其中 nSR 为 由约束条件限定的搜索空间， 则称 *X 为 ()fX在 S 内的全局极小点，*()fX )为全局极小值 。 目前，全局优化问题也己存在许多算法，如填充函数法等，但比起局部优化问题的众多成熟方法，其间还有很大差距。另外，解析性优化方法对目标函数及约束域均有较强的解析性要求，对于诸如目标函数
12、不连续、 约束域不连通、目标函数难以用解析函数表达或者难以精确估计 (如仿真优化问题 )等问题时，解析确定性优化方法就难以适应。 为了可靠解决全局优化问题，人们试图离开解析确定性的优化算法研究，转而探讨对函数解析性质要求较低，甚至不做要求的随机型优化方法。最早的随机型优化方法是基于Monte-Carfo 方法的思想，针对具体问题性质的特点，构造以概率 1 收敛于全局最小点的随机搜索算法。真正有效且具有普遍适应性的随机全局优化方法，是近十多年来人们模拟自然界现象而发展起来的一系列仿生型智能优化算法，如禁忌搜索算法、模拟退火算法、 进化类算法、群体智能算法等。 1.4 没有免费午餐定理 1997年
13、在 IEEE Transaction on Evolution Computation 上， Wolpert和 Macready 发表了题为“ No Free Lunch Theorems for Optimization” 的论文，提出并严格论证了所谓的没有免费午餐定理 (No Free Lunch Theorems)，简称 NFL 定理 13。 NFL 定理的简单表述为 :对于所有可能的问题，任意结定两个算法 A、 B，如果 A 在某些问题上表现比 B 好 (差 )，那么 A 在其他问题上的表现就一定比 B 差 (好 )，也就是说，任意两个算法 A、 B对所有问题的平均表现度量是完全一样的
14、。该定理的结论是，由于对所有可能函数的相互补偿，最优化算法的性能是等价的。该定理只是定义在有限的搜索空间，对无限搜索空间结论是否成立尚不清楚。 在计算机上实现的搜索算 法都只能在有限的搜索空间实施，所以该定理对现存的所有算法都可直接使用 。 自从 NFL 定理提出以来，有关定理本身及其相关结论的争论在学术界一直 持续未断，因为 NFL 定理本身涉及到了优化算法最基本的问题，而且其结论多少有点出人意料。 NFL 定理的主要价值在于它对研究与应用优化算法时的观念性启示作用。虽然 NFL定理是在许多假设条件下得出的，但它仍然在很大程度上反映出了优化算法的本质。当我们所面对的是一个大的而且形式多样的适
15、应值函数类时，就必须考虑算法间所表现出的 NFL 效应，即若算法 A在某些函数上的表现超过算法 B，则在这类的其他适应值函数上，算法 B的表现就比 A要好。因此，对于整个函数类，不存在万能的最佳算法，所有算法在整个函数类上的平均表现度量是一样的。 因此，关于优化算法的研究目标就应该从寻找一个大的函数类上的优化算法转变为 : （ 1）以算法为导向，从算法到问题 :对于每一个算法，都有其适用和不适用的问题 ;给定一个算法，尽可能通过理论分析，给出其适用问题类的特征，使其成为一个“指示性”的算法。 （ 2）以问题为导向，从问题到算法 :对于一个小的特定的函数集，或者一个特定的实际问题，可以设计专门适
16、用的算法。 实际上，大多数在进化算法方面的研究工作可以看作是属于这一范畴的，因为它们主要是根据进化的原理设计新的算法，或者将现有算法进行部分改进，以期对若干特定的函数取得好的优化效果。 NFL 定理只是否定了去寻找一个万能的最佳算法的可能性，但对于某些小约函数集合， NFL 定理则认为存在一个在该集合上的好算法。 1.5 进化算法 近十余年来，遗传算法 (Genetic Algorithms， GA)、进化策略 (Evolutionary Strategies， ES)和进化规划 (Evolutionary Programming， EP)等进化类算法在理论和应用两方面发展迅速、效果显著，并逐
17、渐走向了融合，形成了一种新颖的模拟进化的计算理论，统称为 进化计算(Evolutionary Computation， EC)，进化计算的具体实现方法与形式称为进化算法 (Evolutionary Algorithm， EA)。进化算法是一种受生物进化论和遗传学等理论启发而形成的求解优化问题的随机算法，虽然出现了多个具有代表性的重要分支，但它们各自代表了进化计算的不同侧面，各具特点。 进化算法是模拟由个体组成的群体的集体学习过程，其中每个个体表示给定问题搜索空间中的一个点。进化算法从初始群体出发，通过选择、变异和重组过程，使群体进化到搜索空间中越来越好的区域。选择过程使群体中适应性好的个体比适
18、应性差的个体有更多的复制机会，重组算子将父辈信息结合在一起并将他们传到子代个体，变异在群体中引入了新的变种。 进化算法的两个主要特点是群体搜索策略及群体中个体之间的信息交换。它们的优越性主要表现在 :首先，进化算法在搜索过程中不容易陷入局部最优，即使在所定义的适应度函数是不连续的，非规则的或有噪声的情 况下，它们也可能以很大的概率找到全局最优解 ;其次，由于它们固有的并行性，进化算法非常适合于向量并行机 ;再者，进化算法采用自然进化机制来表现复杂的现象，能够快速可靠地解决非常困难的问题 ;此外，由于它们容易介入到已有的模型中并且具有可扩展性，以及易于同其他技术混合等因素，进化算法已经在最优化、
19、机器学习和并行处理等领域得到了越来越广泛的应用。 1.5.1遗传算法 遗传算法最早是由美国 Michgan 大学的 J.Holland 博士 1975提出的，经过学者不断地改进 ，使遗传算用于更广泛的领域。 从数学角度看，遗传算法是一 种随机搜索算法。从工程角度看，它是一种自适应的迭代寻优过程。它从某一随机产生的初始群体开始，按照一定的操作规则，如选择、复制、交叉、变异等等，不断地迭代计算，并根据每一个个体的适应度值，保留优良个体，淘汰劣质个体，引导搜索过程向最优解逼近。 构成简单遗传算法的要素主要有 :染色体编码、个体适应度评价、遗传算子以及遗传参数设置等等。 （ 1）染色体编码方法 在对一
20、个问题采用遗传算法进行求解之前，必须对问题的解空间进行编码，以便能够由遗传算法操作。常见的编码方法是二进制编码，使用固定长度的二进制符号串来表示群体中的 个体。求解结束后再通过解码变换成实变量。在编码和解码的过程中，参变量的精度不可避免会受到影响。因此，有人提出了基于实数编码的遗传算法，其基本原理与二进制编码相同，只是实数编码的染色体是由各个实参变量构成的向量，初始群体中各个个体的基因可用均匀分布的随机数来构成。 （ 2） 适应函数 在遗传算法中，遗传操作主要是通过适应函数的导向来实现。它是用来评估一个染色体相对于整个群体的优劣的相对值的大小。 （ 3） 遗传算子 基本遗传算法通常使用下述三种
21、遗传算子 ： 选择算子 :按照某种策略从父代中挑选个体进入中间代。 交叉算 子 :随机从群体中取两个个体，并按照某种交叉策略使两个个体互相交换 部分染色体码串，从而形成两个新的个体。 变异算子 :通常按照一定的概率，改变染色体中某些基因的值。 （ 4）遗传算法的运行参数 有以下四个运行参数需要提前设定 :群体大小 (N )，即群体中所含个体数量 ;终止迭代代数 (T )；交叉概率 ( cp )；变异概率 ( mp )。这四个参数对遗传算法的求解结果和求解效率都有很大的影响。因此，要合理设定这些参数，才能获得较好的效果。 1.5.2进化策略 进化策略 (Evolutionary Strategi
22、es， ES)由 I.Rechenberg和 H.P.Schwefel于 1964年为优化物体的形状参数而提出。因而其通常应用于实值优化问题。进化策略利用变异和重组操作，使搜索空间和策略参数空间的寻优同时进行。 早期进化策略的种群中只包含一个个体，而且只使用变异操作。在每一进化代，变异后的个体与父体进行比较再选择两者之优，该选择策略称之为 (1+1)策略。它使用的变异算子是基于正态分布的变异操作，这种进化策略称为 (1+1)进化策略或二元进化策略。 由于 (1+1)进化策略存在诸多弊端，如有时收敛不到全局最优解、效率较低等。它的改进即是增加种群内个体的数量，从而演化为 ( 1 )进化策略。此时
23、种群内含有 个个体，随机选择一个个体进行变异，然后取代群体中最差的个体。 ( 1 )进化策略与 (1+1)进化策略的相似之处是每次只产生一个后代。为进一步提高效率，后来又发展成为 ( )进化策略和 ( ,)进化策略，并且引进了重组操作。 ( )进化策略根据种群内的 个个体产生 个个体，然后将这 个个体进行比较再在其中选择声个 最优者。 ( ,)进化策略则是在新产生的 ( )个个体中选择 个最优者。 1.5.3进化规划 进化规划 (Evolutionary programming， EP)方法最初是由美国科学家 Lawrence J.Fogel等人在 20 世纪 60 年代提出的。它在求解连续参
24、数优化问题时与 ES 的区别很小。进化规划仅使用变异与选择算子，而绝对不使用任何重组算子。其变异算子与进化策略的变异相类似，也是对父代个体采用基于正态分布的变异操作进行变异，生成相同数量的子代个体。即 个父代个体总共产生 个子代个体。 EP 采用一种随机 竞争选择方法，从父代和子代的并集中选择出 2 个个体构成下一代群体。其选择过程如下 :对于由父代个体和子代个体组成的大小为 2 的临时群体中的每一个个体，从其他 21 个个体中随机等概率地选取出 q 个个体与其进行比较。在每次比较中，若该个体的适应值不次于与之比较的个体的适应值，则称该个体获得一次胜利。从 2 个个体中选择出获胜次数最多的产个
25、个体作为下一代群体。 1.6 群体智能 受社会昆虫行为的启发，智能自动化、智能计算等相关领域的研究工作者通过对其行为的模 拟，产生了一系列寻优问题求解的新思路，这些研究可被称为针对群体智能的研究。群体智能 (Swarm Intelligence)中的群体 (Swarm)是指“一组相互之间可以进行直接通信或者间接通信 (通过改变局部环境 )，并且能够合作进行分布问题求解的主体”。而所谓群体智能是指“无智能的主体通过合作表现出智能行为的特性”。这样，群体智能的协作性、分布性、鲁棒性和快速性的特点使之在没有集中控制，并且不提供全局模型的前提下，为寻找复杂的大规模分布问题的解决方案提供了基础。 群体智
26、能的优点可以描述如下 14： （ 1）群体中相互合作的个体是分布式的，这样的分布模式更适合于网络环境下的工作状态。 （ 2）系统没有集中的控制指令与数据存储，这样的系统更具有鲁棒性，不会由于某一个或者某几个个体的故障而影响整个问题的求解过程。 （ 3）系统不通过个体之间的直接通信，而通过非直接通信方式进行信息的传输与合作，这样的系统具有更好的可扩充性，由于系统中个体的增加而增加的通信开销也较小。 （ 4）系统中每个个体的能力十分简单，每个个体的执行时间也比较短，并且实现较为方便，具有简单性的特点。 2粒子群优化算法原理 2.1 粒子群优化算法的基本思想 PSO 算法就是由研究鸟类迁徙觅食的模型
27、得到的。在该模型中，群体中的每个个体有基于一定的内部信息和外部信息而控制自己行为的能力。具体说来，就是每个个体都有一定的感知能力，能够感知自己周围的局部最好位置的个体和整个群体的全局最好位置的个体存在，并根据当前的状态和所获得的信息，调整自己的下一步行为，从而整个群体表现出一定的智能性。在解决优化问题时，每个个体的所在位 置可被相应地看成一个潜在的解，按照上述规则，通过概率化地调整这些潜在解，经过反复迭代最终得到所需要的全局最优解。 2.2 原始粒子群优化算法原理 PSO 算法采用速度 位置搜索模型 。在 PSO 中，每个优化问题的潜在解都是搜索空间中的一只鸟，称之为“粒子”。所有的粒子都有一
28、个由被优化的函数决定的适应值，每个粒子还有一个速度决定他们飞翔的方向和距离。粒子们就追随当前的最优粒子在解空间中搜索。PSO 初始化为一群随机粒子 (随机解 )。然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个“极值”来更新自己。第一个就是粒子 本身所找到的最优解 bestP ，这个解称为“个体极值”。另一个极值是整个种群目前找到的最优解 bestG ，这个极值是“全局极值”。 粒子 i 的位置 为 12( , , , )i i i imX x x x ，速度为 12( , , , )i i i inV v v v ， 个体极值表示 为12( , , , )i i i imP p p
29、p ， 可以看作是粒子自己的飞行经验。全局极值 相应的 表示为12( , , , )g g g gnP p p p ，可以看作群体经验。粒子就是通过自己的群体经验来决定下一步的运动。 对于第 k+1次迭代，每一个粒子是按照下式进行变化的 ： 1 1 1 2 2( ) ( )k k k kid id id id gd idv v c r p x c r p x （ 2.1） 11k k kid id idx x v （ 2.2） 式中 ， 1,2, ,im ， m 是群体中粒子的总数 ； 1,2, ,dn ， n 为解空间的维数，即自变量的个数 ;加速因子 1c ， 2c 分别调节向 bestP
30、 和 bestG 方向飞行的最大步长，合适的 1c ， 2c 可以加快收敛且不易陷入局部最优。最大速度 maxV 决定了问题空间搜索的速度 ，粒子的每一维速度 idv 都会被限制在 max max , ddvv 之间 15。 由上式 (2.1)看出，速度更新公式由三部分组成。第一部分是粒子先前的速度，称为动量部分，表示粒子对当前自身运动状态的信任，为粒子提供了一个必要动量，使其依据自身速度进行惯性运动 ;第二部分是认知部分，表示粒子本身的思考，鼓励粒子飞向自身曾经发现的最优位置 ;第三部分为社会部分，表示粒子间的信息共享与合作，它引导粒子飞向粒子群中的最优位置。三个部分共同决定了粒子的空间搜索
31、能力，第一部分起到了平衡全局和局部搜索的能力 ;第二部分使粒子有了足够强的全局搜索能力，避免局部极小 ;第三部分体现了粒子间的信息共享。在这三部分的共同作用下粒子才 能有效的到达最好位置。粒子移动原理如图 2.1所示： 图 2.1粒子移动原理图 2.3标准粒子群优化算法原理 为了改善算法收敛性能， Shi和 Ebethart在 1998年的论文中引入了惯性权重的概念 ， 将速度和位置更新公式修改为如下所示 : 1 1 1 2 2( ) ( )k k k kid id id id gd idv wv c r p x c r p x （ 2.3） 11k k kid id idx x v （ 2.
32、4） 式中 w 称为惯性权重，其大小决定了对粒子当前速度继承的多少，合适的选择可以使粒子具有均衡的探索和开发能力。可见原始 PSO 算法是惯性权重 1w 的特殊情况。 初始时， Shi 将惯性权重取值为常数，但后来的试验发现，动态惯性权重能够获得比固定值更好的寻优结果。动态惯性权重可以在 PSO 搜索过程中线性变化，亦可根据 PSO 性能的某个测度函数而动态改变。目前，采用较多的惯性权重是 Shi 建议的线性递减权重策略，即 m a x m a x m in m a x() tw w w w T （ 3.5） 式中， maxT 为最大进化代数， maxw 为初始惯性权重， minw 为进化至最
33、大代数时的惯性权重。通常取 min 0.4w ， max 0.9w 。 目前，对于 PSO 算法的研究大多以带有惯性权重的 PSO 为对象进行分析、扩展和修正，因此大多数文献中将带有惯性权重的 PSO 算法称为标准 PSO 算法，而将前述 PSO 算法称为原始 PSO 算法。 2.4 标准粒子群优化算法流程 标准 PSO 算法的基本流程可以描述如下 : （ 1）在初始化范围内，对粒子群进行随机初始化，包括随机初始化位置和速度。 （ 2）计算每个粒子的适应值。 （ 3）对每个粒子，将其适应值与所经历过的最好位置的适应值进行比较，如果更好，则将其作为粒子的个体历史最优值，用当前位置更新个体历史最优
34、位置。 （ 4）对每个粒子，将其历史最优 适应值与群体内所经历的最好位置的适应值进行比较，若更好，则将其作为当前的全局最优位置。 （ 5）根据式 (2.3)、 (2.4)和 (2.5)对粒子的速度和位置进行更新。 （ 6）当终止条件满足时停止计算，否则返回步骤 (2)。一般将终止条件设定为一个足够好的适应值或达到一个预设的最大迭代代数。 标准 PSO 算法的流程图见图 2.2所示 ： 图 2.2标准粒子群优化算法流程图 2.5 粒子群优化算法的参数设置 PSO 算法中没有太多需要调节的参数，下面介绍有关几个参数的作用和设置，并给出经验值。 （ 1） 群体规模和粒子的维度 当群体规模很小的时候，
35、陷入局优的可能性很大。然而，群体规模过大将导致计算时间的大幅增加。并且当群体数目增长至一定水平时，再增长将不再有显著的作用。当群体规模为 1的时候， PSO 算法变为基于个体搜索的技术，一旦陷入局优，将不可能跳出。当群体规模很大时， PSO 的优化能力很好，可是收敛的速度将非常慢。一般来说群体规模不用取的太大，几十个粒子就足够用了，当然一些特殊问题可取的更多。如对多目标优化等比较难的问题，或者某些特定的问题，粒子数可以取到 100-200个。粒子度的大小，是由具体的优化问题所决定的，一般就是解空间 的维度。 （ 2） 惯性权重 惯性权重 w 是用来控制粒子以前速度对当前速度的影响，它将影响粒子
36、的全局和局部搜索能力。较大的 w 值有利于全局搜索，较小 w 有利于局部搜索。选择一个合适的 w 可以平衡全局和局部搜索能力，这样可以以较少的迭代次数找到最优解。实验发现 w 的值线性的从 1.4减少到 0要比用固定的好。这是因为算法以一个较大的惯性权重开始可以找到比较好的范围，后来用较小的惯性权重可以获得较好的局部搜索能力 16。另外，文献 17中分析了惯性权重和最大速度对 PSO 算法性能的影响，发现最大速度较小时惯性权重近似为 1 是个好的选择。当最大速度比较大时惯性权重为 0.8是个比较好的选择。一般来讲，对惯性权重 w 的设置可以是从 0.9线性减小到 0.2。 （ 3） 最大速度
37、最大速度决定粒子在一次迭代中最大的移动距离。最大速度较大，探索能力增强，但是粒子容易飞过最好解。最大速度较小时，开发能力增强，但是容易陷入局优 18。有分析和实验表明，设定最大速度的作用可以通过惯性权重的调整来实现。所以现在的实验基本上将最大速度设 定为每维变量的变化范围，而不必进行细致的选择与调节。 （ 4） 学习因子 学习因子 1c ， 2c 使粒子具有自我总结和向群体中优秀个体学习的能力，从而向群体内或邻域内最优点靠近。 1c ， 2c 通常等于 2，不过也有其他的取值。但是一般 12cc ，并且范围在 0和 4之间。有以下几种情况需要说明 : 120cc时，粒子将一直以先前的速度飞行，
38、直至问题空间的边界，因此只能搜索有限的区域，很难找到问题最优解。 当 1 0c 且 2 0c 时，粒子没有“认知”能力，在这种情况下，由于粒子间的相互作用，算法有能力到达新的搜索空间，且收敛速度更快，但是对复杂问题，更容易陷入局部最优。 当 1 0c 且 2 0c 时，粒子间没有社会信息共享。这时由于个体之间没有交互作用，一个规模为 m 的群体等价于 m 个粒子的单独运动，因而得到最优解的几率非常小。 （ 5） 停止准则 一般使用 最大迭代次数或可以接受的满意解作为停止准则。 （ 6） 令仔域定义 （ 拓扑结构 ） 全局版本 PSO 算法将整个群体作为粒子的邻域，速度快，不过有时会陷入局部最优
39、 ;局部版本 PSO 算法将索引号相近或者位置相近的个体作为粒子的邻域，收敛速度慢一点，不过很难陷入局部最优 。在实际应用中，可以先用全局 PSO 算法找到大致的 结果，再用局部PSO 算法进行搜索 。 3动态双种群粒子群算法与机组组合 电力系统机组组合问题是典型的大规模非线性混合整数规划问题，其优化目标是 :在满足系统负荷需求、旋转备用和发电机组运行技术要求等约束条件的情况下，合理地安排发电机组启停和各个时段中的机组出力，使整个系统的发电费用最小。本文提出了解决电力系统机组组合问题的动态双种群粒子群优化 (DDPSO)算法，以提高粒子群算法的全局搜索能力。采用二维实数矩阵对所要制定的发电计划
40、进行编码，从而无须将机组组合问题分解成两层优化问题进行求解。本文将该方法应用于实际算例中，与其他方法的比较结果表明 DDPSO 算法用于解决机组组合问题具有更好的收敛速度和更高的精度。 3.1 动态双种群粒子群优化算法 3.1.1粒子群优化算法的学习策略 由标准 PSO 算法可知，粒子通过跟踪自己迄今为止所找到的最优解和种群迄今为止所找到最优解这两个极值来更新自己的速度，从而更新自己的位置。这种行为也可以理解为，粒子在借鉴自身和整个群体所取得的 成功的经验，通过对以往的成功经验的学习获得有用的信息，指导自己下一步的行动策略。但人们也常说“失败乃成功之母”，“吃一堑，长一智”，可见从一些失败的尝
41、试中我们也可以获得有用的信息，基于这一点，提出了新的 PSO 算法学习策略，这就是从以往的失败中获得有价值的信息，使粒子远离粒子本身和整个群体所找到的最差的位置，从而更新粒子的速度和位置。粒子在搜索过程中的失败可以表现为搜索到的具有较差适应值的位置，记第 i 个粒子迄今为止搜索到的最差位置为 12( , , , )i i i ins s s s ，整个粒子群迄今为止搜索到的最差位置为 12( , , , )g g g gns s s s ， 则第 i 个粒子的速度和位置更新公式如下： 1 1 1 2 2( ) ( )k k k k k kid id id id id gdv wv c r x
42、s c r x s （ 3.1） 11k k kid id idx x v （ 3.2） 如果只是利用上述的位置和速度更新公式更新粒子，也就是说只是从失败中获取经验，这与实际的经验不符。一般的来说，我们还是更多的从成功的经历中获取信息，而从失败的经历中获得相对少的信息，基于这一点在本文的算法中同时从成功和失败的经历中获取信息来更新粒子。为后面叙述方便，将追寻最优位置的 PSO 算法的更新公式描述如下 : 1 1 1 2 2( ) ( )k k k kid id id id gd idv wv c r p x c r p x （ 3.3） 11k k kid id idx x v （ 3.4） 3.1.2双种群粒子群种群规模的动态调整 由上面的叙述可以知道粒子群中的粒子可以按照不同的学习策略进行学习，对速度和位置作出更新。本文将一个种群分成两个子种群，每个子种群选用不同的学习策略，即第一个子种群中的粒子选用从成功经历中获得学习信息的策略来更新自己 ;第二个子种群中的粒子选用从失败的经历中获得学习信息的策略进行进化。可以设置一个比例系数 来控制两个子种群中粒子的个数。
