结合故障输出结构特征的极小冲突求解算法

基于模型诊断(model-based diagnosis)是人工智能领域中的重要研究方向,而基于极小冲突求诊断是求解诊断问题的经典方法,因此求解极小冲突是诊断中的一个重要步骤.通过对电路模型特征的研究,结合CSRDSE极小冲突集求解算法,提出结合故障输出结构特征的极小冲突求解算法MCS-SFFO：首先对CSRDSE算法的剪枝规则进行了改进,避免对集合枚举树SE-Tree中非冲突集叶节点对应子叶节点的访问;其次,提出故障输出无关元件集与故障输出相关元件集等相关概念,并根据系统描述和观测给出求解故障输出无关元件集的方法;最后,提出非冲突集定理,即故障输出无关元件集的子集不是冲突集,并根据非冲突集定理,给出极小冲突集求解算法MCS-SFFO.MCS-SFFO算法在基于CSRDSE算法求冲突集方法的基础上对无解空间进一步剪枝,减少了调用SAT求解器的次数.实验结果表明：与CSRDSE算法相比,MCS-SFFO算法求解效率明显提升.     

结合SE-Tree结构特征的极小碰集求解算法

在结合SE-Tree计算集合簇极小碰集的过程中,现有算法会对大量不会产生碰集的冗余节点进行访问.这无疑将影响算法的效率,冗余节点比例越高,影响越大.通过对SE-Tree中叶节点的特殊性质的分析,并结合现有碰集算法有解空间中冗余节点的特征,提出非解冗余节点概念.在对SE-Tree的结构特征进行深入分析基础上,根据非碰集的子集也不是碰集的特点,提出辅助剪枝的概念,通过在剪枝树上设置剪枝判定节点,减少对极小碰集求解过程中无解空间的访问;针对较大规模问题,还提出结合多级辅助剪枝树的极小碰集求解算法,进而较大程度地减少对非解冗余节点的访问;根据多级辅助剪枝树及SE-Tree的结构特征,给出提前终止算法的判定条件,并证明了此算法的正确性.实验结果表明:与效率较高的Boolean算法相比,该算法高效且易于实现,尤其是对规模较大的问题,效率能提升1个数量级.     

基于伪故障度生成枚举树的极小诊断求解方法

基于模型诊断(model-based diagnosis, MBD)是人工智能领域一个极富有挑战性的问题.近年来,SAT求解器发展十分迅速,且已被应用于求解基于模型诊断问题并取得了显著成果.在对基于模型诊断问题求解方法LLBRS-Tree深入研究的基础上,根据电路组件的拓扑结构信息、系统的观测行为和预期行为之间的差异以及集合枚举树的特点,首次提出了组件静态伪故障度和动态伪故障度的概念.计算所有组件的静态伪故障度,并根据静态伪故障度从大到小对组件重新排序,生成新的枚举树;并且在遍历到新的极小诊断解时,更新相关组件的动态伪故障度,动态建立新的枚举树,从而能较快地搜索到极小诊断解,删除大量冗余解,较大程度地减少SAT求解器的调用次数.实验结果表明:随着诊断系统中组件个数的增多以及极小诊断解长度的增加,提出的方法较LLBRS-Tree方法效率提升明显.     

一种基于ATMS的求解所有极小冲突集的新方法

在Reiter算法的基础上,本文提出一种基于ATMS的求解所有极小冲突集的新方法。其中,对每个元件模型最多调用一次就可求出所有的极小冲突集,防止了ATMS的多次调用,因而能够提高效率。本文提出了极小依赖集的概念,并据此对ATMS求得的极小冲突集进行了分类;分析了算法的复杂度,并将新方法与相关工作进行了比较。该算法程序容易编制,而且效率高。     

极小碰集求解中候选解极小性判定方法

极小碰集问题是人工智能中的重要问题,应用广泛.碰集极小性判定,作为极小碰集求解过程中的关键步骤,效率的高低会对极小碰集求解算法的耗时产生直接影响.现有的极小碰集求解算法主要使用子集检测方法进行碰集极小性判定.针对子集检测方法在极小碰集簇规模较大时效率较低的问题,提出了基于元素独立覆盖度检测的碰集极小性判定方法——ICC方法,剥离了碰集极小性判定耗时与极小碰集簇大小的相关性;通过深入分析增量求解过程中非极小碰集的产生原因,给出了ICC方法的增量判定形式ⅡCC方法,使其可以尽早发现并丢弃非极小候选解,为使用其增量极小碰集求解算法带来额外的剪枝效果,进一步提升算法的效率.实验结果表明：该方法易于实现,可扩展性强,对于当前效率较高的Boolean算法,使用ⅡCC方法后,算法可求解问题的规模和整体效率均有明显提升,效率提升最高达4个数量级以上.     

利用CSP求解极小碰集的方法

基于模型诊断是人工智能领域中具有挑战性的问题,包含了很多人工智能中的关键问题,其研究对整个人工智能领域起着重要推动作用.在基于模型诊断中,候选诊断结果通常由所有极小冲突集对应的所有极小碰集所描述,求出所有极小碰集是其核心问题之一.提出一种将极小碰集问题转换为约束满足问题的方法,该方法调用成熟的CSP求解器进行求解,扩展了约束可满足问题的应用领域.首次提出hard-冲突集和soft-冲突集的概念,并给出利用所提的方法分别求解具有一些特征的极小碰集：小于固定长度、不含特定元素及包含hard-冲突集和soft-冲突集.实验结果表明,提出的方法易于实现、扩展性强,对于特定类型极小碰集问题的求解效率较高.     

结合DOEC极小化策略的SAT求解极小碰集方法

在基于模型诊断中,诊断解通常是根据极小冲突集合簇进行相应的计算得到所有的极小碰集,所以提高极小碰集的求解效率是模型诊断的核心问题.因此提出结合基于元素覆盖集合度(degree of element coverage, DOEC)极小化策略的SAT求解极小碰集的方法SAT-MHS(satisfiability problem-minimal hitting sets).首先,方法SAT-MHS将碰集求解问题转换成SAT问题,即把所有的冲突集合以子句形式表示成SAT的输入CNF进行迭代求解.其次,提出比现有的基于子超集检测极小化策略(sub-superset detecting minimization, SSDM)更为高效的DOEC极小化策略进行极小化处理.由实验数据可见,与SSDM极小化策略相比,其优点是缩减了求解空间和迭代求解次数,尤其当求解规模较大问题时,其极小化效率越高.主要是因为其极小化不会随着待求解问题规模的增加而增加,而是只与冲突集合簇的大小相关,因此时间复杂度较低.实验结果表明,对于一些较大的实例,与目前效率最好的Boolean方法相比,SAT-MHS方法高效且易于实现,求解速度能提高10~20倍,DOEC极小化策略对比传统SSDM极小化策略能达到40倍左右.     

基于动态极大元素覆盖值的极小碰集求解算法

在基于模型诊断(model-based diagnosis, MBD)中,因为所有极小冲突集的极小碰集就是待诊断系统的诊断结果,所以利用所有极小冲突集构造极小冲突集合簇,并基于极小冲突集合簇计算极小碰集是诊断的关键步骤.提出一种基于动态极大元素覆盖值求解极小碰集的新算法.该算法按照元素的元素覆盖值从大到小的顺序依次处理元素,并在求解碰集的过程中加入启发式策略和剪枝策略,使得搜索空间极大减少;利用邻接链表存储输入的极小冲突集合簇,邻接链表相对于用矩阵作为存储结构有较好的空间开销且通过邻接指向能快速地找到元素可以覆盖的集合簇中的元素;每得到一个碰集便使用极小碰集判定规则进行筛选,因此算法结束时可以产生而且仅产生所有的极小碰集.实验结果表明该算法有较高的计算效率.     

一种求解极小诊断的遗传模拟退火算法

基于模型的诊断方法是人工智能领域发展起来的一个十分活跃的分支.在该方法中,由极小冲突集求解极小击中集的过程是一个NP-Hard问题.尽管人们提出了不少算法,但是各种算法的效率仍然不是十分理想.通过将该问题映射到0/1整数规划问题,提出了将遗传算法与模拟退火算法相结合的问题求解思想.在给出遗传模拟退火(genetic simulated anncaling,简称GSA)算法和算法各个参数的同时,对算法的性能和求解精度进行了测试.GSA算法不仅比传统的算法效率有很大的提高,而且在冲突集基数大于35的情况下,较单独使用GA的算法在效率上提高约1/3～1/2.在求解精度上,GSA算法在大多数情况下能够求出98%～100%的极小诊断.     

求极小碰集的蛛网算法

为降低空间复杂度和减少搜索时间,结合极小碰集的特点和生物学中蜘蛛捕食思想,提出了一种搜索极小碰集的蛛网算法。该方法考虑集合之间的相关性,并构造能在蛛网上寻路的访问蜘蛛用于寻找蛛网内集合的所有极小碰集。在该算法中,所提出的访问蜘蛛生成和搜索策略能够降低空间复杂度和减少搜索时间。将此算法与其他的极小碰集算法进行比较,实验结果表明,该算法在保证得到所有极小碰集的前提下,具有较低的空间复杂度和较高的时间效率。     

求解掩盖故障的新方法

针对用单故障策略诊断多故障时可能出错的原因,提出一种确定性的,效率较高的求解掩盖故障的算法;首先通过定义寻找系统中可能存在的隐藏故障集;然后在隐藏故障集中寻找可能存在掩盖故障的故障元件集以及冲突集;其次通过建立冲突集簇的相关矩阵,把求解冲突集簇掩盖故障的问题转换为求解集合覆盖,并用确定性方法DNA粘贴模型来求解,获得全部真实解;最后通过实例验证,该方法是一种并行算法,可行、简单、有效。     

基于动态极大度的极小碰集求解方法

在计算集合簇的碰集时,结合SE-Tree(set enumeration tree)形式化地表达计算过程,逐步生成所有的极小碰集.并在SE-Tree中添加了终止结点,避免了非极小碰集的产生,并且不会因剪枝而丢失正确的解.提出未扩展元素度的概念和结点度的概念,进而在扩展SE-Tree结点时按照未扩展元素度由大到小的顺序扩展,极早地生成集合簇的碰集,减少枚举树生成的结点个数,并且直接根据结点度得出结点对应的集合是否为集合簇的碰集,避免计算集合是否为集合簇的碰集.实验结果表明,该算法程序容易编制且效率较好.     

基于模型诊断中结合问题特征的新方法

基于模型诊断一直是人工智能领域中热门的研究问题.近些年来,随着SAT求解器效率的逐渐提高,基于模型的诊断也被转换成SAT问题进行求解.在对基于模型诊断求解方法CSSE-tree深入研究基础上,结合诊断问题和SAT求解过程的特征,给出先对包含组件个数较多的候选诊断进行求解的方法,进而减小SAT求解问题的规模;在对极小诊断解和非极小诊断解剪枝方法的基础上,首次提出非诊断解定理及非诊断解空间的剪枝方法,有效地实现了对诊断的无解空间进行剪枝.根据组件个数较多的候选诊断先求解及有解无解剪枝方法特征,构建基于反向搜索的LLBRS-tree方法.实验结果表明:与CSSE-tree算法相比,LLBRS-tree算法减少了SAT求解次数、减小了求解问题规模,效率较好,尤其是求解多诊断时效率提高更为显著.     

结合互补度的基于扩展规则#SAT问题求解方法

#SAT问题又称模型计数(model counting)问题是人工智能领域的研究热点之一,在人工智能领域被广泛应用.在对基于扩展规则的#SAT问题求解方法CER(counting models using extension rules)深入研究的基础上,提出一种结合互补度的#SAT问题求解方法.在计算给定子句集的模型个数时,利用SE-Tree(set enumeration tree)形式化地表达计算过程,逐步生成需要计算的子句集合,并在SE-Tree中添加终止结点,避免大部分含互补文字子句集合的生成,且不会因剪枝而导致求解不完备.提出互补度的概念,在扩展SE-Tree结点时按照互补度由大到小的顺序扩展,较早地生成含互补文字且长度较小的子句集合,有效减少枚举树生成的结点个数,进而减少对子句集合判断是否含互补文字的计算次数.实验结果表明：与CER方法相比该方法效率较好,且进一步改进了CER方法在互补因子较低时求解效率低下的不足.     

求解最小完全测试集的第一原理方法

应用第一原理的故障诊断思想,基于故障测试矩阵,提出了一种根据系统每一个故障都可检测的行为与系统所有故障不能检测的行为之间的不相容推理技术,来判断和求取系统存在的所有最小完全测试集的方法。方法分两步：一是根据系统的结构和测试矢量等知识,结合故障测试矩阵,识别冲突集候选;二是根据冲突集候选,确定最小命中集合组,生成最小完全测试集。该方法可有效求解最小完全测试集,减少测试矢量施加的工作量,提高故障诊断的效率。     

基于极小碰集求解算法的测试向量集约简

自动测试向量生成的目的是对特定的故障模型确定1个高质量测试向量集使得芯片(设计)的故障覆盖率达到期望值,在芯片测试中是非常重要的环节.TetraMAX ATPG 2018是众多ATPG工具中功能最强、最易于使用的自动测试向量生成工具,可以在很短的时间内生成具有高故障覆盖率的高质量测试向量集.提出基于极小碰集求解算法的极小完全测试向量集求解算法,通过对测试向量集约简问题重新建模,利用极小碰集求解算法对TetraMAX ATPG 2018产生的测试向量集进行约简.利用这一算法可以有效地缩减测试向量集规模,且保证其故障覆盖率不变,对降低芯片的测试成本有着重要的现实意义.实验针对固定型故障,结果表明：该算法具有良好的约简效果,而且可以保证所得测试向量集中不包含冗余的测试向量.     

用对分HS-树计算最小碰集

在基于模型的诊断中,利用冲突集计算最小碰集是其关键的步骤,因为所有冲突集的最小碰集就是所考察系统的诊断.在Reiter的方法中,要用HS-树(图)来计算最小冲突集的最小碰集.HS-树的计算量比较大,且又会因为剪枝的问题而剪掉真实解.提出了用对分HS-树(binary hitting set-树,简称BHS-树)计算最小碰集的方法.这种方法的优点是:(1)产生的树的节点数明显少于HS-树,因而效率较高;(2)解决了因为剪枝而产生的最小碰集丢失的问题;(3)在新增加冲突集时不必完全重新计算,只需在原BHS-树     

基于子集一致性检测的诊断解极小性判定方法

基于模型诊断作为克服第1代诊断系统的缺陷而出现的智能诊断推理技术,现已成为十分活跃的人工智能研究分支,随着相关技术的不断发展,应用愈加广泛.其中,大多数研究集中于诊断求解过程,而诊断解的极小性检测方法保证了最终求得诊断解的极小性,也是问题求解过程中至关重要的一步.传统诊断解的极小性判定过程是将新求得的诊断解与已有诊断集合中的诊断解依次比较,检查是否有新得诊断解的超集或子集来判定极小性,这种方法随着求解过程中得到的诊断解数量增多,检测难度逐渐提高,耗时也随之增大.为解决此问题,提出了一种基于子集一致性检测的诊断解极小性判定的新方法：子集一致性(subset consistency detection, SCD)方法.通过对诊断解少数几个子集的一致性检测来给出该诊断解的极小性判定,避免了求解过程中诊断解集合增大对效率的影响.SCD方法可应用于许多高效的诊断方法,如GD(grouped diagnosis)和ACDIAG(abstract circuit diagnosis)方法,算法效率均有所提高.     

一种基于冲突的增量诊断方法

增量诊断是一种在离散事件系统中进行诊断的重要方法,因其能够根据新观测和原有诊断的结果进行进一步诊断,在长时间复杂行为的系统上有着良好的运行效率和诊断特性.文章提出了一种带有回溯的增量诊断方法.在离线定义的自动机链模型上根据在线观测进行局部诊断,用轨迹概率选出最可能诊断的同时,保存可行的候选诊断作为回溯点.若增量过程产生冲突,则回溯并根据新观测动态重新对候选诊断选择排序.既避免了不完全可诊断性条件下,增量诊断所面临的多候选选择,亦避免了由于仅保留最优结果导致的重复诊断.