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

基于两阶段的黑启动分区搜索算法 0 黑启动分区的确定 根据不同恢复过程的特点和主要矛盾，整体恢复过程可分为三个阶段：黑开始阶段、主网络框架恢复阶段和负荷恢复阶段。目前国内、外在黑启动研究领域取得了一系列进展，其中包括黑启动的一般性规律研究、黑启动时的自励磁问题、恢复过程中频率和电压控制、主网架构建问题、负荷恢复问题、恢复过程中的继电保护配合问题以及决策支持系统的构建。 在黑启动阶段，电网中通常有多个机组具备自启动能力，因此在制订省级电网或大区电网黑启动方案时，应按照电网结构和黑启动电源分布特点，划分为多个黑启动分区。良好的黑启动分区的作用是：(1)在黑启动的初始阶段，可以保证各区域的自启动成功；(2)在扩大带电电网规模以扩大恢复供电范围阶段，可以控制相邻区域的待恢复电网，使之容易达到并网条件。因此，良好的黑启动分区策略是保证整个黑启动成功的基础条件，具有重要意义。然而，以往黑启动分区的确定一般采用凭经验的人工指定方式，缺乏科学的依据。 本文根据黑启动过程的电气特点，定义了合理黑启动分区的数学模型，包括黑启动电源约束、功率平衡约束和安全约束。为降低黑启动分区计算的复杂度，把黑启动分区问题转化成布尔型的决策问题，并引入有序二元决策图(ordered binary decision diagram,OBDD)表示法进行建模求解，设计了两阶段搜索的算法。 1 obd描述 1.1 数值积分的一般过程性和可选择性条件 OBDD是Bryant提出的一种布尔函数表示法。它通过在二元决策图(binary decision diagram,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表示法是对全部解空间的搜索，可以保证得到所有可行解，因此不会丢