微分进化算法的优化研究及其在聚类分析中的应用

摘 要： 为了使微分进化算法在进化过程中充分挖掘和利用历史数据信息，提高它的全局搜索能力和收敛速度，提出了一种基于主成分的微分进化算法PCADE。该算法将种群空间映射到主成分空间从而得到一个由主成分构成的种群空间，在进化过程中前个主成分构成的个体可以直接进入下一代的进化，而剩余的个个体则从原种群和主成分种群空间中选择出适应度值较高的个体进入下一代。实验结果表明改进算法在聚类分析中取得了较好的结果。

关键词： 微分进化算法； 粒子群算法； 主成分分析； 聚类分析； K?均值聚类算法

中图分类号： TN710?34； TM417 文献标识码： A 文章编号： 1004?373X（2016）13?0103?05

Abstract： In order to make the differential evolution algorithm fully mine and use the historical data information in evolution process， and improve the global searching ability and convergence rate， a differential evolution algorithm based on principal component PCADE is proposed in this paper. The population space is mapped to the principal component space in this algorithm to obtain a population space composed of principal component. In evolution process， the first individuals composing of the principal component can access to the next generation evolution directly， and the individual with high fitness value in the residual N?m individuals is selected from the original population and principal component population space to access to the next generation. The experimental results show that the improved algorithm can obtain better result in cluster analysis.

Keywords： differential evolution algorithm； particle swarm optimization algorithm； principal component analysis； cluster analysis； K?means clustering algorithm

0 引 言

微分进化算法作为一种新兴的演化计算方法，它不依赖具体问题的领域，有很强的鲁棒性，是求解复杂系统优化问题的有效方法，因此在很多领域都得到了广泛的应用。微分进化算法虽然计算简单，但是易限入局部最优，存在早熟收敛现象。目前主要通过三个方面解决：一是调整控制参数改进算法；二是通过对搜索空间的改进提高算法性能；三是和其他算法结合产生新的混合算法。

本文主要对微分进化算法的收敛性及收敛速度进行深入分析，提出一种改进策略，提高算法的全局搜索能力和收敛速度，防止算法出现早熟的现象。并将改进的微分进化算法应用于聚类分析问题中，用于改善K?均值算法对初始聚类中心的敏感性。针对K?均值算法对噪声数据、孤立点、初始聚类中心的敏感性，利用基于PCADE算法对K?均值聚类算法进行改进，并利用典型的测试数据集IRIS进行验证，实验结果表明该改进算法在聚类结果的精度方面有所提高。

1 基于主成分的微分进化算法PCADE

1.1 算法介绍

在群体的进化过程中如果子代能够遗传到父代较多的优良信息，那么就越容易收敛到最优解，子代个体的产生只是从种群中随机挑选父代个体进行差分而得到的，而且并没有遗传到除了父代之外其他个体的任何信息。为了充分利用历史数据信息，将主成分分析的方法引入到微分进化算法中。

主成分分析方法可以将数据中彼此相关的变量经过线性变换转化为不相关的变量而且又能够反应原始数据的大部分特征。那么在微分进化算法的迭代过程中，利用主成分分析方法，将种群pop经过线性变换映射到主成分构成的种群空间pca_pop中。在主成分构成的种群pca_pop中各个体之间互不相关，而且前m个主成分就能代表原始数据中80%以上的信息量。那么种群的更新将在这两个空间中进行。

种群采取的进化策略如下：

假设迭代到第k代，种群pop（k）完成微分进化算法的交叉、变异，选择时不立即进行下一代的进化，而是首先将该种群pop（k）映射到其主成分空间得到主成分种群pca_pop（k），然后将前个主成分作为下一代种群的前m个个体，即pca_pop（k）中前m个个体为pop（k+1）中前m个个体，种群pop（k+1）中剩余的N-m个个体从pca_pop（k），pop（k）中选出适应度值高的个体进入pop（k+1），直到种群个体数达到N。这样就得到了下一代的种群pop（k+1），然后继续进行下一步的迭代过程。

由于主成分构成的个体之间具有很小的相关性，当进化若干代之后，个体之间进行信息交流，提高种群多样性，避免种群趋于一致性，极大地搜索出新的解空间，利于找到全局最优解。

1.2 算法流程

Step5：计算种群pop的协方差矩阵，求解协方差矩阵的特征值和特征向量然后求主成分，得到一个由主成分构成的新的种群pca_pop；

Step6：种群pca_pop中主成分累积贡献度达到90%的前个个体直接进入下一代，剩余个个体从种群pca_pop，pop中选出适应度值较高的个体进入下一代，直到种群规模达到

Step7：判断是否满足迭代条件，若不满足则返回Step2。

算法流程图如图1所示。

2 微分进化算法在聚类分析中的应用

2.1 基于DE的K?均值聚类算法

K?均值算法对初始点的选取和样本中的孤立点是敏感的，而且易陷入局部极小值，导致算法的聚类结果稳定性较差。如果能采用一种快速有效的优化算法对聚类中心进行优化，找到质量较高的聚类中心，势必会大大提高聚类的质量。目前针对这些问题处理的方法有很多，很多学者用模拟退火，遗传算法，粒子群算法，蚁群算法等对K?均值算法进行改进，都取得了不错的效果，和其他优化算法相比，微分进化算法具有结构简单，参数少，易于实现的优良性能，因此将微分进化算法引入到K?均值算法中，将二者有机结合，弥补K?均值算法对孤立点的敏感性，发挥二者的优势，形成性能较优的混合算法。

聚类问题的核心是求解各个聚类中心，因此利用DE算法进行聚类选取的时候，一个重要的问题是对聚类中心编码。设在空间中，给定数据集该数据集共有个样本，每个样本点包含个属性，即要将样本数据分成类，在基于DE的聚类分析中，每个个体代表个聚类的中心，因此个体实际上就是维的向量。这样每个个体采用如下的编码结构：

2.2 基于PCADE的K?均值聚类算法

上述将微分进化算法引入到K?均值算法中，将二者有机结合，弥补K?均值算法对孤立点的敏感性，发挥二者的优势，形成性能较优的混合算法。但是微分进化算法本身容易陷入局部最优，尤其是算法进化后期收敛速度有所下降，因此将改进的微分进化算法PCADE与K?均值算法相结合，产生一种新的混合算法。

3 实验结果及分析

为了验证上述基于主成分分析方法的微分进化算法PCADE能否得到好的效果，利用测试函数对该改进算法进行数值实验，并与原始微分进化算法（DE），粒子群算法（PSO）进行比较。首先DE算法中CR=0.5，最大迭代次数设置为1 000代；PSO算法惯性系数从0.9线性减少到0.1，最大迭代次数设置为1 000代；改进的微分进化算法PCADE中CR=0.5，主成分累积贡献度为90%，最大迭代次数设置为1 000代。以上三种算法种群个数维数连续运行10次。

为了对算法性能进行评估，采用如下的评估办法对测试函数1～4进行评价：

（1） 适应度值平均值：由于多次独立运行结果存在数值上的差异，平均值表明其运行结果的平均性能；

（2） 最佳适应度值，最差适应度值：考虑在运行过程中的随机性，增加10 次运行结果的最佳适应度和最差适应度值；

（3） 收敛曲线图：从收敛曲线图中可以直观看出算法的收敛速度和收敛的精度。

测试函数1：的取值范围为[-100，100]，最优解为0；

测试函数2：的取值范围为[-10，10]，最优解为0；

测试函数3：的取值范围为[-1.28，1.28]，最优解为0；

测试函数4：的取值范围为[-5.12，5.12]，最优解为0。

利用上述测试函数对三种算法进行数值实验，利用Matlab编程软件进行编程，得出结果如表1～表3所示。

聚类算法仿真实验的环境为：仿真软件Matlab 7.0，采用的测试数据集为IRIS数据集。IRIS数据集被作为机器学习中分类问题的基准测试数据集，IRIS数据集一共包含150个样本，3类花型（setosa，versicolor，vinginica）4个特征属性（萼片长，萼片宽，花瓣长，花瓣宽），每类花一共有50个样本。在进行聚类分析时，由于样本数据受量纲和数量级的影响，因此在聚类分析处理过程中，应对原始数据矩阵进行变换处理，就是从数据矩阵的每个变量中找出其最大值和最小值，这两者之差称为极差，然后将每个原始数据减去该变量的最小值，再除以极差就得到规格化数据，进行规格化变化之后数据的特点是将数据转化到[0，1]之间。将规格化后的数据集用来测试K?均值算法，基于微分进化的K?均值算法以及提出的基于PCADE的K?均值算法，从聚类结果分析聚类的效果。本文中算法参数设置如下：种群规模放缩因子交叉概率CR=0.5，累积贡献度=90%，最大迭代次数50，独立运行10次，实验以10次运行结果取平均来分析聚类的好坏，如表4和图8所示。

从表4结果可以看出在独立运行10次之后，PCADE?Kmeans算法的正确识别率要高于其他两种算法，最优运行结果的正确率可以达到94.67%。从图8也可以看出PCADE?Kmeans算法将IRIS数据进行了很好的聚类。因此改进的算法性能较好。

4 结 论

微分进化算法利用自然界优胜劣汰的思想和简单的差分操作使得其在一定程度上具有自组织、自适应、自学习的特征。但微分进化算法跟其他进化算法一样存在早熟收敛等问题，因此对微分进化算法进行改进，提高其全局搜索能力和收敛速度，使之能够适应各种复杂的工程问题，这是一个值得深入研究的领域。

本文通过研究国内外学者对微分进化算法的改进方法，提出了一种基于主成分的微分进化算法，该算法将种群空间映射到由主成分构成的种群空间，主成分空间中前个主成分构成的个体可以直接进入下一代的进化，而其余的个体则从主成分空间和原始种群空间中挑选出适应度值高的进入下一代，这样的改进方法使得种群能够更多地获得父代的信息，增加了种群的多样性。通过数值实验证明该算法在收敛精度和收敛速度上都有很大的提高。该算法对聚类中心进行编码构成进化种群，利用PCADE算法更新种群，最终得到较好的聚类中心，然后根据聚类中心对样本进行聚类，利用IRIS数据集进行试验，结果表明基于PCADE的K?均值聚类算法在聚类问题中得到了较好的结果。

从上述两个方面来看，该改进的微分进化算法PCADE在性能方面有了很大的提升，值得进一步推广。

参考文献

[1] 李士勇，陈永强，李研.蚁群算法及其应用[M].哈尔滨：哈尔滨工业大学出版社，2004.

[2] 胡中波，熊盛武，胡付高.改进的差分演化算法及其在函数优化中的应用[J].武汉理工大学学报，2007，29（4）：125?128.

[3] 苏海军，杨煜普，王宇嘉.微分进化算法的研究综述[J].系统工程与电子技术，2008，30（9）：1793?1797.

[4] 欧陈委.K?均值聚类算法的研究与改进[D].长沙：长沙理工大学，2011.

[5] 孟凡军，李天伟，徐冠雷，等.基于K?均值聚类算法的雾天识别方法研究[J].现代电子技术，2015，38（22）：56?58.

[6] VOSS M S. Principal component particle swarm optimization [C]// Proceedings of 2005 IEEE Swarm Intelligence Symposium. [S.l.]： IEEE， 2005： 401?404.

[7] EBERHART R， SHI Y. Comparing inertia weights and constriction factors in particle swarm optimization [C]// Proceedings of 2000 IEEE Congress on Evolutional Computation. La Jolla： IEEE， 2000： 84?88.

[8] TASGETIREN M F， SUGANTHAN P N. A multi?populated differential evolution algorithm for solving constrained optimization problem [C]// Proceedings of 2006 IEEE Congress on Evolutionary Computation. Vancouver： IEEE， 2006： 33?40.