模拟退火算法聚类设计.pptx

《模拟退火算法聚类设计.pptx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、主讲：周润景教授单位：电子信息工程学院模拟退火算法聚类设计目录模拟退火算法的应用背景模拟退火算法介绍模拟退火算法的参数模拟退火算法的缺陷基于模拟退火思想的改进K均值算法算法实现总结一.模拟退火算法的应用背景模拟退火算法提出于1982年。Kirkpatrick等人首先意识到固体退火过程与优化问题之间存在着类似性；Metropolis等人对固体在恒定温度下达到热平衡过程的模拟也给他们以启迪。通过把Metropolis算法引入到优化过程中，最终得到一种对Metropolis算法进行迭代的优化算法，这种算法类似固体退火过程，称之为“模拟

2、退火算法”。模拟退火算法是一种适合求解大规模组合优化问题的随机搜索算法。目前，模拟退火算法在求解TSP，VLSI电路设计等组合优化问题上取得了令人满意的结果。将模拟退火算法同其它的计算智能方法相结合，应用到各类复杂系统的建模和优化问题中也得到了越来越多的重视，已经逐渐成为一种重要的发展方向。二.模拟退火算法介绍模拟退火算法的思想源于物理中固体物质退火过程与一般组合优化之间的相似性。1.物理退火过程物理中固体物质退火过程由三部分组成：（1）升温过程；（2）等温过程；（3）冷却过程二.模拟退火算法介绍2.Metropolis准则如果

3、用粒子的能量定义材料的状态，Metropolis算法用一个简单的数字模型描述了退火过程。假设材料在状态i的能量为，那么材料在温度T时从状态i进入到状态j就遵循如下规律：如果Ej≤Ei，接收该状态被转换；如果Ej>Ei，则状态转换以概率被接收（K为物理学中的常数；T为材料的温度）由可知，高温下可接受与当前状态能差较大的新状态为重要状态，而在低温下只能接受与当前状态能差较小的新状态为重要状态。这与不同温度下热运动的影响完全一致。二.模拟退火算法介绍3.模拟退火算法的基本原理组合优化模拟退火解粒子状态最优解能量最低态目标函数能量设定温

4、度熔解过程Metropolis抽样过程等温过程控制参数的下降冷却过程组合优化与物理退火的相似性二.模拟退火算法介绍用固体退火模拟组合优化问题，将内能E模拟为目标函数值J，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解。4.模拟退火算法新解的产生和接受可分为四个步骤第一步是由一个产生函数从当前解产生一个位于解空间的新解第二步是计算与新解所对应的目标函数差第三步是判断新解是否被

5、接受第四步是当新解被确定接受时，用新解代替当前解三.模拟退火算法的参数模拟退火是一种优化算法，它本身是不能独立存在的，需要有一个应用场合，其中温度就是模拟退火需要优化的参数，如果它应用到了聚类分析中，那么就是说聚类分析中有某个或者某几个参数需要优化，而这个参数，或者参数集就是温度所代表的。它可以是某项指标，某项关联度，某个距离等等。三.模拟退火算法的参数1.模拟退火算法的参数控制问题温度T的初始值设置问题退火速度问题温度管理问题四.模拟退火算法的缺陷模拟退火算法已在理论上证明它是一种以概率1，收敛于全局最优解的全局优化算法。但它

6、明显地存在两个弱点：（1）如果降温过程足够慢，所得到解的性能会较好，但算法收敛速度太慢；（2）如果降温过程过快，很可能得不到全局最优解。为此，模拟退火算法的改进及其在各类复杂系统建模及优化问题中的应用仍有大量的内容值得研究。五.基于模拟退火思想的改进K均值算法模拟退火算法是一种启发式随机搜索算法，具有并行件和渐近收敛性，已在理论上证明它是一种以概率为1，收敛于全局最优解的全局优化算法，因此用模拟退火算法对K均值聚类算法进行优化，可以改进K均值聚类算法的局限性，提高算法性能。基于模拟退火思想的改进K均值聚类算法中，将内能E模拟为目

7、标函数值，将基本K均值聚类算法的聚类结果作为初始解，初始目标函数值作为初始温度T0，对当前解重复“产生新解→计算目标函数差→接受或舍弃新解”的迭代过程，并逐步降低T值，算法终止时当前解为近似最优解。这种算法开始时以较快的速度找到相对较优的区域，然后进行更精确的搜索，最终找到全局最优解。五.基于模拟退火思想的改进K均值算法几个重要参数的选择目标函数：选择当前聚类划分的总类间离散度作为目标函数（式中，为样本向量；为聚类划分；为第i个聚类的中心；为样本到对应聚类中心距离；聚类准则函数即为各类样本到对应聚类中心距离的总和）五.基于模拟退

8、火思想的改进K均值算法初始温度：为了使最初产生的新解被接受，在算法开始时就应达到准平衡。选取初始温度聚类结果作为初始解。扰动方法：模拟退火算法中的新解的产生是对当前解进行扰动得到的。本算法采用一种随机扰动方法，即随机改变一个聚类样品的当前所属类别，从而产生一种新