改进多目标蚁群算法在电网规划中的应用

第33卷第18期2009年10月文章编号：1000-3673（2009）18-0057-06电网技术PowerSystemTechnology中图分类号：TM715文献标志码：AVol.33No.18Oct.2009学科代码：470·4051改进多目标蚁群算法在电网规划中的应用符杨1，孟令合2，胡荣1，曹家麟1（1．上海电力学院电力工程系，上海市杨浦区200090；2．上海大学机电工程与自动化学院，上海市闸北区200072）ApplicationofImprovedMulti-ObjectiveAntColonyAlgorithminPowerNetworkPlanningFUYang1，MENGLing-he2，HURong1，CAOJia-lin1（1．DepartmentofElectricalEngineering，ShanghaiUniversityofElectricPower，YangpuDistrict，Shanghai200090，China；2．SchoolofMechatronicsEngineeringandAutomation，ShanghaiUniversity，ZhabeiDistrict，Shanghai200072，China）ABSTRACT:Forthereasonthatbotheconomyandreliabilityshouldbeconsideredduringpowernetworkplanning,animprovedmulti-objectiveantcolonyalgorithm(IMACA)isproposed.Intheproposedalgorithm,themodifiedquicksortmethodisadoptedtoconstructParetooptimalsolutionset,thustheslow-chainisshortenedandthetimecomplexityofthisalgorithmismitigated;theclusteringalgorithmisadoptedtomodifynon-dominatedsolution,thustheobtainedsolutioncanpossessgooddiversityanddistributivityinwholeParetosolutionspace;thesociohormoneisadoptedtoupdatevariableparametercontrol,thustheglobalconvergenceisspeededup;thesociohormonevolatilizationcoefficientisusedtodynamicadaptiveregulationmechanism,thustheglobalsearchabilityoftheproposedalgorithmisimproved.Thecalculationresultsofan18-buspowernetworkplanningshowthatmoreParetooptimalsolutionscanbeobtainedbytheproposedalgorithmthanbybasicmulti-objectiveantcolonyalgorithm,andtheParetofrontierdistributionismoreuniform,meanwhile,theconvergenceandrapidityareimproved.KEYWORDS:multi-objectiveantcolonyalgorithm；clusteringanalysis；Paretooptimal；powernetworkplanning摘要：针对电网规划需综合考虑经济性和可靠性的问题，提出一种改进的多目标蚁群算法。该算法采用改进的快速排序方法构造Pareto最优解集，缩短了“慢速链”，降低了算法的时间复杂度；采用聚类算法裁剪非支配解，使所得解在整个Pareto解空间具有良好的多样性和分布性；采用信息素更新变参数控制，加快算法的全局收敛速度；采用挥发系数动态自适应调节机制，提高算法全局搜索能力。通过18节点电网规划算例证明，提出的改进算法与基本多目标蚁群算法相比，所得的Pareto最优解数量更多，Pareto前沿分布更基金项目：上海市重点攻关计划项目(071605123)；上海市教委科研创新项目(08ZZ92)；上海市教委重点学科建设资助项目(J51301)。加均匀，同时收敛性和快速性也得到了提高。关键词：多目标蚁群算法；聚类分析；Pareto最优；电网规划0引言电网规划是一个多目标的优化问题，传统的规划方法主要侧重于经济性目标。2008年南方雪灾和汶川地震导致电力受灾严重的原因就是电网抗灾能力不够，而要提高电网的抗灾能力，工程造价也将相应增加。如何综合考虑经济性和可靠性的关系，进行多目标电网规划具有重要的现实意义。近年来，一些新兴的用于解决多目标优化问题的智能优化方法逐渐应用于电力系统中，如非支配遗传算法[1]、多目标进化算法[2]及多智能体方法[3]等。这些方法取得了一定的效果，但还存在一些问题，如收敛性较差和计算速度较慢等。相对于其它多目标智能算法，多目标蚁群算法的研究起步较晚。文献[4]提出一种多目标蚁群搜索算法用于优化配电系统战略规划，该算法采用多种群策略，种群数和目标数相同，引入遗传算法中的共享机制来协调各种群，算法复杂度较高，且对各目标函数的协调不是很完善。文献[5]提出一种用于多目标资产选择问题的Pareto蚁群算法，该算法引入信息素向量的概念，每个信息素向量的元素数和目标数相同，在寻优的初始阶段随机取各目标的权系数，从而很好地协调了各目标之间的关系。Pareto蚁群算法简单实用，算法流程类似于基但缺少优秀的Pareto最优解集构造方本蚁群算法[6]，法，没有考虑解的多样性和分布性，与基本蚁群算法一样存在收敛速度慢和易陷入局优的问题。本文将针对基本多目标蚁群算法的上述缺陷加以改进，58符杨等：改进多目标蚁群算法在电网规划中的应用Vol.33No.18用于实现综合考虑电网投资和运行成本及缺电损失成本的电网规划，并对算法的有效性进行验证。经济性目标赋一大值。1.3多目标优化问题的解多目标优化问题需要同时优化多个目标函数，这些目标往往是互相冲突的，很难存在一个最优解使得所有目标同时达到最优，而是存在一组非支配解，称为Pareto最优解集[11]。电网规划问题的经济性目标和可靠性目标是矛盾的，这也就意味着多目标电网规划问题的解同样是一组Pareto最优解。传统的单目标优化方法得到的解只是Pareto最优解集中的一个非支配解，甚至无法保证所得解是全局非支配解，这样多目标规划就需要一种新的多目标智能优化方法来求得Pareto最优解集。1电网规划问题的数学描述1.1目标函数传统电网规划问题的数学模型主要考虑经济性目标，其目标函数一般为[7]minf1=k1∑cjxj+k2∑rjPj∈Ω1j∈Ω2j(1)式中：第一部分为设备投资成本，k1为资金回收系数，k1=r(1+r)n/[r(1+r)n−1]，cj为支路j中扩展1回新建线路的投资费用，xj为支路j中新建线路回数，Ω1为待选新建线路集合；第二部分为网损费用，k2为年网损费用系数，k2=Costτ/u2，Cost为网损电价，τ为最大负荷损耗时间，u为系统额定电压；rj为支路j的电阻，Pj为正常情况下支路j输送的有功功率，Ω为网络中已有线路和新建线路的集合。电网规划的可靠性目标通常转化为经济形式，以缺电成本为代表的可靠性目标函数为[8-10]minf2=(∑PTl∑IIEARi)EEENSi,lll∈SLDi=1Ln2基于改进多目标蚁群算法的电网规划2.1Pareto蚁群算法Pareto蚁群算法本质上是一种多目标单种群蚁群算法，与单目标蚁群算法最大的不同就是各条路径上对应经济性目标和可靠性目标分别有一个信息素，用信息素向量τi1、τi2表示。在每只蚂蚁构造解的开始阶段随机确定经济性目标的权重p1，0≤pk≤1，可靠性目标的权重p2=1−p1。Pareto蚁群算法的核心思想是用信息素加权和p1τi1+p2τi2代替单目标蚁群算法中的单一信息素向(2)式中：SLD为系统的负荷水平集合；Pl、Tl为第l种负荷水平的概率和负荷持续时间；Ln为负荷节点数；IIEARi为节点i的缺电损失评价率；EEENSi,l为第l种负荷水平下节点i的电量不足期望值。EEENSl=∑Lq,l∏Pqs∏(1−Pqt)q∈Fs∈ht∈H量τi。p1的随机性使信息素向量τi1、τi2在寻优过程中概率相同，确保了二者所代表的经济性目标和可靠性目标地位相同。寻优过程中，针对各个目标分别进行信息素局部更新和全局更新，使蚂蚁朝着经济性和可靠性目标各自的最优方向优化，每一次迭代得到的非支配解保存到Pareto最优解集中，从而使算法尽可能达到二者同时最优。2.2用改进的快速排序方法构造Pareto最优解集多目标蚁群算法是通过构造优化问题的非支配集并使非支配集不断逼近真正的Pareto最优边界来实现的。算法的收敛过程，就是通过在每一次迭代时构造当前蚁群的非支配集，并通过最优个体保留机制(构造并保留当前非支配解)，使非支配集一步一步地逼近真正的Pareto最优边界。算法的每一次迭代都要构造一次非支配集，因而构造非支配集的效率将直接影响算法的运行效率。传统方法时间复杂度较高，且容易出现“慢速链”现象，改进的快速排序方法[12]可以有效提高效率并减少“慢速链”带来的问题。Pareto最优解集中的解之间是相互不被支配(3)式中：F为系统故障事件集合；H、h分别为发生故障q时正常设备和故障设备集合；Pqs、Pqt为故障q状态下设备s、t的故障停运率；Lq,l为发生故障q时系统的切负荷量。1.2约束条件0≤xj≤xjmax,xj∈N,j∈Ω1(4)Vimin≤Vi≤Vimax,i∈NPj≤PjPj′≤Pj(5)(6)(7)式中：xjmax为架线回数最大值；N为非负整数集；Vi为节点电压；Pj、Pj′为正常运行和N−1校验时支路j潮流相量；Pj为支路j潮流容量限值相量。式(6)(7)是网络运行的约束条件，包括正常运行时和N−1校验时不过负荷。为避免算法在初始阶段陷入瘫痪，本文采用罚函数的方法处理潮流约束，即在违反正常运行和N−1校验潮流约束时分别为第33卷第18期电网技术59的，这个关系称为不相关，快速排序方法引入了一个新的关系：如果解xy或者x和y是不相关的，则称xdy。改进快速排序的思路是将非支配解集从原始解集中分类出来。每次先选第一个解x作为比较对象，按照关系d”“与其它解进行比较判断，以第一个支配x或者和x不相关的解y作为第二个比较对象，经一轮排序后，比x和y“小”的解全部排除掉，如果x和y不被所有这些解所支配，则并入Pareto最优解集，否则一起排除掉。如此进行下一轮排序，直至原始解集为空集。用聚类分析保持Pareto最优解集的分布性多目标蚁群算法本质上是一种仿生学方法，与大自然需要生态平衡一样，也需要制定合适的生存规则来维持种群的多样性和分布性，而文献[13]提出的Pareto最优解集的量化评价标准之一就是分散性。保持解分布性的方法很多，如小生境技术、信息熵、网格以及聚类分析等。根据多目标电网规划解的特点，本文采用基于层次凝聚距离的聚类算法[14]实现Pareto前沿的均匀分布。凝聚的层次聚类方法是一种按照自底向上的策略来聚类个体的方法，初始时把N个解分别当作一个子类，然后通过计算解之间的相似度，逐步将具有最大相似度的个体聚集到同一类中，直至满足终止条件。算法的实现过程为：1）初始化聚类C，使C中每个子集包含非支配集S的一个解：C=i{{i}}，i∈S。2.3提高算法的全局收敛速度，参考单目标蚁群算法的一些改进思路[15-16]，结合电网规划问题的实际特点，本文对Pareto蚁群算法的参数设置