丁成 王秋萍 王曉峰

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

關鍵詞：磷蝦群算法;余弦遞減策略;廣義反向?qū)W習;數(shù)據(jù)聚類;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]是從南極磷蝦群體的生存環(huán)境和生活習性的仿真模擬實驗中受到啟發(fā)，由伊朗學者Gandomi等[1]于2012年首次提出的一種基于隨機搜索的群智能優(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具有更快的收斂速度，尤其在解決多峰、高維的復雜問題時具有一定優(yōu)勢[5]，現(xiàn)已被成功應用于機械[6]、光學[7]、電力系統(tǒng)[8]、生產(chǎn)調(diào)度[9]和聚類分析[10-11]等諸多領域。

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

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

4 結語

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

參考文獻：

[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] 姜建國，田旻，王向前，等.采用擾動加速因子的自適應粒子群優(yōu)化算法[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] 艾兵，董明剛.基于高斯擾動和自然選擇的改進粒子群優(yōu)化算法[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] 許世鵬，吳定會，孔飛，等.基于改進雞群算法的柔性作業(yè)車間調(diào)度問題求解[J].系統(tǒng)仿真學報，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)化算法的慣性權值遞減策略研究[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.