Please wait a minute...
Journal of ZheJiang University (Engineering Science)  2022, Vol. 56 Issue (5): 977-986    DOI: 10.3785/j.issn.1008-973X.2022.05.015
    
Dragonfly algorithm based on clustering and detection elite guidance
Xiao-xin DU(),Hao WANG,Lian-he CUI,Jin-qi LUO,Yan LIU,Jian-fei ZHANG,Yi-ping WANG
School of Computer and Control Engineering, Qiqihar University, Heilongjiang 161006, China
Download: HTML     PDF(1152KB) HTML
Export: BibTeX | EndNote (RIS)      

Abstract  

Aiming at the shortcomings of the dragonfly algorithm (DA), i.e., slow convergence speed, low convergence accuracy, and poor global search ability, a new DA algorithm was proposed. Firstly, tent chaos was used to initialize the population and K-Means++ clustering was performed on the population. According to the results of clustering, reverse learning and Gaussian mutation were performed on the individuals of the population respectively to enhance the diversity of the population and improve the search efficiency. Secondly, the nonlinear adaptive factor was introduced to accelerate the convergence speed, and the probing elite guiding strategy was used to enhance the ability of jumping out of local convergence. Finally, square hash detection was introduced to increase the convergence accuracy. The optimization algorithm was applied to eight typical complex function optimization problems, and compared with the original dragonfly algorithm and other bionic algorithms. Experimental results show that the improved algorithm has good global convergence and optimization accuracy.



Key wordsdragonfly algorithm      clustering      detection elite guidance strategy      square hash detection      tent chaos     
Received: 12 June 2021      Published: 31 May 2022
CLC:  TP 301.6  
Fund:  2020年度黑龙江省省属高等学校基本科研业务费面上资助项目(135509112)
Cite this article:

Xiao-xin DU,Hao WANG,Lian-he CUI,Jin-qi LUO,Yan LIU,Jian-fei ZHANG,Yi-ping WANG. Dragonfly algorithm based on clustering and detection elite guidance. Journal of ZheJiang University (Engineering Science), 2022, 56(5): 977-986.

URL:

https://www.zjujournals.com/eng/10.3785/j.issn.1008-973X.2022.05.015     OR     https://www.zjujournals.com/eng/Y2022/V56/I5/977


基于聚类和探测精英引导的蜻蜓算法

针对蜻蜓算法(DA)收敛速度慢、收敛精度低、全局搜索能力差等不足,提出新的蜻蜓优化算法. 利用tent混沌初始化种群并对种群进行K-Means++聚类,根据聚类的结果分别对种群个体进行反向学习和高斯变异以增强种群的多样性,提高搜索效率. 引入非线性自适应因子加快收敛速度,使用探测精英引导策略增强算法跳出局部收敛的能力. 引入平方散列探测增加收敛精度. 将该优化算法应用于8个典型复杂函数优化问题,并与原蜻蜓算法,以及其他仿生计算算法对比,实验结果表明该改进算法具有良好的全局收敛性和寻优精度.


关键词: 蜻蜓算法,  聚类,  探测精英引导策略,  平方散列探测,  tent混沌 
Fig.1 Weight comparison curve of flight step
Fig.2 Illustration of probing elite guiding strategy
Fig.3 Illustration of square hash detection replacement
Fig.4 Flow chart of dragonfly algorithm based on clustering and detection elite guidance
函数名 表达式 维度 搜索区域
Sphere ${f_1}(x) = \displaystyle \sum\limits_{i = 1}^n {{x_i}^2} $ 10 [?100, 100]
Roscnbrock ${f_2}(x) = \displaystyle \sum\limits_{i = 1}^{n - 1} {(100{{({x_{i + 1}} - x_i^2)}^2})} $ 10 [?30, 30]
Step ${f_3}(x) = \displaystyle \sum\limits_{i = 1}^n { { {({x_i} + 0.5)}^2} }$ 10 [?100, 100]
Rastrigin ${f_4}(x) = \displaystyle \sum\limits_{i = 1}^n {[x_i^2 - 10\cos\; (2\pi {x_i}) + 10]}$ 10 [?5.12, 5.12]
Ackley $\begin{gathered} {f_5}(x) = - 20\exp\; \left( - 0.2\sqrt {\dfrac{1}{n}\displaystyle \sum\limits_{i = 1}^n {x_i^2} } \right) - \exp\; (\dfrac{1}{n}\displaystyle \sum\limits_{i = 1}^n {\cos \;(2\pi {x_i})} ) + 20 + {\rm{e}} \end{gathered}$ 10 [?32, 32]
Griewank ${f_6}(x) = \dfrac{1}{ {4\;000} }\displaystyle \sum\limits_{i = 1}^n {x_i^2 - \prod\limits_{i = 1}^n {\cos\; (\dfrac{ { {x_i} } }{ {\sqrt i } })} } + 1$ 10 [?600, 600]
Penalized1 $\begin{gathered} {f_7}(x) = \dfrac{\pi }{n}\left\{ {\left. {10\sin\; (\pi {y_1}) + \displaystyle \sum\limits_{i = 1}^{n - 1} { { {({y_i} - 1)}^2} } \left[ {1 + 10{ {\sin }^2}\;(\pi {y_{i + 1} })} \right] + { {({y_n} - 1)}^2} } \right\} } \right. + \displaystyle \sum\limits_{i = 1}^n {\mu ({x_i},10,100,4),\;{y_i} = 1 + \dfrac{ { {x_i} + 1} }{4} } \hfill \\ \end{gathered}$ 10 [?50, 50]
Penalized2 $\begin{gathered} {f_8}(x) = \displaystyle \sum\limits_{i = 1}^n {0.1\left\{ { { {\sin }^2}\;(3\pi {x_1}) + \displaystyle \sum\limits_{i = 1}^n { { {({x_i} - 1)}^2} } \left[ {1 + { {\sin }^2}(3\pi {x_i} + 1)} \right]} \right.} + \left. { { {({x_n} - 1)}^2}\left[ {1 + { {\sin }^2}\;(2\pi {x_n})} \right]} \right\} + \displaystyle \sum\limits_{i = 1}^n {\mu ({x_i},5,100,4)} \hfill \\ \end{gathered}$ 10 [?50, 50]
Tab.1 Eight typical complex functions
函数 算法 Xbest Xmean $\sigma $
f1 CEDA 2.36×10?93 5.43×10?90 1.05×10?89
DA 1.54×10?3 5.15×100 9.82×100
GWO 5.78×10?69 3.36×10?63 2.11×10?62
FOA 1.38×10?4 2.39×10?4 5.73×10?5
DE 2.40×10?20 4.52×10?19 4.93×10?19
ABC 4.61×10?10 4.61×10?10 1.25×10?07
PSO 1.28×10?5 4.82×10?4 1.10×10?3
f2 CEDA 1.39×10?6 2.37×10?2 1.21×10?1
DA 5.86×100 7.36×102 1.25×103
GWO 5.12×100 6.58×100 6.32×10?1
FOA 8.07×100 8.75×100 1.86×10?1
DE 6.74×100 7.81×100 3.61×100
ABC 4.70×100 7.25×100 1.47×100
PSO 1.80×10?2 6.83×101 1.15×102
f3 CEDA 0 0 0
DA 1.49×10?5 5.66×100 1.06×101
GWO 1.21×10?6 5.00×10?3 3.53×10?2
FOA 2.53×100 2.54×100 5.30×10?3
DE 2.32×10?20 4.19×10?19 4.75×10?19
ABC 3.46×10?10 4.13×10?8 9.69×10?8
PSO 3.87×10?5 5.50×10?4 5.58×10?4
Tab.2 Results of 2 000 independent runs of unimodal function
函数 算法 Xbest Xmean $\sigma $
f4 CEDA 0 0 0
DA 5.26×100 2.54×101 1.26×101
GWO 0 8.65×101 1.75×100
FOA 1.03×101 1.66×101 3.64×100
DE 1.40×10?10 4.13×10?6 1.46×10?6
ABC 1.20×101 2.62×101 4.46×100
PSO 5.07×100 2.35×101 1.23×101
f5 CEDA 8.88×10?16 2.55×10?15 1.98×10?15
DA 8.79×10?16 2.34×100 1.27×100
GWO 4.44×10?15 6.60×10?15 1.74×10?15
FOA 5.78×10?2 7.62×10?2 1.40×10?2
DE 9.33×10?11 2.66×10?10 1.16×10?10
ABC 6.51×10?5 8.02×10?5 6.47×10?4
PSO 1.27×10?2 1.05×100 8.33×10?1
f6 CEDA 0 0 0
DA 0 4.34×10?1 2.86×10?1
GWO 0 1.99×10?2 2.05×10?2
FOA 4.35×10?7 9.32×10?7 2.47×10?7
DE 1.74×10?11 3.60×10?3 8.10×10?3
ABC 2.02×10?1 3.72×10?1 7.03×10?2
PSO 1.49×10?2 1.24×10?1 6.18×10?2
f7 CEDA 4.71×10?32 4.71×10?32 4.95×10?47
DA 9.10×10?4 1.24×100 1.22×100
GWO 2.73×10?7 2.50×10?3 7.20×10?3
FOA 2.69×100 2.70×100 7.98×10?3
DE 8.36×10?22 3.06×10?20 4.18×10?20
ABC 2.49×10?9 8.45×10?7 2.03×10?6
PSO 5.62×10?5 6.94×10?2 2.09×10?1
f8 CEDA 1.34×10?32 1.34×10?32 1.34×10?48
DA 2.30×10?3 6.38×10?1 9.37×10?1
GWO 1.46×10?6 7.70×10?3 2.64×10?2
FOA 8.11×10?1 8.93×10?1 2.66×10?2
DE 7.95×10?21 1.11×10?19 1.33×10?19
ABC 4.10×10?8 6.83×10?6 1.08×10?5
PSO 1.33×10?4 7.70×10?3 9.10×10?3
Tab.3 Results of 2 000 independent runs of multimodal function
Fig.5 Comparison of convergence effect of CEDA algorithm and other classical algorithms
[1]   VISHAL S, GROVER A A modified ant colony optimization algorithm (MACO) for energy efficient wireless sensor networks[J]. Optik, 2016, 127 (4): 2169- 2172
doi: 10.1016/j.ijleo.2015.11.117
[2]   LI X T, WANG J N, YIN M H Enhancing the performance of cuckoo search algorithm using orthogonal learning method[J]. Neural Computing and Applications, 2014, 24 (6): 1233- 1247
doi: 10.1007/s00521-013-1354-6
[3]   YANG X S A new metaheuristic bat-inspired algorithm[J]. Nicso, 2010, 284: 65- 74
[4]   WANG G G, GANDOMI A, ALAVI A H, et al A comprehensive review of krill herd algorithm: variants, hybrids and applications[J]. Artificial Intelligence Review, 2019, 51 (1): 119- 148
doi: 10.1007/s10462-017-9559-1
[5]   SEYEDALI M The ant lion optimizer[J]. Advances in Engineering Software, 2015, 83 (5): 80- 98
[6]   SEYEDALI M Dragonfly algorithm: a new meta-heuristic optimization technique for solving single-objective, discrete, and multi-objective problems[J]. Neural Computing and Applications, 2016, 27 (4): 1053- 1073
doi: 10.1007/s00521-015-1920-1
[7]   PENG X X, JIA H M, LANG C B Modified dragonfly algorithm based multilevel thresholding method for color images segmentation[J]. Mathematical Biosciences and Engineering, 2019, 16 (6): 6467- 6511
doi: 10.3934/mbe.2019324
[8]   CUI X T, LI Y, FAN J H, et al A hybrid improved dragonfly algorithm for feature selection[J]. IEEE Access, 2020, 8: 155619- 155629
doi: 10.1109/ACCESS.2020.3012838
[9]   SANJOYD S, BAISHYA S, SEN D, et al A hybrid memory-based dragonfly algorithm with differential evolution for engineering application[J]. Engineering with Computers, 2020, 37 (4): 2775- 2802
[10]   赵齐辉, 杜兆宏, 刘升, 等 差分进化的蜻蜓算法[J]. 微电子学与计算机, 2018, 35 (7): 101- 105
ZHAO Qi-hui, DU Zhao-hong, LIU Sheng, et al Dragonfly algorithm based on differential evolution[J]. Microelectronics and Computer, 2018, 35 (7): 101- 105
[11]   林涛, 冯嘉冀, 赵伊 基于精英策略与正弦余弦机制的蜻蜓算法研究[J]. 微电子学与计算机, 2020, 37 (9): 24- 33
LIN Tao, FENG Jia-ji, ZHAO Yi Study on dragonfly algorithm based on elite strategy and cosines mechanism[J]. Microelectronics and Computer, 2020, 37 (9): 24- 33
[12]   张水平, 高栋 基于随机替换和混合变异的蜻蜓算法[J]. 科学技术与工程, 2020, 20 (22): 9108- 9115
ZHANG Shui-ping, GAO Dong Dragonfly algorithm based on random substitution and hybrid mutation[J]. Science Technology and Engineering, 2020, 20 (22): 9108- 9115
doi: 10.3969/j.issn.1671-1815.2020.22.038
[13]   ZHONG L, ZHOU Y, LUO Q, et al Wind driven dragonfly algorithm for global optimization[J]. Concurrency and Computation: Practice and Experience, 2021, 33 (6): 1- 31
[14]   TENG Z, LV J, GUO L An improved hybrid grey wolf optimization algorithm[J]. Soft Computing, 2019, 23 (15): 6617- 6631
doi: 10.1007/s00500-018-3310-y
[15]   AGGARWAL S, SINGH P Cuckoo, bat and krill herd based K-means++ clustering algorithms[J]. Cluster Computing, 2019, 22 (6): 14169- 14180
[16]   ANDERSON C, CHRISTINE M Practical genetic algorithms[J]. Publications of the American Statistical Association, 2004, 100 (471): 1099- 1099
[17]   龙文, 伍铁斌, 唐斌 收敛因子非线性变化的鲸鱼优化算法[J]. 兰州理工大学学报, 2017, 43 (6): 102- 107
LONG Wen, WU Tie-bin, TANG Bin Whale optimization algorithm with nonlinearly variable convergence factor[J]. Journal of Lanzhou University of Technology, 2017, 43 (6): 102- 107
doi: 10.3969/j.issn.1673-5196.2017.06.020
[18]   PHATAK S C, RAO S S Logistic map: a possible random-number generator[J]. Physical Review E, 1995, 51 (4): 3670- 3678
doi: 10.1103/PhysRevE.51.3670
[19]   滕志军, 吕金玲, 郭力文, 等 一种基于Tent映射的混合灰狼优化的改进算法[J]. 哈尔滨工业大学报, 2018, 50 (11): 40- 49
TENG Zhi-jun, LYU Jin-ling, GUO Li-wen, et al An improved hybrid grey wolf optimization algorithm based on tent mapping[J]. Journal of Harbin Institute of Technology, 2018, 50 (11): 40- 49
[20]   TSENG L Y, YANG S B A genetic clustering algorithm for data with non-spherical-shape clusters[J]. Pattern Recognition, 2000, 33 (7): 1251- 1259
doi: 10.1016/S0031-3203(99)00105-3
[21]   ZHOU Y, WANG R, LUO Q Elite opposition-based flower pollination algorithm[J]. Neurocomputing, 2016, 188 (5): 294- 310
[22]   KAUR G, ARORA S Chaotic whale optimization algorithm[J]. Journal of Computational Design and Engineering, 2018, 5 (3): 275- 284
doi: 10.1016/j.jcde.2017.12.006
[23]   黄元春, 张凌波 改进的鲸鱼优化算法及其应用[J]. 计算机工程与应用, 2019, 55 (21): 220- 226+270
HUANG Yuan-chun, ZHANG Ling-bo Improved whale optimization algorithm and its application[J]. Computer Engineering and Applications, 2019, 55 (21): 220- 226+270
doi: 10.3778/j.issn.1002-8331.1901-0296
[24]   CAI Y, SHAO C, ZHOU Y, et al Differential evolution with adaptive guiding mechanism based on heuristic rules[J]. IEEE Access, 2019, 7: 58023- 58040
doi: 10.1109/ACCESS.2019.2914963
[25]   ZHONG Y W, LIU X, WANG L J, et al Particle swarm optimisation algorithm with iterative improvement strategy for multi-dimensional function optimisation problems[J]. International Journal of Innovative Computing and Applications, 2012, 4 (3): 223- 232
[26]   MENG A B, CHEN Y C, YIN H, et al Crisscross optimization algorithm and its application[J]. Knowledge Based Systems, 2014, 67: 218- 229
doi: 10.1016/j.knosys.2014.05.004
[27]   SEYEDALI M, SEYEDM M, LEWIS A Grey wolf optimizer[J]. Advances in Engineering Software, 2014, 69: 46- 61
doi: 10.1016/j.advengsoft.2013.12.007
[28]   PAN W T A new fruit fly optimization algorithm: taking the financial distress model as an example[J]. Knowledge-based Systems, 2012, 26: 69- 74
doi: 10.1016/j.knosys.2011.07.001
[29]   MALLIPEDDI R, SUGANTHAN P N, PAN Q K Differential evolution algorithm with ensemble of parameters and mutation strategies[J]. Applied Soft Computing Archive, 2011, 11 (2): 1679- 1696
doi: 10.1016/j.asoc.2010.04.024
[30]   KARABOGA D, BASTURK B On the performance of artificial bee colony (abc) algorithm[J]. Applied Soft Computing Archive, 2008, 8 (1): 687- 697
doi: 10.1016/j.asoc.2007.05.007
[1] Chao-bo ZHANG,Yong-zheng LIU,Hong-bo LI,Yang ZHAO,Li-zhu ZHANG,Zi-hao WANG. Weighted residual clustering-based building load prediction interval estimation[J]. Journal of ZheJiang University (Engineering Science), 2022, 56(5): 930-937.
[2] Yun-hao WANG,Ming-hui SUN,Yi XIN,Bo-xuan ZHANG. Robot tactile recognition system based on piezoelectric film sensor[J]. Journal of ZheJiang University (Engineering Science), 2022, 56(4): 702-710.
[3] Zhi-hui GE,Jiang-kuan XING,Kun LUO,Jian-ren FAN. Application of ensemble learning based on preferred sample selection in desulfurization optimization process[J]. Journal of ZheJiang University (Engineering Science), 2021, 55(8): 1566-1575.
[4] Qi ZHANG,Hong CHEN,Ji-biao ZHOU,Min ZHANG,Lin GUO,Ren-fa YANG. Effect of roadway access on traffic safety at adjacent intersection[J]. Journal of ZheJiang University (Engineering Science), 2021, 55(4): 720-726.
[5] Shuo-peng WANG,Peng YANG,Hao SUN,Mai LIU. Fingerprint-based sound source localization method using two-stage reference points matching[J]. Journal of ZheJiang University (Engineering Science), 2019, 53(6): 1198-1204.
[6] XU Yue, XU Zhi-hai, FENG Hua-jun, LI Qi, CHEN Yue-ting, XU Yi, ZHAO Hong-bo. Registration and stitching optimization for two-scene-type remote sensing image[J]. Journal of ZheJiang University (Engineering Science), 2019, 53(1): 107-114.
[7] LIU Dong-xu, DONG Hong-zhao. Fractal tree based self-balanced partitioning algorithms for bike sharing system[J]. Journal of ZheJiang University (Engineering Science), 2018, 52(7): 1275-1283.
[8] LIU Ru-hui, HUANG Wei-ping, WANG Kai, LIU Chuang, LIANG Jun. Semi-supervised constraint ensemble clustering by fast search and find of density peaks[J]. Journal of ZheJiang University (Engineering Science), 2018, 52(11): 2191-2200.
[9] YOU Hai-hui, MA Zeng-yi, TANG Yi-jun, WANG Yue-lan, ZHENG Lin, YU Zhong, JI Cheng-jun. Soft measurement of heating value of burning municipal solid waste for circulating fluidized bed[J]. Journal of ZheJiang University (Engineering Science), 2017, 51(6): 1163-1172.
[10] LI Jian-li, DING Ding, LI Tao. Multi-objective hybrid cloud task scheduling using twice clustering[J]. Journal of ZheJiang University (Engineering Science), 2017, 51(6): 1233-1241.
[11] MAO Yi-yu, LIU Jian-xun, HU Rong, TANG Ming-dong. Collaborative filtering algorithm based on Logistic function and user clustering[J]. Journal of ZheJiang University (Engineering Science), 2017, 51(6): 1252-1258.
[12] SU Liang, SONG Ming-liang, DONG Shi-lin, LUO Yao-zhi. Automatic analysis of stabilization diagram using iterative genetic-fuzzy clustering method[J]. Journal of ZheJiang University (Engineering Science), 2017, 51(3): 514-523.
[13] LI Tao, WANG Shi-tong. Incremental zero-order TSK fuzzy classifier and its robust version[J]. Journal of ZheJiang University (Engineering Science), 2017, 51(10): 1901-1911.
[14] TU Ding, CHEN Ling, CHEN Gen cai, WU Yong, WANG Jing chang. Hierarchical online NMF for detecting and tracking topics[J]. Journal of ZheJiang University (Engineering Science), 2016, 50(8): 1618-1626.
[15] YANG Hui lin, HUANG Zhi gang, LIU Jiu wen, DU Yuan feng. WIFI fingerprinting localization based on Kernel Fuzzy C means II Clustering[J]. Journal of ZheJiang University (Engineering Science), 2016, 50(6): 1126-1133.