基于CBR-GA的建筑块重组

《基于CBR-GA的建筑块重组》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第28卷第5期2011年5月计算机应用研究ApplicationResearchofCompute鹏Vol-28No．5Mav2叭1基于CBR—GA的建筑块重组邹鹏，闭应洲，杨虎林，刘阿宁，元昌安(广西师范学院计算机与信息工程学院，南宁530004)摘要：为了解决遗传算法(GA)中好的建筑块被破坏的问题，提出基于CBR—GA的建筑块重组方法。首先反复运行简单的遗传算法找到多个局部最优解，并选择多个不同的局部最优解构建案例库；然后应用差异化学习方法产生新案例，有效解决了GA中随机交叉对建筑块破坏的问题；最后通过4阶欺骗问题验证了新算法的可行性。关键词：案例推理；遗传算法

2、；欺骗问题中图分类号：仍01．6文献标志码：A文章编号：1001．3695(2011)05．1658．03doi：10．3969／j．is蚰．100l一3695．加11．05．017TowardrecombinationofbuildingblocksbasedonCBR—GAZOUPerIg，BIYillg-zhou，YANGHu-lin，UUA·niIlg，YUANCIlaIlg-锄(coZ妇口o，co唧u幻&岫m动％En副，柳r，‰，增研％∞^m尉蚴砌n№汹妙，盹n，“昭530004，m妇m)Abstr嗣哦：Inordertosolvetheproblemoft

3、lledestruction0fgoodbuildiIlgblocksinGA，thi8paperpresentedanovelap-proachtorecombinethebuildingblocksbasedoncBR—GA．Firstly，啪simpleGArepeate曲tofindmultiplekaloptimal∞luti伽8，锄dchosethedifkrentlocal叩tiIIlal“utionst0buiIdtheca跎-ba∞．Secondly，genemtedthenewca∞bydi脆ren-tiationle唧ingwhicheffect

4、ivelysoIvedtheproblemofthede8tmctionofbuildingblockinGA．FinaUy，verifiedthenewaIgo．rithmwith4一orderdeceptivepmblem．Keywords：c鹪e·ba∞drea∞ning；genetic蜊thm；deceptivepmblem0引言遗传算法(GA)是20世纪70年代由美国的Hou粕d提出的模仿生物进化过程的优化方法，它的主要思想是基于Da耐n的生物进化论和Mendel的遗传学。GA结合了Da州n的适者生存和随机交换理论。适者生存理论消除了解中的不适应因素；随机交

5、换理论利用了原有解中的已有知识，从而加速了对优化解的搜索过程。GA作为一种基于优胜劣汰自然选择机制的优化方法，计算简单、功能强大且具有很好的并行计算能力，在很大搜索空间下能很快地找到较好的解，在复杂情况下的鲁棒性依然很高。它尤其适于目标函数具有诸多限制条件下的多参数优化问题⋯。GA通过交叉算子产生新的后代，但是由于交叉算子的交叉点是随机选择的，有些交叉会破坏个体中原有的高质量部分解(文献中常称之为建筑块)，使得后代的适应值要比父代的更差。因此，为了设计快速有效的演化算法，降低交叉算子的破坏性研究是十分必要的B1。为了降低交叉算子的破坏性，文献[3]提出通过识别个体中的

6、优秀基因，在交叉过程中保护个体中的优秀基因，达到有效识别和重组建筑块的目的。由于遗传算法、蚁群优化、分布估计算法等算法都属于从当前种群(已知样本)产生新的种群(新的搜索点)，MacreadyHl将这些算法的搜索机理归纳为反复执行以下两个步骤：推断问题的结构；根据推断，决定下一步如何抽样产生新的候选解。从已知样本中推断问题结构的过程就是学习过程，因此利用其他机器学习的成果改进GA内在的学习过程，提高GA的建筑块重组效率是合理的。基于案例推理(cBR)是近年来人工智能领域中兴起的一项重要的推理技术。与规则推理不同，它通过访问案例库中的同类案例(源案例)的求解从而获得当前问

7、题(目标案例)的解决方法。案例存储是一个学习环境，在这个环境中注入新的案例，删除已有案例和修改案例来适应问题情况。随着cBR技术的日益成熟，它已被成功应用于许多应用领域，如呼叫中心决议、经验管理和认知信息检索等"1。为了更有效地求解复杂的优化问题，本文提出了将GA与cBR相结合的问题求解模型，有效解决了遗传算法的随机交叉对建筑块的破坏问题，并且保证了GA种群的多样性，防止陷入“早熟”。1CBR研究概述CBR是一种基于人类问题求解实例的计算模型，首先是由美国耶鲁大学RogerSch肌k在研究动态存储技术中发现的，并且在1982年所著的《Dy—埘nicm