毕业设计-基于自适应和演化自适应的组合遗传算法的聚类分析

1、本科毕业设计文献综述（2014 届）论文题目基于自适应和演化自适应的组合遗传算法的聚类分析作者姓名 指导教师 学科（专业）计算机科学与技术+自动化1001所在学院计算机科学与技术学院提交日期2014年2月基于自适应和演化自适应的组合遗传算法的聚类分析摘要：本文是关于基于自适应和演化自适应的组合遗传算法的聚类分析的一篇文 献综述，先介绍项目的由来及其研究意义，然后详述一下国内外相关研究现状以 及现阶段存在的技术关键及问题，最后进行简单总结与预测未来的发展趋势。关键词：聚类分析，遗传算法，自适应，演化自适应，交叉率，变异率、引言聚类是数据分析领域的常用工具，也是数据预处理的重要手段。聚类分析是 依

2、据数据内在的结构，将数据对象分成类或簇的过程，使得同一簇内的数据具有 高度的相似性，不同簇内的数据具有很高的相异度1,30。针对不同的应用需求， 已经有许多聚类算法被提出。对于大数据聚类，划分聚类已被公认为最为重要的 一类方法。K-means算法在众多的划分聚类方法中因其的简单高效已被广泛使 用，但是存在对初始聚类中心高度依赖以及易于收敛于局部最优值等问题。因此，介于聚类分析是一类组合优化问题以及划分聚类是已知的NP-难问题，我们可以使用启发式全局优化算法来解决聚类问题。而遗传算法作为一类常 见的智能优化算法，具有很高的隐含并行性，特别适用于解决复杂的非线性和多 维空间寻优问题4,5,6。早有

3、一些学者将遗传算法用于解聚类分析问题7,8。然而， 遗传算法的参数会影响其性能。首先，特定的问题会有特定的参数值来决定其是 否有找到最优解或者次优解的能力， 再者，这些参数值存在非线性关系，所以很 难找到他们的最优值。因此，如何选择正确的参数设置策略诸如交叉率和变异率 是一个研究热点，也是本论文将解决的难点。运行前固定参数和动态适应是现有的两种重要的遗传算法参数设置机制 9,10,11。运行前参数固定方法违背了算法固有的动态性和自适应性，已很少使用。动态适应方法主要分为演化自适应控制(Self-adaptive parameter contro)和自适 应控制(Adaptive paramet

4、er control)两种方法。本论文将结合两种方法，提出一 种新的参数设置机制用于解决聚类分析问题。、研究意义演化自适应控制(Self-adaptive parameter control)和自适应控制(Adaptiveparameter contro)是目前应用最为广泛的两种动态适应参数设置机制。演化自适应控制通过把遗传算法的参数值编码到个体中，然后利用算法本身来确定合适的参数值。该机制的工作原理是编码在个体中合适的参数值将产生高适宜度个体， 这些高适宜度个体将有高几率生存下去并产生后代，因此延续了这些合适的参数 值。采用这种参数设置机制，现有多种方法来调节遗传算法的变异和/或交叉率。演化

5、自适应控制适合于在复杂的优化问题上设置遗传算法的交叉和变异率。然 而，采用该机制，算法在运行过程中其交叉和变异率往往会过快下降而陷于局部 最优12。自适应控制则利用遗传算法运行过程中的某种反馈信息来自适应的改 变参数值。已有学者提出的方法如下：利用群体适宜度的信息来实时改变算法的 变异和/或交叉率；根据交叉操作对个体的相对改善程度来设置交叉率；依照父 代个体的相似度来调整交叉操作的参数值。这些方法已用于聚类分析。基于自适应控制机制的参数设置技术通常能给出较好的结果。但对于本项目要研究的划分聚类问题，其解空间往往非常复杂，定义一个指标来全面捕获算法运行过程中解 空间的动态特征十分困难。上述演化自

6、适应控制和自适应控制机制各有优势和缺 陷。本论文拟结合这两种机制的优势来设计有效的参数设置方法，其成果可为实际工程应用提供更加简单，易行的手段。三、国内外研究现状及难点遗传算法作为一种启发式优化算法，早已被用于聚类分析。Maulik 13和Murthy最先开创性地使用标准遗传算法来解决聚类问题。他们在整个遗传进化过程中使用固定的交叉率和变异率，其结果表明，简单遗传算法比K-means算法在一些人为的和实际的数据上得到的结果较优。傅景广16 则不采用实数编码，而是采用二进制对聚类中心编码，然后在对个体进行选择、交叉和编译，其在两 组模拟数据上产生的结果也明显优于 K-means算法。然而，这些方

7、法使用固定 的参数值以至于在算法运行前可能花费很长时间找到这些参数的最优值，更糟糕的是，简单遗传算法在理论上已被证明不能在有限的时间内找到最优解以及存在 局部收敛和收敛速度慢等问题。Murthy还根据进化迭代的代数去改变变异率， 因为变异率是算法能否跳出局部最优解的关键因素，在进化早期为了保持种群的 多样性，防止过快收敛，变异率设置的较大，而在变异后期为了保证最优解不易 被破坏，变异率又要设置的较低。所以，需要寻找合适的函数去调节变异率使得 其在各个进化阶段保持较优解，这可能比在整个进化过程中确定一个固定的最优 变异率值更加困难。一些学者为了解决简单遗传算法存在的问题，提出了演化自适应交叉率和

8、变异率的方法。其中，最著名的是 Back，15等提出的在指定条件下运用一个对数 函数改变变异率的值.虽然他的算法性能优于简单的遗传算法，但是函数中的学 习率这个参数对结果影响较大，控制着自适应速度。他们认为学习率越高，那么 收敛可能越低，收敛速度越快。因此，学习率直接影响力算法的性能，需要进一 步研究。此后，Serpell17则在著名的旅行商问题上进一步研究了单独的自适应变 异算子，单独的自适应变异率以及同时自适应变异算子和自适应变异率三者的性 能。他测试了大量的演化自适应遗传算法，所有的结果均优于简单遗传算法， 但是在计算交叉率上花的时间较长。具体地，他使用三种不同的方法：正态分布化， 随机

9、平均化和离散化去演化自适应变异率。结果表明正态分布化和随机平均化两种方法终止搜索过程比离散化早，也就是说他们更不容易跳出局部最优解。因为一旦变异率空间进入适应度中立值区域，那么变异率就会有下行压力。更进一步 地, Matthew和Sycard12深入的研究了演化自适应变异率存在很高的下行压力的 原因：可行解碗状空间的影响，变异率和选择压的关系，隐含的内在自适应等等。 总之，演化自适应控制适合于在复杂的优化问题上设置遗传算法的交叉和变异 率。因此，这种方法也已经被应用于聚类分析问题上。Kivij? rvi17在聚类问题上演化自适应地改变了交叉方法，变异率和扰动范围。与此同时，自适应机制也是改变参

10、数值的另一种方法，能同时兼顾种群多样性和收敛速度18,19。Ghosh20, PalmeS21 and Srinivas22基于个体的适应度值实时 地改变交叉率和变异率的值。Srin ivas22以保证种群多样性的同时又要有一定的 收敛能力为目标来改变交叉率和变异率。具体地，在解空间中若种群分布越分散， 那么变异率和交叉率的值将减少，相反，若种群陷入局部最优解，那么他们的值 将增大。种群的收敛程度用种群的平均适应度和最大适应度来评价。同时，交叉率和变异率的值也依赖于父代的适应度值，这样使得高适应度的个体能够被保留 下来不被破坏，而低适应度的个体更容易被交叉和变异，产生优秀基因。但是，这种算法对

11、于进化初期十分不利。因为在进化初期，一些高适应度的个体拥有较 低的交叉率和变异率几乎处于不变的状态，而其他个体很快被淘汰，加速了收敛速度，陷入局部最优解，出现早熟现象。所以，此后有很多学者提出了改进策略， 如史明霞23，陶林波24o Kenn严则提出了一种基于种群多样性的自适应遗传算 法，并在带有时间窗的车辆路径问题上得到很好的结果。他通过在基因空间内染色体的海明距离来度量种群多样性。然后，基于这个海明距离去改变交叉率和变 异率，这样便能保持种群多样性，减少早熟现象产生的可能。然而，函数中的敏 感性常数大小决定了参数的值。一个越小的敏感性常数改变交叉率和变异率越平 滑，相反，敏感性常数越大，他

12、们的值改变的越快。因此，特定的问题需要特定 的敏感性常数。Gi nley26 贝U同时考虑了种群多样性和适应度。他采用描述种群解 空间多样性的标准种群多样性 SPD (standard population diversity)指标来改变交 叉率和变异率，同时，提出一种基于个体适应度的健康种群多样性指标HPD(healthy population diversity )来调节选择算子。算法的目标是创造并保持一个 高适应度的多样性种群并且有能力自适应适应度空间的改变。具体地，SPD通过平均个体标准差的协方差度量。HPD则通过带有适应度权重的协方差来度量。 Liu27提出了用父代表现来排名的方法而

13、不是适应度值改变交叉率和变异率。同 样，高适应度的个体易于保留而低适应度的个体拥有高交叉率。Islam19等根据交叉操作对个体的相对改善程度来设置交叉率；江中央等28则依照父代个体的相似度来调整交叉操作的参数值。这些方法已用于聚类分析。如Wang等29采用Srini vas等22方法的变种来自适应的调节遗传聚类算法的变异和交叉率。基于自 适应控制机制的参数设置技术通常能给出较好的结果。但对于本论文要研究的划分聚类问题，其解空间往往非常复杂，定义一个指标来全面捕获算法运行过程中 解空间的动态特征十分困难。所以，上述演化自适应和自适应控制机制各有优势和缺陷。如何结合两种机制的优势，达到互补的效果将

14、是本论文的重点和难点。四、总结与展望聚类分析是数据挖掘领域的一个极具挑战性的研究热点。其目标是将一个数据对象集划分成若干个簇，使同一个簇中的对象具高度同质性，不同簇之间的 对象具高度异质性。 聚类分析在人工智能、机器学习、模式识别、图像分析、生物信息、决策科学和商业等领域具有广泛应用前景和潜在经济价值31,32。聚类分析方法可分为层次聚类和划分聚类，本论文研究划分聚类。划分聚类是一个已知的NP-难问题。近来，遗传算法已成为研究划分聚类的重要方法， 其作为具有系统优化、适应和学习的高性能计算和建模方法的研究渐趋成熟。遗传算法具有进化计算的所有特征，同时又具有自身的特点33:（ 1）搜索过程既不受

15、优化函数的连续性约束，也没有优化函数导数必须存在的要求（2）遗传算法采用多点搜索或者说是群体搜索，具有很高的隐含并行性，因而可以提高计算 速度（3）遗传算法是一种自适应搜索技术，其选择交叉变异等运算都是以一种 概率方式来进行，从而增加了搜索过程的灵活性，具有较好的全局优化求解能力（4）遗传算法直接以目标函数值为搜索信息，对函数的性态无要求，具有较好 的普适性和易扩充性（5）遗传算法更适合大规模复杂问题的优化。但现有遗传 聚类算法存在诸多问题。首先，这些算法在运行之前通常需要设置若干参数。这些参数的值，比如交叉和变异率，决定着算法的行为和性能。由于这些参数之间 存在非线性关系并依赖于具体的聚类问

16、题，况且其最佳值往往需要随算法运行阶 段的不同而改变，再加上参数值的多样性，使得正确设置这些参数变得异常困难。 因此，如何有效设置这些参数值，使算法性能最优化成为一项重要的研究课题。演化自适应机制适合于在复杂的优化问题上设置遗传算法的交叉和变异 率。然而，采用该机制，算法在运行过程中其交叉和变异率往往过快下降而陷入 局部最优解。自适应机制往往能够防止遗传算法陷入局部最优（早熟现象） ，但 是定义一个指标来全面捕获算法运行过程中解空间的动态特征却十分困难。幸运的是，自适应机制能够阻止过早收敛的优势能弥补演化自适应过早陷入局部最优 的缺点。同时，演化自适应能够削弱自适应机制中选取的函数的影响。因此

17、，虽 然演化自适应和自适应两种机制各有优缺点， 但是我们能够使用他们的优势相互 的去弥补他们的劣势。所以，本论文将结合两种机制的优势来设计有效的参数设 计方法。参考文献:1 Han J, Kamber M.数据挖掘：概念与技术M.第二版.机械工业出版社, 2007.2 Hartigan, J.A. and Wong, M.A.: A k-means clustering algorithm. Applied Statistics, 28(1979) 100-1103 M.Garey and D.Joh nson, Computers and in tractability-a guide to

18、 the theory of NP-complete ness, W.H.Freema n, San Fran cisco, 1979.4 李敏强，寇继松，林丹，李书全.遗传算法的基本理论与应用M.北京：科 学出版社，200235 L.Davis, Han dbook of Gen etic Algorithms, van Nostra nd Rei n hold, New York，1991. 刘勇，等.非数值并行算法(二)遗传算法M 北京：科学出版社，1995.7 Hruschka, Eduardo R., and Nels on FF Ebecke n. A gen etic algor

19、ithm for cluster analysis. Intelligent Data Analysis 7.1 (2003): 15-25.8 Murthy, Chivukula A., and Nirmalya Chowdhury. In search of optimal clusters using genetic algorithms. Pattern Recognition Letters 17.8 (1996): 825-832.9 Eibe n, Agost on En dre, Robert Hin terdi ng, and Zbig niew Michalewicz. P

20、arameter control in evolutionary algorithms. Evolutionary Computation, IEEE Transactions on 3.2 (1999): 124-141.10 Michalewicz, Zbig ni ew, and Marti n Schmidt. Parameter con trol in practice. Parameter setting in evolutionary algorithms. Springer Berlin Heidelberg, 2007. 277-294.11 De Jong, Kenn et

21、h. Parameter sett ing in EAs: a 30 year perspective.Parameter Setti ng in Evoluti on ary Algorithms. Spri nger Berlin Heidelberg, 2007. 1-18.12 Glickma n, Matthew R., and Katia Sycara. Reas ons for premature conv erge nee of self-adapti ng mutatio n rates. Evoluti onary Computatio n, 2000. Proceedi

22、ngs of the 2000 Congress on. Vol. 1. IEEE, 2000.13 Maulik, Ujjwal, and Sanghamitra Bandyopadhyay. Genetic algorithm-basedclusteri ng tech nique. Pattern recog ni tion 33.9 (2000): 1455-1465.14 B?ck, Thomas, and Martin Schtiz. Intelligent mutation rate control in canonical genetic algorithms. Foundat

23、ions of intelligent systems. Springer Berlin Heidelberg, 1996. 158-167.15 Back, Eibe n, “ An empirical study on Gas “ withoutparameters ” ,Lecture Notes in Computer Scie nee, pp.315-324, 2000.16 傅景广，许刚，王裕国.基于遗传算法的聚类分析J.计算机工程，2004, 30(4): 122-124.17 Kivij? rvi, Juha, Pasi Fr?nti, and Olli Nevalainen.

24、 Self-adaptive genetic algorithm for clusteri ng. Journal of Heuristics 9.2 (2003): 113-129.18 Herrera F, Loza no M. Adaptatio n of gen etic algorithm parameters based on fuzzy logic controllersJ. Genetic Algorithms and Soft Computing, 1996, 8: 95-125.19 Islam S M, Das S, Ghosh S, et al. An adaptive

25、 differential evolution algorithm with novel mutation and crossover strategies for global numerical optimizationJ. Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Tran sactio ns on, 2012, 42(2): 482-500.20 Ghosh A, Das S, Chowdhury A, et al. An improved differential evolution algorithm with

26、 fitness-based adaptation of the control parametersJ. In formation Scie nces, 2011, 181(18): 3749-3765.21 Palmes P P, Hayasaka T, Usui S. Mutati on-based gen etic n eural n etworkJ. Neural Networks, IEEE Transactions on, 2005, 16(3): 587-600.22 Srini vas M, Pat naik L M. Adaptive probabilities of cr

27、ossover and mutati on in genetic algorithmsJ. Systems, Man and Cybernetics, IEEE Transactionson, 1994, 24(4): 656-667.23 史明霞，陶林波，沈建京.自适应遗传算法的改进与应用J.微计算机应 用，2006, 27(4): 405-408.24 陶林波，沈建京，韩强.一种解决早熟收敛的自适应遗传算法设计J.微计算机信息，2006 (12S): 268-270.25 Zhu K Q. A diversity-controlling adaptive genetic algorithm for the vehicle routing problem with time windowsC/Tools with Artificial Intelligenee, 2003. Proceedi ngs. 15th IEEE In ternatio nal Co nference on .IEEE, 2003: 176-183.26 MeGinley B, Maher J, ORiordan C, et al. Maintaining healthy population diversity using adaptive crossover, mutation,