模式识别与智能计算——Matlab技术实现(含光盘1张)
9.5 模拟退火聚类算法
更新于2009-04-18 11:02:34

9.5.1 模拟退火的基本概念

模拟退火算法(Simulated annealing,SA)最初由Metropolis等人于20世纪80年代初提出,其思想源于物理中固体物质退火过程与一般组合优化问题之间的相似性。模拟退火方法是一种通用的优化算法,目前已广泛应用于最优控制、机器学习、神经网络等优化问题。

1.物理退火过程

模拟退火算法源于物理中固体物质退火过程,整个过程由以下三部分组成。

(1)升温过程

升温的目的是增强物体中粒子的热运动,使其偏离平衡位置变为无序状态。当温度足够高时,固体将溶解为液体,从而消除系统原先可能存在的非均匀态,使随后的冷却过程以某一平衡态为起点。升温过程与系统的熵增过程相关,系统能量随温度升高而增大。

(2)等温过程

在物理学中,对于与周围环境交换热量而温度不变的封闭系统,系统状态的自发变化总是朝向自由能减小的方向进行,当自由能达到最小时,系统达到平衡态。

(3)冷却过程

与升温过程相反,使物体中粒子的热运动减弱并渐趋有序,系统能量随温度降低而下降,得到低能量的晶体结构。

2.模拟退火算法的基本原理

模拟退火的基本思想是指将固体加温至充分高,再让其徐徐冷却,加温时,固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都达到平衡态,最后在常温时达到基态,内能减为最小。

根据Metropolis准则,粒子在温度T时趋于平衡的几率为e-ΔE/(kT)其中E为温度T时的内能,ΔE为其改变量,K为Boltzmann常数。用固体退火模拟组合优化问题,将内能E模拟为目标函数值f,温度T演化成控制参数t,即得到解组合优化问题的模拟退火算法:由初始解和控制参数初值开始,对当前解重复“产生新解→计算目标函数差→判断是否接受→接受或舍弃”的迭代,并逐步衰减t值,算法终止时的当前解即为所得近似最优解,这是蒙特卡罗迭代求解法的一种启发式随机搜索过程。

如果用粒子的能量定义材料的状态,Metropolis算法用一个简单的数字模型描述了退火过程。假设材料在状态i之下的能量为Ei),那么材料在温度T时从状态i进入到状态j就遵循如下规律:

如果Ej)≤Ei),接收该状态被转换;

如果Ej)>Ei),则状态转换以如下概率被接收:


p=eEi)-Ej))/(KT

公式9-7

式中,K为物理学中的常数;T为材料的温度。

(1)模拟退火算法的组成

模拟退火算法由解空间、目标函数和初始解三部分组成。

① 解空间:对所有可能解均为可行解的问题定义为可能解的集合,对存在不可行解的问题,或限定解空间为所有可行解的集合,或允许包含不可行解但在目标函数中用罚函数(Penalty Function)惩罚以致最终完全排除不可行解。

② 目标函数:对优化目标的量化描述,是解空间到某个数集的一个映射,通常表示为若干优化目标的一个和式,应正确体现问题的整体优化要求且较易计算,当解空间包含不可行解时还应包括罚函数项。

③ 初始解:是算法迭代的起点,试验表明,模拟退火算法是健壮的(Robust),即最终解的求得不十分依赖初始解的选取,从而可任意选取一个初始解。

(2)模拟退火算法的基本过程

① 初始化,给定初始温度T0及初始解ω,计算解对应的目标函数值f(ω),在本节中ω代表一种聚类划分。

② 模型扰动产生新解ω'及对应的目标函数值f(ω')。

③ 计算函数差值Δff(ω’)-f(ω’)。

④ 如果Δf≤0,则接受新解作为当前解。

⑤ 如果Δf>0,则以概率狆接受新解。


p=e-f(ω’)-f(ω))/f(KT)

公式9-8


⑥ 对当前T值降温,对②~⑤步骤迭代N次。

⑦ 如果满足终止条件,输出当前解为最优解,结束算法,否则降低温度,继续迭代。

模拟退火算法的算法流程,如图9-14所示。算法中包含1个内循环和1个外循环内循环就是在同一温度下的多次扰动产生不同模型状态,并按照Metropolis准则接受新模型,因此是用模型扰动次数控制的;外循环包括了温度下降的模拟退火算法的迭代次数的递增和算法停止的条件,因此基本是用迭代次数控制的。


图9-14 模拟退火算法流程图

3.退火方式

模拟退火算法中,退火方式对算法有很大的影响。如果温度下降过慢,算法的收敛速度会大大降低。如果温度下降过快,可能会丢失极值点。为了提高模拟退火算法的性能,许多学者提出了退火方式,比较有代表性的几种退火方式如下:

  公式9-9

t代表图9-14中的最外层当前循环次数,其特点是温度下降缓慢,算法收敛速度也较慢。

  公式9-10

a为可调参数,可以改善退火曲线的形态。其特点是高温区温度下降较快,低温区是温度下降较慢,即主要在低温区进行寻优。

  公式9-11

a为可调参数。其特点是温度下降较快,算法收敛速度快。

9.5.2 基于模拟退火思想的改进K均值聚类算法

1.K均值算法的局限性

基本的K均值算法目的是找到使目标函数值最小的K个划分,算法思想简单,易实现,而且收敛速度较快。如果各个簇之间区别明显,且数据分布稠密,则该算法比较有效,但如果各个簇的形状和大小差别不大,则可能会出现较大的簇分割现象。此外,在K均值算法聚类时,最佳聚类结果通常对应于目标函数的极值点,由于目标函数可能存在很多的局部极小值点,这就会导致算法在局部极小值点收敛。因此初始聚类中心的随机选取可能会使解陷入局部最优解,难以获得全局最优解。

该算法主要的局限性主要表现为:

① 最终的聚类结果依赖于最初的划分。
② 需要事先指定聚类的数目M
③ 产生的类大小相关较大,对于“噪声”和孤立点敏感。
④ 算法经常陷入局部最优。
⑤ 不适合对非凸面形状的簇或差别很小的簇进行聚类。

2.基于模拟退火思想的改进K均值聚类算法

模拟退火算法是一种启发式随机搜索算法,具有并行性和渐近收敛性,已在理论上证明它是一种以概率为l,收敛于全局最优解的全局优化算法,因此用模拟退火算法对K均值聚类算法进行优化,可以改进K均值聚类算法的局限性,提高算法性能。

基于模拟退火思想的改进K均值聚类算法中,将内能E模拟为目标函数值,将基本K均值聚类算法的聚类结果作为初始解,初始目标函数值作为初始温度T0,对当前解重复“产生新解→计算目标函数差→接受或舍弃新解”的迭代过程,并逐步降低T值,算法终止时当前解为近似最优解。这种算法开始时以较快的速度找到相对较优的区域,然后进行更精确的搜索,最终找到全局最优解。

3.几个重要参数的选择

(1)目标函数

选择当前聚类划分的总类间离散度作为目标函数,如式9-12所示。



公式9-12

式中,X为样本向量;ω为聚类划分;为第i个聚类的中心;为样品到对应聚类中心距离;聚类准则函数Jω即为各类样本到对应聚类中心距离的总和。

(2)初始温度

一般情况下,为了使最初产生的新解被接受,在算法开始时就应达到准平衡。因此选取基本K均值聚类算法的聚类结果作为初始解,初始温度T0Jω

(3)扰动方法

模拟退火算法中的新解的产生是对当前解进行扰动得到的。本算法采用一种随机扰动方法,即随机改变一个聚类样品的当前所属类别,从而产生一种新的聚类划分,从而使算法有可能跳出局部极小值。

(4)退火方式

本算法采用公式9-11描述的退火方式,其中a为退火速度,控制温度下降的快慢,取a=0.99。

4.算法流程

基于模拟退火思想的改进K均值聚类算法流程如图9-15所示。

5.实现步骤

① 对样品进行K均值聚类,将聚类划分结果作为初始解ω,根据公式9-12计算目标函数值Jω
② 初始化温度T0,令T0Jω。初始化退火速度a和最大退火次数。
③ 对于某一温度t,在步骤④~⑦进行迭代,直到达到最大迭代次数跳到步骤⑧。
④ 随机扰动产生新的聚类划分ω',即随机改变一个聚类样品的当前所属类别,计算新的目标函数值Jω'
⑤ 判断新的目标函数值Jω'是否为最优目标函数值,是则保存聚类划分ω'为最优聚类划分、Jω'为最优目标函数值;否则跳到下一步。
⑥ 计算新的目标函数值与当前目标函数值的差ΔJ
⑦ 判断ΔJ是否小于0:
ΔJ<0,则接受新解,即将新解作为当前解。
ΔJ≥0,则根据Metropolis准则,以概率ppeΔJ/Kt)接受新解。K为常数,t为当前温度。
⑧ 判断是否达到最大退火次数,是则结束算法,输出最优聚类划分;否则根据退火公式9-12对温度t进行退火,返回步骤③继续迭代。


图9-15 基于模拟退火思想的改进K均值聚类算法流程图

6.编程代码
 







 

7.效果图

基于模拟退火思想的改进K均值聚类算法采用了Metropolis准则,故成为全局寻优算法。Metropolis准则及算法的优点是:中间解以一定的接受概率跳出局部极小,避免落入局部极小点的可能,然后在退火温度的控制下最终找到最优解。

如图9-16(a)所示,对待聚类样品进行聚类时,选择不同的距离类型,在输入对话框中输入类中心数,k均值算法最大迭代次数,退火次数和降温速度,如图9-16(b)所示,最终输出聚类划分结果。如图9-16(c)所示,最优解出现时的退火次数,如图9-16(d)所示。如图9-16(e)所示为整个退火过程中输出的最优目标函数值,可以看出K均值聚类的最终结果并不是全局最优,经过逐次退火,最终在第16次退火时找到全局最优解。



图9-16 基于模拟退火思想的改进犓均值聚类算法效果图

本章小结

本章介绍了两种基于试探的未知类别聚类算法,包括最临近规则的试探法和最大最小距离算法,还介绍了五种层次聚类算法,包括最短距离法、最长距离法、中间距离法、重心法、类平均距离法;介绍了两种动态聚类算法,K均值算法和迭代自组织的数据分析算法(ISODATA),最后介绍了模拟退火算法以及基于模拟退火思想的改进K均值算法。


习题9

1.样品间的距离度量方式有哪些?
2.简述基于试探的未知类别聚类算法。
3.什么是层次聚类算法?它与基于试探的未知类别聚类算法有何异同?
4.简述K均值算法的基本思想。
5.叙述ISODATA的计算步骤。
6.简述模拟退火算法的基本原理。




 

网友留言