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

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

通信学报 ›› 2016, Vol. 37 ›› Issue (9): 68-74.doi: 10.11959/j.issn.1000-436x.2016179

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

黄焱¹,王鹏²(),程琨³,刘峰⁴

¹ 淮阴师范学院计算机科学与技术学院，江苏淮安 223300
² 西南民族大学计算机科学与技术学院，四川成都 610225
³ 中国科学院成都计算机应用研究所，四川成都 610041
⁴ 成都信息工程大学并行计算实验室，四川成都 610225

出版日期:2016-09-25 发布日期:2016-09-28
基金资助:
国家自然科学基金资助项目;模式识别与智能信息处理四川省高校重点实验室开放基金资助项目

Parallelism of multi-scale quantum harmonic oscillator algorithm

Yan HUANG¹,Peng WANG²(),Kun CHENG³,Feng LIU⁴

¹ School of Computer Science and Technology,Huaiyin Normal University,Huaian 223300,China
² School of Computer Science and Technology,Southwest University for Nationalities,Chengdu 610225,China
³ Chengdu Institute of Computer Application,Chinese Academy of Sciences,Chengdu 610041,China
⁴ Parallel Computing Lab,Chengdu University of Information Technology,Chengdu 610225,China

Online:2016-09-25 Published:2016-09-28
Supported by:
The National Natural Science Foundation of China;Sichuan Key Laboratory Open Foundationof Pattern Recognition and Intelligent Information Processing

摘要/Abstract

摘要：

多尺度量子谐振子优化算法(MQHOA,multi-scale quantum harmonic oscillator algorithm)是一种利用量子谐振子波函数构造的新的智能算法，采样运算是MQHOA算法的基本运算单元和主要运算量，采样运算的独立性赋予MQHOA算法内在并行性。通过对MQHOA算法群体参数和采样参数进行实验，确定算法的并行粒度并提出多尺度量子谐振子并行算法（MQHOA-P,multi-scale quantum harmonic oscillator parallel algorithm）。在由10个计算节点构成的集群上对6种标准测试函数进行实验，通过改变计算节点数、函数维数和采样参数测试MQHOA-P算法的加速比，实验结果表明，MQHOA-P算法具有良好的加速比和扩展性，可以在大规模集群中部署、运行。

关键词: 多尺度量子谐振子优化算法, 算法并行性, 加速比, 并行粒度, 函数优化

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

黄焱,王鹏,程琨,刘峰. 多尺度量子谐振子优化算法的并行性研究[J]. 通信学报, 2016, 37(9): 68-74.

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.

图/表 9

图1

表1

MQHOA算法的运行时间"

编号	名称	单位运行时间	运算次数
$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}$	—

表1

图2

图3

图4

表2

测试函数"

函数表达式	定义域	最优解位置	全局最小值单机执行时间/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

表2

表3

表4

表5

参考文献 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.

节点数	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

在线阅读

PDF下载

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 9

参考文献 9

相关文章 2

Metrics

推荐阅读 0

[1]	王鹏,黄焱. 具有能级稳定过程的MQHOA优化算法[J]. 通信学报, 2016, 37(7): 79-86.
[2]	范朝冬,章兢,易灵芝. M-精英协同进化分子动理论优化算法[J]. 通信学报, 2015, 36(7): 144-152.