基于广义反向学习的磷虾群算法及其在数据聚类中的应用

丁成 王秋萍 王晓峰

摘 要：针对磷虾群（KH）算法在寻优过程中因种群多样性降低而过早收敛的问题，提出基于广义反向学习的磷虾群算法GOBL-KH。首先，通过余弦递减策略确定步长因子平衡算法的探索与开发能力;然后，加入广义反向学习策略对每个磷虾进行广义反向搜索，增强磷虾探索其周围邻域空间的能力。将改进的算法在15个经典测试函数上进行测试并与KH算法、步长线性递减的磷虾群（KHLD）算法和余弦递减步长的磷虾群（KHCD）算法比较，实验结果表明：GOBL-KH算法可有效避免早熟且具有较高的求解精度。为体现算法有效性，将GOBL-KH算法与K均值算法结合提出HK-KH算法用于解决数据聚类问题，即在每次迭代后用最优个体或经过K均值迭代一次后的新个体替换最差个体，使用UCI五个真实数据集进行测试并与K均值、遗传算法（GA）、粒子群优化（PSO）算法、蚁群算法（ACO）、KH算法、磷虾群聚类算法（KHCA）、改進磷虾群（IKH）算法进行比较，结果表明：HK-KH算法适用于解决数据聚类问题且具有较强的全局收敛性和较高的稳定性。

关键词：磷虾群算法;余弦递减策略;广义反向学习;数据聚类;K均值聚类算法

中图分类号： TP183; TP301.6

文献标志码：A

Abstract： In order to solve the problem of premature convergence caused by the decrease of population diversity in the optimization process of Krill Herd （KH） algorithm， an improved krill herd algorithm based on Generalized Opposition-Based Learning was proposed， namely GOBL-KH. Firstly， step size factors were determined by cosine decreasing strategy to balance the exploration and exploitation ability of the algorithm. Then， a generalized opposition-based learning strategy was added to search each krill， which enhanced the ability of the krill to explore the neighborhood space around it. The proposed algorithm was tested on fifteen benchmark functions and compared with the original KH algorithm， KH with Linear Decreasing step （KHLD） and KH with Cosiner Decreasing step （KHCD）. The experimental results show that the proposed algorithm can effectively avoid premature and has higher accuracy. In order to demonstrate the effectiveness of the proposed algorithm， it was combined with K-means algorithm to solve the data clustering problem， namely HK-KH. In this fusion algorithm， after each iteration， the worst individual was replaced by the optimal individual or a new individual after the K-means iteration. Five datasets of UCI were used to test HK-KH algorithm and the results were compared with the K-means， Genetic Algorithm （GA）， Particle Swarm Optimization （PSO）， Ant Colony Optimization （ACO）， KH， KH Clustering Algorithm （KHCA）， Improved KH （IKH） algorithm for clustering problems. The experimental results show that HK-KH algorithm is suitable to solve the data clustering problem and has strong global convergence and high stability.

Key words： Krill Herd （KH） algorithm; cosine decreasing strategy; generalized opposition-based learning; data clustering; K-means clustering algorithm

0 引言

磷虾群（Krill Herd，KH）算法[1]是从南极磷虾群体的生存环境和生活习性的仿真模拟实验中受到启发，由伊朗学者Gandomi等[1]于2012年首次提出的一种基于随机搜索的群智能优化算法。相比粒子群优化（Particle Swarm Optimization，PSO）算法[2]、蚁群优化（Ant Colony Optimization，ACO）算法[3]和人工蜂群（Artificial Bee Colony，ABC）算法[4]等经典仿生优化算法，KH具有更快的收敛速度，尤其在解决多峰、高维的复杂问题时具有一定优势[5]，现已被成功应用于机械[6]、光学[7]、电力系统[8]、生产调度[9]和聚类分析[10-11]等诸多领域。

与其他群智能算法相同，磷虾群算法在优化过程中也面临着如何平衡全局勘探与局部开发的问题。 Wang等[12]提出一种混沌磷虾群算法，采用Singer map混沌映射生成惯性权重，同时加入精英策略，用全局最优的个体替换最差个体，提高了全局最优的可靠性和解的质量;Li等[13]提出步长线性递减的磷虾群（KH with Linear Decreasing step，KHLD）算法，验证了步长采用递减策略的有效性，但因线性递减的步长下降速率单一且过快的原因，易导致算法陷入局部最优;Wang等[14]提出了基于反向学习的磷虾群算法，对KH中的一般个体进行反向学习（Opposition-Based Learning，OBL），同时也体现出优化过程中求其反向解的可行性，但反向学习在求其反向解时是基于中心对称的且对称中心较单一，只能从一定程度上增强种群的多样性。本文提出基于廣义反向学习（Generalized Opposition-Based Learning，GOBL）的磷虾群算法（GOBL-KH），对KH算法做了两处改进：1）采用余弦递减策略控制步长大小，非线性递减的步长能够相对平衡迭代前后期算法的探索和开发能力;2）引入广义反向学习策略，每次迭代后随机生成对称中心，能很大程度上提高种群的多样性，增强磷虾个体的全局搜索能力，也加快了收敛速度。15个测试函数的实验结果表明，改进的KH算法能够有效地平衡全局勘探与局部开发能力，求解精度和收敛速度都优于传统的KH算法及其相关改进算法。

为验证改进算法的有效性，本文提出基于GOBL-KH与K均值的混合聚类算法（Hybrid clustering algorithm based on K-means and GOBL-KH， HK-KH），将改进的KH算法与K均值聚类算法结合用于解决数据聚类问题，充分利用改进后KH算法的全局搜索性与K均值高效的局部寻优能力，使得算法能够快速准确地找到最佳聚类中心，同时也解决了K均值算法过于依赖初始聚类中心而导致算法易陷入局部最优的不足。将新的聚类算法在5个常用的UCI数据集上进行测试，实验结果表明将改进的KH算法用于K均值聚类算法中，求解精度和算法的稳定性都得到了改善。

4 结语

为改善磷虾群算法在快速收敛时易陷入局部最优的不足，本文提出了一种基于广义反向学习的磷虾群算法。通过引入余弦递减策略和广义反向学习策略，既扩大了磷虾个体的搜索范围，又在一定程度上平衡了算法的局部与全局的开发能力。15个测试函数的实验结果表明改进算法能够有效地提高算法的求解精度和收敛速度。将改进后算法与K均值聚类算法融合用于求解数据聚类问题，五个UCI数据集的实验结果表明融合后的算法具有较快的收敛速度和较好的稳定性。今后进一步的研究方向为：1）将KH与其他优化策略相结合，进一步提高KH的性能;2）将该算法应用于解决调度、路径规划、文本文档聚类和约束优化等实际工程问题。

参考文献：

[1] GANDOMI A H， ALAVI A H. Krill herd： a new bio-inspired optimization algorithm [J]. Communications in Nonlinear Science and Numerical Simulation， 2012， 17（12）： 4831-4845

[2] EBERHART R， KENNEDY J. A new optimizer using particle swarm theory [C]// Proceedings of the Sixth International Symposium on Micro Machine and Human Science. Piscataway： IEEE， 1995： 39-43.

[3] DORIGO M， MANIEZZO V， COLORNI A. Ant system： optimization by a colony of cooperating agents [J]. IEEE Transactions on Systems， Man and Cybernetics， Part B， 1996， 26（1）： 29-41.

[4] KARABOGA D， BASTURK B. A powerful and efficient algorithm for numerical function optimization： Artificial Bee Colony （ABC） algorithm [J]. Journal of Global Optimization， 2007， 39（3）： 459-471.

[5] BOLAJI A L， AL-BETAR M A， AWADALLAH M A， et al. A comprehensive review： Krill Herd algorithm （KH） and its applications [J]. Applied Soft Computing， 2016， 49： 437-446.

[6] RADOVAN R B， GORAN M， MARINA S B. Modified Krill Herd （MKH） algorithm and its application in dimensional synthesis of a four-bar linkage [J]. Mechanism and Machine Theory， 2016， 95（95）： 1-21.

[7] REN Y-T， QI H， HUANG X， et al. Application of improved krill herd algorithms to inverse radiation problems [J]. International Journal of Thermal Sciences， 2016， 103： 24-34.

[8] PRASAD S， KUMAR D M V. Optimal allocation of measurement devices for distribution state estimation using multiobjective hybrid PSO-krill herd algorithm [J]. IEEE Transactions on Instrumentation & Measurement， 2017， 66（8）： 2022-2035.

[9] MUKHERJEE A， MUKHERJEE V. Solution of optimal reactive power dispatch by chaotic krill herd algorithm [J]. IET Generation Transmission & Distribution， 2015， 9（15）： 2351-2362.

[10] NIKBAKHT H， MIRVAZIRI H. A new clustering approach based on K-means and krill herd algorithm [C]// Proceedings of the 2015 23rd Iranian Conference on Electrical Engineering. Piscataway， NJ： IEEE， 2015： 662-667.

[11] JENSI R， JIJI G W. An improved krill herd algorithm with global exploration capability for solving numerical function optimization problems and its application to data clustering [J]. Applied Soft Computing， 2016， 46： 230-245.

[12] WANG G-G， GUO L， GANDOMI A H， et al. Chaotic krill herd algorithm [J]. Information Sciences， 2014， 274： 17-34.

[13] LI J， TANG Y， HUA C， et al. An improved krill herd algorithm： krill herd with linear decreasing step [J]. Applied Mathematics & Computation， 2014， 234： 356-367.

[14] WANG G-G， DEB S， GANDOMI A H， et al. Opposition-based krill herd algorithm with Cauchy mutation and position clamping [J]. Neurocomputing， 2016， 177： 147-157.

[15] 姜建國，田旻，王向前，等.采用扰动加速因子的自适应粒子群优化算法[J].西安电子科技大学学报（自然科学版），2012，39（4）：74-80. （JIANG J G， TIAN M， WANG X Q， et al. Adaptiveparticle swarm optimization via disturbing acceleration coefficents[J]. Journal of Xidian University （Natural Science）， 2012， 39（4）： 74-80.）

[16] 艾兵，董明刚.基于高斯扰动和自然选择的改进粒子群优化算法[J].计算机应用，2016，36（3）：687-691. （AI Bing，DONG Minggang. Improved particle swarm optimization algorithm based on Gaussian disturbance and natural selection [J]. Journal of Computer Applications， 2016， 36（3）： 687-691.）

[17] 许世鹏，吴定会，孔飞，等.基于改进鸡群算法的柔性作业车间调度问题求解[J].系统仿真学报，2017，29（7）：1497-1505. （XU S P， WU D H， KONG F， et al. Solving flexible job-shop scheduling problem by improved chicken swarm optimization algorithm [J]. Journal of System Simulation， 2017， 29（7）： 1497-1505.）

[18] 陈贵敏，贾建援，韩琪.粒子群优化算法的惯性权值递减策略研究[J].西安交通大学学报，2006，40（1）：53-56. （CHEN G M， JIA J Y， HAN Q. Study on the strategy of decreasing inertia weight in particle swarm optimization algorithm [J]. Journal of Xian Jiaotong University， 2006， 40（1）： 53-56.）

[19] RAHNAMAYAN S， TIZHOOSH H R， SALAMA M M A. Opposition-based differential evolution [J]. IEEE Transactions on Evolutionary Computation， 2008， 12（1）： 64-79.

[20] WANG H， WU Z， RAHNAMAYAN S. Enhanced opposition-based differential evolution for solving high-dimensional continuous optimization problems[J]. Soft Computing， 2011， 15（11）： 2127-2140.

[21] WANG H， WU Z， RAHNAMAYAN S， et al. Enhancing particle swarm optimization using generalized opposition-based learning [J]. Information Sciences， 2011， 181（20）： 4699-4714.

[22] YU S， ZHU S， MA Y， et al. Enhancing firefly algorithm using generalized opposition-based learning [J]. Computing， 2015， 97（7）： 741-754.

[23] MAULIK U， BANDYOPADHYAY S. Genetic algorithm-based clustering technique [J]. Pattern Recognition， 2004， 33（9）： 1455-1465.

[24] KAO Y-T， ZAHARA E， KAO I-W. A hybridized approach to data clustering [J]. Expert Systems with Applications， 2008， 34（3）： 1754-1762.

[25] SHELOKAR P S， JAYARAMAN V K， KULKARNI B D. An ant colony approach for clustering [J]. Analytica Chimica Acta， 2004， 509（2）： 187-195.