一种改进的求解聚类问题的差分进化算法  

Improved differential evolution algorithm for clustering

作　　者：王勇臻 陈燕[1] 张金松[1] Wang Yongzhen;Chen Yan;Zhang Jinsong(Transportation Management College, Dalian Maritime University, Dalian Liaoning 116026 , China)

机构地区：[1]大连海事大学交通运输管理学院,辽宁大连116026

出　　处：《计算机应用研究》2016年第9期2630-2633,共4页Application Research of Computers

基　　金：国家自然科学基金资助项目(71271034);辽宁省自然科学基金资助项目(2014025015);青年骨干教师基金资助项目(3132015048)

摘　　要：针对K-means算法依赖于初始聚类中心和易陷入局部最优解的缺陷,提出一种改进的求解聚类问题的差分进化算法。将改进的差分进化算法与K-means迭代相结合,使算法对初始聚类中心的敏感性和陷入局部最优解的可能性降低。通过将反向学习技术引入到框架中来指导搜索新的空间,以增强算法的全局寻优能力。为了改善算法的计算效率,根据聚类问题编码的特点设计了一种整理算子来消除冗余以及调整差分进化算法的种群更新策略。最后,在迭代过程中不断引入随机个体以提高种群的多样性。与K-means和几种进化聚类算法进行比较,实验结果表明,该算法不仅能有效抑制早熟收敛,而且具有较强的稳定性和较好的聚类效果。Since the K-means depended on the selection of initial clustering centers and was easy to be trapped by local optimal, this paper presented an improved differential evolution algorithm for clustering. The algorithm integrated an improved differentialevolution algorithm with the K-means iteration, which reduced its sensitivity on initial clustering centers and its probability to be stuck in the local optimal. For enhancing its global optimization ability, the algorithm used the opposition-based learning to direct searching. According to the characteristics of clustering problem, it designed a reordering operator to eliminate the redundancy of encoding and adjusted the population updating strategy so as to raise its computing efficiency. In order to improve the diversity level of the population, it introduced random individuals continuously in the iterative process. Compared with K-means and several evolutionary clustering algorithms, the result of experiments demonstrate that the proposed algorithm not only can effectively suppress the premature convergence, but also has a strong stability and produces good clustering results.

关 键 词：K-均值 差分进化 聚类分析 反向学习 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]