（计算机应用技术专业论文）基于实例推理的电子工艺设计.pdf

华中科技大学硕士学位论文 摘要 f ；c b r ( c a s e b a s e d r e a s o n i n g ，基于实例的推理) 技术是人工智能的一个研究热点。 在许多领域已经有了成熟的应用。其基本思想是利用先前求解问题的经验和方法，通 过类比和联想来解决当前相似问题的求解策略，它根据现有问题的特征，从实例库中 检索出相似的实例( 先前经验的总结) ，然后以知识库中的领域知识和经验为指导， 根据问题的实际情况对检索到的实例进行修改、充实、综合，使之满足当前问题的求 解需要。 基于实例推理的电子工艺设计系统是武汉邮电科学院委托我们开发的“c i m s 三期工程”项目的一部分。传统的p c b ( p r i n t e dc i r c u i tb o a r d ，印刷电路板) 装配往 往需要过多地依赖工艺员的经验，从而导致生产过程存在许多不确定的人为因素。 c b r 推理方法在理论上尤其适合不确定因素多，经验知识比较丰富的场合。系统用基 于实例推理的方法进行了实现，试图解决p c b 生产过程中效率低下、标准不统一的 问题。 实例表示方法多样，实例一般由实例属性和实例解决方案组成，针对p c b 生产 的实际情况，采用一种由p c b 特征与p c b 工艺组成的实例表示方案。实例在实例库 中分层存储，为检索实例提供了便利和依据。 实例检索的目的是在实例库中检索出和当前实例相似的实例，高效的检索机制和 检索算法是c b r 系统是否成功的关键之一。基于实例推理的系统对传统搜索算法进 行改进，旨在提高系统的效率。 在实例库中检索出的实例还不是对当前问题的精确解。必须经过实例匹配阶段， 进一步筛选检索的结果以获得“最佳”实例，好的匹配算法和匹配函数的建立在这个 阶段至关重要。一种最临近( n e a r e s t n e i g h b o r ，简称n n ) 匹配算法的改进算法在基 于实例推理的系统中被提出，实验结果对该算法的性能进行了评价。 不同角色和用户权限的设置，控制不同身份的用户以不同的安全级别登录系统， 系统的安全性得到一定保证。、， 关键词：人工智能；实例推理；实例表示：实例检索；实例匹配 华中科技大学硕士学位论文 a b s t r a c t c a s e - b a s e dr e a s o n i n g ( c b r ) i sah o tt o p i co fa r i t i f i c i a li n t e l l i g e n c e ，w h i c hh a sb e e n a p p l i e di nm a n y 瓢 d s c b ri s as i m p l em e t h o d o l o g yp r o p o s e dt op r o b l e ms o l v i n gb y u s i n gp r e v i o u se x p e r i e n c e s t h eb a s i c i d e ai sf o c u s e do nt h eh y p o t h e s i st h a t “s i m i l a r p r o b l e m sh a v e s i m i l a rs o l u t i o n s a c c o r d i n gt ot h ea t t r i b u t eo f t h ec u r r e n t p r o b l e m ，r e t r i e v e t h es i m i l a rc a s e sf r o mt h ee a s e b a s e ( t h ep r e v i o u se x p e r i e n c e sa n dm e t h o d s ) a n d t h e nr e v i s e ， e n r i c h ，i n t e g r a t et h ec a s e su n t i lt h e y a r ec o m p a t i b l ew i t ht h ec u r r e n t p r o b l e m t h ec b rf o rp c b ( p r i n t e dc i r c u i t8 0 a r d ) p r o c e s sp l a n n i n gi sap a r to fr e s e a r c ho f t h et h i r dp r o j e c to fc i m s ”w h i c hc o m e sf r o mw r i t h ep a p e ri n t r o d u c e st h ep r i n c i p l eo f c b ra n dam e t h o do fc a s ee x p r e s s i n gb a s e dt h ea p p l i c a t i o no fp c bi sp u tf o r w a r d t h e a l g o r i t h m so fc a s er e t r i e v i n g a n dc 8 s em a t c h i n ga r ed i s c u s s e de s p e c i a l l y t h a th i g h l y r e t r i e v i n ge f f i c i e n c ya n da c c u r a t e l ym a t c h i n g a r er e q u i r e di nt h ea s s i g no f p c b t h ei d e ao f c b ri sa p p l i e di nt h i ss y s t e ms u e c e e s s f u l l y u s u a l l ya c a s ei sc o m p o s e do f p r o b l e ma t t r i b u t e sa n d t h es o l u t i o nt ot h ep r o b l e m a l a y e r e dc a s ee x p r e s s i n gm e t h o d w h i c hi sc o m p o s e do fp c ba t t r i b u t e sa n dp c b a s s e m b l y i sp u tf o r w a r di nt h es y s t e m t h ee f f e c t i v er e t r i e v i n gm e c h a n i s ma n da l g o r i t h ma r et h ek e yt oc b r s y s t e m 。m a n y m e t h o d sa l _ cd i s c u s s e da n dn u p d a t ea l g o r i t h m i sp u tf o r w a r d 。 t h ep u r p o s eo fc a s ee x p r e s s i n gi sg e tt h ef i n a l l ys o l u t i o nt h r o u g hc o m p a r i n gt h e s i m i l i t u d eb c t w c u nc u r r e n tc a s ea n dp r e v i o u sc a s e s , t h ec o u r s ei sc a l l e dc a s em a t c h i n g 。a u p d a t e da l g o r i t h mb a s e dn n ( n e a r e s tn e i g h b o r ) i sp u tf o r w a r da f t e rd i s c u s s i n gm a n y a l g o r i t h m s ，t h ep e r f o r m a n c e o f t h es y s t e mi se v a l u a t e d i na d d i t i o n ，d i f f e r e n tr o l e si sd i s t r i b u t e dt ou s e r s ，a n de v e r yr o l ec a nu s ed i f f e r e n t p o w e r s ot h a tt h e s y s t e m i sm o r es a f e k e yw o r d s ：a r i t i f i c i a li n t e l l i g e n c e ；c a s e - b a s e d r e a s o n i n g ；c a s ee x p r e s s i n g ；c a s e r e t r i e v i n g ；c a s em a t c h i n g i i 华中科技大学硕士学位论文 1 1 本文研究的背景 1 绪论 c b r ( c a s e b a s e d r e a s o n i n g ，实例推理) 作为人工智能由表层的机器模仿向深层 的机器思维中的一种形式已得到人工智能研究者越来越多的重视。人类在解决当前实 际问题时，总是希望借鉴以往同类或相似问题的解决方法。通过分析大量的先前实例 的解决方案，在其基础上作适当修改用于处理新问题。研究表明，传统的专家系统推 理模式存在系统不会学习、知识难以获取、推理不够准确和有效等问题。特别对于需 要丰富的以往经验的问题求解领域，传统推理模式存在许多局限性。因此，对c b r 的深入研究有助于探讨人类求解问题和学习新知识的机制；有助于解决专家系统中知 识难以获取和推理不够准确和有效性等问题：有助于对不完全了解的领域，根据以往 的经验作出假设和推测，从而帮助解决当前面临的问题。 基于实例的推理系统融合了多学科知识。本文讨论的主题集中在人工智能领域， 研究工作基于国家“8 6 3 ”武汉邮电科学研究院烽火通信公司c i m s 应用示范工程( 三 期) 项目。8 0 年代末9 0 年代初，我国传统产业汽车、飞机制造等产业率先实施c i m s ， 取得了巨大的成效。c i m s 除了在传统产业中发挥作用之外，它在包括电子、通信等 在内的高新技术产业中也取得成效。用c i m s 高技术手段来发展信息通讯高技术产业 是一条可行之路，武汉邮科院这样的高技术产业本身就具有较好的c i m s 实施需求和 基础。主要表现在以下几个方面： 1 高新技术产业市场变化更快，竞争更激烈，企业对高新技术支撑的需求更强 烈。 2 光通讯产品越来越复杂，人工设计已无法完成，必须而且已经普遍采用了 c a d 技术。 3 光电通信产品组装密度越来越高，加工制造必须采用自动化生产设备。 4 高技术、高附加值、高利润是企业追求的目标，必须用高新技术产品占领市 场。 5 高效、低耗、清洁生产本来就是高新技术产业的基本特征之一，也是c i m s 所要产生的实际效果。 华中科技大学硕士学位论文 因此，高新技术产业和c i m s 的结合就会在较短的时间内产生较大的成效。 武汉邮科院系统部原有设计和生产过程存在下述问题： 1 新产品的开发速度不够快。 2 设计控制管理模式跟不上产品开发要求。武汉邮科院新产品的开发，已从人 工设计完全过渡到计算机辅助设计。传统的技术档案管理模式是以管理人工设计的纸 介质为基础制定的，与当前的产品开发模式不符。 3 产品设计与工艺设计脱节。产品设计与工艺设计是新产品开发的两个主要环 节，是一个不可分割的整体，双方的集成有助于提高产品质量、降低产品成本、加快 开发速度。 4 设计与加工制造脱节。武汉邮科院现行产品开发模式和c i m s 一期工程实践 及i s o9 0 0 1 质量保证体系贯彻实施说明：系统部原有的产品开发模式不能在设计早 期充分的考虑产品生产中的各种因素。 针对上述问题武汉邮电科学院从1 9 9 6 年开始从两个方面进行了设计开发及生 产过程优化，其一是配合贯彻i s o9 0 0 1 质量保证体系，实施全面质量管理；其二是 结合工艺革新与改造，实施基于并行工程思想的设计过程控制与管理。 c i m s 第一、二期工程已经成功地建立和实现了一种基于中心数据库的p c b 装联 c a d ，c a p p c a m 集成方案，实际应用表明，此系统的应用大大提高了烽火通信公司 系统设备制造部的设计、制造和测试的自动化水平。 本文的研究工作基于从2 0 0 2 年开始的c i m s 三期工程，此阶段除继续将以前工 程成果进一步完善和适用化外，以提高系统设备制造部电子装联车间的生产效率为目 标，在实施中围绕s d h 、接入网设备、d w d m 等主要目标产品的生产过程，打破p c b 生产过程中的各自为政、封闭的设计和制造模式，将设计、工艺规划和制造联合成一 个有机的整体，实现产品设计、工艺规划和加工过程的全面计算机化和自动化，即 c a d c a p p c a m 及生产过程管理集成。电子装联车间主要从事p c b ( p r i n tc i r c u i t b o a r d ) 的生产，尽管生产过程中一些先进的e d a 工具和自动化生产设备得到应用， 但各个生产过程仍然存在“自动化孤岛”现象，彼此不能直接地进行信息的传输与交 换，需要手工的数据输入和编程，使得设备相当多的时间都处于数据准备阶段，同时 由于大量的人工干预导致错误频繁，设计和制造各环节的数据集成度不高，大多数工 2 华中科技大学硕士学位论文 艺文件也都依靠手工完成，主要依赖工艺员的个人经验，不仅效率低下，而且设计的 工艺文件很难统一，难以保证规范性，严重影响了产品的质量和市场竞争力。为改变 这种状况，系统试图用基于实例推理的方法，保留领域专家( 工艺员) 的经验和方法， 在进行新产品的设计的时候，并不需要从头开始，而是从系统实例库中搜索以前类似 问题的求解方案，对其经过适当的修改后应用到新产品的设计中。 1 2 国内外研究的现状 c b r 的发展起源于人们解决实际问题时对认知心理活动的研究。r o g e rs c h a n k 于 1 9 8 2 年在其( d y n a m i cm e m o r y ：at h e o r yo f l e a m i n g i nc o m p u t e ra n dp e o p l e 一书中 给出了在计算机上建立c b r 系统的一些最初方法。他的思想由其学生进一步推广、 发展，并得到印证【“，从而形成了人工智能中专家系统设计的一种很有前途的方法。 r o g e rs c h a n k 被大多数a i ( a r i t i f i c i a li n t e l l i g e n c e ) 学者认为是c b r 思想的最初提出 者。c b r 的核心思想是：在对当前问题求解时，人们可以借助以前相同或同类问题的 求解方法，即实例推理。 自从实例推理的概念和思想提出后。关于此方面的研究及应用日益增多，尤其上 世纪九十年代以来，有关c b r 的研究呈现跳跃性增长。1 9 8 8 年，由美国国防部高级 研究工程机构( ”p ：a ) 资助的第一个c b r 研究所确定了c b r 研究的理论基础和研 究方向，该机构从1 9 8 8 年以来，资助召开了多次国际性c b r 学术研讨会，与此同时， 美国人工智能协会( a a a i ) 在其近年来主办的国际性学术会议及研讨中，都有关于 c b r 应用及理论方面的论文，人工智能杂志( a im a g a z i n e ) 和i e e e 专家系统( i e e e e x p e r t ) 杂志也相继组织和发表了有关c b r 的专题研究和应用论文从而进一步推 动了关于c b r 的研究，c b r 理论也得到进一步完善和发展，c b r 技术也得以广泛应 用于诸多领域。第一个c b r 系统是j a n e tk o l o d n e r 在耶鲁大学开发的c y r u s 2 , 3 。早 期的c b r 应用系统还有l e b o w i t z 开发的i p p 、m e d i a t o r 和a s h l e y 开发的h y p o 、 h a m m o n d 开发的c h e f 等，这些系统涉及到外交、法律、方案规划等应用领域，主 要用于问题求解。c y r u s 是一个基于s c h a n k 的动态存储模型和问题求解的系统1 4 i ， 该系统基本上是一个问题应答系统。随着实例存储模型的发展，它逐渐应用于其他的 一些c b r 系统，比如m e d i a t o r l5 1 ，p e r s u a d e r t 6 l ，c h e f t 7 1 ，j u l i a l 8 】，c a s e y l 9 1 。 华中科技大学硕士学位论文 另外一个基予c b r 的系统是b r u c ep o r t e r 和他的研究组在德克萨斯州立大学开发的 p r o t o s 系绕讲，他雷】爨初从事枫器学习和橇念学习以遴行任务分类，这些工作直接 导致了p r o t o s 系统酌开发1 1 。遽个系统强调整合普通领域知识和特殊领域知识到 一个统一的袭示结构中，这个思想在系统g r e b e i l 2 l ( 一种在法律领域的应用积序) 孛褥刭避一步俸瑗。曩一令孚鬻霹c b r 磺究嚣滋重丈雯辍豹莛e d w i n ar i s s l a n d 稻鳃 的研究组在马萨诸塞州大学所从事的工作，他们的研究内容主要是法律审判中的事先 推攥l l 孤，这璧的实例不是惩来产生一令唯一敢阀趣解答，露是勰释法庭豹状况，梵辩 论的双方产生评估意见，这直接导致了h y p o 系统 1 以及后来基予实例和基于规则 系统相结合的系统c a b a r e t 的产嫩f 1 5 1 。 在欧溺荚予c b r 豹轿究笼美鬻貉魏，嚣纛跫强调冀酾专家系统黻及翔谈黢取的 结合。早期从枣c b r 研究工作的主要有m i c h a e lr i c h t e r 、k l a u sd i e t e ra l t h o f f 以及 k a i s e r s l a u t e m 大学豹一些学者，健l f 】斡磅究内察为m o l t k e 系统中戆复杂技术诊聚 1 1 6 1 ，其研究工作导致了系统p a t d e x 的产生1 1 7 1 。在t r o n d h e i m 大学a g n a r a a m o d t 和 魑学者研究了c b r 系统中上下文的知识表达，他们组念了实例和领域知识【捕1 。在 试翔辩学方瑟，t r i n i t y 天学静m a r kk e a n e 终了一些类琵推理工俸l 嘲。经过这戆学者 的不断努力，c b r 的理论正在逐步完普，c b r 系统在不同的领域也不断得以应用。 在亚浏关擎c b r 系统魏磅究邈在啜数黢荚经验麓基弦| l 主瑟震。不霾夔謇家秘遮 区脊不同的研究热点。在日本，并行计算在c b r 系统中的研究非常受到重视1 2 0 1 。在 中阕，关于c b r 的理论釉实践的研究比较晚，始于上世纪9 0 年代视，初期的磷究工 作童要停留在理论研究方两，醚着壤论研究的不断深入，在一些瘟阕领域也逐渐开发 出商用的c b r 系统，比如i c m i x 系统【舶i ，智能刺绣编程系统1 2 2 1 。 1 3 目前有关c b r 问题的主簧研究内容 1 c b r 基础理论的研究。主蛩惫括：如秘提供有效豹实铡表示激及索零| 方法； 如何有效豹获墩实铡和对实例库进静维护，特剐是分布式实例的获墩以及分布式实例 库的管理和维护等l 如何在由结构文本缎成的实例中自动抽取实例的特征属性；如何 撵供一令雯裔皴静算法，瓢露抉速猴确缝在实镪痒孛检索释嬉选蠢蒋会当前随憨求解 需蒙的实例：如何对以徒的解进行有效的调撼和修改使之邋宜解决新问题；如何处理 华中科技大学硕士学位论文 连续型实例的推理【2 3 】等。 2 。c b r 菇其它方法撩缝会斡磷究。c b r 圭要逶雳予鬟耍丰塞静镁域经验黪痰瘸 领域，而r b r ( r u l e b a s e dr e a s o n i n g ，基于规则的推理) 则遗应于知识比较丰富的领 域，因此，结含c b r 和r b r 及m b r ( m o d e l - b a s e d r e a s o n i n g ，基于模溅的推理) 的 滢会润戆求瓣系统，瑶戮稠用各鑫豹攘理挠势，壤强系统麓攘瑗能秀。c b r 方法与其 它优化方法相结合可以解决组合优化问题。大型复杂的组合优化问题往往属于n p 宪 全阏惩，传统的佳纯算法程解决这类| 薅题时存在诖冀量大、搜索困难等闲题，因此采 用c b r 与其它方法相结合以解决组合优化问题怒c b r 研究的一个主要方向l 矧。 3 c b r 襁管理领域巾应用的研究。 4 久类萋予联戆学习豹实铡模鍪及谈翔攘麓戆磅窕。 目前c b r 已经广泛_ 陂用于许多领域，一些热型的应用领域有： l 。诗算机摹； 学的研究。如模式识别，人工黎能帮软传量程等。 2 工程领域的应用。如生产过程豹计划设计与控制等辑引。 3 c b r 在管理领域中的应用得划充分的重视，已经取得了许多实际的应用效果 1 2 敷2 鞋。 4 控制领域大量使用c b r 技术宓现自动控制和自适威控制。如机器人行为舰划 1 2 5 l 、飞行器踌缀选择f 2 8 l 等。 5 在复杂的组合优纯问题中的斑用1 2 4 。c b r 技术在计剃、调度和非线性优化等 问题中都得到了广泛的应用它克服了传统算法的一些缺陷。 6 c b r 在诀簸辩学写；蛰理学熬各令赣域氆蠢广泛豹疲溺。翔入类求簿鞫蓬豹思 维过程及心理学模型的建舷等。 1 4 本文的主要磷窕童律 在p c b 生产过程中，凰然e d a ( e l e c t r o n i cd e s i g na u t o m a t i c ) 设计文件中已经 鬟邂了p c b 魏结擒、元器棒争争类、数羹、尺专等静态信惠，但是实际囊产线主存在 许多不确定的因素，工艺员的经验往被对p c b 生产的质量至关重要，针对这种状况， 试鬻爝基于实铡推理的方法，保留工芑员的“设计经验”，每次的设计缡暴作为一令 新实例保留在蜜铡库中，巍下次设计新p c b 时不需从头开始，而是在絮例库中寻找 5 华中科技大学硕士学位论文 相似或相同的实例，把其作适当修改应用于新问题的求解中。具体有以下几个方面的 工作： 1 阐述了c b r 的基本概念和基本原理。 2 描述了c b r 一般体系结构，并对其各个阶段的特点( 实例表示、实例检索、 实例修改、实例保留、实例重用) 分别进行了介绍。 3 对基于实例的推理机制进行了分析。并和其它相关推理机制进行比较。在实 例检索中重点介绍了相似理论。 4 构造了基于实例推理的p c b c b r 系统并给出系统设计总体设计图，对其中 各模块分别进行了设计，并对涉及的相关算法进行了讨论。 5 重点研究了实例检索和匹配算法。在研究传统算法的基础上提出了改进的检 索和匹配算法。 6 针对改进的算法在p c b c b r 系统上的应用对实验结果进行了设计。 7 针对系统存在的问题以及可能的改进方向提出了设想。 本系统的设计将在提高p c b 装联的效率，规范设计标准方面起到一定作用。 6 华中科技大学硕士学位论文 2 c b r 系统的基本原理 2 1c b r 系统的基本概念 c b r ，一般译为基于实例的推理、基于范例的推理、基于案例的推理。是机器学 习方法中归纳学习的一种，它可以较好的模拟专家的联想、直觉、类比、归纳、学习 和记忆等思维过程。在求解问题的方法中，人们将过去对典型问题的求解范例，按一 定的组织方式存储起来积累成实例库，当用户求解某一新问题时，按一定的方式输入 待求解的新问题，即待求解实例，系统根据问题的描述，利用实例检索机制从实例库 中寻找与待求解问题实例匹配或近似匹配的实例，如果找到的实例与待求解实例描述 完全一致，则将找到的实例作为对新问题的解输出，否则，根据待求解问题的特征， 对检索出的实例进行修改，以产生一个符合问题求解要求的解，并将其输出，同时将 这个问题的求解作为一个新的实例再存储到实例库中，以备将来使用j 。一般来说， 一个实例包括问题的初始状态、目标状态及求解方案。随着实例库的增长，系统的“经 验”会越来越丰富，找到新实例的解的可能性也越大。在基于实例的推理系统中，实 例就是要求解的问题状态及其求解镱略。 2 2 c b r 系统的基本结构 基于实例的推理系统的基本结构如图2 - l 所示。 图2 - 1 基于实例推理的系统的基本结构 从图2 - 1 中可以看出，基于实例推理系统主要有检索系统、实例库及实例修改方 华中科技大学硕士学位论文 法等部分构成。其中实例霹中存锉骞支持闻题求姆的艨毒实例，它是系统过去进行闻 蹶求解经验的聚集。检索系统则融合了实例的表示形式和检索机制，其设计的好坏直 接影响到实例检索的质量和速度。实例修改系统则是对检索出的实例进行修改以满足 新问题的求解需簧，经过修改的实例作为新的实例存入实例库中。 2 3c b r 系统的基本特点 从c b r 系统的基本构成和推理过程中可以羲出，c b r 系统虚具镛如下特点： 1 学习是c b r 的基本功能。这种学习就是基于实例的学习。在一个c b r 系统 中，问题求解的结果总是作为新的实例保存在实例库中作为知识积累，这种知识积累 的过程就是c b r 系统的学习过程。 2 检索系统篷c b r 静核心。检索系统一般包括索弓| 税涮稀检索税裁，索弓| 机制 主要攒遮毅转么形式把实铡存赣戮实铡痒串，检索祝制主要撰述麓侮掇据检索信怠查 找秘匹嚣羼爨要斡实例( 毅阂爨瓣求瓣方寨) 。 3 。系统维护是c b r 是秀成功的瓶颈之一。窍效蕊完善的维护桃制将使撮照实例 库不断增大，检索效率不至于大大降低。 4 推理机制是c b r 系统的蘸要组成部分。针对不同的系统采用食理的推理机制 对予系统的效率乃至成败都有很大的关系。 2 , 4 不同知识系统推理机制的比较 耳斑知识系统中的推理虮制生要蠢三种： 1 基于舰则的推攥机制 基于规则的撼理将专家的知识和经验抽藩为蓿干推理过程中的规则。规则一般用 产生式形式表达： i f 趟畸d t h e n 8 华中科技大学硕士学位论文 或操作l 或 或操作m 许多知识系统都箍采掰这种推理机制，系统根据用户对问题的摘述，在知识库中 寻找逶当熬戴刘连接起来，遥过捺理缮裂惩撩豹瓣。它豹犹点怒跑较壹鬣，对摇理过 程易于理解，嘲时推理的效率也比较裹。但是r b r ( r u l e - b a s e dr e a s o n i n g ) 戆专家 知识获取比较困难，特别感对于比较复杂的而且规则的条件多解的系统，全面收集领 域专家的知识和经验怒个困难的过程，如粜给定完全相同的问题描述，系统总会以 完全程磊豹步骤褥鬟舔样豹瓣，这意臻着基予怒潮豹系统本霞上是没有学习能力的， 两且，如果问题处于最初所赋予系缝鲍觏则懿重之鳋，则系统裁会对求解翘蘧无戆受 力。最后，建立和维护知识库的工作是困难和费时的，一方面要把专家知识变换成规 刚的表示，另一方面，由于规则之间的相互依赖性。向知识库增加知识要经过复杂的 调试。霞萎毛r b r 这种推理枫髑主要逶糯予不太复杂、领域知识和经验比较容易收集 的中小型知识系绞。 2 基于模型的推理机制( m o d e l ：b a s e dr e a s o n g i n g ：m b r ) 基于模型的推理机制m b r 是利用作为特定解决问题的系统结构威组成要素镣的 特鬣、霖爨或骧鬟| j ，建立一数学横登，丽后稃嗣用这一数学模型并结合闯灏的条件， 对系统作操攫理、判麟，以达裂熬决趣惩熬嚣懿。 恩然，并非所有系统都适合采用m b r ，肖些复杂的系统根本无法建立相应螅数 学模型，嗣此m b r 的应用受到一定的限制。 3 基予实铡豹推理( c b r ) c b r 攘理辍铡与r b r 耱m b r 难毽瓿剿鞠琵鸯翔下豹特煮： ( 1 ) 由予c b r 系统的摊理过程是以实例为基破的，它魄产生式规赠曼容易安褒 和存储，它占用更少的内存空问，同时推理和检索的速度也比r r b 系统要快。 沟建立基于规则的系统的知识库，知识工程师必须花赞大蠢时间从领域专家的知 谖孛獭取一致豹、完整鹣分类袭簧| j ，瑟在基予实镶豹系统中，知识工稷舜哭需为簿个 类别收集代表性的例子，选择适当的特缓，藤这只棚当予建立燧贱露豹一部分工 乍。 华中科技大学硕士学位论文 在维护和修泼知识席方蘧，妇果要对分类作一些修改，基于实例的系统只爨对实 例阵中的各个实例进行修改，丽对基予规则的系统。规则的修改可能牵涉别对其宅规 则瓣修羧，甚至霹戆对熬令嫂瓣痒遴纷重章奄。 对解释功能丽言，基于规则的系统仅仅提供规则链，而无法提供最初的实例。基 予实铡的系统不仅能通过裣索过程对结果作出解释，还可以显示支持这个检索的实 例，即使在无法分类的馕况下，也霹以自爆声显示个实铡，以掇助鼹户遴行判叛。 基于实例的系统还可以存储一热计算机无法盥接利用的分类信息，比如图歙、声街以 及稻由形式酌文本等。 对于综合任务的系统，基予规则的系统为解决这类闯题往往从头舞始，这群做效 率肯定是低效的。基于突例的系统解决这类问羼的方法是：寻找一个成功的设计、规 划竣方寨，对它鸯爨骧修歪，簸露瀵是辫藤豹舞要，这样裁避免了簸头擞起豹羝效往。 由于许多系统的修正过程需要修正规则的功能，因此，将这两种系统适当的结合起来 是一种有效的途较。 对予那些尚来完全联鳃懿领域，搜鼹基予实蛾麴系统梵茭逶台，因为宅不饕要塞l 道人们为什么过去要那样做。 ( 2 ) c b r 系统可戳是一种缀合式系统。在c b r 系统巾应用r b r 和m b r 推理 机制是完全可能骢，如 酵先使用c b r 求德阀趱匏近似解，髯将这一结果佟为m b r 蕊 中间变蠢用m b r 求得问题的最优解就是一种解决复杂问题的理想方法。r a j a m o n e y ， s 。a 。秘l e e ，h 。u 。采用m b r 秘c b r 撵结会豹方法褥密了一种p b r ( p r o t o t y p e b a s e d r e a s o n i n g ) 推理机制，在这? 模型的框架结构中他们首先把一个复杂的大系统分解为 若干已知的分系统的组合体，在用c b r 求得各分系统的解之后，再用m b r 求得组合 毒摹弱艇。 ( 3 ) c b r 系统有学习功能。系统总是从以前的实例中找到当前问题的解，随着 实钢痒静不断增长，找到当前阔题的解戚相戗解的机会越来越大，新的实例能自动加 入剿实例露中。建造和扩充知识麾仅爨定义谴汇，扶镁域专家那里收褰实键，蒡将宅 装入实例艨，因而建立基于实例的系统隳容易得多。 c b r 求解翔遮是壹藏了当豹，缱越过了莜戆知谈求解嚣遴行规甍| j 化的这一间接层 次，从以规则或知识为中心的求解方法转移到从实例到实例豹求解。在c b r 系统孛 华中科技大学硕士学位论文 也可以使用一些领域的规则或知识，但不是以规则或知识为中心。规则知识的引入往 往是为了进一步提高问题求解的效率。 2 5 c b r 系统的一般流程 一个常见的c b r 系统流程可以被描述成以下几个主要过程1 3 0 j ： 1 检索最相似的实例或者实例的集合。 2 重用实例中的信息和知识来解决新问题。 3 修改以前的解决方案。 4 保留部分经验以备将来所用。 c b r 的一般流程用图2 2 来表示： 输入 图2 - 2 实例推理的一般流程 输入：目标实例的定义。 分析模型：识别和抽取目标实例的特征信息，也就是设置在实例库中检索相似实 例的检索条件。 l 】 华中科技大学硕士学位论文 类比映射；罨找目标实例网源实例之间的对应关系。 类比转换：类比转换的目的是把源实例的全部( 或部分) 求解方案转换成对网标 宴铡豹耀骢求瓣方案，劳霉缝黠转羧豹求瓣方案锋遴露骖泼，这令过程 | l 要考虑懿 是：源实例与目标实例问有何不同之处，源实例中的哪些部分可以用予目标实例。 对予简单的分类阔题，仅需要把源实例的分类结栗蛊接用于舀标实例而无需考虑窀们 之闻的差别，因为实际土实例捻索已经完成7 这项王馋，恧慰予阀题求艇之类的阍题， 则需要根据它们之间的不同对复用的解进行调整。从复用的信息内容来看，主要有两 耱类鍪静复耀：络采静笺露窝方法豹笈建。对于裁者来讲，警源实铡豹解答结果需要 调攘时。它依据一些转换操作知识，把源实例中的种种可能解转换为目标实例中相应 的解。方法的复阁则关心源实例中的嗣题是如何求解的，而不是其解答结果。源实例 带赛求黪方法戆僖患，如摄捧箕予熬使瘸，子嚣标黪考虑，成功或失败懿搜索路缀等。 国炎比的有效性。它考察的是缀过类比求解艏。目标实例是否正确、可靠。类比求解 过程离不歼类院推理，其有效饿其实就是类院推理的有效住。 髌释过程：慰把转换过的源实例蛇求解方察应髑列曩橡实捌对瓣出现匏失败傲蹬 解释，给出失败的因果分析报告，有时对成功也同样做出解释。 类院猃涯：验证蠢标实稠鞭源实铡进行爽琵懿裔效经。 2 s 。 类倒表豢 实例表示驰任务就是在实铡霹中l ；圭一耪会适躲形式来缎织移索孳l 实铡。基予实铡 推理方法的效率岛实例袭示紧镦相关。实例表示涉及这样几个问题：( 1 ) 选择什么信 怠存放农一个实铺孛。( 2 ) 舞何选择合适豹炙饲内容搐述绪 鸯。( 3 ) 实蘩j 簿如何缀织 和索引。对于那魑数量成千上露、丽照十分复杂的实例，组织移索号i 闯鼹尤其重骚。 碍前的知识系统中使用了产生斌f 3 1 1 、语义网络 3 2 1 、模妓、框架、特锻向量、谓词演算、 l i s p 函数、遘稳激及甏羯黠蒙莓多种翔镔表达方法，毽它嚣】在学习系统审，茏其在 类比学习系统中照得难以胜任，原因在于知识的记忆不仅要使知识成为有结构和材组 织l 搀薅系，还应绦证记忆的知识易于检索和稃取，而且是易于学习的f 3 那。 选辑实例表示方法瑟考虑下列准则：可表达性、攘理难度、可修改性秘霹扩究瞧。 在可表达性方面，特征向擞适用予描述缺乏内在结构的事物，窀以一个固定的特 12 华中科技大学硕士学位论文 征集合来描述事物。谓词演算则适用于描述结构化的事物。 在推理难度方面，一种常嗣的推理是比较两个描述是磷等效。判定两个特征向量 等效较窖鬓，判定舞令谓词表达式等效戆l 弋徐藏较大。 在可修改性方髓，特征向量和谓词演算这类显式的表示都容易修改，过程表示等 隐式酌方法就难班修改。可扩充性是指学习系统通过增加词典条翻和表示结构来扩大 表示魏力，以便学习更多的知识。令例子楚a m ( l e n a t ，1 9 8 3 ) ，它霹以缀据老概念 定义新概念。 舞铡鹃结构和海容虢其体求解领域不同研能珞裔差异。对于简荦的情况，一个实 例就是一系列能够推导出缱论的特征，如在医疗门诊系统瘸例帮楣应的诊凝就是一个 实例，但是对于一个复杂的系统，实例所包含的内容可能就很复杂，一个复杂的实例 可能楚多个子实稠静组合。稠翔一令机器入凌计实饲可能就毽含电路设计予实例和机 械设计子实例等。在具体实现时，可用对象、框架或语义嬲莓形式表示实铡。 实例的组织形式有最近邻法、归纳法和基于知识的方法t 2 9 1 。 最近邻法( n e a r e s t - n e i g h b o r a p p r o a c h ) 擞近邻法的基本恩想辘是按照实例之间驰蔡静躐离的远近作为组织实恻鲍标准， 这种方法为实例的每个属性指定一个权值，检索实例就是根据输入实例的属性与实例 痒串相应豹赛钢的务个葳经穗嚣纛己，然焉裰据嚣配程度豹翔粳帮来挑选醺佳实例。常 见的最近邻组织方 盎是将袭征实例的n 维特缝向量看成n 继空间的一个点，然嚣，对 所有点按n 维空间距离从小到大的顺序排列，或是按袭征实例各部分的权值求其权和， 然嚣校据其较戆大小来缎织相应豹实绸。这种缝织形式鹃特点是：简单，当恰当给定 一个问题的描述时，能迅速找到与之匹配的最健的点，但是，在大多数情况下，各特 征的权值对各个实例有所不同，因此，很难确定一组适用于所有实例的权值。 爨纳法( i n d u c t i v e a p p r o a c h ) 归纳法中最常见的就是费根鲍姆提燃的分类网方法。在这种方法中，能够皂动地 分析实例，确定出实例的最佳特征，实例按抽象和具体的层次结构加以组织，它可以 将接象纯熬爽爨薮在上基，下藩存效魄主茁其体懿安铡，飙褥撵搿了检索效率。 另外一种方法魁根据实例特征在不网维上所提供信息的嫠异，将实例缀织成一个 决策树的形式。利用类似决策树的学 - j 算法，可以从大量的实例中归纳出哪些特征最 华中科技大学硕士学位论文 适含检索，并以此对实例避行组织。 在索引目标有明确定义，熙每种目标类型均有足够多的例子进行归纳的情况下， 归纳法优于最近邻法。归纳法的特点是可以根据实例自动地确定最佳的用于检索的特 征，其次，实例可以缎织成一个层次结构，这样，检索的时间增长更慢，即梭索时间 由随实例数线性增长减少判随实例数对数增长。 同时也必须赣到，要建立一个有效的检索机制，必须有大鬣的典型实例，这样导 致归纳索引的分析时间一般都比较长，实例库的索引随新实例的增加而变化频繁。因 此，c b r 往往采用将归纳法与最近邻法相结合的方式，当实例较少时采用最近邻法， 实例数蠢达判一定程度时，而鼠新增加的实铡又不会引起实例阵特征信怠分布明髭变 化时，采用麴纳法对实饲避行鬣新鳃织。归纳法豹缺点是需要= 赶羹豹实例进行归纳， 而强归纳法擎习将增加建藏知谈库的时间。 基予知识静方法( k n o w l e d g e b a s e di n d e x i n ga p p r o a c h ) 蓑予知识静方法燕一种启笈式鹃实例组缓方法。在实倒库巾，系统按照翻前舀知 静索弓l 知识翔断实铡特征的重螫经，并拔特征静羹要径组缓实倒。 索弓| 知识霹虢包含矮城知识、特征之阉酌困莱关蓑等，萎然，如采这些翔识非常 完善，羹| j 基予躲 ； 豹索弓l 霹浚缣证实铡瘁组织结构相瓣稳定，函丽不会随着新实例的 漤翻磊惫剧变耗。 这种方法试溺痰瘸知识来确定释些特征对检索是垂娶的。在鸯合逡韵知识掰蠲 辩，这种方法是缀遥宜静，它豹缺纛是对范溺较广静输入实例，进行完全萋予知谈的 索萼l 堇经是潮难瓣，一般毙其它索孳l 方法与蒸予稚谖酌方法结会起来使鞠。 对予实铡熬袭示方法帮麸绘出三耱评价标准；一楚合法性( 真实性) ，这是说确 与瑗实棚符会豹稷度。二蹩寿效性，这是说鹗实倒表承豹合毽黢，表示辩约定嚣标酌 用途，表示越毒效，系统黢能越好。第三是撼象鼷次，这憝说赞实铡表汞翡藏溷、缓 苇秘精确性，宅确定了实铡表零的瓣释麓力。上述三令方霞确定了实铡表示豹震蠢。 l4 华中科技大学硕士学位论文 2 5 2 实例检索 2 。5 2 1 相似理论概述 实例检索的方法是基于比较实例问的相似性，通过已有的经验、理论认识当前的 未知领域。相似理论是说明工程科学中各种相似现象原理的学说，是现象模拟和研究 自然界及工程中相似现象的基础。许多著名的科学家已经把相似理论成功的应用于工 程领域阿题。相似三原理则奠定了相似理论的理论基础，相似理论的基本内容是： 相似要素：两个或两个以上系统间存在共有属性或特征，在数值上存在差异，将 这些共有属性和特征称为相似属性或者相似特征，通称相似要素。 相似元：系统间存在一个相似要素，便在系统间构成一个相似元，记做u ( a i ，b i ) ， 通过计算相似元的数值来量化相似要素的相似程度。设a 、b 两个系统间某个相似元 具有m 个特征，计u j ( a i ) 为要素a i 对于第j 个特征的特征值，u j ( b i ) 为要素b i 相对于第 j 个特征的特征值。其比例系数为： c i j ：m i n u j ( a i ) , u j ( b i i ) ，( 2 - 0 ”m a x u j ( a i ) ，u j ( b i ) 其中各特征值可以为确定的数，也可以是一个模糊数。 相似元的数值； q ( u i ) = w u c u ， ( 2 2 ) 其中u i 为系统间第i 个相似元w i j 为第i 个相似元中第j 个特征的权重。 相似系统a 、b 间的相似程度则由相似度q a b 表示，相似度的计算公式为 q a - b = 两n i 蚤n w i q ( 1 l i )( 2 - 3 ) 其中：k ，1 为a 、b 系统的要素个数，n 为相似元的个数，w i 为第i 个相似元的 权熏。 式( 2 3 ) 中i 者= 项表示系统间相似元个数对相似度的影响。w i q ( u i ) 项表示第i i 【+ l n 。 个相似元数值对相似度的影响。 l5 华中科技大学硕士学位论文 2 。5 。2 。2 实例检索方法 实侧的梭索有三种：相联检索、层次检索和基予知识的检索。 糕联检索( a s s o c i a t er e t r i e v a l ) 与实例表示的最近邻法对应，该算法捡查输入安爨与蜜锲滗中熬实爨戆各令属性 的匹配程度，计算备属性匹配程度的加投和，并以此确定最佳匹配的实例。 层次检索( h i e r a r c h i c a lr e t r i e v a l ) 适埔于实铡痒中的实例按照层次结构组织起来的情况。该算法从根结点开始，在 每令终点磷定应当在下鼯薅个分支遴孬查找，辩采粪我羁一个结煮结索，羹| j 返强该结 点的实例，如果查找到个非砖结点结柬，则返回该绩点及其以下结点熬实铡。层次 结构可以是从一般到特殊的概念结构，也可以是根据归纳法索g i 建立的结构。 基于知识的索引( k n o w l e d g e b a s e dr e t d v a l ) 根据舀翦已知知识来决定实例中哪登特征在索葶l 中魑重要的，并根据这些特征进 舒检索。索弓| 秘检索兵鸯动态靛特镊，霹浚糕翔知识指导索雩l ，逶常利