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