（计算机软件与理论专业论文）基于遗传模拟退火算法的范例推理的研究.pdf

独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得 的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得蛾磲薹或其他教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文储张前午撕期：如o 年丫月哆目 学位论文版权使用授权书 本学位论文作者完全了解宝端a 术洋有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查闶 和借阅。本人授趄安栩岳萝以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者始前予 签字日期：1 。口 年叶月_ 岁日 学位论文作者毕业去向： 工作单位 通讯地址： 导! j f 鲐勿垮厶、( 够挑 签字日期：力一7 年中月；日 电话 邮编 摘要 摘要 范例推理是人工智能领域中较新崛起的一种重要的基于知识的问题求解和 学习的方法，它是根据过去的成功或失败的事例来推导出新问题的解，是一种知 识库同推理机融为一体的新的推理技术。近年来，关于范例推理的研究及其系统 的开发受到人们的普遍关注。范例推理是由目标范例的提示而得到记忆中最相似 的源范例，并由源案例来指导目标范例求解的一种策略。范例推理不仅是关于人 类认知的心理学理论，而且将成为智能计算机系统技术新的基石之一。范例推理 技术在许多领域都可以使用，尤其在不好总结出专家知识的领域效果很好。 对于给定的目标范例，如何从范例库中检索和选择出最为相似的范例决定了 范例推理系统的学习与推理性能。范例间的相似性度量是关键。其中范例的特征 项权重对检索的质量与速度都起到了重要作用。 本文介绍了遗传算法和模拟退火算法，比较了两种算法的特性，分析了遗传 算法的优点和不足。针对遗传算法容易产生早熟现象和局部寻优能力差的特点， 使用一种混合遗传模拟退火算法用于发掘范例库上特征权重。理论分析和实验结 果表明了这种混合遗传模拟退火算法优于普通的遗传算法。再将遗传模拟退火算 法引入到范例推理中，用于范例特征项权重的发现，并将发现的权重运用到范例 检索中去，以提高检索的质量和速度。同时，将遗传模拟退火算法的思想引入到 范例推理的结构中，提出一种基于遗传模拟退火算法的范例推理模型加快了检索 速度，提高了检索质量。 最后将基于遗传模拟退火算法范例推理的思想，应用于农户信用评估系统 中，详细介绍了农户信用评估的功能模块、体系结构、范例的表示、范例检索方 法等。 安徽大学硕士学位论文 关键词：遗传算法，模拟退火算法，遗传模拟退火算法，范例推理，权重，粗糙 集理论，农户信用评估 2 a b s t r a c t a b s t r a c t c a s e b a s e dr e a s o n i n gi sak i n do fi m p o r t a n tm e t h o d sf o rq u e s t i o n a n s w e r i n ga n dl e a r n i n gb a s e do nk n o w l e d g ew h i c hg r o w su pr e c e n t l yi n a r t i f i c i a li n t e l l i g e n c ef i e l d i ti st or e a s o na n s w e rf o rn e wp r o b l e m b a s e do nt h ep a s ts u c c e s s f u lo rf a i l e dc a s e s i ti san e wr e a s o n i n g t e c h n o l o g yc o m b i n gk n o w l e d g eb a s e w i t hr e a s o n i n g i nr e c e n ty e a r s ， c a s e b a s e dr e a s o n i n gr e s e a r c ha n di t ss y s t e md e v e l o p m e n th a sr e c e i v e d p e o p l e su n i v e r s a la t t e n t i o n c a s e b a s e dr e a s o n i n gi sas t r a t e g yw h i c h g e t st h em o s ts i m il a rs o u r c ec a s ei nt h em e m o r yb yt h eh i n t so ft h et a r g e t c a s ea n dg e t st h ea n s w e r sb yt h ei n s t r u c t i o no ft h es o u r c ec a s e c a s e b a s e d r e a s o n i n gi sn o to n l ya b o u th u m a nc o g n i t i o np s y c h o l o g yt h e o r y ，b u ta l s o w i l lb e c o m et h ef o u n d a t i o ns t o n eo ft h ei n t e l l i g e n tc o m p u t e r s y s t e m t e c h n o l o g y c a s e b a s e dr e a s o n i n gc a nb eu s e di nm a n yd i f f e r e n tf i e l d s ， e s p e c i a l l y i nt h ef i e l d sw h i c ha r ed i f f i c u l tt oc o n c l u d ee x p e r t s k n o w l e d g e a st ot a r g e tc a s eg i v e n h o wt oc h e c ka n dc h o o s et h em o s ts i m il a rc a s e f r o mc a s e 。b a s ed e c i d e sl e a r n i n ga n dr e a s o n i n gf u n c t i o n so fc a s e b a s e d r e a s o n i n gs y s t e m t h es i m i l a r it yb e t w e e nc a s e sist h ek e y t h ef e a t u r e w e i g h to fc a s ep l a y sa ni m p o r t a n tr o l ei nc h e c k i n gq u a l i t ya n ds p e e do f i n d e x t h i sp a p e rf i r s ti n t r o d u c e st h et r a d i t i o n a lg e n e t i ca l g o r i t h mb r i e f l y ， t h e na n a l y s i st h ea d v a n t a g e sa n dd is a d v a n t a g e so fg a a i m e da tt h e p r e m a t u r ec o n v e r g e n c ep r o b l e ma n dt h eb a d l y1 0 c a l o p t i m i z a t i o ne x i s t e d i ng a ，b r i n g sf o r w a r df lm i x e dg e n e t i ca n ds i m u l a t e da n n e a l i n ga l g o r i t h m 。 a n d p u t sf o r w a r do n ew e i g h t i n gm e t h o db yu s i n gg e n e t i c s i m u l a t e d a n n e a l i n ga l g o r i t h m t h et h e o r e t i c a la n a l y s i sa n de x p e r i m e n t a lr e s u l t s l 窒堕盔兰塑主堂垡堡奎 s h o w st h a tt h ism e t h o dh a sb e t t e rp e r f o r m a n c et h a no t h e rm e t h o d s i th a s b e e nu s e di nc a s e b a s e dr e a s o n i n gt od i s c o v e rt h ef e a t u r ew e i g h to fc a s e a n di m p r o v eq u a l i t ya n ds p e e do fc a s ec h e c k i n g a tt h es i m i l et i m e ，i d e a o fs i m u l a t e da n n e a li n ga l g o r i t h mi si m p o r t e di n t oc a s e b a s e dr e a s o n i n g s t r u c t u r ea n dp r o m o t e sac a s e b a s e dr e a s o n i n gm o d e lo nt h eb a s i so f s i m u l a t e da n n e a l i n ga l g o r i t h m i nt h e e n d t h ei d e aw h i c hb a s e so nt h ec a s e - b a s e dr e a s o n i n go f s i m u l a t e da n n e a l i n ga l g o r i t h mi sa p p l i e di n t of a r m e rc r e d i te v a l u a t i o n s y s t e m ，t h e ni n t r o d u c e st h ef u n c t i o nm o d u l e s ，s y s t e ma r c h i t e c t u r e ，c a s e d e s c r i p t i o n ，t h em e t h o do fs i m i l a re v a l u a t i o na n dt h em e t h o do f c a s e c h e c k i n gi nd e t a i 1 k e yw o r d s ：g e n e t i ca l g o r i t h m ，s i m u l a t e da n n e a l i n ga l g o r i t h m s ，g e n e t i ca n d s i m u l a t e da n n e a l i n ga l g o r i t h m s ，c a s e b a s e dr e a s o n i n g ，w e i g h t ，r o u g hs e t ，f a r m e rc r e d i te v a l u a t i o n 2 第一章引言 第一章引言 1 1 范例推理的发展历史与现状 基于范例的推理( c a s e b a s e dr e a s o n i n g ，c b r ) 是人工智能领域中较新崛 起的一种重要的基于知识的问题求解和学习的方法，它是根据过去的成功的或失 败的事例来推导出新闯题的解，它是一种知识库同推理机融为一体的新的推理技 术。 最早是由美国耶鲁大学的r o g e rs h a n k 在1 9 8 2 年提出的。他出版了一本 ( d y n a m i cm e m o r y ，书中详细描述了c b r 的最早研究工作，给出了在计算机上 建造c b r 的方法。由佐治亚工学院的j a n e tk o l o d n e r 等人于1 9 8 3 年开始在计算 机上实现，c y r u s 即是其领导开发的第一个基于范例的推理系统；在c y r u s 的范 例记忆模型基础上，美国许多大学的研究人员开发了一些c b r 系统。c b r 出现后， 美国在8 0 年代后期就这一推理机制的理论及方法进行了较为系统的研究，并用 在分类、计划、设计、法律、烹饪、医学、土建等诸多领域，开发了数百个应用 实例。典型的c b r 软件及开发工具有e s t e e m 公司的e s t e e m 、i n f e r e n c e 公司的 c b r 2 、h a l e y 公司的e e l i p s e 等。 随着对c b r 的研究兴趣逐渐增大，1 9 9 5 年l o 月在葡萄牙召开了第一界c b r 国际会议。我国在c b r 方面的研究与发展起步较晚，非常成型的产品尚不多见。 目前，人们对c b r 的研究和应用，已经深入到热门的电子商务、w w 及信息服务、 规划、设计、诊断、分类、辅助决策、音乐、软件复用、辩论和法律案例推理、 医学、争端调节以及智能教学等领域。 我国的c b r 的研究与系统开发起步较晚，但在上个世纪9 0 年代初也见到了 这方面的研究与应用。例如北方交大的田盛丰、张清等人将c b r 用于岩石工程中 的支护辅助设计中，效果显著，复旦大学的蒋栎等人将c b r 用于西文图书分类中， 以相当高的正确率获得了用户欢迎。中国科学院计算技术研究所智能信息处理重 点实验室在基于范例推理方面进行了一系列研究。1 9 9 1 年史忠植、李宝东提出 了记忆网模型和范例检索算法。1 9 9 3 年周涵研制了基于范例学习的内燃机油产 品设计系统e o f d s 。1 9 9 4 年徐众会开发了基于范例推理的天气预报系统。1 9 9 6 安徽大学硕士学位论文 年王军开发了基于范例推理的淮河王家坝洪水预报调度系统f o r e z 。2 0 0 0 年叶施 仁等研制了渔情分析专家系统。这些都充分说明了c b r 作为人工智能的一个分支 有较大的应用价值凹。 经过二十年的深入研究，人们基本上对c b r 有了一个明确的了解，下面是 c b r 中被研究最多的几类问题。 ( 1 ) 范例的表达 实践中的范例是各种各样的，如何有效地表示范例以便于推理及贮存， 是c b r 首先遇到的问题，近二十年的研究，提出了许多种范例表达的方法。 ( 2 ) 范例的索引 c b r 系统的效率很大程度上决定于快速准确地从范例库中检索出合适范 例的能力，为此必须对范例库中的范例进行适当的组织及索引。索引的方法 也多种多样。 ( 3 ) 范例的检索 检索就是依据索引对范例库检索出候选的范例来，其方法与索引一一对 应有相应的算法。 ( 4 ) 范例的修正 范例的检索找到了与输入范例最类似的范例，即检索出的范例应满足大 部分输入的要求。修正则是将范例由满足大部分输入的要求修改成满足所有 输入要求的范例。由于修正同具体问题领域知识有关，因此没有统一的办法， 往往要和领域专家合作。 c b r 的发展趋势可以概括为以下几个主要方面：与其它学习方法的集成；与 其它推理方法的集成；被融合进大规模并行处理；通过认知科学的新进展带动 c b r 方法的进步；用c b r 方法进行知识管理。 1 2 遗传算法的发展历史与现状 2 0 世纪5 0 年代和6 0 年代，就有计算机学者开始研究。入工进化系统”，将 进化的思想发展成为许多工程问题的优化工具。早期的研究形成了遗传算法的雏 形，大多数系统都遵循“适者生存”的仿自然法则。 6 第一章引言 1 9 7 5 年，美国m i c h i g a n 大学的h o l l a n d 教授发表了a d a p t a t i o ni nn a t u r a l a n da r t i f i c i a ls y s t e m s 一书，该书系统地阐述了遗传算法的基本理论和方法， 为其奠定了数学基础，提出了对遗传算法的理论研究和发展极为重要的模式理 论。同年，d ej o n g 完成了对g a 算法研究具有指导意义的博士学位论文遗 传自适应系统的行为分析 a na n a l y s i so ft h eb e h a v i o ro fac l a s so fg e n e t i c a d a p t i v es y s t e m s 。d ej o n g 把h o ll a n d 的模式定理和他自己细致的计算结果 成功地结合在一起，在此基础上给出了至今仍广泛应用的著名的d ej o n g 五函数 测试平台。可以认为，d ej o n g 的研究工作为g a 算法及其应用打下了坚实的基 础，他的研究成果是g a 算法发展史上的里程碑。 自8 0 年代中期以来，是遗传算法的蓬勃发展期，研究者对遗传算法的应用 研究不断扩大和深入。有用于t s p 问题、调度问题、键盘构造问题、多关节机械 手轨迹规划问题、工程中的设计辅助问题、机器学习问题、囚徒困境问题、模式 分类问题，神经网的基因综合，神经网的辅助设计、程序自动生成一遗传编码。 此外，遗传算法还在预测控制等问题中都有运用研究。目前g a 的研究己构成与 神经网络，模糊控制并驾齐驱的一大领域。 遗传算法是一种进化搜索算法，它的基本思想是基于d a r w i n 的进化论和 m e n d e l 的遗传学说。其中交叉算子和变异算子是遗传算法的两个重要组成部分， 它们被重复地应用到对问题的解进行编码而构成的染色体上。在许多优化问题和 工业实际应用上，g a 已经得到了成功的应用。 遗传算法思想独特、通用性强、实现简单，给研究者们留下了广阔的探索空 间。它是一个多学科结合与渗透的产物，已经发展成一种自组织、自适应的综合 技术，广泛应用在计算机科学、工程技术和社会科学等领域”1 。 我国有关遗传算法的研究，从2 0 世纪如年代以来一直处于不断上升的趋势， 特别是近年来，遗传算法的应用在许多领域取得了令人瞩目的成果，该类研究获 得不同渠道的经费资助比例也在逐年上升。武汉大学的刘勇、康立山等于1 9 9 5 年出版了非数值并行算法( 第2 册) 一遗传算法：周明、孙树栋于1 9 9 9 年出版 了遗传算法原理及其应用：同济大学的王小平，曹立明于2 0 0 0 年出版了遗 传算法理论、应用与软件实现。国内有关遗传算法的b b s 电子公告牌有国家智 能中心曙光站b b s n e i c ，a c ，e n 、北京大学阳光创意站h b s p k u e d u e l l 清华大学 水土清华站b b s n e t t s i n g h u a e d u ，c n 、西安交通大学兵马佣站b b s 安徽大学硕士学位论文 x n n e t e d u c n 、研学论坛h t t p ：b b s m a t w a v c o m 等。 总之，遗传算法在理论上己经借鉴生物进化理论及遗传学机理形成了一套较 为完整的算法体系，然而在实践上还有很多问题有待于进一步研究、探讨和完善。 它们主要反映在以下方面：( 1 ) 控制参数选择问题：2 ) 成熟前收敛问题：( 3 ) 遗传算 法的性能评价问题：( 4 ) 遗传算法的适应性问题：( 5 ) 混合算法问题：( 6 ) 从生物进 化或遗传工程中不断汲取新的知识获得新的启发，从而对现有遗传算法讲行改进 或提出新的新的算法等。 遗传算法自提出，特别是八十年代中期以来，已得到广泛研究与应用。其研 究的内容大体集中在以下儿个方面： 1 有关算法随机搜索机理的研究 遗传算法是通过作用于一个初始种群，而循环执行复制、杂交、变异及选择 过程的随机迭代，故阐明如此简单的循环操作如何有效搜索整个编码空间以达到 全局优化之目的有特别重要的意义。在这方面，j h h o l l a n d 等人发展的所谓 “模式( s c h e m a ) 理论”引人注目。一个模式是指编码空间( 即所使用的染色体的 全体。当应用l 位二进制串编码时，该空间为一个具有相同构形( c o n f i g u r a t i o n ) 的编码的子集。所谓具有相同构形是指：这个子集中诸编码串在某些位上具有相 同的码值。例如，在编码空间中，给定一个模式，一个编码称为与该模式相匹配， 如果在模式的确定位上，此编码的值与模式的值相同，例如，编码( 100010 1 100 ) ， ( 1010101000 ) 均与上述所指定的模式相匹配。任一给定编 码必与许多模式相匹配。模式理论的核心在于：遗传算法能够有效搜索的根本原 因是，它充分利用了模式所描述的编码之间的相似性，虽然算法仅作用于n 个编 码组成的种群，但这n 个编码实际上包含阶个模式的信息。这一性质常被称作是 遗传算法的隐含并行性( i m p l i c i tp a r a l l i s m ) 。 模式理论可以较好地解释遗传算法的搜索机制。对于任一模式，定义它的阶 为模式中确定码值的个数，而定义它的长度为模式中第一个确定码值位与最后一 个确定码值位之间的差，则h o l l a n d 证明了如下的模式定理：“具有短长度的、 低阶的、适应性在群体平均之上的模式将在遗传算法中以指数增长率在子代中被 采样。 2 有关算法的全局最优性( 或收敛性) 研究 生物进化的“趋势向上”性似乎应蕴含遗传算法的最终收敛性，这一研究的 8 第一章引言 目的在于从理论上对这一事实给出证明。与算法收敛性紧密相关的一个问题是遗 传算法的过早收敛( p r c m a t u r ec o n v e r g e n c e ) 。它出现在算法还未达到全局最优 情形而不再产生适应性更强的后代。研究表明：遗传算法的过早收敛主要由杂交 算子引起。在模式空间中存在大量所谓的早熟集( p r e m a t u r e s e t ) ( 即在选择与杂 交算子复合作用下的不变集) ，而在杂交算子作用下，遗传算法总以非零概率“撞 入”早熟集。由于早熟集的吸收性，从而使算法产生过早收敛。 3 有关染色体编码格式的讨论 遗传算法的作用对象是优化变量的染色体编码( 即与变量的某种离散化近 似) 。通常认为：采用编码方式( 特别是二进制编码) 有以下优点：a ) 可很好地指导 搜索，使得有关某种结构的个体容易生存，以产生适应性更强的后代：b ) 使算法 具有隐含并行性，使在相对少量的种群上进行的操作实质上隐含着大范围的搜 索。采用编码格式的缺陷是：由于连续问题化归到组合问题求解，使算法的求解 精度受到很大影响。这些优点和缺点当遗传算法用于( 组合) 优化问题的求解时均 有明显体现“。 上述有关遗传算法研究的几个方面应该说还是相当初步的。对它的进一步深 入探讨正构成当前计算智能研究的“热点”。概括地说，当前有关遗传算法的研 究兴趣主要集中在以下几个方面： ( 1 ) 有关算法的理论基础：这特别包括遗传算法的收敛性、收敛速度估计、过 早收敛的机理探索与预防、杂交算子的几何意义与统计解释、参数设置( 如种群 规模、编码长度等) 对算法效率的影响等方面。我们认为：有关算法的收敛速度估 计是当前特别值得花大力气加以探讨的问题( 目前尚无任何结果) ，因为它能从理 论上对遗传算法的任何修正形式，提供判别标准，以指明改进遗传算法效能的正 确方向。 ( 2 ) 有关算法与其它优化技术的比较与融合：作为已知较为成熟的全局优化 算法一模拟退火方法，它与遗传算法的结合已有不少研究。然而，充分利用遗传 算法的大范围群体搜索性能与己知局部优化方法的快速收敛性来产生有效全局 优化方法，研究仍不多见。人们感到，这种整体搜索策略与快速局部优化方法的 混合是从根本上提高遗传算法计算效能的措施。这方面还需要做大量的理论分析 与实验研究。 ( 3 ) 有关遗传算法的并行化研究遗传算法的群体、随机搜索特征使它有明显 9 安徽大学硕士学位论文 的可行并行化特性。设计它的各种并行化执行策略及其建立相应并行算法的理论 基础均是具有重要意义的工作。 ( 4 ) 遗传算法在人工神经网络、机器学习、复杂组合优化问题求解、金融市 场分析和预测、专家系统等领域己有广泛应用。一般说，根据具体应用领域来有 效改进遗传算法是可能的和实际的( 而相反，泛泛地对一般问题研究显得极其困 难) 。所以，针对具体应用问题，深化研究遗传算法( 如参数设置、遗传算子构造 等) 是当前特别值得提倡的上作嘲。 1 3 模拟退火算法的发展历史与现状 模拟退火又称m o n t ec a r l o 退火，是一种常用的全局优化方法，它来源于固 体退火原理：将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随 温升变为无序状态，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到 平衡态，最后在常温时达到基态，内能减为最小；然而要是迅速冷却或被“碎熄”， 那么仅仅能达到其局部能量极小点，该材料处于易碎状态。这就是所谓退火在技 术上的定义，同时也表明了确保达到低能量状态所必需的条件。 1 9 8 2 年，k i r k p a t r i c k 等将退火思想引入组合优化问题，同时综合了统计物 理学和局部搜索方法，提出一种解大规模组合优化问题的方法，特别是n p 完全 组合优化问题的有效近似算法一模拟退火算法。采用m e t r o p o l i s 接受准则，并 用一组称为冷却进度表的参数控制算法进程，是算法在多项式时间里给出一个近 似最优解。 模拟退火法是随机最优化算法的迭代。当连续梯度下降函数不存在，或连续 梯度下降函数局限于一个地区的最小化时，它经常应用于最佳问题的选择中。 模拟退火算法要优于局部搜索算法，原因在于它与局部搜索算法接受新解的 准则不同，允许目标函数在有限范围内交坏，由一控制参数r ( 温度) 决定。温度 r 在程序刚开始时被设置为一个较高的值，在程序进行的过程中慢慢减少，高温 下，可以接受较差的恶化解，随着r 值的减小，只能接受与当前状态差别较小的 恶化解，最后在r 值趋于零时，就不再接受任何恶化解了。高温时，接受“坏” 状态的可能性高，即使没有改进：低温时，接受没有提高质量的状态的可能性很 l o 第一章引言 小，该特点使得模拟退火法可以从局部极小的“陷井”中跳出，更有可能求得组 合优化问题的整体最优解”1 。 模拟退火算法具有十分顽强的全局搜索性，这是因为比起普通的优化搜索 方法，它采用了许多独特的方法和技术，归纳起来主要有一下二个方面。 ( 1 ) 在模拟退火算法中，基本不用搜索空间的知识或者其它的辅助信息( 启 发式搜索算法需用) ，而只是定义邻域结构，在其邻域结构内选取相邻解，再用 目标函数进行评估。 ( 2 ) 模拟退火算法不是采用确定性规则，二是采用概率的变迁来指导它的 搜索方向的。它所采用的概率仅仅是作为一种工具来引导其搜索过程朝着搜索空 间的更优化的解区域移动。因此，虽然看起来它是一种盲目的搜索方法，但实 际上有着明确的搜索方向。 以往的排料系统中，遗传算法应用的很多，相对也较成熟，模拟退火算法 在自动排料系统的研究处于发展阶段，有研究的空间：还有相对于遗传算法， 模拟退火算法无需进行编码的操作，减少了计算的复杂性”1 。 1 4 本文所做的主要工作 在本文中，我们重点研究了遗传模拟退火算法在范例推理系统( c b r ) 中的 应用。全文共分六章，下面是本文的组织及各章的主要内容： 第一章是引言。首先对范例推理、遗传算法、模拟退火算法的发展历史和研 究现状进行了综述，提出了本文的研究方向，之后概述了本文各章的研究内容。 第二章是范例推理的基本原理。首先简要介绍了范例推理的提出的发展状 况、范例推理基本原理以及结构、范例推理系统的特点一些相关的基本概念。之 后对范例推理中的关键技术作了深入的研究和探讨。 第三章是遗传模拟退火算法。首先简要介绍了遗传算法的一些基本概念、工 作过程、以及其优缺点，然后介绍了模拟退火算法的基本思想、算法流程、以及 其特点。最后将模拟退火算法引入遗传算法中。 第四章是遗传模拟退火算法在范例推理中的应用研究。首先讨论了粗糙集理 论和基于遗传算法的粗糙集理论约简属性，之后在前面两章的基础上，研究和探 安徽大学硕士学位论文 讨了将遗传模拟退火算法应用到范例权重发现和范例检索中，并给出了实验实 例。实验结果证明了该算法能够有效地提高范例推理系统的性能。 第五章研究了基于g a s a 与c b r 的农户信用评估技术，介绍了农户信用评 估的功能模块、体系结构。 第六章是总结与展望。对全文主要的研究工作做了总结，并对今后的研究方 向作了迸一步的展望。 1 2 第二章范例推理 第二章范例推理 2 1c b r 的提出及发展概况 最早描述了c b r 的研究工作的是，r o g e rs c h a n k 在1 9 8 2 年出版的黔n a m i c m e m o r y ：at h e o r yo fr e m i n d i n ga n dl e a r n i n gi nc o m p u t e ra n dp e o p l e 著 作中，给出了计算机上建造这种推理系统的方法。他的早期思想被耶鲁大学的学 生推广，1 9 8 3 年著名的佐治亚工学院的j a n e tk o l o d n e r 的c y r u s 系统在计算机 上首次实现了r o g e rs c h a n k 著作中的许多原理。接着，耶鲁大学、佐治亚工学 院和马萨诸塞大学的研究生又建立了一些系统，这些系统在法律、烹饪、医药、 故障诊断、农业、气象、软件工程、电路或机械设计等领域中证明了c b r 。目前 美国是开展c b r 研究与开发最普遍的国家，欧洲、日本等工业化国家对c b r 的有 关问题及相应的系统正在进行大量的研究与开发，建立上百个用c b r 推理的知识 系统阱。 。 我国的c b r 的研究与系统开发起步较晚，但在上个世纪9 0 年代初也见到了 这方厦的研究与应用。例如北方交大的田盛丰、张清等人将c b r 用于岩石工程中 的支护辅助设计中，效果显著，复旦大学的蒋栎等人将c b r 用于西文图书分类中， 以相当高的正确率获得了用户欢迎。中国科学院计算技术研究所智能信息处理重 点实验室在基于范例推理方面进行了一系列研究。1 9 9 1 年史忠植、李宝东提出 了记忆网模型和范例检索算法。1 9 9 3 年周涵研制了基于范例学习的内燃机油产 品设计系统e o f d s 。1 9 9 4 年徐众会开发了基于范例推理的天气预报系统。1 9 9 6 年王军开发了基于范例推理的淮河王家坝洪水预报调度系统f o r e z 。2 0 0 0 年叶施 仁等研制了渔情分析专家系统。这些都充分说明了c b r 作为人工智能的一个分支 有较大的应用价值。 2 2c b r 原理及结构 范例推理c b r 是一种类比推理方法，是由目标范例的提示而得到历史记忆中 安徽大学硕士学位论文 的源范例，并由源范例来指导目标范例求解的一种策略，它是一种重要的机器学 习方法。c b r 提供了一种近似人类思维模型的建造专家系统的新的方法学，这与 人对自然问题的求解相一致。它克服了传统的基于规则推理( r u l e b a s e d r e a s o n i n g ，r b r ) 系统的知识难于获取和推理的脆弱性。c b r 是区别于基于规则 推理的一种推理和学习模式，它是指借用旧的事例或经验来解决问题、评价解决 方案、解释异常情况或理解新情况。 所谓范例( c a s e ) 就是对应用领域内一个问题的描述，由问题的状态和与其 相应的解决方案两部分组成，实际上是一个从问题的状态空闻到解决方案空间的 一个映射。范例是一段带有上下文信息的知识，该知识表达了推理机在达到其目 标的过程中能起关键作用的经验。在c b r 中，把当前面临的问题或情况称为目标 范例，而把记忆中的问题或情况称为源范例。对于范例推理，一个通俗的解释是： 为了找到一个实际新问题的解，首先在经验库中寻找相似的问题，从过去的相似 问题中取出解，并把它作为求解实际问题解的起点，通过适应性修改而获得新问 题的解。 范例推理的基本思想是：基于人们在问题求解中习惯于过去处理类似问题的 经验和获取的知识，再针对新旧情况的差异做相应的调整，从而得到新问题的解 并形成新的范例。一般地，范例推理具有如下步骤。如图2 1 图2 - 1 范例推理的步骤 ( 1 ) 范例库( c a s eb a s e ) ：范例库是用来存储过去范例的存储空间，包含成 功及失败的范例，每一种范例都以一定的表示方式存放在范例库中，这种表示形 式必须包含范例的丰要因素、环境条件及范例的基本特征与丰要参数值，但范例 的表示没有统一的方式与方法，主要根据问题的类型具体分析确定。 1 4 第二章范例推理 ( 2 ) 检索( r e t r i e v e ) ：依据输入待解决的问题的有关信息，检索出范例库中 同新问题最近似的范例。常用的有相联法、层次法及基于知识法，f u z z y 检索等。 ( 3 ) 重用( r e u s e ) ：从检索到的一组范例中获得求解方案，判别是否符合需 求，若符合，则重用这些方案( 或多个方案的合并解) ，否则需要修正： ( 4 ) 修正( r e v i s e ) ：范例的检索得到与新问题最匹配的范例，范例的修正就 是将该范例由满足大部分输入的要求修正成满足所有输入的范例。由于范例的修 正与具体问题邻域有关，难以规定统一的方法“。 ( 5 ) 保存( r e t a i n ) ：是扩充和更新范例库的一种手段，以确保所建立的c b r 系统长期有效、可靠地应用。它根据所给问题的条件通过修正所得到的成功的或 失败的范例根据一定的策略进行加工，然后存入范例库中。这是c b r 的学习方式。 2 3c b r 系统的特点 人类求解问题的方法需要鲁棒性，我们常常以有限的、不确定的知识解决困 难问题，并且随着经验的增长，处理问题的能力不断地增强。这也是应用于现实 世界问题领域的人工智能系统所需要的性质。复用以前经验的方法是人类专家的 一种基本而重要的解决问题的方法。 传统的基于知识系统( 主要指知识表示采用产生式规则或框架的专家系统) 存在一定的困难，例如： ( 1 ) 知识获取的瓶颈问题，随着大型专家系统的出现，知识获取的瓶颈问题 将越来越严重，一定程度上影响了传统基于知识系统的应用发展； ( 2 ) 固定的求解范围，专家系统仅仅能求解知识库所覆盖的问题； ( 3 ) 推理链不能太长，为了保证不确定性推理的有效性，专家系统的推理链 不能太长，因而传统的基于知识系统不适于解决推理链过长的复杂问题： ( 4 ) 知识库维护的困难，假定知识表示采用产生式规则。由于知识库中的规 则之间并不具有完全的独立性，知识库的增长并非单调的，新旧规则之问可能会 存在冲突，所以知识库的维护仍然十分困难； ( 5 ) 问题推理的重复性，传统的基于知识的系统遇到其以前求解过的问题时， 就如同没有遇到过一样，它照旧要重复完成全部推理过程； 安徽大学硕士学位论文 ( 6 ) 在一些领域，人类专家还不能提供问题求解的规则，在这样的领域无法 建立基于规则的专家系统“”。 c b r 方法在以下方面做出了改进： ( 1 ) 知识获取 c b r 系统使用的主要知识是范例，而范例的获取要比规则获取容易得多。c b r 不需要特化和泛化经验以形成规则。在一些应用领域，存在着天然的范例，例如 医院中的病历。这些领域中，范例获取的代价非常低。对于提取范例有困难的应 用领域，c b r 系统的建立需要通过“范例工程( c a s ee n g i n e e r i n g ) ”来确定范 例所必须包含的信息，定义信息的表示方法以及从可提供的数据中抽取信息，从 而进一步提取范例。抽取信息的过程中可以采用数据挖掘技术。虽然，这种初始 的处理过程需要大量的工作，c b r 仍然具有优势，因为大部分的专家感到提取领 域中的规则集十分困难时，更愿意讲述他们解决难题时的真实故事，即他们所记 住的范例。 ( 2 ) 知识库维护 初始时对领域问题的理解往往是不完备的，而且任务需求和环境的变化可能 会导致已有知识的过时，因此知识库的维护是十分重要的。c b r 为知识维护提供 了很大的方便，可以不需要专家的干预而把需要的范例加到范例库中，完成c b r 的学习功能。 ( 3 ) 解决问题的范围扩大 传统的专家系统是演绎推理，所有关于问题的解答都预先包含在知识库中， 不具备创新求解能力。c b r 系统主要基于类比推理，通过适应性修改可以形成与 旧范例处理不同的新方案，即c b r 与专家系统不同。它可以处理“例外情况”。 ( 4 ) 求解过程的简化 在复杂问题的求解中，c b r 一般不需要考虑问题求解的具体细节，范例的复 用节省了大量的时间。当同样一个问题出现时，传统的专家系统会重复进行推理， 而c b r 系统会记住和使用上一次的结果，并且可以避免重复失败求解的代价，因 为c b r 保存了成功的解和失败的解。同时，它跳过了依赖问题求解知识进行规则 化抽象这一间接层次。如果说从解决复杂问题的数学模型发展到专家系统的以规 则或知识为中心的方法是问题求解模型认识上的一大飞跃，那么从以规则或知识 1 6 第二章范例推理 为中心的方法转变到从范例到范例的问题求解思想又是一个新的进步。当然，在 范例推理中并不排斥领域规则知识的使用，就像专家系统不排斥定量的数学模型 使用一样，规则知识的引入在范例推理中往往是为了进一步提高问题求解的效 率； ( 5 ) 解质量的提高 由于c b r 中保存的是真实发生过的事情，因此通常比规则链更准确。当人们 对一个研究领域还没有完全掌握时，所获得的规则性知识将是不完备的。这种情 况下，由范铡建汉的结果可能比由规则链推出的结果更加准确和可靠，因为范例 毕竟是真实发生过的事情。 ( 6 ) c b r 系统得到的结果用户易于接受 用户需要证明他们所得到的解是可信的。c b r 系统的结论是以过去的范例为 基础，这些范例可以展示给用户，“用事实说话”，作为系统得出结论的有利支持。 由于它把知识获取的任务简化为建立范例描述方法和从专家那里搜集范例，因此 可以杜绝知识获取中知识畸变的一些环节，从而有利于克服专家系统构造中的瓶 颈问题。 2 4c b r 的关键技术 2 4 1 范例的表示及存储 范例推理的效果在某种程度上依赖于范例库的结构以及范例的知识表示方 式。以一种适当的形式将知识在计算机中表示出来是使机器具有智能的前提和基 础，这也是知识表示的研究为什么一直在人工智能中占据相当重要地位的原因。 同样，基于范例推理方法的效率和范例表示紧密相关。范例表示常常涉及到 这样几个问题：什么是范例；选择什么信息存放在一个范例中；如何选择合适的 范例内容描述结构；范例库如何组织和索引，以便于检索及复用，对于那些数量 达到成千上万，而且十分复杂的范例，组织和索引问题尤其重要。简单地说，一 个范例就是能导致特定结果的事物的一系列特征属性的集合，例如，病例及其相 应的诊断。对于复杂的形式而言，范例就是形成问题求解结构的子范例的关联集 合，例如，一架飞机和一个电路的设计由许多子设计组成，整个问题的每一组成 安徽大学硕士学位论文 部分对整个问题来说可以认为是一个范例。 范例库包含了应用领域中的历史经验。从问题求解角度来看，范例应包含对 问题整体情况的描述，还应包含对问题的解或解的方法的描述，有时我们需要知 道一次问题求解的效果，所给的问题求解方法是否有效等，所以范例可表示成： ( 问题描述，解描述) ，或( 问题描述，解描述，效果描述) 当然，范例的表示也可以有其它的方式。例如：在p r o t o s 系统中建立了一 种分类一一范例模型，范例被保存在一个由分类、范例和索引指针构成的网状结 构中。 迄今为止，关于范例的表示及存储的研究已取得了令人瞩目的成就，比较成 功的知识表示方法有十余种，如：逻辑表示法、产生式表示法、语义网表示法、 面向对象表示法“”。 一般来说，范例表示的设计可以分为两个阶段：概念设计阶段，即方案的生 成；方案的实现阶段，即根据设计方案进行结果的生成操作，形成最后的设计结 果。比如将范例表示为层次形式，可以降低每个范例中的信息粒度，使得范例容 易操作，还可以根据设计活动中不同阶段的特点，表示不同的层次。 2 4 2 范例的检索技术 范例检索是从范例库中找到一个或多个与当前问题最相似的范例。c b r 系统 中的知识库是由领域专家以前解决过的一些问题组成。当接受一个求解新问题的 要求后，c b r 利用相似度知识和特征索引从范例库中找出与当前问题相关的最佳 范例。所得到的范例的质量和数量直接影响着问题的解决效果，所以范例的检索 技术也是相当重要的。一般说来，范例检索应达到两个目标：检索出来的范例应 尽可能少；检索出来的范例应尽可能与当前范例相关或相似。检索任务的子过程 包括：特性鉴别，初始匹配和最佳选定。 特征鉴别是指对问题进行分析，提取有关特征。特征提取的方式有：从问题 的描述中直接获得问题的特征。例如，对自然语言对问题进行描述，并输入系统， 系统提取关键词获得问题的某些特征。对问题经过分析理解后导出特征，如图像 分析理解中涉及的特征提取。根据上下文或知识模型的需要扶用户那里通过交互 方式获取特征。系统向用， 1 提问，以缩小检索范围，使检索的事例更加准确。 初步匹配是指从范例库中找到一组与当前问题相关的候选范例，这是通过使 - 1 s 第二章范例推理 用特征鉴别获取的特征作为范例库的索引来完成检索的。由于一般不存在完全的 精确匹配，所以要对范例之间的特征关系进行相似度估计，它可以是基于上述特 征的与领域知识关系不大的表面估计，也可以是通过问题进行深入理解和分析后 的深层估计。在具体做法上，则可以通过对特