Page 158 - 《软件学报》2025年第12期

欧阳继红 等: HSDiag: 变种碰集算法求解诊断 5539

出了增量 BWIICC 算法, 利用左分支是右分支的真子集关系, 在计算左分支解集后, 通过增量的形式生成右分支,
是目前求解极小碰集效率较高的算法. 除此之外, 还有一些进化算法被提出 [23,24] , 但是这些算法大都是不完备的,
在获得部分解时花费较少, 当获得全部解时, 耗时也不容乐观 [25] .
随着系统软件的复杂性不断增加, 对诊断算法的要求也越来越高. 当系统是单观测时 [26] , 在某些情况下离线
求解冲突集是可以接受的, 但是只通过一次观测, 很难获得具体的故障位置. 获得多次观测数据是容易且廉价的,
许多专家提出了多观测算法, 即对故障组件进行多次观测, 获得多对输入输出数据, 通过计算聚合诊断来缩小待诊
断组件的范围 [27] . 在多观测系统及实时观测系统中, 求解极小诊断的时间是求解极小冲突集和极小碰集之和, 因
此求解极小冲突集在这种情况下已不适合离线进行 [28] .
近年来, 把系统描述编码成合取范式, 利用 SAT/MaxSAT 求解器获得极小冲突集或极小诊断. 不幸的是, 随着
电路规模的增大, 编码子句呈线性增长, 在求解所有冲突集或极小诊断时大部分情况是耗时严重或者是不现实
的 [29−31] . 为了能够在有限时间返回有用的诊断, 不完备的算法被提出. 2007 年 Siddiqi 等人 [32] 提出了一种顶层诊断概念,
把电路中的组件分为统治节点和被统治节点, 并且默认被统治节点是健康的, 在获得所有极小顶层诊断后, 再通过
统治节点替换被统治节点策略求出所有极小诊断. 2015 年 Mencia 等人 [33] 提出过滤边和过滤节点概念, 默认过滤
节点中的组件健康, 进一步缩小故障组件的范围, 能够快速获得一个诊断. 2019 年 Ignatiev 等人 [28] 计算多观测诊
断时, 利用 MARCO 算法收集极小冲突集, 利用极小碰集算法得到所有的诊断, 但是由于求解极小冲突集耗时严
重, 在处理多故障系统时, 效率有待进一步提高. 2022 年 Zhou 等人 [34] 提出了压缩策略, 利用第 1 次观测得到的变
量尽可能地共享其余观测的变量, 但是当其他观测与第 1 次观测共享的变量较少时优化效率不明显, 并且压缩模
型在单观测诊断上不起作用.
计算所有极小冲突集和极小碰集都是 NP-hard 问题, 为了缩短过程提高求解速度, 本文基于碰集思想, 定义组
件变量和传播变量, 修改系统编码, 提出一种集合分裂规则及变种碰集算法直接计算诊断. 换句话说, 把系统编码
当成冲突集, 在计算诊断的过程中, 因碰集中只需要保留组件变量, 故其余变量都相当于传播约束. 为了进一步加
快求解速度, 本文在基于等价类的基础上分解冲突集. 当冲突集合簇不可分时, 通过调用集合分裂规则, 对传播变
量进行删除, 减少集合簇之间的连接关系, 当对传播变量进行赋值时, 因求得的诊断解只含有组件变量, 故碰集中
不需要扩展传播变量.
本文第 1 节介绍基于模型诊断的相关概念以及基于冲突集计算诊断. 第 2 节首先介绍集合分裂规则, 然后结
合碰集算法提出了 HSDiag 算法, 最后为了缩减编码规模, 提出了一个专属计算诊断的等价类优化策略. 第 3 节将
所提出的算法与目前最快的基于冲突集计算诊断的算法进行对比, 实验数据采用 ISCAS-85, Fulladder, Polybox 这
3 种标准的数据集, 验证了所提算法的有效性. 最后总结全文.

1 基础知识

1.1 基于模型诊断的相关概念
待诊断系统可定义为一个三元组<SD, Comps, Obs>. 其中, SD 为系统描述, 为一阶谓词公式的集合; Comps 为
系统组成部件的集合, 是一个有限常量集; Obs 为观测集, 是一阶谓词公式的有限集. 假定所有组件状态是正常的
情况下, 当系统模型描述和观测出现不一致时, 我们称存在一个诊断问题, 即 SD ∧ Obs ∧ {¬A(c)|c ∈ Comps}是不一
致的. 其中, A(c) 为真代表组件 c 故障, 值为假代表组件 c 正常.
如果系统输出的真实值和理论值不同, 我们称为是不一致的, 反之是一致的.
定义 1. 诊断 (diagnosis) [28] . 给定一个诊断问题 D=<SD, Comps, Obs>.一个诊断被定义为一组组件∆ 的集合, 其
⊆ Comps, 当 ∈ Comps−∆}是一致的, 其中∆ 是一个极小子集诊断, 当且仅当它
中∆ D ∧ Obs ∧ {A(c)|c ∈ ∆} ∧ {¬A(c)|c
的任意真子集都不是诊断.
为了判定一个部件集是否为冲突集即判定该组件集中所有组件的正常行为描述与相关的系统描述及观测描
述是否逻辑一致.
[1]
定义 2. 极小冲突集 (minimal conflict set, MCS) . 组件集 f 是系统组件集 Comps 的冲突集, 当且仅当 f ⊆