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

东北大学硕士学位论文摘要 遗传算法在基于事例推理中的应用研究 摘要 基于事例推理( c a s e - b a s e dr e a s o n i n g ，c b 鼬作为基于知识的专家系统( e x p e r t s y s t e m ) 的一个分支，它是目前人工智能( a r t i f i c i a li n t e l l i g e n c e ) 研究中一种正在迅速发 展的推理方法。 遗传算法是用计算机来模拟生物进化思想的一种优化算法。美国m i c 挝g a n 大学的 h o l l a n d 教授于1 9 7 5 年首次提出遗传算法。遗传算法是在固定的种群规模下，利用个体 适应度来引导搜索，通过按一定概率进行的选择、杂交和变异等遗传操作来完成群体的 更新，因而它实际上是一种“盲目的概率启发搜索策略”。由于它简单，鲁棒性强，易 于并行化，已经在各个领域得到了广泛的应用。 本文首先介绍了c b r 和遗传算法的基本概念和原理，然后结合本文的应用背景， 具体的阐述了c b r 系统的核心环节：事例表示和存储、事例检索和匹配、事例的修改 和学习、事例库维护。 将遗传算法应用到c b r 系统，使用改进的遗传算法，对事例库中的特征权重向量 进行优化；对于给定的目标事例，如何从事例库率检索和选择出最为相似的事例决定了 基于事例推理系统的学习与推理性能。事例间的相似性度量是检索的关键，其中事例的 特征项权重对检索的质量与速度都起到了重要的作用，因为本质的相似比表象的相似更 重要，即通过对特征项赋权重来体现事例的不同的特征具有不同的重要性。在事例的表 示中采用了面向对象的方法，有效的解决了知识表达的问题；在事例检索中，采用了最 近相邻方法。最后，通过系统运行测试验证了上述方法的有效性和实用性。 关键词：事例推理；专家系统；遗传算法；事例检索；特征权重向量 i i 东北大学硕士学位论文 a b s l r a e t t h er e s e a r c ho fg e n e t i ca l g o r i t h m sa n di t s a p p l i c a t i o ni nc a s e b a s e dr e a s o n i n g a b s t r a c t c a s e - b a s er e a s o n i n g ( c 3 r ) ，ab r a n c ho f k n o w t e d g e - b a s e de x p e r ts y s t e m , i sar a p i d l y g r o w i n gr e a s o n i n gm e t h o di nt h er e s e a r c ho f a r t i f i c i a li n t e l l i g e n c e ( a d g e n e t i ca i g o r i t h m ( g a ) i so n eo fo p t i m i z a t i o na l g o r i t h m si m i t a t i n gb i o l o g i c a le v o l u t i o n w i t hc o m p u t e r s i tw a sf i r s tp u tf o r w a r db yh o l l a n di nu n i v e r s i t yo f m i c h i g a ni n1 9 7 5 w i t h t h e 丘x e dp o p u l a t i o ns i z e , g ao n l yb s ef i t n e s sv a l u et og u i d es e a r c h i n ga n dr e g e n e r a t e p o p u l a t i o nt h r o u g he x e c u t i n gg e n e t i co p e r a t i o n ss u c ha s l e c t i o r lc r o s s o v e ra n dm u t a t i o n w i t hp r o b a b i l i t y t h u st h eg ai si nf a c ta b l i n dh e u r i s t i cs e a r c h i n gs t r a t e g yw i t h p r o b a b i l i t i e s “b e c a u s eo f i t ss i m p l i c i t y , f l e x i b i l i t y , a n db e i n gp r o n et op a r a l l e lc o m p u t i n g , i t h a sb e e n w i d e l yu s e di nv a r i o u sf i e l d s t h i st h e s i sb e g i n sw i t hab f i e fi n t m d u c f i o nt ot h ec o n c e p t i o na n dt h e o r yo fc a s e b a s e d r e a s o n i n ga n dg e n e t i ca l g o r i t h m t h e na c c o r d i n gt ot h ea p p h e df i e l d s ，t h et h e s i sd e t a i l e d d i s c u s st h ek e yp a r t so fc b rs y s t e m ：e a s er e p r e s e n t a t i o na n ds t o r a g e ，c a s er e t r i e v a la n d m a t c h i n g , c a s ea d a p t a t i o na n ds t u d y , c a s eb a s em a i n t e n a n c e t h et h e s i si m p o r t sg e n e t i ca l g o r i t h mi n t oc a s e b a s e dr e a s o n i n gs y s t e m ，b yi m p r o v e d g e n e t i ca l g o r i t h m , a n do p t i m i z e st h ew e i g h to f f e a t u r e s ，a st ot h ec c n a i l lc a s e , h o wt or e t r i e v e a n ds e l e c tt h em o s ts i m i l a rc a s ef r o mt h ec a s eb a s e sd e t e r m i n et h ec a p a b i l i t yo fl e a r n i n ga n d r e a s o n i n gi nc b rs y s t e m t h em e a s u r c m g n to f s i m i l a r i t ya m o n g c a s e si st h ek e yo f r e t r i e v a l t h ew e i g h to f f e a t u r e si si m p o r t a n tt oq u a l i t ya n ds p e e do f r e t r i e v a lb e c a u s et h es i m i l a r i t yo f e s n c ei sm o l ei m p o r t a n tt h a na p p e a r a n c e , n a m e l yw e i g ht h ef e a t u r e st or e p r e s e n tt h e d i f f e r e n tf e a t u r e sh a v ed i f f e r e n ti m p o r t a n c ei nc a s e t h eo b j e c t - o r i e n t e dm e t h o di su s e di n c a s er e p r e s e n t a t i o n , e f f e c t i v e l yr e s o l v i n gt h ep r o b l e mo f r e p r e s e n t a t i o no f k n o w l e d g e a n dt h e n e a r e s tn e i g h b o rm e t h o di se m p l o y e di nc a s er e t r i e v a l f i n a l l yt h et h e s i sv e r i f i e dt h e u s e f u l n e s sa n de f f e c t i v e n e s so f t h ea b o v em e t h o dt h r o u g hs y s t e mr u n n i n ga n d t e s t i n g k e yw o r d s ：c b r ；e x p e r ts y s t e m ；g e n e t i ca l g o r i t h m ；c a s er e t r i e v a l ；w e i g h to f f e a t u r e s m 一 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的 研究成果除加以标注和致谢的地方外，不包含其他人已经发表或撰写过的 研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示诚挚 的谢意。 学位论文作者签名：徐哥 签字日期! 加7 乃 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名：否则视为不同意) 学位论文作者签名：彳衾舟 钠签名：锨 一堋一乃辨嗍：，如 东北大学硕士学位论文 第l 章绪论 第一章绪论 1 1 人工智能 人工智能( a r t i f i c i a l i n t e l l i g e n c e ，a i ) 是计算机科学、控制论、信息论、神经生理学、 心理学、语言学等多种学科相互渗透而发展起来的一门综合性新学科。其诞生可追溯到 5 0 年代中。1 9 5 6 年在美国d a r t m o u t h 大学举行的夏季学术讨论班上人工智能这一术语 第一次被正式使用，从而开创了人工智能的研究方向。人工智能的研究目标是如何制造 出人造的智能机器或智能系统，来模拟人类智能活动的能力，以延伸人类智能。人工智 能的主要应用领域有：专家系统，自然语言理解，机器入学，数据库的智能检索，博弈， 定理机器证明，自动程序设计，组合调度问题，感知问题等等”】伫】。 1 2 专家系统 在众多的人工智能应用领域中，专家系统是近4 0 年发展起来的一种极富代表性的智 能应用系统。专家系统的目的在于设计一种基于知识的计算机程序系统来模仿人类专家 求解专门问题，从而在相关领域为人们提供具体的帮助和指导。 “专家”是一个在特定领域内具有专门知识( e x p e r t i s e ) 的人，专家具有不为大多 数人所知或所利用的专门技能，并能够解决大多数人所不能解决的问题或者向人们提出 一些建设性的建议等。 专家系统就是存贮在计算机中的专家经验。通常，先由专家系统的开发者把人类专 家从多年经验中积累起来的核心知识存贮到磁盘上，并设计一个具智能特点的计算机程 序。专家系统具有类似人类专家思维的推理能力，并能用这些知识来解决实际问题。 专家系统具有如下一些基本特征： ( 1 ) 具有专家水平的专业知识。一个专家系统为了能够像人类专家一样的工作， 必须具有专家级的知识，知识越多，质量越高，解决闯题的能力就越强。 ( 2 ) 能进行有效的推理。在专家系统中，问题的求解过程是一个思维过程，即推 理的过程，因此专家系统不仅能做一般的逻辑推理，而且能利用问题的启发性信息进行 启发式搜索、试探性推理阻及不精确推理、不完全推理。 ( 3 ) 具有知识获取的能力。专家系统的基础是知识，为了得到知识就必须提供获 取的手段，从而使系统自身具有学习的能力，能从系统运行的实践中不断总结出新的知 东北大学硕士学位论文 第1 章绪论 识，使知识库中的知识越来越丰富、完善，通过自身的知识积累提高解决问题的能力。 ( 4 ) 具有灵活性。在绝大多数专家系统中都采用了知识库与推理机构相分离的构 造原则，彼此相对独立。这就使得知识的更新和扩充比较方便，不会因某一部分的变动 而牵动全局。系统运行时，推理机构可根据具体问题的不同特点选取不同的知识构成求 解序列，具有较强的适应性。 ( 5 ) 具有交互性。专家系统一般是交互式系统，一方面它需要领域专家或知识工 程师对话获取知识，另一方面它也需要与使用它的用户对话以索取证据或回答用户提出 的问题。 目前，专家系统在各个领域中已经得到广泛应用，并取得了可喜的成果，例如个人 理财专家系统、投资风险分析系统、医疗诊断系统等。 1 2 1 专家系统的要素 专家系统通常由人机交互界面、知识库、推理机、解释机、综合数据库、知识获取 机等6 个部分构成。典型的专家系统的组成如图1 1 所示，箭头方向为数据流动的方向。 人机交互界面是用户和专家系统之间的通信机制，是专家系统和用户之间进行交互 通信和信息交换的媒介。专家系统的生命力在于它能同用户一起组成高性能的人机共存 系统，友善的用户界面是这种人机共存系统的重要组成部分。知识库用来存放专家提供 的知识，专家系统的问题求解过程是通过知识库中的知识来模拟专家的思维方式的。因 此，知识库是专家系统质量是否优越的关键所在，即知识库中知识的质量和数量决定着 专家系统的质量水平。一般来说，专家系统中的知识库与专家系统程序是相互独立的， 用户可以通过改变、完善知识库中的知识内容来提高专家系统的性能。推理机主要由调 度程序与解释程序组成，是实施问题求解的核心机构。推理机就如同专家解决问题的思 维方式，知识库就是通过推理机来实现其价值的。 解释机是专家系统中回答用户询问、对自己的问题求解过程或对自己当前的求解状 态提供说明的一个重要机构，也即解释系统的推理给用户。 综合数据库专门用于存储推理过程中所需的原始数据中间结果和最终结论，往往是 作为暂时的存储区。 知识获取机制是专家系统中把问题求解的各种专门知识从人类专家的头脑中或其 他知识那里转换到知识库中来的一个重要机构。通过知识获取，可以扩充和修改知识库 中的内容，也可以实现自动学习功能。 东北大学硕士学位论文 第1 章绪论 专家、知识工程师 用户 人机交互界面 i： ： l 氅龛爹h 解释机 知识获取机 ” i 。 i 推醐 h 知识库 图1 i 专家系统的组成 f i g i ib a s i cs t r u c t u r eo f e x p e r ts y s t e m 1 2 2 专家系统的工作流程 专家系统的基本工作流程是，用户通过人机界面回答系统的提问，推理机将用户输 入的信息与知识库中各个规则的条件进行匹配，并把被匹配规则的结论存放到综合数据 库中。最后，专家系统将得出最终的结论呈现给用户。领域专家或知识工程师通过专门 的软件工具，或编程实现专家系统中知识的获取，不断地充实和完善知识库中的知识。 1 3 本文组织结构 本文探讨了基于事例推理循环的基本过程，并且结合某歌厅分析系统对循环中的各 个核心环节进行了研究。在事例表示中采用了面向对象的方法，有效的解决了知识表达 的问题：在事例检索中，采用了最近相邻方法，在相似度计算中，利用基于模糊判别相 似度计算，确保了系统的检索效率：对于最近相邻相似度计算中的共性问题：特征权值 的优化，提出了一种新颖的基于遗传算法的特征权值优化模块，改善了系统的整体运行 效率及性能。 本文的组织结构如下： 第一章是绪论，概要介绍人工智能与专家系统的相关理论。 第二章是介绍基于事例推理的基本理论和循环的基本过程、基于事例推理的优点以 及遗传算法的工作过程和基本原理。 第三章是本文系统的设计与实现。将遗传算法应用到c b r 中，解决了特征权值优化 的问题，改善系统的性能。 东北大学硕士学位论文 第1 章绪论 第四章是系统的运行测试，并与其他两种权值优化方法进行比较。 第五章是分析系统技术上的有待进一步改进之处，并提出结论与展望。 东北大学硕士学位论文 第2 章基于事例推理和遗传算法综述 第二章基于事例推理和遗传算法综述 2 1c b r 理论与技术 2 1 1c b r 基本原理 基于案例推理是模拟人类类比思维的一种推理方法，其推理过程往往具有人类经验 推理的一些特征【3 】。 c b r 的基本过程是：当遇到一个新的问题时，系统根据关键的特征在原始的案例库 中进行检索，找出一个与待求问题最相近的候选案例，重用此候选案例的解决方法【4 】。 如果对此候选案例的解决方法不满意，可以对它进行修改以适应待求问题，最后把修改 过的案例作为一个新的案例保存在库中，以便下次遇至类似的问题时作为参考。c b r 以 案例作为知识元，知识获取和表示自然直接，并且具有自学习功能，其本质是基于相似 性的类比推理，这正是符合了人类类比思维的逻辑嘲。c b r 有两种类型，即问题求解型 和解释型。问题求解型侧重于对过去策略的匹配与修改，而解释型强调以旧案例对新案 例做出评价与解释。无论哪一种，其推理过程均类似于人类经验类比推理，而且具有简 化知识获取、通过直接获得提高求解效率、求解质量较高、适用于非计算推导的优点 6 l 。 因此，它将是人工智能与专家系统设计的种非常具有发展前景的方法。 2 1 2 知识表示 2 1 2 1 知识表示概述 知识表示与获取是a j 研究的一个大难点。传统的知识表示方式多种多样，各有特 色，也各有局限。比较重要的知识表示方式有：命题谓词符号，产生式规则，框架， 语义网，面向对象的知识表示等等【”。近年发展迅速的神经网络也可以认为是知识表示 方式的一种。 在事例的具体表示方法上，各种各样的知识表示方法都可以应用于事例的表示： 语义网，框架，谓词符号，面向对象等等i s 。随具体系统和应用领域的不同，开发者可 以根据需要选择最合适的事例表示方式。 2 1 2 2 面向对象的知识表示 客观世界中的问题都是由客观世界的事物及事物之间的相互关系构成的。从面向对 东北大学硕士学位论文第2 章基于事例推理和遗传算法综述 象的角度来看，人们在认识问题和分析问题时，可以把问题分解为一些对象( o b j e c t ) 以及对象之间的组合和联系。面向对象中的主要概念有对象、消息、方法、类和类层次。 ( 1 ) 对象、消息和方法。从广义上讲，所谓“对象”是指客观世界中的任何事物， 即任何事物都可以在一定前提下被作为认识的对象。从问题求解角度来讲，对象是与问 题领域有关的客观事物。由于客观事物都具有其自然属性及行为，因此，当把与问题有 关的属性及行为抽取出来加以研究时，相应客观事物就在这些属性与行为的背景下成为 所关心的对象。 在面向对象的知识系统中，一个对象具有的知识组成了该对象的静态属性，一个对 象所具有的知识处理和各种操作描述了该对象的智能行为。按照面向对象方法学的观 点，一个对象的形式定义可以用如下四元组表示： ：= ( d ，d s ，m s ，m i ) 也就是说，一个完整的对象由该对象的标识符d 、数据结构d s 、方法集合m s 和消息接 口m i 组成。对象的标识符i d ( i d e n t i f i e r ) 又称对象名，用以标识一个特定的对象。对象 的数据结构d s ( d a t as t r u c t u r e ) 播述了对象当前的内部状态或具有的静态属性，常用 一组 表示。对象的方法集合m s ( m e t h o ds e t ) 用以说明对象具有的 内部处理方法或操作。接口分为两类，一类用以对内部数据进行操作，从而改变对象的 当前状态；另一类用于产生对外的输出。对象的消息接口m i ( m e s s a g ei n t e r f a c e ) 是对 象接收外部信息和驱动内部有关操作的对外接口。这里的外部信息称为消息。消息接口 以消息模式集的形式给出，每一消息模式有一个消息名，通常还包含必要的参数集。当 接收者从它的消息接口受理发送者的某一消息时，首先要判断该消息属于哪一消息模 式，并找出与消息模式相联系的内部操作，然后执行内部操作，进行相应的消息处理或 产生向外的输出消息 ( 2 ) 类和类的层次。类( c l a s s ) 在概念上是一种抽象机制，它是对一组相似对象 的抽象。具体地说，在一组相似的对象中，会有些相同的特征( 包含部分相同的数据 和操作) ，为了避免相同数据和操作的重复描述及存储，就把共同的部分抽取出来构成 一个类。一个类的上层可以有超类( s u p e r c l a s s ) ，下层可以有子类( s u b c l a s s ) ，从而形 成一重层次结构，称为类层次。超类和予类同样是类，它们可以建立各自的实例。类层 次的一个重要特性是继承性，即一个类可以继承其超类的全部描述，且这种继承具有传 递性，从而，一个类可以继承层次结构中在其之上的所有的类的全部描述。因此属于某 个类的对象除了直接具有该类所描述的特性外，还通过继承具有该类上层所有类描述的 东北大学硕士学位论文第2 章基于事例推理和遗传算法综述 全部特征。 下面给出用面向对象方法表示知识的一种描述形式： c l a s s ：( 超类名 s t r u c t u r e m e t h o d r e s t r a i n t ( 限制条件 e n d c l a s s + 其中，c l a s s 是类描述的开始标志， 是该类的名字，它是系统中该类的唯一 标识。 是可选的，当该类有父类时，用它指出父类的名字。 是一组 变量名构成的序列，该类中所有对象都共享这些变量，对该类对象来说，这些变量是它 们的全局变量。s t r u c t u r e 后面的 用于描述该类对象的数据结构。 m e t h o d 后面的 用于定义该类对象可施行的各种操作。r e s t r a i n t 后 面的 指出该类对象所应满足的限制条件，可用包含类变量的谓词或其他形式 的条件表达式表示。若没有限制条件，则表示没有限制。 一 面向对象表示方法作为人类认识自然和世界的一种新颖的方法与传统的表示方法 具有很大的差别，它具有以下特点： ( 1 ) 封装性。对象就是被封装的数据和操作。每个对象的内部状态不允许其它对 象直接引用和修改。对象的内部状态和方法对外界是隐蔽的。一个对象的外部特性只由 对象的所有消息模式及相应于每个消息模式的处理功能来定义，面向对象表示的封装性 使得用户只需知道对象的外部特性而无需了解其内部细节就可以使用它。 ( 2 ) 模块性。显式地把对象的外部定义和对象的内部实现分开是面向对象表示的 一大特色，这种现象的封装住就是模块性。公开模块的外部定义和隐藏模块的内部实现， 使面向对象的软件系统便于维护和修改。 ( 3 ) 继承性。面向对象表示的继承性使子类可继承父类的数据和操作，从而可以 把每个子类拥有的数据和操作分为两部分，一部分是从父类继承过来的共享数据和操 作，另一部分是子类自己私有的数据和操作。 一1 一 东北大学硕士学位论文 第2 章基于事例推理和遗传算法综述 在面向对象的程序设计中，程序设计就是定义对象并建立对象间的通信关系，类是 系统的基本构件。如果开发设计的面向对象系统的功能需求发生变化，通常较少波及到 对象类的设计与实现，更多的是影响到它们的组装形式，因此，实现的系统基本构件无 需修改或少量修改后仍可使用，从而可采用快速原型法构造系统，以及对系统进行优化 和增量开发。 2 1 3c b r 的工作过程及相关技术 一个典型的c b r h 题求解过程的基本步骤可以归纳为r 4 ：案例检索( r e t r i e v e ) 、案 例重用( r c u s e ) 、案例修改( r e v i s e ) 和案例保留( r e t a i n ) 【9 】。其工作过程如图2 1 所示。 图2 1 基于事例推理的过程 f i g 2 1t h ep r o c e s so f c a - b a s e dr e a s o n i n g 2 1 3 1 案例表示与组织 案例的表示方式决定着现实世界问题向案例的转换，同时对案例推理的效率有很大 的影响。一个合格的案例表示至少应该包括两部分：问题的说明信息，即问题的初始条 件；问题求解目标，即达到该目标的解决方法。在案例表示中也有图片、声音、影像等。 根据不同的问题，案例的表示般有不同的方法，但大体可以分为两种思路：动态存储 模式和类别样本模式。所谓动态存储模式就是通过一种通用的案例结构来组织具有共同 特征的案例，再用它们的不同点作为索引把不同的案例区分开【姗。分类样本模式中的案 例处于分类、特征、案例所组成的网状结构中，它包含三种指针：特征指针，从不同特 征指向分类；案例指针，从分类指向案例；差异指针，从一个案例指向差异最小的另一 个案例。案例恰当的表示与合理组织能够反映事物的本质特征，案例检索系统就能够迅 速的从案例库中检索出所要的案例，从而使效率提高。 东北大学硕士学位论文 第2 章基于事例推理和遗传算法综述 2 1 3 2 案例检索与匹配 案例知识的检索与匹配是实现案例推理的关键，也是目前c b r 的一个研究热点。案 例检索最终要达到以下两个目标：检索出来的案例应该尽可能的少；检索出来的案例应 尽可能的与当前案例( 目标案例) 相关或相似或匹配【1 。案例检索与一般检索( 如w e b 搜 索、数据库检索) 有很大区别的，这种检索是在特定的案例中查找类似的历史经验，因 此它有自己的特点：带有一定的不精确性或模糊性；为从各个角度去比较案例之间的相 似性、衡量案例间的相似性，或者确定一个案例的比较标准，学者们提出了相似度、差 异度、模糊贴近度等概念，并针对这些概念提出了许多算法 1 2 】。从检索策略的角度来说， 目前c b r 的案例知识检索主要有最近相邻策略、归纳推理策略、知识引导策略、模板检 索策略等，并且最近相邻策略和归纳推理策略是较为通用的检索方法。 2 1 3 3 案例重用 案例的重用就是用解决旧案例的经验来解决新的问题。案例重用包括思路重用和过 程重用 1 ”。所谓思路重用就是重新应用旧案例中解决问题的方法到新案例中。所谓过程 重用是重新应用整个解决问题的过程，包括思路和具体的实施细节。 2 1 3 4 案例修改和保留 案例修改是指解决方案的评估和错误的修正。一般地，在c b r q b 有两种案例修改方 法：结构修改和诱导修改。结构修改就是直接应用规则或公式修改所存储的相似案倒( 候 选案例) 的结论以适应新的问题【1 4 】。诱导修改就是重用得出以前案例结果的规则或公式。 采用诱导修改需要另外存储如何得出案例结论的步骤和知识，以便改写时应用。系统对 案例修改分为两步进行：首先分析新问题的要求与候选案例之间的不同，再以候选案例 为基础进行修改i ”】。可以对某一候选案例进行修改，也可以对多个候选案例进行重组和 修改。修改后的案例经过验证，如果是可行的或正确的，就可作为新的案例存储到案例 库中。这样，随着新案例的加入，就标志着系统进行了一次知识获取，即完成了一次学 习过程。这种自学习功能最能体现c b r 的优势和生命力。 2 1 3 5 系统维护 一系统维护主要是对案例库的维护。案例库的维护分为案例的增加、删除、完善等方 面。为了保证案例检索的速度，在保持案例典型性的前提下，需要不断减少案例的冗余， 但这在实际中往往与案例库丰富相矛盾【1 6 1 。所以一般应根据c b r 系统的应用领域来决定 - 9 - 东北大学硕士学位论文 第2 章基于事铡推理和遗传算法综述 案例数量范围。例如，在c a s s i o p e e 系统中，案例库中就包括2 3 0 0 0 个案例，而且案例 越多越好。但根据研究结果表明，对于c b r 在农业中应用( 如病虫害诊断、预测) ，案例 就特别要求其具有典型性。这是因为农业领域的许多知识比较粗糙，案例过多必然会产 生大量重叠，势必要影响系统检索速率。 2 1 4c 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 的一些缺点。首先，基于规则推理过程中的知识获取是一个瓶颈。它需要 领域专家把自己的知识经验告诉知识工程师，然后由知识工程师将其抽取、转化、编写 成规则形式，存储于知识库。这个过程往往费时费力，十分繁琐困难。而c b r 的知识获 取仅是简单的获取过去的案例。其次，r b r 中的规则一旦确定，如果需要增加或修改其 中的一点或一条，则牵扯到整个规则库。而c b r 的知识库储存的是一个一个案例，修改 其中的某一案例不会影响其他内容。也就是c b r 的知识库维护十分简单。再则，c b r f l 够在解决新问题的同时，保存新案例到案例库中来实现自学习的功能。经过一段时间的 使用，系统的准确性会得到提高。这是c b r 系统最突出的优点。而r b r 则没有这个功能， 它必须借助于领域专家和知识工程师的合作。最后，c b r 系统中案例的表示简单明了， 直观性强。 2 ，2 遗传算法简介 h o l l a n d 认为，遗传算法本质上是适应算法，应用最多的是系统最优化的研究。他 认为现实世界中，许多复杂问题的解都可以用二进制位串编码来表示，并且通过一些简 单的变换算子就可以逐步改进这些用二进制位串编码表示的结构，使之向好的方向“进 化” 1 7 1 。其中，。位串编码”对应遗传学中的染色体，“变换算子”相当于染色体之间的 交叉和变异。 遗传算法是从代表问题一个潜在解集的一个种群( p o p u l a t i o n ) 开始的，而一个种群 是由经过基因编码的一定数目的个体组成。每个个体是染色体带有特征的实体。染色体 作为遗传物质的主要载体，其内部表现( 即基因型) 是某种基因组合，它决定了个体的外 部表现，如黄皮肤的特征是由染色体中控制这一特征的某种基因组合决定的。在执行遗 传算法时，必须包含两个数据转换的过程，一个是从表现型到基因型的转换，另一个是 从基因型到表现型的转换1 8 】。前者又称为编码( c o d i n g ) 操作，是把搜索空闻的解或参数 转换成遗传空间的染色体或个体；后者又称为译码( d e c o d i n g ) 操作，是与前者相反的操 东北大学硕士学位论文 第2 章基于事例推理和遗传算法综述 作i 嘲。 初始种群产生之后，按照适者生存的和优胜劣汰的原理，逐代演化产生出越来越好 的近似解。在每一代，根据问题域中个体的适应度大小挑选个体，并借助于自然遗传学 的遗传算子进行组合交叉和变异，产生出代表新解集的种群 2 0 1 。此过程将导致后生代种 群比前代更加适应于环境，末代种群中的最优个体经过解码可以作为问题的近似最优 解。 2 2 1g a 的工作过程 g a 作为一种借鉴生物界自然选择和自然遗传机制的高度并行、随机、自适应的搜 索算法，由于其隐含并行性和收敛的全局性两大显著特点，使它尤其适于处理传统搜索 方法所难于解决的复杂问题【2 1 1 。 图2 2 是s a a ( 简单遗传算法) 一种模式的工作流程图。由图2 2 可见，遗传算法是 一种群体型操作，该操作以群体中的所有个体为对象。 遗传算法中通常包含了如下五个基本要素：参数编码；初始群体的设定；适应度函 数的设计；遗传操作设计；控制参数设定【瑚。 东北大学硕士学位论文第2 章基于事例推理和遗传算法综述 2 2 2g a 的基本原理 图2 2s g a 一种模式的流程图 f i g 2 2 t h e f l o wc h a r t o f a s g a p a t t e r n 2 。2 2 1 模式定理 定义2 1 染色体是指个长度为l 的 o ，1 ) 字符串a 2 3 。 一1 2 - 东北大学硕士学位论文第2 章基于事例推理和遗传算法综述 定义2 2 模式是指在某些基因座上具有相同基因的染色体集合。记作h ， h o ，l ，) 。 定义2 3 模式阶是指模式h 中确定位置的个数。记作o h a i ) 。 定义2 4 模式定义距是指模式h 中第一个确定位置和最后一个确定位置之间的距离。 记作6 但) 。 到目前为止，遗传算法中最主要的定量结果是模式定理阱l 圜。该定理是 h o l l a n d ( 1 9 7 5 ) 为了解释遗传算法机理而提出的一个数学理论，它是遗传算法的一大理论 基础。 设m ( h ，0 表示在第t 代染色体池a ( t ) 中模式h 能匹配的元素个数，肥) 表示h 在池 中的平均适应值，厂表示染色体池中元素的平均适应值，只，厶分别表示交叉概率与变 异概率，h 在第t + l 代时染色体池中的元素个数记为巩但z t + o 。 首先探讨选择对种群中的模式的影响。在选择中，一个串是以概率b 号乃进行 = l 选择，是染色体一r 的适应值。设种群规模n 不变，则： m ( h t + 1 ) = m r t ) n 毪h ) ? f i 卢i 设种群的平均适应值为7 = 乃h ，则有： m ( h , t + 1 ) = m ( h , t ) f ( h ) f ( 2 1 ) ( 2 2 ) 由式( 2 2 ) 看出，下一代中模式h 的数量正比于h 的平均适应值。式( 2 2 ) 是选择操作 对模式h 数量影响的定量描述。 为得出更好的结论，不妨假定种群的平均适应值厂与模式h 的平均适应值觚) 之间 存在如下关系： - ， 矽= “+ 砂+ f ( 2 3 ) 其中，c 为一常数，则式( 2 2 ) 可改写为： m h 。t + 1 ) ：m l h d f c ) f = m m 1 ) 1 + c )q q 从而得出，选择操作使得平均适应值高于种群平均适应值的模式将按指数级增长， 而低于平均适应值的模式将按指数级减少。 其次讨论交叉对种群中的模式的影响。在这里为简单起见，只讨论单点交叉。对于 一1 3 东北大学硕士学位论文 第2 章基于事例推理和遗传算法综述 模式h ，要保持在下一代中继续生存，通常只有让交叉点落在模式的定义距之外，否则 模式h 将会被破坏2 6 1 。模式h 的定义距越大，h 被破坏的可能性就越大。在单点交叉 下h 的生存概率只爿- p c 6 阱，其中，是染色体长度。设交叉的概率为b ，则h 的 生存概率可表示为： 只爿- p c a 以) a - o ( 2 5 ) 最后讨论变异对种群中模式的影响。设某位变异的概率为p m ，则模式h 在变异中 保持生存的概率可表示为： p 严( i ，p 1 eq q 通常p m o ，使得_ ，御咿+ f ，则有： m 但t + o m ( h ，i ) ( i + c ) l q 9 这个推论说明，在遗传算子的作用下，具有高适应度、低阶和短定义距的染色体， 在遗传过程中其个数将随代数技指数增长。这也解释了，为什么在自然界中按“优胜劣 汰”的原则进化，能使生物很好地适应不断变化的环境而代代相传。 2 2 2 2 改进的模式定理 由上节中模式定理的推论过程知模式定理的成立需要一个重要的条件，即存在一常 数c ，对每一代俑) 部+ 砂厂都成立，但是，弘矽和在迭代过程中是变化的，御应换成 f ( h , o ，7 应换成7 何，而且随着遗传操作的进行和：砂的值与7 的值之差会越来越小， 因而上面的不等式是很难保持的。因此，模式定理需要改进，如下【2 7 1 1 2 8 ： 设染色体池中只有2 个适应度不同的染色体，模式h 的适应度为五，其余染色体的 东北大学硕士学位论文第2 章基于事例推理和遗传算法综述 适应度为五，且五) = 7 三；设第t 代模式h 的染色体个数占全体个数的比率为斫砂，池中全 体染色体适应度均值为7 何，可得： 通过复制有 将( 2 1 0 ) 式代入( 2 1 1 ) 式： 了( t ) = 蟊( i - d ( t ) ) ( f 1 j 0 d ( t + 1 ) - - d ( t ) 和h 但1 0 ) ( 2 i i ) d ( t + j ) = d ( t ) 1 ( 1 - d 功b jq 1 2 ) 其中，令b = - f z ) f t ，显然o b l ，由( 2 1 2 ) 式可知d d ，故4 = 1 ， 对( 2 1 0 ) 式取极限，则当r o 硎，f ( 1 ) 一矗，即当复制代数增加时，池中染色体的 适应度的均值将趋向矗( 最高的适应度值) 。 上面是就池中只有2 个不同的适应度值的情况进行讨论的。对于一般情况，设最高 适应度的模式h 在第t 代的适应度为力渺，其余染色体的适应度均值为尼。由上面的 推导可知，正何随t 单调增加，而石将趋于模式h 的适应度的均值。故对( 2 1 2 ) 式取极 限仍可得到( 2 1 3 ) ，所以说，上述的结论对于一般情况也是成立的。 对同时进行3 种遗传操作的情况，将得到类似( 2 8 ) 的公式： m ( i - i , t + 1 ) ；m h t ) 趣h t ) ( 1 - p c 8 ( h ) f ( 1 一1 ) 一o ( h ) p m ) f ( t )q ，1 4 1 由上分析，得到改进的模式定理如下： 若染色体中存在有结构块( b u i l d i n gb l o c k ，即高适应度、低阶和短定义距的模式) ， 则经过若干代遗传操作后，池中染色体的平均适应度至少趋近池中结构块的最高适应度 值。 这个定理没有对结构块的适应度作任何限制性的假定，同时也说明了原定理的推论 中的假设：存在一常数c ，对每一代- ，阻砂聋口+ 7 都成立的要求是不可能成立的【2 9 1 。 2 2 3 防止g a 早熟问题 在实际中，很多参数优化问题是多参数和非线性的，且往往还伴随着不可微和参数 耦合等问题。这时用传统的优化方法解决这种问题，效率很低，有时候甚至根本得不出 结果。遗传算法的高鲁棒性和有效性为解决这类问题提供了一种有效的途径。 一ls 东北大学硕士学位论文 第2 章基于事例推理和遗传算法综述 遗传算法是近年来得以迅速发展的种优化算法，其特点在于，在模拟自然界的过 程中，应用了自然界的进化规律，染色体的交叉、变异等现象，结合自然选择过程，使 物种不断向前进化。遗传算法也因此显示出了顽强的生命力，以其突出的优点而越来越 受到重视。但是遗传算法也存在着缺点，在实际应用中也因此出现了一些问题。其中很 重要的是遗传算法未成熟收敛( p r e m a t u r ec o n v e r g e n c e ，p c ) 问题【3 0 】。对于遗传算法的应 用，解决未成熟收敛问题是必要的，否则，g a 的一些优良性能( 例如全局寻优能力) 将 无法完全体现出来。 2 2 3 1 未成熟收敛现象及其产生原因 未成熟收敛现象是遗传算法中的特有现象，且十分常见。它指的是，当还未达到全 局最优解或满意解时，群体中不能再产生性能超过父代的后代，群体中的各个个体非常 相似。未成熟收敛的重要特征是群体中个体结构的多样性急剧减少【3 ”。这将导致g a 的 交叉算子和选择算子( g a 最重要的两个算子) 不能再产生更有生命力的新个体。遗传算 法希望找到最优解或满意解，而不是在找到最优解或满意解之前，整个群体就收敛到一 个非优个体；它希望能够保持群体中个体结构的多样性，从而使搜索能够进行下去【3 2 1 【3 3 1 。 未成熟收敛问题很像其它算法中的局部极小值问题，但它和局部极小值问题有着本 质上的不同，未成熟收敛问题并不一定出现在局部极小点【3 4 1 。同时，它的产生是带有随 机性的，人们很难预见是否会出现未成熟收敛问题。 未成熟收敛产生的主要原因在于【”】： ( 1 ) 理论上考虑的选择、交叉、变异操作都是绝对精确的，它们之间相互协调， 能搜索到整个解空间，但在具体实现时很难达到这个要求。 ( 2 ) 遗传算法处理的群体是有限的，因而存在随机误差，它主要包括取样误差和 选择误差。取样误差指的是，所选择的有限群体不能代表整个群体所产生的误差。当表 示有效模板串的数量不充分或所选的串不是相似子集的代表时，遗传算法就会发生上述 类似的情况。小群体中的取样误差妨碍模板的正确传播，因而阻碍模板原理所预测的期 望性能产生。选择误差是指，不能按期望的概率进行个体选择。 对一个染色体来说，在遗传操作中它只能产生整数个后代。在有限群体中，模板的 样本不可能以任意精度反映所要求的比例，这是产生取样误差的根本原因，加上随机选 择的误差，就可以导致模板样品数量与理论预测值有很大差别。随着这种偏差的积累， 一些有用的模板将会从群体中消失。遗传学家认为当群体很小时，选择就不会起作用， 表北大学硕士学位论文第2 章基于事例推理和遗传算法综述 这时有利的基因可能被淘汰，有害的基因也可能被保留。引起群体结构发生变化的主要 因素是随机波动的遗传漂移，它也是产生未成熟收敛的一个主要原因。对此可以采用 增大群体容量的方法来减缓遗传漂移，但这样做可能导致算法效率的降低。 ( 3 ) 所求解的问题是遗传算法欺骗问题。当解决的问题对于标准遗传算法来说比 较困难时，遗传算法就会偏