2004年11月系统工程理论与实践第11期 文章编号:100026788(2004)1120122206基于混合遗传算法的配电网络重构优化刘 扬,杨建军,魏立新,战 红(大庆石油学院机械科学与工程学院,黑龙江大庆163318)摘要: 以网损最小为目标函数,电压降、线路电流值和电源容量的限制为约束条件,建立了配电网络重构优化数学模型,用外部惩罚函数法将该问题转化为无约束问题Λ针对遗传算法的局限性,对适应函数进行了调整,实施了最优保留策略,改进了交叉和变异操作,并结合了模拟退火算法,从而形成了混合遗传算法,该算法能够有效地提高收敛速度,避免早熟收敛Λ优化过程中考虑了配电网自身特点,提高了计算效率Λ重构算例说明,该优化方法有效、实用Λ关键词: 配电网络;网络重构;自适应遗传算法;模拟退火;混合遗传算法中图分类号: TM744 文献标识码: A T he Op ti m izati on of D istribu ti on N etw o rk R econfigu rati onBased on H yb rid Genetic A lgo rithmL I U Yang,YAN G J ian2jun,W E I L i2x in,ZHAN Hong(M echan ical Science and Engineering Co llege,D aqing Petro leum In stitu te,D aqing163318,Ch ina)Abstract: A n op ti m izati on model of distribu ti on netw o rk reconfigu rati on is estab lished,in w h ich them in i m um netw o rk lo ss is taken as ob jective functi on,the restricti on s to the vo ltage,cu rren t and thecapacity of pow er sou rce are taken as con strain t conditi on s.T h rough the ou ter penalty functi on m ethod,the p rob lem is tran sfo rm ed to non restrain t op ti m izati on p rob lem.A i m ing at the li m itati on of geneticalgo rithm,the fitness functi on is adju sted,the op ti m ized reserved strategy is u sed,the cro ss andm u tati on m ethod are i m p roved,and si m u lated annealing algo rithm is com b ined w ith,then the hyb ridgenetic algo rithm is fo rm ed.It can i m p rove the speed of convergence and avo id p rem atu re convergence.Based on the featu res of distribu ti on netw o rk,the hyb rid genetic algo rithm is u sed to so lve the p rob lem,so the compu tati onal efficiency is i m p roved.R econfigu rati on resu lts show that the algo rithm is efficien tand p ractical.Key words: distribu ti on netw o rk;netw o rk reconfigu rati on;adap tive genetic algo rithm;si m u latedannealing;hyb rid genetic algo rithm1 引言网络重构的基本原理是在满足系统中电压、电流、电源容量等约束的前提下,通过调整网络中分段开关和联络开关的组合状态,寻找某一供电路径,以达到降低网损、消除过载、改善电压分布、提高供电可靠性的目的Λ配电网络重构问题是一个大规模非线性组合优化问题Λ目前关于配电网络重构的研究方法较多,其中遗传算法(Genetic A lgo rithm,简称GA)、模拟退火算法(Si m u lated A nnealing A lgo rithm,简称SA)等现代优化方法也得到了应用Λ但模拟退火算法收敛的关键在于退火方案的选取,若选择不当,则需要大量的随机迭代,计算量大,得到的解与最优解相差甚远Λ遗传算法的算法性能易受控制参数(如交叉率、变异率等)的影响,选择不当易陷入“早熟”,当仅依靠遗传操作进行寻优,而不利用问题的特有性质时,收敛速度收稿日期:2003212230基金项目:黑龙江省教育厅科技项目(10541008)作者简介:刘扬(1957-),男,河北秦皇岛人,教授,博士生导师,主要从事油田地面工程优化与仿真、石油机械安全评价的研究工作慢,局部寻优能力差Λ本文针对配电网络的实际情况,建立了网络重构优化数学模型,并探讨了混合遗传算法实现的技术问题,及在配电网络重构优化问题中的应用Λ2 配电网络重构优化数学模型本文的配电网络重构以网损f ′最小为目标函数,其数学模型为:m in f ′=∑Ni =1∃PL i =∑N i =1R i P 2i +Q 2i U 2i ,(1)式中∃1L i 为线路i 的有功损耗;i =1,…,N ,N 为线路总数量;R i 为线路i 的电阻;P i 为线路i 上流过的有功功率;Q i 为线路i 上流过的无功功率;U i 为线路i 的电压值Ζ不等式约束包括电压降约束、线路电流值约束和电源容量约束,即U i ≥U m in i ,(2)I i ≤I m ax i ,(3)S b ≤S m ax b ,(4)式中U m in i 为线路i 要求的最低工作电压值;I m ax i为线路i 的导线型号对应的载流量值;S b 为变电所b 的负荷值,b =1,…,B ,B 为变电所总数量;S m ax b为变电所b 的供电能力Ζ利用外部惩罚函数法[1]将式(1)～(4)转化为无约束问题Ζ先作如下定义:P =∑N i =1m in (0,U i -U m in i )2+m in (0,I m ax i -I i )2+∑Bb =1[m in (0,S m ax b -S b )]2.(5)则经惩罚函数法转换的数学模型为:m in f =f ′+M p ,(6)式中M p 为惩罚项;M 为惩罚因子Ζ此外,还应保持网络的放射性,即不形成环网,以及不出现“孤岛”的情况,即每次循环遍历的负荷节点个数应等于整个网络中总的负荷节点个数Ζ3 混合遗传算法及其在配电网络重构优化中的应用311 编码在遗传算法中,问题的解用数字串来表示,每个数字串叫做一个染色体,遗传算子也是直接对串进行操作Ζ遗传算法常用的有十进制编码和二进制编码Ζ配电网络重构的实质就是通过改变开关的开合状态来改变网络的拓扑结构,目的是找到最优的网络结构所对应的开关状态,以使网损降到最小Ζ因此,取开关状态为控制变量比较合适,将网络中的开关状态自然的用0或1表示(0表示开,1表示合),每个开关占据染色体的一位,各开关状态组合在一起,就形成了一条染色体,染色体的长度等于网络中开关数量总和Ζ312 产生初始种群随机产生p op siz e 个长度为L (L 为网络中开关数量的总和)的二进制编码,作为初始种群Ζ为了让初始种群遍及整个解空间,尽量反映搜索空间的性态,p op siz e 不能取太小,且随节点数的增多而变大,不过太大会使运算时间增加,这是我们不希望的Ζp op siz e 取染色体长度数的一个线性倍数是实际应用时经常采用的方法,如可取为L 和2L 之间的一个确定数Ζ同时为了保持网络的放射性,以及不形成“孤岛”,在配电网潮流计算程序中加入了搜索判断程序,将不符合实际运行条件的个体去掉Ζ313 确定初温及退温操作初温的确定选择t 0=K ∆的形式,其中,K 为充分大的数,∆=f m ax x -f m in s Ζ式中f m ax s 、f m in s 为初始种群中最大目标函数值和最小目标函数值Ζ退温函数选用常用的t n +1=Αt n 形式,其中0<Α<1Ζ314 确定适应函数适应函数值f it i 是遗传算法指导搜索方向的依据,首先应保证适应函数值不为负,其次,因为在轮盘321第11期基于混合遗传算法的配电网络重构优化赌选择过程中,适应函数值大的染色体被选中的概率大,因此目标函数的优化方向对应适应函数值增加的方向Ζ网络重构的目标函数是网损最小,属于最小值优化问题,应加以调整Ζ本文采用的变换方式如下[2]:f it i=exp-f i-f m int(7)式中f i为染色体对应的目标函数值;f m in为当前代进化群体中最小目标函数值;t为温度参数Ζ应注意,经此变换后进化过程中每代的最大适应函数值均为1Ζ当采用轮盘赌方式进行选择复制时,调整后的适应函数在温度高时(遗传算法早期)计算出的各染色体适应函数值差异较小,因此染色体被选择复制的概率相近,这样避免了个别好的染色体充斥整个种群,造成早熟;而当温度不断下降时,目标函数值相近的染色体适应函数值差异逐渐增大,从而使得优秀染色体的优势更加明显,避免了种群进化停滞不前Ζ315 遗传算法的选择复制根据适应函数值的大小进行群体选择,选择方法采用常用的轮盘赌选择法Ζ因简单遗传算法不具有全局收敛性[2],因此对算法进行改动,实施了最优保留策略,即运算开始时,把初始种群中最大适应函数值对应的染色体记录在染色体数组的第0位(如ch r[0]),每代进化完后,计算出ch r[0]染色体在当前温度下对应的适应函数值,如果小于1,则把当前代最大适应函数值对应的染色体赋给ch r[0];如果等于1,则不进行操作Ζ染色体ch r[0]只起记录功能,不参与遗传运算Ζ实施了最优保留策略的遗传算法将收敛到全局最优解Ζ316 基因操作——交叉、变异本文采用改进的自适应交叉、变异操作,其交叉率P c和变异率P m的计算公式为:P c=k1+k2(f it m ax-f it′i),(f it m ax-f it avg)f it′i≥f it avg,k3,f it′i<f it avg.(8)P m=k4+k5(f it m ax-f it i),(f it m ax-f it avg)f it i≥f it avg,k6,f it i<f it avg.(9)式中k1、k2、k3、k4、k5、k6为常数,且k3=k1+k2,k6=k4+k5;f it m ax、f it avg分别为当前代进化群体的最大和平均适应函数值;f it′i为两个交叉个体中较大的适应函数值Ζ这样在操作过程中,适应函数值小的个体,具有较大的交叉率和变异率,这样有利于加快搜索速度,且最大适应函数值对应染色体的交叉率和变异率不为零,而为一较小值Ζ当遗传算法陷入问题的局部极值时,即f it avg→f it m ax时,根据式(8)和(9),适应函数值较大的个体对应的P c、P m也将增大,这样有利于避免“早熟”Ζ但太大的P c、P m有可能造成解空间过于分散,甚至可能导致原有的解被破坏Ζ为此,一旦f it m ax-f it avg<Ε2时,就固定P c、P m值,以避免原有解空间被完全破坏Ζ交叉操作时,因两点交叉比单点交叉具有更好的空间搜索能力,而又比均匀交叉的破坏能力低,因此采用两点交叉Ζ当普通交叉方法的两个父个体在交叉范围内的基因相同时将不能产生新个体,为了增强算法的搜索能力,本文中交叉方法采用的是部分随机两点交叉[3](Partially R andom ized22Po in t C ro ssover),该方法主要分成两步:第一步,按照标准的两点交叉产生两个子个体;第二步,在其中一个子个体中随机选择一段长度为l PRC的基因代码,并以一定概率P PRC变化其中模板位置上的基因,使该子个体发生变化Ζ如图1所示Ζ其中可以定义P PRC=l PRC (2・N CS),N CS为在长度为l PRC的基因代码中,两个染色体具有相同基因位的数量Ζ这样定义的P PRC具有一定的适应性,因为在初始种群中各二进制位产生0、1的概率相同,因此N CS的均值为l PRC 2,从而P PRC=1(当N CS<l PRC 2时,同样取P PRC=1),当程序运行到末期时,N CS逐渐趋于l PRC,从而P PRC趋于015Ζ同时为了避免该方法产生过大的破坏作用,两个子个体是否进入下一代采用如下的判断策略:如果生成的两个子个体中至少有一个个体的适应函数值大于或等于两个父个体中较高的适应函数值,则两个子个体同时进入下一代;否则,较好的父个体和较好的子个体进入下一代Ζ变异操作时,如果采用普通的单点变异就会造成配电网络形成环网或出现“孤岛”的情况,因此,变异421系统工程理论与实践2004年11月图1 部分随机两点交叉示意图操作时其它基因位需作相应变化,设选中了染色体的某一位进行变异,如0变1,与此同时,应将该染色体中另外一个或几个为1的相关位变成0,反之亦然Ζ这样操作可以避免大量不可行解的产生,提高计算效率Ζ317 模拟退火操作以经过遗传算法选择复制、交叉、变异操作的群体作为模拟退火算法的初始群体,运用基于M etropo lis 判别准则的复制策略,产生下一代群体Ζ即在染色体的邻域中随机产生新个体j ,i 和j 竞争进入下一代群体的准则采用M etropo lis 判别准则:令∃f =f it i -f it j ,若∃f ≤0,则把染色体j 复制到下一代群体;否则产生[0,1]之间的随机数r ,如果r <exp (-∃f t n ),则同样把染色体j 复制到下一代群体,否则,把染色体i 复制到下一代群体Ζ基于M etropo lis 判别准则的复制策略,在接受优质解的同时,有限度的接受劣质解,保证了群体的多样性,进一步避免了算法陷入局部最优解的可能性Ζ318 终止规则算法终止规则要满足两个条件:首先,染色体数组的第0位ch r [0]连续q 代没有发生变化;其次,惩罚项M p 应小于Ε1Ζ当同时满足这两个条件时,即可认为算法收敛,停止计算,输出最优解Ζ319 算法计算过程ST EP 1 给定群体规模p op siz e ,和算法中其它系数值,具体如下:惩罚因子M 0,以及惩罚因子放大系数c ,确定初温时的系数K ,退温时的系数Α,交叉和变异操作时的系数k 1、k 2、k 3、k 4、k 5、k 6、l PRC ,对P c 、P m 实施固定时的系数Ε2,算法终止规则中的q 和Ε1;ST EP 2 随机产生p op siz e 个染色体作为初始种群p op (0),计算各染色体的目标函数值,确定初温,令算法迭代次数n =0,初始最优解s 3=f m in ,并用ch r [0]记录下最优染色体,用g 表示该染色体保持的代数,令g =1;ST EP 3 根据染色体的适应函数值,按当前各染色体的交叉概率P c 执行遗传算法的交叉操作,生成种群p op ′(n );ST EP 4 根据染色体的适应函数值,按当前各染色体的变异概率P m 执行遗传算法的变异操作,生成种群p op ″(n );ST EP 5 执行基于M etropo lis 判别准则的复制策略,生成种群p op (n );ST EP 6 计算各染色体的适应函数值,采用轮盘赌方法进行群体选择,生成下一代种群p op (n +1),同时实施最优保留策略(计算出ch r [0]染色体在当前温度和惩罚因子下对应的适应函数值,如果小于1,则更新ch r [0],并令s 3=f m in ,g =1;如果等于1,则令g =g +1);ST EP 7 判断g 是否大于q ,惩罚项M p 是否小于Ε1,如果是,则停止计算,输出优化结果Ζ此时的ch r [0]为最优开关状态组合,s 3为最小网损Ζ否则,执行ST EP 8ΖST EP 8 执行退温操作,t n +1=Αt n ,并增大罚因子,M r +i =c M r ,令n =n +1,返回ST EP 3Ζ混合遗传算法的结构流程图见图2Ζ4 算例根据本文算法,用C ++B u ilder 510编制了网络重构程序,并以大庆油田某区块6kV 配电线路为例进行了试算Ζ计算信息如下:此系统共有3个变电所、338条线段、129台变压器和26个开关Ζ计算时染色体长度L 等于开关总数26,令群体规模p op siz e =2L =52,算法中各系数确定如下:惩罚因子M 0=5,惩罚因子放大系数c =115,选择确定初温系数K =20,退温操作系数Α=018,交叉操作系数k 1=012、k 2=016、k 3=k 1+k 2=018、l PRC =5,变异操作系数k 4=0101、k 5=011、k 6=k 4+k 5=0111,为防止解空间被破坏,当Ε2=015f it avg 时,交叉率和变异率固定为012和0101,算法终止规则中q =20,Ε1=0101Ζ521第11期基于混合遗传算法的配电网络重构优化图2 混合遗传算法的结构流程图优化结果见表1Ζ从优化结果中可以看到,不但配电网网损率降低了117%,而且配电网末端电压质量得到了明显改善Ζ表1 系统优化前后对比表配电网功率总损耗(kw )配电网网损率(%)配电网末端最大压降(%)处于打开状态的开关处于闭合状态的开关优化前250.2465.97.966K 2、K 6、K 9、K 10、K 14、K 17、K 18、K 19、K 21、K 22、K 24K 1、K 3、K 4、K 5、K 7、K 8、K 11、K 12、K 13、K 15、K 16、K 20、K 23、K 25、K 26优化后177.7244.24.408K 2、K 6、K 7、K 10、K 14、K 15、K 18、K 20、K 22、K 24、K 25、K 26K 1、K 3、K 4、K 5、K 8、K 9、K 11、K 12、K 13、K 16、K 17、K 19、K 21、K 235 结论本文对遗传算法的操作进行了改进,尽量避免了早熟收敛现象Λ此外混合遗传算法的搜索行为还可以通过初温和退温函数加以控制Λ该算法结合了遗传算法和模拟退火算法的特点,两种算法的搜索能力得到了相互补充,使算法在优化能力、效率和可靠性方面得到了提高Λ在求解过程中,用开关状态作为染色体的编码,简洁明了,同时考虑了配电网络自身特点,极大地提高了计算效率Λ621系统工程理论与实践2004年11月参考文献:[1] 施光燕,董加礼.最优化方法[M ].北京:高等教育出版社,2001.78-81.SH I Guang 2yan ,DON G J ia 2li .M ethods of Op ti m izati on [M ].Beijing :H igher Educati on P ress ,2001.78-81.[2] 邢文训,谢金星.现代优化计算方法[M ].北京:清华大学出版社,1999.181-182.X I N G W en 2xun ,X IE J in 2x ing .M odern Op ti m izati on Compu tingM ethods [M ].Beijing :T singhua U n iversity P ress ,1999.181-182..[3] J ir íKubal ík ,J ir íL azan sky .A new genetic operato r m ain tain ing popu lati on diversity [J ].A IP ConferenceP roceedings ,2001,573(1):338-348.(上接第48页)的问题转化为多类分类问题Λ同时,在讨论了现有的多类分类器不足的基础上,提出了一种基于可行域解析中心的多类分类器:M 2A C M Λ实验结果说明了M 2A C M 具有强的泛化能力,同时也说明了本文提出的时间序列预测方法是有效的且有较高的实用性Λ参考文献:[1] Peter J .B rockw ell et a l .T i m e Series :T heo ry and M ethods ,Sp ringer 2V erlag W o rld Pub lish ing Co rpo rati on ,1991.[2] 安鸿志.非线性时间序列分析[M ].上海科学技术出版社,1998.A n Hongzh i .N on 2linear T i m e Series A nalysis (In ch inese )[M ].Shanghai Science P ress ,1998.[3] Bai 2L ing zhang ,et a l .M u ltireso lu ti on fo recasting fo r fu tu re trading u sing w avelet decompo siti on s [J ].IEEE T ran son N eu ral N etw o rk s ,2001,12(4):765-775.[4] Khalaf A M ,et a l .T i m e series p redicti on u sing a hyb rid model of neu ral netw o rk and F I R filter [A ].P roc I JCNN ’98[C ],1975-1980,1998.[5] O fer D ekel ,Yo ram Singer .M u lticlass learn ing by p robab ilistic em beddings [J ].A dvances in N eu ral Info rm ati onP rocessing System s ,2002,15:945-952.[6] E rin A ll w ein ,et a l .R educing m u lticlass to b inary :a un ifying app roach fo r m argin classifiers [J ].Jou rnal ofM ach ineL earn ing R esearch ,2001,1(2):113-141.[7] E rin J B reden steiner ,et a l .M u lticatego ry classificati on by suppo rt vecto r m ach ines [EB OL ].h ttp : mpa .itc .itb ib li o papers b reden steiner 99m u lticatego ry .pdf .[8] A Smo la ,et a l .A dvances in L arge M argin C lassifiers [M ].T he M IT P ress ,Cam b ridge ,M assachu setts ,2000.[9] T B T rafalis ,et a l .A n analytic cen ter m ach ine [J ].M ach ine L earn ing ,2002,46(1 3):203-223.721第11期基于混合遗传算法的配电网络重构优化。
