快速寻找一些高科技人造设备的有缺陷部件，如核反应堆、航天器、智能汽车等，对我们社会的安全极其重要^[1]. 传统的基于专家的诊断方法可以根据经验帮助人们发现设备的故障组件，然而关于新型高科技人造设备的经验却很少，因此传统的基于经验的诊断方法并不适用^[2]. 基于模型诊断（model-based diagnosis，MBD）技术不需要专家的经验，只用考虑设备的行为和结构信息就能够找到故障组件^[3]. 图1是MBD流程图：第①步根据系统的内部结构和行为进行建模；第②步给定系统的一些输入和预期输出，当预期的理论值和观察到的真实值行为存在明显的差异时，利用求解器对建模后的编码求解极小冲突集；第③步计算冲突集的极小碰集，即候选诊断；第④步利用贝叶斯定理，从众多候选诊断中计算出最有可能的故障组件^[4]. MBD最初被用于发现电子电路等硬件工件的故障^[5]，后来，由于其通用性，该方法被应用于许多不同的问题，包括卫星决策系统^[6]、汽车工业^[7]、电子制表软件等^[8-10].

图  1  MBD流程图

Figure  1.  MBD workflow diagram

下载: 全尺寸图片 幻灯片

因为被加工出来的组件内部结构是已知的，系统编码可以在离线阶段获取^[11]，诊断识别主要是在获取所有候选诊断后进行定向筛选，所以MBD主要耗时的阶段是冲突识别和候选诊断^[12-13]. 对于冲突识别阶段一般依靠哈斯图和先进的SAT求解器^[14]，它能够快速获得大量的冲突集^[15-16]. 而计算冲突集的极小碰集是一个NP-hard问题，计算出的极小碰集数量随冲突集数量的增加呈爆炸式增长，并且验证碰集是否是诊断所需的时间受极小碰集数量的影响，可见，候选诊断阶段在MBD中需要大量的时间开销^[1,17].

极小碰集最早算法是由人工智能专家Reiter^[1]提出，他利用碰集树（hitting set tree，HST）进行宽度优先的方法标记节点，并使用节点剪枝技术减少无解空间的搜索，但是由于剪枝策略可能会破坏算法的完备性. 1989年Greiner等人^[18]在HS-Tree算法的基础上提出了HS-DAG算法，利用有向无环图结构对相同节点进行重用，保证了算法的完备性. 2001年Wotawa等人^[19]提出了HST-Tree算法，通过对元素的唯一标识，不再需要有向无环图也能保证算法的完备性，同时大幅度减少了冗余节点的生成. 2003年姜云飞等人^[20]提出了Boolean算法，该算法在递归时每个节点最多生成2个节点，提高了计算效率. 2012年Pill等人^[21]对Boolean算法进行改进，利用单元素集合极小化冲突集，减少了树的深度. 由于求出的碰集不一定是极小的，碰集的极小化也是阻碍极小碰集的整体求解效率. 2018年刘思光等人^[22]提出了增量独立覆盖检测（incremental independent coverage checking，IICC）算法，利用独立覆盖思想判断碰集是否是超集，提高了碰集极小化效率. 2019年田乃予等人^[23]提出基于子集一致性检测去超集算法，缩小了解集极小化的规模. 2022年赵相福等人^[24]针对Boolean算法生成节点较多问题提出了增量布尔（incremental Boolean with IICC，IBWIICC）算法，该算法利用左分支增量求解右分支，减少了右分支的重复性计算. 除了基于枚举树的算法，还有一些其他策略的算法被提出^[25]，如：基于map-reduce环境的MHS²算法和多线程的HS-Tree算法^[17]，基于MCS特殊结构的LinerMerge和TreeMerge算法^[2,26]. 这些算法虽然能够快速的计算极小碰集，但是由于自身的局限性只能在特定场景工作^[27].

本文的主要贡献包括3个方面：

1） 提出了一种用于筛选冲突集的Q函数，利用碰集与冲突集的二元性，删除了大量冗余冲突集，在有限的时间内能够获得更多的极小势碰集.

2） 提出了一种数学编码的方式，在验证候选解可满足性时，只需要计算候选诊断的关键组件，减少大量不必要的计算.

3） 在ISCAS-85数据中，新提出的方法能够大幅度提高求解诊断的数量和质量；在诊断识别阶段，提高了为获得最终的故障位置的精准度.

1.   相关工作

在求解大规模电路时（极小碰集数量大于10¹⁰）^[11]，由于产生的冲突集数量较多，求出所有极小碰集已经不现实. 在故障识别阶段，如果是计算所有冲突集的极小碰集，那么得到的极小碰集都是该系统的候选诊断，显然，每个极小碰集中的组件（用碰集中的元素代替组件）都出现故障的可能性随组件个数的增加而降低，故同时出现故障组件的个数越少该极小碰集成为最终候选诊断的可能性要就越大^[28-30]. 2012年Pill等人^[21]通过宽度优先生成树，仅生成势最小的所有碰集，但是这种完备算法也只能对规模较小的冲突集有效. 2014年Metodi等人^[3]利用通过顶层诊断来求解所有极小势碰集（cardinality-minimal hitting set，CMHS），然后通过一一替换策略扩展其他极小碰集. 2015年Marques-Silva等人^[4]提出了过滤节点和过滤边概念，在默认一些组件是正常的前提下，能够快速的求出一个诊断，然而这样很有可能错过其他重要信息. 2019年Ignatiev等人^[31]提出了碰集二元性（hitting set dualization，HSD）算法，该算法是每求出一个冲突集就计算已有冲突集的极小碰集，然后通过SAT求解器来判断该碰集是否是诊断，这样虽然能够快速的获得一个诊断，然而频繁的调用碰集算法，且验证每个碰集是否是诊断时，都耗费了大量的求解时间. 2021年Kalech等人^[29]提出了One-SAT算法，该算法虽然把多观测问题的数据编码成单观测算法可计算的格式，但是随着观测次数的增加编码数量呈线性增长. 2022年Zhou等人^[32]在顶层诊断的基础上提出了压缩模型（compacted model with multiple observations，CMMO）算法，利用差异输入输出减少变量的生成，在多观测情况下效率有一定的提升.

在MBD中，获取最有可能的故障组件需要所有极小诊断的后验故障概率，然而验证所有极小碰集非常耗时^[14]. 国内外一些学者通过调用成熟的可满足性（satisfiability，SAT）求解器来提高求解效率，如wboinc，RC2等^[33-34]，这些求解器在计算规模较小的数据集时，因能够求出大部分甚至所有的冲突集，验证的极小碰集大都是诊断，相当于在验证可满足性问题时，大多数实例都是可满足的，故求解效率较高. 而处理大规模电路时，由于时间限制求不出所有的冲突集，导致大部分极小碰集都不是诊断，相当于大多数实例都是不可满足的，故求解效率较低^[35-36].

根据以上分析，我们得到阻碍获得诊断的2个关键点，即计算大规模冲突集的极小碰集和验证极小碰集是否是诊断. 对于前一点，因获取最终的诊断在很大程度上取决于极小势碰集，而又根据独立覆盖度思想，极小势碰集中大多数元素的独立覆盖度都大于1，故大量的冲突集对于该极小碰集来说都是冗余的. 为了能够在有限的时间内获得最优价值的极小碰集，我们设计了一个目标函数来缩小冲突集的规模. 该目标函数筛选冲突集主要有2个倾向，首先是选取含有元素较少的冲突集，因为在计算所有冲突集的极小碰集时，碰集需要与所有冲突集都有交集，所以该集合内的元素尤为重要；其次是选取冲突集中相对元素不相同较多的集合，这样是为了保证解集的多样性. 对于后一点，我们根据电路门的逻辑关系，设计了相应的数学表达式，只需要计算候选诊断的后继组件来验证候选解是否是诊断.

2.   基于模型的诊断问题

在本节主要介绍MBD问题的相关定义及概念.

2.1   基本定义

待诊断系统可定义为一个三元组$\langle$SD，Comps，Obs$\rangle$. 其中，SD是诊断系统的模型，为一阶谓词公式的集合；Comps为系统组件的集合，是一个有限常量集；Obs是观测到的系统行为(例如，观察到的系统输入和输出)，是一阶谓词公式的有限集.

系统模型SD为每个组件指定了其行为的一组可能假设，它至少包含一个指定的正常行为模式. 如果SD包含一些关于组件c在它有故障时的行为信息，我们说组件c有一个强故障模型. 否则，c有一个弱故障模型. MBD问题的一个解决方案是一个诊断. 诊断是一组关于系统组件行为的假设，这些假设构成了对观察到的行为的合理解释. 为了正式定义诊断，我们为每个组件c关联一个变量h(c)，称为健康变量，其值是观察到组件c的行为模式. 在逻辑术语中，h(c)=1代表组件c故障，h(c)=0(¬h(c))代表组件c正常. 如果所有组件分配其正常行为模式的SD和Obs不一致(如果系统输出的真实值和理论值不同，我们称为是不一致的，反之是一致的)，那么至少有一个组件有故障.

定义1. 诊断(diagnosis)^[17]. 当SD$\wedge$Obs$\wedge$ {h(c)|c$\in$$\Delta$，$\Delta$$\subseteq$Comps}$\wedge${¬h(c)|c$\in$Comps −$\Delta$，$\Delta$$\subseteq$Comps}是一致的，则$\Delta$被定义为该系统的诊断.

如果$\Delta$的任意真子集都不是诊断，那么$\Delta$是一个极小诊断. 对于该系统的任意一个诊断$\Delta$'，如果|$\Delta$'|≥|$\Delta$|，那么$\Delta$是一个极小势诊断.

定义2. 极小冲突集(minimal conflict set，MCS)^[1]. 当SD$\wedge$Obs$\wedge${¬h(c)|c$\in$f，f$\subseteq$Comps}不一致时，则f被定义为该系统的冲突集.

如果f的任意真子集都不是冲突集，那么f为极小冲突集. F是冲突集簇，F={f₁，f₂，$…$，f_n}.

定义3. 碰集（hitting set，HS）^[1]. 当S与任意f_i交集不为空，f_i$\in$F，则S被定义为F的碰集.

如果S的任意真子集都不是F的碰集，那么S是一个极小碰集；对于任意一个极小碰集S，如果|S'|$\geqslant$|S|，那么S是一个极小势碰集.

定义4. 隐式碰集（implicit hitting set，HIS）^[31]. F'是F的真子集，若S是F'的碰集又是F的碰集，那么S是F的一个隐式碰集.

下面通过例1对以上定义进一步说明.

例1. 图2描述了ISCAS-85数据中的c17电路，给定一组观测Obs，计算所有的候选诊断.

图  2  c17电路故障识别

Figure  2.  c17 circuit fault identification

下载: 全尺寸图片 幻灯片

在模型诊断中，合取范式（conjunctive normal form，CNF）公式可以用子句集表示^[31]，子句可以表示文字的集合，每个文字可以用变量表示，每个变量的取值为x或者补集-x. 在电路的系统描述中，每一个元件的输入输出均可以转化为CNF的形式，将转化的CNF子句存储到文件后，再使用SAT求解器读取此CNF文件进行求解，便将一个诊断问题转化为SAT问题. 对于图2中的示例图，其中图2（a）是ISCAS-85数据中c17电路，它由6个与非门组成{N₁，N₂，N₃，N₄，N₅，N₆}，其中只有系统的输入{i₇，i₈，i₉，i₁₀，i₁₁}和输出{i₁₄，i₁₅}是可观测的. 图2（b）是描述电路的门的性质（在该电路中描述的都是对应的与非门），图2（c）是c17电路转化成CNF公式的部分主要数据. 在计算诊断前对图2（a）中的编码进行了一个映射（用数字代替变量，如7=i₇，5=N₅）. 通过系统观测可知，系统输入{i₇，i₈，i₉，i₁₀，i₁₁}的值是{−7，8，9，10，11}，代表{0，1，1，1，1}（0表示低电平，1表示高电平），假设电路中每一个组件都是正常工作的，那么得到系统输出{i₁₄，i₁₅}是{14，−15}，而系统观测到的是{−14，15}，显然，该系统中必然存在至少一个故障组件才能解释观测情况.

首先利用MCS算法(每个冲突集中所有组件都正常工作是不可能的)求出所有极小冲突集{1，2，4}，{2，3，4}，{1，3，4}，然后利用MHS算法(结合每个冲突集最少一个故障组件)求出所有极小碰集{1，2}，{2，3}，{1，3}，{4}，其中{4}是极小势碰集. 如：{4}(对应N₄组件)组件故障，通过系统输入可以得到和系统观测一样的输出值，说明该碰集是一个诊断. 可见获得系统诊断取决于计算MCS的MHS.

在每个组件被生产出来时，我们是能够获得所有组件的先验故障概率（通过机器学习也可以获得）^[11]，并且假设所有组件故障是相互独立的. 例如组件N₁，N₂，N₃，N₄的先验故障概率是0.01，0.01，0.02，0.02，我们通贝叶斯定理得到所有组件的后验故障概率. 从表1中可以看出，{4}的后验故障概率最大，最有可能成为故障点.

表  1  组件的后验故障概率

Table  1.  Posterior Failure Probability of Component

诊断	先验故障	组件	后验故障
{1, 2}	0.000 1	1	0.000 3
{2, 3}	0.000 2	2	0.000 3
{1, 3}	0.000 2	3	0.000 4
{4}	0.020 0	4	0.020 0

下载: 导出CSV 

| 显示表格

2.2   HSD算法回顾

在模型诊断中，如果能够计算出所有的极小冲突集，那么计算所有极小冲突集的极小碰集就是诊断. 不幸的是，计算大规模电路的所有极小冲突集是耗时严重的^[22]，并且计算所有冲突集的所有极小碰集也是不现实的^[11,31]. 为了能够在有限时间内返回尽可能多的解，HSD算法每计算出一个冲突集，就计算已有冲突集的极小碰集，然后再验证极小碰集是否是诊断. HSD算法是目前求解故障诊断最好的算法之一，我们给出HSD算法的流程图并用一个例2进行说明.

例2. HSD算法计算图2（c）中的诊断.

把系统描述SD和Obs编码成SAT求解器可用的CNF数据格式后，假设HSD算法求出的第1个极小冲突集C₁={1，2，4}，那么{1}是C₁的一个极小碰集，也是该系统的一个候选诊断. 利用SAT求解器判断子句集CNF\{1}（表示CNF去掉含有组件1后的子句）是否可满足，因不可满足，故{1}不是诊断. 继续计算极小冲突集C₂={2，3，4}，计算{C₁，C₂}的一个极小碰集是{2};因为CNF\{1，2}是不可满足的，所以继续计算极小不可满足子集C₃={1，3，4}. 计算{C₁，C₂，C₃}的一个极小碰集是{4}；因CNF\{1，2，4}可满足，故{4}是一个诊断解. 继续计算{C₁，C₂，C₃}的极小碰集{1，2}；因CNF\{1，2}是可满足的，故{1，2}是一个诊断. 继续计算{C₁，C₂，C₃}的极小碰集{2，3}，因CNF\{2，3}是可满足的，故{2，3}是一个诊断. 当{C₁，C₂，C₃}已经没有新的碰集生成时算法截止.

值得注意的是，若先获得C₁的一个极小碰集是{4}，那么{4}也是{C₁，C₂，C₃}的极小碰集，可见{4}是一个隐式碰集. HSD虽然有可能快速得到一个诊断，但是频繁的调用碰集算法且验证得到的碰集是否是诊断，这都是非常耗时的. 图3是HSD算法的流程图.

图  3  HSD算法流程图

Figure  3.  HSD algorithm flowchart

下载: 全尺寸图片 幻灯片

3.   判断隐式碰集求解诊断

在本节介绍新提出的冲突集选取策略和数学编码方式.

3.1   冲突集的选取

在诊断时别中，确定最终的故障组件是由所有诊断的后验故障概率获得，换句话说，求得的诊断越多，确定真实故障组件的概率就越大^[3,11]. 现有的诊断算法在求解诊断时，虽然能够快速获得大量的极小冲突集，但是有些冲突集对获得精确诊断意义不大，反而会影响诊断的整体运行效率^[11]. 根据碰集与冲突集的对偶性，一些冲突集的获取也是不重要的^[31]. 在表1中，显然势最小的{4}在获得最有可能的故障组件中起着关键性作用，获得一些势比较大的诊断反而会影响算法的整体效率. 为了尽可能的获得故障组件并兼顾诊断算法的运行时间，我们先求出大量甚至所有的MCS，并设计了一个目标函数来删除一些质量较低的MCS，最后进行一次碰集算法来获得候选诊断. 设计的目标函数主要从极小势碰集和碰集的数量上评价一个冲突集的质量，因为现有MCS算法从系统编码中求出的MCS含有大量的冗余解，导致求解效率非常缓慢，甚至在规定时间内都很难求出一个诊断. 为了保证求出足够的候选解数量，我们只对相对质量较高的MCS进行碰集求解. 下面我们给出设计的目标函数并通过实例进一步说明.

C={e|e$\in$C₁$\wedge$e$\notin$C₂}，|C₁|$\leqslant$|C₂|.

Q(C₁,C₂)函数(简称Q函数)用来计算冲突集C₂相应C₁的值(质量)，值越大被选择的可能性就越高. 我们有2个倾向是不舍弃新添加的C₂. |C|表示C₁中的元素不在C₂中元素的个数，若|C|=0，则说明C₁是C₂的子集，C₂需要删除. 对于|C|/C₁，若C₁中的元素不在C₂中的占比越高，则C₁就不能代表C₂的可能性就越大(去掉C₂则可能不是整体的碰集概率就越大)，我们选择C₂的可能性就越高. 对于$({\text{|}}{{\text{C}}_2}| - {\text{|}}{{\text{C}}_1}|)/{\text{|}}{{\text{C}}_2}|$，若C₂中含有不同于C₁中的元素越多，那么生成的碰集个数就越多，选择C₂的可能性也就越大.

Q函数中存在一个阈值k，是一个大于0的正数，根据相应的数据集来判断是否选择该冲突集. 在图2(c)中，每一个组件都对应3个集合，我们对每一个集合进行排序标记，即S₁，S₂，…，S₁₈. 假设通过系统观测及MCS算法，求出C₁={S₁，S₂，S₅，S₈}，C₂={S₁，S₆，S₇}，C₃={S₂，S₈，S₉}. 虽然每一个MCS都是极小且互不相同，但是映射成组件的冲突集时$C_1'$={1，2，3}，$C_2'$={1，2，3}，$C_3'$={1，3}. 故利用MCS算法直接对系统编码计算可能会得到冗余的冲突集，从而计算碰集时会增加额外的开销.

Q函数能够很好的避免这种情况的发生. 当利用Q函数进行筛选时，$|C_3'| \leqslant |C_1'| \leqslant |C_2'|$，优先选择$C_3'$，当再添加$C_1'$时，因为Q($C_1'$,$C_2'$)=0<k，Q($C_1'$,$C_3'$)=0<k，所以删除$C_1'$，$C_2'$.

例3. 选取c880电路中映射成组件后的极小冲突集，C₁={3，4，21，23，42，48，76}，C₂={3，4，21，23，25，29，30，37，40，41，48，51，56，73，76，77}，C₃={3，4，21，23，25，29，30，37，40，48，51，56，60，73，76，77}，ε设置为0.1. Q(C₁,C₂)=1/7+9/16=0.705(>k)，Q(C₂,C₃)=1/16+ 0/16=0.063(<k). CMHS({C₁,C₂})=CMHS({C₁,C₂,C₃})，|{mhs|mhs$\cap$C₃$\ne$$\varnothing$，mhs$\in$MHS({C₁,C₂})}|/ |MHS({C₁,C₂,C₃})|=0.938.

我们通过Q函数删除了C₃，通过MHS算法计算{C₁，C₂}与{C₁，C₂，C₃}含有相同的极小势碰集，且二者含有93.8%相同的极小碰集. 在诊断识别阶段，我们最终目的是为了获得一个最有可能的故障点(后验故障排名)，而并非精确的概率值. 因此删除低质量的冲突集对诊断识别阶段影响并不大(从表1也可以看出主要取决于极小势诊断). 在大规模电路中(c7522，c6288)，直接对所有冲突集求解极小碰集是不现实的，这是因为MCS的个数远远大于10万且大部分集合的势大于500(获取MHS是一个NP-hard的问题，这可能导致诊断的数量与组件的个数呈指数级关系)，所以约简他们的规模是非常有必要的. 算法1是利用目标函数Q选取MCS的算法.

算法1. MCS选取算法.

输入：冲突集簇MCSs，阈值k;

输出：冲突集簇MCSs.

① MCSs$\leftarrow$Order(MCSs); 　/*升序排序*/

② for(i=2; i≤|MCSs|; ++i)

③ 　for(j=1; j<i; ++j)

④ 　　c={e|e$\in$c_i$\wedge$e$\notin$c_j,c_i$\in$MCSs,c_j$\in$MCSs};

⑤ 　　if((|c|/|c_j|+(|c_i|-|c_j|)/|c_i|)<k)

⑥ 　　　MCSs\c_i;　　 /*删除c_i*/

⑦ 　　end if

⑧ 　end for

⑨ end for

算法1首先对所有MCS按照势进行一个排序（第1行），然后对每一个MCS进行筛选（第2~3行），如果通过Q函数计算的值小于k（第5行），则删除该MCS（第6行）.

因为计算冲突集的极小碰集后需要再对其进行验证是否是诊断，SAT求解器虽然能够高效的判断解集的可满足性，但是频繁的调用求解器也是一个极具耗时的事情. 下面我们给出一种适用于判断候选解是否满足所有观测的数学编码方式（式（2）），并提出了一种优化策略大幅度缩减需要计算组件的规模.

式（2）利用了电路门的性质生成，$\neg N$表示组件正常，o表示组件的输出，i表示组件的输入（i，o取值0或1）. 根据电路的逻辑关系我们进行数学编码，假设与非门有2个输入{i₁，i₂}和1个输出{o₁}，根据与非门逻辑关系（输入有0，输出为1），则数学公式可以表示为o₁=1-i₁i₂，（i₁，i₂，o₁取值为0或1）. 同理，其他电路门也可以用数学公式表示. 式（2）的7个公式包含了ISCAS-85基准数据中所有的电路类型，而该数据集包含了现实生活中1 300多种故障类型，在模型诊断中被众多学者认可并使用^{[2-4,11,22-26,30-34]}.

我们利用式（2）给出c17电路中 组件N₄的输出值i₁₅的数学编码方式：i₁₅=1−i₁₃i₁₇=1−(1−i₈i₁₂)(1−i₁₁i₁₂) =i₈+i₁₁−i₈i₁₁−i₉i₁₀i₁₁−i₈i₉i₁₀+2×i₈i₉i₁₀i₁₁−i₈i₉²i₁₀²i₁₁=i₈+i₁₁−i₈i₁₁−i₉i₁₀i₁₁−i₈i₉i₁₀+i₈i₉i₁₀i₁₁.

因为i的值只能为0或1，所以在计算等式右侧的值时，可以其去掉指数，如i₉²=i₉. 而对于其他的输出组件，如N₃，不必要重新从输入端开始计算，这是因为在计算N₄的值时，N₂和N₆的输出值已经获取，所以只需要从他们开始计算即可.

3.2   代数表达式

在c17电路中，因为只有系统观测{i₇，i₈，i₉，i₁₀，i₁₁，i₁₄，i₁₅}是已知的，其余变量及组件是否正常工作是未知的，所以要想判断某些组件故障后是否使输入和输出相一致，则需要重新计算输出组件的输出值. 而计算输出组件的输出值需要先计算其他组件的输出值. 下面通过算法2给出每个组件计算的顺序.

算法2. 诊断的判断算法.

输入：Obs，Comps，SD，DiagSet;

输出：DiagSet.

① Order=$\varnothing$;

② Sys_in$\leftarrow$Obs; /*Sys_in存储已计算变量*/

③ while(Comps) /*Comps是否为空*/

④　 for(c$\in$Comps)

⑤　　 if(c.input$\subset$(Sys_in$\cup$Order))

⑥　　　 Order$\leftarrow$Order$\cup$c;

⑦　　　 Comps\c; 　/*删除c*/

⑧　　 end if

⑨　 end for

⑩ end while

⑪ for(Diag$\in$DiagSet)

⑫　 for(Diag$\in$DiagSet)

⑬　　 n_i$\leftarrow$式(2)(Diag); /*计算所有组件*/

⑭　 end for

⑮　 if(输出组件的值和系统观测的值不相同)

⑯　　 DiagSet\Diag; 　/*删除该候选解*/

⑰　 end if

⑱ end for

算法2先对组件进行排序然后判断候选解是否是诊断. 初始时Order为空，Sys_in存储系统的所有输入（第12行）. 若未排序的组件集为空，则算法结束（第3行），否则循环判断剩余未排序的组件，若该组件的所有输入都已经选取，则该组件存入Order中，并把该组件从未排序的组件中删除（第5~10行）.

例如c17电路，初始时Sys_in存储{i₇，i₈，i₉，i₁₀，i₁₁}，因只有组件N₁和N₅的输入值{i₇，i₉}和{i₉，i₁₀}属于Sys_in，故Order={N₁，N₅}；因N₂和N₆的输入值{i₈，N₁}，{i₁₁，N₁}属于{Sys_in，Order}，故Order={N₁，N₅，N₂，N₆}；因N₃和N₄的输入值{N₂，N₅}，{N₂，N₆}都属于{Sys_in，Order}，故Order={N₁，N₅，N₂，N₆，N₃，N₄}.

算法2的11~18行是对候选解进行检验，首先计算每一个候选解对应的组件输出值（第12~14行），然后判断观测值和真实值是否相同，若不相同，则从候选解中删除该解（第15~17行）. 该算法主要的缺点是对每一个候选解都需要重新计算所有的组件. 为了尽可能的减少计算组件的个数，我们发现若通过系统的输入，可以得到所有组件都正常情况下的理论值. 利用这一点，若检验一个候选解是否是诊断，我们只需要重新计算故障组件的影响部分.

定义5. 后继组件. 组件N_i到达系统任意输出端所经过的组件，称为N_i的后继组件.

在图2（a）中，N₂的所有后继组件为{N₃，N₄}，N₁的所有后继组件为{N₂，N₆，N₃，N₄}. 我们可以看到，当组件{N₂}故障时，组件N₁，N₅，N₆不会受到影响. 此时，判断候选解{N₂}是否是诊断时，只需要重新计算它的后继组件{N₃，N₄}的输出值. 对于N₁，N₅，N₆的输出值只需要用理论值代替，而N₂不在后继组件中，故只需要翻转N₂的正常输出值. 通过诊断的性质可知，当判断每个候选解是否满足所有观测时，我们只需要计算候选解的所有后继组件，对于不在后继组件的候选解组件，只需要改变该组件的门，即翻转该值（0变为1，1变为0，）. 翻转策略如式（3）：

例4. 继续例2，利用算法2判断候选解{N₁，N₆}是否是诊断解.

由系统的输入，可以得到{i₁₆，i₁₂，i₁₃，i₁₇，i₁₄，i₁₅}的理论值分别是{1，1，1，0，0，1}. N₁的后继组件是{N₂，N₆，N₃，N₄}，N₆的后继组件是{N₄}，二者的关键组件取交集是{N₂，N₆，N₃，N₄}. 因诊断解N₂不在后继组件中，故只需要利用式（3）反转N₁的理论值. N₆故障，N₂，N₃，N₄正常，带入式（2）（3），可以得到在组件N₁，N₆故障的情况下，得到的理论输出值{0，1}与系统观测的输出值一致，可见，候选解{N₁，N₆}是一个诊断解.

通过计算故障组件的后继组件，避免了一些不相关组件的重复计算. 显然，当故障组件越靠近输出端，重新计算的组件越少. 如：判断候选解{N₄}是否是一个诊断，则只需要翻转N₄的值即可. 不幸的是，若判断候选解的越靠近输出端，则后续的组件可能占总体组件的绝大部分. 下面我们通过命题1，进一步缩减计算组件的个数.

命题1. 若故障组件的输出不影响后继组件的输出，则无需计算该故障组件的输出值.

考虑到图2（a）的候选解{N₁，N₆}，只有候选解中的组件故障，其余组件都是正常的. 因为i₈的输入为0，则不论i₁₂取何值时，i₁₃的取值都为1. 可见N₁故障并不影响i₁₃的取值，故在求解N₁的后续组件时，不需要添加N₂的后继组件. 而N₆的输出值需要i₁₁和i₁₂共同决定，故N₁的后续组件需要添加N₆及其后继组件. 最终{N₁，N₆}的后继组件有{N₆，N₄}. 计算后继组件同例4这里不再赘述，

我们利用式（3）结合命题1给出组件N₄的输出值i₁₅的数学编码方式：i₁₅=1−i₁₃i₁₇=1−(1−i₈i₁₂)(i₁₁i₁₂)=1−i₁₁i₁₂+i₈i₁₁i₁₂.

可见通过命题1，我们少计算了一半的后继组件. 算法3是添加命题1的候选解判定算法.

算法3. 优化的诊断判断算法.

输入：Obs，Comps，SD，DiagSet;

输出：DiagSet.

① Rear[]=$\varnothing$;

② for(N_i$\in$Comps)

③　 if(N_i.output$\in$N_j.input, N_j$\in$Comps)

④　　 Rear[N_i]$\leftarrow$N_j; /*N_i的后续组件N_j*/

⑤　 end if

⑥ end for

⑦ for(N_i$\leftarrow$Order.pop) /*组件排序*/

⑧　 for(N_j$\in$Rear[N_i])

⑨　　 Rear[N_i]$\leftarrow$Rear[N_j];

⑩　 end for

⑪ end for /*递归统计每个组件的后继*/

⑫ for(c_i$\in$Comps)

⑬　 n_ci$\leftarrow$式(2)(c_i);

⑭　 end for /*计算所有组件的理论值*/

⑮ if(理论值与系统观测值一致)

⑯　 return;

⑰ end if

⑱ for(Diag$\in$DiagSet)

⑲　 for(c_i$\in$Diag)

⑳　　 if(后继组件受c_i影响) /*命题1*/

㉑　　　 Wait$\leftarrow$Rear[c_i];

㉒　　 end if

㉓　 end for

㉔　 for(c_i$\in$Diag$\wedge$c_i$\notin$Wait)

㉕　　 ${{{n}}_{{c}}}_{_{{i}}}$$\leftarrow$式(3)(${{{n}}_{{c}}}_{_{{i}}}$);

㉖　 end for /*翻转不在后继组件中的组件*/

㉗　 for(c_i$\in$Wait)

㉘　　 ${{n}}_{{c}_{i}}$$\leftarrow$式(2)(3)(Diag); /*后继组件*/

㉙　 end for

㉚　 if(输出组件和系统观测的值不相同)

㉛　　 DiagSet/Diag;

㉜　 end if

㉝ end for

算法3初始化所有组件的后继组件为空（第1行）；接着遍历每个组件输入，如果组件N_i的输出属于N_j的输入，则组件N_j是N_i的后继组件（第2~6行）；递归的添加每个组件的所有后继组件（第7~11行）. 然后利用系统输入及式(2)计算所有组件的理论值（第12~14行）. 如果理论值和系统观测值一致，则不存在故障组件，直接返回（第15~17行）. 依次判断所有的候选解，通过命题1计算所有需要计算的组件（第19~23行）. 若诊断解中的组件不在后继的组件中，则直接翻转该组件的理论值（第2425行）. 利用式(2)(3)计算所有后继组件的值（第27~29行），若存在输出的组件值与系统观测值不相同，则从解集中删除该候选解（第30~32行）.

因为我们最终是计算所有的极小诊断，而计算部分冲突集的极小碰集后需要验证是否是诊断，也就是说，需要验证部分冲突集的极小碰集是否是该系统的隐式碰集，所以我们对算法1，2，3进行合并，命名为JIHS（judgment implicit hitting set）算法. 下面我们给出具体的诊断算法.

算法4. JIHS算法求解诊断.

输入：Obs，Comps，SD，ε，MCSs;

输出：DiagSet.

① DiagSet=$\varnothing$，MHSs=$\varnothing$;

② MCSs$\leftarrow$算法1(MCSs); /*选取MCS*/

③ MHSs$\leftarrow$MHS(MCSs); /*计算极小碰集*/

④ DiagSet$\leftarrow$算法3(MHSs); /*检验是否是诊断*/

算法的中间变量：ε，MHSs，DiagSet分别代表阈值、极小碰集的数量、诊断的数量. 算法4主要先对冲突集进行筛选，然后计算冲突集的极小碰集(可以直接调用碰集算法^[22]). 注意的是，这里每求解一个极小碰集就可以直接检验该解是否是诊断，并非把所有的碰集都计算完毕再验证. 算法4中调用碰集算法和对比算法一致，因算法1只是对冲突集进行选取，运行时间相对于验证候选解忽略不计，我们分析检验碰集是否是诊断的时间复杂度.

时间复杂度分析：假设候选解的个数为n，组件个数为m. 选取每个组件的后继组件时间复杂度为O(m²)；计算所有组件的理论值是O(m)；在验证一个候选解是否是诊断时，最坏的情况下，需要重新计算所有的组件，时间复杂度是O(m)，故总体时间复杂度是O(mn). 因为在重新计算所有组件时，由于命题1的存在，计算组件的个数要远远小于m，最好的情况下，只翻转一个组件的值，时间复杂度是O(n).

4.   实验分析

在本节中我们对新提出的JIHS算法进行实验分析，对比算法采用目前效率较高的CMMO，HSD，One-SAT算法，所有算法都统一使用RC2求解器，这是求解诊断效率最高的求解器之一^[33-34]. 实验平台：Ubuntu 16.04 Linux Intel Xeon E5-1607@3.00GHz 16GB RAM C++，实验数据采用国际标准的ISCAS-85电路数据，该数据根据真实的环境系统生成，由DXC'09的研究人员注入故障，主要用来比较模型诊断算法求解效率.

本文主要从冲突集的选取和诊断验证2个方面进行综合考虑，为了公平性，在计算极小碰集时，统一使用目前较快BWIICC极小碰集算法^[22]. JIHS算法与对比算法都是一种不完备的算法，计算规模不同的问题比较的标准不同，具体看实验分析.

在模型诊断中，计算诊断的时候需要先求出极小冲突集，再计算极小冲突集的极小碰集. 在计算MHS时，对MCS进行一个极小化后的预处理是一个有效的策略. 图4主要从MCS极小化和诊断验证2个角度进行分析，横坐标都表示运行实例的个数，图4（a）纵坐标表示MCS极小化的比值，图4（b）纵坐标表示RC2求解器和JIHS算法判断候选解是否是诊断所花费的时间. 除了规模较小的c17电路，我们对ISCAS-85其他数据集进行了测试，每个数据集随机选择10组带故障的观测，对MCS约简比进行升序排序. 其中c432电路最高约简82.3%，平均约简71.2%，所有电路平均约简35.1%. 在候选解判断的过程中，我们对300个实例进行测试，仅有少数实例使用求解器比我们的好，其他都是JIHS算法的候选判断要快，最高达5倍以上.

图  4  MCS极小化比值和诊断验证运行时间

Figure  4.  MCS minimization ratio and diagnosis judgement runtime

下载: 全尺寸图片 幻灯片

在图5中，我们随机注入了5个故障组件，可以计算出所有的MCS，CMMO，HSD，One-SAT算法运行时间分别是89.5s，109.7s，124.1s. 图5中横坐标轴表示k的取值范围，图5（a）纵坐标表示3种算法运行时间与JIHS的比值，图5（b）纵坐标表示JIHS算法相对与对比算法求解冲突集和诊断数量的比值. k=0时表示只对MCS进行一个极小化操作，MCS的数量减少了22%，JIHS算法求解诊断的数量与对比算法的数量一致，运行时间比对比算法快1倍以上. 在对MCS进行极小化后，随着k值的不断增加删除冲突集的数量也在增加，从而导致隐式碰集（诊断）的减少. 在k=0.2时，JIHS算法比对比算法快接近1个数量级，而求解诊断数量仍在85%以上.

图  5  10个故障组件诊断实例

Figure  5.  10 Fault component diagnosis instances

下载: 全尺寸图片 幻灯片

在图5（a）中，当k=0，求解效率比其他算法至少快一倍，而图5（b）中要有一个数量级的提升. 在故障组件较少的数据中，因为在计算出所有MCS后，每一个MHS都是可满足的，所以SAT求解器判断MHS的时间具有较高的效率.

在图6中，我们随机注入了15个故障组件，由于生成的冲突集数量较多，规定所有算法计算10万解集停止，CMMO，HSD，One-SAT算法运行时间分别为995.2 s，1 178.6 s，1 554.5 s. 当系统规模较大且故障组件较多时，由于生成冲突集的数量较多，导致碰集的求解时间占据总体求解的大部分时间. 而对比算法频繁的调用碰集算法，求解效率较低，当k=0时，JIHS算法比其他算法快1个数量级. 随着k值的增加，JIHS算法获得诊断的数量也随着下降，在k=0.2时，MCS的数量是对比算法的0.1倍，诊断数量是0.55倍，求解效率提高约30倍.

图  6  15个故障组件诊断实例

Figure  6.  15 Fault component diagnosis instances

下载: 全尺寸图片 幻灯片

在图7中，我们随机注入了40个故障组件，所有算法的截止时间是3 600 s. 图7（a）纵坐标表示求出诊断的比值，图7（b）纵坐标表示求出极小势的比值. 由于在有限的时间内无法求出所有的冲突集，使大量的碰集都不是诊断，对比算法在判断每个碰集是否是诊断时也都耗费了大量的时间. 而我们的检验算法对于非诊断解判断具有一定的优势，只需要找到系统观测的一个不同组件即可. 而又因为命题1，只需要找到候选解影响的组件，极大减少了组件的不必要计算. 在图7（a），JIHS算法比其他算法要多求出1~2个数量级的诊断，随着k值的增大，求出的诊断数并不是越来越少. 这是因为在规定时间内无法计算出所有的极小碰集，导致一些诊断数量的丢失(相当于陷入了无解空间)，而随着不断减少低质量的冲突集，JIHS算法能够获得高质量冲突集更多的极小碰集. 在图7（b），随着k值的增加，由于删除了较多相似的冲突集，留给大量的时间计算极小碰集，而这些极小碰集都倾向于势较小的解，JIHS算法求出的极小势诊断比其他对比算法要多10~200倍，这也大幅度增加我们获得最有可能的故障位置的精准度.

图  7  40个故障组件诊断实例

Figure  7.  40 Fault component diagnosis instances

下载: 全尺寸图片 幻灯片

5.   总　　结

基于模型诊断是著名的系统调试方法，它对日益复杂的软件、硬件和网络物理系统的调试尤为重要. 在求解多故障诊断问题时，由于庞大的冲突集数量，导致许多诊断算法很难在有限的时间给出一个具体的故障组件解释. 本文提出了一个新型高效的诊断算法JIHS，该算法主要对候选解的获取和检验2个方面进行优化，在诊断识别阶段，我们首先设计了一个目标函数，主要倾向于获得势最小的诊断，因为极小势诊断对确定最有可能的故障组件起到至关重要的作用. 由于计算出的候选解大部分都不是诊断，基于此，我们根据电路组件的逻辑关系进行编码，通过重新计算关键组件来判断候选解是否是诊断，极大提高了检验效率. 最后，我们通过实验，从诊断的效率和数量2个方面验证本文的所提算法的有效性.

作者贡献声明：欧阳继红给出指导意见并修改论文;黄森提出了算法思路负责撰写论文.