基于启发式规则与和声搜索的配电网重构算法*

江亚群,陈祝峰,黄 纯,曹一家,孙彦广,贾天云

(1.湖南大学 电气与信息工程学院,湖南 长沙 410082; 2.冶金自动化研究设计院,北京 100071)

配电网中包含有大量的常闭分段开关和少量的常开联络开关，配电网重构就是通过操作这些开关的开断来改变网络结构，从而降低配电网损耗、均衡负荷、消除过载、提高供电电压质量，使网络处于更优的运行状态．

配电网重构是一个大规模非线性混合整数规划问题，目前常用的算法可分为以下几类：(ⅰ)传统数学方法，包括规划法[1]、分支定界法[2]、单纯型法[3]等，这类方法可以得到不依赖于配电网初始结构的全局最优解，但属于贪婪搜索算法，计算时间长，难以实际应用．(ⅱ)启发式算法，包括支路交换法[4-5]、最优流模式算法[6]等，这类算法结合配电网重构问题的物理特性，简单、直观但不是理论上的全局最优．(ⅲ)人工智能算法，包括遗传算法(GA)[7]、禁忌搜索法(TS)[8]、蚁群优化算法(ACO)[9]、免疫算法[10]以及综合这些方法的混合法[11]等．这类算法具有全局最优、准确性高的特点，但计算量大，重构时间长．和声搜索(Harmony search，HS)算法是2001年韩国学者Geem Z W等人提出的一种智能优化算法[12]．该算法概念简单，参数少，不需要衍生信息，容易实现，寻优高效且与初始值无关．文献[13]将HS算法应用于配电网重构并取得了较好效果．

然而实际配电网规模大，需优化的开关组合数多，HS算法的随机搜索会得到大量的不可行解和非有效解，导致不必要的网络约束分析及潮流计算，增加了网络重构计算时间，降低了寻优稳定性．本文根据配电网重构的网络结构要求及HS算法特点，提出特殊支路组的概念；结合基于重构环解的编码方式，通过设置支路断开原则避免不可行解的产生；利用启发式规则缩小重构环有效解范围，提高搜索效率．IEEE典型算例的仿真测试表明，本文方法计算效率高，收敛速度快，稳定性好，且收敛特性不随网络规模的变大而变差．

1 配电网重构的数学模型及优化算法

1.1 配电网重构的数学模型

1.1.1 经济性重构的目标函数

配电网重构的目标有多种，本文以网损最小为目标函数进行经济性重构．对于一个含n个节点b条支路的网络，目标函数表达式为：

(1)

式中：ki为支路i的状态，ki=1为支路闭合，ki=0为支路断开；ri为支路i的电阻；Pi，Qi为支路i末端流过的有功功率和无功功率；Ui为支路i末端节点电压；b为支路数．

1.1.2 配电网重构的网络拓扑约束

配电网重构要求重构后的网络呈辐射状，无环路和孤立节点．根据这一要求，将所有联络开关闭合后，不在任何一个环网中的支路必须保持闭合，断开支路只能从环网中选择且断开条数为联络开关数[11]．为便于叙述，本文称单个联络开关闭合后形成的环网为重构环，重构解(ki的组合)即为各重构环中断开支路的组合．

1.1.3 重构潮流约束

配电网重构还必须满足电压约束和支路容量约束，即：

(2)

(3)

式中：Ujmax,Ujmin为节点j的电压上下限；n为节点总数；Si,Simax为支路i上的功率及其最大允许容量．

1.2 基于HS算法的重构

1.2.1 算法简介

HS算法模拟的是音乐创作中乐师凭借自己的记忆，通过反复调整乐队中各乐器的音调，最终达到一个美妙的和声状态的过程[12]．

将各重构环中断开支路类比于乐器的音调，重构解类比于声调的和声，目标函数值f对应和声状态的评价，即将HS算法引入了配电网重构．

1.2.2 和声向量编码

在HS算法寻优过程中，解向量的每一维决策变量是独立确定的，不影响也不受其它维决策变量的影响[12]．结合各重构环断开支路独立确定的特点，将HS算法解向量X设置为各重构环中断开支路的组合．采用整数的编码方式，以断开支路在重构环中位置的编号为决策变量，联络开关数目为解向量维数，编码如式(4)所示：

X=[x1,x2,…,xN]．

(4)

式中：xi为第i个重构环中断开支路的编号；N为重构环的个数．

1.3 重构改进策略

用HS算法进行配电网重构时，虽然采用上述编码方式能大大降低解向量的维数，给出的解向量大部分情况下满足网络拓扑要求 ，但由于配电网结构的复杂性及HS算法取值的随机性，在初始化和寻优过程中仍会产生大量的不可行解和非有效解．不可行解是指重构后的配电网络结构不满足辐射状约束，非有效解指的是重构后的网损更大．这两类解的存在极大地增加了配电网重构的搜索空间，降低了搜索效率，导致大量不必要的网络约束拓扑分析和潮流计算．因此，在优化过程中应尽可能地减少这两类解的产生．

2 重构环特殊支路组及支路断开原则

本节通过构建重构环特殊支路组、设定支路断开原则来满足重构网络拓扑要求，在上节和声向量编码的基础上，完全避免不可行解的产生．

2.1 重构环特殊支路组

为满足配电网重构的拓扑约束条件，断开支路只能从各重构环中选择．由于有些支路至少被2个重构环包含，重构时若被重复选择，则会造成不可行解，因此这类支路需特别处理．

本文引入文献[9]中关于“T型节点” 、“道路”、“公共道路”及“独立道路”的概念，基于重构环给出如下定义：①独立支路组：只被相同的一个重构环包含的多条支路；②公共支路组：同时被至少2个重构环包含的多条支路；③T型支路组：与T型节点相连且所有支路组至少处于3个重构环中的支路组集合；④第1类T型支路组：各边均为公共支路组的T型支路组；⑤第2类T型支路组：某一边为独立支路组的T型支路组．

根据上述定义，图1所示简单网络共有5个重构环，支路9-8-2-3、支路3-4、支路4-5、支路5-6、支路4-11-12为网络的5个公共支路组，依次编为公共支路组①②③④⑤；支路3-14-15-12、支路5-9、支路6-10-9、支路6-7-13-12是网络的4个独立支路组．T型节点3及其所连公共支路组①②和独立支路组3-14-15-12构成T型支路组T1，T型节点4及其所连公共支路组②③⑤构成T型支路组T2，T型节点5及其所连公共支路组③④和独立支路组5-9构成T型支路组T3；T2为第1类T型支路组，T1和T3为第2类T型支路组．

图1 某简单网络

2.2 重构环支路断开原则

配电网重构时，不在环网中的支路必须保持闭合状态；闭合一个联络开关形成环网时，则必须打开环网中的一条支路，恢复辐射状．

根据这个思路，每次重构时，只需确定每个重构环中的断开支路即可．结合上述支路分组，给出如下断开原则，以避免不可行解的产生．

1)重构时每个重构环中只断开一条支路，即有n个重构环就只断开n条支路．

2)重构时一个支路组只能断开一条支路，一个T型支路组最多只能断开两条支路．

3)重构时，若第2类T型支路组中独立支路组的某一条支路断开，由于T型支路组其它两边处于接下来选择断开支路的相同重构环中，故将这两边合并，代入各自所在的T型支路组中．图1所示网络，在重构中，若支路5-9断开，则T型支路组T3的公共支路组4-5，5-6同时处于重构环L6-10，L13-7中，故将支路4-5-6合并为一个公共支路组，代入T型支路组T2中．

2.3 和声向量可行解的确定

支路分组编号完成后，依照和声向量编码方式及上述原则，可行解的确定步骤如下:

1)初始化：给重构环中的所有支路一个标志位，初始化为“0”；解向量X=[x1,x2,…,xN]置空集．

2)标志位判断：利用HS算法从某个重构环中选出一条断开支路后，判断该支路的标志位是否为“0”，若是则将该支路在重构环中位置的编号赋予xi(i=1,2,…，N)，否则放弃该支路，重新选择．

3)标志位修改：将选出支路连同其所在支路组中其他支路的标志位改为“1”．若该支路为某一第2类T型支路组中独立支路组的支路，则将该T型支路组另外两边公共支路组的编号及标志位改为一致(若一边公共支路组支路标志位为“1”，则另一公共支路组中所有支路标为“1”)．标志位修改完后，若所处T型支路组有两边公共支路组中支路均标为“1”，则将第三边标志位修改为“1”．

4)还原：解向量决策变量xi全部确定后，所有支路组的分组编号及支路标志位还原．

3 重构的启发式规则

本节将全局寻优转化为各重构环的局部寻优，并利用启发式规则将各重构环的局部搜索范围确定在最有可能的更小有效范围内，来提高有效解的搜索效率．

3.1 基于重构环局部寻优的重构可行性分析

当重构环上的节点不再接有下游支路时，可将环内所有支路全部等效到最靠近电源的节点上．当环网内部支路发生交换时，重构环上连接负荷并未减少，忽略网损变化的影响，对外部的等效电路不变，故不会对外部支路造成影响．当重构环接有下游支路时，考虑到下游电压只能在约束范围内运行，节点电压变化很小，下游支路电流变化也很小，对外部支路影响很小[5]．

以图2所示IEEE 33配电系统[6]为例进行模拟验证．表1和表2给出了重构环L24-28内支路24-28和27-28交换前后环内外支路的网损变化情况．由表1，表2可见，支路交换后，重构环内每条支路的损耗变化率很大，最大的达到1 133.7%．而环外支路变化较小，其中馈线1-18-19-20-21网损的变化量为零；重构环L24-28外网损的变化总和仅1.86 kW，仅为负荷转移前该重构环外所有支路有功损耗的2.02%，影响很小．

图2 IEEE 33节点系统

表1 支路交换前后重构环内部分支路的网损变化

表2 支路交换前后重构环外馈线的网损变化

综上分析，重构环内支路交换时对环外支路线损造成的影响很小，全局寻优可转化为各重构环寻优．而单个重构环重构(其他环支路不动作)时，可以进一步确定其有效范围，这个有效范围是该环内能使该环网损降低的断开支路集合．要使全局网损减少，断开支路需从各重构环有效解范围中产生．

3.2 重构环有效范围的确定

将网络中某一联络开关确定的环网展开成双端供电网络，如图3所示．

图3 重构环示例

图3中，支路m-(m+1)为联络开关，初始状态断开．若支路以末端节点编号表示，原始状态网损为

(5)

(6)

馈线2到(m+1)节点侧的支路电流为：

(7)

(8)

馈线2到(m+1)节点侧的支路电流为：

(9)

联络支路m-(m+1)上的电流为：

(10)

闭合联络开关，断开支路k后的网损为：

(11)

转换前后的网损差为：

(12)

若断开环网中馈线2侧的某一条支路k时：

(13)

对于含有无功补偿的理想配电网来说，由于各点电压的相位差及电压、电流间的相位差基本可以忽略，可以使用实部计算代替向量计算[4]．一般地，假设联络开关两端编号为m，n，则式(13)转变为

(14)

式(14)第1部分为正数，第2部分是正是负取决于联络开关两节点的电压差，要使网损朝着降低的方向进行，必须是Um明显小于Un，即断开支路需从将联络开关电压低的一侧选择．

当支路电流值在0到2Iopt的支路断开时，ΔP为负，为有效搜索范围．网损减少最大时，支路电流Ik接近最优电流Iopt：

(15)

当Um和Un接近时，式(14)第2项近似为零，ΔP为正，即此时闭合联络开关，无论断开其他哪一条支路都将使网损增大．若要使网损增量最小，则要求断开支路的支路电流最小．考虑到其它重构环的影响，根据潮流流向可知，断开联络开关附近支路时网损增量最少，即断开支路的有效范围为此时联络开关及其附近的支路．

根据上述思路，在最优重构前，先求出初始状态下各重构环联络开关两端的电压差和Iopt，若联络开关电压差绝对值大于某一给定阈值ε(如0.01 pu)，则将搜索范围缩小到电压低的一侧，支路电流值在0～2Iopt的支路为其有效搜索范围；若电压差小于给定值，则将有效搜索范围缩小到联络开关附近的几条支路．图2所示的IEEE 33配电系统的有效搜索范围如表3所示．在有效搜索范围内，采用HS算法搜索重构全局最优解．

表3 IEEE 33节点系统有效搜索范围

4 重构算法实现步骤

本文重构算法通过构建重构环特殊支路组、确定支路断开原则来避免不可行解的方法是基于网络拓扑约束条件提出的，与网络电源数无关；基于环网损耗降低确定有效解范围的启发式规则，是在将环网展开成双馈线的情况下提出的，与该环网所处网络的电源数也无关．故本文重构算法在单电源或多电源供电的配电网具有良好的适用性．

4.1 算法实现步骤

本文经济性重构算法主要包括构建重构环特殊支路组，利用启发式规则确定各重构环有效解范围及结合支路断开原则利用和声搜索算法在有效解范围中全局寻优3个部分．具体实现步骤如下．

1)读入配电网的基本数据，形成配网拓扑结构并进行简化；

2)在简化后的拓扑结构中从每一个联络开关的一端起，采用深度遍历找出闭合该联络开关形成的重构环；以逆时针或顺时针方式给重构环各支路编号(同一支路在不同重构环中的编号可能不同)；

3)将重构环中支路编为支路组和T型支路组，识别步骤如下：

①在所有重构环中依次搜索每条支路，确定支路被各重构环包含的情况；将只被相同的一个重构环包含的多条支路编为一个独立支路组；将同时被至少2个重构环包含的多条支路编为一个公共支路组，并给支路组编号．

②查找度数大于2的节点，找出该节点连接的所有支路组；判断所有支路组是否被至少3个重构环包含，若是则将该节点各边所连支路编为一个T型支路组．

③判断T型支路组各边是否为公共支路组，若是则为第1类T型支路组，否则为第2类T型支路组．

4)利用启发式规则对初始网络进行分析，将各重构环搜索范围缩小到有效搜索范围中(方法详见3.2节)；

5)结合支路分组及断开原则，利用HS算法在有效范围中进行最优搜索，具体步骤见4.2节；

6)输出最优结果，算法结束．

4.2 HS算法实现步骤

HS算法首先初始化和声记忆库，然后通过记忆库学习、音调微调及随机选择3种机理产生新和声，若新和声优于记忆库中最差的和声，则用新和声替代最差和声，更新和声库；如此循环直至满足终止条件．结合配网重构，在支路分组编号完成后，HS算法具体实现步骤为：

1)初始化HS算法参数：包括解向量的维数N、和声记忆库的大小HMS、和声记忆库取值概率HMCR、微调概率PAR、音调微调带宽bw(由于决策变量是离散整数，故取为1)、创作次数Ntm和终止条件；

2)初始化和声库(HM)：从有效范围中随机产生HMS个和声向量放入HM中，向量的每维为支路在重构环中的位置编号，按式(1)计算和声向量的目标函数值，并按大小进行排序；

①初始化支路标志位，Xnew置空集；

④判断Xnew的所有维决策变量是否得到，若全部得到，所有支路组的分组编号及支路标志位还原，转步骤4)，否则转步骤②；

4)更新和声记忆库：计算新和声Xnew的目标函数值，若优于HM中最差和声，则用新和声替代最差和声，更新和声库；

5)判断是否达到终止条件：若满足，则停止迭代，否则转步骤3)．

5 算例分析

为了验证本文方法的可行性与有效性，选择IEEE 33配电网和IEEE 69配电网[14](图4)作为测试算例，分别用本文方法、文献[13]原始和声搜索算法及文献[9]蚁群算法进行网络重构．本文算法参数为：HMS=10，PAR=0.3，HMCR=0.85，Ntm=200；联络开关电压差比较阈值ε=0.01 pu．

图4 IEEE 69节点系统

利用本文算法得到的网络重构结果如表4所示，优化后的网络电压和网损得到了大幅改善，优化结果与已知文献重构最优结果相近[9]．

表4 网络重构结果

连续测试本文算法和文献[13]算法各100次，将算法性能统计指标与文献[9]提供的数据进行比较，结果如表5所示．表5中文献[9]蚁群算法计算次数为文献[9]提供的迭代次数乘以蚁群个体数(每次迭代需计算种群所有个体的新目标值)，文献[13] IEEE 69节点系统重构结果为依据其算法编程统计得到．

表5 算法性能比较

从表中可以看出，对于IEEE 33节点系统，本文算法得到最优结果所需的最小、最大和平均计算次数分别为 2次，190次和83.5次，明显小于文献[13] HS算法及文献[9]蚁群算法计算次数；且本文算法99%能得到全局最优结果，远高于文献[13] HS算法的21%；可见本文算法收敛迭代次数明显小于文献[13] HS算法，得到最优解的概率也更大，与文献[9]蚁群算法性能比较，本文算法稳定性更好，收敛速度更快．

对于IEEE 69节点系统，利用本文算法得到最优结果所需的最小、最大和平均计算次数和IEEE 33节点系统相近，故本文算法稳定性好，收敛速度不随规模的扩大而变差．综上分析，本算法具有较高的搜索效率和良好的鲁棒性．

6 结 论

1)根据配电网重构网络拓扑约束及HS算法的特点，采用基于重构环的和声向量编码方式，缩短了编码长度，有效减少了不可行解的产生．

2)通过将重构环公共支路分组，并设定断开原则，限制了公共支路的重复选择，避免了不可行解的产生．

3)利用启发式规则指明有效搜索方向，缩小了重构环寻优范围，增大了有效解的概率，提高了算法的搜索效率．

4)HS算法概念清晰，操作简单，与启发式规则配合使用，收敛速度快，稳定性好，重构结果与初始状态无关，搜索性能不随网络规模的扩大而变差，是求解配电网重构问题的一种较好算法．

[1] SARMA N D R, PRAKASA RAO K S. A new 0-1 integer programming method of feeder reconfiguration for loss minimization in distribution systems[J]. Electric Power Systems Research, 1995,33(2):125-131.

[2] MERLIN A, BAEK H. Search for a minimal-loss operating spanning tree for an urban power distribution system[C]//Proceedings of Fifth Power System Computation Conference. Cambridge, 1975:2-6.

[3] FAN JI-yuan, LAN Zhang, MCDONALD J D. Distribution network reconfiguration: Single loop optimization[J]. IEEE Trans on Power Systems，1996,11(3):1643-1647.

[4] CIVANLA S, GRAINGER J J, YIN H,etal. Distribution feeder reconfiguration for loss reduction[J]. IEEE Trans on Power Delivery,1988,3(3):1217-1223.

[5] 何禹清，彭建春，文明，等.配电网重构的最小可行分析对象及其快速算法[J].中国电机工程学报，2010,30(31):50-56.

HE Yu-qing, PENG Jian-chun, WEN Ming,etal. Minus feasible analysis unit and fast algorithm for distribution network reconfiguration[J]. Proceedings of the CSEE,2010,30(31):50-56.(in Chinese)

[6] GOSWAMI S K, BASU S K. A new algorithm for the reconfiguration of distribution feeders for loss minimization[J]. IEEE Trans on Power Delivery,1992,7(3):1484-1491.

[7] 麻秀范，张粒子.基于十进制编码的配网重构遗传算法[J].电工技术学报，2004,19(10):65-69.

MA Xiu-fan, ZHANG Li-zi. Distribution network reconfiguration based on genetic algorithm using decimal encoding[J]. Transactions of China Electrotechnical Society, 2004,19(10):65-69.(In Chinese)

[8] 张栋，张刘春，傅正财.基于改进禁忌算法的配电网络重构[J].电工技术学报，2005,20(11):60-64.

ZHANG Dong, ZHANG Liu-chun, FU Zheng-cai. Network reconfiguration in distribution systems using a modified TS algorithm[J]. Transactions of China Electrotechnical Society, 2005,20(11):60-64.(In Chinese)

[9] 王超学，崔杜武，崔颖安，等.使用基于中医思想的蚁群算法求解配电网重构[J].中国电机工程学报，2008,28(7):13-18.

WANG Chao-xue, CUI Du-wu, CUI Ying-an,etal. Distribution network reconfiguration using a novel ant colony system based on traditional Chinese medicine theory[J]. Proceedings of the CSEE, 2008,28(7):13-18.(In Chinese)

[10]余健明，张凡.基于改进免疫遗传算法的配电网重构[J].电网技术，2009,33(19):100-105.

YU Jian-ming, ZHANG Fan. Distribution network reconfiguration based on improved immune genetic algorithm[J]. Power System Technology, 2009,33(19):100-105.(In Chinese)

[12]李振坤，陈星莺，余昆，等.配电网重构的混合粒子群算法[J].中国电机工程学报，2008,28(31):35-41.

LI Zhen-kun, CHEN Xing-ying, YU Kun,etal. Hybrid particle swarm optimization for distribution network reconfiguration [J].Proceedings of the CSEE, 2008,28(31):35-41.(In Chinese)

[13]GEEM Z W, KIM J H, LOGANATHAN G V．A new heuristic optimization algorithm: Harmony search[J]. Simulation,2001, 76(2):60-68.

[14]SRINIVASA R R, NARASIMHAM S V L, RAMALINGA R M,etal. Optimal network reconfiguration of large-scale distribution system using harmony search algorithm[J]. IEEE Trans on Power Delivery,2011,26(3):1080-1088.