基于自动快速密度峰值聚类的粒子群动态优化算法

doi:10.11772/j.issn.1001-9081.2022060815

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (S1): 154-162.DOI: 10.11772/j.issn.1001-9081.2022060815

• 先进计算 • 上一篇

基于自动快速密度峰值聚类的粒子群动态优化算法

李飞¹^,²^,³^,⁴(), 乐强², 潘紫微¹, 孙怡宁³, 余晓流⁴

^1.马鞍山学院智造工程学院，安徽马鞍山，243100
^2.安徽工业大学电气与信息工程学院，安徽马鞍山，243032
^3.中国科学院合肥物质科学研究院，合肥230031
^4.特种重载机器人安徽省重点实验室（安徽工业大学），安徽马鞍山，243032

收稿日期:2022-06-04 修回日期:2022-08-12 接受日期:2022-08-13 发布日期:2023-07-04 出版日期:2023-06-30
通讯作者: 李飞
作者简介:李飞（1988—），男，安徽太和人，副教授，博士，CCF会员，主要研究方向：进化多目标优化、动态优化.lanceleeneu@126.com
乐强（1998—），男，安徽池州人，硕士研究生，主要研究方向：动态优化、多模态优化
潘紫微（1957—），男，江苏南京人，教授，博士，主要研究方向：机械设计及其自动化
孙怡宁（1963—），男，安徽太湖人，教授，博士生导师，博士，主要研究方向：生物医学信息工程、智能感知
余晓流（1962—），男，安徽岳西人，教授，博士生导师，博士，主要研究方向：特种重载机器人动态优化、机械设计。
基金资助:
国家自然科学基金青年项目(61903003);安徽省自然科学基金青年项目(2008085QE227);特种重载机器人安徽省重点实验室开放课题(TZJQR001?2021)

Dynamic particle swarm optimization algorithm based on automatic fast density peak clustering

Fei LI¹^,²^,³^,⁴(), Qiang YUE², Ziwei PAN¹, Yining SUN³, Xiaoliu YU⁴

^1.College of Intelligent Manufacturing Engineering，Ma’anshan University，Ma’anshan Anhui 243100，China
^2.College of Electrical and Information Engineering，Anhui University of Technology，Ma’anshan Anhui 243032，China
^3.Hefei Institutes of Physical Science，Chinese Academy of Sciences，Hefei Anhui 230031，China
^4.Anhui Province Key Laboratory of Special Heavy Load Robot （Anhui University of Technology），Ma’anshan Anhui 243032，China

Received:2022-06-04 Revised:2022-08-12 Accepted:2022-08-13 Online:2023-07-04 Published:2023-06-30
Contact: Fei LI

摘要/Abstract

摘要：

针对常规多种群方法在求解动态优化问题时往往存在多样性缺失现象，提出一种基于自动快速密度峰值聚类的粒子群动态优化算法（DPCPSO）。首先，利用自动快速密度峰值聚类通过粒子的自身密度和相对距离创建无敏感参数子种群；然后，使用粒子群优化（PSO）来寻找最优解，在搜索过程中采用停滞计数器来判断粒子是否停滞，防止种群过早收敛；最后，采用最优粒子重定位策略响应环境变化。为了验证所提出算法的性能，在移动峰值基准（MPB）和广义动态基准生成器（GDBG）测试问题上进行了仿真实验。仿真实验中，所提算法性能与基于亲和传播聚类的动态优化算法（APCPSO）、基于聚类的动态优化（CPSO）算法等其他先进算法相比较，在峰值数大于20以及变化频率为2 000和3 000时均取得良好的结果。实验结果表明，所提算法更适合求解多模态和快变特性的动态优化问题。

关键词: 动态优化问题, 多种群方法, 快速密度峰值聚类, 停滞检测, 最优粒子重定位策略

Abstract:

Aiming at the lack of diversity in solving dynamic optimization problems by conventional multi-population methods， a dynamic Particle Swarm Optimization algorithm based on automatic fast Density Peak Clustering （DPCPSO） was proposed. Firstly， the automatic fast peak density clustering method was used to generate the subpopulations without introducing any sensitive parameter through the densities and relative distances of particles. Therefore， Particle Swarm Optimization （PSO） was used to find the optimal solution. In the search process， stagnation counter was used to determine whether the particles are stagnant to prevent premature convergence of the population. Finally， the optimal particle relocation strategy was adopted to respond to the environmental changes. To validate the performance of the proposed algorithm， a variety of experiments were carried out on Moving Peaks Benchmark （MPB） and Generalized Dynamic Benchmark Generator （GBDG） problems. In simulation experiments， the performance of the proposed algorithm was compared with other advanced algorithms such as Affinity Propagation on Clustering based PSO for dynamic optimization algorithm （APCPSO） and Clustering PSO （CPSO） algorithm. Good results were obtained when the peak number was greater than 20 and the change frequency was 2 000 and 3 000. Experimental results show that the proposed algorithm was more suitable for solving dynamic optimization problems with multimodal and fast change characteristics.

Key words: Dynamic Optimization Problem (DOP), multi-population method, Density Peak Clustering (DPC), stagnation detection, optimal particle relocation strategy

中图分类号:

TP301.6

李飞, 乐强, 潘紫微, 孙怡宁, 余晓流. 基于自动快速密度峰值聚类的粒子群动态优化算法[J]. 计算机应用, 2023, 43(S1): 154-162.

Fei LI, Qiang YUE, Ziwei PAN, Yining SUN, Xiaoliu YU. Dynamic particle swarm optimization algorithm based on automatic fast density peak clustering[J]. Journal of Computer Applications, 2023, 43(S1): 154-162.

图/表 12

图1 DPCPSO算法流程

图2 快速密度峰值聚类示意图

图3 聚类截止数k与峰值关系

图4 最优粒子重定位策略

表1 DPCPSO的参数设置

参数	值
峰值数目P	10
每个峰的初始高度	50.0
惯性向量范围 $ω$	［0.3，0.6］
学习因子 $c 1 c 2$	1.7
变化频率U	5 000（MPB） 10 000*D（GDBG）
环境K	100（MPB） 60（GDBG）
高度变化率 $α$	7.0（MPB） 5.0（GDBG）
宽度变化率 $β$	1.0（MPB） 0.5（GDBG）
每个维度范围	［0，100］（MPB）［10，100］（GDBG）
维度D	5（MPB） 10（GDBG）
每个峰的高度范围	［30.0，70.0］（MPB）［10.0，100.0］（GDBG）
每个峰的宽度范围	［1，12］（MPB）［1，10］（GDBG）

表1 DPCPSO的参数设置

参数	值
峰值数目P	10
每个峰的初始高度	50.0
惯性向量范围 $ω$	［0.3，0.6］
学习因子 $c 1 c 2$	1.7
变化频率U	5 000（MPB） 10 000*D（GDBG）
环境K	100（MPB） 60（GDBG）
高度变化率 $α$	7.0（MPB） 5.0（GDBG）
宽度变化率 $β$	1.0（MPB） 0.5（GDBG）
每个维度范围	［0，100］（MPB）［10，100］（GDBG）
维度D	5（MPB） 10（GDBG）
每个峰的高度范围	［30.0，70.0］（MPB）［10.0，100.0］（GDBG）
每个峰的宽度范围	［1，12］（MPB）［1，10］（GDBG）

表2 不同N值得到的EBBC的统计结果（均值和方差）

峰值数 P	粒子数N
	70		85		100		115		130		145		160
	均值	方差	均值	方差	均值	方差	均值	方差	均值	方差	均值	方差	均值	方差
10	0.85	0.34	0.78	0.21	0.76	0.26	0.89	0.41	1.03	0.31	1.14	0.34	1.33	0.26
20	1.19	0.29	1.06	0.21	1.03	0.34	1.12	0.31	1.21	0.20	1.23	0.26	1.54	0.35
30	1.38	0.25	1.30	0.17	1.29	0.19	1.36	0.30	1.34	0.25	1.49	0.24	1.66	0.30
50	1.91	0.27	1.53	0.19	1.52	0.19	1.53	0.14	1.61	0.17	1.75	0.21	1.86	0.23

表3 不同N值得到的MPB问题的排名

峰值数 P	粒子数N
峰值数 P	70	85	100	115	130	145	160
平均值	4.50	2.00	1.00	3.75	4.25	5.75	6.75
10	3	2	1	4	5	6	7
20	4	2	1	3	5	6	7
30	4	2	1	5	3	6	7
50	7	2	1	3	4	5	6

图5 MPB上不同θ与不同环境的比较

表4 各算法得到的EBBC值在不同峰数MPB上的统计结果

峰值数P	DPCPSO		APCPSO		CPSO		DynDE		PSO-CP		CDDE_Ar		jDE
峰值数P	均值	方差	均值	方差	均值	方差	均值	方差	均值	方差	均值	方差	均值	方差
+/-/≈			5/2/0		5/2/0		7/0/0		7/0/0		7/0/0		7/0/0
1	1.58	1.05	1.13（+）	0.14	0.14（-）	0.11	3.80（+）	0.17	3.21（+）	0.22	1.12（+）	0.12	2.02（+）	0.29
5	0.69	0.39	0.53（-）	0.31	0.72（+）	0.30	1.64（+）	0.09	3.05（+）	0.31	1.37（+）	0.18	1.43（+）	0.20
10	0.70	0.26	0.66（-）	0.24	1.06（+）	0.24	1.50（+）	0.05	1.23（+）	0.31	1.27（+）	0.11	1.59（+）	0.35
20	1.03	0.33	1.04（+）	0.27	1.59（+）	0.22	2.74（+）	0.07	2.34（+）	0.38	2.13（+）	0.31	2.25（+）	0.24
30	1.28	0.19	1.41（+）	0.24	1.58（+）	0.17	3.22（+）	0.10	2.07（+）	0.25	1.59（+）	0.29	2.56（+）	0.19
50	1.52	0.19	1.95（+）	0.28	1.57（+）	0.12	3.81（+）	0.10	2.13（+）	0.40	2.08（+）	0.29	2.67（+）	0.14
100	1.69	0.20	2.36（+）	0.29	1.49（-）	0.08	4.21（+）	0.12	2.04（+）	0.41	1.91（+）	0.26	2.53（+）	0.38

表5 各算法得到的EBBC值在不同移位程度的MPB上的统计结果

移位距离s	DPCPSO		APCPSO		CPSO		DynDE		PSO-CP		CDDE_Ar		jDE
移位距离s	均值	方差	均值	方差	均值	方差	均值	方差	均值	方差	均值	方差	均值	方差
+/-/≈			7/0/0		6/1/0		7/0/0		7/0/0		7/0/0		7/0/0
0	0.145	0.18	0.16（+）	0.24	0.80（+）	0.21	1.15（+）	0.31	0.87（+）	0.20	0.81（+）	0.12	0.96（+）	0.10
1	1.58	1.05	1.13（+）	0.14	0.14（-）	0.11	3.80（+）	0.17	3.21（+）	0.22	1.12（+）	0.12	2.02（+）	0.29
2	0.81	0.33	0.94（+）	0.41	1.17（+）	0.22	2.27（+）	0.18	1.98（+）	0.06	1.56（+）	0.19	2.12（+）	0.26
3	0.87	0.33	1.01（+）	0.37	1.36（+）	0.28	2.69（+）	0.07	2.21（+）	0.06	2.12（+）	0.17	2.55（+）	0.23
4	1.02	0.31	1.38（+）	0.27	3.29（+）	0.29	2.61（+）	0.24	2.61（+）	0.11	2.67（+）	0.22	3.10（+）	0.31
5	1.15	0.32	1.19（+）	0.36	1.58（+）	0.32	4.26（+）	0.10	3.20（+）	0.13	2.63（+）	0.25	3.19（+）	0.30
6	1.14	0.40	1.33（+）	0.47	1.53（+）	0.29	4.55（+）	0.48	3.93（+）	0.14	3.21（+）	0.31	3.78（+）	0.30

表6 各算法得到的EBBC 值在不同变化频率的 MPB 上的统计结果

变化频率U	DPCPSO		APCPSO		CPSO		DynDE		PSO-CP		CDDE_Ar		jDE
变化频率U	均值	方差	均值	方差	均值	方差	均值	方差	均值	方差	均值	方差	均值	方差
+/-/≈			2/2/0		4/0/0		4/0/0		4/0/0		4/0/0		4/0/0
2 000	4.73	0.66	5.72（+）	0.66	5.98（+）	0.94	5.73（+）	0.60	6.13（+）	0.88	6.05（+）	0.81	6.76（+）	1.04
3 000	1.80	0.43	2.12（+）	0.43	2.37（+）	0.13	2.39（+）	0.17	2.17（+）	0.10	2.13（+）	0.06	2.35（+）	0.26
5 000	0.69	0.30	0.66（-）	0.24	1.06（+）	0.24	1.50（+）	0.05	1.23（+）	0.31	1.27（+）	0.11	1.59（+）	0.35
10 000	0.40	0.26	0.32（-）	0.29	0.74（+）	0.10	1.33（+）	0.24	0.97（+）	0.30	0.85（+）	0.17	0.96（+）	0.34

表7 各算法在GBDG上得到的EBBC值的统计结果（均值和标准差）

变化类型	DPCPSO		APCPSO		CPSO		DynDE		PSO-CP		CDDE_Ar		jDE
变化类型	均值	方差	均值	方差	均值	方差	均值	方差	均值	方差	均值	方差	均值	方差
+/-/≈			3/3/0		5/1/0		4/2/0		6/0/0		4/2/0		6/0/0
T1	0.32	0.26	0.01（+）	0.01	0.04（+）	0.43	0.07（-）	2.95	0.04（+）	0.52	0.01（-）	0.03	0.03 （+）	0.43
T2	0.46	0.50	0.71（+）	0.63	2.72（+）	6.52	2.56（+）	8.43	2.70（+）	7.12	1.26（+）	5.89	3.60（+）	7.92
T3	1.77	0.92	2.35（+）	2.03	4.13（+）	8.99	5.42（+）	9.24	4.68（+）	8.98	12.54（+）	29.74	3.11（+）	8.26
T4	0.59	0.13	0.09（-）	0.56	0.09（-）	0.78	0.12（-）	0.94	0.05（+）	0.82	0.07（-）	0.32	0.02（+）	0.63
T5	0.88	0.42	0.28（-）	0.19	1.87（+）	4.49	1.57（+）	4.46	1.58（+）	4.45	0.79（+）	2.00	2.32（+）	5.38
T6	0.59	0.29	0.35（-）	0.16	1.16（+）	4.48	1.31（+）	6.25	1.52（+）	5.93	0.97（+）	3.28	1.24（+）	5.54

参考文献 23

1	仇书山，陈劲帆，毛承雄，等.含能源路由器的交直流互联配电网协调动态优化［J/OL］.高电压技术，2022：1-16［2022-05-04］..
2	蒋彪，吴楷，蒋炜，等.边缘计算下整车驾驶辅助系统动态优化［J］.智能网联汽车，2022（1）：54-58. 10.11970/j.issn.2095-7866.2022.1.gyjjlt202201020
3	原毅军，孙晓华.宏观经济要素与企业资本结构的动态优化［J］.经济与管理研究，2006（5）：39-42. 10.3969/j.issn.1000-7636.2006.05.007
4	JIN Y， BRANKE J. Evolutionary optimization in uncertain environments a survey ［J］. IEEE Transactions on Evolutionary Computation， 2005，9（3）：303-317. 10.1109/tevc.2005.846356
5	LI C， NGUYEN T T， YANG M， et al. An adaptive multi-population framework for locating and tracking multiple optima ［J］.IEEE Transactions on Evolutionary Computation，2016，20（4）：590-605. 10.1109/tevc.2015.2504383
6	ZHOU A， JIN Y， ZHANG Q. A population prediction strategy for evolutionary dynamic multi-objective optimization ［J］. IEEE Transactions on Cybernetics，2013，44（1）：40-53. 10.1109/tcyb.2013.2245892
7	YANG S， LI C H. A clustering particle swarm optimizer for locating and tracking multiple optima in dynamic environments ［J］. IEEE Transactions on Evolutionary Computation，2010，14（6）：959-974. 10.1109/tevc.2010.2046667
8	BRANKE J， KAUSSLER T， SMIDT C，et al. A multi-population approach to dynamic optimization problems ［M］// PARMEE I C. Evolutionary Design and Manufacture. London：Springer， 2000： 299-307. 10.1007/978-1-4471-0519-0_24
9	LI C， YANG S. Fast multi-swarm optimization for dynamic optimization problems ［C］// Proceedings of the 2008 4th International Conference on Natural Computation. Piscataway：IEEE， 2008： 624-628. 10.1109/icnc.2008.313
10	PARROTT D， LI X. A particle swarm model for tracking multiple peaks in a dynamic environment using speciation ［C］// Proceedings of the 2004 Congress on Evolutionary Computation. Piscataway： IEEE， 2004： 98-103.
11	BIRD S， LI X. Using regression to improve local convergence ［C］// Proceedings of the 2007 IEEE Congress on Evolutionary Computation. Piscataway： IEEE，2007：592-599. 10.1109/cec.2007.4424524
12	LIU L， YANG S， WANG D. Particle swarm optimization with composite particles in dynamic environments ［J］. IEEE Transactions on Systems，Man， and Cybernetics， Part B （Cybernetics），2010，40（6）： 1634-1648. 10.1109/tsmcb.2010.2043527
13	BLACKWELL T， BRANKE J. Multi-swarm optimization in dynamic environments ［C］// Proceedings of the 2004 Workshops on Applications of Evolutionary Computing， LNCS 3005. Berlin： Springer， 2004：489-500.
14	MENDES R， MOHAIS A S. DynDE： a differential evolution for dynamic optimization problems ［C］// Proceedings of the 2005 IEEE Congress on Evolutionary Computation. Piscataway： IEEE，2005： 2808-2815.
15	BREST J， ZAMUDA A， BOSKOVIC B， et al. Dynamic optimization using self-adaptive differential evolution ［C］// Proceedings of the 2009 IEEE Congress on Evolutionary Computation. Piscataway： IEEE， 2009： 415-422. 10.1109/cec.2009.4982976
16	HALDER U， DAS S， MAITY D.A cluster-based differential evolution algorithm with external archive for optimization in dynamic environments ［J］. IEEE Transactions on Cybernetics，2013， 43（3）：881-897. 10.1109/tsmcb.2012.2217491
17	RODRIGUEZ A， LAIO A. Clustering by fast search and find of density peaks ［J］. Science，2014，344（6191）： 1492-1496. 10.1126/science.1242072
18	EBERHART R， KENNEDY J. A new optimizer using particle swarm theory ［C］// Proceedings of the 6th International Symposium on Micro Machine and Human Science. Piscataway： IEEE，1995：39-43. 10.1109/mhs.1995.494249
19	BLACKWELL T， BRANKE J， LI X. Particle swarms for dynamic optimization problems ［M］// BLUM C， MERKLE D. Swarm Intelligence. Berlin： Springer， 2008： 193-217.
20	LIU Y， LIU J， JIN Y， et al. An affinity propagation clustering based particle swarm optimizer for dynamic optimization ［J］.Knowledge-Based Systems，2020，195：No.105711. 10.1016/j.knosys.2020.105711
21	BRANKE J. Memory enhanced evolutionary algorithms for changing optimization problems ［C］// Proceedings of the 1999 Congress on Evolutionary Computation. Piscataway： IEEE，1999：1875-1882.
22	LI C， YANG S， NGUYEN T T，et al. Benchmark generator for CEC’2009 competition on dynamic optimization ［EB/OL］.［2022-05-17］. ’2009_Competition_on_Dynamic_Optimization.
23	NGUYEN T T， YANG S， BRANKE J. Evolutionary dynamic optimization： a survey of the state of the art ［J］. Swarm and Evolutionary Computation，2012，6：1-24.[. 10.1016/j.swevo.2012.05.001

[1]	贾鹤鸣, 力尚龙, 陈丽珍, 刘庆鑫, 吴迪, 郑荣. 基于混沌宿主切换机制的䲟鱼优化算法[J]. 《计算机应用》唯一官方网站, 2023, 43(6): 1759-1767.
[2]	袁泉, 唐成亮, 徐雲鹏. 基于长度约束的蝙蝠高效用项集挖掘算法[J]. 《计算机应用》唯一官方网站, 2023, 43(5): 1473-1480.
[3]	孙亚男, 吴杰宏, 石峻岭, 高利军. 改进自组织映射的多无人机协同任务分配方法[J]. 《计算机应用》唯一官方网站, 2023, 43(5): 1551-1556.
[4]	程顺航, 李志华, 魏涛. 融合自举与语义角色标注的威胁情报实体关系抽取方法[J]. 《计算机应用》唯一官方网站, 2023, 43(5): 1445-1453.
[5]	马磊罗川李天瑞陈红梅. 基于模糊粗糙集的无监督动态特征选择算法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[6]	张瑾徐文周宇乔刘凯. 不规则物体点云切片中的多轮廓分割算法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[7]	杨淑莹国海铭李欣. 基于通道选择和多维特征融合的脑电信号分类[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[8]	温祥西彭娅婷毕可心衡宇铭吴明功. 基于最优样本集在线模糊最小二乘支持向量机的飞行冲突网络态势预测#br# #br# [J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[9]	喻诚皓仇润鹤. RIS辅助索引调制协作系统的误码率性能分析[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[10]	赵一鉴, 林利, 王茜蒨, 闻鹏, 杨东. 基于大地距离计算相似度的海上目标轨迹预测[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[11]	薛海蓉韩晓龙. 基于改进NSGA-Ⅱ的考虑自动引导车充电策略的集成调度[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[12]	李鹏, 王世林, 陈光武, 闫光辉. 基于改进的局部结构熵复杂网络重要节点挖掘[J]. 《计算机应用》唯一官方网站, 2023, 43(4): 1109-1114.
[13]	蒋溢, 伍书平, 胡昆, 龙林波. 基于Lasso和构造性覆盖算法的不均衡数据分类方法[J]. 《计算机应用》唯一官方网站, 2023, 43(4): 1086-1093.
[14]	黄霖符强童楠. 基于自适应调整哈里斯鹰优化算法求解机器人路径规划问题[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[15]	钟新成刘昶赵秀梅. 基于马尔可夫优化的高效用项集挖掘算法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.

基于自动快速密度峰值聚类的粒子群动态优化算法

Dynamic particle swarm optimization algorithm based on automatic fast density peak clustering

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献 23

相关文章 15

编辑推荐

Metrics