基于并行禁忌搜索算法的配电网重构

武晓朦，李新桥

(1.西安石油大学 电子工程学院/陕西省油气井测控技术重点实验室，陕西 西安 710065；2.国网渭南供电公司，陕西 渭南 714000)

引 言

配电网重构是使系统运行方式更优的重要举措，也是配网自动化研究的重要内容之一。封闭式设计、开放式运行是配电网运行最显著的特点。配电网正常运行时，电力工作人员可以根据运行情况的差异进行开关通断操作以调整网络结构，由此可以带来两方面的效益：一方面可均衡馈线负载水平，系统的电压质量能得到较大改善；另一方面网络重构能降低配网运行过程中的网络损耗，有利于改善系统的经济性能。当配电网在故障工况运行时，电力工作人员可以通过改变某些开关的闭合状态隔离故障，同时闭合某些联络开关从而实现将负荷从故障线路上转移到未故障的线路上，进而达到缩小停电范围、减小停电影响并在故障排除后迅速恢复供电的目的。因此对配电网进行网络重构具有重要的经济效益和实用价值[1]。

配电网重构问题属于一种规模巨大、多优化目标且非线性的组合优化问题。配电网重构的数学模型种类繁多，可以是某一个性能指标，也可以综合2个甚至是多个指标。比较流行的网络重构的优化模型都是以单一目标作为优化指标；具有多个优化指标的重构模型也是通过数学的方法把多目标问题转换成单目标优化问题，继而运用单目标优化技术进行重构[2]。配电网重构问题的另一个研究热点是应用于网络重构的优化算法，配电网重构能否寻找到最优解很大程度上取决于优化算法的性能。国内外学者针对配电网重构问题研究出了许多不同的优化算法，主要有传统数学法、启发式优化算法、智能优化算法等[3]。目前配电网重构研究中最常用的是人工智能算法，主要包括人工神经网络算法、遗传算法、禁忌搜索算法、粒子群算法、模拟退火算法等[4]。虽然智能优化算法寻求全局最优解的效果好，但随着配电网络结构的发展变化，算法中的某些关键参数很难确定，且重构的时间较长，因此提高优化算法的计算效率具有重要的意义[5]。

本文应用禁忌搜索算法对配电网进行重构研究，针对配电网重构问题的复杂性、特殊性和禁忌搜索算法是串行搜索的缺陷，提出并行禁忌搜索算法，通过设置多个禁忌长度来实现对解空间进行并行同时搜索，在扩大搜索范围的同时，提高禁忌搜索算法的效率，从而进一步提高配电网重构的效率。

1 配电网重构问题的数学模型

配电网重构通过调整网络中开关状态的组合方式来改变配电网运行结构，从而实现配电网的经济运行。本文对配电网运行过程中的有功损耗进行优化，即以全网有功网络损耗最小作为目标函数，其具体的数学表达公式为：

(1)

式中：Nb代表网络中的支路总数；Ki为开关i的状态，分别用0和1代表开关的断开和闭合状态；Pi、Qi分别表示流过支路bi的有功功率和无功功率；Ri和Ui分别代表支路bi的支路电阻及其末端节点电压。

由于配电网运行必须满足封闭式设计、开放式运行的条件，因此重构过程需要考虑以下约束条件：

(1)配电网系统的潮流方程约束。

(2)网络拓扑约束，配电网在正常运行时呈辐射状，网络中不存在环网。

(3) 连通性约束。配电网在正常运行时必须保证对每一负荷节点都进行供电，即网络中不存在供电孤岛。

(4)支路电流约束。对支路电流约束也就是对各馈线容量进行约束，配网中每条支路上流过的电流不能超过该线路允许的最大电流，即：

Ii

(2)

式中，Ii和Ii,max分别代表流过支路bi的实际电流和其允许流过电流的最大值。

(5)节点电压约束。配网中节点电压必须保持在额定的范围内。

Ui,min

(3)

式中：Ui为节点i的实际电压；Ui,min、Ui,max分别为节点i上允许的电压最值。

2 并行禁忌搜索算法在配电网重构中的应用

2.1 算法简介

禁忌搜索(Tabu Search,TS)算法的原理最早由F.Glover在20世纪70年代末提出，经过之后近十年的发展完善，最终形成一套完整的算法。TS算法是一种基于局部邻域搜索的全局逐步寻优算法，它通过引入存储结构和禁忌准则模拟人类智力思考的过程，避免迂回重复搜索，从而增加了有效搜索的次数，能实现搜索范围内的全局优化[6]。

TS算法虽然模拟了人类智力过程，但同样存在一定缺陷：(1)算法的优化性能受初始解的影响较大；(2)在同时注重搜索的集中性与多样性时，会出现多样性不足的情况；(3)迭代搜索过程仅是单一状态的移动，并非并行搜索，导致搜索效率不是很高。

本文采用并行禁忌搜索(Parallel Tabu Search,PTS)算法来改善TS过程是串行搜索的缺陷，PTS算法设置不同禁忌长度的禁忌表同时进行搜索，进一步扩大搜索范围，提高TS算法的搜索效率[7-8]。

2.2 优化变量的设计

针对配电网重构过程中编码复杂和计算效率低等问题，本文利用N维坐标系的编码策略对配电网中的开关进行编码，其中坐标系的维数与配电网络中所含环路的个数相对应，网络中环路的个数则等于网络中联络开关的个数，即网络中有几个联络开关，则就有几个环路，对应的坐标系就是几维。该种编码方式解决了大规模开关编码复杂的问题，同时简化了计算，提高了重构效率[9]。

图1 IEEE16节点网络拓扑图Fig.1 IEEE 16-node network topology

如图1所示的配电网络中，(5)、(9)、(13)号开关为联络开关，为保证配电网络的连通性与辐射性要求，图中的某些开关必须闭合，如(1)、(2)、(3)、(16)号开关，这些开关不参与编码。坐标的维数即为网络中联络开关的个数，每一维坐标都代表一个环路，坐标轴上的点为环内的开关，即优化变量。在解空间进行寻优时，各单环中打开的开关号码所对应的矢量坐标即为状态量。对图1中的网络进行邻域搜索，搜索空间如图2所示，x，y，z轴分别代表配电网中的3个环路，括号外的数字为坐标，括号内的数字代表开关在网络中的编号。图1此时的优化变量状态为(5,9,13)，根据上述编码规则，此时的状态量为(2,2,3)。

图2 邻域搜索空间Fig.2 Neighborhood search space

2.3 邻域结构的设计

邻域结构是解的“移动”途径或准则，是影响算法搜索性能的重要因素之一。图1中有3个环路，环路1、2、3的开关集合为{(4),(5),(6),(7)}，{(8),(9),(10)}，{(11),(12),(13),(14),(15)}，此时优化变量的状态为(5,9,13)，状态量为(2,2,3)。在每维坐标中针对每个状态量分别进行加1和减1操作，以此对应在网络拓扑图中的开关的移动操作[10]。在环路1中，此时对应x轴的坐标为2，对其进行加1和减1操作，得到一个邻域集合为{(1,2,3),(3,2,3)}。然后再分别对环路2和环路3中的变量进行加1和减1的“移动”操作，得到各自的邻域集合为{(2,1,3),(2,3,3)}和{(2,2,2),(2,2,4)}，这3个邻域集合便组成了一个初始的邻域集合{(1,2,3),(3,2,3),(2,1,3),(2,3,3),(2,2,2),(2,2,4)}。利用N维坐标系的编码策略对配电网中的开关进行编码，可以大大简化计算，提高重构的效率。

2.4 禁忌长度和候选解集

候选解集通常由邻域解集中目标值或评价值最优的邻居组成，即择优选取，候选解集是当前状态邻域解集的一个子集，是影响TS算法性能的关键参数之一。候选解集可大可小，确定依据是所求问题的特性和对算法性能的要求。禁忌长度是指在不考虑藐视准则的情况下，禁忌对象不被选取的最大次数，也可以将其理解为禁忌对象在禁忌表中所对应的任期，只有当任期为0时才对该禁忌对象进行解禁释放。在解决实际问题的过程中，对算法的计算量和存储量都有比较高的要求，为计算简单起见，候选解集和禁忌表能小则小，即禁忌长度越小，算法的性能越好，但也不宜过小，过小时算法容易陷入局部极小。针对上述问题，本文采用多个禁忌长度同时进行并行搜索，多个禁忌长度能控制搜索方向并扩大搜索范围，最后通过比较使目标函数取得最优解。

2.5 藐视准则和终止准则

在TS算法的搜索过程中，候选解全部被禁忌的情况时有发生。此时若被禁对象中存在一个优于当前最优解的候选解，藐视准则将忽略其禁忌属性，将该候选解直接作为当前解以及当前最优解，以实现更高效的算法优化性能。TS算法需要一个终止准则来结束算法的搜索进程，本文采用的结束搜索的判据是给定最优状态连续保持不变的最大持续迭代步数ICmax，当最优状态的持续迭代步数达到限定值ICmax，算法终止。ICmax的大小与网络的规模和对算法性能的要求密切相关[11]。

3 算例分析

本文通过对IEEE16节点系统和IEEE33节点系统进行网络重构来验证所提出方法的可行性和优越性。IEEE16节点系统(算例1)如图1所示，该系统有16个节点、16条支路、3个联络开关和13个分段开关，系统的额定电压为23 kV，总负荷为28 600 kW+j 7 300 kV·A，初始网络的有功网损为521.36 kW，最低节点电压为0.970 2 标幺值(p.u.)。TS的相关参数按下列要求进行设置：根据邻域结构的设计规则，邻域解个数取为6，候选解个数取3，将解空间进行分组，取每组的禁忌长度分别为3、4、5，终止准则ICmax取为5。

IEEE33节点系统(算例2)如图3所示，该系统有33个负荷节点、37条支路、网络拓扑中含有5个联络开关、32个分段开关。该网络系统的额定电压为12.66 kV，总负荷为3 715 kW+j 2 300 kV·A，初始网络的有功网损为206.68 kW，最低节点电压为0.916 9 p.u.。优化过程中，根据邻域结构的设计规则，邻域解个数取为10，候选解个数取5，将解空间进行分组，取每组的禁忌长度分别为3、4、5、6、7，终止准则ICmax取为7。针对上述2个算例运行本文算法程序，得出相应的计算结果，见表1。算例中各节点的电压如图4和图5所示。

图3 IEEE33节点系统网络拓扑图Fig.3 Network topology of IEEE33 node system

图4 IEEE16节点系统重构前后节点电压Fig.4 Node voltage of IEEE16 system before and after reconstruction

图5 IEEE33节点系统重构前后节点电压Fig.5 Node voltage of IEEE33 system before and after reconstruction

表1 重构结果Tab.1 Reconstruction results

由表1的计算结果可知，通过基于N维坐标系的并行禁忌搜索算法的配电网重构，IEEE16节点系统的网损降低为463.73 kW，最低节点的电压改善为0.978 3 p.u.；IEEE33节点系统的网损降低为206.68 kW，最低节点的电压改善为0.941 0 p.u.。因此本文算法在实现重构的过程中，能有效降低配电网的网络损耗，实现配电网的经济运行；同时，也能有效地改善网络中节点的最低电压，保证网络中节点电压的质量。

针对本文的2个算例，将采用本文所提出方法得到的运算结果与文献[10]和文献[12]所采用方法得到的运算结果进行对比(表2)。

表2 不同算法的重构结果指标对比Tab.2 Comparison of reconstruction indicators of different algorithms

由表2的分析对比结果可以看出，应用本文方法进行配电网重构，IEEE16节点系统的降损率达到11.054%，迭代次数为2次；IEEE33节点系统的降损率为33.253%，迭代次数为3次。本文方法在降损率和迭代次数等方面的优化效果均优于文献[10]和文献[12]所采用的方法。表明其能够在有效降低网损的同时较快速地寻找到全局最优解。

4 结 论

采用N维坐标系的编码策略对网络中开关进行编码，在每维坐标中针对每个状态量分别进行加1和减1操作，对应在网络拓扑图中的开关的移动操作，使得程序的编写和计算过程复杂度降低；在应用禁忌搜索算法时设置多个禁忌长度同时对解空间进行搜索，进一步提高计算效率，能够在有效降低网损的同时较快速地寻找到全局最优解，从而实现配电网重构的目的。针对一些环路不容易划分的复杂配电网络重构，还有待于进一步分析研究。