基于混合遗传模拟退火的模糊C-均值聚类算法

殷旅江，杨立君，胡明茂，邓义成

（1.湖北汽车工业学院经济管理学院，湖北十堰442002；2.湖北汽车工业学院机械工程学院，湖北十堰442002；3.上海海事大学经济管理学院，上海201306）

模糊聚类分析概念最早由Ruspini[1]提出，模糊聚类是基于模糊理论的聚类算法，可以将集中的数据根据其隶属度进行分类。模糊C-均值（Fuzzy C-means，FCM）是比较常用的聚类方法，目前已运用于图像分割[2]、脑电信号处理[3]、税务决策支持系统[4]等。由于FCM算法本质是用梯度下降的方法寻找最优解，因此存在局部收敛的问题。许多学者为了弥补FCM算法的不足，将一些进化算法引入模糊聚类中，从而形成了新的聚类方法：主要有基于粒子群算法[5]、基于改进遗传算法[6]和基于模拟退火算法[7]的方法等。

遗传算法（Genetic Algorithm，GA）由J.H.Holland于1975年提出[8]，目前应用于诸多领域[9-13]。遗传算法具有较好的全局搜索性能，将其引入到聚类分析中可有效克服局部收敛问题。同时，遗传算法也存在早熟缺陷，因此本文中又将模拟退火算法引入[14]，以避免早熟现象。通过将这2种算法结合用于聚类分析，可以使遗传算法与模拟退火算法互相取长补短，获得较好效果。

1 多类指派约束建模

1.1 模型变量定义

FCM的目标函数定义为

FCM算法是通过将目标函数最小化的迭代收敛来获得最优解。迭代过程中，U和A取值如下：

FCM算法迭代示意图如图1所示。

图1 FCM算法示意图

1.2 遗传算法

遗传算法是一种基于对自然界生物进化的认识而提出的算法，有非常广泛的应用，此处不做详细介绍，只给出其算法示意图，如图2所示。

1.3 模拟退火算法

模拟退火算法（Simulated Annealing Algorithm，SA）由Metropolis等人[15-16]于1953年提出，其基本思想是通过模拟高温物体退火过程来寻找最优解或者近似最优解。步骤如下：1）设置初始温度、终止温度、冷却系数等，并随机产生一个初始解；2）在当前解领域中选择一个最优解，并计算该解与上一个最优解的能量差，若小于0，则该解作为下一个当前解，否则重新选择；3）按照一定方式降温，重复步骤2）；4）检查终止条件，若满足，结束迭代，输出最优解，否则转到步骤2）。

图2 遗传算法示意图

2 基于遗传模拟退火的模糊聚类

2.1 遗传模拟退火算法

遗传模拟退火算法本质是将遗传算法和模拟退火算法结合起来，产生一种新的混合优化算法。遗传算法在把握搜索过程总体的能力比较强，但是局部搜索能力较差；模拟退火算法局部搜索能力较强，但对解的搜索空间了解较少，可能使得其运算效率低。本文中将这2种算法有效结合，可以充分发挥两者优点，获得较好的效果。

该算法与基本的遗传算法基本是类似的，即先随机产生初始解进行全局搜索，然后通过交叉变异产生新个体，再独立的对产生的个体进行模拟退火操作，将结果作为下代种群个体。重复迭代过程，直至达到终止条件。步骤如下：1）设置初始参数、最大迭代次数、遗传算法交叉率、模拟退火算法初始温度等；2）产生初始种群；3）计算初始种群个体适应度；4）进行个体的交叉变异操作，产生新种群；5）对新种群个体进行模拟退火操作，产生新个体；6）评价个体适应度；7）判断是否达到终止条件，是则输出最优解，否则转到步骤4）。

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

根据聚类问题的特征，采用操作较简单、容易实现交叉变异操作的二进制编码方式，并采用随机遍历抽样方式进行选择，以及使用单点变异方式进行变异操作。在变异成功后，再对新个体进行模拟退火操作，操作完毕，通过计算目标函数值，记录最佳值。最后，通过终止准则判断，结束迭代，输出结果。该聚类算法程序伪代码如下：

代码中，m 定义为样本特征维数，cn 定义为类别数，q 定义为冷却系数，T0 定义为初始温度，Tend定义为终止温度，MAXGEN 定义为最大遗传代数，sizepop种群个体数目，PRECI 定义为变量的二进制位数，NVAR 定义为变量的维数，pc 定义为交叉率，pm 定义为变异率。

3 仿真实验

为了验证本文中提出的聚类算法的有效性，从UCI 机器学习数据库中选择了Wine、Iris以及Car数据集做了仿真实验。这些数据集均来源于http∶//archive.ics.uci.edu/ml/网站，在本文中不一一列出。实验中的相关初始参数如表1所示。Car 数据集共1728个数据，将其分为4类，其聚类结果如表2所示。Iris 数据集共150个数据，将其分为3个类别，其聚类结果如表3所示。Wine 数据集共有178个数据，将其分为3类，其聚类结果如表4所示。各数据集和对应算法的聚类过程如图3所示。

由表2～4和图3可知，对于Car 数据集聚类来说，本文中提出的算法聚类效果比原始FCM算法好些，并且其聚类过程图有波动，即其在聚类过程中，目标函数值会出现反复，这就说明了该算法在对样本空间进行聚类时陷入局部极小的可能性较小。对于Iris和Wine 数据集来说，2种算法取得的效果基本相同，但是本文中提出的算法陷入局部最小的可能性小，其全局搜索性能更好。

表1 实验相关参数表

表2 Car数据集聚类结果表

表3 Iris数据集聚类结果表

表4 Wine数据集聚类结果表

图3 各数据集对应的算法聚类

4 结论

本文中提出的算法较原始FCM算法来说，其全局搜索性能更好，较不易陷入局部极小值，聚类效果更好。本文中的算法有效避免了原始FCM算法易于陷入局部极小值的缺陷，对于聚类问题，可以获得更好结果。

[1]Ruspini E H.A New Approach to Clustering[J].Information and Control，1969，19（15）：22-32.

[2]康家银，纪志成，龚成龙.一种核模糊C 均值聚类算法及其应用[J].仪器仪表学报，2010，31（7）：1657-1663.

[3]余炜，万代立，杨喜敬，等.改进的FCM算法及其在脑电信号处理中的应用[J].重庆大学学报，2014，37（7）：83-89.

[4]杨静，税务决策支持系统的FCM应用研究[J].四川理工学院学报：社会科学版，2009（S1）216-218.

[5]张利彪，周春光，马铭，等.基于粒子群优化算法的模糊C-均值聚类[J].吉林大学学报，2006，44（2）：217-222.

[6]董军浪，王庆飞.基于改进遗传算法的模糊C均值聚类算法[J].西安工程大学学报，2008，22（5）：605-609.

[7]刘晓龙，张佑生，谢颖.模拟退火与模糊C-均值聚类相结合的图像分割算法[J].工程图学学报，2007，27（1）：89-93.

[8]J H Holland.Adaptation in Natural and artificial systems[M].Ann Arbor∶University of Michigan Press,1975.

[9]周明，孙树栋.遗传算法原理与应用[M].长沙：国防工业出版社，1999.

[10]李金屏，何苗，杨波.遗传算法平均截止代数和成功率与种群规模之间的关系[J].系统仿真学报，2001，13（8）：206-210.

[11]殷旅江，杨立君，何波.基于主成分分析与支持向量机的汽柴油需求预测[J].工业工程，2015（2）：20-27+50.

[12]史奎凡，陈月辉.提高遗传算法收敛速度的方法[J].信息与控制，1998（8）：289-293.

[13]殷旅江，高亮，李登桥，胡明茂.改进元胞遗传算法的转塔式贴片机贴装优化[J].华中科技大学学报：自然科学版，2015（3）：113-117+132.

[14]韩啸，刘淑芬，徐天琦.基于遗传模拟退火算法的改进K-medoids算法[J].吉林大学学报：工学版，2015（2）：619-623.

[15]王华秋，曹长修.基于模拟退火的并行粒子群优化研究[J].控制与决策，2005，20（5）：500-504.

[16]Mitsunori M K,Tomoyuki H,Toshihiko F.Parallel simulated annealing with adaptive neighborhood determined by GA[A].Proceeding IEEE International Conference System and Cybernetics[C].Washington∶Institute of Electrical and Electronics Engineers Inc,2003∶26-31.