基于廣義反向?qū)W習(xí)的磷蝦群算法及其在數(shù)據(jù)聚類中的應(yīng)用

丁成 王秋萍 王曉峰

摘 要：針對磷蝦群（KH）算法在尋優(yōu)過程中因種群多樣性降低而過早收斂的問題，提出基于廣義反向?qū)W習(xí)的磷蝦群算法GOBL-KH。首先，通過余弦遞減策略確定步長因子平衡算法的探索與開發(fā)能力;然后，加入廣義反向?qū)W習(xí)策略對每個(gè)磷蝦進(jìn)行廣義反向搜索，增強(qiáng)磷蝦探索其周圍鄰域空間的能力。將改進(jìn)的算法在15個(gè)經(jīng)典測試函數(shù)上進(jìn)行測試并與KH算法、步長線性遞減的磷蝦群（KHLD）算法和余弦遞減步長的磷蝦群（KHCD）算法比較，實(shí)驗(yàn)結(jié)果表明：GOBL-KH算法可有效避免早熟且具有較高的求解精度。為體現(xiàn)算法有效性，將GOBL-KH算法與K均值算法結(jié)合提出HK-KH算法用于解決數(shù)據(jù)聚類問題，即在每次迭代后用最優(yōu)個(gè)體或經(jīng)過K均值迭代一次后的新個(gè)體替換最差個(gè)體，使用UCI五個(gè)真實(shí)數(shù)據(jù)集進(jìn)行測試并與K均值、遺傳算法（GA）、粒子群優(yōu)化（PSO）算法、蟻群算法（ACO）、KH算法、磷蝦群聚類算法（KHCA）、改進(jìn)磷蝦群（IKH）算法進(jìn)行比較，結(jié)果表明：HK-KH算法適用于解決數(shù)據(jù)聚類問題且具有較強(qiáng)的全局收斂性和較高的穩(wěn)定性。

關(guān)鍵詞：磷蝦群算法;余弦遞減策略;廣義反向?qū)W習(xí);數(shù)據(jù)聚類;K均值聚類算法

中圖分類號(hào)： TP183; TP301.6

文獻(xiàn)標(biāo)志碼：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]是從南極磷蝦群體的生存環(huán)境和生活習(xí)性的仿真模擬實(shí)驗(yàn)中受到啟發(fā)，由伊朗學(xué)者Gandomi等[1]于2012年首次提出的一種基于隨機(jī)搜索的群智能優(yōu)化算法。相比粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法[2]、蟻群優(yōu)化（Ant Colony Optimization，ACO）算法[3]和人工蜂群（Artificial Bee Colony，ABC）算法[4]等經(jīng)典仿生優(yōu)化算法，KH具有更快的收斂速度，尤其在解決多峰、高維的復(fù)雜問題時(shí)具有一定優(yōu)勢[5]，現(xiàn)已被成功應(yīng)用于機(jī)械[6]、光學(xué)[7]、電力系統(tǒng)[8]、生產(chǎn)調(diào)度[9]和聚類分析[10-11]等諸多領(lǐng)域。

與其他群智能算法相同，磷蝦群算法在優(yōu)化過程中也面臨著如何平衡全局勘探與局部開發(fā)的問題。 Wang等[12]提出一種混沌磷蝦群算法，采用Singer map混沌映射生成慣性權(quán)重，同時(shí)加入精英策略，用全局最優(yōu)的個(gè)體替換最差個(gè)體，提高了全局最優(yōu)的可靠性和解的質(zhì)量;Li等[13]提出步長線性遞減的磷蝦群（KH with Linear Decreasing step，KHLD）算法，驗(yàn)證了步長采用遞減策略的有效性，但因線性遞減的步長下降速率單一且過快的原因，易導(dǎo)致算法陷入局部最優(yōu);Wang等[14]提出了基于反向?qū)W習(xí)的磷蝦群算法，對KH中的一般個(gè)體進(jìn)行反向?qū)W習(xí)（Opposition-Based Learning，OBL），同時(shí)也體現(xiàn)出優(yōu)化過程中求其反向解的可行性，但反向?qū)W習(xí)在求其反向解時(shí)是基于中心對稱的且對稱中心較單一，只能從一定程度上增強(qiáng)種群的多樣性。本文提出基于廣義反向?qū)W習(xí)（Generalized Opposition-Based Learning，GOBL）的磷蝦群算法（GOBL-KH），對KH算法做了兩處改進(jìn)：1）采用余弦遞減策略控制步長大小，非線性遞減的步長能夠相對平衡迭代前后期算法的探索和開發(fā)能力;2）引入廣義反向?qū)W習(xí)策略，每次迭代后隨機(jī)生成對稱中心，能很大程度上提高種群的多樣性，增強(qiáng)磷蝦個(gè)體的全局搜索能力，也加快了收斂速度。15個(gè)測試函數(shù)的實(shí)驗(yàn)結(jié)果表明，改進(jìn)的KH算法能夠有效地平衡全局勘探與局部開發(fā)能力，求解精度和收斂速度都優(yōu)于傳統(tǒng)的KH算法及其相關(guān)改進(jìn)算法。

為驗(yàn)證改進(jìn)算法的有效性，本文提出基于GOBL-KH與K均值的混合聚類算法（Hybrid clustering algorithm based on K-means and GOBL-KH， HK-KH），將改進(jìn)的KH算法與K均值聚類算法結(jié)合用于解決數(shù)據(jù)聚類問題，充分利用改進(jìn)后KH算法的全局搜索性與K均值高效的局部尋優(yōu)能力，使得算法能夠快速準(zhǔn)確地找到最佳聚類中心，同時(shí)也解決了K均值算法過于依賴初始聚類中心而導(dǎo)致算法易陷入局部最優(yōu)的不足。將新的聚類算法在5個(gè)常用的UCI數(shù)據(jù)集上進(jìn)行測試，實(shí)驗(yàn)結(jié)果表明將改進(jìn)的KH算法用于K均值聚類算法中，求解精度和算法的穩(wěn)定性都得到了改善。

4 結(jié)語

為改善磷蝦群算法在快速收斂時(shí)易陷入局部最優(yōu)的不足，本文提出了一種基于廣義反向?qū)W習(xí)的磷蝦群算法。通過引入余弦遞減策略和廣義反向?qū)W習(xí)策略，既擴(kuò)大了磷蝦個(gè)體的搜索范圍，又在一定程度上平衡了算法的局部與全局的開發(fā)能力。15個(gè)測試函數(shù)的實(shí)驗(yàn)結(jié)果表明改進(jìn)算法能夠有效地提高算法的求解精度和收斂速度。將改進(jìn)后算法與K均值聚類算法融合用于求解數(shù)據(jù)聚類問題，五個(gè)UCI數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明融合后的算法具有較快的收斂速度和較好的穩(wěn)定性。今后進(jìn)一步的研究方向?yàn)椋?）將KH與其他優(yōu)化策略相結(jié)合，進(jìn)一步提高KH的性能;2）將該算法應(yīng)用于解決調(diào)度、路徑規(guī)劃、文本文檔聚類和約束優(yōu)化等實(shí)際工程問題。

參考文獻(xiàn)：

[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] 姜建國，田旻，王向前，等.采用擾動(dòng)加速因子的自適應(yīng)粒子群優(yōu)化算法[J].西安電子科技大學(xué)學(xué)報(bào)（自然科學(xué)版），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] 艾兵，董明剛.基于高斯擾動(dòng)和自然選擇的改進(jìn)粒子群優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用，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] 許世鵬，吳定會(huì)，孔飛，等.基于改進(jìn)雞群算法的柔性作業(yè)車間調(diào)度問題求解[J].系統(tǒng)仿真學(xué)報(bào)，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] 陳貴敏，賈建援，韓琪.粒子群優(yōu)化算法的慣性權(quán)值遞減策略研究[J].西安交通大學(xué)學(xué)報(bào)，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.