基于简单遗传算法的分类系统

基于简单遗传算法的分类系统摘要遗传算法是一种模拟生物进化过程的自适应全局优化算法，是解决现代非线性优化问题的一种重要方法。作为一种全局优化算法，遗传算法很适合于数据挖掘工作。数据挖掘就是从大量的数据中提取或者“挖掘”知识，从而实现对数据资源的有效利用，为决策者提供决策参考。分类是数据挖掘中一种重要的挖掘算法,它可用于抽取能够描述重要数据集合或预测未来数据趋势的模型。本文在学习数据挖掘和遗传算法的基础上，重点研究了遗传算法在数据挖掘中的应用，并结合实例寿险促销实现了遗传算法的有指导分类，同时对遗传算法的无指导分类如何实现进行了介绍，最后总结了遗传算法在数据挖掘中的应用，以及系统的缺陷。关键词：数据挖掘；遗传算法；有指导分类；无指导分类ABSTRACTGeneticAlgorithmisaadaptiveglobaloptimizationalgorithm,whichsimulatesbiologicalevolution.Besides,itisalsoanimportantmethodthatsolvesnonlinearoptimizationproblems.Asaglobaloptimizationalgorithm,GeneticAlgorithmisstronglyrecommendedtoapplytoDataMining.DataMiningmeansthatextractingor“mining”knowledgefromlargequantitiesofdata,sodataresourcecanbetookadvantageofanddecisionmakerscanbeprovideddecisionreferences.ClassificationisakindofimportantMiningAlgorithminDataMining,whichcanapplytothemodelthatextractsimportantdatasetsorpredictsfuturedatatrend.BasedonthestudyofDataMiningandGeneticAlgorithm,GeneticAlgorithminDataMiningisdiscussedindetailinthispaper.Besides,itdiscussesguidedclassificationinGeneticAlgorithmthatisrelatedtoexampleLifeInsurancePromotion.Meanwhile,itintroduceshowtoimplementunguidedclassificationinGeneticAlgorithminbrief.Finally,itsummarizesGeneticAlgorithmApplicationinDataMiningandthissystem’sdisadvantagesanddefects.Keywords:DataMining;GeneticAlgorithm;guidedclassification;unguidedclassificationPAGE7目录第1章前言 11.1研究背景 11.1.1数据挖掘的研究背景 11.1.2遗传算法的研究背景 11.2课题的目的和意义 21.3研究现状 21.3.1数据挖掘的研究现状 21.3.2遗传算法的研究现状 3第2章数据挖掘 52.1数据挖掘的产生 52.2数据挖掘的概念 52.3数据挖掘的分类 62.4数据挖掘中的分类算法 82.5数据挖掘的发展趋势 9第3章遗传算法 103.1遗传算法的产生和发展 103.2遗传算法的有关概念 113.3遗传算法的特点 123.4遗传算法基本原理 133.4.1遗传算法基本原理概述 133.4.2遗传算子 143.5遗传算法的步骤 16第4章遗传算法在数据挖掘中的应用 194.1遗传算法与数据挖掘 194.2遗传算法与有指导分类 194.3遗传算法与无指导分类 22第5章软件实现 245.1软件开发环境 245.2软件功能 245.3软件设计 255.4软件实现难点 255.4.1寿险促销的应用 255.4.2无指导分类的实现 265.5核心算法实现 27第6章结论 296.1系统特点 296.2进一步的工作 296.3开发心得 30致谢 31参考文献 321第1章前言1.1研究背景1.1.1数据挖掘的研究背景随着信息技术的高速发展，计算机的广泛应用,网络的飞速发展,电子数据管理方法不断涌现，数据库应用的规模、范围和深度已经从点（单台机器）发展到面（网络），甚至到Internate全球信息系统，使得无论是商业、企业、科研机构或是政府部门，在过去若干年的时间里都积累了海量的、不同形式存储的数据资料，这些大量的数据中包含了富有价值的信息,如趋势和模式，可以用于改进和优化事务决策.如何从这些海量数据中准确发现决策支持信息的迫切需求。这些资料十分繁杂，传统的数据库查询方法已经捉襟见肘，仅仅依靠数据库的查询检索机构和统计方法已经远远不能满足现实的需要，因此它迫切要求自动地和智能地将待处理的数据转化为有用的信息和知识，从而达到为决策服务的目的。在这种情况下，一种新的技术——数据挖掘技术应用而生。数据挖掘正是为了迎合这种需要而产生并迅速发展起来的、用于开发信息资源的、一种新的数据处理技术。通过研究数据挖掘，为决策者提供了重要的、极有价值的信息或知识，带来不可估量的效益。主要表现在它为大量数据的利用提供了有效工具，将数据坟墓转换成知识“金块”。数据挖掘理论与算法研究探索出了许多独具特色的理论体系。但是，这决不意味着挖掘理论的探索已经结束：一方面，在这些大的理论框架下有许多面向实际应用目标的挖掘理论等待探索和创新；另一方面，随着数据挖掘技术本身和相关技术的发展，新的挖掘理论的诞生是必然的，而且可能对特定的应用产生推动作用。新理论的发展必然促进新的挖掘算法的产生，这些算法可能扩展挖掘的有效性。1.1.2遗传算法的研究背景遗传算法，在解决大空间、多峰值、非线性、全局优化等高复杂度问题时显示了独特的优势，它是J.H.Holland于1975年提出的一种基于进化论的原理发展起来的高效的随机搜索与优化的方法，其应用范围几乎涉及到用传统的优化方法难以解决的优化问题，在工业工程、经济管理、交通运输、工业设计等许多领域里获得了广泛的应用。它以适应度值函数为依据，通过对群体个体世家遗传操作来实现群体内个体结构的优化重组，在全局范围内逼近最优解。遗传算法作为一种有效的全局并行优化搜索工具，在数据挖掘方面的应用得到了极大的重视。遗传算法在应用于决策树、分类器和模糊规则的获取等方面的文献不断涌现，因此遗传算法是数据挖掘领域的一个重要研究课题。1.2课题的目的和意义随着计算机的广泛应用,网络的飞速发展,电子数据管理方法不断涌现，数据库系统几乎在所有大中型企业得到应用。这些大量的数据中包含了富有价值的信息,如趋势和模式，可以用于改进和优化事务决策.如何从这些海量数据中准确发现决策支持信息的迫切需求，传统的数据库查询方法已经捉襟见肘，从而使数据库中知识发现(KDD)和数据挖掘技术(DM)应运而生。作为一种非常有效的优化方法，遗传算法(GA)也在数据挖掘中得到了广泛应用。当今，国家政府越来越重视民生问题，但是中国人口数量巨大，让国家来负担每个人福利是不现实的，所以购买保险成为一种保障措施，此时保险业得到发展，保险公司之间的竞争势必变得激励，决策者就需要想办法赢得客户的青睐，以前存放在数据库里的购买保险的数据就成为依据，数据挖掘据成为决策者的工具，而遗传算法可以作为核心算法。1.3研究现状1.3.1数据挖掘的研究现状目前国际上数据挖掘技术在科学研究、金融投资、市场营销、保险、医疗卫生、产品制造业、通信网络管理等行业已得到应用，如宝钢已应用数据挖掘系统辅助生产决策，每年能节省近千万元的资金。现在我国的研究人员正在加紧研制有关领域的数据挖掘工具，且数据挖掘技术的应用领域正在不断扩大。1.3.2遗传算法的研究现状进入90年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。尤其是遗传算法的应用研究显得格外活跃，不但它的应用领域扩大，而且利用遗传算法进行优化和规则学习的能力也显著提高，同时产业应用方面的研究也在摸索之中。此外一些新的理论和方法在应用研究中亦得到了迅速的发展，这些无疑均给遗传算法增添了新的活力。遗传算法的应用研究已从初期的组合优化求解扩展到了许多更新、更工程化的应用方面。随着应用领域的扩展，遗传算法的研究出现了几个引人注目的新动向：一是基于遗传算法的机器学习，这一新的研究课题把遗传算法从历来离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法。这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望。二是遗传算法正日益和神经网络、模糊推理以及混沌理论等其它智能计算方法相互渗透和结合，这对开拓21世纪中新的智能计算技术将具有重要的意义。三是并行处理的遗传算法的研究十分活跃。这一研究不仅对遗传算法本身的发展，而且对于新一代智能计算机体系结构的研究都是十分重要的。四是遗传算法和另一个称为人工生命的崭新研究领域正不断渗透。所谓人工生命即是用计算机模拟自然界丰富多彩的生命现象，其中生物的自适应、进化和免疫等现象是人工生命的重要研究对象，而遗传算法在这方面将会发挥一定的作用，五是遗传算法和进化规划（EvolutionProgramming,EP）以及进化策略（EvolutionStrategy,ES）等进化计算理论日益结合。EP和ES几乎是和遗传算法同时独立发展起来的，同遗传算法一样，它们也是模拟自然界生物进化机制的智能计算方法，即同遗传算法具有相同之处，也有各自的特点。目前，这三者之间的比较研究和彼此结合的探讨正形成热点。中国石油大学（华东）本科毕业设计（论文）11第2章数据挖掘2.1数据挖掘的产生数据挖掘是因为海量有用数据快速增长的产物。考虑到通过计算机进行历史数据分析，1960年代数字方式采集数据已经实现。1980年代关系数据库随着能够适应动态按需分析数据的结构化查询语言(\o"SQL"SQL)发展起来。\o"数据仓库"数据仓库开始用来存储大量的数据。数据挖掘因面临的需要处理的\o"数据库"数据库中的海量数据严峻挑战应运而生,对于这些问题它的主要方法是数据统计分析和\o"人工智能"人工智能搜索技术。同时，数据挖掘引起了信息产业界的极大关注，其主要原因是由于广泛存在可以使用的大量数据，并且迫切需要将这些数据转换成有用的信息和知识，从而被商务管理、生产控制、市场分析、工程设计和科学探索等应用。通过研究数据挖掘，为决策者提供了重要的、极有价值的信息或知识，带来不可估量的效益。主要表现在它为大量数据的利用提供了有效工具，将数据坟墓转换成知识“金块”。遗传算法作为数据挖掘的一种重要算法，在解决大空间、多峰值、非线性、全局优化等高复杂度问题时显示了独特的优势，它是J.H.Holand于1975年提出的一种基于进化论的原理发展起来的高效的随机搜索与优化的方法，其应用范围几乎涉及到用传统的优化方法难以解决的优化问题，在工业工程、经济管理、交通运输、工业设计等许多领域里获得了广泛的应用。2.2数据挖掘的概念数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的实际数据中提取隐含在其中的、人们不知道的、但又是潜在有用的信息和知识的过程；从商业的角度来看，数据挖掘是一种崭新的商业信息处理技术，其主要的特点是对商业数据库中大量业务数据进行抽取、转化、分析和模式化处理，从中提取辅助商业决策的关键知识，即从一个数据库中发现相关商业模式，简单地说，数据挖掘就是在数据中发现模式。2.3数据挖掘的分类数据挖掘技术的分类标准有根据发现知识的种类分类、根据挖掘的数据库种类分类、根据采用的技术分类等几种分类方法。根据发现知识的种类分类：根据数据挖掘的功能可分为特征规则挖掘、区分规则挖掘、关联规则挖掘、分类聚类挖掘、孤立点分析、趋势分析、演变分析、偏差分析、模式分析、类似性分析等。按照所挖掘的知识的粒度或抽象层进行区分，包括概化知识、原始知识或多层知识的数据挖掘。根据挖掘的数据库分类：按数据库类型可分为关系型、事务型、面向对象型、对象关系型、主动型、异构型。根据所处理的数据的特殊类型可分为时间型、空间型、文本型、多媒体、数据库和遗留系统等。根据数据挖掘采用的技术分类主要有如下几种：决策树方法，用树形结构表示决策集合，利用信息论中的互信息（信息增益）寻找数据库中具有最大信息量的字段建立决策树的一个结点，再根据字段的不同取值建立树的分支，即可建立决策树。国际上最优影响和最早的决策树算法是Quiulan研制的ID3方法，数据库越大它的效果越好。此后又发展了各种决策树方法，如ID3的改进算法C4.5和C5,这两种算法从数据丢失和数据连续性等方面对ID3算法进行了改进。人工神经网络方法，它从结构上模拟生物神经网络，是一种通过训练来学习的非线性预测模型，可以完成分类、聚类、特征挖掘等多种数据挖掘任务。这种方法是以MP模型和Hebb学习规则为基础，用神经网络连接的权值表示知识，其学习方法表现在神经网络的权值修改上。神经网络方法主要应用于数据挖掘的聚类技术中。粗糙集（RoughSet）方法在数据库中，将行元素看成对象，列元素看成属性（分为条件属性和决策属性），等价关系R定义为不同对象在某个（或几个）属性上取值相同，这些满足等价关系的对象组成的集合称为该等价关系R的等价类。条件属性上的等价类E与决策属性上的等价类Y之间有3种情况：下近似，Y包含E；上近似，Y和E的交非空；无关，Y和E的交为空。对下近似建立确定性规则，对上近似建立不确定性规则（含可信度），对无关情况不存在规则。可视化技术，通过直观的图形方式将信息数据、关联关系以及发展趋势呈现给决策者，使用最多的方法是直方图、数据立方体、散点图。其中数据立方体可以通过OLAP操作将更多用户关心的信息反映给用户。遗传算法，是一种模拟生物进化过程的算法，最造由Holland于20世纪70年代提出。它是基于群体的、具有随机和定向搜索特征的迭代过程，包括4种典型的算子：遗传、交叉、变异和自然选择。遗传算法作用于一个由问题的多个潜在解（个体）组成的群体上，并且群体中的每个个体都由一个编码表示，同时个体均需依据问题的目标函数而被赋予一个适应值。另外，为了应用遗传算法，还需要把数据挖掘任务表达为一种搜索的问题，以便发挥遗传算法的优势搜索能力。同时可以用遗传算法中的交叉、变异完成数据挖掘中用于异常数据的处理。统计学方法，在数据字段项之间存在着两种关系：函数关系（能用函数公式表示的确定性关系）和相关关系（不能用函数公式表示，但仍是相关确定关系）。对它们的分析采用如下方法：回归反洗、相关分析、主成分分析。主要用于数据挖掘的聚类方法中。模糊集（Fuzzyset）方法，利用模糊集理论对实际问题进行模糊评判、模糊决策、模糊模式识别和模糊聚类分析。模糊性是客观存在的。系统的复杂性越高，精确化能力就越低，即模糊性就越强，这是Zadeh总结出的互克性原理。2.4数据挖掘中的分类算法分类技术针对数据集构造分类器，从而对未知类别样本赋予类别标签。在其学习过程中和无监督的聚类相比，一般而言，分类技术假定存在具备环境知识和输入输出样本集知识的，但环境及其特性、模型参数等却是未知的。判定树的归纳分类，由判定树可以很容易得到“IFTHEN”形式的分类规则。方法是沿着由根节点到树叶节点的路径，路径上的每个属性-值对形成“IF”部分的一个合取项，树叶节点包含类预测，形成“THEN”部分。一条路径创建一个规则。贝叶斯分类是统计学的分类方法，基于贝叶斯公式即后验概率公式。朴素贝叶斯分类的分类过程是首先令每个数据样本用一个N维特征向量建立贝叶斯信念网络可以被分为两个阶段。第一阶段网络拓扑学习，即有向非循环图的学习，利用贝叶斯网络的学习算法，从实例数据建立所有属性变量和类变量构成的贝叶斯网结构。第二个阶段网络中每个变量的局部条件概率分布的学习，采用贝叶斯网的推理算法，计算给定属性变量的值时类变量的最大后验概率。采用这种分类思想的算法有TAN(treeaugmentedBayesnetwork)算法。但是统计上的贝叶斯分类对非线性样本数据，含噪声、孤立点的数据，在分类准确性上仍存在问题。粗糙集(roughset)，粗糙集理论将分类能力和知识联系在一起，使用等价关系来形式化地表示分类，知识因而表示为等价关系集R对离散空间U的划分。粗糙集理论还包含求取数据中最小不变集和最小规则集的理论，即约简算法(即分类中属性约简和规则生成)，其基本原理是通过求属性的重要性并排序，在泛化关系中找出与原始数据具有同一决策或分辨能力的相关属性的最小集合，以此实现信息约简，这也是粗糙集理论在分类中的主要应用。遗传算法，遗传算法综合了定向搜索与随机搜索的优点，避免了大多数经典优化方法基于目标函数的梯度或高阶导数而易陷入局部最优的缺陷，可以取得较好的区域搜索与空间扩展的平衡。在运算时随机的多样性群体和交叉运算利于扩展搜索空间；随着高适应值的获得，交叉运算利于在这些解周围探索。遗传算法由于通过保持一个潜在解的群体进行多方向的搜索而有能力跳出局部最优解。遗传算法的应用主要集中在分类算法等方面。2.5数据挖掘的发展趋势当前，数据挖掘知识发现的研究方兴未艾，数据挖掘研究人员、系统和应用开发人员所面临的主要问题是高效而有效的数据挖掘开发和系统开发，交互和集成的数据挖掘环境的建立，以及如何应用挖掘技术解决大型应用问题。研究的焦点可能会聚集在以下几方面：数据挖掘语言的形式化描述：即研究专门用于知识发现的数据挖掘语音，也许会像SQL语言一样走向形式化和标准化。可视化数据挖掘：是从大量数据中发现知识的有效途径，它使数据挖掘的过程能够被用户理解，也便于在数据挖掘过程中进行人机交互，该技术将有助于推进数据挖掘作为数据分析的基本工具。多媒体数据挖掘：是指从大量的文本数据、图形数据、视频图像数据、音频数据乃至综合多媒体数据的开采中，通过分析语义和视听特征，发现其中隐含的、有价值的模式。它和传统的数据挖掘方法中处理的数据不同，传统的数据挖掘处理的数据是非结构化的数据。Web数据挖掘：主要是利用数据挖掘技术从web文档及web服务器中自动发现并提取有用信息的过程。Web上有海量数据，这些数据最大特点是半结构化。那么开发新的Web挖掘技术以及对Web文档进行预测处理以得到关于文档的特征表示，就成为Web挖掘的重点。数据挖掘中的隐私与信息安全：随着数据挖掘工具和电信与计算机网络的日益普及，数据挖掘要面对的一个重要问题就是隐私保护和信息安全。需要进一步开发以便在适当的信息访问和挖掘中确保隐私保护与安全。第3章遗传算法3.1遗传算法的产生和发展达尔文的自然选择学说是一种被人们广泛接受的生物进化学说。这种学说认为，生物要生存下去，就必须进行生存斗争。生存斗争包括种内斗争、种间斗争以及生物跟无机环境之间的斗争三个方面。在生存斗争中，具有有利变异的个体容易存活下来，并且有更多的机会将有利变异传给后代；具有不利变异的个体就容易被淘汰，产生后代的机会也少的多。因此，凡是在生存斗争中获胜的个体都是对环境适应性比较强的。达尔文把这种在生存斗争中适者生存，不适者淘汰的过程叫做自然选择。它表明，遗传和变异是决定生物进化的内在因素。自然界中的多种生物之所以能够适应环境而得以生存进化，是和遗传、变异生命现象分不开的。正是生物的这种遗传特性，使生物界的物种能够保持相对的稳定；而生物的变异特性，使生物个体产生新的性状，以致于形成新的物种，推动了生物的进化和发展。遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。它的思想源于生物遗传学和适者生存的自然规律，是具有“生存＋检测”的迭代过程的搜索算法。1975年，美国Michigan大学的John.Holland在他的著作《AdaptationinNaturalandArtificialSystems》中提出了遗传算法(GeneticAlgorithm,GA)，成为演化计算的一个主要研究分支。而遗传算法的概念最早是由Bogley.J.D在1967年提出的。遗传算法提出之初，计算机的发展水平还比较低。那时的计算机容量小，计算速度慢，而遗传算法要求的计算量很大，需要存储的信息量多，因此在当时难以实际应用。20世纪80年代以来，随着计算机的不断发展，计算机的容量不断增大，计算速度也不断提高。而与此同时，遗传算法本身也不断成熟，越来越多的进入了实际应用。3.2遗传算法的有关概念遗传算法是根据Darwin进化论和Mendal的遗传学说生物进化思想而启发得到的一种全局优化算法，是仿真生物遗传学和自然选择机理，通过人工方式所构造的一类搜索算法，从某种程度上说遗传算法是对生物进化过程进行的数学方式仿真。遗传算法从试图解释自然系统中生物的复杂适应过程入手，模拟生物进化的机制来构造人工系统的模型。它是基于进化理论,采用遗传结合、遗传变异以及自然选择等设计方法的优化技术。遗传算法模拟进化，适者生存的过程，以随机的形式将最适合指定目标函数的种群通过重组产生新的一代。生物种群的生存过程普遍遵循达尔文进化准则，群体中的个体根据对环境的适应能力而被大自然所选择或淘汰。进化过程的结果反映在个体的结构上，其染色体包含若干基因，相应的表现型和基因型的联系体现了个体的外部特性与内部机理间逻辑关系。通过个体之间的交叉、变异来适应大自然环境。生物染色体用数学方式或计算机方式来体现就是一串数码，仍叫染色体，有时也叫个体；适应能力是对应着一个染色体的一个数值来衡量；染色体的选择或淘汰则按所面对的问题是求最大还是最小来进行。遗传算法的有关概念：染色体(Chromosome)，染色体又可以叫做基因型个体(individuals),一定数量的个体组成了群体(population),群体中个体的数量叫做群体大小。基因(Gene)，基因是串中的元素，基因用于表示个体的特征。例如有一个串S＝1011，则其中的1，0，1，1这4个元素分别称为基因。它们的值称为等位基因(Alleles)。基因地点(Locus)，基因地点在算法中表示一个基因在串中的位置称为基因位置(GenePosition)，有时也简称基因位。基因位置由串的左向右计算，例如在串S＝1101中，0的基因位置是3。基因特征值(GeneFeature)，在用串表示整数时，基因的特征值与二进制数的权一致；例如在串S=1011中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。适应度值，各个个体对环境的适应程度叫做适应度(fitness)。为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数。这个函数是计算个体在群体中被使用的概率。3.3遗传算法的特点遗传算法是解决搜索问题的一种通用算法，对于各种通用问题都可以使用。搜索算法的共同特征为：首先组成一组候选解；依据某些适应性条件测算这些候选解的适应度；根据适应度保留某些候选解，放弃其他候选解；对保留的候选解进行某些操作，生成新的候选解。在遗传算法中，上述几个特征以一种特殊的方式组合在一起：基于染色体群的并行搜索，带有猜测性质的选择操作、交换操作和突变操作。这种特殊的组合方式将遗传算法与其它搜索算法区别开来。遗传算法还具有以下几方面的特点：遗传算法从问题解的串集开始嫂索，而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，覆盖面大，利于全局择优。许多传统搜索算法都是单点搜索算法，容易陷入局部的最优解。遗传算法同时处理群体中的多个个体，即对搜索空间中的多个解进行评估，减少了陷入局部最优解的风险，同时算法本身易于实现并行化。遗传算法基本上不用搜索空间的知识或其它辅助信息，而仅用适应度函数值来评估个体，在此基础上进行遗传操作。适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。这一特点使得遗传算法的应用范围大大扩展。遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导他的搜索方向。具有自组织、自适应和自学习性。遗传算法利用进化过程获得的信息自行组织搜索时，硬度大的个体具有较高的生存概率，并获得更适应环境的基因结构。3.4遗传算法基本原理3.4.1遗传算法基本原理概述遗传算法是建立在自然选择和群体遗传学机理基础上的随机、选代、进化，具有广泛适用性的搜索方法，所有的自然种类都是适应环境而得以生存，这一自然适应性是遗传算法的主旋律，遗传算法结合了达尔文适者生存和随机信息交换，前者消除了解中不适应因素，后者利用了原有解已有的知识，从而有力地加快了搜索过程.遗传算法的基本原理是：编码，由于遗传算法不能直接处理解空间的解数据，因此在进行搜索之前，必须先通过编码把解空间变量表示成遗传空间的基因型串结构——染色体。生成初始群体，遗传算法是群体型操作算法，在对解空间变量进行编码后，紧接着就要随机产生N个染色体，构造遗传算法的初始群体，然后以这个初始群体作为起始点开始迭代搜索。计算个体适应度，遗传算法在搜索进化过程中一般不需要其它外部信息，仅用适应度函数值来评估个体或解的优劣。选择，选择操作的目的是为了从当前群体中选出生命力强的染色体，使它有机会保留用以繁殖后代。判断染色体优良与否的准则就是各自的适应度值，个体适应度值越大，其被选择的机会就越多。交叉（Crossover），交叉操作是遗传算法中最主要的遗传操作，对于选中用于繁殖后代的个体，随机选择交叉位置k，交换两个基因串位置k右边的部分，产生两个新的个体，这两个新个体组合了其父代的特性。变异（Mutation），选择和交叉基本上完成了遗传算法的大部分搜索功能，而变异则增加了遗传算法找到接近最优解的能力，变异首先在群体中随机地选择一个个体，以一定的概率随机改变基因串中某个字符的值，变异操作是按位进行的，对于采用二进制编码的个体来说就是将1变为0或将0变为1，变异发生的概率极低（一般取值为0.0001-0.1之间），它本身是一种随机搜索，但与选择、交叉算子结合在一起，就能避免由复制和交叉算子一起的某些信息的永久丢失，从而保证了遗传算法的有效性。3.4.2遗传算子选择选择算法：轮盘赌选择，随机遍历抽样，局部选择，截断选择，锦标赛选择轮盘赌选择算法：如图3-1所示。Fitness值：220018001200950400100选择概率：0.3310.2710.180.1430.060.015图3-1轮盘赌选择交叉交叉也叫基因重组，是结合来自父代交配种群中的信息产生新的个体。依据个体编码表示方法的不同，可以有实值重组算法和二进制交叉算法。实值重组算法：离散重组，中间重组，线性重组，扩展线性重组二进制交叉算法：单点交叉，多点交叉，均匀交叉，洗牌交叉，缩小代理交叉单点交叉：如表3-2所示。表3-2单点交叉Crossover11110000Crossover11110000S110001111S211101100P110001100P211101111变异这是在选中的个体中，将新个体的基因链的各位按概率pm进行异向转化，最简单方式是改变串上某个位置数值。对二进制编码来说将0与1互换：0变异为1，1变异为0。如下8位二进制编码：11101100随机产生一个1至8之间的数i，假如现在k=6，对从右往左的第6位进行变异操作，将原来的1变为0，得到如下串：11001100整个交叉变异过程，如图3-2所示。

图3-2交叉变异过程3.5遗传算法的步骤编码：对待解决问题进行编码，我们将问题结构变换为位串形式编码表示的过程；而相反将位串形式编码表示变换为原来问题结构的过程叫译码；随机初始化群体；计算群体上每个个体的适应度值；评估适应度：对当前群体中每个个体计算其适应度，适应度表示了该个体的性能的好坏；按由个体适应度值所决定的某个规则应用选择算子产生中间代Pr(t)；依照Pc选择个体进行交叉操作；仿照Pm对繁殖个体进行变异操作；满足停止条件？没有满足某种停止条件，则转第3步，否则进入9；输出种群中适应度值最优的个体；遗传算法流程：如图3-3所示。开始开始条件终止？输出适应度最优群体结束初始化群体计算适应度值选择操作交叉操作变异操作图3-3遗传算法流程图基本遗传操作(SGA)可以定义为一个8元组SGA=(C,E,P0,M,Φ,Г,Ψ,Τ)C－个体的编码方法，SGA使用固定长度二进制符号串的编码方法；E－个体的适应度评价函数；P0－初始群体；M－群体大小，一般取20～100；Φ－选择算子，SGA使用比例选择算子；Г－交叉算子，SGA使用单点交叉算子；Ψ－变异算子，SGA使用基本位变异算子；Τ－算法终止条件，一般终止进化代数为100～500。第4章遗传算法在数据挖掘中的应用4.1遗传算法与数据挖掘遗传算法是数据挖掘的主要算法之一。遗传算法作为一种有效的全局并行优化搜索工具已被众多应用领域接受，它在数据挖掘方面的应用也得到了极大的重视。遗传算法应用于决策树、分类器和模糊规则的获取等方面的文献不断涌现，因此遗传算法是数据挖掘领域的一个重要研究课题。4.2遗传算法与有指导分类遗传算法与有指导分类的一个例子例：寿险促销将基于简单遗传算法的分类系统用于寿险促销上：条件属性；收入，信誉度，性别，年龄决策属性：是否参加寿险促销目的：创建一个模型，能够区分是否接受寿险促销最后就是要产生一个规则，描述为：if收入在50-60w之间∧信誉度为yes∧性别为男∧年龄在40-49之间then接受寿险；if收入在20-30w之间∧信誉度为no∧性别为男∧年龄在20-29之间then不接受寿险。有指导遗传学习过程：如图4-1所示。种群元素种群元素训练数据交叉和变异的候选数据保留抛出适应度函数图4-1有指导遗传学习过程选择初始种群要求每次迭代后，每个类恰有两个元素留在种群中初始种群数据如表4-1所示。表4-1初始种群数据元素收入寿险信誉性别年龄120-30wNOYES男30-39230-40wYESNO女50-593？NONO男40-49430-40wYESYES男40-49训练种群数据如表4-2所示。表4-2训练种群数据元素收入寿险信誉性别年龄130-40wYESYES男30-39230-40wYESNO女40-49350-60wYESNO女30-39420-30wNONO女50-59520-30wNONO男20-29630-40wNONO男40-49定义适应度函数对于一个单一元素E，其适应度函数定义如下：设N为E的输入属性值与同类中训练实例匹配的个数；设M为输入属性值与竞争类中训练实例匹配的个数；M加1；用N除以M；计算每个元素的适应度值：元素1是寿险为“NO”的成员，因此N就是元素1与训练数据集中寿险为“NO”的成员匹配的个数收入20-30w与训练实例4，5匹配(2)没有与信誉为“YES”匹配的实例(0)性别为“男”与训练实例5，6匹配(2)没有与年龄为“30-39”匹配的实例(0)因此N的值为4通过元素1和训练实例1，2，3比较确定M没有与收入为“20-30w”匹配实例(0)信誉为“YES”与实例1匹配(1)性别为“男”与实例1匹配(1)年龄为“30-39”实例1，3匹配(2)因此M的值为4，M=4+1=5所以:F(1)=4/5=0.80同理可计算元素2，3，4的适应度值F(1)=4/5=0.80F(2)=6/7=0.86F(3)=6/5=1.20F(4)=5/5=1.00淘汰种群中子集并使用遗传算法来创建新的元素元素1和2执行交叉前的属性数据，如表4-3所示。表4-3元素1和2执行交叉前的属性数据元素收入寿险信誉性别年龄120-30wNOYES男30-39230-40wYESNO女50-59元素1和2执行交叉后的属性数据，如表4-4所示。表4-4元素1和2执行交叉后的属性数据元素收入寿险信誉性别年龄120-30wNONO女50-59230-40wYESYES男30-39新一代种群数据，如表4-5所示。表4-5新一代种群数据元素收入寿险信誉性别年龄120-30wNONO女50-59230-40wYESYES男30-393？NONO男40-49430-40wYESYES男40-49继续执行交叉和变异，直到满足终止条件为止。算法结束后，就得到一个模型，可适当分类新的实例或预测未来结果。将未知元素划分为种群中最相似元素所在的类，找到与要分类的实例最相似的m个元素，然后，算法任意选择这m个元素中的一个，并将未知实例划归该元素所在的类。4.3遗传算法与无指导分类假设空间内有P个数据实例，每个数据实例由n个属性值组成，假设需要m个簇；模型随后产生k个可能的解决方案。一个特定方案中包含m个n维点，每个点都是当前簇中最具代表性的元素；无指导遗传学习过程，如图4-2所示。PP个实例l1a1a2…anlpS1S2SkE11E12E21E22Ek1Ek2图4-2无指导遗传学习过程可通过将Si中的元素移到Sj中来实现交叉操作；对于变异，可交换Si中元素一个或多个点的坐标；Sj的适合度函数：为n维空间p个实例与Sj中最近邻元素的平均欧氏距离：即取p的每个实例I，分别计算其到Sj中m个元素的欧氏距离，最近的距离保存起来并相加后，取均值就是Sj的适应度值，显然，值越小表示适合度越好；遗传学习终止后，k个可能的解决方案中最好的一个确定为最终方案。然后，将n维空间中的每个实例指定到与最终方案中距它最近的元素所对映的簇中。实例：如表4-6所示。表4-6无指导分类实例实例xy11.01.521.04.532.01.542.03.553.02.563.06.0第5章软件实现本章主要实现第4章介绍的寿险促销和无指导分类5.1软件开发环境硬件环境：标准PC；操作系统：Windows系列；编程环境：VisualC++6.0+Access数据库。程序模块，如图5-1所示寿险（有指导学习）寿险（有指导学习）无指导学习遗传算法分类系统设置参数产生分类规则对新数据分类查看算法不同参数下性能数据库管理设置参数开始分类图5-1程序模块5.2软件功能明确目标：本软件重点在于实现简单遗传算法，将简单遗传算法应用在寿险促销上，在应用实践的过程中研究遗传算法的性能，实践在不同的参数下遗传算法的收敛性。寿险促销（有指导分类）：数据库管理功能：实现对例子寿险促销的数据库里的训练数据添加、删除和修改的功能；产生分类规则：根据输入的参数产生分类寿险促销的规则；输入待分类数据：输入待分组的条件属性；查看遗传算法的性能：在不同参数（交叉率和变异率）下遗传算法得到结果时所需要的运行次数和进化代数是不一样的，通过查看得到最佳个体的运行次数和进化代数可以了解设置什么样的交叉率和变异率遗传算法的性能比较好；显示遗传算法无指导分类的分类的过程和结果：可以设置遗传算法的参数。5.3软件设计使用VC6.0的ODBC访问Access数据库，数据库里的表包括寿险促销的训练数据表和无指导分类的实例数据表。可以自行设置遗传算法的参数，包括：交叉率，变异率，进化代数，运行次数，通过设置参数，显示最后的分类规则；得到分类规则后可以输入条件属性（收入，信誉度，性别，年龄），提交后显示匹配的分类规则，并给出输入的属性与规则的相似程度，从而给决策者一个判断的依据；得到分类规则后查看遗传算法在不同参数（交叉率和变异率）下得到最佳个体，显示最佳个体的适应度，所需的运行次数和进化代数，还可以查看最佳个体的属性值；无指导分类：可以设置遗传算法的参数，显示无指导分类的分类结果，每一次进化代数的适应度值，最后显示分类结果，即每一类包含的实例。5.4软件实现难点5.4.1寿险促销的应用编码，遗传算法的第一步就是对种群中的每一个个体编码，所以编码方式影响遗传算法的整个过程。在这里考虑了二进制和实数编码，若采用二进制编码，则二进制的位数要与属性一一对应，编程困难；若采用实数编码，编程简单，但是极大地浪费存储空间。但是考虑到后面计算适应度值时要将训练种群的编码读到一个文本中，正好适用于二进制编码，实数编码的话文本所占的空间将很大。在经过试验权衡后采用二进制编码。初始化种群，最后结果是否最优和收敛的稳定性和与初始种群也有关系，当采用表4-1所给的初始种群时，结果比较稳定，而采用随机化初始种群的方法时，即使最大种群数取到800.结果还是不稳定。再通过观察发现表4-1里的每一条记录之间差异较大，数据呈现多样化。所以在随机初始化的种群也应该呈现出多样化。要求每次迭代后每个类恰有两个元素留在种群中：每个类设置一个计数器，在交叉产生两个子个体后改变计数器值，第二次交叉产生子个体后依照计数器产生个体，完成交叉变异之后如果不符合计数器要求则强制变异决策位。交叉，交叉的时候要避免近亲交叉，即父个体不能是同一个，这就要求选择的时候不能选择两个相同的父个体，要保证父个体不同，就要在选择的时候做工作，引进集合，将种群的所有个体就加入集合中，将第一次选择的个体从集合中除去，从剩下的种群个体中选择第二个父个体，这样就不会出现近亲杂交。消除最佳种群的不稳定性，采用多运行几次的方法消除，（即从头开始执行，重复执行几次）消除最后求得的最适应种群的不稳定性。这种不稳定性是由于初始种群的选取是随机的，如果随机选取的初始种群是比较恰当的，基因是多样的，则最后结果接近全局最优，如果随机选取的初始种群不恰当，且基因比较单一，则即使进化上百代，结果也可能不是最优的。5.4.2无指导分类的实现编码，通过观察表4-6中的实例数据，得出采用实数编码比较恰当，实数编码的话就不需要对数据进行译码和解码，操作方便；初始种群的产生：采用随机产生的方法，并设定产生随机数的范围为[0,10]；选择：轮盘赌选择父个体，为了避免近亲杂交，也就是选择的父个体是一个相同的个体，解决：比如说种群个体的编号构成一个集合，要使轮盘赌产生一个父个体编号之后，把这个编号从集合中排除，然后从剩余的集合中再使用轮盘赌选择编号。开始集合中的元素是：{0，1，2}；变异：变异将S1中第一个元素的y坐标和第二个元素的x坐标交换。所以说现在的变异只是交换，将变异改成既有坐标的交换，又有数值的改变（通过选择在[0,10]之间的随机数）。5.5核心算法实现简单遗传算法：设置交叉率Pc，变异率Pm，最大进化代数为m_nMaxGens，最大运行次数为m_nMaxRuns；初始运行次数为m_nRun=1；初始化最佳种群；如果(m_nRun<=m_nMaxRuns)继续向下执行，否则转到14；初始化进化代数m_nGen=0，当前种群的所有个体加入集合；随机初始化初始种群，最佳种群即为初始种群，设置m_nGen=1；如果（m_nGen<=m_nMaxGens）继续向下执行，否则转到13；依照Pc选择：将上次出去的个体加入集合，将第一次选择的父个体从集合中出去，第二次选择父个体时从剩余的个体中选