基于模拟退火算法的输电网中长期规划研究.doc

基于模拟退火算法的输电网中长期规划研究第12誊第1期1999年a月青岛大学JOURNALOFQINGDAOUNIVERSITYVoL.12No1Mar.1999一基于模拟退火算法的输电网中长期规划研究金明7./1青岛大学电气及自动化工程学院青岛.Tn一模拟退火算法是一种解决组合优化问题的有效方法,其最终优化结果不依抽干初始解的选择,理论上可避免算法过早收敛干局部最小点.从而保证找到全局最优解或全局近似最优解.本文特蠖粗退又算法用于输电网中长期规划问题的研究,详细介绍j算法实现过程中各种誊数的选择方法并蛤出了具体算倒.试算结果表明利用谊算法得到的优化结果是令人满意的.关键词:模拟退火算法输电网络一电力系统规划投引言随着电力工业的不断发展,系统的发电容量和用电负荷持续增长.为保证系统运行的安全性和可靠性,输电网络的规模也必将随之扩大.以消除增大的输电容量在原有网络中引起的过载问题.输电网中长期规划的任务是研究未来五至十年电网扩建的投资策略和网架构想,即规划何时,何地,架设多少条何种电压等级的待选线来经济,可靠地消除系统在各阶段出现的原有线路潮流过载现象.目前要对这一动态过程进行完全准确地求解还比较困难.实际的处理方法是将其分成规划单阶段架线梢载的静态决策和考虑过程的阶段性的动态决策两个子问题.本文算法仅用于输电网中长期规划的静态决策问题.当给定未来某一阶段的电源出力和负荷分布后,利用某种最优化决策方法,求出最优的架线方案,从数学上讲这是一个离散,非线性的组合优化问题.其目标函数具有多极值点的特性.目前常用的方法,其最终优化结果与初始解的选择有密切的关系.算法往往过早收敛于局部最小点,很难保证最终能获得问题的全局最优解或全局近似最优解.模拟退火算法是1953年N.Metropolis等人在研究二维相变时提出的,该方法将组合优化问题与统计力学中的热平衡问题相类比,通过模拟退火过程对优化问题进行求解.由于该算法在理论上可保证找到问题的全局最优解或全局近似最优解,故其具有相当广泛的应用前景.本文中将模拟退火算法用于输电网中长期规划问题的研究.取得了令人满作者筒介差鼍着要皆青岛大学电气盈自动化学碗副教授?目前主要研究方向为人工神经嗣络技术收薯日期t1998-I2-04第1期基于谟拟退火算法的输电网中长期规划研究81意的结果.1模拟退火算法的基本原理模拟退火算法是基于蒙特卡罗(MonteCarlo)迭代求解法的一种启发式随机搜索算法.该算法用于解决组合优化问题的出发点是物理学中固体物质的退火过程与一般组合优化问题间的相似性.在对固体物质进行退火处理时,通常先将它加热熔化.使其中的粒子可自由运动,然后随着温度的逐渐下降,粒子也逐渐形成了低能态的晶格.复足够次数后,系统将达到该温度下的热平衡状态,且服从Boltzmann分布.这里6为Boltzmann常数.将以上基本思想写成算法形式1.1退火过程实现算法(AP)任选一初始状态S.作为初始当前解,并设初始温度T.,令iO.令TT,SSn以和调用Metropolis抽样算法,并返回当前解.按一定方式将降温,即令T一+I,+1<,ii+1目前常用的降温方式为;T=灯,0<则依概率expf一;等I接收l,A,作为下一个当前解.即产生一个0,1上的随机数r,若r<expI一,则接收S作为下一个当前解,否则不接受.若锻接受,则令(+1)一S,滞令(+1)一S旺).令+1,判断是否满足收敛条件,不满足回到.收敛条件实用中一般为k达到某一定值.,82青岛大学第12卷将当前解()返回调用它的AP算法.2输电网中长期规划模型2.1网络模型超高压输电网一般具有下列特点:(1)线路电阻远小于电抗,可略去不计,(2)各线路两端电压相角差较小,其三角函数值可用一次项近似;(3)各节点电压幅值接近1,0标幺值.这样实际输电网规划中,可用直流潮流方程进行计算.一个一节点的系统,其直流潮流方程可描述为;尸一(1)上式中尸为(一一1)维列相量,称为节点注入有功功率列向量.其中无对应于平街节点s的元素尸.;印为一1)维列相量,称为节点电压相位角列向量,其中无对应于平街节点s的元素【明是一个(一一1)阶对称方阵.称为节点电纳阵,其中无对应于平衡节点s的相应行和相应列.2.2网络安全约束为保证系统的运行稳定性,网络中相邻两节点间的电压相位差必须满足不等式ll硝(2)式中表示相邻两节点与之间电压相位差的最大允许限值(绝对值).在采用直流潮流方程所描述的系统中,(2)式亦可等价地表示为II尸(3)式中尸表示支路fJ中有功潮流的最大允许限值(绝对值).2.3输电网中长期规划模型尽管实际工程中的架线消载是一个多目标优化问题,但考虑到可能性,社会和环境等,一般输电网中长期规划问题均以投资最省为目标,结合2.1和2.2可得输电网中长期规划数学模型为:minZ一.1工t.尸=印Il尸毛_0,1其中i,=1,2,一,f,一为系统节点数I=l,2.?,为节点f之间的待选线数一1表示节点f之间需架设第t条待选线一0表示节点巧之间不需架设第t条待选线.3模拟遇火算法在输电网中长期规划中的应用3.1适用于模拟遇火算法的优化标准形由于模拟退火算法属于无约束优化方法,因此在将其用于求解,这样就把(4)式中示出的有约束优化问题转化为无约束优化问题.从理论上讲,模拟退火算法的初始状态应在整个状态空间中随机选取,以保证最终优化结果收敛到全局最优点或近似全局最优点.本文中采甩如下方法产生算法的初始状态;依2.3节中所述,将系统中的每一条待选路径的规划结果用一位二进制数字表示,若该位数字为1,则表示相应的待选路径上应架设新线,若该位数字为0,则表示相应的待选路径上不需架设新线.这样所有待选路径的规划结果就表示为一个二进制串,串的长度等于网络中所有待选路径的数目.与初始状态所对应的二进制串,是对该串中的每一位随机地取根据模拟退火算法的要求,为避免算法陷入局部最优点,控制参数的韧值应选得足够大,以便使算法的擅索范围尽可能遍及整个状态空间,但该值若选得过大,将会大大增加算法的迭代次数,延长计算时间.根据经验,本文中将丁.选定为10O.3.3冷却方式的选择理论上,只有当控制参数拄对数规律下降时,才能保证算法收敛到全局最优解.但在实际应用中这样慢的收敛速度是令人难一-一可扩建线路V.:,ll青岛大学第12卷以接收的,目前采取的冷却方式一般取+.一7其中0<<l,一般E(O.5,0.99).但这样带来的问题是A的选取与具体问题的性质有关.本文中取一0.85.3.4控制参数终值的选取控制参数终值的选取依较于算法的终止判据,合理的终值选取既要确保算法具有较高的质量,又要尽可能减少CPU时间.目前一般采用确定控制参数个数的方法来决定算法的终止.本文中取控制参数的个数为100,即算法中一100.3.5新状态的构成方法模拟退火算法中重要的一环是如何在现有状态的邻域中随机地产生下一个新状态.本文中采用方法是对表示待选路径规划结果的二进制串的各位进行随机变位,即对二进制串中的每一位产生一个O,1上的随机数,若,则保持该位状态不变,否则将该位变位,以此产生对应一个新状态的二进制串.其中P.为变位概率,当T值较大时.P值较小,随着T的减小,P值逐渐增大.4计算实例囝2利用线性规划法得到的优化结果本文采用文囝3利用模拟遇火算法得到的优化结果献”中所给的算例进行计算.该系统现有lO个节点,9条线路.在未来菜水平年.系统增加为18个节点,如图l所示.图2是利用线性规划法得到的优化结果,该结果中需架新线l4条,新线总长度1685公里图3是利用模拟退火算法得到的优化结果,该结果中也架新线14条,但新线总长度减至1645公里.5结论模拟遇火算法是一种解决组合优化问题的有效方法,它通过模拟退火过程,理论上可第1期基于模拟退火算法的输电网中长期规划研究85避免算法过早收敛于局部最小点,从而保证找到全局最优解或全局近似最优解.本文将模拟遇火算法用于输电网中长期规划问蹶的研究,详细介绍了算法实现过程中各种参数的选择方法并给出了具体算例.试算结果表明利用该算法得到的优化结果是令人满意的.参考文献王仲鸿等.输电网中长期规划支路追加法.全国高校电自专业第三届学术年会论文集,西安:西安交大出版社,1987王锡凡主编.电力系统优化规划.北京水利电力出版社,1990,3闰钿等.10KV线路故障测距模拟退火算法应用.继电器,1998,10康立山等,非数值并行算法模拟退火算法.北京:科学出版社,1997,7金明.遗传算法在输电网中长期规划中的应用.青岛大学(自然科学版),1998,1STUDYOFMlDLONGTERMTRANSMlSslONNETWORKPLANNlNGBASEDONTHESIMULATEDANNEALINGALGORITHMJiMing(TheCollegeofElectricalandAutomationofQingdaoUniversity,Qingdao266071)A自tractThesimulatedannealingalgorithmisaneffectivemethodtosolvethecombinatorialoptimizationproblem.Itcanavoidthealgorithmconvergingtothelocaloptimumvalueandensuregettingtheglobaloptimumsolutionortheapproximateglobaloptimumsolution.Thispaperusesthemethodinthestudyofmidlongtermtransmissionnetworkplanning.Themethodtoselectthecontrolparametersofthealgorithmisintroducedindetail.Someexamplesaregivenandtheresultsaresatisfactory.Keywords:simulatedannealingalgorithm;transmissionnetwork;powersystemplanninglt;1,一般(0.5,0.99).检查退则依概率expf一;等I接收l,A,作为下一个当前解.即产生一个0,1上的随机数r,若r<expI一,则接收S作为下一个当前解,否则不接受.若锻接受,则令(+1)一S,滞令(+1)一S旺).令+1,判断是否满足收敛条件,不满足回到.收敛条件实用中一般为k达到某一定值.,82青岛大学第12卷将当前解()返回调用它的AP算法.2输电网中长期规划模型2.1网络模型超高压输电网一般具有下列特点:(1)线路电阻远小于电抗,可略去不计,(2)各线路两端电压相角差较小,其三角函数值可用一次项近似;(3)各节点电压幅值接近1,0标幺值.这样实际输电网规划中,可用直流潮流方程进行计算.一个一节点的系统,其直流潮流方程可描述为;尸一(1)上式中尸为(一一1)维列相量,称为节点注入有功功率列向量.其中无对应于平街节点s的元素尸.;印为一1)维列相量,称为节点电压相位角列向量,其中无对应于平街节点s的元素【明是一个(一一1)阶对称方阵.称为节点电纳阵,其中无对应于平衡节点s的相应行和相应列.2.2网络安全约束为保证系统的运行稳定性,网络中相邻两节点间的电压相位差必须满足不等式ll硝(2)式中表示相邻两节点与之间电压相位差的最大允许限值(绝对值).在采用直流潮流方程所描述的系统中,(2)式亦可等价地表示为II尸(3)式中尸表示支路fJ中有功潮流的最大允许限值(绝对值).2.3输电网中长期规划模型尽管实际工程中的架线消载是一个多目标优化问题,但考虑到可能性,社会和环境等,一般输电网中长期规划问题均以投资最省为目标,结合2.1和2.2可得输电网中长期规划数学模型为:minZ一.1工t.尸=印Il尸毛_0,1其中i,=1,2,一,f,一为系统节点数I=l,2.?,为节点f之间的待选线数一1表示节点f之间需架设第t条待选线一0表示节点巧之间不需架设第t条待选线.3模拟遇火算法在输电网中长期规划中的应用3.1适用于模拟遇火算法的优化标准形由于模拟退火算法属于无约束优化方法,因此在将其用于求解,这样就把(4)式中示出的有约束优化问题转化为无约束优化问题.从理论上讲,模拟退火算法的初始状态应在整个状态空间中随机选取,以保证最终优化结果收敛到全局最优点或近似全局最优点.本文中采甩如下方法产生算法的初始状态;依2.3节中所述,将系统中的每一条待选路径的规划结果用一位二进制数字表示,若该位数字为1,则表示相应的待选路径上应架设新线,若该位数字为0,则表示相应的待选路径上不需架设新线.这样所有待选路径的规划结果就表示为一个二进制串,串的长度等于网络中所有待选路径的数目.与初始状态所对应的二进制串,是对该串中的每一位随机地取根据模拟退火算法的要求,为避免算法陷入局部最优点,控制参数的韧值应选得足够大,以便使算法的擅索范围尽可能遍及整个状态空间,但该值若选得过大,将会大大增加算法的迭代次数,延长计算时间.根据经验,本文中将丁.选定为10O.3.3冷却方式的选择理论上,只有当控制参数拄对数规律下降时,才能保证算法收敛到全局最优解.但在实际应用中这样慢的收敛速度是令人难一-一可扩建线路V.:,ll青岛大学第12卷以接收的,目前采取的冷却方式一般取+.一7其中0<<l,一般E(O.5,0.99).但这样带来的问题是A的选取与具体问题的性质有关.本文中取一0.85.3.4控制参数终值的选取控制参数终值的选取依较于算法的终止判据,合理的终值选取既要确保算法具有较高的质量,又要尽可能减少CPU时间.目前一般采用确定控制参数个数的方法来决定算法的终止.本文中取控制参数的个数为100,即算法中一100.3.5新状态的构成方法模拟退火算法中重要的一环是如何在现有状态的邻域中随机地产生下一个新状态.本文中采用方法是对表示待选路径规划结果的二进制串的各位进行随机变位,即对二进制串中的每一位产生一个O,1上的随机数,若,则保持该位状态不变,否则将该位变位,以此产生对应一个新状态的二进制串.其中P.为变位概率,当T值较大时.P值较小,随着T的减小,P值逐渐增大.4计算实例囝2利用线性规划法得到的优化结果本文采用文囝3利用模拟遇火算法得到的优化结果献”中所给的算例进行计算.该系统现有lO个节点,9条线路.在未来菜水平年.系统增加为18个节点,如图l所示.图2是利用线性规划法得到的优化结果,该结果中需架新线l4条,新线总长度1685公里图3是利用模拟退火算法得到的优化结果,该结果中也架新线14条,但新线总长度减至1645公里.5结论模拟遇火算法是一种解决组合优化问题的有效方法,它通过模拟退火过程,理论上可第1期基于模拟退火算法的输电网中长期规划研究85避免算法过早收敛于局部最小点,从而保证找到全局最优解或全局近似最优解.本文将模拟遇火算法用于输电网中长期规划问蹶的研究,详细介绍了算法实现过程中各种参数的选择方法并给出了具体算例.试算结果表明利用该算法得到的优化结果是令人满意的.参考文献王仲鸿等.输电网中长期规划支路追加法.全国高校电自专业第三届学术年会论文集,西安:西安交大出版社,1987王锡凡主编.电力系统优化规划.北京水利电力出版社,1990,3闰钿等.10KV线路故障测距模拟退火算法应用.继电器,1998,10康立山等,非数值并行算法模拟退火算法