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

本科毕业设计开题报告 （201届） 组合遗传算法的聚类分析 基于自适应和演化自适应的组合遗传算法的聚类分析 一、选题的背景与意义 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）是目前 二、研究开发的基本内容、目标，拟解决的主要问题或技术关键 2.1 研究目标 现有基于遗传算法的聚类分析存在参数设置难问题。本课题将提出结合演化自适应和自适应参数设置相结合的技术来研究有效参数设置方法，以解决参数设置问题，提高遗传聚类算法的整体性能。项目成果可应用于科学研究和工程设计，具有较强的理论价值和应用价值。 2.2 研究的基本内容 项目拟通过在演化自适应控制技术中结合自适应控制技术来克服其过高下行压力带来的缺陷。具体的，项目拟采用自适应控制技术来调节演化自适应技术得到的交叉和变异率，其实现过程如下： 对于遗传算法中的每个个体，在更新编码在其中的变异和交叉率时： 首先，利用下列公式： 分别得到P1m(t+1)和P1c(t+1)，得到的值不更新到个体中；式中N(0,1)是均值为0标准差为1的正态分布随机数，γ为控制参数； b) 接着，利用下列公式： 分别得到P2m(t+1)和P2c(t+1)；式中fave为群体的平均适宜度，fmax为群体中最优个体的适宜度，f为个体适宜度，f＇为交叉操作双方较优个体的适宜度，k1，k2，k3，k4为(0,1]之间常数。 c) 假如P1m (t+1)P2m(t+1)，则采用下列公式计算新的P1m(t+1)： 反之，则计算新的P1m(t+1)如下： 式中R(P2m(t+1)-P1m (t+1))和R(P1m (t+1)-P2m (t+1))分别产生[0,P2m (t+1)-P1m (t+1)]和[0,P1m (t+1)-P2m (t+1)]之间的随机数。 d) 以同样的方式计算P1c (t+1)，得到的P1m (t+1)和P1c (t+1)值最后更新到个体中。 另外，项目也可通过自适应控制技术来引导演化自适应技术对交叉和变异率