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

陆志君; 安俊秀; 王鹏

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

计量
- 文章访问数: 2504
- HTML全文浏览量: 180
- PDF下载量: 976
- 被引次数: 0
出版历程
- 收稿日期: 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