胡 非 ，刘志刚 ，何士玉 ，杨红梅

（1.西南交通大学 电气工程学院，四川 成都 610031；2.湖北省黄石供电公司，湖北 黄石 435000）

0 引言

现代电力系统中，电力系统中的大部分故障来源于配电网，配电网故障诊断是从技术上提高配电网安全可靠运行的重要手段。近年来，许多学者将人工智能的理论和方法用于配电网故障诊断，如蚁群算法［1］、遗传算法［2］、协同进化算法［3］、粒子群算法［4］和专家系统［5-7］等，其中，专家系统在配电网故障诊断系统中应用最为广泛。

为了克服传统专家系统的缺陷，从20世纪70年代起，Reiter等国外学者［8-11］提出用基于模型诊断（MBD）方法来开发故障诊断系统。现在，MBD已经成为人工智能领域的一个研究热点，已应用于医疗、经济、航天、电路诊断等诸多领域，但在电网系统故障诊断中的应用研究还处于起步阶段。

在MBD方法中，由最小冲突集求解最小碰集的过程是一个NP-Hard问题。目前，许多学者都对计算最小碰集的算法进行了研究和改进，主要有：HSTREE［12］，HS-DAG［13］，HST-TREE［14］，BHS-TREE［15］，布尔代数算法［16］，逻辑数组算法［17］，遗传算法［18］，粒子群算法［19］等。在以上这些方法中，主要缺点集中表现在：

a.需要进行剪枝，可能会丢失正确解［12］；

b.所建立的树或者图，数据结构复杂而且计算量大［12-14］；

c.要求求出所有的碰集再化简［15-17］；

d.所得到的结果不能保证全是最小碰集［18-19］。

这些缺点的存在使得程序难以编制，而且在处理复杂系统诊断问题时，例如配电网故障诊断，最小冲突集簇元件总数与最小冲突集中元件数对其算法效率影响比较大，导致算法效率不高。

本文针对上述算法产生的缺点，提出使用二进制编码逻辑运算的方法计算最小碰集，以满足模型故障诊断中对配电网系统诊断解的计算，该方法的主要优点是：

a.对每个元件进行二进制编码，有2个好处，一是算法的整个运算过程，只有0/1组成的字符串进行单一的逻辑“或”运算，易于程序的编制和实现，二是该算法的复杂度只与最小冲突集簇中所包含的元件数有关，与最小冲突集个数及最小冲突集中元件个数无关，促使该算法诊断元件数的能力大幅增强；

b.在搜索过程中，采用自底向上的宽度优先类搜索算法，明显地降低了算法的时域复杂度，效率更高。

1 相关定义与定理

下面介绍一些MBD的概念和定理［12］。

定义1 被诊断系统。一个被诊断系统用一个三元组｛系统的模型描述（SD，the system description）；系统的观测值（OBS，observation）；组成系统的元件集合（COMPS，the system components）｝来表示。

定义2 冲突集。 系统（SD，OBS，COMPS）的一个冲突集是一个元件集｛c1，…，ck｝⊆COMPS，它使得SD∪OBS∪｛¬AB（c1），…，¬AB（ck）｝是不可满足的。一个冲突集是最小冲突集当且仅当它的任何一个真子集都不是冲突集。其中，一元谓词AB意味着“abnormal”，AB（c1）表示元件 c1异常，¬AB（c1）表示元件c1正常。

定义3 碰集。设C是一个冲突集合簇，C的碰集是一个集合H，H满足2个条件：一个碰集是最小碰集当且仅当它的任何一个真子集都不是碰集。

定义4 碰集环境。设元件集合COMPS=｛c1，c2，…，cn｝中有 n 个元件，非空集合 E⊆COMPS，则称E为碰集环境，显然，系统中的碰集环境的个数为2n-1（n表示系统中元件的个数）。

定义5 候选碰集。如果E是某系统的碰集环境，则称E为一个候选碰集。例如，某系统有元件集合｛A，B｝，则该系统的候选碰集有｛A｝、｛B｝、｛A，B｝。

定理1 Δ 是（SD，OBS，COMPS）的一个极小诊断，当且仅当Δ是（SD，OBS，COMPS）的最小冲突集的最小碰集。

2 算法描述

设有冲突集合簇 CS=｛C1，C2，…，Ck，…，Cm｝，k=1，…，m。

步骤1求出CS中的全部元件，记∪CS=｛C1∪C2∪C3∪…∪Cm｝=｛c1，c2，…，cn｝，系统中有 n 个元件。如果冲突集簇中含有超集，先要进行超集删除处理。

步骤2对系统的每个元件进行二进制编码并得到一个碰集评判代码。

a.冲突集合簇 CS=｛C1，C2，…，Ck，…，Cm｝，用一维数组B［m］存储集合簇CS中各冲突集元素，即有B［m］=｛C1，C2，…，Ck，…，Cm｝，其中，B［1］=C1，B［2］=C2，…，B［m］=Cm。 对于元件 ci（1≤i≤m），如果 ci∈Ci（1≤i≤m），则用 1 表示；如果则用 0 表示；将二进制码0或1存入Ci在数组B［m］中所在的位置，此时的每个元件都会用一个由m个二进制代码组成的字符串表示。

b.冲突集合簇 CS=｛C1，C2，…，Ck，…，Cm｝，其碰集评判代码为11…1（m个1）。

步骤3求出所有的碰集环境，即候选碰集，对于有n个元件的系统，则有2n-1个候选碰集，并对每个候选碰集进行封装，便于第5步的搜索。

步骤4对每个候选碰集，确认彼此之间的父子关系。如果集合A⊆B，则称A是B的子候选碰集，B是A的父候选碰集，显然，对于一个集合而言，可能有3种情况：

a.可能有多个父候选碰集或多个子候选碰集；

b.可能同时存在父候选碰集和子候选碰集；

c.可能只存在父候选碰集或子候选碰集。

步骤5采用自底向上的宽度优先类搜索算法进行搜索，采用“边搜索，边计算，边判断，边确认”的策略，先对子候选碰集进行判断，将子候选碰集中的每个元件的二进制代码进行“或”运算，如果运算结果和评判代码一致，就可判断该子候选碰集为碰集，则此时就不需要对其父候选碰集进行判断，否则，需要对其父候选碰集进行判断。此步骤结束以后，就得到所有的最小碰集，而且不会产生最小碰集超集，也不会漏掉最小碰集。

算法主要流程如图1所示。

图1 程序流程图Fig.1 Flowchart of program

3 算法的实时性

求最小碰集时，影响其算法效率的有2个因素，分别为最小冲突集数和最小冲突集簇中所含的总元件数。因此，本文将二进制编码算法分别从这两方面与 HS-TREE［12］、BHS-TREE［15］、逻辑数组算法［17］进行比较，在 PC 机上（Celeron 2 GHz，1 GB，Windows XP）用MAPLE12仿真，得出下列2种情况的时间效率图。

a.整个最小冲突集簇含M=30个元件，最小冲突集数不变，n=9，取（1，2，…，m），（2，3，…，m+1），…，（n，n+1，…，n+m+1）；m=5～9，得到最小冲突集元件数时间效率图，如图2所示。

b.当n=9时，整个最小冲突集族中所含元件数M=26～30；得到最小冲突集簇元件数时间效率图，如图3所示。

图2 每个最小冲突集元件数个数不同时间效率图Fig.2 Curves of time needed vs.element number of each minimal conflict set for different algorithms

图3 最小冲突集元件总数不同时间效率图Fig.3 Curves of time needed vs.elements number of minimal conflict sets

可见，比较文献［12］、［15］、［17］中的算法，本文提出的算法特点很明显：算法时间效率与冲突集簇所含元件数及最小冲突集中所含的元件个数有关，这2种因素对二进制编码算法的时间效率影响较小。 若综合上述 2 种因素，比较文献［12］、［15］、［17］中的算法，二进制编码算法在时间效率上优势非常明显。

4 配电网故障诊断

图4为某10 kV配电网子网，它是具有7个节点的辐射型配电网络，其中系统等效是指除了这7个节点外的完整配电网，它的作用相当于电源，给这7个节点供电，从节点1到节点7都布置了相应的信息采集装置。记B3_A为节点3的A相母线，L57_B为节点5和节点7之间的B相输电线，其他母线和线路的编号类似。

假设在该配电网中，线路L23_A发生短路接地和线路L57_B发生短路接地故障。采用文献［20］中的方法对该配网进行建模仿真，可得到最小冲突集MinCs：=｛｛B3_A，L23_A｝，｛B7_B，L57_B｝｝。

对于冲突集簇MinCs，采用二进制编码法计算最小碰集，具体过程如下。

步骤1求出冲突集簇MinCs中的全部元件为∪MCS=｛C1∪C2｝=｛B3_A，L23_A，B7_B，L57_B｝。

步骤 2 候选碰集有｛B3_A｝、｛L23_A｝、…、｛B3_A，L23_A，B7_B，L57_B｝等 15 个。

步骤3确认候选碰集彼此间的父子关系，比如，｛B3_A｝⊆｛B3_A，L23_A｝，则｛B3_A｝是｛B3_A，L23_A｝的子候选碰集，｛B3_A，L23_A｝是｛B3_A｝的父候选碰集。

步骤4元件的二进制代码B3_A为10，L23_A为10，B7_B 为 01，L57_B 为 01；碰集评判代码为 11。

步骤5自底向上进行搜索确认。先从元件最少的候选碰集进行判断，即从含有单个元件的候选碰集开始判断，显然，在此例中单元件的二进制代码均不与碰集评判标准一致，故单元件候选碰集都不可能成为最小碰集。再从双元件的候选碰集进行判断，例如候选碰集｛L23_A，L57_B｝，元件L23_A的代码10，元件L57_B的代码01，将这2个元件的代码进行“或”运算，得11，正好与评判代码一致，说明集合｛L23_A，L57_B｝为碰集，即为该配电网的一个候选诊断，不需要对其父候选碰集｛B3_A，L23_A，L57_B｝、｛B7_B，L23_A，L57_B｝、｛B3_A，B7_B，L23_A，L57_B｝等进行判断。如此进行下去，直至找出所有最小碰集。最后，得到4个最小碰集，即4个候选诊断，为：MinHs：=｛［B3_A，B7_B］，［B3_A，L57_B］，［B7_B，L23_A］，［L23_A，L57_B］｝。

将本例所得的最小冲突集簇，用其他的最小碰集算法计算，花费时间如表1所示。

由此表进一步可以看出，二进制编码法较文献［12］、［15］、［17］中的最小碰集算法效率更高，有较好的实时性。

表1 各种最小碰集算法所需时间Tab.1 Time needed by different algorithms

5 结论

本文将求解最小碰集问题映射到二进制数0/1逻辑“或”关系求解问题上，使得数据结构更为简单，实现算法与程序的一致。先求出系统的所有候选碰集，对系统中每个元件进行二进制编码，然后采用自底向上的搜索方法，进行搜索确认，在确认的过程中，使用二进制代码的逻辑“或”运算。算法易于编程实现，而且该算法在时间与空间复杂性上都表现出了较优的性能。通过实验仿真，与其他算法进行比较，说明该算法具有良好的实时性，最后，以一个实际配电网诊断为例，更加充分地证明了二进制编码算法在处理复杂系统问题上的优越性，实现了在很短的时间内找到全部的最小碰集的目的。本文提出的算法可以为基于模型故障诊断中最小碰集的计算，尤其是复杂系统故障诊断（如配电网）提供有价值的参考。