《毕业设计（论文）基于遗传算法的数据挖掘方法研究及应用.doc》由会员分享，可在线阅读，更多相关《毕业设计（论文）基于遗传算法的数据挖掘方法研究及应用.doc（23页珍藏版）》请在三一办公上搜索。
1、目录摘要 1Abstract(英文摘要) 2第一章绪论1.1 引言 31.2 国内外研究现状 3第二章数据挖掘概述2.1 数据挖掘的发展历史 52.2 数据挖掘的定义 52.3 数据挖掘的目的、任务和对象 62.3.1 数据挖掘的目的 62.3.2 数据挖掘的任务 62.3.3 数据挖掘的对象 72.4 数据挖掘的特点 82.5 数据挖掘的常用方法 82.5.1 归纳学习方法 82.5.2 公式发现 92.5.3 统计分析方法 92.5.4仿生物技术 92.5.5可视化技术 102.6 数据挖掘的基本步骤 10第三章关联规则基本理论3.1 关联规则的定义及性质 123.2 关联规则的挖掘过程
2、133.3 衡量规则的价值 14第四章遗传算法概述4.1 遗传算法的发展历史 154.2 遗传算法的特点 154.3 基本遗传算法的主要思想及术语 164.4 基本遗传算法的描述与形式化定义 174.5 遗传算法的基本实现技术及设计步骤 174.5.1 编码方法的选取 174.5.2 适应度函数的设计 184.5.3 遗传算法的设计步骤 18第五章基于遗传算法的关联规则挖掘模型 19参考文献 21致 谢 22摘要随着人们对数据库技术逐步深入的研究, 数据挖掘技术应运而生. 最初, 商业活动中的各种数据仅仅是存储在计算机的数据库中, 然而为了人们对数据库管理的需求, 我们开始能够查询并访问计算机
3、的数据库, 从而实现了数据库的即时遍历. 数据挖掘技术甚至将数据库技术推动到了一个更为高级的阶段, 自此这项技术不仅能够查询和遍历过去的数据, 并且能够识别数据之间潜在的联系, 从而对信息的传递起到相当的促进作用. 作为一门典型交叉学科, 数据挖掘具有计算机科学、统计学的学术背景,其为当下数据库系统研究及应用领域的热门研究方向, 吸引了学术界和业界的广泛关注. 首先，本文对数据挖掘技术做了概述, 以明确其定义、目的、任务、对象及主要过程、基本方法. 其次, 我们对关联规则的定义、性质及种类等概念作初步介绍. 再次, 重点介绍著名的优化搜索算法遗传算法, 在回顾遗传算法的发展历史以及主要理论之后
4、, 给出了基本遗传算法和算法描述以及算法的基本实现技术. 基于以上本文提出一种基于遗传算法的关联规则提取方法, 并从编码方法及适应度函数等方面详细讨论. 最后，本文给出遗传算法在关联规则挖掘中的应用模型. 关键词：数据挖掘；遗传算法；关联规则；适应度函数AbstractData mining is a result of long-term research on database technology. Initially the data used on the business occasions were only stored incomputers database,whose i
5、nquiries and visits is later on developed then real-time database inquiries is further on so developed. Data mining pushed database technology to an even more advanced stage. It can not only inquire old data butalso identify the potential relationship between them, thusbenefit the information spread
6、ing. As a typical cross-discipline,data mining is a popular area for the current research on database system and its applications,ithas a double academic backgrounds on computer science and statistics, and it hasalsocaught the attentions from industrial fields. Firstly in this paper we give data min
7、ing an overview, as well as clarify its definition, purpose, mission andobjects, further we shall talk about the main processand techniques involved in data mining. Secondly weintroduce its definition, nature, typesof the associated rules. Witha huge significance weintroducegenetic algorithm,which i
8、s widely applied in data mining practices. We make a briefing on history and main theory of genetic algorithm, then give the basic genetic algorithms and its descriptionsalong with several basic implementation technologies. Last but not least, webring forward a mining method for association rules wh
9、ich is mainly based on genetic algorithms. At the same time, we would like to discussthe genetic algorithms fromthe aspects such as coding method, fitness function andgenetic operators.As the ending of the paper, we give the application model of the association rules mining based on genetic. Key Wor
10、ds: Data Mining;Genetic Algorithm; Fitness Function; Association Rules第一章 绪论1.1引言计算机科学及现代通信技术的迅猛发展已将人类带入了信息时代, 近几十年应由社会与经济发展的需求, 计算机的数据库存储的数据剧增, 人们掌握有大量的数据得以提取所需要的信息, 而这些数据所提供的信息在给人们带来方便的同时也对原有数据库技术提出了新的挑战. 现代社会的信息爆炸程度已远远超出了人们掌握和理解数据的能力, 这为正确地利用数据带来了困难. 人们开始逐渐意识到, 那些能够描述事物整体特征、预测未来发展趋势的信息往往是隐藏在大规模的数
11、据背后更深层次的内容, 这些潜在信息对于人们做出决策具有重要的参考价值. 那么如何透过巨量的数据信息获取这些有用的“知识”呢？计算机科学与统计学的最新研究给出回答：数据挖掘. 数据挖掘汇集了数据库、数理统计、人工智能、并行计算、可视化等诸多领域的研究者及业界的工程师,通过对数据库进行从微观到宏观的统计分析与综合推理, 以发现数据之间的相互关联, 乃至利用已有数据对未来进行预测, 从而针对实际问题为人们提供决策支持. 1.2国内外研究现状数据挖掘技术在诸多方面已得到广泛之应用, 但就其目前的研究状况来看, 这一技术还未能称得上成熟, 故在应用上有很大局限. 局限其一, 即挖掘对象之局限, 面对维
12、数更高、各属性之间更为复杂的超大型数据库, 现有数据挖掘技术处理如此巨量数据不免捉襟见肘；局限其二, 大部分数据库在知识发现的过程中可能存在数据或属性丢失的问题；局限其三, 目前数据挖掘工具一般仅能处理特定数值型的结构化数据. 反而思之, 正是由于这些局限的存在, 方才能不断推动数据挖掘技术有着更为长足的发展. 遗传算法作为全局并行优化搜索算法的有效性为人称道, 其在解决具有混沌、随机和非线性等典型特性的复杂问题中提供一种新的计算模型, 克服了由大量数据嘈杂无序造成的难题. 这一模拟自然界进化过程的通用全局搜索算法, 有效避免搜索过程中出现的局部最优, 有望在规则发掘中大施拳脚. 遗传算法自诞
13、生至今虽已经过历次改进, 但仍有待进一步深入研究的必要. 其一, 算法的理论研究相对滞后, 遗传算法提出之灵感源于一种仿生的思想, 故其尽管在实践中被证明极为有用, 然而在理论证明上却遇到瓶颈；其二, 算法的参数设置仍无明确标准, 之前的应用中采用的均为过往的经验数值, 而不同编码与遗传技术将对遗传参数的选取产生影响, 这无疑制约了算法的通用性；其三, 算法对于约束化问题的处理缺乏足够的有效性. 近年对关联规则挖掘的研究主要可分为四个方面. 一是改进由R. Agrawal等提出的Apriori算法, 这些工作主要集中在有效地生成最大项目集并改善该算法效率；二是对关联规则的阈值进行调整, 增强所
14、挖掘规则的关联性与有效性使之更为符合人们的需求；三是提出用于关联规则发掘的并行算法；四是扩展关联规则发掘中的二级问题, 诸如多层/广义关联规则、循环关联规则、定量关联规则等. 因遗传算法简单通用且适于并行处理之特性, 使其在数据挖掘技术占用举足轻重的地位. 目前, 对以遗传算法为基础的数据挖掘研究主要在分类系统方面, 而在关联规则提取方面的应用仍未常见. 本文提出用遗传算法辅助对关联规则进行挖掘, 便是希望能在这方面进行新的尝试. 第二章 数据挖掘概述2.1数据挖掘的发展历史1989年8月, 于底特律召开的第十一届国际人工智能联合会议的专题讨论中首次提出KDD(Knowledge Discov
15、ery in Database)这一术语. 随后, 首届知识发现和数据挖掘国际学术会议于1995年在加拿大蒙特利尔召开. 亚太地区则于1997年在新加坡召开了第一届亚太知识发现和数据挖掘国际会议, 欧洲也于1998年召开了第一届欧洲知识发现和数据挖掘学术会议. 知识发现和数据挖掘长期作为数据库和机器学习的分支, 直到1998年6月ACM(AssociationofComputingMachinery)成立SIGKDD(SpecialInternetGrouponKnowledgeDiscoveryandDataMining), 才使其正式脱身为一门独立学科. METAGroup有评论如下, “
16、全球重要的企业及各类组织将会发现, 在二十一世纪, 数据挖掘技术将在决定其在商业经营中成功与否产生至关重要的影响”. IBM在之后几年随即发布IBMDB2智能挖掘器积分服务, 这一服务基于标准的数据挖掘技术, 提供个性化解决方案. 统计软件SPSS与SAS亦分别推出数据挖掘工具Clementine和EnterpriseMiner. 2.2数据挖掘的定义数据挖掘, 即从大量不完全并且模糊有噪声的随机数据中提取隐含其中事先未知却潜在有用的信息和知识的过程. 这一表述具有若干层次含义, 其一, 数据挖掘中原始数据真实、大量且含噪声；其二, 数据挖掘专注于发现人们感兴趣、有价值的知识；其三, 数据挖掘
17、着力于发现直觉无法发现乃至有悖直觉的知识, 其越是出人意料, 便可能越有价值；其四, 潜在有用性是指数据挖掘发现的知识对于所讨论的业务或研究领域具有实用价值, 诸如常识性的结论、已掌握的事实及无法实现的推论均视作无意义；其五, 数据挖掘发现的知识须可为人们所接受、理解并运用于解决实际问题；其六, 数据挖掘并非要发现那些放之四海皆准的真理抑或全新的自然科学定理, 所有被发现的知识都具有特定约束条件或面向特定领域. 目前来说, 学术界对数据挖掘仍未形成统一的精确定义, 在不同的文献中, 不同的应用领域里有着不同侧重的定义表述. 常见的如Ferruzza定义数据挖掘为于知识发现过程用以辨识存在数据间
18、未知关系和模式的方法；Zekulin定义数据挖掘为从大型数据库中提取未知的、可理解的、可执行的信息并利用其辅助商业决策的过程；Parsaye则认为数据挖掘是为获取未知的信息模式而研究大型数据集合的决策支持过程. 2.3数据挖掘的目的、任务和对象2.3.1 数据挖掘的目的随着数据库及信息系统技术逐步深入的应用, 面对长时间积累所形成的海量数据人们常无所适从, 以至淹没在数据的海洋中却缺少“知识”. 我们开始考虑尝试发现数据中存在的关系和规则并根据已有数据预测未来发展趋势, 从而做到不被信息淹没, 提高信息利用率. 现在, 数据挖掘分析海量数据并发现其中的潜在联系. 2.3.2数据挖掘的任务数据挖
19、掘有关联分析、时间序列模式、聚类、分类、偏差检测及预测六项基本任务. 我们先讨论关联分析. 当若干数据项取值出现重复, 这之间即有某种关联, 从而可建立关联规则. 我们常用“可信度”与“支持度”对其进行筛选. 时间序列模式即根据时间序列搜索重复发生概率较高的模式. 我们需要在时序模式中找出在某个最小时间段内出现概率高于阈值的规则, 当然, 随着形式的变化我们将对规则做出适当的调整. 聚类, 即根据意义之不同对数据库中的数据划分一系列子集, 即类. 人们通过聚类以建立宏观概念,统计分析、机器学习和神经网络均是常见方法. 分类作为数据挖掘中应用最多的任务, 描述一个类别的概念以代表这类数据的整体信
20、息, 称为其内涵描述, 一般用规则或决策树表示. 分类可将数据库中元组影射到给定类别的某一个中. 分类通常是基于训练样本集（已知数据库元组及类别所组成的样本）通过相关算法求得. 然后是偏差检测. 数据库中数据往往存在诸多异常, 偏差检测便是寻找观察结果与参照之间的差别. 观察结果一般为一个或多个域的值的汇总, 参照则通常是给定模型的预测结果、外界提供的标准或另一个观察结果. 最后我们讨论预测. 预测, 顾名思义, 从历史数据中寻找变化规律以建立模型, 并基于此预测未来. 主流的预测方法有回归分析和神经网络, 回归分析用于预测连续数值, 而神经网络预测则连续、离散皆适用. 2.3.3数据挖掘的对
21、象理论上, 在任何类型的数据存储上均可进行数据挖掘, 包括关系数据库、事务数据库、数据仓库等. 这里我们对主要的数据挖掘对象予以介绍. 首先是关系数据库. 关系数据库是表的集合, 每个表命名唯一, 其中包含一组属性用于存放大量元组. 关系中每一元组代表一个被唯一关键字标识的对象, 并由一组属性值所描述. 关系数据库可通过数据库的结构化查询语言访问. 关系数据库拥有完备的数学理论基础且具有相当高的普及度, 是当下数据挖掘最为丰富的数据源之一. 其次, 我们讨论事务数据库. 一般地, 事务数据库由一个文件组成, 每一个事物由其中一个记录所代表. 通常, 一个事务有唯一的事务标识号和一个组成项列表（
22、部分包含事务的处理时间）. 事务数据库常应用于“购物篮数据分析”, 其对关联规则的数据挖掘十分有效. 再次, 我们介绍数据仓库. 数据仓库的创始人WilliamH.Inmon对数据仓库定义如下：数据仓库是面向主题的(Subject-Oriented)、集成的(Integrated)、随时间而变化的(Time-Variant)、稳定的(Non-Volatile)数据集合. 从辨证的角度来看, 从关系数据模型到数据仓库的诞生, 数据仓库的出现与广泛为人们所接受实质上是数据管理螺旋式的上升.数据仓库技术的逐步成熟很大程度上推动了数据挖掘技术的繁荣. 近年来, 数据库技术发生了翻天覆地的变化, 其已由
23、最初单一的关系数据库逐步发展为面向对象数据库、事物数据库、空间数据库、对象-关系数据库、多媒体数据库等新的数据库系统, 与此同时, 数据挖掘的数据来源也更多地取自于新型的高级数据库系统. 2.4数据挖掘的特点数据挖掘的特点可初步归纳为五个方面. 其一, 数据挖掘所处理的数据规模十分庞大；其二, 数据库查询一般是即时的随机查询, 因不能有精确查询要求, 数据挖掘技术则可辅助寻找用户感兴趣的知识；其三, 在一些应用中数据在很短时间内即有较大变化, 数据挖掘技术能够在这种情况下快速反应以提供决策支持；其四, 数据挖掘不仅要发现潜在规则, 而且要管理、维护规则, 规则往往不是一成不变的, 随着数据的不
24、断更新, 规则亦需随之而变；其五, 数据挖掘是基于大样本统计规律发现规则, 这未必适用于全部数据, 当达到某一阈值时即可认为此规则成立. 2.5数据挖掘的常用方法2.5.1归纳学习方法归纳学习方法从技术上分为两类：信息论方法与集合论方法. 我们先讨论前者. 信息论方法主要基于信息论原理建立决策树, 由于最终将以决策树的形式表示知识, 故文献中经常称其为决策树方法. 这里我们介绍两种较有特色的信息论方法. 一是ID3等系列方法, 其利用信息增益寻找包含最大信息量的字段以建立树的结点, 由不同字段取值建立分枝, 再对数据子集重复以上过程, 最终建立决策树. 对愈为庞大的数据库, 这一方法愈为有效；
25、还有一种方法我们称为IBLE(Information-BasedLearningfromExamples)方法, 其根据信息量大小寻找各字段取值建立树的结点, 并将结点中指定字段值的权值和与阈值比较, 建立三个分枝, 再对各分枝子集重复以上过程, 最终建立决策树. 再说集合论方法.这类方法广为人知的有覆盖正例排斥反例的方法、概念树方法和粗糙集(RoughSet)方法.概念树方法则是将数据库中的属性字段根据归类方式进行合并, 以此建立的层次结构称为概念树；最后介绍粗糙集方法, 我们将数据库中的行元素看作对象, 列元素看作属性（分为条件属性与决策属性）. 定义等价关系为不同对象某一个或多个属性具有
26、相同取值, 称满足同一等价关系的对象所组成的集合为该等价关系的等价类. 条件属性上等价类与决策属性上等价类之间有三种关系, 分别是下近似(包含)、上近似(和的交非空)和无关(和的交为空). 我们对下近似建立确定性规则, 对上近似建立不确定性规则, 而无关情况下则不存在规则. 2.5.2公式发现公式发现的含义即是对工程或科学数据库中的若干数据项进行数学运算并求相应的数学公式. 这里举两个典型的例子. 一是经验公式发现系统FDD, 其基本思想是对两个数据项交替取初等函数后再与另一数据项进行线性组合, 若组合结果为直线, 就得到由数据项的初等函数表示的线性组合公式；二是物理定律发现系统BACON,
27、其基本思想很简单, 就是对数据项进行初等数学运算以形成组合数据项, 若值为常数, 就得到组合数据项等于常数的公式. 2.5.3统计分析方法统计分析利用统计学原理分析数据库中数据从而得到其中的统计信息与知识, 已发展成一门独立的学科. 下面简要介绍六种统计分析中的基本方法. 一是常用统计, 即求最简单的统计量；二是相关分析, 即计算变量间的相关系数；三是回归分析, 即以回归方程表示变量间数量关系；四是差异分析, 即从样本统计量的出发进行假设检验；五是聚类分析, 即直接计算样本数据间的距离, 将距离小于某一阈值的归为一类；六是判别分析, 即确立一个判别标准以建立一个或多个判别函数, 据此将未知对象
28、划归到某一类别. 2.5.4仿生物技术典型的仿生物技术方法有遗传算法和神经网络方法.我们先讨论遗传算法. 遗传算法的基本思路是模拟生物进化过程, 有选择、交叉和变异三个基本遗传算子. 选择算子描述从旧种群选择出具有更强竞争力的个体产生新种群的过程；交叉算子描述两个不同个体（染色体）的部分（基因序列）进行交换并产生新个体的过程；变异算子描述个体的某些基因进行变异（1变0, 0变1）的现象. 在优化计算和分类机器学习方面遗传算法已广泛应用并证实了其显著的效果. 后文将对遗传算法做进一步介绍. 再讨论神经网络方法. 神经网络方法基于MP模型与Hebb学习规则, 模拟人脑神经元结构建立三类多种神经网络
29、模型. 一是前馈式网络, 其代表为感知机、BP反向传播模型及函数型网络. 此类网络在预测和模式识别方面有广泛应用；二是反馈式网络, 其代表是Hopfield的连续及离散模型, 分别应用于优化计算和联想记忆；三是自组织网络, 其代表为Kohonen模型和ART模型, 常用于聚类. 2.5.5可视化技术可视化技术, 顾名思义, 是一种图形显示技术. 以图形显示多维数据, 可深刻揭示数据的分布规律及内在本质. 同样, 对数据挖掘过程进行可视化与人机交互可显著提高挖掘效果. D.A.Keim定义数据挖掘可视化为寻找并分析数据库以找到隐藏的有用信息的过程. 常见的可视化方法有三种, 一是提取几何图元,
30、在构造、仿真和分析数据分布模型上极为有效；二是绘制, 主要基于计算机图形学近年的发展成果来进行图像生成、消隐、光照效应及部件绘制；三是显示和演放, 为取得更佳显示效果, 图片组合、文件标准、着色、旋转、放大和存储等诸多功能在这一部件中均有提供. 2.6数据挖掘的基本步骤以下我们将以顺序方式列出数据挖掘的各步骤, 但数据挖掘过程并不是线性的, 需不断重复以下步骤以得到最优的结果. 步骤一：确定业务对象. 首先, 对业务问题要有清晰的定义, 数据挖掘的第一步也是最为重要的一步即是认清数据挖掘的目的；步骤二：数据准备.包含数据选择、预处理与转换；步骤三：数据挖掘. 挖掘已经过转换之数据, 只需选择适
31、当的挖掘算法, 剩下的工作可交由计算机自动完成. 步骤四：结果分析. 即解释并评估结果, 用到的分析方法由数据挖掘的具体操作决定, 可视化技术通常会被应用于此. 步骤五：知识的同化. 即在业务信息系统的组织结构中集成数据挖掘所得知识. 第三章 关联规则基本理论3.1关联规则的定义及性质定义3.1 设为个不同项目之集合, 为事务数据库, 其中每一事务为一项目子集, 即. 称事务包含项目集, 表示为. 关联规则为形如的逻辑蕴含式, 其中, 且. 称作前提, 称作结果. 定义3.2 若事务数据库中有的事务包含, 则称规则的支持度为；若事务数据库中包含的事务中有也包含, 则称规则的置信度为. 可信度表
32、示的是一条规则可信赖的程度. 我们发现关联规则是为了找到可信赖且具有代表性的规则, 因而我们需要事先对支持度和可信度分别给定最小阈值, 所谓发现关联规则, 即是发现可信度与支持度均高于阈值的规则. 性质4.1 若关联规则与在中均成立, 规则不一定在中成立. 性质4.2 若, 且中支持的都只支持或, 则的支持度为零, 故规则的可信度为零. 性质4.1-2描述了关联规则的非结合性, 因其据定义显然, 故此不复证之. 类似地, 若与成立, 不一定成立. 性质4.3 若在中成立, 与不一定在中成立. 证 由与, 若成立, 则与均成立, 矛盾, 故得证. 性质4.3描述的是关联规则的不可分解性. 性质4
33、.4 由及不能推出. 证 设最小可信度为, 即由, 由, 由, , 又, 故, 故规则不成立. 证毕. 性质4.4描述的是关联规则的不可传递性. 性质4.5 设项目集满足, 若不满足最小可信度条件, 则也不满足最小可信度条件. 证 由子集支持性质, 设和是两个不同的项目集, 若, 则. 又因中支持的交易一定支持, 故, 再由可信度定义有, 同理, 对满足的项目集, 若成立, 则亦成立. 性质4.5描述的是关联规则的可扩展性, 当项目集及支持度已确定, 可用这一性质加速规则发现的过程. 3.2关联规则的挖掘过程关联规则的挖掘一般有两个过程, 一是找出所有频繁项集,二是由频繁项集产生关联规则, 这
34、些规则须满足可信度和支持度条件. 第二个过程须在前一个的基础上进行, 工作量较小, 而过程一则决定了关联规则挖掘总体性能. 关联规则的可信度较之期望要高方才表明的出现对的出现产生促进作用, 即表明其之间在某种程度上相关. 对于给定交易集, 挖掘关联规则便是发现可信度与支持度均大于预先给定阈值的关联规则. 3.3衡量规则的价值在用数据挖掘方法发现了一些关联规则后, 系统如何得知哪些规则对于用户来说是有价值的？对这个问题常分为两个层面来考虑, 即系统客观层面与用户主观层面. 我们先讨论系统客观层面. 首先, 我们需明确一点：使用前文所述的“支持度和信任度”框架可能发掘出“不正确”的规则, 即若我们
35、人为地将阈值设置得过低, 则可能得到互相矛盾的规则, 而反之,若阈值被设置得过高, 则所得到的规则又可能不合实际. 因此只依靠可信度与支持度的阈值设定不一定能得出我们需要的规则. 于是, “兴趣度”这一概念被引入用来筛掉我们不感兴趣的规则. 在统计独立性假设下, 定义一条规则的兴趣度为真实强度与期望强度之比值. 再是用户主观层面的考虑, 之前的讨论仅仅是基于系统方面, 但规则的价值判定最终仍应取决于用户, 因为有能力分辨所挖掘规则有效性与可行性的只有用户. 这里我们提出可以采用一种基于约束(Constraint-Based)的挖掘方式, 包括数据约束、维度/层次的约束乃至规则约束, 这其中的约
36、束条件能够和算法紧密结合, 从而可以做到既提高效率, 又更加明确挖掘的目的. 第四章 遗传算法概述4.1遗传算法的发展历史上世纪六十年代密歇根大学的J.H.Holland教授首先提出将生物体通过遗传变异来适应环境的进化论思想应用于优化技术并基于此设计新的优化算法. 在研究自适应系统时他即提出系统与外部环境相互作用与协调的重要性. 另一方面, 涉及到进化算法的思想, 他则已经意识到利用群体搜索方法及选择交叉等策略. 随后, 他和他的学生们在自适应系统方面做了许多工作, 1967年J.D.Bagay在其博士论文中首次使用了遗传算法(GeneticAlgorithm)这一术语, 他采用的是双倍体编码
37、, 并发展了复制、交叉及变异等基因操作, 提出了自组织遗传算法及适应度定标的概念. J.H.Holland教授于1975年问世的专著自然界和人工系统的适应性较为全面地介绍了遗传算法. 遗传算法的数学基础由这本书所奠定, 现在人们常将其视为遗传算法正式诞生并得到世人承认的标志, 至此遗传算法已完成萌芽及蕴育阶段, J.H.Holland亦被视为遗传算法的funding father. 直到八十年代, 遗传算法经历了不断的完善与成长, 并且随着研究和应用逐步深入, 一系列以遗传算法为主题的国际会议一度非常活跃.研究者们意识到, 对复杂问题求最优解常常是不现实的, 遗传算法在寻求近似解中则可大展身手
38、, 因为任何数学理论与证明都不会比自然界中生物遗传进化的客观事实更有效用与说服力. 4.2遗传算法的特点归纳来讲, 遗传算法与其他优化算法相比主要有四大特点. 其一, 遗传算法对决策变量的编码进行运算, 传统优化算法则往往直接计算决策变量的实际值. 对决策变量的进行编码处理使借鉴遗传学中染色体和基因的概念以模仿自然界生物遗传进化机理有了可能, 尤其是对于无数值概念的优化问题, 编码处理方式显示了其不可替代的优越性；其二, 遗传算法可直接搜索目标函数, 而传统优化算法还往往需要其他辅助信息（如导数值）. 遗传算法仅由适应度函数值（由目标函数值变换而来）便可进一步确定搜索范围, 这一特点使得对难以
39、求导（或导数不存在）的目标函数的优化问题的求解便捷了许多；其三, 遗传算法同时使用多点搜索, 而传统优化算法则是从解空间某初始点开始迭代搜索以寻求最优解, 而单个搜索点所提供的搜索信息限制了算法的搜索效率, 甚至于陷入局部最优解而停滞不前. 遗传算法从初始群体而非单一个体开始搜索, 对初始群体进行的选择、交叉及变异等运算产生出新一代的群体, 其中必然包括诸多群体信息, 从而可避免搜索那些不必搜索的点, 实质则相当于搜索了更多的点, 我们称其为遗传算法特有的“隐含并行性”；其四, 遗传算法使用概率搜索, 而很多传统优化算法更多是用确定性的搜索算法, 这无疑限制了算法的应用范围. 4.3基本遗传算
40、法的主要思想及术语自然界中的生物体在演进过程中通过遗传变异来适应环境并发展进化, 遗传算法模拟了这一进化现象. 在遗传算法中, 我们将问题的解空间映为遗传空间, 所谓向量是由空间中每个可能的解编码得到, 亦称为一个染色体, 群体由全体染色体所组成, 并依预先给定的适应度函数评价群体中的每个染色体, 从而给出其适应度. 算法初始化时染色体随机产生并计算其适应度, 然后根据适应度的取值对其进行遗传操作以筛除适应度低的染色体, 从而得到新的群体. 经此反复迭代, 群体将不断进化, 直到满足预先给定的优化指标，即得到了所求的最优解. 作为计算机科学与遗传学相互结合渗透的产物, 遗传算法借用了一些生物学
41、上的基础术语. 如群体(Population)和个体(Individual), 染色体作为个体是遗传算法的处理对象, 以一维串结构数据表示, 若干个体组成的集合成为群体, 也称为集团. 群体规模表示群体中个体的数量. 适应度, 顾名思义为个体对外部环境的适应程度, 适应度函数在优化问题中即为目标函数. 4.4 基本遗传算法的描述与形式化定义在遗传算法中, 我们以表示维决策向量. 其中每个元素可视作一个遗传基因, 其所有可能取值称为等位基因, 从而可被视作由若干遗传基因组成的一个染色体, 遗传算法的解空间由决策变量组成. 遗传算法以所谓遗传算子(GeneticOperators)作用于群体, 与
42、生物进化过程中染色体的交叉与变异对应的，有选择(Selection)算子、交叉(Crossover)算子和变异(Mutation)算子. 只使用这三种基本算子的遗传算法我称为基本遗传算法(SimpleGeneticAlgorithms, SGA), 构成其四要素为染色体编码、个体适应度评价、遗传算子及运行参数. 基本遗传算法可形式化定义为一个由八个元素组成的组, 即, 其中, 表示染色体的编码方法, 表示染色体的适应度评价函数, 表示初始群体, 表示群体大小, 表示选择算子, 表示交叉算子, 表示变异算子, 表示终止条件. 4.5 遗传算法的基本实现技术及设计步骤4.5.1编码方法的选取迄今各
43、个领域应用于遗传算法的编码技术主要有二进制、浮点数编码、可变染色体长度编码及树结构编码. 以下我们对以上编码方法作简要介绍. 二进制编码作为一种一维染色体编码方法, 将参数从搜索空间转换到遗传空间后染色体呈一维排列. 二进制编码方法对多维且精度要求高的连续函数优化存在离散化映射误差, 为克服这一缺点人们提出所谓浮点数编码方法, 即用浮点数表示个体基因值, 个体编码长度就是其决策变量个数, 由于这里使用的是决策变量的真实值, 故浮点数编码方法也称真值编码方法. 我们知道, 生物进化过程中生物的染色体长度并非是固定不变的, 为描述这一现象, Goldberg等人提出了一种可变长度的染色体编码方法用
44、以克服基本遗传算法在处理非线性问题上的不足, 除此之外还可以提高函数优化及算法搜索性能, 从而提高短距模式下的检测与重组效率. 然而, 以上编码方法在诸多应用场合已显现出若干不足之处, 如所求问题之结构层次难于个体所表示, 且问题的解须经特定编码与解码技术才能表示为合适的形式, 最重要的, 以上编码方法在表示高层次知识及相应学习系统方面显得余力不足. 在实际应用中, 由于很多问题本身可由结构方式描述, 故可将其结构表示直接作为染色体处理, 总而省去编码译码操作. 4.5.2 适应度函数的设计遗传算法中设计适应度函数有一些基本准则, 其适应度函数并不需要满足连续可微条件, 且其定义域可为任意集合
45、. 在处理规模较小群体的遗传算法进化初期, 常出现占群体比例极高的异常个体, 这一现象可能导致未成熟收敛, 进一步影响算法的全局优化. 除此之外, 在进化过程中群体平均适应度接近最佳时即使仍存在个体多样性, 但因个体间竞争减弱使得最佳个体无法获得被优先选择的机会, 导致优化过程趋于随机漫游. 对于未成熟收敛现象, 可缩小适应度函数值以削弱异常个体竞争力；相应对于随机漫游现象, 可放大适应度函数值以促进个体间竞争. 称这种对适应度的缩放调整为适应度定标,常见定标方式有线性定标、截断及乘幂标. 4.5.3 遗传算法的设计步骤步骤一, 确定决策变量及约束条件；步骤二, 建立优化模型及其数学描述形式（量化方法）；步骤三, 确定染色体编码与解码方法；步骤四, 确定对适应度的量化评价方法；步骤五, 设计遗传算予；步骤六, 确定运行参数. 第五章 基于遗传算法的关联规则挖掘模型目前已有的针对关联规则发掘的算法主要是R.Agrawal等提出的
