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

• 先进计算 • 上一篇    下一篇

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

袁亚男1,2, 王鹏3, 刘峰3   

  1. 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 Yanan1,2, WANG Peng3, LIU Feng3   

  1. 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

摘要: 多尺度量子谐振子算法(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)

中图分类号: