多尺度量子谐振子优化算法的并行性研究

doi:10.11959/j.issn.1000-436x.2016179

Abstract

Abstract:

MQHOA was a novel intelligent algorithm constructed by quantum harmonic oscillator's wave function.Sampling was the basic operation and main computational burden of MQHOA.The independence of sampling operation constructs MAHOA’s parallelism.Parallel granularity was obtained by experiments of group parameter and sampling parameter,and MQHOA-P was proposed.Experiments were done in a cluster of ten nodes on six standard test functions.By changing node number,function dimension and sampling parameter,experiments of MQHOA-P’s speed-up ratio were done.The experimental results show the good performance of MQHOA-P’s speed-up ratio and expansibility.MQHOA-P can be deployed and run on multiple nodes in a large-scale cluster.

Key words: MQHOA, algorithm parallelization, speedup, parallel granularity, functional optimization

Yan HUANG,Peng WANG,Kun CHENG,Feng LIU. Parallelism of multi-scale quantum harmonic oscillator algorithm[J]. Journal on Communications, 2016, 37(9): 68-74.

Figures/Tables 9

编号	名称	单位运行时间	运算次数
$A_{1}$	初始化	$C_{1}$	1
$A_{2}$	迭代运算	$C_{2}$	$a_{1}$
$A_{3}$	尺度判断	$C_{3}$	$a_{1}$
$A_{4}$	尺度收缩	$C_{4}$	$a_{2}$
$A_{5}$	精度判断	$C_{5}$	$a_{3}$
$A_{6}$	输出结果	$C_{6}$	1
$B_{1}$	采样运算	$D_{1}$	$a_{1} k$
$B_{2}$	单位采样	$D_{2}$	$a_{1} k m$
$B_{3}$	节点通信	$D_{3}$	—

函数表达式	定义域	最优解位置	全局最小值单机执行时间/s
$f_{1} (x) = 10 n + \sum_{i = 1}^{n} (x_{i}^{2} - 10 \cos (2 π x_{i}))$	$- 600 \leq x_{i} \leq 600, i = 1, \dots, n$	(0.000 000,0.000 000)	0.000 000351.965 333
$f_{2} (x) = \sum_{i = 1}^{n} \frac{x_{i}^{2}}{40000} - \prod_{i = 1}^{n} \cos (\frac{x_{i}}{\sqrt{i}}) + 1$	$- 5.12 \leq 5.12 x_{i} \leq, i = 1, \dots, n$	(0.000 000,0.000 000)	0.000 0006.427 333
$f_{3} (x) = \sin^{2} (π y_{1}) + \sum_{i = 1}^{n - 1} [{(y_{i} - 1)}^{2} (1 + 10 \sin^{2} (π y_{i} + 1))] +$ ${(y_{n} - 1)}^{2} (1 + 10 \sin^{2} (2 π y_{n})), y_{i} = 1 + \frac{x_{i} - 1}{4}$	$- 10 \leq x_{i} \leq 10, i = 1, \dots, n$	(?1.306 853,?1.424 845)	?176.137 5780.523 667
$f_{4} (x) = {\sum_{i = 1}^{n} x_{i}^{2} + (\sum_{i = 1}^{n} 0.5 i x_{i})}^{2} + {(\sum_{i = 1}^{n} 0.5 i x_{i})}^{4}$	$- 5 \leq x_{i} \leq 10, i = 1, \dots, n$	(0.000 000,0.000 000)	0.000 0000.400 667
$f_{5} (x) = \sum_{i = 1}^{n} i x_{i}^{2}$	$- 10 \leq x_{i} \leq 10, i = 1, \dots, n$	(0.000 000,0.000 000)	0.000 0000.355 000
$f_{6} (x) = \sum_{i = 1}^{n} x_{i}^{2}$	$- 5.12 \leq 5.12 x_{i} \leq, i = 1, \dots, n$	(0.000 000,0.000 000)	0.000 0000.350 000

References 9

[1]	王鹏, 黄焱, 任超 ,等. 多尺度量子谐振子高维函数全局优化算法[J]. 电子学报, 2013,41(12): 2468-2473. WANG P , HUANG Y , REN C ,et al. Multi-scale quantum harmonic oscillator for high-dimensional function global optimization algorithm[J]. Acta Electronica Sinica, 2013,41(12): 2468-2473.
[2]	ZABARAS N , YANG G Z . A functional optimization formulation and implementation of an inverse natural convection problem[J]. Computer Methods in Applied Mechanics and Engineering, 1997,144(3): 245-274.
[3]	PAPADIMITRIOU C H , STEIGLITZ K . Combinatorial optimization:algorithms and complexity[M]. Courier Corporation, 1998.
[4]	LAI J Z C , HUANG T J , LIAW Y C . A fast k-means clustering algorithm using cluster center displacement[J]. Pattern Recognition, 2009,42(11): 2551-2556.
[5]	王鹏, 黄焱 . 多尺度量子谐振子优化算法物理模型[J]. 计算机研究与探索, 2015,9(10): 1271-1280. WANG P , HUANG Y . Physical model of multi-scale quantum harmonic oscillator optimization algorithm[J]. Journal of Frontiers of Computer Science & Technology, 2015,9(10): 1271-1280.
[6]	袁亚男, 王鹏, 刘峰 . 多尺度量子谐振子算法性能分析[J]. 计算机应用, 2015,35(6): 1600-1604. YUAN Y N , WANG P , LIU F . Performance analysis of multi-scale quantum harmonic oscillator algorithm[J]. Journal of Computer Applications, 2015,35(6): 1600-1604.
[7]	燕京京 . 基于量子谐振子模型的聚类中心选取算法[D]. 成都:中国科学院成都计算机应用研究所, 2015. YAN J J . Clustering center selecting algorithm based on quantum harmonic oscillator model[D]. Chengdu:Chengdu Institute of Computer Application, 2015.
[8]	王鹏, 黄焱 . 具有能级稳定过程的 MQHOA 优化算法[J]. 通信学报, 2016,37(7): 79-86. WANG P , HUANG Y . MQHOA algorithm with energy level stabilizing process[J]. Journal on Communications, 2016,37(7): 79-86.
[9]	GRAMA A , GUPTA A , KARYPIS G . Introduction to parallel computing:design and analysis of algorithms[M]. Redwood City,CA: Benjamin/Cummings Publishing CompanyPress, 1994.

Metrics

Recommended 0

No Suggested Reading articles found!

节点数	f₁	f₂	f₃	f₄	f₅	f₆
2	1.406 597 68	1.713 275	1.959 493	1.944 946	1.924 994	1.901 553
3	2.285 842 56	2.082 543	2.832 287	2.793 387	2.755 718	2.901 710
4	3.263 174 93	3.147 938	3.695 499	3.568 996	2.743 106	3.580 870
5	3.442 467 67	3.483 784	4.415 762	4.345 221	4.373 072	4.319 634
6	3.463 230 28	4.224 470	5.613 564 1	5.578 059	4.747 294	5.434 101
7	3.726 798 11	4.386 515	6.138 731 7	6.172 003	5.335 081	6.002 582
8	3.408 043 96	4.185 896	6.082 875 1	6.053 333	5.877 689	6.278 014
9	3.393 770 63	4.479 221	6.461 573 0	6.420 042	6.276 037	7.126 693
10	3.410 369 47	4.590 488	6.430 997 5	6.800 474	6.728 722	7.102 575

维数	f₃	f₄	f₅	f₆
3	2.880 649	2.711 77	3.530 218	2.665 889
4	2.976 71	2.859 233	3.134 647	2.866 137
5	2.881 833	2.961 212	3.297 564	3.009 759
6	3.129 49	2.951 289	2.566 698	3.039 434
7	3.128 264	3.103 655	3.456 517	3.149 114
8	3.164 913	3.060 944	3.373 018	2.866 696
10	3.344 578	3.170 757	3.660 677	3.250 646
15	3.526 671	3.608 939	3.914 432	3.396 572

m	k=80	k=100	k=150	k=200	k=250	k=300
200	3.450 087	3.065 583	2.792 84	3.026 471	3.051 19	3.394 296
300	3.442 412	3.621 03	3.667 513	3.198 545	3.192 759	3.448 752
400	3.508 801	3.943 25	3.809 55	3.591 404	3.392 792	3.771 928
500	3.421 67	4.062 604	3.777 593	3.746 629	3.535 984	3.379 141
600	3.945 592	4.080 465	4.115 259	3.793 128	3.669 308	3.510 004

Parallelism of multi-scale quantum harmonic oscillator algorithm

RichHTML

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

Figures/Tables 9

References 9

Related Articles 1

Metrics

Recommended 0