基于Tabu搜索的配电网络重构算法陈根军¹,李繼洸²,唐国庆¹(1.东南大学电气工程系，江苏南京210096；2.香港理工大学电机工程系香港)摘要：配电网络重构是一个非常复杂的、大规模的组合优化问题。该文提出了一种非常有效的、鲁棒性很好的算法来求解正常运行条件下配电网络的重构问题，以减少网络中的能量损失费用。该算法基于Tabu搜索方法（TS）。作为现代启发式方法家族中的重要一员，Tabu搜索方法是近几年来发展起来的用于求解组合最优问题的一种通用算法。文中详细阐述了用于配电网络重构问题时Tabu搜索方法中各成员的设计。为了证明该文方法的可行性和有效性，还研究了3个不同规模的IEEE测试网络的重构问题。结果表明，该文提出的方法是一种非常有效的方法。
关键词：配电网络重构；损失减少；Tabu搜索1引言
在配电系统中，每一条馈线的负荷通常是由工业负荷、商业负荷和居民负荷等几种负荷组合而成的。这些不同负荷类型的日负荷曲线是不同的，因而使得不同馈线的峰荷发生在不同的时刻。在正常运行条件下，可以通过网络重构功能将负荷较重的馈线上的负荷转移到负荷较轻的馈线上去，并达到减少配电网络中能量损失、提高网络中电压分布的目的。
配电馈线包含了大量的常开开关和常闭开关。当系统运行条件改变时，通过网络重构合上常开开关并断开常闭开关来减少线路损失，同时满足变电站容量、馈线容量、电压降落、辐射状网络结构等约束条件。因此，进行配电网络重构就是为了决定这些网络开关的状态，从而最大限度地减少配电系统中的线路损失。它是一个非线性的混合整数规划问题。
到目前为止，关于研究用网络重构的方法来减少线路损失已有大量的文章面世，并相应地提出了许多方法，这些方法可以分成3类^[1]：启发式和优化方法相混合的方法、纯启发式方法及利用人工智能的方法，包括专家系统的方法（ES）、模拟退火法（SA）、遗传算法（GAs）、进化规划（EP）、人工神经网络（ANN）等。
本文提出了一种基于Tabu搜索的有效算法来求解配电网络重构问题，以减少正常运行条件下的线路损失。
Tabu搜索是一种通用的启发式最优技术，用于有效求解组合最优问题的近似最优解。到目前为止，Tabu搜索在许多领域已经取得了令人瞩目的成功。近年来，Tabu搜索开始被成功地应用于求解电力系统的组合优化问题中如水-热机组的调度问题^[2]、热机组的维修调度问题^[3]、警报处理^[4]、故障区估计^[5]、投诉电话分析^[6]等。
本文详细地阐述了用于配电网络重构问题时Tabu搜索方法中各成员的设计。为了证明本文方法的可行性和有效性，文中研究了3个不同规模的IEEE测试网络的重构问题。结果表明，本文提出的方法是一种非常有效的方法。
2配电网络重构问题的数学描述
在配电系统中一般有2种类型的开关：联络开关和分段开关，如图1^[9]所示。图中，虚线表示的支路15，21和26上装有联络开关，而其余用实线表示的支路装有分段开关。当运行条件改变时，通过打开和闭合这2种类型的开关来实现网络重构以减少线路损失。也就是说，其中一个联络开关被合上以转移负荷到不同的馈线上；同时，一个分段开关被打开以维持配电网络的辐射状网络结构。例如在图1中，当馈线2上的负荷在正常运行条件下变为重负荷时，联络开关15被合上以将母线11上的负荷从馈线2转移到馈线1。同时，分段开关19被打开以维持配电网络的辐射状网络结构。本文中，网络重构问题的主要任务是确定配电网络中哪些联络开关需要闭合、那些分段开关需要打开，以使最终的网络具有最小的线路损失。可用数学公式描述如下：
式中r_i为馈线i上的阻抗；P_i为馈线i上流过的有功功率；Q_i为馈线i上的流过的无功功率；V_i为馈线I上的电压；F_c为网络中所有闭合馈线的集合。
式(1)服从如下约束：
(1)潮流约束AP=0(2)
式中A为节点－支路关联矩阵；P为馈线潮流矢量；D为负荷需求矢量。
（４）辐射状网络结构约束
由此可见，配电网络重构是一个非线性的混合整数规划问题。在本文中，将采用Tabu搜索算法来求解。
3Tabu搜索
Tabu搜索(TS)最早由FredGlover于1977年提出，作为一个最优工具来求解非线性覆盖问题^[7]。近年来，它已被成功地用于求解许多领域的组合最优问题，并被证明是行之有效的。文[2～6]则报道了Tabu搜索在电力系统中的应用。
TS是一项通用的内启发式最优技术，可用于求解大规模的组合最优问题。它通过利用灵活记忆的特殊形式，来避免搜索陷入局部最优。TS中的基本概念主要由“邻居”(neighborhood)和“保留期”(tenure)组成。通常，TS方法从一初始解开始搜索。初始解可以通过随机方法产生或由已有的启发式方法产生。通过应用操作符‘移动’（move），对当前解进行操作，产生一组当前解的邻居试验解。在产生的这些邻居试验解中，最能改善评价函数的那个解被选择为新的当前最优解。如果所有的‘移动’均不能改善评价函数，表明当前的解为局部最优解。为了防止陷入局部最优，在TS中还设置了一指定长度的tabu表，称作为tabulist，在tabu表中保存了那些最近已经实现了‘移动’的反方向‘移动’，称之为tabu‘移动’，tabu表在每次迭代中都进行更新。在产生新的‘移动’时，tabu表中的‘移动’必须加以限制，因为它们会使搜索过程返回到已经访问过的搜索空间中去。重复TS的搜索过程，直到满足指定的停止规则。
4Tabu搜索在配电网络重构中的应用
4.1算法描述
本文提出的基于Tabu搜索的配电网络重构算法描述如下：
（1）选择当前的运行网络作为初始解S^initial，并计算S^initial的评价函数。令当前解向量S^current=S^initial，最好解向量S^best=S^initial。初始化tabu表T和释放水平函数A。设置迭代计数器K=0。
（2）如果K等于预先设定的最大允许迭代次数K_max，那么输出S^best作为最终的规划方案；否则，令K=K 1，并转步骤(3)。
（3）通过后面将要定义的2种‘移动’，作用于S^current，生成S^current的一个辐射状试验解S，并计算对应该试验解的评价函数f(S)。重复该过程，直到指定的邻居取样数N_max已经达到。
（4[1][2][3]下一页