文献综述基于自适应和演化自适应组合遗传算法聚类分析.docVIP

本科毕业设计文献综述 （2014届） 论文题目 基于自适应和演化自适应的 组合遗传算法的聚类分析 作者姓名 指导教师 学科(专业) 所在学院 计算机科学与技术学院 提交日期 2014年2月 　  基于自适应和演化自适应的组合遗传算法的聚类分析 摘要：本文是关于基于自适应和演化自适应的组合遗传算法的聚类分析的一篇文献综述，先介绍项目的由来及其研究意义，然后详述一下国内外相关研究现状以及现阶段存在的技术关键及问题，最后进行简单总结与预测未来的发展趋势。 关键词：聚类分析，遗传算法，自适应，演化自适应，交叉率，变异率 一、引言 聚类是数据分析领域的常用工具，也是数据预处理的重要手段。聚类分析是依据数据内在的结构，将数据对象分成类或簇的过程，使得同一簇内的数据具有高度的相似性，不同簇内的数据具有很高的相异度[1,30]。针对不同的应用需求，已经有许多聚类算法被提出。对于大数据聚类，划分聚类已被公认为最为重要的一类方法。K-means算法[2]在众多的划分聚类方法中因其的简单高效已被广泛使用，但是存在对初始聚类中心高度依赖以及易于收敛于局部最优值等问题。 因此，介于聚类分析是一类组合优化问题以及划分聚类是已知的NP-难问题[3]，我们可以使用启发式全局优化算法来解决聚类问题。而遗传算法作为一类常见的智能优化算法，具有很高的隐含并行性，特别适用于解决复杂的非线性和多维空间寻优问题[4,5,6]。早有一些学者将遗传算法用于解聚类分析问题[7,8]。然而，遗传算法的参数会影响其性能。首先，特定的问题会有特定的参数值来决定其是否有找到最优解或者次优解的能力，再者，这些参数值存在非线性关系，所以很难找到他们的最优值。因此，如何选择正确的参数设置策略诸如交叉率和变异率是一个研究热点，也是本论文将解决的难点。 运行前固定参数和动态适应是现有的两种重要的遗传算法参数设置机制[9,10,11]。运行前参数固定方法违背了算法固有的动态性和自适应性，已很少使用。动态适应方法主要分为演化自适应控制（Self-adaptive parameter control）和自适应控制（Adaptive parameter control）两种方法。本论文将结合两种方法，提出一种新的参数设置机制用于解决聚类分析问题。 二、研究意义 演化自适应控制（Self-adaptive parameter control）和自适应控制（Adaptive parameter control）是目前应用最为广泛的两种动态适应参数设置机制。演化自适应控制通过把遗传算法的参数值编码到个体中，然后利用算法本身来确定合适的参数值。该机制的工作原理是编码在个体中合适的参数值将产生高适宜度个体，这些高适宜度个体将有高几率生存下去并产生后代，因此延续了这些合适的参数值。采用这种参数设置机制，现有多种方法来调节遗传算法的变异和/或交叉率。演化自适应控制适合于在复杂的优化问题上设置遗传算法的交叉和变异率。然而，采用该机制，算法在运行过程中其交叉和变异率往往会过快下降而陷于局部最优[12]。自适应控制则利用遗传算法运行过程中的某种反馈信息来自适应的改变参数值。已有学者提出的方法如下：利用群体适宜度的信息来实时改变算法的变异和/或交叉率；根据交叉操作对个体的相对改善程度来设置交叉率；依照父代个体的相似度来调整交叉操作的参数值。这些方法已用于聚类分析。基于自适应控制机制的参数设置技术通常能给出较好的结果。但对于本项目要研究的划分聚类问题，其解空间往往非常复杂，定义一个指标来全面捕获算法运行过程中解空间的动态特征十分困难。上述演化自适应控制和自适应控制机制各有优势和缺陷。本论文拟结合这两种机制的优势来设计有效的参数设置方法，其成果可为实际工程应用提供更加简单，易行的手段。 三、国内外研究现状及难点 遗传算法作为一种启发式优化算法，早已被用于聚类分析。Maulik [13]和Murthy[8]最先开创性地使用标准遗传算法来解决聚类问题。他们在整个遗传进化过程中使用固定的交叉率和变异率，其结果表明，简单遗传算法比K-means算法在一些人为的和实际的数据上得到的结果较优。傅景广[16]则不采用实数编码，而是采用二进制对聚类中心编码，然后在对个体进行选择、交叉和编译，其在两组模拟数据上产生的结果也明显优于K-means算法。然而，这些方法使用固定的参数值以至于在算法运行前可能花费很长时间找到这些参数的最优值，更糟糕的是，简单遗传算法在理论上已被证明不能在有限的时间内找到最优解以及存在局部收敛和收敛速度慢等问题。Mu