《[计算机软件及应用]K-均值遗传算法的论文.doc》由会员分享，可在线阅读，更多相关《[计算机软件及应用]K-均值遗传算法的论文.doc（40页珍藏版）》请在三一文库上搜索。
1、 本科毕业设计（论文）题目：基于K-均值遗传算法的聚类程序 学 院 软件学院 专 业 软件工程 学生姓名 学生学号 指导教师 提交日期 2012 年 月 日摘 要在这篇论文里，我们先介绍遗传算法的原理以及特点，然后介绍遗传算法的现今的发展状况。之后我们介绍在数据挖掘方面的发展和前景，最后，介绍遗传算法在数据挖掘方面的应用。我们提出一个能够把一个给定的数据整体上理想的划分成指定数目的簇的新颖的混合遗传算法。在聚类方面，GA早期要么用于从父染色体中生成子染色体的昂贵的交叉算子，要么用于昂贵的适应度函数或者二者都有。围绕这些昂贵的操作，我们把GA和一种用于聚类的经典梯度下降算法K均值算法混合起来。因
2、此，我们叫它遗传K均值算法(GKA)。我们用K均值算法定义K均值算子并把它作为搜索运算子，使他在GKA中替换交叉运算子。我们在聚类中也定义了一种以距离基础的突变的特殊的偏差突变运算子。根据有限马克洛夫链理论，证明GKA算法会聚合在一个整体最优解。之后我们会介绍这个混合算法的C+实现，介绍程序用到的类和类内部的成员参数和成员函数。介绍一下世界各国物价水平数据，最后我们用程序对世界各国物价水平进行聚类分析，检查程序的实用性和性能，最后根据结果得出结论。关键词：数据挖掘，聚类，遗传算法， K均值算法，整体最优解。AbstractWe firstly introducedthe principle a
3、nd featureofgenetic algorithm,and then describethepresent state of developmentofthegenetic algorithm. We introducethedata miningdevelopments andprospects, and finallyto introduce the application of the geneticalgorithm in data mining.We propose a novel hybrid genetic algorithm that finds a globally
4、optimal partition of a given data into a specified number of clusters. GAs used earlier in clustering employ either an expensive crossover operator to generate valid child chromosomes from parent chromosomes or a costly fitness function or both. To circumvent these expensive operations, we hybridize
5、 GA with a classical gradient descent algorithm used in clustering viz., K-means algorithm. Hence, the name is genetic K-means algorithm (GKA). We define K-means operator, one-step of K-means algorithm, and use it in GKA as a search operator instead of crossover. We also define a biased mutation ope
6、rator specific to clustering which base on distance. Using finite Markov chain theory, we prove that the GKA converges to the global optimum. Then we will introduce the implementation of this hybrid algorithm in C+ and the class of parameter members and member functions in this program. And then we
7、will introduce the data of the world price level data. Finally we use this program on the data to clustering analysis. Check the usability and performance of the program, and finally concluded that based on the results.Keyword: Data mining，Clustering, genetic algorithms, K-means algorithm, global op
8、timization.目录摘 要2Abstract3第一章引言51.1遗传算法起源51.2数据挖掘起源51.3遗传算法与数据挖掘的现状61.4本章小结7第二章算法详解82.1算法简介82.1.1遗传算法与k-均值算法82.1.2聚类算法102.3基因K-均值算法112.4算法证明142.5实验验证17第三章 代码介绍193.1类的介绍193.2主函数介绍233.3实验253.3.1对突变率和迭代次数实验内容253.3.2个体数目和属性数目的实验内容293.3.3对簇类个数的实验内容30第四章 实验研究324.1本章小结32结论34感谢36参考文献37第一章 引言1.1遗传算法起源遗传算法（Ge
9、netic Algorithm）是借鉴生物界的进化机制（适者生存，优胜劣汰）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年在其著作Adaptation in Natural and Artificial Systems首先提出。其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。遗传算法首先从一
10、个可能是解的一个种群开始，而种群的个体是根据基因编码而成。而每个个体带有各种特征的染色体组成的实体。染色体是遗传物质的主要载体，里面是多个基因的集合，其中的内部表现是各种积阴德组合，它决定了个体的最终外部表现，比如皮肤的颜色就是根据染色体中的某些基因组合所决定的。所以，在一开始需要编码工作来实现从表现型到基因型的映射。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码等方法来产生种群之后，按照适者生存和优胜劣汰的进化原理，逐代的演化使得产生出近似解越来越好。在每一代中，根据问题域中个体的适应度大小选择个体，并借助于自然遗传学的遗传算子进行组合交叉和变异或者一些其他算子，产生出代表新的
11、解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，最终末代种群中的最优个体经过解码后，就可以作为问题近似最优解。151.2数据挖掘起源近年来随着数据库技术和计算机网络的广泛应用，加上使用先进的自动数据生成和采集工具，人们所拥有的数据量急剧增大。激增的数据背后隐藏着许多重要的信息，如何从大量的数据中提取并找到有用的信息以指导决策，是迫切需要解决的问题。在这种情况下，数据挖掘新型的数据分析技术于1995年诞生了。16现在，数据挖掘已经是信息时代的热门学科。它能够帮助人们在信息海洋中发现有用的知识和信息，使得面对信息时代海量数据时，能够有效地利用巨量的原始数据分析现状以预
12、测未来。数据挖掘技术在信息时代迅猛发展。目前，数据挖掘已经成为一个研究热点。数据挖掘所得到的知识能够为决策支持提供数据依据和技术支持。数据挖掘是通过分析大量数据，从中寻找其规律的技术。主要有数据预处理、规律搜寻和规律表达3个步骤。数据预处理是从相关的数据源中选取所需的数据并整合成用于数据挖掘的数据集；规律搜寻是用某种方法将数据集所含的规律找出来；规律表达则是尽可能以用户可理解的方式（如可视化）将找出的规律表示出来。数据挖掘主要利用了来自如下一些领域的思想：(1) 来自统计学的抽样、估计和假设检验，(2) 人工智能、模式识别和机器学习的搜索算法、建模技术和学习理论。数据挖掘也迅速地接纳了来自其他
13、领域的思想，这些领域包括最优化、进化计算、信息论、信号处理、可视化和信息检索。一些其他领域也起到重要的支撑作用。特别地，需要数据库系统提供有效的存储、索引和查询处理支持。源于高性能（并行）计算的技术在处理海量数据集方面常常是重要的。分布式技术也能帮助处理海量数据，并且当数据不能集中到一起处理时更是至关重要。21.3遗传算法与数据挖掘的现状遗传算法作为一种有效的全面并行优化搜索工具，早被众多应用领域所接受，在数据挖掘方面的应用也得到了极高的重视。应用于决策树、分类器、模糊规则获取等方面的遗传算法的文献不断涌现，早已成为数据挖掘领域的热点研究课题。因为其解决问题的混沌、随机和非线性等特征，遗传算法
14、为其它科学技术无法解决或难以解决的复杂问题提供了新的计算模型。对于嘈杂无序的数据，遗传算法更成为了最有效的方法。许多知识发现的问题可以看成是搜索问题，数据库可以看作是搜索空间，发现算法可以看作是搜索策略，而遗传算法是模拟自然进化的全局搜索算法。应用遗传算法在数据中进行迭代，利用遗传规律对随机产生的一组规则进行进化和淘汰，直到产生能够被该组规则覆盖的数据，从而便挖掘出其中的规则。同时遗传算法避免了搜索过程中的局部最优解，用在规则发现方面有希望发现真正有用的规则。1.4本章小结本章主要介绍了遗传算法的起源，然后介绍了遗传算法的原理。之后又介绍了数据挖掘的起源和概述，介绍数据挖掘是通过分析大量数据，
15、从中寻找其规律的技术。最后我们介绍了遗传算法与数据挖掘的现状，以及遗传算法在数据挖掘的应用。第二章算法详解2.1算法简介2.1.1遗传算法与k-均值算法演化算法是基于自然选择和自然遗传学的原理的随机优化算法。他们在复杂的搜索空间内执行平行搜索。演化算法包含遗传算法，进化策略和演化编程。我们在本文主要研究遗传算法。GA经常被用于函数最优化问题而且被认为在寻找最理想和接近理想的结果时表现不错。在大型检索空间里表现出的适应性以及域独立的天性激发了它在很多领域的应用像模式识别，机器学习，VLSI设计，等。在这篇论文中，我们提出一个算法，那是GA在聚类应用中的修改。聚类已经有效地应用于各种各样的工程和科
16、学科目像物理，生物，化学，计算机视觉，通信，以及遥感。聚类分析通过抽象基层结构来组织数据（一个模式集，每个模式可以作为一个矢量测量）。当一个组（簇）里的模式要比不同组里的模式更相似时，分组结束。因此，使用聚类分析组织的数据使用一些相似度量（dissimilarity measure）在模式集之间。相似度量根据经过分析的数据和分析的目的来定义。各种类型的聚类算法被提出来以便适应不同的需求。聚类算法根据抽象的结构能够被明显的分为层次算法和分割式算法。分级聚类算法由一个有等级的分割系统树图，即在层级中每个区间都嵌套在下一个级别的区间中的模式，组成。分割式聚类算法生成一个单一的区间，有特定的或估计数目
17、的不重叠簇，里面的数据力图恢复现在数据中原有的组。在这篇论文中，我们主要把我们的注意力集中在在一个给定的实数矢量集合中的划分聚类，里面两个矢量的相异程度作为他们之间的欧几里得距离。 在分割式聚类中一个很重要的问题是如何找到一个划分有特定数目簇的给定数据的方法使得簇的变化达到最小。在这论文里，我们把这个问题叫做TWCV的最小化。总之，分割式聚类算法是反复的和爬坡式的，最后通常收敛于一个局部最小值。更深一步，由于相关目标函数是高度非线性的和多峰值的。因此，想要用爬坡技术发现一个最理想的数据分割方法是非常困难的事。基于像整数规划，动态规划还有分支界限法等组合优化方法的算法甚至对中等规模的数据点和中等
18、规模的簇代价都是昂贵的。对于聚类算法的更多细节可以在3中找到。 最简单而且最流行的反复和爬坡式聚类算法是K均值算法（KMA）。就像上文所说，这个算法可能收敛于一个次优区间。因为随机最有方法在避免收敛于局部最优结果方面有优势，因这些方法能够用于发现全局最优解。这些随机方法用于基于模拟退火法，遗传算法，演化策略和演化规划等聚类中4-11。往往，这些随机算法花费了大量时间在收敛一个全局最优区间。这篇论文中，我们提出一个基于GA的算法，证明他有概率收敛于全局最优解，而且把他的性能和和其他相关算法进行比较。 遗传算法(GA)编码的工作参数设置在搜索已经执行而不是参数自己。这些编码参数被叫做解决方法或染色
19、体而且在一个解决办法中目标函数值的大小是目标函数值的大小相应的参数。GA解决优化问题的算法的使用群体的固定数目,也称为的群体大小的适当的解决方案。一个解决方案包括一个字符串的符号,即典型的二进制符号。GA进化到新的时代。经历每个时代，他们通过遗传方法，即自然原则，杂交和突变，从当前的群体中产生新的群体。每一个解决方案都在人口相关的数字的优点(健康价值)即根据价值的功能进行了优化设计。选择一个方案的选择算子从现行的人口为下一个人口比例概率健身价值。交叉两种求解字符串操作,导致两个蜇人。典型的交叉算子交换环节选定的刺穿过一个交叉点和概率。这个变异算子每一个字符串中切换位置与概率,叫做变异概率。想要
20、进一步研究GA，读者可以查阅12。最近,研究已经表明, 选择算子渐近收敛到全局最优的之前或之后是GA的维护最好的解决方案13。 这里有很多使用GA进行聚类的尝试如7,8,11。尽管所有这些算法,因为突变收敛于全局最优, 从计算的效果来说他们面临着下面的问题从算法的角度讲是在染色体的表示方法容易交叉、健康评价和7一样昂贵 。在算法中当健康评价是简单的,要么交叉操作复杂要么需要反复应用在染色体上来得到一个合理的字符串8,11。从这个角度讲上, 在对付不同的计算复杂度时选择和交叉是互补的。 当在考虑中的搜索空间的表达有一个自然的结构以至于产生有效编码更容易。同时遗传算在就这个问题必须对代码产生有效的
21、解决方案。为了能够有效地利用GA在各种应用中，可以通过与传统的梯度下降方法杂交来生成一种的特别的GA以应对这个在考虑中的问题。一个混合GA是有可能现今特性最好的算法，可能是对这个在考虑中问题的最好算法。Davis也说过这些在他的指南中14。因为KMA是非常的吸引人，外加他的简单易懂，所以我们选择这个算法来杂交。得出的杂交算法就叫做基因K-均值算法（GKA）。我们使用K-均值算子，即KMA的一步，来代替GKA中交叉算子在传统遗传算法中的使用。我们也专门为聚类定义了一个叫远程基础突变偏颇的变异算子，并使用它在GKA中。因此，GKA结合了k-均值算法的简洁和GA算法的适应的天性。利用有限马尔可夫链理
22、论,我们通过GKA的参数的条件得出收敛到一个全局最优的分区。 我们进行实验来分析在不同数据集和不同尺寸的搜索空间中运算子用于GKA的有效性和性能。通过模型分析,我们通过显示即使当许多重复的KMA不同初始分割开始跑,而且最好的隔断未必是获得全局最优,但是几乎每一个运行而GKA最终收敛到整体最佳的分区。我们也进行了GKA与一些基于遗传算法，进化策略与进化规划等算法的性能指标对比，其中一些也可以收敛到整体最优，结果表明GKA比他们更快。在下一节里，对于在考虑中的问题的KMA的简短描述声明将会被给出。该算法将会在第四章里介绍。在第五章中，我们通过GKA的参数的条件得出收敛到一个全局最优的分区。2.1.
23、2聚类算法 聚类算法主要考虑的主要目标是区分一些给定的N模式，每个模式是一个向量d在k组以至于分区最大限度的减少了TWCV，它的定义如下。让xi，i=1,2,，n作为n模式的集合。Xij代表xi的第j特征。定义i=1,2，n和k=1,2，K， wik=1,如果第i个个体属于第k个簇0，否则 (1)然后，矩阵W=wij就有了如下性质 wij0,1和j=1Kwij=1 (2)让第K簇的质心为ck=(ck1 ，ck2 ，ck3 ，ckd)，然后 ckj=i=1nwikxiji=1nwik (3)第K簇的簇的内部的变种被定义为S(k)w=i-1nwikj=1dxij-ckj2 (4)所有的簇的内部变种
24、（TWCV）被定义为SW=k=1KSk=k=1Ki=1nwikj=1dxij-ckj2 (5)有时这也被叫做平方误差（SE）测量。目标是去发现W*=w*ik它最小化S(W)，举个例子 SW*= minwSWKMA是应用最为广泛,找到一个分区算法使得SE测量最小。KMA有许多变化 3。下面我们简要说明了它的一个会被用在GKA的发展简单的变异。KMA是一个迭代算法。它开始与一个随机配置聚类中心。在每一个迭代,每一个模式被指定到集群,他的中心是最近的中心在所有的模式聚类中心。聚类中心下一次迭代仿真模式是属于相应的集群。聚类中心下一次迭代是属于相应的集群的仿真模式。该算法在没有终止调动任何模式的另一种
25、方法改变,或从一个集群的SE测量后停止受到严重影响的反复而终止。一个主要的问题是如果最初的隔断是不恰当的选择，那么该算法对选择最初的分区敏感而且可能会收敛到局部最小SE。2.3基因K-均值算法 像GA一样，GKA也有群体的编码方案。群体一开始随机初始化而且进化到下一代；下一代的群体通过应用基因算子从当前代中得到。直到演化发生终止条件达到了。在GKA所使用的遗传算子是选择,距离的基础的突变,k -均值算子。在这篇文章里,我们根据指定的编码和初始化方案,遗传算子解释GKA。1）代码：这里的搜索空间是所有满足（2）W矩阵的空间。自然方式编码这样的W转化的一个字符串，sW，考虑一个染色体长度n而且允许
26、每一个基因等位体从1,2,3，K染色体得到结果。在这种情况下,每一个等位基因对应一个模式而且一个值代表集群相应的模式的归属的号码。这肯定能因为参考（1）对于所有i，wik=1只有唯一的一个k。这种类型发的代码叫string-of-group-numbers 编码8。GKA有一个这样的字符串群体。2）初始化：随即选择初始的种群P(0)。每个在种群中的等位基因都可以随机的从均匀分布的集合1,2，K中选择一个集群摘要。在这种情况下，我们最终可能带来非法串,在非零概率下字符串中有些代表一个分区集群是空的。这可以通过分配P，那些小于n=k的最大整数，即每一个簇对应随机被选择的数据点，而且剩下的点通过分配
27、给随机挑选的簇来避免。3）选择：选择算子从以往的群体随机选择一个染色体，分布根据Psi=Fsij=1NFsj (6) 其中F（si）表达在群体中字符串si的适度值，而且定义在下一个分段中，我们用转轮策略处理子二个随机选择机制。 在现行群体的解决方案是基于它在下一个群体中生存的优点来评价的。这要求每一个在群体中的解决方案要与灵敏值或适度值相关。在目前的上下文中，适应价值的解决字符串sW取决于整个簇的内部变异值S(W)。因为目的是减少S(W)，一个字符串要有相对小的平方误差，那它必须有较高的适应值。有许多这样的方式定义适应度函数12。我们为了这目的使用-切断机制。让（sW）=-S（W），g（sW）
28、=（sW）-(f-c)，其中f和分别代表当前群体的平均值和（sW）的标准差。C是1到3之间的常量。因此，适度值的常量，如下FsW=gsW,如果gsW00, 否则 （7）4）突变：一个等位基因突变改变价值取决于各类的聚类质心到相应数据点的距离。他可能会被回忆起来, 其中每一个基因等位体对应每一个数据点，它的值代表聚类数据点的归属。一个算子被定义，如果相应的簇类中心更接近于数据点，那么改变一个等位基因值到簇类值的可能性会更多。为了应用突变算子到对应于模式的等位基因，让作为，之间的欧几里得距离。然后，这个等位基因就被从如下分布中随进选取的值所替代：pj=PrsWi=j=cmdmax-dji=1Kcm
29、dmax-di (8)其中是一个通常的常量而且。万一在一个分区的情况下与一个或一个以上的单件模式的集群在第四节将会被介绍，因为我们需要对于所有的j是非零的来证明GKA的收敛。这强迫严格大于1。在非零的概率下，上述的突变可能导致空的簇的形成，这提醒我们越小数目的簇，SE的值越大。一个快速检测形成空的簇可能性的方法是检查是否数据到它的簇的中心的距离大于零。这提醒我们即使万一非单一簇在数据点中那么簇的中心是相同的。因此，一个等位基因只有当0时才突变。代表K个非空的簇的字符串叫合法字符串；否则，就叫非法字符串。每个在染色体中的等位基因突变发生的概率叫做突变概率。我们在后续篇幅中叫他突变DBM1。在第五
30、章里这些突变将会帮助我们得到更好的结果。这个算子的伪代码如下所示。Mutation(sW)for i=1 to nif (rand()0)dmax=maxd1,d2,dKFor j=1 to K,pj=cmdmax-djk=1K(cmdmax-dj)sW(i)=根据p1,p2,p3随机从1,2K中选择一个;(drand()返回一个从0,1的一个整体分布数)5）K-均值算子：该算法以上述的选择和变异算子可以花更多的时间去收敛，因为最初的作业是任意的和随后的变化作业是概率性的。而且，突变的概率被迫采用更低的值，因为高值的导致算法的震荡。为了去改进这个形式，K-均值算法的一步，叫K-均值算子，被介绍
31、。让作为一个字符串。下面的两步就是KMO作用在产生：1)用给定的矩阵通过（3）计算来计算簇的中心。2）再把每个簇中的数据点再分配给最近的簇的中心以形成。这个简化的算子是有代价要付的。结果字符串可能表达了一个空的簇的分区。KMO可能会导致非法的字符串。我们通过创建需求数量的新的单一的簇来转化非法字符串为合法字符串。这通过放置有最大的簇内变异的簇C中的一个模式x到每个空的簇中参考（4）。X是簇C距离簇中心最远的。因为KMO和DBM1被一次又一次的应用到这些字符串中，我们不必关心分裂是怎么完成的。我们选择像上面那样做因为这个技术是最有效率的而且计算代价最小。6）GKA：在下面中给出了GKA的一段伪代
32、码。开始，初始种群的产生如上所述，随后的种群通过应用性选择，DBM1和KMO从之前的种群中得到。当世代的数量超过了限制算法便终止。这个算法的输出是算法进化过程中遭遇过的最好的结果。遗传K-均值算法输入：突变概率，Pm；种群尺寸，N；最大迭代数，MAX_GEN；输出：结果字符串，s*；种群初始化P；Geno=MAX_GEN；s*=Pi;(Pi是P中第i个字符串)当（Geno0）计算P的适度值；P=SelectionP;For i=1 to N , Pi=MutationPi;For I =1 to N, K-Means(Pi)；S=P中SE值最小的一个；IfSWs*S(WS),s*=s;Geno
33、=geno-1;Output s*2.4算法证明 这章将会显示使用限定马尔科夫链理论导致权威基因算法收敛到全局最优13.我们通过沿着相同路线的GKA参数推导条件确保对全局GKA的收敛性来证明GKA的全局收敛。Prt=ptt-1=pt-1,0=p0=Prt=pt|t-1=pt-1 当通过GKA在t世代中维护代表种群时，某步骤。这个过程的状态空间是所有可能种群S的空间而且转台可以从1数到。就像之前提到的，状态空间受限于包含合法字符串的种群，即有K个非空的簇的字符串所表达的区间。从GKA的定义中可以看出，能够被表达。今后是一个马尔科夫链。同样，转换概率是独立的时间的瞬间，即，如果pij(t)=Prt
34、=pj|t-1=pi则对所有的和所有的s,t1成立。因此，是一个以时间同质的有限马尔科夫链。让P=（pij）作为的转化矩阵。进入矩阵P要满足和。任何矩阵满足上述条件的条目成为随机矩阵。下面将会给出一些将会在这节剩下内容中使用的定义。定义1：一个正方形矩阵A：如果，时被成为正，如果存在一个正整数k以至于是正数时，被叫做原始的。一个正方形矩阵被叫做纵列-许可，当它至少有一个正的在每个队列。在下面的理论中，P被要求是原始矩阵。因此，首先我们研究那些作用在原始矩阵P的算子的条件。由在GKA中使用操作算子导致在种群中随驾变化的染色体被转换矩阵P抓住，它能够用一种自然的方法分解为一个的随机矩阵，其中K,M
35、和S描述分别由K-均值突变和选择算子所导致的间接转化。命题2：让K,M和S作为随机矩阵，其中M是正的，S是纵列-许可的。则是正的。因为每个正矩阵都是原始的，很明显可以发现使M为正，S为纵列-许可的条件。突变的条件：矩阵M是正的，任意的字符串可以从任何其他的字符串中应用相应的突变算子得到。根据之前的定义突变算子（DBM1）不能确定这个因为当时等位基因可能不是突变的。DBM1轻微的修改使得相应的转换矩阵M为正。修改算子被引用为DBM2。DBM2改变每个等位基因，不考虑的值，根据（8）中的分布。这可能导致一些时带有一些很小的概率导致=0的非法的字符串。如果这些操作导致一些非法的字符串，那么重复之前的
36、操作直到我们得到一个合法的字符串。如果在（8）中完全大于一种一个那么所有的则完全大于0。这暗示DBM2在非零的概率下能够改变任意合法字符串为任意其他的合法字符串。因此，转换矩阵M对应于DBM2是正的。条件选择：一个字符串在当前种群的生存概率依赖字符串的适应值；因此对于归功于选择的转换矩阵S也是一样的。如果适应函数被定义如(7)，那么几乎不可能这样说S。下面对适应函数的修改将会确定S的纵列-可行性。让FsW=csSmax-SW (9)其中是我们在当前一代且1之前遇到的最大平方误差。然后在种群中所有的字符串的适度值都完全为正而且种群中任意字符串的生存概率在选择后也完全为正。因此，选择而且不改变现在
37、状态的概率能够被限定如下：siiFs1l=1NFslFsNl=1NFsl=l=1NF(sl)(l=1NF(sl)N0iS其中是种群中被考虑的第个字符串。尽管这个这肯定会在繁殖过程中改变，但它总是为正。因此，按这个修改的S是纵列-可行的。5）理论3：让座位权重矩阵（1）对应字符串s。让，其中是字符串，在GKA进化过程中直到时间瞬间t之前所遇到的最小的SE值。 让有 DBM2，成为一个突变算子而且适应函数像（9）一样被定义。则limtPrXt=S*=1 (10)其中S*=minSi|iT，T代表所有合法的字符串。简要证明：它已经被证明在13,原理6，一个转换矩阵P是原始的且很长一段时间内保持最好的
38、结果的权威GA收敛于全局最优如（10）所示。根据假设的理论，GKA的转换矩阵是原始的。根据上文这是显而易见的。我们注意到GKA在Fig.1中保持着最好的结果发现直到当前的时间瞬间。因此，这个理论遵循13，理论6。之前的理论暗示通过GKA能够遇到最小SE值的字符串直到t时刻，收敛到全局最优的而且概率为1。注意1-关于突变：DBM1 比DBM2有更少的计算代价。因为两个突变算子的在GKA上的性能是一样的，所以我们用更早的那个来模拟。我们观察到的之中较小的变量对GKA的性能没有明显的影响。因此，模拟的结果在下一章中介绍，是集合中的一个。注意2-关于适应函数：GKA用（7）或（9）作为适应函数来模拟。
39、我们可以注意到-截断技巧表现的比气态技术要更好一点，所以，我们使用-截断技巧作为这次的试验研究。2.5实验验证 在1中，文章作者对于上诉算法进行了验证，他利用两个数据进行验证，证明了KMO和DBM1的重要性。有和没有KMO的GKA都被用于数据集中。尽管我们能够经过分析显示GKA没有KMO渐进的收敛于全局最优。经过最初以几代算法的速度变得很慢。作者说可以观察到观察到KMO显著地增加了算法的收敛速度。事实上，主要原因是使用了在GA算法的中的梯度下降步骤。作者在下一个实验中，有或没有DBM1的GKA都被用于数据集中。作者观察到没有DBM1的GKA尽管在10个在运行的中最小的SE达到了已知最好的优化，
40、但平均值依然在一个很高的水平。这显示没有突变的GKA不是总是确定达到了全局最优。对于任何进化算法，越低的突变率会使GKA收敛的越慢，而越高的也会降低GKA的收敛。会造成如此结果是因为在低突变率下，突变在字符窜上的应用很难，而在高突变率下，染色体改变频繁导致算法没有时间去围绕结果开拓搜索空间。事实上，这是唯一一个能控制GKA性能额参数。因此，两个算子，KMO和DBM1,扮演者非常中演的角色；KMO帮助增加收敛的速度而DBM1帮助GKA的全局收敛。对于GKA的性能：作者把 GKA被应用在数据集中不同数量的簇上。可以发现到当簇的数目增加时GKA花费了跟多的时间去实现优化分区上。我们可以清楚地预料到簇
41、数目的增加了搜索组合空间的大小，因此导致寻找全局最优解变得更困难。无论如何，在所有的实例中我们可以看到平均SE最终还是收敛到全局最优。这是同时从之前的部分中到处的收敛结果。GKA和K-均值算法（KMA）的比较： GKA的中，平均SE值很接近最好的SE值，然而KMA却不是。几乎每一个GKA最终收敛到一个全局最优分区。KMA的性能一点也不令人惊讶，因为KMA代表性的收敛到局部最优。因此可以推断即使KMA和GKA有相同数量的初始配置，他也不能保障达到全局最优。当搜索空间更大而有更多的局部最优时，形势会变得更糟。数据也显示在每一个迭代/世代，最好的而且平均的SE对应的GKA要少于那些对应的KMA。在每
42、个世代中GKA创造额外的计算努力，是他的DBM1和选择算子。GKA的复杂度：SE估计的复杂度是一个给定的字符窜，突变算子的复杂度是，K-均值算子的复杂度是。因为突变率是非常小的，所以算子应用在字符窜上的等位基因的有效次数只是整个等位基因的一小部分。而且，K-均值算子是一个梯度下降算子而且它一旦到达了局部最优除非字符串被突变打扰了都不会改变字符窜。并且由于KMO是注定的，当一个字符串在之前的世代中没有改变则没有必要再应用KMO在这个字符窜上了。事实上，KMO只是应用在进化的初级阶段。在之后的阶段，他只有在字符串被突变打扰了才有用。因此，当在世代中字符窜的改变被储存，计算的效率能够被较少。ES和E
43、P的复杂度：在ES中，每个结果包含中心和与每个中心的成分相关的策略参数。在每个世代，算法计算所有在世代中字符串的适合值。通过随机祝贺选择结果和通过添加高斯噪音在每个中心成分中去突变每个结果来使得生成新的后代。尽管比赛策略非常昂贵，ES中符合算子的存在使得ES和EP都计算代价昂贵。适应函数是像下面一样用于这些算法的。每个模式被指派到最接近中心的簇中。根据这些分配新的簇开始计算，然后数据就和之前一样再次指派到不同的簇中。结果的适合函数是这些分配的SE值。因此，在这些实例中适度值的计算花费是GKA中的两倍。前面所给的ES和EP，估计100个结果的适应值，这些适应值中包括每一代父母和后代的。这使得这些
44、算法的适应计算四次才和GKA在每一代上的花费相同。即使我们假KMO在所有代中的结果中使用，计算的努力需要去发下SE值和在GKA中应用KMO和DBM1比那些需要用ES和EP去发现适度值花费更少（几乎3/4）.因此GKA的中提计算效果是比ES和EP小的。尽管平均SE在ES和EP情况下好像已经搜两道最好的SE值在这些例子里，没有什么正式的证据证明这些算法收敛到全局最优。7）GAX的复杂度：GAX操纵分区顺序的代表。在这些实例中每个染色体代表很多数据可能的分区。一个染色体的适度值是有最小SE值的分区的SE值。它是用复杂度为的动态规划算法。这是算法中计算最昂贵的算法。突变和交叉的复杂度是的复杂度分别是和
45、。所以，GKA明显比GAX更快。第三章 代码介绍本程序根据主要用C+语言实现上述算法，由于要保证C+的封装性，代码并没有完全按照上文的GKA伪代码描写，除了其中几个独立的步骤以外，整体流程和伪代码是一致的。首先，我们定义了两个类和一个外部数组，外部数组主要是存储数据，定义为double* Data，他可以根据数据需要动态生成doubleab数组，其中a是代表个体，而b是代表属性。它是那两个类函数的主要参数，下面大多数的数据都是根据它来得到。3.1类的介绍第一个类叫Pattern，主要是用来记录一个聚类模式的。数据成员包括 3个,int，一个,int *,3个double*，一个double*，
46、一个double。3个int分别定义为,int DataNum, int DataFeature, int cluster,分别储存数据个体数，数据属性，所要分的簇类数。一个int *定义为,int * CluBelong，储存每个个体所属簇类，主要根据公式（1）和（2）记录，3个double*定义为double*Direction，double*CenterData，double*probaility，第一个是储存每个个体到簇类的欧几里得距离，第二个是为了储存每个簇类中心的属性，第三个是为了储存每个属性突变的概率。一个double *定义为double *SE，为了储存每个簇的方差，而最后一个dou