改进和声搜索算法用于配电网重构

梁杉，毛弋，刘小丽，彭文强，范幸，邓海潮

（湖南大学电气与信息工程学院，长沙410082）

改进和声搜索算法用于配电网重构

梁杉，毛弋，刘小丽，彭文强，范幸，邓海潮

（湖南大学电气与信息工程学院，长沙410082）

针对配电网重构大规模非线性混合整数规划的特点，提出采用通过粒子群算法控制参数进化的改进和声搜索算法对配电网进行重构。首先，将粒子群算法引入和声搜索算法，用于智能引导和声搜索算法参数的进化；然后，提出新的支路组断开原则及其相关概念。通过上述改进克服固定参数设置对和声搜索算法搜索能力的制约，提高算法的全局寻优性能并有效减少不可行解的生成。最后，将上述方法和原则结合对IEEE33节点系统以及PG&E69节点系统进行仿真，得到的仿真结果验证了该方法的准确性和有效性。

配电网重构；粒子群算法；参数进化；和声搜索算法；支路组断开原则

配电网重构是指在保证网络维持辐射状结构、满足线路电流、电压幅值和变压器容量等约束的前提下，寻找一种使得网络损耗、电压质量以及负荷均衡等指标获得最优值的网络结构。它是一个大规模非线性混合整数规划问题，其关键点是重构过程中采用的算法是否能够迅速准确地找到全局最优解，以及如何减少不可行解的生成。

目前用于解决配电网重构问题的算法主要有：①传统数学优化算法[1]，如线性规划法；②启发式方法，主要是支路交换法[2]和最优流模式算法[3]；③人工智能算法，如模拟退火算法、遗传算法、免疫算法和粒子群算法等[4-7]。各类算法均存在某些不足，以至难以运用于实际中。

和声搜索HS（harmony search）算法从提出到现在已有多种改进。文献[8]通过扩大最优和声搜索区域并引入受和声库影响的微调变量，增强算法跳出局部最优的能力，将改进算法用于电力负荷预测并提出相应的负荷预测方法。文献[9-10]分别将改进后的和声搜索算法用于输电网规划以及印度公用电力系统的短期优化中。

本文提出采用基于粒子群算法的参数协进化改进和声搜索算法进行配电网重构。将重构问题的解，即和声记忆库中的解向量作为原始个体，将和声库选择概率HMCR（harmony memory considering rate）和音调调节概率PAR（pitch ad⁃justing rate）看作原始个体的共生个体。和声搜索算法用于原始种群的进化，同时将粒子群算法用于共生种群的进化。提出新定义下的T型点及其分类，并规定相应的支路组断开原则，以减少不可行解的生成。

1 配电网重构的数学模型

配电网重构的优化目标有很多种，例如网络损耗最小、负荷均匀分布以及提高供电系统的稳定性和可靠性等。本文以网络损耗最小作为重构目标，其数学表达式为

式中：Ploss表示网损；kj表示支路j的开闭情况，其值为1表示支路闭合，为0表示支路断开；rj为支路j的电阻；Pj和Qj分别为流过支路j的有功功率和无功功率；Uj为支路j的末端电压；b为网络的支路数量。

配电网重构的约束条件主要有电压约束、支路容量约束和网络辐射状结构约束等，数学表达式为

式中：Ui、UUi、ULi分别为节点i的电压及其变化范围的最大最小值；Sj和Sjmax分别为线路j流过的功率及最大容许值；g为当前网络结构；G为所有既没有环网又没有孤岛的辐射状结构的集合。

2 基于粒子群的参数协进化和声搜索算法

和声搜索算法的原理简单易懂，控制参数少，编程简单，但是在算法后期不易得到全局最优解、且算法收敛不稳定[11]。因而，陆续出现了各种改进的和声搜索算法，如文献[12]和文献[13]中的改进算法。

2.1 和声搜索算法基本原理

和声搜索算法将演奏各种乐器组成的和声等价于优化目标函数中的解向量，单独一个乐器相当于解向量中的一维变量，各个乐器的音调幅度相当于解向量各维变量的取值范围，对和声的评价相当于目标函数值，音乐家为得到优美和声而对乐器的不断调试相当于搜索最优解向量的过程。音乐家演奏新的音调由3种途径产生，第1种是根据音乐家积累的经验弹奏一个音调，第2种是弹奏一个与原来音色相近的音节，第3种是在音调幅度范围中随机弹奏某个音节。和声搜索算法仿照这一机制，采用类似的方法搜索新的和声向量各维变量的取值，第1种是从和声记忆库HM中选择对应维的一个值，第2种是产生一个与和声记忆库HM中可行解相近的值，该过程称为音调调节，第3种是在变量的取值范围中随机选择一个值。

2.2 参数对算法的影响

和声搜索算法是基于和声库选择概率HMCR、音调调节概率PAR和音调调节带宽bw等参数的智能优化算法。这些参数的选择直接影响着算法的全局寻优能力以及寻优速度。然而参数的合理设置缺乏一般性准则，大部分使用和声搜索算法的研究都采取根据经验选择固定参数值的方式，这种方式在一定程度上制约了算法的搜索能力。

在原始的和声搜索算法中，常常设定算法的参数为常数，具体取值根据处理问题的不同而存在差异。在算法前期，一般将HMCR设置为较大的值，PAR设置为较小值。当迭代进行到后期，因为PAR取值较小，这时，即使HMCR取值较大，亦难以搜索到更好的新解。可见，和声搜索算法的局部寻优能力较弱，算法进行到后期容易陷入局部最优解。因而本文算例在选取HMCR和PAR的值时，将设置在一定取值区间内变化，根据前述内容，设置HMCR取值范围靠近1而PAR的取值范围靠近0。

2.3 基于粒子群的参数协进化和声搜索算法

粒子群算法中，每个粒子按照一定速度在多维空间里飞行搜索。在搜索过程中，每个粒子记住到目前为止自身搜索到的最优位置（个体最优解），同时，所有粒子间通过信息交换可知道并记住整个群体当前找到的最优位置（全体最优解）。全体粒子均以个体最优解、全体最优解及自身速度为基础不断更新自己的搜索速度，最终找到全局最优解。

由于在算法不断迭代进行的过程中，固定的参数设置制约了和声搜索算法的寻优能力，本文把和声搜索算法的主要参数和声库选择概率HMCR和音调调节概率PAR当作经过进化过程的个体，并采用粒子群算法控制其进化，以期望更合理的控制参数能产生更好的且容易保留下来的子代个体，进而得到更合理的参数值。下面介绍如何将粒子群算法用于和声搜索算法参数的进化。

步骤1初始化。设定和声记忆库大小HMS（harmonymemory size）及共生种群大小PSnum，初始化原始种群HM和共生种群PS0。共生种群的每一个粒子为[HMCRi,PARi]（i的取值是1，2，…，PSnum），各粒子的第一维分量即HMCRi随机分布在其取值范围的上半部分，第二维分量即PARi随机分布在其取值范围的下半部分。设定和声搜索算法迭代次数的最大值MaxItr、当前代数currentItr=1、Tmax（即共生种群的一个粒子在更新前被调用次数的最大值）和当前调用次数T=1，设定粒子群算法的控制参数w、c1和c2，生成共生种群中每一个粒子的初始速度向量vi，共生种群个体调用指针i=1，粒子群当前代数设置为C=0。

步骤2进化原始种群。

（1）从PSC中选择第i个粒子[HMCRi,PARi]，结合当前的和声记忆库HM生成一个新解（i对应于被选中的粒子[HMCRi,PARi]），具体过程如下。

生成新和声解向量的每一维分量时，先产生一个随机数ran并与HMCRi进行比较，当ran小于HMCRi时有

否则有

当currentItr不为指定迭代次数时有

式中，xbest,ii是HM中最优解的第ii维分量；bw根据和第ii维变量的上下限决定。

若i＜PSnum成立，则i=i+1，重复步骤（1）。

若i＜PSnum不成立，则重置i=1；currentItr=currentItr+1，若currentItr大于MaxItr成立，结束迭代，若不成立则转到步骤（2）。

（2）根据生成的PSnum个新解以及原HM，选择其中适应度值最好的HMS个解更新HM，T=T+1。若T＞Tmax（Tmax表示共生种群的一个粒子在更新前被调用次数的最大值）成立，转步骤（3）并置T=1，若不成立，返回步骤（1）。

（3）对PSC中每一个粒子，通过由其生成的Tmax个解向量的适应度均值来评价其优劣为式中：i=1,2,…,PSnum；表示由PSC中第i个粒子生成的Tmax个解向量的适应度均值。

步骤3进化共生种群生成PSC+1。

式中：w为惯性因子；c1和c2为学习因子；和分别为中第i个粒子速度向量的第1和第2维分量；和分别为PSC中第i个粒子个体最优解的第1和第2维分量；gb1和gb2分别为第C代粒子中全体最优的第1和第2维分量。

HMCR和PAR更新完后，C=C+1。

步骤4重复步骤2和步骤3，直到迭代结束。

3 支路组断开原则

辐射型配电网中，合上一个联络开关后将形成一个环网，本文引入文献[14]，将该环网称为重构环。只要能确定每个重构环中打开的开关，即断开的支路，就能得到配电网的一种结构。因而本文应用和声搜索算法于配电网重构时，采用十进制编码，算法解向量的维数即网络中的重构环数，解向量每一维的取值均为断开支路在各自重构环中的编号，每一维变量的范围即为相应重构环中支路的数量。

3.1 T型点及其分类

由于和声搜索算法随机搜索的特点，必然会产生不可行解，为减少不可行解的产生，本文根据网络拓扑结构定义新的“T型点”等概念，具体定义如下：①支路组：所处重构环完全相同的几条支路，称为一个支路组。根据这一定义，可以得到图1所示IEEE33节点系统中的12个支路组，分别为：6-7、8、9-10-11、12-13-14、25-26-27-28、15-16-17-29-30-31-32-37、3-4-5、22-23-24-33、2-18-19-20、34、21-35和36。②独立支路组：只存在于一个重构环中的支路组。③公共支路组：存在于两个及以上重构环中的支路组。④T型点：不考虑支路的开闭状态，连接3个支路组的节点，称为T型点。⑤第1类T型点：若某T型点所连支路组全部为公共支路组或者有两个为公共支路组一个为独立支路组，则将该T型点称为第1类T型点。根据该定义，图1中节点（3）、（6）、（8）、（9）和（12）为第1类T型点。⑥第2类T型点：若某T型点所连支路组有一个为公共支路组两个为独立支路组，则将该T型点称为第2类T型点。根据该定义，图1中节点（15）、（21）和（29）为第2类T型点。

3.2 支路组断开原则

由前文所述可知，只要能够确定每个重构环中断开的支路，就能得到一个和声解向量。基于上述定义，考虑根据下面几条支路组断开原则，减少不可行解的生成。

（1）生成新和声解向量每一维分量时，每个重构环中只选择一个未被选中过的支路断开；

（2）重构过程中，一个支路组最多只能打开一条支路；

（3）对于任意一个第1类T型点，其所连接的3个支路组中，最多只能有两条属于不同支路组的支路断开；

（4）重构过程中，若某一第2类T型点已经断开两条属于不同支路组的支路，且一条为公共支路组支路一条为独立支路组支路，则规定之后的重构中不能打开剩下的独立支路组的支路。

3.3 可行解的生成步骤

根据上述支路组断开原则，可以得到可行解生成过程中修改支路标志位的步骤：

（1）给所有支路一个标志位，初始化时将标志位均置为0；

（2）生成解向量的某一维分量时，判断选出的支路标志位是否为0，若是则将其赋予给该分量，若否则重新选择；

（3）先将选出的支路以及其所在支路组的所有支路的标志位都置1，然后考察第1类T型点和第2类T型点。若某一个第1类T型点连接的支路组中有两个支路组的标志位均为1，则根据支路组断开原则第⑶条，将另一个支路组所有支路标志位也置1。若某一个第2类T型点连接的支路组中有两个支路组的标志位为1，且这两个支路组一个为公共支路组另一个为独立支路组，则根据支路组断开原则第⑷条，将剩下的独立支路组所包含的所有支路标志位均置1。

（4）新的解向量各维变量都生成后，将所有支路的标志位还原。

4 算例

本文用IEEE33节点系统以及PG&E69节点系统作为算例验证本文算法，各系统详细参数见文献[15-16]。PG&E69节点系统各支路编号见图2。

设置IEEE33系统的MaxItr=100，PG&E69系统的MaxItr=150，两个算例中其他参数均为：HMS= 10，PSnum=10，Tmax=3，w=0.8，c1=2，c2=2，HMCRmax=0.95，HMCRmin=0.65，PARmax=0.55，PARmin=0.25。重构结果列在表1、表2和表3中。

从表1和表2可知，采用本文算法进行重构后IEEE33系统和PG&E69系统网损分别降低31.1%和55.5%。从表3可发现，经本文算法重构的IEEE33系统电压最低值由重构前的0.913 1p.u.上升到重构后的0.937 8p.u.，PG&E69系统电压最低值由重构前的0.908 1p.u.上升到重构后的0.942 5p.u.。由此可见，应用本文算法重构后的网络损耗和节点电压最低值都得到了显著改善。通过与其他文献方法提供的数据比较，可证明本文所提方法的正确性。将本文算法连续运行100次的结果与文献[17-21]提供的数据进行对比，列在表4中。

从表4可以看出，本文算法得到的结果中除了IEEE33系统的最大计算次数和平均计算次数略逊色于文献[18]对应的数据之外，本文算法的结果均优于其他数据，特别是最小计算次数，不仅明显优于其他算法，且两个系统均在计算30次，即迭代3次后收敛到全局最优解。由此可知，本文算法具有更快的收敛速度。

5 结语

本文将粒子群算法引入和声搜索算法并用于和声搜索算法参数的进化，避免了传统固定参数以及按一定规律变化的参数对算法全局搜索能力以及搜索速度的制约，通过智能算法引导和声搜索算法参数的进化，进而更好的搜索适应度值更优的和声。本文提出新的T型点定义及其分类，并规定新的支路组断开原则，有效减少不可行解的生成，提高搜索全局最优解的效率。算例结果表明，本文方法不仅能够准确地搜索到全局最优解，并且具有更好的收敛速度。

[1]Sarma N D R，Prakasa Rao K S.A new 0-1 integer pro⁃grammingmethod of feeder reconfiguration for lossmini⁃mization in distribution systems[J].Electric Power System Research，1995，33（2）：125-131．

[2]毕鹏翔，刘健，张文元（BiPengxiang，Liu Jian，ZhangWe⁃nyuan）.配电网络重构的改进支路交换法（A refined branch-exchange algorithm for distribution networks re⁃configuration）[J].中国电机工程学报（Proceedings of the CSEE），2001，21（8）：98-103．

[3]邓佑满，张伯明，相年德（Deng Youman，Zhang Boming，Xiang Niande）.配电网络重构的改进最优流模式算法（An improved optimal flow pattern algorithm for distribu⁃tion network reconfiguration）[J].电网技术（Power Sys⁃tem Technology），1995，19（7）：47-50．

[4]胡敏羑，陈元（Hu Minyou，Chen Yuan）.配电系统最优网络重构的模拟退火算法（Simulated annealing algo⁃rithm of optimal reconstruction in distribution system）[J].电力系统自动化（Automation of Electric Power Sys⁃tems），1994，18（2）：24-28．

[5]刘莉，陈学允（Liu Li，Chen Xueyun）.基于模糊遗传算法的配电网络重构（Reconfiguration of distribution net⁃works based on fuzzy genetic algorithms）[J].中国电机工程学报（Proceedingsof the CSEE），2000，20（2）：66-69．

[6]蒙文川，邱家驹（MengWenchuan，Qiu Jiaju）.基于免疫算法的配电网重构（An artificial immune algorithm to distribution network reconfiguration）[J].中国电机工程学报（Proceedingsof the CSEE），2006，26（17）：25-29．

[7]唐贤伦，程祥，汪斌全（Tang Xianlun，Cheng Xiang，Wang Binquan）.采用多Agent混沌粒子群算法的配电网重构（Distribution network reconfiguration aaopting chaos particle swarm algorithm ofmulti-agent system）[J].电力系统及其自动化学报（Proceedings of the CSU-EP⁃SA），2015，27（3）：17-23．

[8]江鑫，刘晓华，高荣（Jiang Xin，Liu Xiaohua，Gao Rong）.基于改进全局和声搜索算法LSSVM的短期电力负荷预测（Short-term load forecasting based on a combination of an improved global harmony search algorithm and LSS⁃VM）[J].计算技术与自动化（Computing Technology and Automation），2012，31（2）：62-65．

[9]聂宏展，赵丹，段柯均，等（Nie Hongzhan，Zhao Dan，Duan Kejun，etal）.基于混沌自适应分组和声搜索算法的输电网规划（Transmission network planning based on chaos adaptive grouping harmony search algorithm）[J].电力系统保护与控制（Power System Protection and Con⁃trol），2014，42（19）：32-36．

[10]任苹，李楠（Ren Ping，LiNan）.基于差分和声搜索算法的短期电力系统优化调度（Optimal short-term hydro⁃thermal scheduling based on differential harmony search algorithm）[J].新型工业化（The Journal of New Industri⁃alization），2014，4（4）：32-38．

[11]黄哲（Huang Zhe）.基于改进和声搜索算法的配电网重构研究（Study on Distribution Network Reconfiguration Based on Improved Harmony Search Algorithm）[D].南宁：广西大学电气工程学院（Nanning：College of Elec⁃tricalEngineering，GuangxiUniversity），2013．

[12]MahdaviM，Fesanghary M，Damangir E.An improved har⁃mony search algorithm for solving optimization problems [J].Applied Mathematics and Computation，2007，188（2）：1567-1579．

[13]Omran M G H，Mahdavi M.Global-best harmony search [J].Applied Mathematics and Computation，2008，198（2）：643-656．

[14]江亚群，陈祝峰，黄纯，等（Jiang Yaqun，Chen Zhufeng， Huang Chun，etal）.基于启发式规则与和声搜索的配电网重构算法（Distribution network reconfiguration based on heuristic rules and harmony search algorithm）[J].湖南大学学报：自然科学版（Journal of Hunan Uni⁃versity：Natural Sciences），2014，41（3）：61-67．

[15]Baran M E，Wu F F.Network reconfiguration in distribu⁃tion systems for loss reduction and load balancing[J]. IEEETranson Power Delivery，1989，4（2）：1401-1407．

[16]朱春涛（Zhu Chuntao）.基于粒子群遗传混合算法的配电网重构研究（Study on Distribution Network Reconfigu⁃ration Based on PSOGA Hybrid Algorithm）[D].南京：南京理工大学自动化学院（Nanjing：Schoolof Automation，Nanjing University of Science&Technology），2012.

[17]董思兵（Dong Sibing）.基于免疫二进制粒子群算法的配电网重构（Distribution Network Reconfiguration Based on Immune Discrete Particle Swarm Optimization）[D].济南：山东大学电气工程学院（Jinan：School of Electrical Engineering，Shandong University），2008．

[18]王超学，崔杜武，崔颖安，等（Wang Chaoxue，CuiDuwu，CuiYingan，etal）.使用基于中医思想的蚁群算法求解配电网重构（Distribution network reconfiguration using a novelant colony system based on traditional Chinesemed⁃icine theory）[J].中国电机工程学报（Proceedings of the CSEE），2008，28（7）：13-18．

[19]宫林，王昕，刘斌，等（Gong Lin，Wang Xin，Liu Bin，et al）.隔离小生境遗传算法在配电网络重构中的应用（Application of isolation niche genetic algorithm to power distribution system reconfiguration）[J].电力系统及其自动化学报（Proceedings of the CSU-EPSA），2011，23（4）：143-147．

[20]孙涛，朱生鸿，李玥，等（Sun Tao，Zhu Shenghong，Li Yue，etal）.改进的分布估计算法在配网重构中的应用（Improved estimation of distribution algorithm in the ap⁃plication of distribution network reconfiguration）[J].电力系统及其自动化学报（Proceedings of the CSU-EPSA），2014，26（6）：54-59．

[21]李鹏（Li Peng）.基于群搜索优化算法的配电网重构（Distribution Network Reconfiguration Based on Group Search Optimizer）[D].长沙：湖南大学电气与信息工程学院（Changsha：Institute of Electrical and Information Engineering，Hunan University），2011．

Im proved Harmony Search Algorithm for Distribution Network Reconfiguration

LIANGShan，MAOYi，LIU Xiaoli，PENGWenqiang，FAN Xing，DENGHaichao
（College ofElectricaland Information Engineering，Hunan University，Changsha410082，China）

Considering the characteristics of large scale nonlinearmixed integer programming for distribution network reconfiguration，an improved harmony search algorithm is proposed，which controls the parameter evolution of by parti⁃cle swarm algorithm．First，particle swarm algorithm is introduced to harmony search algorithm to smartly guide the pa⁃rameter evolution．Then，new disconnecting rules of branch groups and their related concepts are also proposed.By overcoming the constraints on the search capabilities due to fixed parameters，global optimization performance is im⁃proved and the generation of infeasible solutions is reduced.Finally，by combining the abovemethod and principles，the accuracy and effectiveness of the proposed algorithm are verified by simulation on IEEE 33-node system and PG&E 69-node system．

distribution network reconfiguration；particle swarm algorithm；parameter evolution；harmony search algo⁃rithm；disconnecting rulesofbranch groups

TM727.2

A

1003-8930（2017）03-0090-06

10.3969/j.issn.1003-8930.2017.03.015

梁杉（1991—），女，硕士研究生，研究方向为配电网自动化。Email：ysdhls@163.com

2015-09-01；

2016-06-07

毛弋（1965—），男，硕士，副教授，研究方向为电力系统负荷预测、电力系统规划、电力市场。Email：maoyidu@aliyun.com

刘小丽（1989—），女，硕士研究生，研究方向为电网脆弱线路辨识。Email：738776439@qq.com