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

计算机光盘软件与应用　２０１２年第５期　Ｃｏｍｐｕｔｅｒ　ＣＤ　Ｓｏｆｔｗａｒｅ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ　工程技术　一种基于模拟退火的遗传聚类算法　张婧　（太原理工大学，太原０３００２４）　摘要：针对传统聚类算法中存在的较易陷入局部最优解等问题，在传统的Ｋ均值算法中引入了遗传算法和模拟　退火算法，将两种算法相结合，通过交叉、变异、模拟退火等操作，实现了聚类分析。通过模拟数据集的实验和ＵＣＩ　数据集的实验验证了算法的稳定性和获取全局最优解特性。　关键词：聚类；模拟退火；遗传算法　中图分类号：ＴＰ１８文献标识码：Ａ文章编号：１００７—９５９９（２０１２）０５—００７１—０２　一、引言　（７）继续进化；并判断是否满足算法结束条件，如果满　数据挖掘是从海量的数据中获取潜在的有用的知识。其中　足输出最优个体。　聚类分析作为数据挖掘的重要手段，主要思想是把样本数据划　四、实验分析　分为两个或多个类簇。同个类簇之间的样本数据相似度较大，　在ｍａｔｌａｂ环境下编写Ｋ均值算法、遗传算法和基于模拟　而类与类之间的相似度较小　。传统的聚类算法主要有基于划　退火的遗传聚类算法。通过模拟数据和ＵＣＩ数据集的聚类分　分的聚类算法、基于层次的聚类算法、基于密度的聚类算法、　析，对Ｌｔ－－种算法的实验结果，来验证算法的可行性、有效性　基于网格的聚类算法和基于模型的聚类算法　。其中较经典的　和稳定性。　聚类算法为ｋ－ｍｅａｎｓ算法，由于其实现简单、容易理解而被广　表４—１实验参数设置　泛应用。同时ｋ－ｍｅａｎｓ聚类算法由于其存在容易陷入局部最优　参数　人工数据　ＩｒｉＳ　Ｗｉｎｅ　Ｖｅｈｉｃｌｅ　解、对初始聚类中心敏感、对数据输入顺序敏感等缺点，在非　集　线性的样本空间上聚类效果较差。因此，广大研究学者对　种群规模　２０　５０　５０　７０　ｋ－ｍｅａｎｓ算法进行了深入研究，试图克服ｋ－ｍｅａｎｓ算法的这些　Ｐｃ　０．６－０．９　Ｏ．６一Ｏ．９　０．６－０．９　０．６－０．９　缺点。其中遗传算法是一种高效全局优化算法、该算法以适应　Ｐｍ　０．０１－０．２　０．０１－０．　０．０１一Ｏ．　０．０１－０．２　度函数为依据，通过对个体施加遗传操作，实现个体一代代地　２　２　优化并逐渐逼近最优解　。模拟退火算法在组合优化、ＮＰ难问　其中Ｐｃ为个体交叉概率，Ｐｍ为个体变异概率。　题中取得了良好的应用，能够提高算法的收敛速度，同时能够　实验１随机生成一组线性可分的模拟数据ＤＡＴＡ１，该组数　跳出局部最优、获得全局最优解　。　据服从正太分布，分别用三种算法对该数据集进行分析来验证　二、遗传聚类算法　遗传算法（简称ＧＡ）作为一种自适应全局优化概率搜索方　算法的可行性。　表４－２模拟数据ＤＡＴＡ１参数设置　法，它最早由美国Ｍ　ｉｃｈｉｇａｎ大学的Ｈｏ—ｌｌａｎｄ教授提出。该　算法具有很好的鲁棒性、随机性、全局性，现已被人们广泛地　参数　第一类　第二类　第四类　应用于以下主要应用领域：自动控制、图像处理、机器学习、　均值（ｕ）　ｕ　：Ｏ，ｕ　＝一０　ｕ　＝５，ｕ　＝３　ｕ　＝６，　一２　数据挖掘。遗传算法通过遗传编码、基因交叉、基因变异，不　标准差（ｏ）　Ｏ＝１　０＝Ｏ．５　ｏ＝０．５　断迭代最终找到相应的全局最优解。　表４—２为模拟数据集ＤＡＴＡ１的生成方法，分别用三种算法　三、基于模拟退火的遗传聚类算法　对其进行分析后得到的聚类中心和最小误差平方和如表４—３　（一）模拟退火算法　所示。　模拟退火算法（Ｓｉｍｕ　ｌａ　ｔｅｄ　Ａｎｎｅａ　ｌｉｎｇ　Ａ　ｌｇｏｒｉｔｈｍ）于　表４－３模拟数据集ＤＡＴＡ１实验结果　１９８３年成功地应用在组合优化的问题上。其思想是通过模拟　数据集　算法　聚类中心　最小误差平方　高温物体退火过程的方法来找到优化问题的全局最优或近似　和　全局最优解。模拟退火算法的基本步骤为：　ＤＡＴＡ１　Ｋ均值　５．９００３，一２．２３４４　２０．２８２　（１）初始化温度Ｔ，初始解状态Ｓ，迭代次数Ｎ。　０．４２０７，０．０５７７　（２）在解空间搜索新解Ｓ’。　４．８６４７，２．８４９６　（３）计算　Ｔ＝Ｐ（ｓ’）一　（　），其中Ｆ（Ｓ）为目标函　遗传算法　５．９００３，一２．２３４４　２０．２８２　数。如果　＜０则接受Ｓ’为当前最优解，否则随机产生一　０．４２０７，０．０５７７　个随机数　，其中　∈（０，１），根据Ｍｅｔｒｏｐｏｌｉｓ接受准则，　４．８６４７，２．８４９６　计算Ｐ＝ｅｘｐ（ＶＴ）／豫，如果Ｐ＞　则接受该解，否则舍弃。　模拟退火　５．９００３，一２．２３４４　２０．２８２　（４）判断是否满足终止条件，如果满足则输出当前解为　遗传算法　０．４２０７，０．０５７７　最优解，算法结束，否则继续执行。　４．８６４７，２．８４９６　（二）基于模拟退火的遗传聚类算法　为得到更好的聚类结果将模拟退火算法和遗传算法结合，　实验２选择ＵＣＩ数据集中的Ｉｒｉｓ、Ｗｉｎｅ、Ｖｅｈｉｃｌｅ三个数　来优化Ｋ－ｍｅａｎｓ算法得到聚类分析的全局最优解。基于模拟退　据集分别用三种算法对这三个数据集进行分析，来验证算法的　火的遗传聚类算法的流程为：　有效性和稳定性。　（１）初始化种群、计数器、交叉概率ｐｃ和变异概率ｐｍ。　用三种算法对ＵＣＩ数据集进行分析后得到的实验结果表　（２）计算种群适应度。　４＿４所示。　（３）个体交叉、变异操作。　表４－４　ＵＧＩ数据集实验结果　（４）个体模拟退火操作。　数据集　算法　Ｅ　Ｎ　ＩＴ　（５）重新计算个体适应度。　ＩｒｉＳ　Ｋ均值　７８．９４０８　１５　２．５　（６）个体选择复制，并判断是否满足终止条件，如果不　遗传算法　７８．９４０８　１６　３　满足则转到步骤３）。　模拟退火遗传算法　７８．９４０８　２０　２　计算机光盘软件与应用　工程技术　Ｗｉｎｅ　Ｋ均值　Ｃｏｍｐｕｔｅｒ　ＣＤ　Ｓｏｆｔｗａｒｅ　ａｎｄ　Ａｐｐｌ　ｉｃａｔ　ｉｏｎｓ　２．３７０７Ｅ＋００６　１３　３．３　２０１２年第５期　针对传统聚类算法中ｋ－ｍｅａｎｓ算法较易出现局部最优解、　对初始聚类中心、数据输入顺序敏感等问题，本文将遗传算法　和模拟退火算法相结合，通过算法的交叉、变异、适应度计算、　模拟退火遗传　３．５５５８Ｅ＋００６　２０　２　模拟退火等操作，克服了Ｋ均值算法的这些缺点，提高了算法　算法　的效率和聚类的效果以及稳定性，最后在实验上进行了验证，　表４—４中Ｅ代表最小误差平方和即最优解，Ｎ代表达到最　验证了算法的有效性和稳定性。　优解的次数，ＩＴ表示做２０次实验得到最优解时的平均迭代次　参考文献：　数。　【１］毛国君，段立娟．数据挖掘原理与算法（第二版）【Ｍ１．北京：　从实验１的实验结果可以看出三种算法在线性可分的数　清华大学出版社，２００７　据集上得到的聚类中心和最小误差平方和完全相同，证明了模　【２］Ｈａｎ　ｌ　Ｗ，Ｍｉｃｈｅｆｉｎｅ　Ｋａｍｂｅｒ擞据挖掘概念与技术ＩＭｌ＿范　拟退火遗传算法可行。从实验２得到的结果表４－４中可以看出　明，孟小峰．北京：机械工业出版社，２００６　模拟退火遗传算法得到的最优解次数要多于其他２中算法，且　【３葛继科，３】邱玉辉．遗传算法研究综述【Ｊｌ＿计算机应用研　达到最优解时的平均迭代次数明显较少。以Ｉｒｉｓ为例，三种　究，２００８，２５（１０）：９１１—２９１６　算法得到的最优解都是７８．９４０８，模拟退火遗传算法得到的最　［４】崔勇，吴建平，徐恪．基于模拟退火的服务质量路由算法　优解次数为２Ｏ次，而其他２中算法分别为１５和１６次，从平　【『１＿软件学报，２００３，１４（５）：７７—８８４　Ｖｅｈｉｃｌｅ　１０．６　８．３　遗传算法　２．３７０７Ｅ＋００６　１６　模拟退火遗传　２．３７０７Ｅ＋００６　２０　算法　Ｋ均值　３．５５５８Ｅ＋００６　１０　遗传算法　３．５５５８Ｅ＋００６　１３　６．１　１　均迭代次数来模拟退火遗传算法迭代次数为２而其他两种分　别为２．５和３。因此可以看出该算法有效，并且具有较高的稳　定性。　五、小结　（上接第８９页）　试运行制度进行初步制定；内部技术员工的技术不断熟练，外　部技术员工变为后续服务。在优化级中，软件与硬件稳定地运　行；全部员工主动参与；正常地试运行，还运用高级管理功能　模块；资金足够保证，完成了ＥＲＰ试运行制度；技术人员掌握　日常应用维护的技能，外部技术人员继续服务。　交付阶段为进行系统交付、试运行以及验收的一个阶段；　其成熟度模型如图１所示：　图３更新准备阶段成熟度模型　随后于各阶段中进行成熟度等级以及关键状态的合理设　置，评价各阶段的成熟度。对于成熟度评价，评价指标是重要　方面，基于上文ＥＲＰ成熟度模型分析，该成熟度模型基于ＥＲＰ　用户、环境、管理以及技术这些指标作出评价。对于ＥＲＰ用户　指标，其重点对用户对ＥＲＰ的理解和支持度、ＥＲＰ应用能力以　及用户信息素养进行考虑；针对环境指标，其对外部环境造成　的影响程度、资金的投入度以及信息化制度的完善程度进行重　图１交付阶段成熟度模型　点考虑：对于管理指标，其对应用ＥＲＰ深度、广度以及数据和　运行阶段为进行正式运行以及维护的一个阶段，其成熟度　业务流程的规范度进行考虑；对于技术指标，其对ＥＲＰ软硬件　模型如图２：　的安全性与适应程度，还有外部及内部技术力量的支持程度进　行考虑。处于各个阶段，每项指标的重要程度不同，尤其针对　二级指标，在一些阶段中，重要度可能是零。　四、总结　对于中小制造企业ＥＲＰ应用成熟度模型，通过对文献的研　究，根据访谈、调研得以建立，目前仅为…个定性模型，定量　指标缺少，更深的研究方向为给出某些定量指标实施更精确评　定，同时进一步细分行业模型作出研究。　参考文献：　【１］孙璐，董毅明，陶福平．医药企业信息化成熟度综合评价　应用研究兀１．科技管理研究，２００７，６：１９３—１９６　【２１苏选良．ＥＲＰ应用成熟度及其评价体系［１１．湘潭师范学　图２运行阶段成熟度模型　院学报：自然科学版，２００６，２８（１）：１１—１４　『３汪小梅．企业信息化成熟度模型研究【３］Ｉ１ｌ情报杂　更新准备阶段为经过一段时间运行，系统进行升级更新的　志，２００７，１０：１１—１４　个准备阶段，其成熟度模型如图３：　【４】王惠芬．我国企业ＥＲＰ实施的能力成熟度分析卟科学　管理研究，２００８，２１（３）：６０—６４　一