多尺度量子谐振子算法性能分析

doi:10.11772/j.issn.1001-9081.2015.06.1600

计算机应用 ›› 2015, Vol. 35 ›› Issue (6): 1600-1604.DOI: 10.11772/j.issn.1001-9081.2015.06.1600

多尺度量子谐振子算法性能分析

袁亚男^1,2, 王鹏³, 刘峰³

1. 中国科学院成都计算机应用研究所, 成都 610041;
2. 中国科学院大学, 北京 100049;
3. 成都信息工程学院并行计算实验室, 成都 610225

收稿日期:2014-12-31 修回日期:2015-04-01 发布日期:2015-06-12
通讯作者: 袁亚男(1990-),男,安徽阜阳人,硕士研究生,主要研究方向:云计算、量子算法;1029246630@qq.com
作者简介:王鹏(1975-),男,成都乐山人,教授,博士,CCF会员,主要研究方向:云计算、并行计算、量子算法;刘峰(1987-),男,河南郑州人,硕士研究生,主要研究方向:云计算、量子算法。
基金资助:
国家自然科学基金资助项目(60702075);广东省科技厅高新技术产业化科技攻关项目(2011B010200007);四川省青年科学基金资助项目(09ZQ026-068);成都市科技局创新发展战略研究项目(11RXYB016ZF)。

Performance analysis of multi-scale quantum harmonic oscillator algorithm

YUAN Yanan^1,2, WANG Peng³, LIU Feng³

1. Chengdu Institute of Computer Application, Chinese Academy of Sciences, Chengdu Sichuan 610041, China;
2. University of Chinese Academy of Sciences, Beijing 100049, China;
3. Parallel Computing Laboratory, Chengdu University of Information Technology, Chengdu Sichuan 610225, China

Received:2014-12-31 Revised:2015-04-01 Published:2015-06-12

摘要/Abstract

摘要： 多尺度量子谐振子算法(MQHOA)具有良好的全局收敛性以及自适应性。为分析研究MQHOA求解精度与速度具体性能,通过求解整数非线性规划问题,将MQHOA和采用量子行为模型且已被广泛使用的量子粒子群优化(QPSO)算法以及改进的随机平均最好位置量子粒子群(QPSO-RM)算法进行理论模型和实验对比,仿真实验中,MQHOA对7组无约束整数规划问题的求解均取得100%成功率且求解速度整体上略快于QPSO和QPSO-RM;对2组有约束整数规划问题的求解速度比QPSO、QPSO-RM稍慢,但MQHOA的求解成功率均为100%,高于后两者;通过和QPSO、QPSO-RM的收敛过程进行对比,MQHOA更快更早于对比算法收敛到全局最优解。实验结果表明:MQHOA能有效地适应整数规划求解问题,能够避免陷入局部最优解的情况从而获得全局最优解,并在求解精度和收敛速度上均优于对比算法。

关键词: 多尺度量子谐振子算法, 全局收敛, 量子行为模型, 量子粒子群优化算法, 整数非线性规划

Abstract: Multi-scale Quantum Oscillator Harmonic Algorithm (MQHOA) has good characteristics of global convergence and adaptability. For analyzing the specific performance of MQHOA on solution precision and speed, the comparisons of theoretical models and experiments were completed among the MQHOA, the classic Quantum Particle Swarm Optimization (QPSO) algorithm adopting the quantum-behaved model and having been widely used, and the QPSO with Random Mean best position (QPSO-RM) through solving the integer nonlinear programming problems. In simulation experiments, MQHOA achieved 100% success rate in solving seven unconstrained integer nonlinear programming problems, and was faster than QPSO and QPSO-RM in most cases. MQHOA was a little slower than QPSO and QPSO-RM in solving the two constrained integer nonlinear programming problems, but could obtain 100% success rate which was higher than the latter. Through the comparison of the convergence process of QPSO, QPSO-RM, MQHOA was faster and earlier on converging to the global optimal solution. The experimental results show that MQHOA can effectively adapt to solving the integer programming problems, and can avoid falling into the local optimal solution so as to obtain the global optimal solution. MQHOA is better than the contrast algorithms of QPSO and QPSO-RM in accuracy and convergence rate.

Key words: Multi-Scale Quantum Harmonic Oscillator Algorithm (MQHOA), global convergence, quantum-behaved model, Quantum-behaved Particle Swarm Optimization (QPSO) algorithm, Integer Nonlinear Programming (INP)

中图分类号:

TP301.6

袁亚男, 王鹏, 刘峰. 多尺度量子谐振子算法性能分析[J]. 计算机应用, 2015, 35(6): 1600-1604.

YUAN Yanan, WANG Peng, LIU Feng. Performance analysis of multi-scale quantum harmonic oscillator algorithm[J]. Journal of Computer Applications, 2015, 35(6): 1600-1604.

参考文献

[1] SUN J, FANG W, WU X, et al. Quantum-behaved particle swarm optimization: the principle and application [M]. Beijing: Tsinghua University Press, 2011: 36-37.(孙俊, 方伟, 吴小俊, 等.量子行为粒子群优化:原理及其应用[M].北京:清华大学出版社, 2011:36-37.)
[2] COLORNI A, DORIGO M, MANIEZZO V. Distributed optimization by ant colonies [C]//Proceedings of the First European Conference on Artificial Life. Amsterdam: Elsevier Publishing, 1991: 134-142.
[3] COLORNI A, DORIGO M, MANIEZZO V. An investigation of some properties of an ant algorithm [C]//PPSN 1992: Proceeding of the Parallel Problem Solving from Nature Conference. Amsterdam: Elsevier Publishing, 1992: 509-520.
[4] KENNEDY J. Particle swarm optimization [M]//Encyclopedia of Machine Learning. New York: Springer US, 2010: 760-766.
[5] WANG P. The key technology and application examples of cloud computing [M]. Beijing: Posts and Telecom Press, 2010: 168-194.(王鹏.云计算的关键技术与应用实例[M].北京:人民邮电出版社, 2010:168-194.)
[6] WANG P, QIAN X. Simulated harmonic oscillator algorithm and its global convergence analysis [J]. Computer Engineering, 2013, 39(3): 209-212.(王培崇, 钱旭.模拟谐振子算法及其全局收敛性分析[J].计算机工程, 2013, 39(3):209-212.)
[7] NI L, DUAN C, ZHONG H. Multi-project scheduling based on simulated harmonic oscillator algorithm [J]. Journal of Computer Applications, 2011, 31(9): 2559-2562.(倪霖, 段超, 钟辉.基于模拟谐振子算法的多项目调度[J].计算机应用, 2011, 31(9):2559-2562.)
[8] YU H, WANG H, LI Z, et al. Optimized K-means clustering algorithm based on simulated harmonic oscillator [J]. Computer Engineering and Applications, 2012, 48(30): 122-127.(于海涛, 王慧强, 李梓, 等.基于模拟谐振子的优化K-means聚类算法[J].计算机工程与应用, 2012, 48(30):122-127.)
[9] 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.(王鹏, 黄焱, 任超, 等.多尺度量子谐振子高维函数全局优化算法[J].电子学报, 2013, 41(12):2468-2473.)
[10] LIU J, XU W, SUN J. Quantum-behaved particle swarm optimization for integer programming [J]. Application Research of Computers, 2007, 24(3): 79-81.(刘静, 须文波, 孙俊.基于量子粒子群算法求解整数规划[J].计算机应用研究, 2007, 24(3):79-81.)
[11] CHEN B. The theory and algorithm of optimization [M]. Beijing: Tsinghua University Press, 2005: 431-433.(陈宝林.最优化理论与算法[M].北京:清华大学出版社, 2005:431-433.)
[12] SUN J, FENG B, XU W. Particle swarm optimization with particles having quantum behavior [C]//CEC 2004: Proceedings of the 2004 IEEE Congress on Evolutionary Computation. Piscataway: IEEE, 2004, 1: 325-331.
[13] SUN J, WU X, PALADE V, et al. Convergence analysis and improvements of quantum-behaved particle swarm optimization [J]. Information Sciences, 2012, 193: 81-103.
[14] MENG Z, HU Q, YANG X. A method of non-linear penalty function for solving integer programming and mixed integer programming [J]. Control and Decision, 2002, 17(3): 310-314.(孟志青, 胡奇英, 杨晓琪.一种求解整数规划与混合整数规划非线性罚函数方法[J].控制与决策, 2002, 17(3):310-314.)
[15] LUO W, YU J, HUANG J. Bionic algorithm for solving nonlinear integer programming [J]. Computer Engineering and Applications, 2008, 44(7): 57-59.(罗伟强, 于建涛, 黄家栋. 一种求非线性整数规划最优解的仿生算法[J].计算机工程与应用, 2008, 44(7):57-59.)

多尺度量子谐振子算法性能分析

Performance analysis of multi-scale quantum harmonic oscillator algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 10

编辑推荐

Metrics

[1]	王德志, 王鹏. 无能级稳定判据的多尺度量子谐振子算法[J]. 计算机应用, 2019, 39(9): 2641-2645.
[2]	韩虎, 王鹏, 程琨, 李波. 基于多尺度量子谐振子算法的云计算任务调度[J]. 计算机应用, 2017, 37(7): 1888-1892.
[3]	武巍, 邹杰. 基于改进教学算法的无人机航路规划[J]. 计算机应用, 2016, 36(9): 2626-2630.
[4]	李瑞国, 张宏立, 王雅. 基于量子粒子群优化算法的新型正交基神经网络分数阶混沌时间序列单步预测[J]. 计算机应用, 2015, 35(8): 2227-2232.
[5]	张前图, 房立清, 赵玉龙. 具有Levy飞行特征的双子群果蝇优化算法[J]. 计算机应用, 2015, 35(5): 1348-1352.
[6]	宋玉坚叶春明黄佐钘. 多资源均衡优化的布谷鸟算法[J]. 计算机应用, 2014, 34(1): 189-193.
[7]	吴涛严余松陈曦. 基于随机评价机制的量子粒子群优化算法及其参数控制[J]. 计算机应用, 2013, 33(10): 2815-2818.
[8]	罗晓清吴小俊. 结合熵主成分变换与优化方法的遥感图像融合[J]. 计算机应用, 2013, 33(02): 468-475.
[9]	陆秋琴杨少敏黄光球. 求解非线性方程组的元胞自动机方法及其全局收敛性证明[J]. 计算机应用, 2012, 32(12): 3283-3286.
[10]	陈伟冯斌孙俊 . 基于QPSO算法的RBF神经网络参数优化仿真研究[J]. 计算机应用, 2006, 26(8): 1928-1931.