Page 306 - 《软件学报》2025年第7期

赵相福 等: BWSS: 结合可疑集合簇计算极小碰集的 Boolean 算法 3227

all and only MHS are generated at the end of the algorithm. In addition, each candidate solution has at least m (m≥1) elements or even
the entire solution in no need of complex minimization. Theoretically, BWSS algorithm is far less complex than Boolean algorithm.
According to random data and mass reference circuit data, experimental results show that compared with many other state-of-the-art
methods, the proposed algorithm reduces several orders of magnitude in runtime.
Key words: model-based diagnosis; minimal hitting set; Boolean algorithm; candidate solution; conflict set

随着系统规模及复杂程度不断增加, 当新兴人造设备 (核技术、空间探索、智能汽车等) 出现故障时, 由于专
家经验有限, 基于经验的诊断技术已不再适用. 为了快速找到故障点, 大量专家利用系统结构、行为、状态、功能
[1]
等方面的知识, 提出了基于模型的诊断 (model-based diagnosis, MBD) . MBD 主要分为两个步骤: 冲突识别和候选
诊断. 如图 1 所示, 冲突识别是根据待诊断设备的描述和实际观测产生极小冲突集 (minimal conflict set, MCS) , 设
备的候选诊断是求解极小冲突集的极小碰集 (minimal hitting set, MHS). 因为冲突识别可以根据系统已知结构和当
前观测的信息离线求出极小冲突集 [2,3] , 所以整个诊断问题的求解效率将取决于极小碰集求解算法.

系统建模 候选诊断 实际系统设备
极小碰集
预测 监测

预期结果 冲突识别 观测结果

极小冲突集
图 1 基于模型诊断流程图

[1]
极小碰集求解是人工智能领域的一个重要课题, 最具有代表性的工作是人工智能专家 Reiter 在故障诊断中
的应用, 其提出了 HS-Tree 算法, 然而可能会因剪枝而丢失解的完备性. 1989 年, Greiner 等人 [4] 在 HS-Tree 算法的
基础上提出了 HS-DAG 算法, 利用有向无环图结构对相同节点进行重用, 保证了算法的完备性. 2001 年, Wotawa
等人 [5] 对 HS-DAG 算法进行了优化, 提出了 HST-Tree 算法, 通过对元素的唯一标识, 不再需要有向无环图也能保
证算法的完备性, 同时减少了大量冗余节点的生成.
2003 年姜云飞等人 [6] 提出了 Boolean 算法, 通过布尔规则来产生所有极小碰集, 在很多情况下都优于当前其
他集中式的求解算法 [7] . 其后, 该算法的许多优化算法及相似算法相继被提出 [8] . 比如, Abreu 等人 [9] 提出的
STACCATO 算法的原理和 Boolean 算法类似. 该算法通过设置求解极小碰集的数量及时间来中止算法. Cardoso
等人 [10] 在 STACCATO 算法的基础上提出了 MHS 算法, 利用 Map-Reduce 环境进行并行计算, 虽然并行计算一般
2
都高于串行计算, 然而在一定情况下, 串行计算可以转化为并行计算 [11] . Pill 等人 [12] 将 Boolean 算法的深度优先搜
索替换为宽度优先搜索, 改变了算法扩展规则, 减少了空间消耗并提高了计算效率. Huang 等人 [13] 利用 Boolean 算
法与增量算法结合提出了 IBoolean 算法, 大幅度减少了节点生成的数量. 以上优化算法大多期望减少节点的生成
数量来提高求解效率, 近几年, 一些研究人员对解的极小化进行了大量研究, 整体效率提升明显 [14] . 比如, 刘思光
等人 [15] 利用 Boolean 算法与独立覆盖思想结合, 判断每个碰集的真子集是否仍然满足碰集的定义. 该策略在判断
每个解的极小性时不必考虑解集的规模, 极大地提高了极小化时间. 王荣全等人 [7] 在优化极小化策略的同时, 又将
碰集求解问题转化成 SAT 问题, 把所有的冲突集合以子句形式表示成 SAT 的输入 CNF 进行迭代求解. Pill 等
人 [11] 通过对候选解中元素个数设置算法中止条件, 因求出的解集相对完备、算法较少, 故极小化时相对耗时较少.
Wang 等人 [16] 在针对配电网问题集合簇特有的拓扑结构特点, 对候选解的生成及极小化时设置了特定的目标函数,
使其计算出来的解都为极小解, 提高了求解效率. 我们针对问题集合簇独有的结构, 提出了一种针对树形结构的算
法 [17] , 求出的解仅为极小解, 极大地提高了求解效率.
极小化运算作为极小碰集算法的最后一步, 其作用是保证算法最终求得问题解的极小性, 所选用方法效率的
高低直接影响整体效率 [18,19] . 目前常见的极小化算法分为两种. 一种是基于子超集检测极小化算法 (sub-superset