《文献综述--基于自适应和演化自适应的组合遗传算法的聚类分析》由会员分享，可在线阅读，更多相关《文献综述--基于自适应和演化自适应的组合遗传算法的聚类分析（9页珍藏版）》请在金锄头文库上搜索。
1、本科毕业设计文献综述（2014 届）届）论文题目 基于自适应和演化自适应的 组合遗传算法的聚类分析作者姓名 指导教师 学科(专业)计算机科学与技术+自动化1001所在学院 计算机科学与技术学院 提交日期 2014 年 2 月 1基于自适应和演化自适应的组合遗传算法的聚类分析基于自适应和演化自适应的组合遗传算法的聚类分析摘要：摘要：本文是关于基于自适应和演化自适应的组合遗传算法的聚类分析的一篇文献综述，先介绍项目的由来及其研究意义，然后详述一下国内外相关研究现状以及现阶段存在的技术关键及问题，最后进行简单总结与预测未来的发展趋势。关键词：关键词：聚类分析，遗传算法，自适应，演化自适应，交叉率，变
2、异率一、引言聚类是数据分析领域的常用工具，也是数据预处理的重要手段。聚类分析是依据数据内在的结构，将数据对象分成类或簇的过程，使得同一簇内的数据具有高度的相似性，不同簇内的数据具有很高的相异度1,30。针对不同的应用需求，已经有许多聚类算法被提出。对于大数据聚类，划分聚类已被公认为最为重要的一类方法。K-means 算法2在众多的划分聚类方法中因其的简单高效已被广泛使用，但是存在对初始聚类中心高度依赖以及易于收敛于局部最优值等问题。因此，介于聚类分析是一类组合优化问题以及划分聚类是已知的 NP-难问题3，我们可以使用启发式全局优化算法来解决聚类问题。而遗传算法作为一类常见的智能优化算法，具有很
3、高的隐含并行性，特别适用于解决复杂的非线性和多维空间寻优问题4,5,6。早有一些学者将遗传算法用于解聚类分析问题7,8。然而，遗传算法的参数会影响其性能。首先，特定的问题会有特定的参数值来决定其是否有找到最优解或者次优解的能力，再者，这些参数值存在非线性关系，所以很难找到他们的最优值。因此，如何选择正确的参数设置策略诸如交叉率和变异率是一个研究热点，也是本论文将解决的难点。运行前固定参数和动态适应是现有的两种重要的遗传算法参数设置机制9,10,11。运行前参数固定方法违背了算法固有的动态性和自适应性，已很少使用。动态适应方法主要分为演化自适应控制（Self-adaptive parameter
4、 control）和自2适应控制（Adaptive parameter control）两种方法。本论文将结合两种方法，提出一种新的参数设置机制用于解决聚类分析问题。二、研究意义演化自适应控制（Self-adaptive parameter control）和自适应控制（Adaptive parameter control）是目前应用最为广泛的两种动态适应参数设置机制。演化自适应控制通过把遗传算法的参数值编码到个体中，然后利用算法本身来确定合适的参数值。该机制的工作原理是编码在个体中合适的参数值将产生高适宜度个体，这些高适宜度个体将有高几率生存下去并产生后代，因此延续了这些合适的参数值。采用这
5、种参数设置机制，现有多种方法来调节遗传算法的变异和/或交叉率。演化自适应控制适合于在复杂的优化问题上设置遗传算法的交叉和变异率。然而，采用该机制，算法在运行过程中其交叉和变异率往往会过快下降而陷于局部最优12。自适应控制则利用遗传算法运行过程中的某种反馈信息来自适应的改变参数值。已有学者提出的方法如下：利用群体适宜度的信息来实时改变算法的变异和/或交叉率；根据交叉操作对个体的相对改善程度来设置交叉率；依照父代个体的相似度来调整交叉操作的参数值。这些方法已用于聚类分析。基于自适应控制机制的参数设置技术通常能给出较好的结果。但对于本项目要研究的划分聚类问题，其解空间往往非常复杂，定义一个指标来全面
6、捕获算法运行过程中解空间的动态特征十分困难。上述演化自适应控制和自适应控制机制各有优势和缺陷。本论文拟结合这两种机制的优势来设计有效的参数设置方法，其成果可为实际工程应用提供更加简单，易行的手段。三、国内外研究现状及难点遗传算法作为一种启发式优化算法，早已被用于聚类分析。Maulik 13和Murthy8最先开创性地使用标准遗传算法来解决聚类问题。他们在整个遗传进化过程中使用固定的交叉率和变异率，其结果表明，简单遗传算法比 K-means算法在一些人为的和实际的数据上得到的结果较优。傅景广16则不采用实数编码，而是采用二进制对聚类中心编码，然后在对个体进行选择、交叉和编译，其在两组模拟数据上产
7、生的结果也明显优于 K-means 算法。然而，这些方法使用固定的参数值以至于在算法运行前可能花费很长时间找到这些参数的最优值，更糟糕的是，简单遗传算法在理论上已被证明不能在有限的时间内找到最优解3以及存在局部收敛和收敛速度慢等问题。Murthy8还根据进化迭代的代数去改变变异率，因为变异率是算法能否跳出局部最优解的关键因素，在进化早期为了保持种群的多样性，防止过快收敛，变异率设置的较大，而在变异后期为了保证最优解不易被破坏，变异率又要设置的较低。所以，需要寻找合适的函数去调节变异率使得其在各个进化阶段保持较优解，这可能比在整个进化过程中确定一个固定的最优变异率值更加困难。一些学者为了解决简单
8、遗传算法存在的问题，提出了演化自适应交叉率和变异率的方法。其中，最著名的是 Back14，15等提出的在指定条件下运用一个对数函数改变变异率的值.虽然他的算法性能优于简单的遗传算法，但是函数中的学习率这个参数对结果影响较大，控制着自适应速度。他们认为学习率越高，那么收敛可能越低，收敛速度越快。因此，学习率直接影响力算法的性能，需要进一步研究。此后，Serpell17则在著名的旅行商问题上进一步研究了单独的自适应变异算子，单独的自适应变异率以及同时自适应变异算子和自适应变异率三者的性能。他测试了大量的演化自适应遗传算法，所有的结果均优于简单遗传算法，但是在计算交叉率上花的时间较长。具体地，他使用
9、三种不同的方法：正态分布化，随机平均化和离散化去演化自适应变异率。结果表明正态分布化和随机平均化两种方法终止搜索过程比离散化早，也就是说他们更不容易跳出局部最优解。因为一旦变异率空间进入适应度中立值区域，那么变异率就会有下行压力。更进一步地，Matthew 和 Sycara12深入的研究了演化自适应变异率存在很高的下行压力的原因：可行解碗状空间的影响，变异率和选择压的关系，隐含的内在自适应等等。总之，演化自适应控制适合于在复杂的优化问题上设置遗传算法的交叉和变异率。因此，这种方法也已经被应用于聚类分析问题上。Kivijrvi17在聚类问题上演化自适应地改变了交叉方法，变异率和扰动范围。与此同时
10、，自适应机制也是改变参数值的另一种方法，能同时兼顾种群多样性和收敛速度18,19。Ghosh20, Palmes21 and Srinivas22基于个体的适应度值实时地改变交叉率和变异率的值。Srinivas22以保证种群多样性的同时又要有一定的收敛能力为目标来改变交叉率和变异率。具体地，在解空间中若种群分布越分散，那么变异率和交叉率的值将减少，相反，若种群陷入局部最优解，那么4他们的值将增大。种群的收敛程度用种群的平均适应度和最大适应度来评价。同时，交叉率和变异率的值也依赖于父代的适应度值，这样使得高适应度的个体能够被保留下来不被破坏，而低适应度的个体更容易被交叉和变异，产生优秀基因。但是
11、，这种算法对于进化初期十分不利。因为在进化初期，一些高适应度的个体拥有较低的交叉率和变异率几乎处于不变的状态，而其他个体很快被淘汰，加速了收敛速度，陷入局部最优解，出现早熟现象。所以，此后有很多学者提出了改进策略，如史明霞23，陶林波24。Kenny25则提出了一种基于种群多样性的自适应遗传算法，并在带有时间窗的车辆路径问题上得到很好的结果。他通过在基因空间内染色体的海明距离来度量种群多样性。然后，基于这个海明距离去改变交叉率和变异率，这样便能保持种群多样性，减少早熟现象产生的可能。然而，函数中的敏感性常数大小决定了参数的值。一个越小的敏感性常数改变交叉率和变异率越平滑，相反，敏感性常数越大，
12、他们的值改变的越快。因此，特定的问题需要特定的敏感性常数。Ginley26则同时考虑了种群多样性和适应度。他采用描述种群解空间多样性的标准种群多样性SPD（standard population diversity）指标来改变交叉率和变异率，同时，提出一种基于个体适应度的健康种群多样性指标 HPD（healthy population diversity）来调节选择算子。算法的目标是创造并保持一个高适应度的多样性种群并且有能力自适应适应度空间的改变。具体地，SPD 通过平均个体标准差的协方差度量。HPD 则通过带有适应度权重的协方差来度量。Liu27提出了用父代表现来排名的方法而不是适应度值改
13、变交叉率和变异率。同样，高适应度的个体易于保留而低适应度的个体拥有高交叉率。Islam19等根据交叉操作对个体的相对改善程度来设置交叉率；江中央等28则依照父代个体的相似度来调整交叉操作的参数值。这些方法已用于聚类分析。如 Wang 等29采用 Srinivas 等22方法的变种来自适应的调节遗传聚类算法的变异和交叉率。基于自适应控制机制的参数设置技术通常能给出较好的结果。但对于本论文要研究的划分聚类问题，其解空间往往非常复杂，定义一个指标来全面捕获算法运行过程中解空间的动态特征十分困难。所以，上述演化自适应和自适应控制机制各有优势和缺陷。如何结合两种机制的优势，达到互补的效果将是本论文的重点
14、和难点。5四、总结与展望聚类分析是数据挖掘领域的一个极具挑战性的研究热点。其目标是将一个数据对象集划分成若干个簇，使同一个簇中的对象具高度同质性，不同簇之间的对象具高度异质性。 聚类分析在人工智能、机器学习、模式识别、 图像分析、生物信息、决策科学和商业等领域具有广泛应用前景和潜在经济价值31,32。聚类分析方法可分为层次聚类和划分聚类，本论文研究划分聚类。划分聚类是一个已知的 NP-难问题。近来，遗传算法已成为研究划分聚类的重要方法，其作为具有系统优化、适应和学习的高性能计算和建模方法的研究渐趋成熟。遗传算法具有进化计算的所有特征，同时又具有自身的特点33：（1）搜索过程既不受优化函数的连续
15、性约束，也没有优化函数导数必须存在的要求（2）遗传算法采用多点搜索或者说是群体搜索，具有很高的隐含并行性，因而可以提高计算速度（3）遗传算法是一种自适应搜索技术，其选择交叉变异等运算都是以一种概率方式来进行，从而增加了搜索过程的灵活性，具有较好的全局优化求解能力（4）遗传算法直接以目标函数值为搜索信息，对函数的性态无要求，具有较好的普适性和易扩充性（5）遗传算法更适合大规模复杂问题的优化。但现有遗传聚类算法存在诸多问题。首先，这些算法在运行之前通常需要设置若干参数。这些参数的值，比如交叉和变异率，决定着算法的行为和性能。由于这些参数之间存在非线性关系并依赖于具体的聚类问题，况且其最佳值往往需要
16、随算法运行阶段的不同而改变，再加上参数值的多样性，使得正确设置这些参数变得异常困难。因此，如何有效设置这些参数值，使算法性能最优化成为一项重要的研究课题。演化自适应机制适合于在复杂的优化问题上设置遗传算法的交叉和变异率。然而，采用该机制，算法在运行过程中其交叉和变异率往往过快下降而陷入局部最优解。自适应机制往往能够防止遗传算法陷入局部最优（早熟现象） ，但是定义一个指标来全面捕获算法运行过程中解空间的动态特征却十分困难。幸运的是，自适应机制能够阻止过早收敛的优势能弥补演化自适应过早陷入局部最优的缺点。同时，演化自适应能够削弱自适应机制中选取的函数的影响。因此，虽然演化自适应和自适应两种机制各有优缺点，但是我们能够使用他们的优势6相互的去弥补他们的劣势。所以，本论文将结合两种机制的
