开题报告基于自适应和演化自适应组合遗传算法聚类分析.docxVIP

 PAGE 7 本科毕业设计开题报告 （2014届） 论文题目 基于自适应和演化自适应的 组合遗传算法的聚类分析 PAGE   PAGE 8 一、选题的背景与意义 1.1 研究开发的目的 聚类分析作为一种重要的数据预处理技术，是数据挖掘领域极具挑战性的一类组合优化问题，其目标是将一个数据对象集或模式集划分成若干个簇，使同一个簇中的对象具高度同质性，不同簇之间的对象具高度异质性[1,2,3]。现有的不同类型的聚类算法已广泛应用于各类领域，诸如模式识别、机器学习、决策科学、图像处理、人工智能和商业等。传统的聚类算法大体上可分为层次聚类和划分聚类两大类，前者是将数据对象组成一颗聚类树，通过合并或者分裂两种方式递归地产生嵌套聚类层次而后者则同时找到K个聚类中心来划分数据集，并采用迭代重定位技术改进数据聚类效果。本文主要研究划分聚类并且聚类中心数目作为先验条件，这个先验条件对于大数据处理是十分必要的。然而，因为通常数据规模大和数据维度高，而且划分聚类作为一种已知的NP-难问题，许多已有的聚类算法诸如K-means算法根据其规则函数只能找到局部最优解，而无法找到全局最优解[4]。 显然，我们可以通过启发式全局随机优化算法来解决此类聚类问题，诸如美国Michigan大学的John Holland教授发明的遗传算法。其作为一类进化算法，可在可行解空间内随机化有哪些信誉好的足球投注网站最优解，具有很高的隐含并行性，适用于解决复杂的非线性和多维空间寻优问题以及组合优化问题[5,6,7]。传统的遗传算法根据个体的适应度值来选择个体，然后通过遗传算子进行交叉、变异，产生新的种群。显然，遗传算法已成为一种重要的解决数据聚类问题的工具，然而如何设置合适的遗传算法的参数值将决定遗传算法的性能[8,9]。其一，因为特定的问题需要特定的参数值才能找到最优解或者近似解，其值也决定了是否能够高效地找到可行解。其二，因为这些参数存在非线性关系以至于很难决定参数的最优值。其三，因为在遗传进化的不同阶段，这些参数值的最优值可能不同。因此，如何优化如交叉率和变异率这些参数值将是本文的重点。 为了解决参数设置问题，本文将结合现有的自适应和演化自适应参数设置两种方法来改善遗传算法的性能，提高聚类效果，为实际工程应用提供更加简单，易行的手段。 1.2 国内外研究发展现状 为遗传算法设置合适的参数值是一个研究热点，现有的参数设置机制主要由运行前确定和动态适应两种方法[9,10,11]。运行前确定是指用户在算法运行前找到合适的参数值并且这些参数值在运行过程中保持不变。但是，已从实践和理论上证明了最优参数值的组合不仅在每个问题上不同，而且依据有哪些信誉好的足球投注网站的状态和已有哪些信誉好的足球投注网站到的空间，在进化的不同阶段，也不尽相同。所以，这显然是一个十分耗时的过程。更重要的是，这种方法违背了遗传算法固有的动态和自适应特征。 演化自适应控制（Self-adaptive parameter control）和自适应控制（Adaptive parameter control）是目前应用最为广泛的两种动态适应参数设置机制。演化自适应控制通过把遗传算法的参数值编码到个体中，与个体一起经历交叉和变异，利用算法本身来确定合适的参数值。该机制的工作原理是编码在个体中合适的参数值将产生高适宜度个体，这些高适宜度个体将有高几率生存下去并产生后代，因此延续了这些合适的参数值。采用这种参数设置机制，现有多种方法来调节遗传算法的变异和/或交叉率。Back[12,13]通过对数函数改变个体的变异率，虽然这种方法在组合优化问题上比传统的遗传算法性能好，但是学习率对自适应速度影响大。Juha[14]则将演化自适应这种方法应用于聚类分析。演化自适应控制适合于在复杂的优化问题上设置遗传算法的交叉和变异率。然而，采用该机制，算法在运行过程中其交叉和变异率往往会过快下降而陷于局部最优[15]。自适应控制则利用遗传算法运行过程中的某种反馈信息来自适应的改变参数值。如 Ghosh等[16]，Palmes 等[17]和 Srinivas 等[18]利用群体适宜度的信息来实时改变算法的变异和/或交叉率；Islam[19]等根据交叉操作对个体的相对改善程度来设置交叉率；江中央等[20]则依照父代个体的相似度来调整交叉操作的参数值。 这些方法已用于聚类分析。 如 Wang 等[21]采用 Srinivas 等[18]方法的变种来自适应的调节遗传聚类算法的变异和交叉率。这些方法已用于聚类分析。基于自适应控制机制的参数设置技术通常能给出较好的结果。但对于本课题要研究的划分聚类问题，其解空间往往非常复杂，定义一个指标来全面捕获算法运行过程中解空间的动态特征十分困难。上述演化自适应控制和自适应控制机制各有优势和缺陷。本文拟结合这两种机制的