（计算机应用技术专业论文）基于遗传禁忌算法的范例推理的研究.pdf

安徽人学顷l 学位论文 摘要 摘要 范例推理是人工智能领域中较新崛起的一种重要的基于知识的问题求解和 学习的方法，它是根据过去的成功或失败的事例来推导出新问题的解它是一种 知识库同推理机融为一体的新的推理技术。近年来，关于范例推理的研究及其系 统的丌发受到人们的普遍关注。范例推理是由目标范例的提示而得到记忆中最相 似的源范例，并由源案例束指导目标范例求解的一种策略。范例推理不仅是关于 人类认知的心理学理论，而且将成为智能计算机系统技术新的基石之一范例推 理技术在许多领域都可以使用，尤其在不好总结出专家知识的领域效果很好 然而在范例推理中也存在一些问题，主要体现在范例工程过程的自动化，即 范例知识的自动生成，如范例结构及其内容、相似性评估知识、现有范例库的自 动更新，修正知识库的获取、索引模式等而这些知识的获取也存在一定程度的 瓶颈问题这些知识是由领域专家与知识工程师通过不断积累慢慢取得的 对于给定的目标范例，如何从范例库中检索和选择出最为相似的范例决定了 范例推理系统的学习与推理性能范例日j 的相似性度量是关键。其中范例的特征 项权重对检索的质量与速度都起到了重要作用。对范例库特征项权重的提取也就 是来发现范例的不同特征具有不同的重要性。 遗传算法作为一种借鉴生物界自然选择和自然遗传机制的高度并行、自组 织、自适应的搜索算法，由于其隐含并行性和收敛的全局性两大显著特点，使其 尤其适用于处理传统搜索方法难于解决的复杂问题禁忌搜索算法是一种局部搜 索修正算法，模拟人类具有记忆功能的寻优特征即人们常常在对已经搜索过的 地方暂时不会再次去搜索，先对尚未搜索过的地方进行搜索，如果没有更为合适 的解，则返回原来已经搜索过的地方禁忌搜索算法通过局部邻域搜索机制和相 应的禁忌准则，来避免重复迂回搜索，并通过期望标准来释放一些被禁忌的优良 个体，进而保证多样化的有效搜索，以此来最终实现全局优化。 遗传禁忌算法结合了遗传算法的随机搜索能力、并行性和禁忌搜索算法的记 忆功能，有效地解决了遗传算法的爬山能力差、早熟的问题。该算法把禁忌搜索 的“多样化”引入到遗传算法的交叉算子和变异算子中，生成禁忌交叉算子和禁 盘徽人学硕i 学位论义苹十遗传禁忌算法的范倒扦理的研究 忌变异算子，使得算法在搜索过程具有记忆性。禁忌遗传算法避免了遗传算法的 早熟问题，提高了遗传算法的收敛速度和优化质量，改善遗传算法的优化性能及 其鲁棒性：同时，遗传算法的种群操作，保留了遗传算法得多出发点的优势，弥 补了禁忌搜索的单一单操作缺乏并行性的弱点。 将遗传禁忌算法引入到范例推理中，用于范例特征项权重的发现。将发现的 权重运用到范例检索中去，以提高检索的质量和速度。同时，将遗传禁忌算法的 思想引入到范例推理的结构中，提出一种基于遗传禁忌算法的范例推理模型。使 得算法过程已经不是简单的范例检索过程，而是一个利用修正知识库、修正规则 学习的过程。通过自身的学习，来找到一个与之最相似的范例。 最后将基于遗传禁忌算法范例推理的思想，应用于银行客户信用评估系统 中，详细介绍了银行客户信用评估的功能模块、体系结构、范例的表示、相似性 计算方法的确定，范例检索方法的确定 关键词：遗传算法，禁忌搜索算法，范例推理，权重，银行客户信用评估 安徽人学顾i 学位论文 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 na n s w e r i n g a 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 na r t i f i c i a li n t e l l i g e n c e f 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 mb a s e do nt h ep a s ts u c c e s s f u lo rf a i l e d c a s e s i ti san e wr e a s o n i n gt 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 ew i t hr e a s o n i n g i n r 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 hg e t st h em o s t s i m i l 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 tc a s ea n dg e t st h ea n s w e r s b 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 dr e a s o n i n gi sn o to n l ya b o u th u m a n c 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 ow 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 e i n t e l l i g e n tc o m p u t e rs y s t e mt 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 y d i f f e r e n tf i e l d s ，e s p e c i a l l yi 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 e e x p e r t s k n o w l e d g e b u tt h e r ea l es o m ep r o b l e m si nc a s e - b a s e dr e a s o n i n ga sw e l l ，m a i n l y e m b o d i e si nc a s e b a s e dp r o j e c ta u t o m a t i o n ，t h a ti sa u t o m a t i cp r o d u c t i o no fc a s e k n o w l e d g e ，s u c ha sc a s es t r u c t u r ea n di t sc o n t e n t s ，s i m i l a re v a l u a t i o nk n o w l e d g e ， a u t o m a t i cu p d a t i n go fc a s e b a s e ，a c h i e v e m e n to fa m e n d m e n tk n o w l e d g ed a t a b a s e ， i n d e xp a t t e r ne t c b u tt h e r ea r ea l s os o m ec h o k ep o i n tp r o b l e m si n a t t a i n i n gt h i s k n o w l e d g ew h i c hi sa c c u m u l a t e ds l o w l yb ye x p e r t si ns p e c i f i e df i e l d sa n dk n o w l e d g e e n g i n e e r s 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 i l a rc a s ef r o m c 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 dr e a s o n i n gs y s t e m t h es i m i l a r i t yb e t w e e nc a s e si st h ek e y t h ef e a t u r ew e i g h to fc a s ep l a y sa l li m p o r t a n t r o l ei nc h e c k i n gq u a l i t ya n ds p e e do fi n d e x e x t r a c tf o rf e a t u r ew e i g h to fe a s e b a s ei s a l s ot od i s c o v e rt h a td i f f e r e n tc h a r a c t e r so fc a s eh a v ed i f f e r e n ti m p o r t a n c e g e n e r i ca l g o r i t h mi sap a r a l l e lh i g h l y ，o r g a n i c a l l yi t s e l f , a d a p ti t s e l fs e a r c h i n g a l g o r i t h mr e f e r r i n gt om e c h a n i s mo fn a t u r es e l e c t i o na n dn a t u r ei n h e r i t a n c ei nb i o l o g y f i e l d b e c a u s eo fi t st w op r o m i n e n tf e a t u r e sw h i c ha r ec o n n o t a t i v ep a r a l l e la n d c o n v e r g e n tg l o b a l i t y ，g e n e r i ca l g o r i t h mi st y p i c a l l ys u i t a b l et op r o c e s sc o m p l e x i 宜徽人学坝i 。学位论文 毕十遗传禁忌算往的把例_ f f 卜理的耐f 究 p r o b l e m sw h i c ha r ed i f f i c u l tt op r o c e s sb yt r a d i t i o n a ls e a r c hm e t h o d s t a b us e a r c h i n g a l g o r i t h mi sal o c a ls e a r c ha m e n d m e n ta l g o r i t h mb ys i m u l a t i n gt h ef e a t u r et h a t h u m a n i t yh a sm e m o r yt of i n dt h eb e s t n a m e l y ，h u m a n i t ya l w a y sw o n ts e a r c hp l a c e s t h a th a v eb e c ns e a r c h e dt e m p o r a r i l y ，a n dw i l ls e a r c hp l a c e st h a th a v en e v e rb e e n s e a r c h e d i f t h e r ei sn os u i t a b l ea n s w e r , b a c kt op l a c e st h a th a v eb e e ns e a r c h e d t a b u s e a r c h i n ga l g o r i t h ma v o i d sr e p e a t e da n dc i r c u i t o u ss e a r c hb ys e a r c hr u l ef o rl o c a l n e i g h b o f i n gf i e l d sa n dc o r r e s p o n d i n gt a b ur u l e s ，r e l e a s es o m ee x c e l l e n ti n d i v i d u a l s i nt a b ub ya s p i r a t i o nc r i t e r i aa n de n s u r e sv a r i o u s l ye f f e c t i v es e a r c ht or e a l i z eg l o b a l u t i l i z a t i o nf i n a l l y g e n e t i c - t a b us e a r c hc o m b i n e st h er a n d o ms e a r c h i n ga b i l i t ya n dp a r a l l e lo f g e n e t i ca l g o r i t h mw i t ht h em e m o r yf u n c t i o no f t a b ua l g o r i t h m , a n ds o l v e sp r o b l e m s o f g e n e t i ca l g o r i t h ms u c ha sb a dg r a d ea b i l i t y 、p r e - m a t u r i t ye f f e c t i v e l y t h i sa l g o r i t h mi n t r o d u c e st h ed i v e r s i f i c a t i o no ft a b us e a r c h i n gi n t ot h ec r o s s a r i t h m e t i co p e r a t o r sa n dt h ev a r i a t i o na r i t h m e t i co p e r a t o r so fg e n e r i ca l g o r i t h mt o c r e a t et a b uc r o s sa r i t h m e t i co p e r a t o r sa n dt a b uv a r i a t i o na r i t h m e t i co p e r a t o r sw h i c h m a k e st h ea l g o r i t h mh a sm e m o r yi nt h e p r o c e s so fs e a r c h i n g g e n e r i c - t a b u a l g o r i t h ma v o i d sp r e m a t u r i t yp r o b l e m ，e n h a n c e st h ec o n v e r g e n c es p e e da n d u t i l i z a t i o nq u a l i t ya n di m p r o v et h eu t i l i z a t i o np e r f o r m a n c ea n dr o b u s t n e s so f g e n e r i c a l g o r i t h m m e a n w h i l e ，t h ec a t e g o r yo p e r a t i o n so fg e n e r i ca l g o r i t h mk e e p t h e a d v a n t a g e so fm u l t i - o r i g i no fg e n e r i ca l g o r i t h r oa n da m e n dt h ew e a kp o i n to ft a b u s e a r c h i n gw h i c hi st h el a c ko f p a r a l l e lf o rs i n g l e s i n g l eo p e r a t i o n i th a sb 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 a m et i m e ，i d e ao f g e n e t i c - t a b ua 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 gs u u c t u 把a n dp r o m o t e s ac 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 fg e n e t i c - t a b ua l g o r i t h m i tm a k e s a l g o r i t h mp r o c e s s i s n ts i m p l e p r o c e s so fc a s ei n d e x i n g , b u tap l 脚t a k i n g a d v a n t a g eo f k n o w l e d g eb a s ea n da m e n d m e n tr u l e st ol e a r n b yl e a r n i n gi t s e l f , am o s t s i m i l a rc a s ei sf o u n d i nt h ee n dt h ei d e aw h i c hb a s e so nt h ec a s e - b a s e dr 咄o n i n go fg e n e r i c - t a b u a l g o r i t h mi sa p p l i e di n t ob a n kc u s t o m e rc r e d i te v a l u a t i o ns y s t e m t h ef u n c t i o n i v ，立徽人学碘i 学位论文 m o d u l e s ，w o r k f l o w , s y s t e ma r c h i t e c t u r e ，c a s ed e s c r i p t i o n ，t h em e t h o do fs i m i l a r e v a l u a t i o na n dt h em e t h o do fc a s oc h e c k i n ga r ci n t r o d u c e di nd e t a i l k e yw o r d s ：g e n e t i c a l g o r i t h m ，t a b us e a r c h ，c a s e b a s e dr e a s o n i n g ，w e i g h t ，b a n k c u s t o m e rc r e d i te v a l u a t i o n v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，狳了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得筏饺大学或其他教育机构 的学位或证书而使用过的材料。与我一掏工作的同志对本研究所做的任何贡献均 已在论文中作了明确曲说明并表示谢意。 学位论文作者签名：王救前 签字日期： 2 0 0 年s 月客日 学位论文版权使用授权书 本学位论文作者完全了解撒失辱案关保留、使用学位论文曲规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阋。本人授权珐锯六射以将学位论文的全都或部分内容编入有关数据库进行 检索，覃| ；之采用影帮、缩印或扫描等复期手段保存、嚣缡学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：王救舒 导师签名：f 宪名许 茶字甚辩：嬲簪5 - 月g 日 签字目襄：励6 年，月矿嚣 学位论文作者毕业去向： 工作单位： 电话： 遵讯地垃：邮绽： 耍徽人学硕i 学位论文第一章口i 鲁 第一章引言 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 c l i p s e 等。 随着对c b r 的研究兴趣逐渐增大，1 9 9 5 年1 0 月在葡萄牙召丌了第一界c b r 国际会议。我国在c b r 方面的研究与发展起步较晚，非常成型的产品尚不多见。 目前，人们对c b r 的研究和应用，已经深入到热门的电子商务、w w 及信息服务、 规划、设计、诊断、分类、辅助决策、音乐、软件复用、辩论和法律案例推理、 医学、争端调节以及智能教学等领域。 经过二十年的深入研究，人们基本上对c b r 有了一个明确的了解，下面是 c b r 中被研究最多的几类问题。 ( 1 ) 范例的表达 实践中的范例是各种各样的，如何有效地表示范例以便于推理及贮存， 是c b r 首先遇到的问题，近二十年的研究，提出了许多种范例表达的方法 ( 2 ) 范例的索引 c b r 系统的效率很大程度上决定于快速准确地从范例库中检索出合适范 例的能力，为此必须对范例库中的范例进行适当的组织及索引索引的方法 l 安徽人学碗i 。学位论立草f 遗传禁忌算法的范例摊理的研究 也多种多样 ( 3 ) 范例的检索 检索就是依据索引对范例库检索出候选的范例来，其方法与索引一一对 应有相应的算法。 ( 4 ) 范例的修j 下 范例的检索找到了与输入范例最类似的范例，即检索出的范例应满足大 部分输入的要求。修j 下则是将范例由满足大部分输入的要求修改成满足所有 输入要求的范例。由于修诈同具体问题领域知识有关，因此没有统一的办法， 往往要和领域专家合作。 c b r 的发展趋势可以概括为以下几个主要方面：与其它学习方法的集成；与 其它推理方法的集成；被融合进大规模并行处理；通过认知科学的新进展带动 c b r 方法的进步；用c b r 方法进行知识管理 1 2 遗传算法的发展历史与现状 2 0 世纪5 0 年代和6 0 年代，就有计算机学者开始研究。人工进化系统”，将 进化的思想发展成为许多工程问题的优化工具。早期的研究形成了遗传算法的雏 形，大多数系统都遵循“适者生存”的仿自然法则。 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 d a 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 l l a n d 的模式定理和他自己细致的计算结果 成功地结合在一起，在此基础上给出了至今仍广泛应用的著名的d ej o n g 五函数 测试平台可以认为，d ej o n g 的研究工作为g a 算法及其应用打下了坚实的基 础，他的研究成果是g 算法发展史上的罩程碑 自8 0 年代中期以来，是遗传算法的蓬勃发展期，研究者对遗传算法的应用 研究不断扩大和深入有用于t s p 问题“一，调度问题m 、键盘构造问题、多关 节机械手轨迹规划问题、工程中的设计辅助问题、机器学习问题旧、囚徒困境问 2 虫徽人学硕f 。学位论文第一乖弓i 亩 题、模式分类问题，神经网的基因综合，神经网的辅助设计、程序自动生成一遗 传编码旧。此外，遗传算法还在预测控制等问题中都有运用研究。目前g a 的研 究己构成与神经网络，模糊控制并驾齐驱的一大领域。 由于遗传算法思想独特、通用性强、实现简单，给研究者们留下了广阔的探 索空间。它是一个多学科结合与渗透的产物，已经发展成一种自组织、自适应的 综合技术，广泛应用在计算机科学、工程技术和社会科学等领域。目前遗传算法 的研究工作主要集中在以下几个方面： 1 遗传算法的基础理论 遗传算法自创建以来，在各个领域广泛应用，但它的理论基础却相当薄弱。 包括进一步发展遗传算法的数学基础，从理论和试验研究它们的计算复杂性。在 遗传算法中，群体规模和遗传算子的控制参数的选取非常困难，但它们又是必不 可少的试验参数在这方面，已有一些具有指导性的试验结果遗传算法还有一 个过早收敛的问题，怎样阻止过早收敛也是人们正在研究的问题之一 2 分布并行遗传算法 遗传算法在操作上具有高度的并行性，因为其群体操作，所以本质上具有很 好的并行分布处理特性。尤其是算法中各个体的适应度值计算可独立进行而彼此 间无需任何通信，所以并行处理效率很高。但是，标准的遗传算法除适应度计算 外，几乎所有的遗传操作都建立在全局统计处理的基础上，这意味着在整个进化 过程中，这种全局统计处理所引起的通信丌销依然是不可忽视的。许多研究人员 都在探索在并行机和分布式系统上高效执行遗传算法的策略。对分布并行遗传算 法的研究表明，只要通过保持多个群体和恰当控制群体间的相互作用来模拟并行 执行过程，即使不使用并行计算机，也能提高算法的执行效率 3 分类系统 分类系统属于基于遗传算法的机器学习中的一类，包括一个简单的基于串规 则的并行生成子系统、规则评价子系统和遗传算法子系统分类系统被人们越来 越多地应用在科学，工程和经济领域中，是目前遗传算法研究中一个十分活跃的 领域。 4 遗传神经网络 包括连接权、网络结构和学习规则的进化遗传算法与神经网络相结合，正 安徽人学颂l 学位论文肇f 遗传禁忌算法的范倒推理的研究 成功地用于从时问序列分析来进行财政预算。在这些系统中，训练信号是模糊的。 数掘是有噪声的，般很难币确给出每个执行的定量评价。如果采用遗传算法来 学习，就能克服这些困难，显著提高系统性能。m u b l e n b e i n 分析了多层感知机网络 的局限性并猜想下一代神经网络将是遗传神经网络。 5 进化算法 模拟自然进化过程可以产生鲁棒的计算机算法一进化算法。遗传算法是其三 种典型的算法之一，其余两种算法是进化规划( e v o l u t i o n a r yp r o g r a m m i n g ，e p ) 和进化策略( e v o l u ti on a r ys t r a t e g i e s ，e s ) 。这三种算法是彼此独立地发展起 来的。进化规划最早由美国的l j f o g e l 、a j o w e n s 和m j w a l s h 提出：进化策 略则由德国的i r e c h e n b e r g 和h p s c h w e f e l 建立 1 3 禁忌搜索算法的发展历史与现状 f r e dg l o v e r 教授于1 9 8 6 年首次提出了禁忌搜索( t a b us e a r c h ，t s ) 算法 的概念。接着，1 9 8 9 年和1 9 9 0 年。6 1 0 v e r 分别发表了两篇文章胁删系统地阐述 了禁忌搜索算法的概念、基本结构和流程1 9 9 3 年和1 9 9 4 年，6 1 0 v e r 又发表了 两篇文章“枷介绍了禁忌搜索算法的性能以及一些理论结果此后，禁忌搜索算 法丌始逐渐地被人们认识和接受，并在一些应用领域上崭露头角，它在优化组合 中的应用领域非常广阔，在旅行商( t s p ) 问题、图节点着色等问题”1 都有出色的 表现。自从h u r i n kj 于1 9 9 4 年将禁忌搜索应用于j o b - s h o p 问题后m ，禁忌搜 索算法在调度领域获得了蓬勃的发展。直到今天调度问题仍是禁忌搜索算法应用 最广泛而成功的一个领域。此外，禁忌搜索还被应用到图分区、频带分配、o - l 背包问题、时| 日j 表设计、电力系统设计与调度、聚类问题、卫星通讯、计算机结 构设计、光学工程等领域。目前禁忌搜索算法仍然处于发展之中。而且其应用领 域大有拓宽的趋势。 目i ；i 禁忌搜索算法的研究工作主要集中在以下几个方面； ( 1 ) 算法理论研究 算法的全局收敛性研究是算法理论研究的重要方面虽然取得了一些成果， 但是远不及遗传算法和模拟退火算法那样完善如g l o v e r 等阱得到了基于最近 记忆或频率记忆禁忌搜索的一些结果；f a i g l e 等“”得到了概率型禁忌搜索的一 安徽人学颀l 。学位论文第一章引言 些结果。原因主要是禁忌搜索算法只是一个框架性的思想，没有确定的、具体的 数学模型，难以进行准确的数学分析。 ( 2 ) 算法设计的研究 算法设计的研究主要是算法参数的设胃和算法操作上的研究，这些都是直 接影响算法性能和效率的关键。由于参数空间的庞大和各参数之间的相关性，目 前还没有确定最优参数的一般方法。影响禁忌搜索算法性能的参数主要有禁忌表 大小、邻域结构、期望标准和禁忌准则的设置等。算法操作研究得最多的是邻域 结构和禁忌表结构。如孙元凯等”提出了一种变邻域结构的t s 算法：g l o v e r 等 “”提出了自适应记忆的禁忌搜索算法；j 6 z e f o w s k a 等“”，p 6 r e z 等“”研究了各种 禁忌表结构的影响：s a l h i l m l 研究了禁忌表长度及特赦规则的影响 ( 4 ) 混合算法的研究 为提高优化性能和效率，很多算法都会结合其他启发式算法，互相取长补 短，以达到优化的目的。禁忌搜索算法通常是和遗传算法、模拟退火算法相结合 居多“删经过研究表明，混合算法对算法性能和效率有较大幅度的改善 ( 4 ) 算法应用的研究 由于禁忌搜索算法具有很强的通用性，因此其应用领域非常广泛目前主 要的应用领域有：生产调度，这是禁忌搜索算法应用最为广泛，也最为成功的领 域。包括f l o w s h o p 和j o b - s h o p 等问题的求解9 “；组合优化，如t s p 的求解” ”，o - 1 背包问题的求解“”等；神经网络设计，主要是将t s 作为前向神经网络的 学习算法，如s e x t o n 等n 妇、y a m a z a k i 等吲b a t t i t i 等嘲1 1 4 本文的内容与安排 在本文中，我们重点研究了遗传禁忌算法在范例推理系统( c b r ) 中的应用 全文共分六章，下面是本文的组织及各章的主要内容： 第一章是引言。首先对范例推理、遗传算法、禁忌搜索算法的发展历史和研 究现状进行了综述，提出了本文的研究方向，之后概述了本文各章的研究内容 第二章是范例推理的基本原理首先简要介绍了范例推理的提出的发展状 况、范例推理基本原理以及结构，范例推理系统的特点一些相关的基本概念之 后对范例推理中的关键技术作了深入的研究和探讨 5 安徽人学硕i 学位论文幕十遗传禁忌算法的范例推理的研究 第三章是遗传禁忌算法。首先简要介绍了遗传算法的一些基本概念、工作过 程、以及其优缺点，然后介绍了禁忌搜索算法的基本思想、算法流程、以及其特 点。最后将禁忌搜索算法引入遗传算法中，优化其交叉和变异两个算子。 第四章是遗传禁忌算法在范例推理中的应用研究。首先在前面两章的基础 上，研究和探讨了将遗传禁忌算法应用到范例权重发现和范例检索中，并给出了 实验实例。实验结果证明了该算法能够有效地提高范例推理系统的性能，最后给 出了一个基于遗传禁忌算法的范例推理的模型。 第血章研究了基于g a t a b u 与c b r 的银行客户信用评估技术，介绍了银 行客户信用评估的功能模块、体系结构、范例的表示、相似性计算方法的确定、 范例检索方法的确定。 第六章是总结与展望对全文主要的研究工作做了总结，并对今后的研究方 向作了进一步的展望。 6 安徽人学硕l 。学位论立第一二章托例推理 第二章范例推理 2 1c b r 的提出及发展概况 最早描述了c b r 的研究工作的是，r o g e rs c h a n k 在1 9 8 2 年出版的( d y 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 g a 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 年代初也见到了 这方面的研究与应用。例如北方交大的f 日盛丰、张清等人将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 是一种类比推理方法，是由目标范例的提示而得到历史记忆 中的源范例，斥山源范例来指导目标范例求解的一种策略，它是一种重要的机器 7 安徽人学顾i 学位论文苹卡遗传禁忌算泣的范例= f f 理的研究 学习方法。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 中，把当前面l 临的问题或情况称为目标 范例，而把记忆中的问题或情况称为源范例对于范例推理，一个通俗的解释是： 为了找到一个实际新问题的解，首先在经验库中寻找相似的问题，从过去的相似 问题中取出解，并把它作为求解实际问题解的起点，通过适应性修改而获得新问 题的解 范例推理的基本思想是：基于人们在问题求解中习惯于过去处理类似问题的 经验和获取的知识，再针对新旧情况的差异做相应的调整，从而得到新问题的解 并形成新的范例一般地，范例推理具有如下步骤( 如图2 1 ) 姗 图2 1c b r 的工作过程 ( 1 ) 范例库( c a s eb a s e ) ：范例库是用来存储过去范例的存储空间，包含成 功及失败的范例，每一种范例都以一定的表示方式存放在范例库中，这种表示形 式必须包含范例的主要因素，环境条件及范例的基本特征与主要参数值，但范例 的表示没有统一的方式与方法，主要根掘问题的类型具体分析确定 ( 2 ) 检索( r e t r i e v e ) ：依据输入待解决的问题的有关信息，检索出范例库中 8 安徽人学坝f 学位论文第一二章范例 f f 理 同新问题最近似的范例常用的有相联法、层次法及基于知识法，f u z z y 检索等。 ( 3 ) 重用( r e u s e ) ：从检索到的一组范例中获得求解方案，判别是否符合需 求，若符合，则重用这些方案( 或多个方案的合并解) ，否则需要修诈： ( 4 ) 修币( r e v is e ) ：范例的检索得到与新问题最匹配的范例，范例的修诈就 是将恢范例由满足大部分输入的要求修正成满足所有输入的范例。由于范例的修 j 下与具体问题邻域有关，难以规定统一的方法。 ( 5 ) 保存( r e t a i n ) ：是扩充和更新范例库的一种手段，以确保所建立的c b r 系统长期有效、可靠地应用。它根掘所给问题的条件通过修币所得到的成功的或 失败的范例根据一定的策略进行加工，然后存入范例库中。这是c b r 的学习方式 2 3c b r 系统的特点 人类求解问题的方法需要鲁棒性，我们常常以有限的、不确定的知识解决困 难问题，并且随着经验的增长，处理问题的能力不断地增强这也是应用于现实 世界问题领域的人工智能系统所需要的性质。复用以前经验的方法是人类专家的 一种基本而重要的解决问题的方法m 传统的基于知识系统( 主要指知识表示采用产生式规则或框架的专家系统) 存在一定的困难，例如： ( 1 ) 知识获耿的瓶颈问题：随着大型专家系统的出现，知识获取的瓶颈问题将 越来越严重，一定程度上影响了传统基于知识系统的应用发展； ( 2 ) 固定的求解范围：专家系统仅仅能求解知识库所覆盖的问题； ( 3 ) 推理链不能太长：为了保证不确定性推理的有效性，专家系统的推理链不 能太长，因而传统的基于知识系统不适于解决推理链过长的复杂问题； ( 4 ) 知识库维护的困难：假定知识表示采用产生式规则。由于知识库中的规则 之间并不具有完全的独立性，知识库的增长并非单调的，新旧规则之间可能会存 在冲突，所以知识库的维护仍然十分困难； ( 5 ) 问题推理的重复性：传统的基于知识的系统遇到其以前求解过的问题时， 就如同没有遇到过一样，它照旧要重复完成全部推理过程； ( 6 ) 在一些领域，人类专家还不能提供问题求解的规则，在这样的领域无法建 立基于规则的专家系统 j 立徼大学碗i 擘位论文 甚于遗传禁忌算法的抱例推理的研究 c b r 方法在以下方面做出了改进： ( 1 ) 知识获取 c b r 系统使用的主要知识是范例，而范例的获取要比规则获取容易得多。 c b r 不需要特化和泛化经验以形成规则。在一些应用领域，存在着天然的范 例，例如医院中的病历。这些领域中，范例获取的代价非常低对于提取范 例有困难的应用领域，c b r 系统的建立需要通过“范例工程( c a s e e n g i n e e r i n g ) ”来确定范例所必须包含的信息，定义信息的表示方法以及从可 提供的数掘中抽取信息，从而进