基于划分的多尺度量子谐振子算法多峰优化

陆志君; 安俊秀; 王鹏

doi:10.16383/j.aas.2016.c150429

基于划分的多尺度量子谐振子算法多峰优化

doi: 10.16383/j.aas.2016.c150429

成都信息工程大学并行实验室成都 610225

基金项目:

国家社会科学基金 12XSH019

国家自然科学基金 60702075

详细信息

作者简介:
陆志君成都信息工程大学软件工程学院硕士研究生.2013年获得南京信息工程大学软件工程学院学士学位.主要研究方向为分布式计算, 智能算法.E-mail:bingjungg@126.com

安俊秀成都信息工程大学软件工程学院教授.2004年获得西安交通大学工学硕士学位.主要研究方向为社会计算, 智能搜索, 分布式计算.E-mail:anjunxiu@cuit.edu.cn

通讯作者:
王鹏成都信息工程大学软件工程学院教授.2004年获得中国科学院成都计算机应用研究所博士学位.主要研究方向为分布式计算, 智能算法.本文通信作者.E-mail:wp002005@163.com

计量
- 文章访问数: 2515
- HTML全文浏览量: 196
- PDF下载量: 986
- 被引次数: 20
出版历程
- 收稿日期: 2015-07-02
- 录用日期: 2015-11-02
- 刊出日期: 2016-02-20

Partition-based MQHOA for Multimodal Optimization

Parallel Laboratory, Chengdu University of Information and Technology, Chengdu 610225

Funds:

National Social Science Foundation of China 12XSH019

Supported by National Natural Science Foundation of China 60702075

More Information

Author Bio:
Master student at the College of Software, Chengdu University of Information Technology. He received his bachelor degree from the College of Software, Nanjing University of Information Technology in 2013. His research interest covers distributed computing and intelligent algorithm

Professor at the College of Software, Chengdu University of Information Technology. She received her master degree from Xi0an Jiaotong University in 2004. Her research interest covers social computing, intelligent searching, and distributed computing

Corresponding author: WANG Peng Professor at the College of Software, Chengdu University of Information Technology. He received his Ph. D. degree from Chengdu Institute of Computer Application, Chinese Academy of Sciences in 2004. His research interest covers distributed computing and intelligent algorithm. Corresponding author of this paper

摘要

摘要: 针对多峰优化问题, 本文结合多尺度量子谐振子算法的全局优化特性提出了基于划分的多尺度量子谐振子算法.对定义域进行合理均匀划分, 根据划分区域长度构建初始基态高斯曲线, 随着标准差衰减高斯曲线逐渐收敛, 从而在各个区域内快速搜索到极值点.对于实际函数的维度和极值数不同, 本文提出固定分辨率策略和多级分辨率策略来解决实际问题, 通过寻优精确性、全极值点寻优和全局多峰优化三个角度进行实验, 对比蚁群算法、差分进化算法等主流群智能算法, 可以表明该算法参数设置简单, 具有很好的寻优准确性、快速收敛性和记忆性.
- 量子谐振子 /
- 多峰优化 /
- 全极值 /
- 群智能算法
Abstract: To solve the problem of multimodal optimization, a partition-based multi-scale quantum harmonic oscillator algorithm (MQHOA) is proposed depending on MQHOA's global optimization characteristic. It divides reasonably a domain into uniform areas, and then Gauss curves with ground state can be constructed according to the lengths of these uniform areas. With the attenuation of standard deviation, the Gauss curves will converge gradually, thus, extreme points can be found quickly. In addition, two strategies comprising fixed wavelength resolution and muti-level resolution are used for practical problems. Experiments are carried out from three aspects including optimization's accuracy, all extremal points optimization and global multimodal optimization. Compared with the ant colony algorithm, differential evolution algorithms and other mainstream swarm intelligence algorithms, the algorithm has, in addition to its simpleness on setting parameters, superior optimization accuracy, fast convergence and memory property.
- Quantum harmonic oscillator /
- multimodal optimization /
- all the extremum /
- swarm intelligence algorithms

HTML全文

图 1 k个高斯分布函数均匀叠加概率密度图

Fig. 1 Probability density map of the uniform superpositionwith k Gauss distribution functions

下载: 全尺寸图片幻灯片

图 2 不同函数的极小值搜索

Fig. 2 Search minimum values of different functions

下载: 全尺寸图片幻灯片

图 3 P-MQHOA收敛过程示意图

Fig. 3 Schematic diagram of P-MQHOA convergence process

下载: 全尺寸图片幻灯片

图 4 3级分辨率策略下对 $f (x, y)$ 求极值

Fig. 4 3-level resolution strategy for the extreme value of $f (x, y)$

下载: 全尺寸图片幻灯片

图 5 不等值极值点函数搜索准确性随a变化图

Fig. 5 Searching accuracy of unequal-value-extremum functionvaring with a

下载: 全尺寸图片幻灯片

图 6 等值极值点函数搜索准确性随a变化图

Fig. 6 Searching accuracy of equal-value-extremum functionvaring with a

下载: 全尺寸图片幻灯片

图 7 一维震荡函数曲线

Fig. 7 One-dimensional shock function curve

下载: 全尺寸图片幻灯片

图 8 二维Griewank函数

Fig. 8 Two-dimensional Griewank function

下载: 全尺寸图片幻灯片

图 9 算法全局寻优比较热力图

Fig. 9 Comparison of global optimization algorithms thermodynamic diagram

下载: 全尺寸图片幻灯片

表 1 一维震荡函数两种策略寻优性能比较

Table 1 Comparison of two strategies for one dimensional shock function

K₀	λ₀	K₁	CN₁	TC₁	K₂	CN₂	TC₂
2	0.1	3.9	10	0.0030	4.0	4	0.0038
12	0.01	13.9	100	0.0180	11.9	10	0.0084
46	0.001	47.7	1 000	0.1499	41.6	31	0.0348
156	0.0001	157.0	10 000	1.312	144.2	100	0.167
500	0.00001	493.2	100 000	10.374	461.0	316	0.767
1592	0.000001	1515.0	1 000 000	95.614	1 419.6	1 000	3.067

下载: 导出CSV

表 2 二维Griewank函数两种策略寻优性能比较

Table 2 Comparison of two strategies for two dimensional Griewank function

K₀	λ₀	K₁	CN₁	TC₁	K₂	CN₂	TC₂
1 369	20	75.7	10	0.051	40.3	4	0.036
1 369	10	307.8	400	0.183	231.2	10	0.291
1 369	5	1 049.2	1 600	0.726	617.5	31	1.472
1 369	2	1 333.4	10 000	4.078	670.2	100	1.657
1 369	1	1 340.5	40 000	15.312	783.0	316	9.64
1 369	0.5	1 353.10	160 000	57.272	1 924.1	1 000	21.04

下载: 导出CSV

表 3 P-MQHOA与蚁群算法全极值搜索比较

Table 3 Comparison of total-extremum-searching of P-MQHOA and ant colony algorithm

NO.	P-MQHOA (x₁, x₂, f/(x₁, x₂))	ANT
1	(-0.878093608, -0.878093599, 3.53255484)	(-0.8781, -0.8781, 3.5326)
2	(-0.878093550, -0.526852857, 3.042136418)	-0.8737, -0.5310, 3.0362
3	(-0.878093617, -0.17561706, 2.796928371)	(-0.8725, -0.1810, 2.7873)
4	(-0.878093568, 0.175617049, 2.796928371)	(-0.8725, -0.5310, 3.0362)
5	(-0.878093628, 0.526852825, 3.042136418)	(-0.8700, 0.5175, 3.0176)
6	(-0.878093611, 0.878093569, 3.53255484)	(-0.8675, 0.8675, 3.4966)
7	(-0.52685281, -0.878093573, 3.042136418)	(-0.5310, -0.8737, 3.0362)
8	(-0.526852791, -0.526852812, 2.551717996)	(-0.5268, -0.5268, 2.5517)
9	(-0.526852794, -0.175617069, 2.306509949)	(-0.5352, -0.1773, 2.3056)
10	(-0.526852803, 0.17561705, 2.306509949)	(-0.5215, 0.1700, 2.2969)
11	(-0.526852866, 0.526852858, 2.551717996)	(-0.5200, 0.5200, 2.5367)
12	(-0.526852827, 0.878093628, 3.042136418)	(-0.5175, 0.8700, 3.0176)
13	(-0.175617027, -0.878093592, 2.796928371)	(-0.1810, -0.8725, 2.7873)
14	(-0.175617075, -0.526852805, 2.306509949)	(-0.1773, -0.5252, 2.3056)
15	(-0.175617028, -0.175617046, 2.061301903)	(-0.1756, -0.1756, 2.0613)
16	(-0.175617006, 0.175617028, 2.061301903)	(-0.1756, 0.1756, 2.0559)
17	(-0.175617067, 0.526852847, 2.306509949)	(-0.1700, 0.5215, 2.2969)
18	(-0.175617056, 0.878093620, 2.796928371)	(-0.1675, 0.8700, 2.7759)
19	(0.175617041, -0.878093592, 2.796928371)	(0.1675, -0.8700, 2.7759)
20	(0.175617068, -0.526852815, 2.306509949)	(0.1700, -0.5215, 2.2969)
21	(0.175617061, -0.175617041, 2.061301903)	(0.1715, -0.1715, 2.0559)
22	(0.175617051, 0.175617057, 2.061301903)	(0.1756, 0.1756, 2.0613)
23	(0.175617054, 0.526852783, 2.306509949)	(0.1773, 0.5252, 2.3056)
24	(0.175617039, 0.878093590, 2.796928371)	(0.1810, 0.8725, 2.7873)
25	(0.526852762, -0.878093542, 3.042136418)	(0.5175, -0.8700, 3.0176)
26	(0.526852876, -0.526852885, 2.551717996)	(0.5200, -0.5200, 2.5367)
27	(0.526852785, -0.175617064, 2.306509949)	(0.5215, -0.1700, 2.2969)
28	(0.526852823, 0.175617064, 2.306509949)	(0.5252, 0.1773, 2.3056)
29	(0.52685278, 0.52685282, 2.551717996)	(0.5268, 0.5268, 2.5517)
30	(0.526852781, 0.878093598, 3.042136418)	(0.5310, 0.8737, 3.0362)
31	(0.878093552, -0.878093598, 3.53255484)	(0.8675, -0.8675, 3.4966)
32	(0.87809359, -0.526852814, 3.042136418)	(0.8700, -0.5175, 3.0176)
33	(0.878093528, -0.175617038, 2.796928371)	(0.8700, -0.1675, 2.7759)
34	(0.878093604, 0.175617041, 2.796928371)	(0.8725, 0.1810, 2.7873)
35	(0.878093617, 0.526852807, 3.042136418)	(0.8737, 0.5310, 3.0362)
36	(0.878093597, 0.878093581, 3.53255484)	(0.8781, 0.8781, 3.5326)

下载: 导出CSV

表 4 二维Griewank函数极值分布拟合结果

Table 4 Fitting results of extremum values0 distribution of Griewank function

Func.	No.	ε	P-MQHOA	MOBi-DE	CDE	SDE	S-CMA	CMA	SPSO	PER-PSO	r2pso	r3pso	Niching-based	BNPGA NSGA-Ⅱ
f₁	1	0.05	1(4)	1(4)	1(4)	1(4)	1(4)	1(4)	0.44(12)	0.82(10)	0.76(11)	0.84(9)	1(4)	1(4)
f₂	1	0.05	1(5)	1(5)	1(5)	1(5)	1(5)	1(5)	0.40(12)	1(5)	0.88(11)	0.96(10)	1(5)	1(5)
f₃	2	1E-6	2(2.5)	2(2.5)	2(2.5)	1.96(5)	1.92(7)	1.95(6)	1.38(9)	0.8(10)	0.48(12)	0.6(11)	2(2.5)	1.5(8)
f₄	5	1E-6	5(1.5)	5(1.5)	3.84(10)	4.70(6)	0.04(12)	0.6(11)	4.88(3)	4.84(4)	4.68(7)	4.74(5)	4.37(9)	4.64(8)
f₅	1	1E-6	1(6)	1(6)	0.72(12)	1(6)	1(6)	1(6)	1(6)	1(6)	1(6)	1(6)	1(6)	1(6)
f₆	5	1E-6	5(1.5)	5(1.5)	3.96(9)	4.6(7)	0(12)	0.64(11)	4.92(4)	4.96(3)	4.88(5)	4.72(6)	4.52(8)	3.56(10)
f₇	1	1E-6	1(5.5)	1(5.5)	0.8(11)	1(5.5)	1(5.5)	1(5.5)	1(5.5)	1(5.5)	1(5.5)	1(5.5)	0.6(12)	1(5.5)
f₈	4	5E-4	4(1.5)	4(1.5)	0.32(12)	3.72(4.5)	3.72(4.5)	3.43(7)	0.84(11)	3.68(6)	2.92(9)	2.76(10)	3.74(3)	3.34(8)
f₉	2	1E-6	2(3)	2(3)	0.04(12)	2(3)	1.6(7)	2(3)	0.08(11)	1.96(6)	1.44(9)	1.56(8)	2(3)	1.24(10)
f₁₀	1	1E-6	1(2)	1(2)	0.52(9)	0.32(10)	0.06(12)	0.18(11)	0.56(8)	1(2)	0.88(6)	0.76(7)	0.94(5)	0.96(4)
f₁₁	18 5	E-2	17.5(1)	17.4(2)	11.39(12)	12.78(9)	12.04(10)	12(11)	14.36(7)	15.61(6)	15.95(5)	16.45(4)	16.94(3)	13.72(8)
f₁₂	6	0.05	6(1.5)	6(1.5)	5.56(6.5)	4.88(12)	5.56(6.5)	5.81(3)	5.6(5)	5.28(10)	5.52(8)	5.16(11)	5.36(9)	5.71(4)
f₁₃	36	1E-3	35.6(1)	35.4(2)	33.8(3)	23.8(7)	24.6(6)	23.6(8)	25.72(5)	21.8(12)	22.4(9)	22.2(10)	22.05(11)	31.76(4)
f₁₄	218	1E-3	163.56(2)	175.88(1)	152(3)	50.6(8)	0.6(12)	32.5(11)	70.12(6)	68.6(7)	40.6(10)	45.4(9)	92.76(5)	121.54(4)
Total ranks			38	39	111	92	109.5	102.5	104.5	92.5	113.5	111.5	85.5	88.5

下载: 导出CSV

表 5 P-MQHOA算法与MOBi-DE算法时间消耗 (s)

Table 5 Time consumption of P-MQHOA algorithm and MOBi-DE algorithm (s)

Func.	f₁	f₂	f₃	f₄	f₅	f₆	f₇	f₈	f₉	f₁₀	f₁₁	f₁₂	f₁₃	f₁₄
P-MQHOA	0.01	0.01	0.01	0.01	0.01	0.01	0.02	0.1	0.1	0.1	1.76	0.28	4.32	12.14
MOBi-DE	1.56	1.46	2.82	2.64	1.54	2.04	1.68	18.34	15.28	41.24	46.28	36.49	51.74	72.36

下载: 导出CSV

参考文献(15)

[1]	Chang Y W, Yu G F. Multi-Sub-Swarm PSO algorithm for multimodal function optimization. In:Proceedings of the 2014 International Conference on Computer Science and Information Technology. India:Springer, 2014. 687-695
[2]	Qu B Y, Suganthan P N, Das S. A distance-based locally informed particle swarm model for multimodal optimization. IEEE Transactions on Evolutionary Computation, 2013, 17(3):387-402 doi: 10.1109/TEVC.2012.2203138
[3]	Shih C J, Teng T L, Chen S K. A niche-related particle swarm meta-heuristic algorithm for multimodal optimization. In:Proceedings of the 2nd International Conference on Intelligent Technologies and Engineering Systems. Switzerland, Germany:Springer, 2014. 313-321
[4]	Agrawal S, Sanjay S. FRPSO:fletcher-reeves based particle swarm optimization for multimodal function optimization. Soft Computing, 2014, 18(11):2227-2243 doi: 10.1007/s00500-013-1196-2
[5]	Qu B Y, Suganthan P N, Liang J J. Differential evolution with neighborhood mutation for multimodal optimization. IEEE Transactions on Evolutionary Computation, 2012, 16(5):601-614 doi: 10.1109/TEVC.2011.2161873
[6]	Basak A, Das S, Tan K C. Multimodal optimization using a biobjective differential evolution algorithm enhanced with mean distance-based selection. IEEE Transactions on Evolutionary Computation, 2013, 17(5):666-685 doi: 10.1109/TEVC.2012.2231685
[7]	Pang C Y, Li X, Liu H, Wang Y F, Hu B Q. Applying ant colony optimization to search all extreme points of function. In:Proceedings of the 5th IEEE Conference on Industrial Electronics and Applications. Taichung, China:IEEE, 2010. 1517-1521
[8]	Dasgupta B, Divya K, Mehta V K, Deb K. RePAMO:recursive perturbation approach for multimodal optimization. Engineering Optimization, 2013, 45(9):1073-1090 doi: 10.1080/0305215X.2012.725050
[9]	Vidya R C, Phaneendra H D, Shivakumar M S. Quantum algorithms and hard problems. In:Proceedings of 5th IEEE International Conference on Cognitive Informatics. Washington, DC, USA:IEEE, 2006. 783-787
[10]	王鹏.云计算的关键技术与应用实例.北京:人民邮电出版社, 2010. 168-194 Wang Peng. The Key Technology and Application Examples of Cloud Computing. Beijing:People's Posts and Telecommunications Press, 2010. 168-194
[11]	王鹏, 黄焱, 任超, 郭又铭.多尺度量子谐振子高维函数全局优化算法.电子学报, 2013, 41(12):2468-2473 http://www.cnki.com.cn/Article/CJFDTOTAL-DZXU201312023.htm Wang Peng, Huang Yan, Ren Chao, Guo You-Ming. Multi-Scale quantum harmonic oscillator for high-dimensional function global optimization algorithm. Acta Electronica Sinica, 2013, 41(12):2468-2473 http://www.cnki.com.cn/Article/CJFDTOTAL-DZXU201312023.htm
[12]	王鹏, 黄焱.多尺度量子谐振子优化算法物理模型.计算机科学与探索, 2015, 9(10):1271-1280 http://www.cnki.com.cn/Article/CJFDTOTAL-KXTS201510014.htm Wang Peng, Huang Yan. Physical model of multi-scale quantum harmonic oscillator optimization algorithm. Journal of Frontiers of Computer Science and Technology, 2015, 9(10):1271-1280 http://www.cnki.com.cn/Article/CJFDTOTAL-KXTS201510014.htm
[13]	肖黎彬, 王鹏, 陈磊, 郭又铭.量子谐振子优化算法.计算机应用, 2013, 32(S2):1-4, 44 http://www.cnki.com.cn/Article/CJFDTOTAL-JSJY2012S2000.htm Xiao Li-Bin, Wang Peng, Chen Lei, Guo You-Ming. Quantum harmonic oscillator optimization algorithm. Journal of Computer Applications, 2013, 32(S2):1-4, 44 http://www.cnki.com.cn/Article/CJFDTOTAL-JSJY2012S2000.htm
[14]	Mallat S G. A theory for multiresolution signal decomposition:the wavelet representation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1989, 11(7):674-693 doi: 10.1109/34.192463
[15]	左斌, 胡云安, 施建洪.极值搜索算法的研究与进展.海军航空工程学院学报, 2006, 21(6):611-617 http://www.cnki.com.cn/Article/CJFDTOTAL-HJHK200606003.htm Zuo Bin, Hu Yun-An, Shi Jian-Hong. Research and development of extremum seeking algorithm. Journal of Naval Aeronautical Engineering Institute, 2006, 21(6):611-617 http://www.cnki.com.cn/Article/CJFDTOTAL-HJHK200606003.htm

施引文献

期刊类型引用(11)

1.	王治和，常筱卿，杜辉. 基于万有引力的自适应近邻传播聚类算法. 计算机应用. 2021(05): 1337-1342 . 百度学术
2.	邱保志，张瑞霖，李向丽. 基于过滤模型的聚类算法. 控制与决策. 2020(05): 1091-1101 . 百度学术
3.	征察，吉立新，高超，李邵梅，吴翼腾. 基于成对约束的偏标记数据消歧算法. 自动化学报. 2020(07): 1367-1377 . 本站查看
4.	钱雪忠，王卫涛. 多维空间可调整的近邻传播聚类算法. 计算机科学与探索. 2019(01): 116-127 . 百度学术
5.	曹愈远，张博文，李艳军. AP聚类改进免疫算法用于航空发动机故障诊断. 航空动力学报. 2019(08): 1795-1804 . 百度学术
6.	刘璧钺，赵章焰. 基于改进LSD和AP聚类的路径边缘识别策略. 图学学报. 2019(05): 915-924 . 百度学术
7.	刘自豪，张斌，祝宁，唐慧林. 基于改进AP聚类算法的自学习应用层DDoS检测方法. 计算机研究与发展. 2018(06): 1236-1246 . 百度学术
8.	赵昱，陈琴，苏一丹，陈慧姣. 基于邻域相似度的近邻传播聚类算法. 计算机工程与设计. 2018(07): 1883-1888 . 百度学术
9.	王卫涛，钱雪忠，曹文彬. 自适应参数调整的近邻传播聚类算法. 小型微型计算机系统. 2018(06): 1305-1311 . 百度学术
10.	李晓庆，唐昊，司加胜，苗刚中. 面向混合属性数据集的改进半监督FCM聚类方法. 自动化学报. 2018(12): 2259-2268 . 本站查看
11.	陈雷，肖创柏，禹晶，王真理，李学良. 基于相似性传播聚类与主成分分析的断层识别方法. 石油地球物理勘探. 2017(04): 826-833+627-628 . 百度学术