付费下载
下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
遗传算法在数据挖掘中的应用实例分析摘要:本文简要介绍了数据挖掘的一些基本概念及数据挖掘的过程,阐述了遗传算法的基本思想、步骤及其在数据挖掘中的应用,以遗传算法在旅行商问题中的应用为例,全面分析了遗传算法在数据挖掘中的应用过程及其实现,同时提出了简单遗传算法在数据挖掘应用中所存在的问题。关键词:遗传算法;数据挖掘;旅行商问题GeneticalgorithmsindataminingapplicationAbstract:Thispaperbrieflyintroducessomebasicconceptsofdatamining,explainthebasicthought,theprocedureandapplicationindateminingofthegeneticalgorithm.TaketheTravelingsalesmanproblemforexample,analysestheapplicationandeffectivenessofGeneticalgorithmindatamining.AnddiscussesthedrawbackofthesimpleapplicationindateminingofgeneticalgorithmKeywords:Geneticalgorithm;Datamining;Travelingsalesmanproblem
1数据挖掘简介数据挖掘(data
mining)是近年来数据库应用领域中相当热门的话题。数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中发现隐含的、规律性的、人们事先未知的,但又是潜在有用的并且最终可理解的信息和知识的非平凡过程[1]。通俗地说,数据挖掘就是从数据中发掘信息或知识,有人称为知识发现(knowledge
discovery
indatabase,KDD),也有人称为数据考古学(dataarcheology)、数据模式分析(datapatternanalysis)或功能相依分析(functionaldependencyanalysis)。目前,数据挖掘已经成为数据库系统、机器学习、统计方法等多个学科相互交叉的重要领域,而在实务界,越来越多的企业开始认识到,实施数据挖掘可以为企业带来更多潜在的商业机会。数据挖掘完整的步骤如下:①理解数据和数据的来源(understanding)。②获取相关知识与技术(acquisition)。③整合与检查数据(integrationandchecking)。④去除错误或不一致的数据(datacleaning)。⑤建立模型和假设(modelandhypothesisdevelopment)。⑥实际数据挖掘工作(datamining)。⑦测试和验证挖掘结果(testingandverfication)。⑧解释和应用(interpretationanduse)。数据挖掘涵盖的算法很广,目前应用较多的基本算法分为三类:①数据处理与特征提取,主要有聚类分析、主成分分析、因子分析等。②数据建模与知识规则提取,主要有回归分析、神经网络、决策树、关联分析、关联分类、时序关联、贝叶斯网络等。③优化与控制,主要有遗传算法、遗传算法与神经网络混合算法等。本文主要介绍遗传算法在数据挖掘中的应用,并结合一个旅行商的问题具体阐述这种思想。2基本遗传算法遗传算法(GeneticAlgorithm,GA)是由美国J.Holland教授提出的一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。它起源于达尔文的进化论,是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。作为一种全局优化搜索算法,遗传算法以其简单通用、鲁棒性强、适于并行处理以及应用范围广等特点,使其成为21世纪智能计算核心技术之一。进入80年代,遗传算法迎来了兴盛发展时期,无论是理论研究还是应用研究都成了十分热门的话题[2]。在遗传算法中,首先将空间问题中的决策变量通过一定的编码表示成遗传空间的一个个体,它是一个基因型串结构数据,然后将目标函数转换成适应度值,用来评价每个个体的优劣,并将其作为遗传操作的依据。遗传操作包括三个算子:选择、重组和变异。选择是从当前群体中选择适应值高的个体以生成交配池的过程,交配池是当前代与下一代之间的中间群体。选择算子的作用是用来提高群体的平均适应度值。重组算子的作用是将原有的优良基因遗传给下一代个体,并生成包含更复杂基因的新个体,它先从交配池中的个体随机配对,然后将两两配对的个体按一定方式相互交换部分基因。变异算子是对个体的某一个或几位按某一较小的概率进行反转其二进制字符,模拟自然界的基因突变现象。遗传算法的基本程序实现流程如下:(1)先确定待优化的参数大致范围,然后对搜索空间进行编码;(2)随机产生包含各个个体的初始种群;(3)将种群中各个个体解码成对应的参数值,用解码后的参数求代价函数和适应度函数,运用适应度函数评估检测各个个体适应度;(4)对收敛条件进行判断,如果已经找到最佳个体,则停止,否则继续进行遗传操作;(5)进行选择操作,让适应度大的个体在种群中占有较大的比例,一些适应度较小的个体将会被淘汰;(6)随机交叉,两个个体按一定的交叉概率进行交叉操作,并产生两个新的子个体;(7)按照一定的变异概率变异,使个体的某个或某些位的性质发生改变;(8)重复步骤(3)至(7),直至参数收敛达到预定的指标。其流程图如下:初始化群体初始化群体个体评价t<T?选择变异终止交叉图1遗传算法流程图使用遗传算法需要确定的运行参数有:编码串长度、交叉和变异概率、种群规模。编码串长度由问题的所要求的精度来决定。交叉概率控制着交叉操作的频率,交叉操作是遗传算法中产生新个体的主要方法,所以交叉概率通常应取较大值,但如果交叉概率太大的话又可能反过来会破坏群体的优良模式,一般取0.4—0.99。变异概率也是影响新个体产生的一个因素,如果变异概率太小,则产生新个体较少;如果变异概率太大,则又会使遗传算法变成随机搜索,为保证个体变异后与其父体不会产生太大的差异,通常取变异概率为0.0001-0.1以保证种群发展的稳定性。种群规模太大时,计算量会很大,使遗传算法的运行效率降低,种群规模太小时,可以提高遗传算法的运行速度,但却种群的多样性却降低了,有可能找不出最优解,通常取种群数目20-100。从理论上讲,不存在一组适用于所有问题的最佳参数值,随着问题参数的变化,有效问题的参数的差异往往是十分显著的。3遗传算法在数据挖掘中应用举例现有城市、、……、,一旅行商,想选择一条最短的路线环游所有城市各一次后回到原出发地,如何选择一条路径?现将问题转化为相应的参数表示如下:定义:简单的遗传算法GEN的一个8元组如下:GEN=(C,E,P0,M,F,G,Y,T)(1)其中:C为个体的编码方法;E为个体的适应度评价函数;P0为初始群体;M为群体大小;F为选择因子;G为交叉因子;Y为变异因子;T为算法终止条件。3.1参数选择和编码方法初始群体随机产生,其个体个数取100个。这里采用染色体编码方法,即将每个城市表示为一个基因,城市数即为染色体的基因数,城市编号用十进制数表示,使用0-(n-1)这n个数码表示以上n个城市,一条路径t(i)就是由这n个数码组成的编码串,其中单个数码对应为一个基因,编码串对应于染色体。其中编码串中的每个数码只能出现一次。3.2适应度及适应度函数设问题的目标函数为length(t),问题的目标是求取最小路径,所以属于最小值优化问题,所以可以取适应度函数F(t)为路线t所对应的路线长度length(t)的倒数,其中有:(2)(,,…,)表示路线t所经过的n个城市的顺序,表示两个城市之间的距离。3.3遗传因子的选择根据适应度比例法(比如轮盘赌法)选择择进用来行交叉的父代,生成子代。该例子采用了染色体编码的方法决定了采用普通交叉算子将无法保证基因编码串中仅仅出现一次,即不能保证每个城市在一个路径中只出现一次。为了满足在子代中不出现重复基因码的条件,我们采用循环交叉法。由于我们应用了染色体编码方式,使得编码串中的异位发生突变的常规的变异算法不能适用,这时我们可以采用倒位变异、基于次序的变异或基于位置的变异。这里我们采用倒位变异。3.4终止条件分析迭代次数的选择对计算结果至关重要,固定迭代次数有利于遗传算法处理,但设置选择困难而且不利于产生最优解;不固定迭代次数通过对个体解得判断自动进行迭代,有利于产生最优解,并且解决了参数选择的困难,但容易增加遗传算法的斥力时间。这里我们采用了固定的迭代次数N=3500。4实验分析为检验该算法的实际应用效果,文中以15,22,24,32个城市为例(这4个TSP实例,弹性网络算法的计算结果及最优解见参考文献[3]),应用MATLAB编程实现,将该算法得到的结果与用弹性网络算法得到的结果进行了比较,如表1所示。表格SEQ表格\*ARABIC1遗传算法与弹性网络算法计算结果比较城市数15222432最优解2123278535124133遗传算法2125278935184138弹性网络2154283136054195为了更好地说明遗传算法在求解TSP问题中良好的全局搜索能力,文中以求解32个城市为例进行运算。通过MATLAB编程运算可以发现,随着迭代次数的增加,最佳个体的适应度函数值逐步增加,最后收敛于一个相对稳定值。用遗传算法求解得到的32个城市的遍历图。其结果如图2所示。图232个城市的遍历图从表1,图2中可以看出,遗传算法有较好的全局最优解的求解能力。5结语遗传算法在数据挖掘中已经得到了很广泛的应用,并取得了很好的计算结果。简单遗传算法在数据挖掘中的应用在大部分情况下可达到较好的计算结果,但有时候也产生一些问题,例如缺乏广泛而完整的遗传算法收敛理论,有时产生早熟现象和欺骗问题,搜索效率及时间复杂性问题等。
参考文献:
[1]陈文伟,黄金才.数据仓库与数据挖掘[M].北京:人民邮电出版社,2004.8:8-200.
[2]
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026 主流企业邮箱价格表看完就知道贵不贵
- 社区老年人健康问题应对预案老年人健康随访手册
- 智能制造车间运营效能考核表
- 如何影响他人并提升影响力的沟通技巧指南书
- 家电企业售后服务部客户满意度与问题解决速度绩效分析表
- 六上英语补全对话
- 关于优化企业信用评分的通知(5篇)
- 农业科技研究员农作物研发成果及技术应用绩效考核评估表
- 订单确认函关于下月采购需求(4篇)范文
- 关于订货合同金额的确认函(7篇范文)
- 【新教材】统编版(2026)九年级下册道德与法治期末复习全册知识点考点提纲
- 十五五(2026-2030)河南省智能微电网可行性研究报告
- 《听 口哨与小狗》课件-2025-2026学年苏少版(简谱)二年级上册音乐
- 生产现场综合管理制度
- 高中政治必修一经济生活知识点总结
- 福建省泉州市惠安县第一教研联盟2025-2026学年七年级上册期中联考数学科试卷(含答案)
- 超高层玻璃幕墙系统安装施工方案
- 小型水电站设备运行规程细则
- 儿童服装设计基础与创意实践
- 小儿营养性疾病诊疗与管理要点
- 设计院新员工入职培训方案
评论
0/150
提交评论