赵新超，陈 敏



基于聚类分析的差分算法协作研究

赵新超，陈 敏

（北京邮电大学 理学院，北京 100876）

针对差分进化算法存在的收敛速度慢、易陷入局部最优等不足，本文提出一种融入聚类分析的差分进化算法。首先，利用聚类分析方法将差分算法的种群进行聚类分类，抽取代表元个体，利用新的个体来替换原种群中的较差个体，去除种群中的冗余信息将种群进行优化更新，从而使得整个种群可以快速准确地收敛于全局最优解。最后本文利用MATLAB编程模拟仿真，基于CEC2005测试函数库进行了模拟实验，结果表明加入了聚类分析替换策略的差分进化算法不仅有效地抑制了早熟收敛、提高了收敛速度，还有着简洁高效、鲁棒性强等特性。

差分算法；聚类分析；层次聚类；群智能优化

0 引言

与传统的优化算法相比，群智能（Swarm Intelligence）[1]的演化计算方法在近年来得到了学界极大的关注并获得了广泛的应用，它与人工智能，特别是遗传算法[2]和进化策略之间有着极为紧密而特殊的联系。这种方法模拟了自然环境中各种物种的繁衍、进化、生存等行为或过程，并将这些行为或过程抽象成为一种算法。差分进化算法（DE）[3]作为群智能算法的一种，因为它的简单实现和高效性，已经成功应用于各种科学和工程等领域。然而，差分进化算法本身存在着收敛速度慢、产生局部最优解等缺陷。此外，差分进化算法中的控制参数，如交叉因子、缩放因子和种群大小的选择对于算法的最终优化性具有较大的影响。近年来，国内外的相关学者提出了很多改进措施，比如控制参数的改进[4]，变异方向的改进[5]以及混合的差分进化算法[6]等，其中，混合的进化算法成为了最近研究的热点。

Das[7]等人基于统计学习提出一种混合差分进化粒子群(DEPSO)算法，该算法在迭代过程中根据两种策略在先前学习代数中的相对成功率来选择算法的下一步进化策略；Wang[8]等人对经典DE算法中的选择策略进行改进，融合模拟退火的思想以一定的概率接受较差解；张[9]等人在基本DE算法的选择过程中融入引力搜索策略来改善实验个体的质量；适应性调整算法参数和缩放因子的差分进化算法（jDE）[10]。上述改进虽然在一定程度上改善了算法性能，但是早熟收敛问题依然存在,而且一些改进措施还增加了算法的函数评价次数及时间复杂度。聚类分析[11-16]方法将数据集分为不同性质的类别，并可以利用这些聚类分析策略来去除冗余信息，比如降低维数等，也可以利用代表元这个富含信息量的元素进行特定的算法运算。

为进一步提高算法的收敛精度和收敛速度,本文提出了一种新的融合聚类分析算法的差分进化算法，在差分进化算法运行过程中，利用几种不同的聚类分析方法将整个种群的信息进行分类和抽取，并利用提取的信息优化先前的部分个体，使得原种群拥有更加丰富和代表性的信息和搜索能力，从而使整个算法的综合性能得到提高，也能减少算法落入局部最优、进入全局最优的可能性。实验证明加入了不同聚类分析方法的差分进化算法有着简洁高效、鲁棒性强等特性，不仅对通常的单峰和多峰优化问题表现出很强的寻优能力,而且对带最优解和函数值偏移量的优化问题也较其他算法表现要好。

1 标准差分进化算法

1.1 差分进化算法

其中i= 1, 2,…, NP，NP是种群规模大小，G是当前迭代次数。

rand(0,1)代表了服从均匀分布的[0, 1]区间中一个随机数。

初始化群体之后，差分进化算法开始进行一系列的循环进化操作，包括变异（Mutation）, 交叉（Crossover）和选择（Selection）。

1.1.1 变异

1.1.2 交叉

1.1.3 选择

差分进化算法的搜索性能取决于这个算法对全局探索和局部开发能力的平衡，而这些性质在很大程度上取决于对算法的控制参数的选择，包括种群规模的大小、缩放比例因子的大小和交叉率的大小。而相比于其他进化算法，差分进化算法所需要调节的参数较少。

2 融入聚类分析算法的差分进化算法

2.1 聚类分析算法

聚类分析仅根据在数据中发现的描述对象及其关系的信息，将数据对象分组。其目标是，组内的对象相互之间是相似的（相关的），而不同组中的对象是不同的（不相关的）。组内的的相似性（同质性）越大，组间差别越大，聚类就越好。

2.2 算法思想

聚类分析方法将差分进化算法的种群进行分布式信息的处理，即将种群划分为不同的类别，然后取出每个类别中最富含信息的代表元进行运算。并利用这些代表元重新构建更优秀的种群，使得整个种群逐渐优化并最终收敛于全局最优解。由于初始化阶段，解的分布信息比较分散，信息数量较为庞大，因此算法开始阶段就执行聚类方法，可能会产生很多问题，例如丰富的种群信息被过早削减，从而导致整个种群的提早成熟或提早收敛等,结果只会增加收敛到局部最优点的概率，而更危险的是聚类分析可能将具有最优解模式、但当前适应值交叉的解直接排除，导致不能得到问题的最终解。因此，聚类分析执行时机的选择非常重要，并且聚类分析也需要耗费一定的计算量。从实际经验来看也没有必要进行频繁的执行聚类分析，因为从一定角度看聚类分析本身就是一种加速技术，聚类分析不但能使聚类后的解群体更好地加快整体的收敛速度，而且能在一定程度上避免种群整体信息的缩减。

得到整个种群聚类分析的结果之后，第一，对于每一个类之中的聚类结果，可以在选出代表元之后利用经典的计算方法来对这个富含信息量的代表元进行快速收敛；第二，如何将新提取出来的代表元个体放回到种群之中。

在本文中，作者先将每一个聚类中心对应的适应值求出，并且根据聚类中心适应值进行排序，然后跟原始种群中最差解向量个体进行比较。如果聚类中心的适应值优于原始种群中的适应值，则使用聚类中心对应的解替代原始种群中较差的那些解，在这种情况下种群规模大小并不会发生改变。这种方法可以被认为是一种比较保守的竞争机制，在不降低整个种群规模的情况下，把最差的部分解进行了筛选淘汰，从而促进整个种群适应性能的提高，而整个种群的规模并不改变，其优点是鲁棒性好，减缓算法陷入局部最优。

2.3 算法思想

下面给出基于聚类分析的差分进化算法的基本步骤。

Step0. 群体和算法参数初始化；

Step1. 进行和经典差分进化算法相同的变异操作，交叉操作和选择操作；

Step2. 迭代一定次数之后，在某一次迭代选择操作结束之后，对整个种群使用一种特定的聚类分析算法，将整个种群聚集为K个类别；

Step3. 分别抽取这K个类别的代表元，计算这K个代表元的函数值，

If K个函数值<原来种群最差的K个个体函数值

利用代表元来替代原种群中的较差个体；

End If

Step4. If 迭代次数<最大迭代次数

回到Step 1；

Else 输出最优解和最优适应值。

3 仿真实验与结果分析

实验仿真环境为Win8.1，仿真软件为MATLAB 2016b，为验证本文提出的混合算法对复杂函数优化的收敛速度与收敛精度等性能，引入若干基准测试函数对算法进行测试，以全面考察算法对于不同类型优化问题的性能。文中基准测试函数实验参数设置：种群规模设置为100；最大函数评价次数(FES)设为100000；为减少实验误差，所有实验独立运行50次，取最优适应值的平均结果进行比较。文中对比算法DE/rand/1和本文提出的混合算法基本参数设置为F=0.5, CR=0.95。

3.1 不同聚类分析方法与差分进化算法的协作性分析

本文采用了三种经典的聚类分析方法，分别为：k-means算法，k-medoids算法和层次聚类算法[11]。首先对采用三种聚类分析的差分进化算法和经典差分算法进行了比较，对比结果如下：

从图1可以看出，基于k-means聚类分析方法的差分进化算法性能相对于另外两种算法来说较差，并且不很稳定；而基于k-medoids的聚类分析方法在与差分进化算法协作研究中表现出很好的效果，但是相比之下基于层次聚类分析方法的差分进化算法在这三个混合算法中表现是最优秀的，它不但能提高差分算法的收敛速度，而且也不会陷入局部最优。上述仿真实验和结果分析表明,无论是单模态还是多模态函数优化问题, 层次聚类分析方法的寻优能力通常都优于另外两种聚类算法，因此本文后续的混合算法都采用层次聚类分析方法与差分进化算法的融合。

图1 不同算法的运行效果对比图

3.2 算法综合对比实验

为了更好的分析差分-聚类算法的收敛速度、收敛速度和收敛精度等性能，本文将层次聚类分析方法（Clustering）融合标准差分进化（DE）算法形成混合进化算法DEClu。本文采用广泛采用的标准差分算法DE/rand/1和一种经典的改进DE变形（jDE）的两种差分进化算法作为比较对象，研究对比分析基于层次聚类的混合差分进化算法与两种经典的DE算法性能的比较。

从图2中的进化曲线可以看出在f1，f2，f6和f10函数中，加入了层次聚类的差分进化算法对比于先前的算法本身收敛速度和收敛精度都有所提高，其中基于层次聚类的进化算法对函数f8能非常有效地使标准DE快速收敛并取得全局最优解。结果表明，无论对于广为采用的基准差分算法， 还是经典的改进版本的差分进化，融入层次聚类 分析方法能使算法的收敛速度和收敛精度有所 提高。

图2 不同算法的运行效果对比图

4 结论

本文将层次聚类方法与不同版本的差分算法相结合提出了一种基于聚类的差分协同算法框架。利用择优的竞争方式使得种群在进化过程中能够不断向优秀的解所在方向逐步进化，从而生成更优秀的子种群和提高子代群体的平均适应性能，提高了算法群体在探索新的搜索方向与开发现有的潜力区域之间的平衡。除此之外，聚类分析方法被包装成模块化的部分，能够适用于所有变种的差分进化算法以及其他的进化算法，并且能够简单高效地提高相应差分进化算法的性能。通过对测试函数进行模拟实验，结果分析表明该算法框架具有较好地收敛速度与收敛精度，能有效的避免早熟收敛，跳出局部最优解，并且具有较好的鲁棒性。

[1] Beni G, Wang J., Swarm Intelligence in Cellular Robotic Systems[M]. Robots and Biological Systems: Towards a New Bionics. 1993: 703-712.

[2] Holland JH, Adaptation in natural and artificial systems[J]. Ann Arbor, 1975, 6(2): 126-137.

[3] Storn and K. Price, Differential evolution a simple and efficient heuristic for global optimization over continuous spaces[J]. Journal of Global Optimization, vol.11, no. 4, pp.341-359, 1997.

[4] Peñuñuri F, Cab C, Carvente O, et al. A Study of the Classical Differential Evolution Control Parameters[J]. Swarm & Evolutionary Computation, 2016, 26: 86-96.

[5] 吕铭晟, 沈洪远, 李志高,等. 多变异策略差分进化算法的研究与应用[J]. 计算机工程, 2014, 40(12): 146-150.

[6] Cui C Y, Jiao Y C, Zhang L. Synthesis of Some Low Sidelobe Linear Arrays Using Hybrid Differential Evolution Algorithm Integrated with Convex Programming[J]. IEEE Antennas & Wireless Propagation Letters, 2017, 16(99): 2444-2448.

[7] Das S, Abraham A, Konar A. Particle Swarm Optimization and Differential Evolution Algorithms: Technical Analysis, Applications and Hybridization Perspectives[J]. 2010, 116: 1-38.

[8] Wang P C, Qian X, Zhou Y, et al. A novel Differential Evolution algorithm based on simulated annealing[C]// Chinese Control and Decision Conference. 20-10: 7-10.

[9] 张英杰, 龚中汉. 基于阈值统计学习的差分进化引力搜索算法[J]. 计算机研究与发展, 2014, 51(10): 2187-2194.

[10] Brest J, Greiner S, Boskovic B, et al. Self-Adapting Control Parameters in Differential Evolution: A Comparative Study on Numerical Benchmark Problems[J]. IEEE Transactions on Evolutionary Computation, 2006, 10(6): 646-657. 2006.

[11] Pang-NingTan, MichaelSteinbach, VipinKumar. 数据挖掘导论: 完整版.第2版[M]. 人民邮电出版社, 2011.

[12] 左黎斌, 何傲, 王昕, 等. 基于FCM聚类算法的电能表标准装置监测数据分析与研究[J]. 软件, 2018, 39(6): 89-95.

[13] 何傲, 左黎斌, 王昕, 等. 基于K-means算法的电能表检定误差分析与研究[J]. 软件, 2018, 39(6): 64-73.

[14] 陈曦斌, 焦明海, 刘昊汧, 等. 移动机器人养老服务路径规划的粒子群算法研究[J]. 软件, 2018, 39(6): 135-138.

[15] 刘露萍, 贾文生. 基于方体剖分和量子免疫粒子群算法的Nash均衡求解[J]. 软件, 2018, 39(6): 01-03.

[16] 颜乐鸣. 基于工作流的软件测试过程模型研究[J]. 软件, 2018, 39(5): 160-165.

Cooperation Research on Differential Evolution Algorithm Based on Clustering Analysis

ZHAO Xin-chao, CHEN Min

(School of Science, Beijing University of Posts and Telecommunications, Beijing 100876)

Aiming at the shortcomings of differential evolution (DE) algorithm, such as slow convergence speed and easy to fall into local optimal solution, a differential evolution algorithm that incorporates cluster analysis is proposed in this paper. Cluster analysis is firstly used to classify populations, and typical new individuals are extracted. New individuals are used to replace poor individuals in the original population and redundant information in the population is removed. The population is optimized and updated so that the entire population can quickly and accurately converge to the global optimum. Finally, this paper does simulation experiments with CEC2005 test function using MATLAB simulation. The results show that differential evolution algorithm with cluster analysis replacing strategy not only effectively inhibits premature convergence, improves the convergence speed, but also has simple, efficient, and robust characteristics.

Differential algorithm; Cluster analysis; Hierarchical clustering; Swarm intelligence optimization

TP315

A

10.3969/j.issn.1003-6970.2018.10.018

赵新超(1976-)，男，教授，主要研究方向：群体智能、运筹优化及其相关应用；陈敏(1992-)，女，研究生，主要研究方向：遗传算法及其投资组合优化。

赵新超，陈敏. 基于聚类分析的差分算法协作研究[J]. 软件，2018，39（10）：87-91