（计算机软件与理论专业论文）基于模型诊断算法及应用.pdf

- 1 1 -摘要 代数直接由最小冲突集计算最小碰集的算法 该算法将冲突集用负布 尔表达式表示， 取一集合用正布尔表达式表示， 若冲突集的布尔表达 式与该集合的布尔表达式之积为 0 ， 则该集合是冲突集合簇的碰集. 同时， 本文中给出了求解全部碰集的函数， 并证明了该函数的正确性， 同时，也用程序实现了该函数 该函数的数据结构更为简单， 不需要 建立树， 只需要用字符串来表示布尔表达式的运算， 时间效率和空间 效率上该算法比以前的一些研究结果都要好， 同时可克服丢失正确解 的问 题， 具有通用性， 碰集的最小性可以由 布尔代数的吸收律获得. 5用遗传算法( g e n e t i c a l g o r i t h m ， 简记g a ) 来计 算最小 碰集. g a 算法是近年来的研究和应用非常活跃的算法， 并已 有大量的成熟算子 和实例， 但是一直没有与基于模型诊断相结合， 本文用 g a来计算最 小碰集， 用该算法的遗传适应性， 做两个方向的演化:一个由非碰集 向碰集方向 “ 进化” ;另一个是由碰集向最小碰集方向 “ 退化” . 取得 了 很好的效果. 尤其是当冲突集的数量非常巨大时， g a算法的所需时 间和空间增加很慢. 且该算法的程序实现非常容易. 6给出了基于模型诊断的应用例子， 且实现了二次探测诊断， 为 真正系统的实现做了尝试. 本文的结果虽然有待于进一步丰富和完善， 但我们相信它们能够 为求解基于模型诊断问题提供一些可供选择的方法和思路， 并且对人 工智能的理论和实践具有积极的促进作用 曰 关键词 遗传算法 4 4 型 诊 断冲突集， 碰集， b h s 一 树，布尔代数 中山大学博士学位论文 i i i - t h e a l g o r i t h m s a n d a p p l i c a t i o n s o f m o d e l - b a s e d d i a g n o s i s c o m p u t e r s o ft w a r e a n d t h e o r y na me : l i n l i s u p e r v i s o r : j i a n g y u n f e i h ab s t r act t h e c o n s t r u c t i o n o f d i a g n o s t i c s y s t e m s w i t h t r a d i t i o n a l e x p e rt s y s t e m a p p r o a c h e s h a v e m a n y s h o rt c o m i n g s , s u c h a s k n o w l e d g e i n c o m p l e t e n e s s , s y s t e m d e p e n d e n t a n d t h e d i f f i c u l t i e s o f t h e a c q u i s i t i o n o f t h e n e c e s s a r y d i a g n o s t i c k n o w l e d g e f r o m e x p e rt s , e t c , a l l o f t h e s e p r e v e n t t h e a p p l i c a t i o n o f m o d e l - b a s e d d i a g n o s i s . mo d e l - b a s e d d i a g n o s i s i s a n e w a r t i f i c i a l i n t e l l i g e n c e t e c h n i q u e , w h i c h c a n o v e r c o m e t h e s h o rt c o m i n g s o f t r a d i t i o n a l d i a g n o s t i c m e t h o d s . m o d e l - b a s e d d i a g n o s t i c m e t h o d s e m p l o y t h e m o d e l o f t h e i n t e r n a l s t r u c t u r e a n d b e h a v i o r o f t h e d e v i c e t o b e d i a g n o s e d . t h e m o d e l - b a s e d a p p r o a c h i s m o r e l i k e l y t o p r o v i d e m e t h o d i c a l c o v e r a g e . s o m e a rt i f i c i a l i n t e l l i g e n c e e x p e rt s n o t o n l y t h i n k h i g h l y o f m o d e l - b a s e d d i a g n o s i s a s a r e v o l u t i o n o f d i a gno s t i c t h e o r y a n d t e c h n i q u e , b u t a l s o c a l l i t a s a n i m p o rt a n t c h a l l e n g e a n d t o u c h s t o n e f o r a rt i f i c i a l i n t e l l i g e n c e . t h e m o d e l - b a s e d d i a gno s i s i s c o m p o s e d o f t h r e e s t e p s : c o n fl i c t r e c o g n i t i o n , c a n d i d a t e g e n e r a t i o n a n d d i a g n o s i s t e s t . i n t h i s d i s s e rt a t i o n , w e h a v e g o t s o me a d v a n t a g e s i n t h e f i r s t t w o s t e p s . t h e ma i n r e s u l t s a r e : f i r s t l y , s i m p l i f y t h e m o d e l i n mo d e l - b a s e d d i a gno s i s b y e q u i v a l e n t c o m p o n e n t s t r e e s t r u c t u r e . e q u i v a l e n t c o m p o n e n t s a r e b e l o n g e d t o t h e s a m e c o n fl i c t s e t s o r n o t a t me a n t i m e , s o w e c a n r e d u c e c o m p u t a t i o n b y t h e m. i v-a b s t r a c t s e c o n d l y , w e u s e e n v t o d e s c r i p t t h e s y s t e m . t h e c o m p u t a t i o n o f c o n fl i c t s e t s a n d h i t t i n g s e t s c a n b e r e p l a c e d b y p r o c e s s i n g e n v . s o t h e d a t a s t r u c t u r e i s v e r y s i m p l e a n d e f f i c i e n t . t h i r d l y , w e u s e t h e b h s - t r e e t o c o m p u t e m i n i m a l h i t t i n g s e t s . t h e a d v a n t a g e s o f t h i s m e t h o d a r e : ( 1 ) t h e n o d e s a r e l e s s t h a n t h o s e o f h s - t r e e ; ( 2 ) n e e d n o t b e p r u n e d s o t h a t t h e h i t t i n g s e t s a r e n o t l o s t ; ( 3 ) w h e n t h e n e w m e a s u r e m e n t c o n fl i c t s e t s a r e a d d e d , w e c a n c o m p u t e t h e n e w h i t t i n g s e t s f r o m t h e o l d h i t t i n g s e t s , s o t h a t t h e e f f i c i e n c y i s b e t t e r t h a n t h a t o f hs - t r e e . f o u r t h l y , w e r e p r e s e n t t h e c o m p o n e n t s b y b o o l e a n a l g e b r a v a r i a b l e s ; s o , w e p r o c e s s t h e b o o l e a n a l g e b r a f o r m u l a i n s t e a d o f c o n s t r u c t i n g h i t t i n g s e t s t r e e . t h e f o r m u l a s a r e t h e s a m e a s s t r i n g s , s o b o t h t h e d a t a s t r u c t u r e a n d e f f i c i e n c y a r e b e t t e r . f i ft h l y . we p r e s e n t g e n e t i c a l g o r i t h m t o c o m p u t e h i t t i n g s e t s ; t h i s m e t h o d c a n g e t t h e r e s u l t w h e n t h e s c a l e o f c o n fl i c t s e t s i s v e r y l a r g e . t h i s a l g o r i t h m c a n g e t m o r e t h a n 9 5%h i t t i n g s e t s i n a s h o r t t i me . f i n a l l y , w e e x p l o r e a n e x a m p l e t o p r a c t i c e t h e c o n fl i c t r e c o g n i t i o n , c a n d i d a t e g e n e r a t i o n a n d m e a s u r e m e n t . t h e m e t h o d s o f c o m p u t i n g h i t t i n g s e t s a r e : h s - t r e e , b h s - t r e e a n d g a . a l t h o u g h t h e r e s u l t s i n t h i s d i s s e r t a t i o n d e s e r v e f u r t h e r p e r f e c t i o n , w e b e l i e v e t h a t t h e y c a n b e p r o v i d e u s w i t h s o m e o p t i m a l l o g i c a l a p p r o a c h e s f o r s o l v i n g m o d e l - b a s e d d i a g n o s t i c p r o b l e m a n d t h a t t h e y a r e b e n e f i c i a l t o t h e t h e o r y a n d p r a c t i c e o f a r t i f i c i a l i n t e l l i g e n c e . k e y wo r d s : mo d e l - b a s e d d i a g n o s i s , c o n fl i c t s e t , h i t t i n g s e t , b h s - t r e e , b o o l e a n a l g e b r a , g e n e t i c a l g o r i t h m 提要 本文对基于模型的诊断的全部诊断过程:模型表示、冲突识别、候 选产生等，均给出了改进的算法。首先，对于模型的表示，根据部件之 间的拓扑结构分成等价的部件树，这样可以 减少部件的数量，从而达到 提高计算效率的目的。其次，冲突识别采用 e n v模型，可以提高识别 的效率。 再次， 对于候选的产生， 本文提出了 三个改进的算法: 用b h s - 树、布尔代数公式化简、g a算法等，使得计算效率有很大的提高，使 基于模型诊断的实际应用成为可能。最后，本文也对基于模型的诊断在 实际系统中的应用给出了二个演示程序:计算碰集算法效率的比较，基 于模型诊断的电路系统( 从冲突识别到候选产生全过程和探测) 。 该模型 虽然仍有许多不足之处，但是对于基于模型的诊断的理论在实际上的应 用会起到一定的推进作用。 关键词: 基 乎模型诊断;等价部件; e n v模型; b h s 一 树; 遗传算 法: 中山大学博士学位论文 第一章 绪论 1 . 1 引言 诊断学 ( d i a g n o s t i c s ) 一词源于希腊文， 意指鉴别、 确定. 最早的诊断学 来自 于医疗诊断， 但是现在它的意义早已超出医学领域， 诊断推理技术在 医学、工程、社会和经济等领域都有着广泛的应用. 最初， 机械设备较为简单， 维修人员可以凭感觉器官、简单的仪表和 工具就可以 进行诊断和维修， 但是， 随着现代化工业及科学技术的迅速发 展， 生产设备日 益大型化、自 动化、高速化、智能化， 传统的诊断技术已 不能适应需要， 并且， 现代化的工业生产， 一发生故障， 所造成的损失也 非常巨大. 例如: 1 9 8 4年， 印度博帕尔市毒气泄露事件， 造成二千多人死 亡， 二十多万人受害. 1 9 8 6 年， 美国“ 挑战者”号航天飞机空中爆炸事件， 导致7 名宇航员全部遇难， 损失达十二亿美元. 1 9 8 6 年， 前苏联切尔诺贝 利核电站泄露， 二千多人死亡， 损失达三十亿美元. 诊断已成为人类发展 迫切需要的技术。随着计算机的发展， 智能诊断逐步成为人工智能中一个 研究十分活跃的分支. 从七十年代中期，已 有一些诊断系统问世， 如: 关 于电 路故障查找系统: i n t e r h 6 1 , s o p h i 2 o 1 , h t i2 p , d a r t 2 2 ; 医学诊断 系 统: c a s n e t i4 1 , a b e l 1 6 1 , l o c a l i z e . 在八 十 年 代中 期 诊 断 系 统 的研究开始引起人们的重视， 于近期走向 成熟， 其应用也越来越广泛. 故障诊断的主要方法见图1 . 1 j b i l 第一章 绪论 一 基 于数 学一以 基于输入输出和信号处理的方法 基于状态估计的方法 基于过程参数估计的方法 基于浅知识的方法 基于深知识的方法 基于深浅知识的混合方法 户十、lest 法 方 统 系 家 专 基于人工智能诊断方1基于案例的方法 基于人工神经网 络的方法 基于模糊数学的方法 基于故障树的方法 图1 . 1故障诊断方法分类示意图 本文的研究领域主要在 “ 基于深知识的方法”. 本章安排如下: 第二节是关于基于模型诊断介绍;第三节是关于基于 模型诊断研究的各种方法及其发展; 第四节是基于模型的诊断过程; 第五 节是基于模型诊断的研究现状:第六节是基于模型诊断的主要研究课题; 第七节是基于模型诊断目前存在的问题;第八节对基于模型诊断的展望; 第九节介绍了本文的工作. 1 .2 关于基于模型诊断的介绍 基于 模型诊断( m o d e l - b a s e d d i a g n o s i s ) 是人z智能 领域近年来发展起 来的一个十分活动的研究分支. 基于模型诊断研究的动机源于希望克服第 一代诊断专家系统的缺陷. 从七十年代中期到八十年代中期为此项研究的 开创性时期， 随后逐渐发展起来成为新型诊断推理技术 这一新的诊断技 术使用待诊断系统( 设备) 内 部结构和行为模型， 这些模型可用标准a i 技术 构造， 如谓词逻辑、框架、约束和规则等. 实现模型化技术的诊断算法也 是基于标准a i 技术的， 如定理证明， 启发式搜索， 定性仿真和贝叶斯网络 等. 基于模型诊断的主要思想是: 根据系统组成元件与元件之间的连接建 立起待诊断系统模型( 如结构， 功能， 行为) ， 这种模型通常用一阶逻辑语 句来描述， 根据系统的逻辑模型以及系统的输入， 我们能通过逻辑的推理 中山大学博士 学位论文 理论推导出系统在正常情况下预期行为， 如果观测到的系统实际行为与系 统预斯行为有差异， 就说明系统存在故障， 利用逻辑的推理理论， 我们能 够确定引发故障的元件集合， 这就是基于模型的诊断 】诊断 图1 . 2把诊断看作观测值与预测值间的相互对比 基于模型诊断推理的基本范式可最恰当地理解为观测值和预测值间 的 相互比 较( 见图 1 .2 ) ， 一方面我 们有实际 设备( 系统 ) ， 并能观测某些物理 设备的实际行为. 另一方面， 我们有此设备预测其行为的模型 观测值表 示设备实际上做了 什么， 预测值表示设备应该做什么， 我们感兴趣的是两 者之间 存在的 任何差异( 不一致 ) . 基于模型诊断背后的 基本假设是: 如果 模型正确， 那么观测值和预测值间的差异源于( 可回溯到) 设备中的缺陷 这 一思想. 基于模型诊断与传统诊断方法有着本质的区别， 基于模型诊断是使用 系统的结构与行为知识作为背景理论的， 是一种全新的诊断， 被一些人工 智能专家誉为诊断理论和技术上的革命9 . 传统诊断都是基于经验的诊断 ( 也称为基于 “ 浅知识”的诊断) ， 这种诊断主要依靠领域专家对诊断对象 的经验. 对领域有极强依赖性. 对一个对象适用的诊断不能用在另外一个 诊断对象上. 采用这种方法的计算机诊断系统主要有两类: 一类是基于规 则的诊断系统( r u l e - b a s e d d i a g n o s i s s y s t e m ) ， 另一类是使用判别树 ( d e c i s i o n t r e e ) 的诊断系统. 研究这种诊断系统的关键是知识获取， 而问 第一章 绪论 题就是由此产生: 一方面领域专家需要长时间积累才能获得诊断对象知 识( 事实上这些知识总是不完备的) ， 另一方面， 从领域专家那里获得知识 并转化成计算机系统可用的产生式规则也是一大问 题， 因此开发计算机自 动诊断系统所需研制周期较长， 跟不上设备更新换代的步伐( 往往知识积 累还不充分时， 产品已 更新， 一些旧知识对新产品己 没有价值) ， 满足不了 应用的需要， 对于不断采用新技术新设计的电子电路产品更是如此 此外， 基于经验的诊断不能对诊断给出令人信服的解释. 与之相比， 基于模型诊 断的优点是: 它可以从产品设计或制造时， 利用知识开始构造， 避免从领 域专家获取知识的困难; 只要模型抽象的正确， 就能诊断所有可能的故障， 不但能处理新故障 ( 传统诊断往往无能为力) ， 而且还能给出 令人信服的 解 释. 并且由于它把系统的推理内核与系统模型分开， 只要更新系统模型就 可用于诊断另外一种设备， 因而具有设备独立性， 可推广性好. 从长远来 看， 基于模型技术最有可能打破专家系统构造方法的知识获取瓶颈. 8 0 年 代中期这个领域热了起来， 因其具有上述诸多优点及很高应用价值， 到了 9 0 年代在国际上已成为一个十分活跃的人工智能研究分支. 1 . 3 基于模型诊断的表示 “ 模型” ( m o d e l ) 这一广泛使用的术语是d e k l e e r 在文献 1 6 1 的 研究工 作中首先提出来的， 随后被大家所接受并沿用至今. 模型的含义有些不确 定， 像文献 1 所提出的 那样， 它不仅指设备中 元器件的 结构和正确行为描 述， 而且也包含医学中不带结构的行为描述和传统电路诊断的故障模型， 实际遇到的各种元件异常行为描述. 因此用上述任何描述构造的系统都可 以 称作基于模型的. 从诊断推理的知识表示角度看， 基于模型诊断可以分 为两大类: 一类是基于一致性( c o n s i s t e n c y - b a s e d ) 的方法， 另一类是溯因 ( a b d u c t i o n ) 方法 1 . 3 . 1 基于一致性方法 中山大学博士学位论文 异， 确定哪些元件可能失效会导致这个差异. 候选诊断测试的基本任务是: 对候选诊断生成的候选诊断进行测试， 确定哪个能够解释对设备所做的所 有观测. 一般地， 每次测试可能会有多个候选诊断通过检验. 候选诊断鉴 别的基本任务是: 当有多个候选通过检验时， 应该搜集什么样的新信息， 才能鉴别它们， 以得到真正的诊断. 如再做些什么额外的观测或改变系统 输入看看有什么样的结果. 1 . 4 . 1 候选诊断的生成 这一步骤的基本任务是， 给定一差异， 确定哪些元件以可能产生该差 异的方式发生了异常. 经典的人工智能智者告诉我们一个好的( 候选) 生成 器应该是完备的 ( 即， 能够产生所有合理的 候选诊断 ) ;非冗余的 ( 即， 对每 个候选诊断只生成一次 ) ; 并且是有头脑的 ( i n f o r m e d ) ( 即几乎不生成实际证 明是不正确的候选诊断) . 例1 . 6以图1 .3 中运算电路为例， 这里通过一系列观察产生候选诊断. 观察 卜对于一可疑元件， 它一定与某一差异有关联 即为了合理解释一个差异， 这个可疑元件一定以 某种( 行为) 方式参与 进来对它施加了影响. 如果不考虑信息流的方向， 候选生成器会利用设备结构的描述， 从一 差异( 图1 . 3 中f 处的差异) 找出与它相连的所有元件. 观察2 : 设备常常有可辨别的输入和输出 若我们只考虑差异上游的那些元件， 对于此例( 见图 1 . 3 ) 可疑元件将 减少到m1 , m 2 , a 1 . 观察 3 : 并不是设备的每一个输入都影响输出;不必考虑不相关的 上游输入. = 0 j c = c 第一章 绪论 图 1 . 8 例1 . 7 或门 ( 如图1 . 8 ) ， 假设它的两个输入分别由两个独立的元件集产 生己知输入为1 和。 ， 那么c处的预期值显然为1 . 如果实际观测值为0 , 那么只可能 有三种情形 ( 1 ) 或门 本身失灵; ( 2 ) 或门正常， 但输入a是。 而 不是 1 ， 那么问题一定出在此分支上游， 因此， 我们只需沿着这个方向去 查找. ( 3 ) 或门正常， 问题出 现在 b的上游分支， 但这种情况不可能. 因为 不论 b所在分支上游是否正常， 不可能出现上述观测值. 因此， 我们不必 追究这一上游分支 一般地， 候选生成器可以使用部件行为的知识来判定 哪些输入是不相关的， 因而不必回溯那些上游分支. 观察4 : 可利用从多个差异来的信息来进一步约束可疑元件的产生. 当有多个差异出现时， 可对每一个差异产生一个可疑元件集. 如果是 单故障诊断， 那么可以将这些集合取交， 就可以把可疑元件减少到一个. 如果是多故障诊断， 可利用求最小碰集的办法减少可疑元件数目 . 1 . 4 . 2 候选诊断的 测试 利用上一节各种诊断方法获得的候选诊断会有多个， 下面分别简单介 绍三种典型的测试方法. 它们使用关于设备行为的知识来产生并测试候 选. 1 .4 .2 . 1 约束暂停( c o n s t a i n t s u s p e n s i o n ) d a v i s 2 3 1 提出的约束暂停方法的基本思想是: 首先将每一元件的行为 模型化为一个约束集; 然后测试一可疑元件看它是否与设备的所有观测相 一致， 即已知输入和观测到的输出， 如果相信只有该可疑部件失效， 而其 它部件均正常， 看看这时是否与观测一致. 正常是指部件的行为是模型预期的行为， 这被模拟成让相应的约束保 留 ( t u rn e d o n ) . 相反， 说某一部件可疑是指我们不知道它的 行为是什么， 不知它将要做什么， 此时最稳妥的态度是取消关于它行为的假设， 这被模 拟成将它的约束暂停， 即暂时将它从网络中移掉 中山大学博士学位论文 图 1 . 9 例1 . 8 如图1 . 9 ， 两个输出端的值都已 测出. 在0 1 处， 观测值与预测 值之间产生了差异; 在0 2 处， 观测值与预测值相等. 每一元件的行为都用 一约束集表示. 当测试可疑元件m1 时， 将m1 约束暂停， 如图1 . 1 0 . 假设测试可通过只暂停可疑元件的约束， 保留其它元件的约束， 然后 加入观测值并让化简后的网络运行至静止状态， 那么有两种可能情形出现: ( a ) 网络没有遇到不一致的情况. 这时可得到如下两个重要信息: ( a l ) 当前 可疑元件与观测值是一致的， 即， 该可疑元件的某一行为可解释所有观测 值， 它通过了 测试. ( a 2 ) 约束常常将值传播到可疑元件的终端， 提供它是如 何失效的信息 ( b ) 即使将可 疑元件约束暂停， 网 络仍然不一 致. 那么， 排 除了该可疑元件. 即， 对于该可疑元件不存在任何一种对其终端值的指定 能与观测值和当前约束相一致. 第一章 绪论 图 1 . 1 0 继续例1 . 8 . 如图1 . 1 0 的约束网， 最终判断出m1 通过了测试， 并且通 过约束传播知道了它的终端值是3 , 2 和4 ， 即将3 和2 相乘得到了4 . 若测 试m 2 暂停其约束， 那么无论怎样指定其终端值都与输入值和观测到的输 出值不一致. 因此排除了该元件. 约束暂停技术具有如下性质: ( 1 ) 如上所述， 它不仅指出一可疑元件是否是一个一致的候选( 候选是 指这样的组成元件， 它失效能与所有的观测值相一致， 也就是能通过假设 测试的可疑元件. 当处理多故障时， 一个候选可包含多于一个组成元件) ， 还能指出在候选终端的征兆. ( 2 ) 假设测试的能力和它推出征兆的能力取决了传播机制的能力 ( 3 ) 约束暂停技术不要求描述该元件是如何失效的. ( 4 ) 上面处理的是单故障假设， 使用约束暂停技术对多故障假设亦适 用 比如， 若想测试一故障对， 那么可暂停相应的两个约束， 其它同上 1 . 4 . 2 .2 设计自 动推理工具d a r t d a r t ( d e s i g n a u t o m a t e d r e a s o n in g t o o l ) j2 2 系 统 将谓 词 演 算 作为 基于 模型推理的机制， 将设备的结构和行为表示为公理. d a r t程序的诊断测 试过程是这样的: 第一步， 从设备的模型( d a r t中称为设计描述) 和观测到的征兆出发 中山大学博士学位论文 演绎出具有如下形式的命题: ( o r ( n o t p , ) ( n o t p ) ) 其中p ; ( i =1 , . . . , n ) 为设计描述中的某一命题， 称为可疑问题. 比如从 0 1 ( 图1 .7 ) 处的 征兆出 发可演绎出: ( o r ( n o t ( mu l t i p l i e r ( ml ) ) ) ( n o t ( mu l t i p l i e r ( m2 ) ) ) ( n o t ( a d d e r ( a l ) ) ) ) 第二步， 检查是否只有一个可疑命题 若是， 则诊断结束， 否则 d a r t试图产生测试来鉴别这些可疑命题. 若找到这样的测试， 则执行它 并得出结论， 重复第二步. 若找不到这样的测试， 则返回当前可疑命题集， 诊断结束. 1 .4 . 2 . 3 通用诊断机g d e ( g e n e r a l d i a g n o s t i c e n g i n e ) g d e i 系统既能产生单故障候选诊断， 也能够产生多故障候选诊断， 并提供了测量选择的一个详细的构造策略. g d e的第一个步骤是构造冲突， 每当在电路的同一参量出现两个不 同的预测时， 则取这两个预言所依赖的环境( 取并) 作为冲突集合. g d e的第二个步骤是生成能处理所有冲突集合的候选集合 g d e的候选诊断测试， 利用候选诊断故障概率最小嫡作指导. 1 . 4 . 3 候选诊断鉴别 由于一般来说会有多个假设通过了测试， 那么如何鉴别这些假设以找 出真正的诊断就是假设鉴别的任务 鉴别假设需收集关于设备行为的新信 息. 这可通过: 探测( p r o b i n g ) ， 即增加新的观测. 测试( t e s t i n g ) ， 即 改变输入或替换元件， 并在新情形下再做观测. 不论哪一种情况，目的都是以最小代价获得最多信息. 一般情况下， 探测是最简单的鉴别方法， 它是在不改变设备状态和外 部环境条件下， 对未知真值的观测点进行的简单观测. 而测试一般是在无 - 2 2 - 第一章 绪论 法进行探测的情况下才采用的一种方法， 是改变系统外部环境( 如输入) 或 设备状态( 替换嫌疑元件后) ， 重新对系统进行的观测. 探测点的选取一般也要考虑代价及效率， 即以最少的探测点的数量， 得到最多的信息， 同时也要兼顾系统的连接结构. 如图 1 .4所示的四个反 相器的电路中， 探测加到c点可能就会优于b . d点 因为在c点可以一 次排除两个部件. 而如果我们知道反相器几乎总是失效于输出 s t u c k - a t - 1 , 那么、 我们可以确定是第二或第四个反相器中的哪个发生了故障. 1 . 5 基于模型诊断的研究现状 经过二十多年的发展， 基于模型诊断在理论上己 逐步走向成熟， 现在 己成为一个十分活跃的人工智能研究分支， 至今已出版了两本关于基于模 型 诊 断 理 论 的 论 文 集 ， 一 本 是1 9 9 2 年由 h a m s c h e r . c o n s o l e 和d e k l e e r 主 编的 r e a d in g s i n m o d e l - b a s e d d i a g n o s i s ) 9 1， 另一 本是1 9 9 4 年由c o n s o l e 和f r i e d r i c h主 编的 m o d e l - b a s e d d i a g n o s i s ) 1 1 4 期刊专辑， 另外i j c a i , a a a i 和e c a i 等重要会议文集上， 也经常有关于基于模型诊断的文章出 现 另外， 欧美一些西文发达国家从九十年代初开始每年举行一次诊断原 理会议( d x ) . 这些论文反映了目 前各种各样的基于模型诊断理论和方法 对诊断知识的表示与描述. 如欧阳丹彤4 0 1 对基于模型中心诊断的 刻划， c o n s o l e 等人 5 3 -5 4 1对动态诊断 系统的 刻 划. p r e i s t 等人5 5 讨论了 在待诊断系 统 模型中 使 用失 败即 否定 ( n e g a t i o n a s f a i l u r e ) 的 重 要性 d a m a s i o 和n e j d l 等人4 4 -4 5 1 对诊断策略和优先序的表示， 强调了策略在诊断中的重要性. g e f f n e r 和p e a r l 将系 统行为的因 果 知识用 信念网 表示 ， 并用b a y e s 推理 来实 现诊断 . f r i e d r ic h 4 3 1对r e i t e r 2 1理论的 抽象 刻划 ， 为层次 诊断 提供了 理 论依据. 正是由于这些理论和方法的不断出现促进了基于模型诊断理论的 蓬勃发展， 并使其在实践中逐步走向成熟. 在应用上， 一些开发的基于模型诊断系统已应用到实际中， 满足了应 中山大学博士学位论文 用的需要. 如在工程领域， m o s t e r m e n 和b i s w a s 5 7 成功地把l a c k i n g e r 和 n e j d t 13 6 1提出的 动态系 统的监视与 诊断 相结合的方 法应用到增殖反 应堆辅 助冷却循环系统的故障诊断上， 在医学领域， 帮助医生诊断与修复外伤治 疗的t r a u a i d 3 7 j 系统， 在经济领域， h a m s c h e r 3 8 成功 地把基于 模型诊断 理 论应用于财会审计上， 开发出了决策系统c r o s b y等. 1 . 6 基于模型诊断的主要研究课题 模型化方面问题的研究 处理基于模型诊断复杂性方面的研究 基于逻辑的诊断的理论方面的研究 基于模型诊断方法在其它领域的应用 重构与修复方面问题的研究 动态设备在线监控与诊断方面问题的研究 模拟设备的诊断方面问题的研究 1 . 7 基于模型诊断目前存在的问题 基 于 模型 诊断目 前待 解 决的问 题 ( o p e n i s s u e s ) 12 , 6 s 1 : 应 用的 广 度; 在 处 理复杂行为上有一定困难;模型的构建;模型的选择;模拟设备的推理. 1 . 7 . 1 应用的 广度 前面已 介绍过， 基于模型的诊断具有设备独立性. 我们所做的任何一 件事都是通用的， 而不是针对某一特定的设备， 也就是说只要给出不同电 路的新描述， 可马上使用同样的推理过程工作 然而， 我们对于这些技术 究竟有多大程度的领域独立性却不是很清楚. 因为目 前的诊断系统主要是 针对简单电子电 路， 在其它领域， 如机械设备， 水利设备等所做工作较少. 1 . 7 . 2 复杂行为 这一问题是指现有技术是否可用于复杂的设备， 如何表示更复杂设备 - 2 4 - 第一章 绪论 的 行为 并 进行推理. 不仅大型设 备具 有复杂性 ， 小 型设备也如此. d a u g e s s 1 等人指出一个晶体管的行为就很复杂 复杂性尤其体现在具有动态行为的 设备中 3 8 ,4 0 ,4 2 ,4 3 1 ， 在模型化， 预测机制， 推理机制上都比简单诊断的静止 设备复杂得多. 对动态设备、模拟设备的诊断方面的研究虽然有了一定的 成果， 但动态设备的诊断仍是基于模型诊断的一个有待解决的问题. 那么， 对于这些具有不同复杂性的设备如何处理呢?一种可能的方法 是寻找一个新的词汇表， 设计一个新的抽象集来处理所遇到的复杂性的类 型( 不同复杂性用不同抽象层来处理) ， 但是寻找 “ 合适”的抽象集很困难. 怎么理解 “ 合适” 这个词呢?这些抽象忽略了 什么， 强调了什么?如何知 道这些是有效的选择呢?对复杂设备进行推理的一个可能有效办法是使 用故障的 行为的“ 第二原理” ( s e c o n d p ri n c ip l e ) 这一启 发式概 念 第二原 理 源于设计知识， 即可以从设计观点来解释:一个例子是使用启发式信息， 如在一复杂设备中故障征兆是很明显的. 这可从设计角度解释， 理由是复 杂的设计经常包含重复使用的模块， 这意味着一个模块的错误会带来组合 错误的后果. 我们注意到第二原理不是针对某一设备的启发式， 因此可能 广泛应用. 现在的问题是如何找到更多的第二原理知识， 这显然应该从有 经验的故障检修员那里得到. 每当一个基于模型诊断系统产生一个诊断虽 然逻辑上合理， 但人类故障检修员认为它不合适时， 就要从有经验的故障 检修员那里了解到系统模型中缺少的知识. 有些知识就可能暗示出一些有 用的第二原理. 1 . 7 . 3 模型构造 模型的构造也是阻碍基于模型诊断应用的难题之一， 有几个因素使得 这一任务对许多真实设备悬而未决. 这是因为， 如果模型是正确的， 那么 观测和预言行之间的差异都源于模型， 通过诊断一定能够找到故障部件， 但问题是: 从理论上看， 模型永远是不完备的。 模型之所以称之为模型， 就是因为它不是设备本身， 只是设备的近似， 总有未捕捉到的东西. 每一 模型背后都有一些简化假设， 如果模型选择不好， 就可能没有体现设备的 中山大学博士学位论文 因果关系， 导致诊断失败. 由于模型必然是不完备的， 这一点使得我们必须在复杂性和完备性之 间进行权衡， 要想完备， 诊断推理必须沿着每一个可能的相互作用路径， 考虑所有可能出错的元件. 但这同时意味着增加问题复杂性. 为此， 我们 必须做出某些合理的简化假设， 比如假定导线正常， 但这样就要冒失去完 备性的风险. 因为有可能故障就出在导线上. 这样， 诊断系统永远不会诊 断出该类故障元件. 因此， 有待解决的问 题是找到能帮助我们选择、 组织、 简化假设的技术. 所以， 模型的选择就要在完备性与复杂性之间进行权衡， 如果模型过 于复杂， 则诊断的效率势必很低， 诊断过程势必非常繁杂. 而相反， 若模 型过于简单， 则可能导致不能找到问题的真正所在. 模型选择的主要问题是: 1 、它要求穷举， 显式地重构整个设备的设计， 常常所需信息不易获 得. 2 、有大量的信息要表示， 并且 3 、所需信息常常是用不规范语言描述的. 另外， 模型的表示也会影响到诊断效率， 同样多内容的模型， 若采用 不同的表示方法， 可能产生的诊断效率会相差很大， 所以 这也正是我们要 解决的问题之一 因此， 甚至像个人计算机一样简单的设备， 构造模型的任务也是对智 能 考古学( 重新考察设计细节) 和转换( 从不规范到 更准确描述 ) 任务的 一 个 挑战. 我们需要使这一过程既容易又直观， 在纯语义层次上， 能够阅读和 转换已 有c a d文件， 减少所需手工作业量. 更重要的是， 我们需要更好的 理解最终产品( 模型) 和把不规范描述转换成所需模型的过程. 第一章 绪论 基于模型诊断的展望 多一ou 月. 由于模型诊断存在上述问 题有待解决， 这一方面对人工智能是一个挑 战， 另一方面对人工智能研究起到积极推动作用 随着神经网络技术的发 展， 人们已开发出基于神经网络技术的诊断系统， 试图利用神经网络技术 的优点解决这些问题 7 2 -7 4 1 . 但纯神经网络诊断系统同样存在一定的缺陷 ( 如没有理论指导且不能解释诊断， 训练样本困难， 忽视专家经验等) . 同 时， 随着模糊推理技术的不断发展， 人们也正在尝试基于模糊推理的诊断 系统7 1 a 5 1， 试图 用模糊推理技术解决诊断系统中 征兆的随机性和间断 性， 以及因果蕴涵的不确定给基于模型诊断带来的困难. 基于上述情况， 我们认为基于模型诊断的一个未来发展方向应是将神 经网络理解成一类知识源的表达与处理模式， 并把它融入基于模型诊断模 型中 ， 实现逻辑抽象推理与形象思维相结合;另一个发展方向是如何把模 糊推理技术结合到基于模型诊断中， 发挥它们各自 的长处，目 前， 我们也 己 把g a算法成功地应用于最小碰集的计算， 今后将做更深一步的工作. 模型的构造一直是基于模型诊断的一个障碍， 本文在这方面做了一些 工作， 但是距通用性及广泛性仍有一定差距， 如何能够用通用简单的方法 来表示模型， 也是我们进一步要做的工作之一 1 . 9 本文的工作 本文的主要工作是: 将基于模型诊断从模型的表示， 模型的简化， 冲 突识别， 候选产生都进行了 探讨. 主要有: ( 1 ) 用布尔代数的 模型来表示系 统及诊断的计算， 这样与传统的用一阶逻辑表示、 用集合来进行计算相比 ， 效率及计算机实现上均有较大的改进. ( 2 ) 在系统部件的 描述上， 也考虑到 等价部件结构， 从而可以“ 减少” 部件数量， 简化计算. ( 3 ) 在冲突识别中， 用到e n v模型来提高效率. ( 4 ) 对碰集的计算， 也提出了b h s 一 树和布尔代 中山 大学博士学位论文 数的方法， 这样就可以自 始至终均统一采用布尔代数来实现诊断， 整个系 统的数据结构统一简便. 这些改进算法对计算的时间、空间效率都有很大 改进， 使计算机实现成为可能. 在本文的最后， 也给出了3 个实例， 其中有 一个是汽车诊断的实例， 从而说明本文中提出的方法和路线是可行的， 当 然若再增加适当的领域知识及进一步加强实际系统的模型化工作， 本文提 出的论点是完全可以应用于实际诊断领域中的. 本文是按如下方式组织的: 第二章， 利用等价部件模型， 对基于模型诊断的模型进行了简化， 把 系统中的部件按连接方式划分成若干个 “