Please wait a minute...
浙江大学学报(工学版)
浙江大学学报(工学版)  2022, Vol. 56 Issue (5): 977-986    DOI: 10.3785/j.issn.1008-973X.2022.05.015
计算机与控制工程     
基于聚类和探测精英引导的蜻蜓算法
杜晓昕(),王浩,崔连和,罗金琦,刘岩,张剑飞,王一萍
齐齐哈尔大学 计算机与控制工程学院，黑龙江 齐齐哈尔 161006
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
 全文: PDF(1152 KB)   HTML
摘要：

针对蜻蜓算法（DA）收敛速度慢、收敛精度低、全局搜索能力差等不足，提出新的蜻蜓优化算法. 利用tent混沌初始化种群并对种群进行K-Means++聚类，根据聚类的结果分别对种群个体进行反向学习和高斯变异以增强种群的多样性，提高搜索效率. 引入非线性自适应因子加快收敛速度，使用探测精英引导策略增强算法跳出局部收敛的能力. 引入平方散列探测增加收敛精度. 将该优化算法应用于8个典型复杂函数优化问题，并与原蜻蜓算法，以及其他仿生计算算法对比，实验结果表明该改进算法具有良好的全局收敛性和寻优精度.
关键词： 蜻蜓算法;  聚类;  探测精英引导策略;  平方散列探测;  tent混沌    
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 words: dragonfly algorithm    clustering    detection elite guidance strategy    square hash detection    tent chaos
收稿日期: 2021-06-12 出版日期: 2022-05-31
CLC:  TP 301.6  
基金资助: 2020年度黑龙江省省属高等学校基本科研业务费面上资助项目（135509112）
作者简介: 杜晓昕（1983—），女，教授，从事仿生计算研究. orcid.org/0000-0002-9519-4850. E-mail： duxiaoxinpro@163.com
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章　　
杜晓昕
王浩
崔连和
罗金琦
刘岩
张剑飞
王一萍

引用本文:

杜晓昕,王浩,崔连和,罗金琦,刘岩,张剑飞,王一萍. 基于聚类和探测精英引导的蜻蜓算法[J]. 浙江大学学报(工学版), 2022, 56(5): 977-986.

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.

链接本文:

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

图 1  飞行步长的权重对比曲线
图 2  探测精英引导机制示意图
图 3  平方散列探测替换示意图
图 4  基于聚类和探测精英引导的蜻蜓算法流程图
函数名 表达式 维度 搜索区域
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]
表 1  8个典型的复杂函数
函数 算法 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
表 2  单峰函数2 000次独立运行结果
函数 算法 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
表 3  多峰函数2 000次独立运行结果
图 5  CEDA算法与其他经典算法的收敛效果对比图
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] 章超波,刘永政,李宏波,赵阳,张丽珠,王子豪. 基于加权残差聚类的建筑负荷预测区间估计[J]. 浙江大学学报(工学版), 2022, 56(5): 930-937.
[2] 王云灏,孙铭会,辛毅,张博宣. 基于压电薄膜传感器的机器人触觉识别系统[J]. 浙江大学学报(工学版), 2022, 56(4): 702-710.
[3] 葛志辉,邢江宽,罗坤,樊建人. 基于样本优选的集成学习在脱硫优化中的应用[J]. 浙江大学学报(工学版), 2021, 55(8): 1566-1575.
[4] 庞维庆,何宁,罗燕华,郁晞. 基于数据融合的ABC-SVM社区疾病预测方法[J]. 浙江大学学报(工学版), 2021, 55(7): 1253-1260.
[5] 张琦,陈红,周继彪,张敏,郭璘,杨仁法. 道路开口对临近交叉口交通安全的影响[J]. 浙江大学学报(工学版), 2021, 55(4): 720-726.
[6] 王硕朋,杨鹏,孙昊,刘迈. 两级参考点匹配位置指纹声源定位方法[J]. 浙江大学学报(工学版), 2019, 53(6): 1198-1204.
[7] 许越, 徐之海, 冯华君, 李奇, 陈跃庭, 徐毅, 赵洪波. 双场景类型遥感图像的配准拼接优化[J]. 浙江大学学报(工学版), 2019, 53(1): 107-114.
[8] 刘冬旭, 董红召. 共享自行车系统调度区域的分形树自平衡划分算法[J]. 浙江大学学报(工学版), 2018, 52(7): 1275-1283.
[9] 李文婧, 孙锋, 李茜瑶, 马东方. 采用递归有序聚类的信号控制时段划分方法[J]. 浙江大学学报(工学版), 2018, 52(6): 1150-1156.
[10] 曲昭伟, 罗瑞琪, 陈永恒, 曹宁博, 邓晓磊, 汪昆维. 信号交叉口右转机动车轨迹特性[J]. 浙江大学学报(工学版), 2018, 52(2): 341-351.
[11] 孟濬, 邓晓雨, 虞捷舟. 基于变量聚类的BP神经网络术后生存期预测模型[J]. 浙江大学学报(工学版), 2018, 52(12): 2365-2371.
[12] 刘如辉, 黄炜平, 王凯, 刘创, 梁军. 半监督约束集成的快速密度峰值聚类算法[J]. 浙江大学学报(工学版), 2018, 52(11): 2191-2200.
[13] 王桦, 韩同阳, 周可. 公安情报中基于关键图谱的群体发现算法[J]. 浙江大学学报(工学版), 2017, 51(6): 1173-1180.
[14] 尤海辉, 马增益, 唐义军, 王月兰, 郑林, 俞钟, 吉澄军. 循环流化床入炉垃圾热值软测量[J]. 浙江大学学报(工学版), 2017, 51(6): 1163-1172.
[15] 李建丽, 丁丁, 李涛. 基于二次聚类的多目标混合云任务调度算法[J]. 浙江大学学报(工学版), 2017, 51(6): 1233-1241.