基于改进离散粒子群算法的机组组合优化方法

基于改进离散粒子群算法的机组组合优化方法0引言实际的日常生活中或在处理工程问题的过程中，人们经常遇到在某个问题有多个解决方案可供选择的情况下，如何根据自身所提出的某些性能的要求，从多个可供选择的方案中选择一个可行方案，使所要求的性能指标达到最大或最小，这就是优化问题[1]。如工程设计中怎样选择参数，使得设计即满足要求又能降低成本;资源分配中，怎样的分配方案既能满足各个方面的基本要求，又能获得好的经济效益等。优化是个古老的课题，早在17世纪，英国Newton和德国Leibnitz创立的微积分就蕴含了优化的内容。而法国数学家Cauchy则首次采用梯度下降法解决无约束优化问题，后来针对约束优化问题又提出了Lagrange乘数法。人们关于优化问题的研究工作，随着历史的发展不断深入，优化理论和算法迅速发展形成一门新的学科。二十世纪八十年代以来，一些新颖的优化算法得到了迅速发展。人工神经网络(ANN)在一定程度上模拟了人脑的组织结构[2-4];遗传算法(GA)借鉴了自然界优胜劣汰的进化思想[5,6];蚁群优化算法(ACO)受启发于自然界蚂蚁的寻径方式[7];模拟退火(SA)思路源于物理学中固体物质的退火过程[8,9];禁忌搜索(TS)模拟了人类有记忆过程的智力过程。这些算法有个共同点:都是通过模拟或揭示某些自然界的现象和过程得到发展，在优化领域，有人称之为智能优化算法(IntelligentOptimizationAlgorithms)。本文研究的粒子群优化算法（ParticleSwarmOptimization，PSO），是在1995年由美国社会心理学家Kennedy和电气工程师Eberhart共同提出的[10-12]，其基本思想是受他们早期对鸟类群体行为研究结果的启发，并利用了生物学家FrankHeppner的生物群体模型。PSO算法从诞生起，就引起了国内外学者的广泛关注，并掀起了该方法的研究热潮，并在短短几年时间里涌现出大量的研究成果，己经在函数优化、神经网络设计、分类、模式识别、信号处理、机器人技术等应用领域取得了成功应用。该算法目前己被“国际演化计算会议”(ConferenceofEvolutionaryComputation，CEC)列为讨论专题之一。PSO算法在电力系统中的应用研究起步较晚，最近几年它在电力系统领域中逐渐显示出广阔的应用前景，己开始引起电力科学工作者的关注和研究兴趣。如何充分发挥PSO算法的优势来解决电力系统的有关难题，已成为一个新的研究热点。1优化算法基础1.1最优化问题最优化问题是寻找最小值（最大值问题可转化为需求最小值）的问题。最优化问题根据其目标函数、约束函数的性质以及优化变量的取值等可以分成许多类型，每一种类型的最优化问题根据其性质的不同都有其特定的求解方法。不失一般性，最小化问题可定义为:min()..{|()0,1,2,,}tfXstXSXgXim（1.1）其中，()fX为目标函数，()tgX为约束函数，S为约束域，X为n维优化变量。通常，对()0tgX的的约束和等式约束可转换()0tgX的约束。当()fX，()tgX为线性函数，且0X时，上述最优化问题即为线性规划问题，其求解方法有成熟的单纯形法和Karmarc方法。当()fX，()tgX中至少有一个函数为非线性函数时，上述问题即为非线性规划问题。非线性规划问题相当复杂，其求解方法多种多样，但到目前仍然没有一种有效的适合所有问题的方法。当优化变量X仅取整数值时，上述问题即为整数规划问题，特别是当X仅能取0或1时，上述问题即为0-1整数规划问题。由于整数规划问题属于组合优化范畴，其计算量随变量维数的增长而指数增长，所以存在着“维数灾难”问题。当()0,(1,2,,)gXim)所限制的约束空间为整个n维欧式空间，即nR时，上述最优化问题为无约束优化问题。非线性规划问题(包括无约束优化问题和约束优化问题)，由于函数的非线性，使得问题的求解变得十分困难，特别是当目标函数在约束域内存在多峰值时。常见的求解非线性规划问题的优化方法，其求解结果与初值的选择关系很大，也就是说，一般的约束或无约束非线性优化方法均是求目标函数在约束域内的近似极值点，而非真正的最小点。总的说来，求最优解或近似最优解的方法主要有三种:枚举法、启发式算法和搜索算法。（1）枚举法。枚举出可行解空间内的所有可行解，以求出精确最优解。对于连续问题，该方法要求先对其进行离散化处理，这样就有可能产生离散误差而永远达不到最优解。另外，当枚举空间比较大时，该方法的求解效率比较低。（2）启发式算法。寻求一种能产生可行解的启发式规则，以找到一个最优解或近似最优解。该方法的求解效率虽然比较高，但对每一个需要求解的问题都必须找出其特有的启发式规则，这种启发式规则无通用性，不适用于其他问题。（3）搜索算法。寻找一种搜索算法，该算法在可行解空间的一个子空间内进行搜索操作，以找到问题的最优解或近似最优解。该方法虽然保证不了一定能够得到问题的最优解，但若适当地利用一些启发知识，就可近似地使解的质量和求解效率达到一种较好的平衡。搜索算法可分为两大类:平行搜索法和序贯搜索法。作平行搜索时，需要计算目标函数值的自变量节点位置在事先一起选定。而作序贯搜索法时则根据前一轮计算得到的目标函数值的情况用以确定下一轮计算目标函数值的自变量节点位置，因此它带有迭代性。搜索算法又可分确定性搜索法和随机性搜索法两种。确定性搜索算法在寻优过程中，一个搜索点到另一个搜索点转移有确定的转移方法和转移关系，因而其过程可再现，其不足在于寻优结果与初值有关，初值选取不当往往有可能使搜索永远达不到最优点。随机性算法在算法执行过程中加入随机性(因为真正理论意义下的随机数是不可能由计算机产生的，所以实际上用的是伪随机数)，需计算算法输出结果的概率平均值。随机算法往往比确定性算法计算时间少，但它的准确率略微降低。1.2局部优化算法定义1.1如果存在*BXB，使得对XB有：*()(),BfXfXXB（1.2）成立，其中nBSR，S为由约束函数限定的搜索空间，则称*BX为()fX在B内的局部极小点，*()bfX为局部极小值。常见的优化方法大多为局部优化方法，都是从一个给定的初始点0XS开始，依据一定的方法寻找下一个使得目标函数得到改善的更好解，直至满足某种停止准则。成熟的局部优化方法很多，如Newron-Raphson法、共扼梯度法、Fleteher-Reeves法、Polar-Ribiere法、Davidon-Fleteher-Power(DFP)法、Broyden-Fletcher-Goldfarb-Shsnn(BFGS)方法等，还有专门为求解最小二乘问题而发展的Leven-berg-Marquardt(LM)算法。所有这些局部优化算法都是针对无约束优化问题而提出的，而且对目标函数均有一定的解析性质要求，如Newton-RaPhson法要求目标函数连续可微，同时要求其一阶导数连续。1.3全局优化算法定义1.2如果存在*XS，使得对XS有：*()(),fXfXXS（1.3）成立，其中nSR为由约束条件限定的搜索空间，则称*X为()fX在S内的全局极小点，*()fX)为全局极小值。目前，全局优化问题也己存在许多算法，如填充函数法等，但比起局部优化问题的众多成熟方法，其间还有很大差距。另外，解析性优化方法对目标函数及约束域均有较强的解析性要求，对于诸如目标函数不连续、约束域不连通、目标函数难以用解析函数表达或者难以精确估计(如仿真优化问题)等问题时，解析确定性优化方法就难以适应。为了可靠解决全局优化问题，人们试图离开解析确定性的优化算法研究，转而探讨对函数解析性质要求较低，甚至不做要求的随机型优化方法。最早的随机型优化方法是基于Monte-Carfo方法的思想，针对具体问题性质的特点，构造以概率1收敛于全局最小点的随机搜索算法。真正有效且具有普遍适应性的随机全局优化方法，是近十多年来人们模拟自然界现象而发展起来的一系列仿生型智能优化算法，如禁忌搜索算法、模拟退火算法、进化类算法、群体智能算法等。1.4没有免费午餐定理1997年在IEEETransactiononEvolutionComputation上，Wolpert和Macready发表了题为“NoFreeLunchTheoremsforOptimization”的论文，提出并严格论证了所谓的没有免费午餐定理(NoFreeLunchTheorems)，简称NFL定理[13]。NFL定理的简单表述为:对于所有可能的问题，任意结定两个算法A、B，如果A在某些问题上表现比B好(差)，那么A在其他问题上的表现就一定比B差(好)，也就是说，任意两个算法A、B对所有问题的平均表现度量是完全一样的。该定理的结论是，由于对所有可能函数的相互补偿，最优化算法的性能是等价的。该定理只是定义在有限的搜索空间，对无限搜索空间结论是否成立尚不清楚。在计算机上实现的搜索算法都只能在有限的搜索空间实施，所以该定理对现存的所有算法都可直接使用。自从NFL定理提出以来，有关定理本身及其相关结论的争论在学术界一直持续未断，因为NFL定理本身涉及到了优化算法最基本的问题，而且其结论多少有点出人意料。NFL定理的主要价值在于它对研究与应用优化算法时的观念性启示作用。虽然NFL定理是在许多假设条件下得出的，但它仍然在很大程度上反映出了优化算法的本质。当我们所面对的是一个大的而且形式多样的适应值函数类时，就必须考虑算法间所表现出的NFL效应，即若算法A在某些函数上的表现超过算法B，则在这类的其他适应值函数上，算法B的表现就比A要好。因此，对于整个函数类，不存在万能的最佳算法，所有算法在整个函数类上的平均表现度量是一样的。因此，关于优化算法的研究目标就应该从寻找一个大的函数类上的优化算法转变为:（1）以算法为导向，从算法到问题:对于每一个算法，都有其适用和不适用的问题;给定一个算法，尽可能通过理论分析，给出其适用问题类的特征，使其成为一个“指示性”的算法。（2）以问题为导向，从问题到算法:对于一个小的特定的函数集，或者一个特定的实际问题，可以设计专门适用的算法。实际上，大多数在进化算法方面的研究工作可以看作是属于这一范畴的，因为它们主要是根据进化的原理设计新的算法，或者将现有算法进行部分改进，以期对若干特定的函数取得好的优化效果。NFL定理只是否定了去寻找一个万能的最佳算法的可能性，但对于某些小约函数集合，NFL定理则认为存在一个在该集合上的好算法。1.5进化算法近十余年来，遗传算法(GeneticAlgorithms，GA)、进化策略(EvolutionaryStrategies，ES)和进化规划(EvolutionaryProgramming，EP)等进化类算法在理论和应用两方面发展迅速、效果显著，并逐渐走向了融合，形成了一种新颖的模拟进化的计算理论，统称为进化计算(EvolutionaryComputation，EC)，进化计算的具体实现方法与形式称为进化算法(EvolutionaryAlgorithm，EA)。进化算法是一种受生物进化论和遗传学等理论启发而形成的求解优化问题的随机算法，虽然出现了多个具有代表性的重要分支，但它们各自代表了进化计算的不同侧面，各具特点。进化算法是模拟由个体组成的群体的集体学习过程，其中每个个体表示给定问题搜索空间中的一个点。进化算法从初始群体出发，通过选择、变异和重组过程，使群体进化到搜索空间中越来越好的区域。选择过程使群体中适应性好的个体比适应性差的个体有更多的复制机会，重组算子将父辈信息结合在一起并将他们传到子代个体，变异在群体中引入了新的变种。进化算法的两个主要特点是群体搜索策略及群体中个体之间的信息交换。它们的优越性主要表现在:首先，进化算法在搜索过程中不容易陷入局部最优，即使在所定义的适应度函数是不连续的，非规则的或有噪声的情况下，它们也可能以很大的概率找到全局最优解;其次，由于它们固有的并行性，进化算法非常适合于向量并行机;再者，进化算法采