基于遗传算法模拟退火算法的聚类算法

基于遗传算法模拟退火算法的聚类算法聚类是一种无监督学习算法，用于将数据集分成不同的组或簇，使相似的数据点在同一组中。

聚类算法旨在找到数据集内的隐藏模式和结构。

遗传算法和模拟退火算法是两种常用的全局优化算法，可以帮助我们找到最优的聚类方案。

遗传算法（Genetic Algorithm, GA）是一种模拟自然界中生物遗传机制的优化算法。

它模拟了生物进化过程中的选择、交叉和变异等操作。

遗传算法的基本思想是通过不断迭代的方式，保留适应度（优良解）高的个体，并以此为基础进行选择、交叉和变异操作，最终找到全局最优解。

模拟退火算法（Simulated Annealing, SA）是一种基于物理退火过程的全局优化算法。

它模拟了物质冷却的退火过程，通过允许一定概率的“错误移动”以跳出局部最优解，最终找到全局最优解。

将遗传算法和模拟退火算法结合起来，可以得到一个更强大的聚类算法。

这种算法首先使用遗传算法对初始的聚类方案进行初始化，并通过适应度函数对每个个体进行评估。

然后，算法使用模拟退火算法对聚类方案进行迭代优化。

在每个温度阶段，通过改变个体之间的距离以及聚类之间的距离，尝试将方案从当前聚类状态迁移到下一个更优状态。

模拟退火算法中的退火过程可以通过控制温度参数来实现。

1.初始化种群：使用遗传算法随机生成初始的聚类方案。

每个个体表示一种可能的聚类方案。

2.计算适应度：对每个个体使用适应度函数进行评估。

适应度函数可以根据聚类方案的内聚性和分离性来定义，以及其他适应度指标。

3.遗传操作：使用遗传算法的选择、交叉和变异操作对个体进行优化。

4.模拟退火：使用模拟退火算法对个体进行迭代优化。

通过改变个体之间的距离以及聚类之间的距离，尝试将方案从当前聚类状态迁移到下一个更优状态。

退火过程可以通过控制温度参数来实现。

5.终止条件：当达到迭代次数的上限或找到满足适应度要求的聚类方案时，停止迭代。

6.输出最优解：返回适应度最高的聚类方案作为最优解。

模拟退火算法在聚类分析中的应用研究随着数据时代的到来，数据量呈指数级别的增长。

对于人类社会而言，数据的积累和处理已经成为一种重要的社会资源。

以往的数据处理方法难以满足时代的需要，更加智能的算法成为必要选择。

聚类算法是一种将类似的数据归为一类的无监督学习方法，目前在数据挖掘、人工智能等领域得到广泛应用。

本文将介绍一种基于模拟退火算法的聚类分析方法，并探讨其在实际应用中的表现。

一、聚类分析简介聚类分析是一种将数据集中相似的数据归为一类的无监督学习方法。

具体而言，聚类分析通过计算不同数据点之间的距离，找出相似的数据点并将其归类。

常见的聚类算法包括K-means、层次聚类等。

这些算法在数据清洗、特征提取、数据分析等方面扮演着重要的角色。

然而，传统的聚类算法存在一些问题。

比如，当数据点的维度非常高时，距离计算的复杂度极大；此外，传统的聚类算法对于初值敏感，容易陷入局部最优解。

这些都限制了聚类算法的应用范围和效率。

二、模拟退火算法简介模拟退火算法是一种全局优化算法，其核心思想源于材料科学领域。

所谓“退火”，是指将金属材料高温加热后逐渐冷却，达到某种特定的晶体结构。

类比到算法中，是通过随机化搜索的方式来得到全局最优解。

模拟退火算法具有以下特点：1. 以概率接受较差的解模拟退火算法在搜索过程中，可能会接受较差的解，这样是为了避免陷入局部最优解。

2. 依靠温度下降调整搜索的方向在模拟退火算法中，随机化策略是关键。

但是，如果每一次搜索都是“盲目”的随机化，搜索的效率会非常低。

模拟退火算法通过设计不同的“温度”来调节随机化的强度，高温时随机性更强，低温时随机性减弱，可以逐步收敛至全局最优解。

三、基于模拟退火算法的聚类分析基于模拟退火算法的聚类分析，可以解决传统聚类算法的一些问题。

模拟退火算法在搜索过程中，可以避免陷入局部最优解，从而得到全局最优解。

同时，模拟退火算法具有随机性，可以逐渐接近全局最优解，减少出现次优解的概率。

基于模拟退火遗传算法的聚类分析
武兆慧;张桂娟;刘希玉
【期刊名称】《计算机应用研究》
【年(卷),期】2005(022)012
【摘要】将模拟退火遗传算法用于聚类分析,通过对聚类中心进行编码,定义适应度函数,选择、交叉、变异操作以及模拟退火算法的运用,给出了一种新的基于模拟退火遗传算法的聚类算法,实验结果显示该方法优于基本的遗传算法.
【总页数】3页(P24-26)
【作者】武兆慧;张桂娟;刘希玉
【作者单位】山东师范大学,信息管理学院,山东,济南,250014;山东师范大学,信息管理学院,山东,济南,250014;山东师范大学,信息管理学院,山东,济南,250014
【正文语种】中文
【中图分类】TP391
【相关文献】
1.基于模拟退火算法的数据聚类分析 [J], 高亮;王喆;孙卫
2.基于模拟退火遗传算法的纺纱车间调度系统 [J], 郑小虎;鲍劲松;马清文;周衡;张良山
3.基于模拟退火遗传算法的自动化立体仓库货位优化 [J], 曹现刚;宫钰蓉;雷一楠
4.基于改进模拟退火-遗传算法的FMS生产排程优化分析 [J], 陈应飞;彭正超;胡晓兵;李彦儒
5.基于模拟退火算法改进遗传算法的织物智能配色 [J], 许雪梅
因版权原因，仅展示原文概要，查看原文内容请购买。

基于遗传算法和模拟退火算法的混合算法的研究与应用基于遗传算法和模拟退火算法的混合算法是一种优化算法，结合了遗传算法的搜索能力和模拟退火算法的避免局部最优解的能力。

这种混合算法在许多领域都有广泛的应用，如机器学习、数据挖掘、运筹学等。

遗传算法是一种基于生物进化原理的优化算法，通过模拟基因的遗传和变异过程来寻找最优解。

它通过不断迭代，逐步淘汰适应度低的解，保留适应度高的解，最终得到全局最优解。

遗传算法具有全局搜索能力强、对初始解依赖性小等优点，但在处理复杂问题时可能会陷入局部最优解。

模拟退火算法是一种基于物理退火原理的优化算法，通过模拟金属退火的过程来寻找最优解。

它通过引入随机因素，使得算法能够在搜索过程中跳出局部最优解，从而找到全局最优解。

模拟退火算法具有避免局部最优解的能力，但对初始解和参数设置敏感，需要经验丰富的程序员进行参数调整。

基于遗传算法和模拟退火算法的混合算法能够结合两者的优点，提高搜索效率，避免陷入局部最优解。

这种混合算法的一般步骤如下：1. 初始化种群：随机生成一定数量的初始解作为种群。

2. 计算适应度：根据问题的目标函数计算每个解的适应度。

3. 遗传操作：根据适应度选择个体，进行交叉和变异操作，生成新的解。

4. 模拟退火操作：对新生成的解进行接受概率的计算，根据接受概率决定是否接受该解。

如果接受，则更新当前解；否则，继续搜索其他解。

5. 迭代：重复步骤2-4直到达到预设的终止条件。

基于遗传算法和模拟退火算法的混合算法在许多领域都有广泛的应用，如机器学习中的分类、聚类、回归等问题；数据挖掘中的关联规则挖掘、聚类分析、特征选择等问题；运筹学中的车辆路径问题、背包问题、旅行商问题等。

这种混合算法可以处理各种复杂的问题，并取得较好的优化效果。

收稿日期:2018-10-17 修回日期:2019-02-19 网络出版时间:2019-04-24基金项目:国家自然科学基金(6127123)作者简介:凌　静(1993-),女,硕士研究生,研究方向为下一代通信网络技术与物联网技术;江凌云,副教授,硕导,研究方向为下一代网络技术㊂网络出版地址: /kcms /detail /61.1450.TP.20190424.1047.036.html结合模拟退火算法的遗传K -Means 聚类方法凌　静,江凌云,赵　迎(南京邮电大学通信与信息工程学院,江苏南京210003)摘　要:K-Means 算法是一种经典的基于划分的聚类方法㊂传统的K-Means 算法中存在很明显的缺陷,它对初始聚类中心的依赖性很大,聚类结果很容易陷入局部最优值;而基于遗传算法改进的K-Means 聚类方法,提高了聚类结果的稳定性,但因为个体的多样性不足,常常会出现早熟等现象,其局部寻优能力较弱㊂针对上述问题,文中提出一种结合模拟退火算法的遗传K-Means 聚类方法㊂利用模拟退火算法改进遗传算法的变异操作,用K-Means 操作取代遗传算法的交叉操作,改善早熟现象,避免聚类结果陷入局部最优,实现聚类方法性能的提升㊂实验结果表明,该方法的聚类准确度比一般K-Means 方法和遗传K-Means 方法都要高㊂关键词:聚类;K-Means 算法;遗传算法;模拟退火算法中图分类号:TP18 文献标识码:A 文章编号:1673-629X (2019)09-0061-05doi:10.3969/j.issn.1673-629X.2019.09.012A Genetic K -Means Clustering Method Combined with SimulatedAnnealing AlgorithmLING Jing ,JIANG Ling -yun ,ZHAO Ying(School of Telecommunications &Information Engineering ,Nanjing University of Posts andTelecommunications ,Nanjing 210003,China )Abstract :K -Means algorithm is one of the most classical division -based clustering methods.In the traditional K -Means algorithm ,there are obvious flaws like strong dependence on the initial clustering center and the clustering result is easy to fall into the local optimal value.The improved K -Means clustering method based on genetic algorithm improves the stability of clustering results.However ,due to the insufficient diversity of individuals ,prematurity and other phenomena often occur ,and its local optimization is weak.For this ,we present a genetic K -Means clustering method combined with simulated annealing algorithm.The simulated annealing algorithm is used to improve the mutation operation of genetic algorithm ,the classical K -Means operation is used to replace the crossover operation of the genetic algorithm ,so as to improve the premature phenomenon ,avoid the clustering result falling into the local optimal ,and improve the performance of the clustering method.The experiment shows that the clustering accuracy of the proposed method is higher than that of the general K -Means method and the genetic K -Means method.Key words :clustering ;K -Means algorithm ;genetic algorithm ;simulated annealing algorithm0　引　言迄今为止已经有了多种聚类算法,根据数据在聚类中的积聚规则,以及应用这些规则的方法,聚类算法主要可以分为[1]:基于划分㊁基于层次㊁基于网格㊁基于密度以及基于模型等类型㊂聚类算法被广泛应用于模式识别㊁图像处理㊁文本检索㊁网络入侵检测㊁生物信息学等领域㊂其中,K -Means 聚类算法是最为经典的一种聚类算法[2],优点是简单有效㊁收敛速度快㊁局部搜索能力强;但也存在难以克服的缺陷,如过度依赖初始聚类中心㊁聚类结果极易陷入局部最优解㊁全局搜索能力不强等㊂针对K -Means 聚类算法过度依赖初始聚类中心,全局搜索能力不强的问题,已经有了大量的研究成果,如文献[3-4]中提出的遗传K -Means 算法㊁优化遗传K -Means 算法等㊂这些结合遗传算法的改进方法,有效提高了K -Means 聚类算法的稳定性和全局性,但遗第29卷　第9期2019年9月 计算机技术与发展COMPUTER TECHNOLOGY AND DEVELOPMENT Vol.29　No.9Sep.　2019传算法自身存在早熟现象,且其局部寻优能力较弱㊂文中提出一种结合模拟退火算法的遗传K-Means聚类方法㊂配合局部寻优能力强的模拟退火算法改进遗传算法的缺陷,得到性能在两者之上的遗传模拟退火算法,再将其应用于K-Means算法,从而提高K-Means聚类算法的性能,实现聚类结果的优化㊂1　相关工作1.1　K-Means算法、遗传算法与模拟退火算法K-Means算法是一种基于划分的经典聚类算法,是由Mac Queen于1967年提出的,他结合Cox㊁Fisher㊁Sebestyen等的研究成果,给出了K-Means算法的详细步骤,并用数学方法对K-Means算法进行了证明㊂K-Means算法的主要思想[5]是:对n个给定的对象,给出k个划分,每个划分代表一个类,其中k≤n㊂首先,从给定的所有对象中任意选择k个对象,作为k 个类的聚类中心㊂对剩余对象,分别计算它们与各个聚类中心的相似度,分到相似度最高的类中;分类完成后,计算新类的平均值作为新的聚类中心,再计算所有对象与新聚类中心的相似度,将对象分到最相似的类中㊂不断重复直到准则函数的值达到最小,准则函数定义如下:J=∑k j=1∑x i∈c‖x i-z j‖2(1)其中,k为类别数;x i为样本对象;z j为类c j的聚类中心㊂遗传算法(GA)是一种全局优化自适应概率搜索算法,由Holland于1975年提出的㊂该算法模拟了生物的繁衍㊁交配和变异现象[6],在初始种群的基础上产生新的更适应环境的种群,一代代繁衍进化,最终收敛到一个最适应环境的个体上㊂在搜索过程中,该算法能够自动获取搜索空间的相关知识,并积累获得的信息;通过对搜索过程的自适应控制,能够获得问题的最优解㊂遗传算法使用适应度函数作为度量标准,通过计算群体中的每个个体的适应度函数值,来判断个体的优劣程度㊂适应度函数值越高,个体越优秀,就越有可能被遗传到新种群中,成为最适应环境个体的概率也就越高㊂一般会根据实际情况设计相应的适应度函数㊂模拟退火算法(SA)又被称为模拟冷却法㊁概率爬山法,是由Kirpatrick于1982年提出的㊂模拟退火算法是模拟了一个高温固体的退火过程[7],在搜索过程中,开始先设定一个温和的初始结果作为最优解,然后随机获得一个新解,当得到的新解优于当前最优解时,直接接受新解为最优解;当新解劣于最优解时,以一定的概率接受新解为最优解,随着温度的下降重复上述操作,最终得到全局最优解㊂模拟退火算法利用了概率的突跳特性,具有并行性和渐近收敛性,理论上能够证明,模拟退火算法是以概率1收敛于全局最优解的㊂1.2　遗传模拟退火算法在遗传算法运行过程中,早期种群的个体之间差异较大即个体适应度函数值差异较大,而在通过选择算子生成下一代新种群时,新种群的子个体出现概率与上一代种群中父个体的适应度函数值成正比,也就是说,适应度值越高的个体越容易遗传到下一代种群中,这就容易出现优秀个体占领整个种群,形成早熟现象㊂后期,整个种群中的个体适应度值基本一致,差异较小,这就导致优秀个体在生成下一代种群个体时的优势较小,造成整个种群的进化停滞㊂因此,在算法运行过程中可以对个体的适应度函数值进行适当拉伸㊂模拟退火算法中按照Metropolis准则[8]接受新解,除了接受优于当前最优解的新解作为新的最优解,还能以一定的概率接受劣于当前最优解的新解㊂在算法早期,温度值T较大,能够接受较劣的新解㊂随着算法不断运行,T值也在不断变小,当前最优解的值会越来越逼近整体最优解,当T值接近0时,当前最优解最接近整体最优解,能够避免算法陷入局部最优㊂遗传模拟退火算法是一种优化算法[9],在算法前期,种群中个体的适应度相差较大即存在较为突出的优良个体,而此时温度较高,有较大可能接受较差的个体,避免种群过早集中于优良个体;而在算法后期,种群中个体的适应度函数值较为接近,此时温度较低,模拟退火算法能对遗传算法中这些个体的适应度函数值进行拉伸,放大这些个体之间的适应度差异,提高优秀个体在选择过程中的优势㊂遗传模拟退火算法能够更加快速有效地收敛到全局最优解㊂已有许多研究尝试将遗传算法与K-Means聚类算法进行结合,以改善K-Means聚类算法的缺陷㊂文献[10]将基于准则函数的经典聚类算法K-Means引入到遗传算法,用K-Means算法的一步 K-means操作(KMO)代替标准遗传算法中的交叉操作,这样既能利用遗传算法确保聚类结果的稳定性,又能借助K-Means算法提高混合算法的收敛速度㊂该算法融合了遗传算法与K-Means算法,保证了算法的全局搜索能力,也保证了算法的简单有效,同时还具有爬山能力㊂然而遗传算法自身还存在早熟㊁局部寻优能力弱等缺点㊂为此,在文献[10]的基础上,文中提出一种结合模拟退火算法的遗传K-Means聚类方法㊂将模拟退火算法引入已有的遗传K-Means 算法,保留K-Means操作取代交叉操作的方法,通过模拟退火算法增强聚类方法的局部搜索能力,实现聚类结果的进一步优化㊂㊃26㊃ 计算机技术与发展 第29卷2　结合模拟退火算法的遗传K-Means聚类方法标准遗传算法中包括选择操作㊁交叉操作以及变异操作㊂文献[10]提出的方法在遗传算法中引入K-Means操作代替交叉操作,文中在其基础上,引入模拟退火算法对遗传算法的变异操作进行改进,改善遗传算法的早熟缺点,避免结果陷入局部最优,提高原有遗传K-Means聚类算法的性能,从而实现聚类结果的优化㊂该方法的整体结构如图1所示㊂图1　聚类方法整体结构2.1　样本编码样本编码[11]是遗传算法的基础操作,要将问题的解进行编码才能进行后续操作㊂遗传算法有多种编码方式,如符号编码㊁二进制编码㊁浮点数编码等㊂在聚类样本维度高㊁数量大时,如果采用传统的二级制编码方式,种群中的个体编码长度会随着维度的增加㊁精度的提高而出现显著增加的情形,从而导致整个搜索空间的增大,影响聚类方法的计算效率㊂因此文中采用的是一种基于聚类中心的十进制编码方式㊂具体编码方式如下:设一个数据集中的样本个数为n,最终聚类的类别数目为k㊂有k个聚类中心,每个中心对应一个类别号,计算所有样本到各个聚类中心的距离,将其划分到相应的类中,编码值对应样本所属聚类的类别号,最终编码长度l=n㊂如图2所示, Sn为聚类的类别号,编码总长度为n㊂图2　样本编码举例:一个数据集为{x1,x2,x3,x4,x5,x6},类别数目k=3,分类模式为1{x1,x4}2{x3,x6}3{x2,x5},则编码为(132132),编码长度l=6㊂文中采用的这种基于聚类中心的编码方式直观明确,相比二进制编码有效缩短了个体编码的长度,提高了整体的计算效率,对于大数据复杂问题的求解效果较好㊂2.2　种群初始化文中采用随机方式生成初始种群,具体方法为:从样本空间中随机选出k个样本作为聚类中心,将所有样本按其到各个聚类中心的距离分类到k个类中,得到一个个体,计算此时的个体编码S n;设种群大小为sizepop,将上述操作重复进行sizepop次,即可得到初始种群P0㊂2.3　适应度函数适应度函数[12]会影响整个聚类方法的收敛速度,以及对最优解的确定㊂一般使用适应度函数来衡量个体的适应度,判别该个体在种群中的优劣程度㊂某个体适应度的值越大,该个体在整个遗传过程中的存活概率也就越大㊂K-Means算法中判断聚类划分质量的标准是准则函数J,J的值与所有聚类中的点到相应聚类中心的距离总和相等㊂J的值越小,表明该聚类划分的质量越好,反之表明该聚类划分的质量越差㊂对于种群中的每个个体,根据准则函数J来构造适应度函数,适应度函数定义如下:F(Si)=1.5×J max-J(S i),i=1,2, ,sizepop(2)其中,J max是种群中所有个体的准则函数值的最大值;J(S i)是当前个体的准则函数值㊂根据函数定义可以看出,准则函数J的值越小,该个体代表的聚类划分的质量越好,适应度函数值越大,其存活概率也就越高㊂2.4　选择操作选择操作[13]遵循优胜劣汰原则,以个体的适应度函数值为基础,由父种群选出新种群㊂在进行选择操作时,适应度函数值越大的个体经过选择操作后,遗传到新种群中的概率就越高,反之被遗传到新种群中的概率就越小,经过多次选择操作得到的个体组成新种群㊂选择操作常用的方法有轮盘赌选择法㊁最优个体保留法㊁锦标赛选择法[14],文中使用轮盘赌方法来进行选择操作㊂轮盘赌方法是将种群中所有个体适应度函数的总和,作为轮盘的整个圆周,按照每个个体的适应度值在总和中所占的比例,为其分配轮盘中相应大小的扇区㊂每选择一个个体就是随机转动一次轮盘,转动轮盘后选中哪个区域,就选择该区域对应的个体作为新种群的个体㊂在轮盘赌方法中,面积越大的区域越有可能被选中,反之被选中的概率就越低,而适应度函数值越大的个体其面积也就越大㊂种群P中第i个个体的适应度函数值为F(S i),则个体i被选中的概率为:㊃36㊃　第9期 凌　静等:结合模拟退火算法的遗传K-Means聚类方法P i =F(S i)∑k i=1F(S i),i=1,2, ,sizepop(3)在父群体中进行sizepop次选择,即生成新种群P1㊂2.5　模拟退火变异操作变异操作[15]按位进行,在个体编码时每个样本都有多个可能的编码值,变异就是将指定位置的样本的现有编码值,按变异概率P i用其余的可能值进行替换㊂文中使用的是均匀变异操作,具体过程为:对个体编码上的每个样本点,依次进行变异操作,也就是按概率P i从样本现有的类别号中选一个编码值替代原有值,最终得到新个体㊂变异概率P i定义如下:P i =1.5×d max(x i)-d(x i-c k)+0.5∑k k=1[1.5×d max(x i)-d(x i-c k)+0.5](4)d max(x i)=max k{d(x i-c k)}(5)其中,d(x i-c k)是样本x i与第k个簇的质心c k之间的欧几里得距离㊂引入偏差0.5是为了避免除0错误㊂这里采用的概率P i不是固定值,使得个体上每个基因座的变异概率都不同,能够大幅度提高个体的变异概率,进一步避免遗传算法的早熟现象㊂在均匀变异操作的基础上引入模拟退火算法㊂具体操作为:首先给定初始温度T0,终止温度T e以及模拟退火算法内部最大迭代次数N㊂将个体原有的准则函数值作为当前解f,经过均匀变异操作后形成的新个体的准则函数值作为新解f',两者差值记为Δf= f'-f㊂当Δf≤0时,直接接受新解为最优解,即将新个体替代种群中的原有个体;当Δf>0时,以概率p= exp-Δf KT接收新解为最优解,其中K为常数,T为当前温度㊂将上述操作重复N次,判断当前温度T是否达到终止温度T e,没有达到就按照降温等式T(t)=T0×a×t来降低当前温度值,其中a为降温速度,t为当前T值,再重新进行模拟退火变异迭代;如果达到终止温度T e则终止算法,得到新个体㊂对父种群P1中的每个个体都进行上述模拟退火变异操作,得到新群体P2㊂2.6　K-Means操作为了加速聚类算法的收敛过程,使用K-Means算法中的一个步骤,即K-Means操作(KMO)代替遗传算法中的交叉操作㊂K-Means操作的具体过程为:经过选择操作,模拟退火变异操作后得到新的种群P2㊂对群体P2中的某个个体,根据其现有的聚类结果计算新的聚类中心,计算方法如下:z*j=1n j∑x m∈z x m,j=1,2, ,k(6)然后计算数据集中所有样本到这些新的聚类中心的距离,并将样本分配到距离最近的类中,从而获得新个体㊂对父种群P2中所有个体都进行KMO操作,形成新的种群P3㊂然后再进行下一轮遗传操作㊂2.7　聚类方法的具体过程文中聚类方法主要包含2层循环:外层为遗传K-Means算法的进化循环,内层为模拟退火算法的降温循环㊂算法的具体过程(见图3)如下:(1)初始化控制参数:聚类个数k,种群个数sizepop,最大迭代次数MAXGEN;退火初始温度T0,温度冷却系数a,模拟退火内部迭代次数N,终止温度T e;(2)随机初始化k个聚类中心,依照聚类中心对各个样本进行聚类得到一个个体,重复sizepop次生成初始种群P0;(3)计算种群中每个个体的适应度值:F(S i),i= 1,2, ,sizepop;(4)对初始种群P0依次进行选择操作㊁模拟退火变异操作㊁K-Means操作,生成新种群;(5)重复步骤3和步骤4,直到达到最大迭代次数MAXGEN;(6)将最后生成的种群中适应度函数值最大的个体作为聚类结果输出㊂图3　聚类方法流程㊃46㊃ 计算机技术与发展 第29卷3　实验结果对传统K-Means算法㊁文献[4]中提出的遗传K-Means算法以及文中提出的结合模拟退火算法的遗传K-Means聚类方法进行了对比实验㊂实验工具为MATLAB软件,实验数据是来自UCI Machine Learning Repository的iris数据集和wine数据集㊂其中iris数据集包含150个数据,每个数据有4个属性,一共分为3类,每类各有50个数据;wine数据集包含178个数据,每个数据有13个属性,一共分为3类,每类分别有59㊁71㊁48个数据㊂分别编写K-Means算法㊁遗传K-Means算法以及文中的聚类方法,导入iris数据集和wine数据集进行测试㊂实验结果分别如表1和表2所示㊂表1　平均聚类准确度(iris数据集)%运行次数K-Means GKAM文中方法152.6784.6688.53264.6784.3290.9935684.7889.23467.2284.5989.58表2　平均聚类准确度(wine数据集)%运行次数K-Means GKAM文中方法159.2369.0371.43253.3769.4771.46357.8770.1371.24460.4969.8871.22 通过对表1和表2的实验结果进行分析,可以看出,与传统K-Means聚类算法相比,GAKM算法的准确率有了明显的提升,而且传统K-Means聚类算法中会出现计算结果的浮动,每次的聚类结果都会存在较大的差异,而GAKM算法相对来说就比较稳定,结果基本不会发生太大的变化㊂在iris数据集中,文中方法的平均聚类准确率最高能够达到90.99%,最低能达到88.53%,高于GAKM算法的84.78%;在wine数据集中,文中方法的平均聚类准确率能达到71.46%,同样高于GKAM算法中的70.13%㊂通过数据对比可以发现,文中的聚类方法相对GAKM算法平均聚类准确度有了提升,而且能保证聚类结果的稳定㊂标准K-Means聚类算法的计算结果受选取的初始聚类中心的影响较大,初始中心选择不当会导致结果陷入局部最优;基于遗传算法的K-Means聚类算法由于遗传算法自身的缺陷,容易出现早熟现象,其局部寻优能力较弱;文中提出的结合模拟退火算法的遗传K-Means聚类方法,充分利用模拟退火算法较强的局部寻优能力,改善遗传算法的缺陷,改善早熟现象,有效避免聚类结果陷入局部最优,最终获得的聚类结果要优于K-Means算法与GKAM算法㊂4　结束语提出一种结合遗传模拟退火算法的K-Means聚类方法,使用K-Means操作取代遗传算法的交叉操作,并引入模拟退火算法对遗传算法中的变异操作进行改进㊂该算法有效地解决了K-Means聚类算法过于依赖初始中心选择,易于陷入局部最优等问题,克服了遗传算法容易出现早熟现象以及局部搜索能力较弱的缺点㊂实验结果表明,该方法有效提高了K-Means 聚类算法的聚类精度,聚类结果更加准确㊂参考文献:[1]　周　涛,陆惠玲.数据挖掘中聚类算法研究进展[J].计算机工程与应用,2012,48(12):100-111.[2]　郁启麟.K-means算法初始聚类中心选择的优化[J].计算机系统应用,2017,26(5):170-174.[3]　KAPIL S,CHAWLA M,ANSARI M D.On K-means dataclustering algorithm with genetic algorithm[C]//Fourthinternational conference on parallel,distributed and gridcomputing.Waknaghat,India:IEEE,2016:202-206. [4]　LU Bin,JU Fangyuan.An optimized genetic K-means clust⁃ering algorithm[C]//International conference on computerscience&information processing.Xi’an,Shaanxi,China: IEEE,2012:1296-1299.[5]　王　千,王　成,冯振元,等.K-means聚类算法研究综述[J].电子设计工程,2012,20(7):21-24.[6]　葛继科,邱玉辉,吴春明,等.遗传算法研究综述[J].计算机应用研究,2008,25(10):2911-2916.[7]　汪松泉,程家兴.遗传算法和模拟退火算法求解TSP的性能分析[J].计算机技术与发展,2009,19(11):97-100. [8]　康立山.非数值并行算法(第一册):模拟退火算法[M].北京:科学出版社,2000:22-38.[9]　齐　平,贾瑞玉,贾兆红,等.用遗传模拟退火算法挖掘特征项权重的研究[J].计算机技术与发展,2007,17(2): 143-145.[10]LU Yi,LU Shiyong,FOTOUHI F,et al.FGKA:a fast genetick-means clustering algorithm[C]//ACM symposium onapplied computing.Nicosia,Cyprus:ACM,2004:622-623.[11]张超群,郑建国,钱　洁.遗传算法编码方案比较[J].计算机应用研究,2011,28(3):819-822.[12]刘　英.遗传算法中适应度函数的研究[J].兰州工业高等专科学校学报,2006,13(3):1-4.[13]张松艳.选择算子与遗传算法的计算效率分析[J].宁波大学学报:理工版,2009,22(3):374-377.[14]凌有临,李　强,史　俊,等.基于改进遗传算法的切削参数优化方法研究[J].机电一体化,2014(6):31-35. [15]贺永兴,杨　瑞,唐　伟,等.基于重构变异算子遗传算法的研究[J].计算机技术与发展,2015,25(12):101-104.㊃56㊃　第9期 凌　静等:结合模拟退火算法的遗传K-Means聚类方法。

模拟退⽕算法和遗传算法爬⼭算法在介绍这两种算法前，先介绍⼀下爬⼭算法。

爬⼭算法是⼀种简单的贪⼼搜索算法，该算法每次从当前解的临近解空间中选择⼀个最优解作为当前解，直到达到⼀个局部最优解。

爬⼭算法实现很简单，其主要缺点是会陷⼊局部最优解，⽽不⼀定能搜索到全局最优解。

如图1所⽰：假设C点为当前解，爬⼭算法搜索到A点这个局部最优解就会停⽌搜索，因为在A点⽆论向那个⽅向⼩幅度移动都不能得到更优的解。

模拟退⽕算法(SA)为了解决局部最优解问题， 1983年，Kirkpatrick等提出了模拟退⽕算法（SA）能有效的解决局部最优解问题。

模拟退⽕其实也是⼀种贪⼼算法，但是它的搜索过程引⼊了随机因素。

模拟退⽕算法以⼀定的概率来接受⼀个⽐当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。

算法介绍我们知道在分⼦和原⼦的世界中，能量越⼤，意味着分⼦和原⼦越不稳定，当能量越低时，原⼦越稳定。

“退⽕”是物理学术语，指对物体加温在冷却的过程。

模拟退⽕算法来源于晶体冷却的过程，如果固体不处于最低能量状态，给固体加热再冷却，随着温度缓慢下降，固体中的原⼦按照⼀定形状排列，形成⾼密度、低能量的有规则晶体，对应于算法中的全局最优解。

⽽如果温度下降过快，可能导致原⼦缺少⾜够的时间排列成晶体的结构，结果产⽣了具有较⾼能量的⾮晶体，这就是局部最优解。

因此就可以根据退⽕的过程，给其在增加⼀点能量，然后在冷却，如果增加能量，跳出了局部最优解，这本次退⽕就是成功的。

算法原理模拟退⽕算法包含两个部分即Metropolis算法和退⽕过程。

Metropolis算法就是如何在局部最优解的情况下让其跳出来，是退⽕的基础。

1953年Metropolis提出重要性采样⽅法，即以概率来接受新状态，⽽不是使⽤完全确定的规则，称为Metropolis准则。

状态转换规则温度很低时，材料以很⼤概率进⼊最⼩能量状态模拟退⽕寻优⽅法注意事项理论上，降温过程要⾜够缓慢，使得在每⼀温度下达到热平衡。

基于遗传算法和模拟退火算法的混合算法基于遗传算法和模拟退火算法的混合算法是一种将两种优化算法结合起来的方法，旨在克服两种算法各自的缺点，并发挥它们的优势，以获得更好的优化结果。

该混合算法可以分为两个阶段：遗传算法阶段和模拟退火算法阶段。

在遗传算法阶段，通过模拟生物进化的过程来最优解。

首先，需要定义问题的适应度函数，作为解决方案的评价指标。

然后，随机生成一组初始解作为种群，并通过适应度函数计算每个解的适应度值。

根据适应度值，进行选择、交叉和变异操作，生成新的解，并更新种群。

通过多轮迭代，逐步优化解的适应度值，直到达到停止条件。

然而，遗传算法在过程中会陷入局部最优解，并且速度相对较慢。

为了克服这些缺点，需要引入模拟退火算法阶段。

在模拟退火算法阶段，通过模拟物质的退火过程来最优解。

首先，需要定义初始解和问题的目标函数。

然后，定义一种温度下解的邻域结构，并通过目标函数计算解的值。

采用Metropolis准则来接受或拒绝新解，以便在空间中充分探索各个解。

逐渐降低温度，逐步缩小解的邻域范围，并最终收敛到最优解。

通过将遗传算法和模拟退火算法结合起来，可以克服两种算法各自的缺点，发挥它们的优势。

遗传算法具有全局能力和并行能力，可以大范围的解空间；而模拟退火算法可以在局部中跳出局部最优解，并且速度相对较快。

混合算法的核心思想是通过遗传算法来进行全局，找到一个较好的解，然后使用模拟退火算法在该解附近进行局部，进一步优化解。

混合算法的主要步骤如下：1.基于遗传算法生成初始种群，并计算适应度值。

2.通过选择、交叉和变异操作生成新的解，并更新种群。

3.迭代执行遗传算法阶段，直到达到停止条件。

4.使用遗传算法得到的最优解作为模拟退火算法的初始解。

5.基于模拟退火算法进行局部，使用目标函数进行评价。

6.逐渐降低温度，缩小解的邻域范围，并最终收敛到最优解。

通过混合遗传算法和模拟退火算法，可以充分利用遗传算法的全局和并行能力，同时利用模拟退火算法的快速优化能力和局部能力，从而获得更好的优化结果。