基于范例推理的进化计算

《基于范例推理的进化计算》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、．}l第24卷第1期西南师范大学学报(自然科学版)1999年2,slVo1．24No．1JournalofSouthwestChinaNormalUniversity(NaturalScience)Feb．1999基于范例推理的进化计算2争、，—查●。’．————_塑～●．—J。—————————一(西南师范大学计算机科学系，重庆400715)弋}《摘要结合进化计算灵活、并行的特点，将遗传算法引人CBR的基本框架中，提出了基于遗传算法的范例修正模式，讨论了GA中重要的编码、适应值函数问题．井通过具体系统的范例推理原型进行了验证．关键词逑篡迄基于范例的推理；堇熊塞；

2、范例修正分类号Ttv311拖理C耿舭艚基于范例的推理(CI3R)已成功地应用于设计、规划、诊断、教育和预测等领域，并且对知识的获取，知识的维护，问题求解的有效性，求解的质量等方面都能加以改善1．而且分布式信息环境的范例推理，将是CBR研究的新热点、因此，研究和实现CBR的理论和技术显得非常重要．EBB．按功能划分为：范倒检索、范例复用、范例修正、范例保留四个环节．(1)CBR首先通过例库检索出一个或多个相似的范例，可利用K-NN算法和归纳决策算法L．范倒的检索是CBR的关键步骤之一3；(2)相似范例的复用，涉及到结果的复用和方法的复用．结果复用涉及解的转换．而方法

3、的复用更关心源范例中问题的求解过程；(3)由于目标范倒与源范例总是存在差异的，除非能完全匹配．否则，对源范倒的修正就极为重要；(4)新问题解决后，可能形成有利于将来相似情形的处理方法，所以，保存新范例也是必要的．一般而言，范例修正知识常用产生式规则、神经网络表示、但有的知识本身比较复杂，比如预报渔场位置，涉及到很多因素，什么因素起作用完全随具体情况而定，而且难于用规则来表示；神经网络虽然能解决权值的分配问题，但同时由于隐单元数不定、可能收敛于局部极小以及其学习算法的局限性，而使神经网络的应用受到限制[43．因而．本文拟采用遗传算法(GA)不受搜索空间限制性假设的约

4、束的特点，以及具有并发性、抗噪声的优点，将GA融入CBR的基本框架中，形成进化CBR系统．利用遗传算法简单的编码技术和遗传机制来解决范例修正这一复杂的问题．本系统的“进化”一词有两含义，其一。利用了进化计算中的遗传算法；其二，当新范例通过修正而匹配并存入范例库后，系统解决问题的能力也相应提高．本文1．1节将给出CBR的基本流程，1．2节主要讨论遗传算法中的编码、遗传算子以及适应值函数，第2节讨论进化CBR系统的框架结构，并详细描述了范例修正问题，第3节收稿日期：1998-08-11李莉，女，岁，讲师20西南师范大学学报(自然科学版)第24卷给出了应用实例，最后是验

5、证结果及今后工作的展望1CBR和GA1．1CBR基本框架．图1给出CBR的基本框架结构．具体过程：用户提交查询，CBR对范例库中的范例进行检索，找出相似范例集．为了形成GA的初始种群，我们采用阈值方法，即找出所有与目标范例的相似度太于阈值的源范例．接着，进行转换操作，以便于范例的复用．如果转换成功，即满足目标范例的要求，就将新的范倒人范例库，以备将来之用，否则．找出源范倒与目标范例的差别，进行范例修正．修正之后，需要重新评价，保证不会产生与目标范例完全不相容或无关的范例，当没有可能从源范例库中找到结果时，CBR转向勰释过程，进行范例的修补，或者干脆放弃范例库，转向

6、用户输入．图1CBR基本框架Fig．1Basicframe~arkofCBR1．2遗传算法70年代，Holland[6]撰写的有关人工系统自适应方面的专著，才使人们逐渐理解了遗传算法(GA)．GA也称为迭代自适应概率搜索算法．它用{0，1，#}表示搜索空间，比如串长为5的模式P=1#O1#，可能有Al：10010，A2：11010，A3=11011，A4=10011等表型．对二进制位串执行复制、交叉、变异等遗传操作，产生新的样本．遗传算法的基本流程如图2所示【．1)编码；2)随机产生由固定字符个数组成的初始种群；3)利用适应值函数以每一个体进行评价，适应值函数被定

7、义为产生的新个体对问题的满足程度；4)执行复制、交叉、变异操作；●复制算子：将现有的个体字符复制到新的种群中；第1期李莉等：基于范例推理的进化计算21●交叉算子：将双亲的位串按交叉概率互换，形成新子代；例如：双亲1：abcdI234，双亲2：ABCD5678子代1：abed5678，子代2：A8CD1234●变异算子：将双亲的位串按变异l随机产生韧始种群f概率突变，即0变成l，1变成0．-l例如：二进制串abedef~r变异操作后f计算个体的适应值井选择适应值高的个体j可得到abedef7y．5)挑选适应值最高的个体，返回4)。直至迭代次数并将最终结果输出；6)解

8、码．遗传算