基于两阶段的黑启动分区搜索算法

基于两阶段的黑启动分区搜索算法

0黑启动分区的确定根据不同恢复过程的特点和主要矛盾，整体恢复过程可分为三个阶段：黑开始阶段、主网络框架恢复阶段和负荷恢复阶段。目前国内、外在黑启动研究领域取得了一系列进展，其中包括黑启动的一般性规律研究、黑启动时的自励磁问题、恢复过程中频率和电压控制、主网架构建问题、负荷恢复问题、恢复过程中的继电保护配合问题以及决策支持系统的构建。在黑启动阶段，电网中通常有多个机组具备自启动能力，因此在制订省级电网或大区电网黑启动方案时，应按照电网结构和黑启动电源分布特点，划分为多个黑启动分区。良好的黑启动分区的作用是：(1)在黑启动的初始阶段，可以保证各区域的自启动成功；(2)在扩大带电电网规模以扩大恢复供电范围阶段，可以控制相邻区域的待恢复电网，使之容易达到并网条件。因此，良好的黑启动分区策略是保证整个黑启动成功的基础条件，具有重要意义。然而，以往黑启动分区的确定一般采用凭经验的人工指定方式，缺乏科学的依据。本文根据黑启动过程的电气特点，定义了合理黑启动分区的数学模型，包括黑启动电源约束、功率平衡约束和安全约束。为降低黑启动分区计算的复杂度，把黑启动分区问题转化成布尔型的决策问题，并引入有序二元决策图(orderedbinarydecisiondiagram,OBDD)表示法进行建模求解，设计了两阶段搜索的算法。1obd描述1.1数值积分的一般过程性和可选择性条件OBDD是Bryant提出的一种布尔函数表示法。它通过在二元决策图(binarydecisiondiagram,BDD)表示法的基础上引入适当的约束，使之在形式上规范，且能更简单、方便地处理布尔变量间的运算。定义1满足如下特征的用于描述布尔函数的有向非循环图称为二元决策图：(1)具有1个或2个出度为0的节点，被标以“1”和“0”，称之为“1-端节点”和“0-端节点”，分别对应于该布尔函数的最终取值为1或0；(2)其它节点的出度均为2，称之为“变量节点”，其中仅有1个变量节点的入度为0，称之为“根节点”，每个变量节点v对应于的布尔变量记为函数v(v)。它有2条引出的边，称之为“0-分枝”和“1-分枝”，分别对应布尔变量v(v)取值为0和1。0-分枝和1-分枝分别连接由函数l(v)和h(v)确定的2个节点(变量节点或端节点)，称之为v的子节点。对于一组确定的布尔变量取值，可由BDD的根节点出发，依次经过对应于各变量取值的树枝最终到达某一确定的端节点。这个端节点确定了这组布尔变量取值情况下的布尔函数数值。由于布尔函数的BDD通常是含有冗余和重复节点的，即便对确定的布尔变量的顺序，表达相同布尔函数的BDD也不是唯一的，其规模也有所不同，因此BDD表示法并不是一种规范的表示法。可以按照一定的规则进行简化，形成规模最小的一种BDD，即OBDD。定义2满足下面条件的BDD称为有序二元决策图：(1）有序性条件。对任意2个相邻变量节点v和u，若u为v的子节点，即u=l(v)或u=h(v)，则有v(v)代表的布尔变量的序号在v(u)之前。(2）简约性条件。(1)无重复的节点：不存在同时满足v(u)=v(v)，l(u)=l(v)和h(u)=h(v)的2个节点u和v。若满足，则称u和i为“重复的”(duplicate)节点，如图1所示；(2)无冗余节点：不存在满足l(u)=h(v)的变量节点u。若满足，则称u为“冗余”的(redundant)的节点，如图1所示。1.2将二元决策树转化为2个变量节点在布尔函数f(x1,,xn)二元决策树的基础上生成OBDD的步骤：(1）确定所有布尔变量x1,,xn的顺序。(2）根据f(x1,,xn)的真值表和布尔变量的顺序建立其二元决策树。(3）简化重复的树叶。对分别标以“0”和“1”的两类树叶各保留一个，作为即将生成的OBDD中的2个端节点。将原来连接同一类树叶的所有边重新连接至被保留的一个同类树叶上。这一操作将使二元决策树转化为仅包含两端节点的BDD。原来二元决策树中的分枝点即成为BDD的变量节点。(4）简化重复的变量节点。对于2个变量节点u和v，若有v(u)=v(v)，l(u)=l(v)，h(u)=h(v)，则去掉v，并将原来连接到v的边重新连接至u上。重复这一操作直至不存在重复的变量节点为止。(5）简化冗余的节点。对于变量节点u和v，有l(v)=h(v)，则去掉v，并将原来连接到v的所有边重新连接至l(v)。重复这一操作直至不存在冗余的节点为止。经过以上5个步骤，就可以生成f(x1,…,xn)的OBDD。1.3基于两阶段的obdd生成策略OBDD具有如下的特点，有利于构造黑启动分区策略的有效方法。首先，OBDD表示法是对全部解空间的搜索，可以保证得到所有可行解，因此不会丢失最优解。OBDD的Satisfy-all算法能执行对全部策略空间的搜索。更重要的是原问题的OBDD形成后，用于搜索出所有可行解所费时间仅为布尔变量个数的多项式。这一特点使OBDD表示法明显不同于随机搜索算法(如遗传算法、模拟退火法、禁忌搜索法等)。此外，OBDD的另外一个显著优点是，生成复杂问题的OBDD的过程可分阶段进行。OBDD的Apply算法或Compose算法可以容易地将分阶段生成的多个OBDD合成一个OBDD。因此，对于黑启动分区问题，可以针对不同的约束，事先生成各自的OBDD。在应用时把它们合成一个OBDD用于决策，从而可以把大量计算量很大的OBDD生成过程放到离线准备中，从而保证了决策应用的效率。基于以上思路，本文提出了基于两阶段的OBDD生成策略，第1步是离线准备，针对不同的约束条件生成各自的OBDD；第2步是决策应用，利用第1步生成的一个或多个OBDD，通过合并形成最后的OBDD，然后调用OBDD软件包的Satisfy-all算法来搜索全部策略，进一步通过安全分析选出最优的策略。关于OBDD的算法原理和如何编写程序可以参见文献。2黑启动分区建模2.1dd生成策略黑启动分区的搜索问题实质上可以等价于满足一定约束条件下确定电网中所有线路的通断状态。对于每一条输电线的通断状态可以采用一个布尔变量来表示。黑启动分区的搜索问题就可以转化为一个布尔函数的“可满足”问题，即把这个问题的部分约束条件用布尔函数表示，进而搜索使布尔函数为真的解作为可能的黑启动分区策略，从而缩小解空间，然后再接受下一步的检验。基于以上思路，本文提出了基于两阶段的OBDD生成策略。(1）第1阶段是离线准备，针对不同的约束条件生成OBDD。约束条件包括：(1)黑启动电源约束(black-startpowerresourceconstraint,BPRC)，指各黑启动电源必须分配到不同分区中，并且第2批自身无启动能力、需尽快启动电源及需要快速恢复的重要负荷必须与一个或多个黑启动电源相连；(2)功率平衡约束(powerbalanceconstraint,PBC)，各分区内的黑启动电源容量应与无启动能力、需尽快启动电源的所需启动电力及重要负荷的能量供需平衡；(3)充电无功约束(reactivepowerconstraint,QC)，各分区内线路的充电无功总和不应大于黑启动电源的进相无功上限，且不能大于某一域值，以保证黑启动机组的安全和线路感应过压(在系统重构阶段，若系统已投入发电机的吸收无功能力不足，必须投入一定的负荷以消耗无功，否则将无法投入新的线路)。(2）第2阶段是决策应用，利用第1步生成的一个或多个OBDD，通过合并形成最后的OBDD，然后调用Satisfy-all算法搜索全部策略，进一步对所有策略进行安全校核，然后给出最优的分区策略。在实际应用中，第1步的计算量比较大，但是可以离线准备好，这样可以降低在线的计算量，所以这种分阶段的算法具有在线应用的前景。2.2节点关联矩阵的计算合理分区的基本思路是：通过主干网把黑启动电源、第2批自身无启动能力、需尽快启动电源、特别重要的负荷组成一个网络，然后根据以上的约束进行合理解裂。解裂得到的几个子网就是黑启动分区。定义3满足黑启动电源约束、功率平衡约束、充电无功约束和安全约束的分区策略称为电力系统的合理黑启动分区策略。定义4满足黑启动电源约束、功率平衡约束和充电无功约束的电网分割称为平衡分割(balancepartition)。定义5同维的节点关联矩阵间的“⊗”和“⊕”运算。若A和B为同维的节点关联矩阵，则“与”运算A⊗B和“或”运算A⊕B的第i行第j列的元素分别为定义6节点关联矩阵的“布尔乘方”运算：若P为节点关联矩阵，则P的各次“布尔乘方”定义为根据图论和布尔矩阵理论，节点关联矩阵AG具有如下2个很好的性质：(1)若将(AGk)ij写成析取范式的形式，它的每一个合取式均对应于电网图上i节点到j节点长度(经过的边数)为k的路(节点可重复)；若节点i和节点j之间不存在长度为k的路，则(AGk)ij=0；(2)若电网图中最长路径的长度为L，则对任意l>L有(I⊕AG)l=(I⊕AG)L,I为与AG同维的单位阵。由上面的2条性质，可以定义AG的星矩阵G*A。定义7令L为电网图中最长路径的长度，则AG的星矩阵G*A为根据G*A的性质，G*A中任意非对角元非零，则对应的节点之间存在连通的路径，其析取范式为对应节点间的所有路径。如图2的4节点系统，最长路径为3，则1节点与3节点之间的所有路径只需计算(G*A)，可得(AG*)13=b13⊕b12b23⊕b12b24b34，其中3个合取式b13、b12b23、b12b24b34代表1节点到3节点的3条路径。按常规方法计算出G*A，其计算复杂度为O(n4)。采用Warshall’s算法求G*A，其计算复杂度仅为O(n3)，可很好地降低该问题的计算复杂度。2.3各节点之间的约束副假设系统可以分成U个黑启动分区，分别用IG,1,IG,2,...,IG,U表示各机群内的发电机节点集合。同时定义系统共有N个节点，AG表示电网的节点关联矩阵，G*A是AG的星矩阵，则黑启动问题可以通过G*A矩阵描述成以线路通断状态为布尔变量的布尔函数，用于生成它的OBDD。(1）黑启动电源约束的布尔函数可以写成：该命题的含义为每个黑启动机群内的所有发电机节点相连，并且每个负荷节点有且只有1个黑启动机群与之相连。其中，iG,i为从第i个黑启动机群节点集合IG,i中任取出的1个黑启动机节点。(2）功率平衡约束PBC命题的布尔函数可以写成：该命题含义每以黑启动分区的负荷和发电之差小于域值d。其中，(A*G)i为G*A的第i行向量；W=[w1r,...,wNr]T为电网简化图中所有节点的注入功率。“〈〉”为命题的取真值运算定义：(3）充电无功约束QC命题的布尔函数可以写成：该命题含义为每以黑启动分区的充电无功小于域值h。其中，(A*G)i为G*A的第i行向量；R=[r1r,...,rNr]T为电网简化图中所有节点的线路充电无功。由于PBC约束式(6)和QC约束式(7)不是一个严格的布尔函数，而是一个决策变量，是布尔型的约束不等式组，需要编写算法把它转为严格的布尔函数。一般的OBDD程序包支持这种问题，采用OBDD向量来描述整型数变量，并支持整型数之间的运算。本文利用buddy程序包的这一功能实现把这两个问题生成OBDD。3计算与分析3.1模型求解结果如图3所示的IEEE-30母线电网G，假如要把该系统分为2个黑启动分区，IG,1={1,2,5,8}、IG,2={11,13}，其中，节点1和11的发电机是黑启动机组。首先对电网G进行化简，合并冗余节点，然后对电网图的节点重新编号得到简化后的图4所示的电网图G′(图4中虚线部分为合并掉的支路)。简化后电网图G′的节点数、边数和发电机节点数为N=23,M=26,NG=6,OBDD向量的二进制编码位数nb=10，简化图的最长可能路径L=17。原始数据中，IEEE-30系统中1号节点的无功上界、下界过大，而实际系统不可能出现这种情况，所以将1号节点的无功上、下界分别调为99Mvar、0Mvar。取有功域值为30MW，无功域值为10Mvar。最后，经过19.656s的计算时间搜索到同时满足BPRC、PBC和QC约束的55个解。计算结果表明，对规模不大的IEEE-30系统黑启动分区问题，利用OBDD法求解十分有效。其中，一个分区结果是：断开未简化网络G中的(4,12),(6,10),(6,9)和(25,27)。3.2分区结果分析本算例采用海南电网2006年9月26日黑启动时的高压电网数据。此时系统共有32个节点、经过初步化简得到19节点、25条线路的简化模型(化简的原则是将度数为1的节点合并至相邻节点)。化简之后的节点数据如表1所示。按表1中的数据，此时海南电网只有3个发电厂：洋浦、大广坝和南山。按黑启动一般安全校核规则，把此时负荷按40%计算，并把3个发电节点分别作为3个分区的黑启动节点进行黑启动分区。在本算例中，引入了最优解条件，利用最优解条件可以在可行解集中搜索出一个最优解。本文定义的最优解条件是：求出每个分区内线路充电无功之和除以分区内发电容量之和，然后再把所有分区的这个比值平方相加，此值最小的即为最优解。最优解条件为其中，U为黑启动分区数;为一个分区i内线路充电无功之和;为分区内j发电容量之和。当然,最优性条件可以根据问题的需要进行修正，如采用安全分析工具进行分析。在该模型中，简化后的电网图G′节点数、边数和发电机节点数为：N=19,M=25,N=3,OBDD向量的二进制编码位数敢nb=9，取有功域值为15MW，无功域值为15Mvar。对G′中25条边所对应的25个布尔变量进行排序。最后，经过总共31.361s的计算时间搜索到同时满足BPRC、PBC和QC约束的18个解。符合最优解条件的分区结果为：第1分区内的节点包括洋浦、洛基、海电、华盛、交叉点、永庄、金盘；第2分区内的节点包括大广坝、鹅毛岭、罗带、八一、那大；第3分区内的节点包括南山、鸭仔塘、天涯、荔枝沟、林旺、陵水、兴隆、红石、万宁、官塘、玉洲、凤翔、桂林洋、东路、抱罗、清澜、文昌、会文。3.3obdd模型中变量顺序的选取表2给出了上述算例中各步骤所花费的时间。主要计算步骤方法包括：生成G*A矩阵以及(A*G)ij,i=1,..,NG;j=1,...,N(NG为黑启动机组数，N为节点数)；然后由BPRC、PBC、QC的约束条件生成对应的O