多尺度量子谐振子优化算法物理模型.pdf

王鹏 黄焱 多尺度量子谐振子优化算法物理模型 J 计算机科学与探索 2015 9 10 1271 1280 ISSN 1673 9418CODEN JKYTA8 Journal of Frontiers of Computer Science and Technology 1673 9418 2015 09 10 1271 10 doi 10 3778 j issn 1673 9418 1502003 E mail fcst http www ceaj org Tel 86 10 89056056 多尺度量子谐振子优化算法物理模型 王鹏 1 黄 焱 2 3 1 成都信息工程学院 并行计算实验室 成都 610225 2 中国科学院 成都计算机应用研究所 成都 610041 3 中国科学院大学 北京 100049 PhysicalModelofMulti ScaleQuantumHarmonicOscillatorOptimizationAlgorithm WANG Peng1 HUANG Yan2 3 1 Parallel Computing Lab Chengdu University of Information Technology Chengdu 610225 China 2 Chengdu Institute of ComputerApplication ChineseAcademy of Sciences Chengdu 610041 China 3 University of ChineseAcademy of Sciences Beijing 100049 China Corresponding author E mail wp002005 WANG Peng HUANG Yan Physical model of multi scale quantum harmonic oscillator optimization algo rithm Journal of Frontiers of Computer Science and Technology 2015 9 10 1271 1280 Abstract Multi scale quantum harmonic oscillator optimization algorithm MQHOA is a novel algorithm inspired by the physical model of harmonic oscillator and the probability interpretation of quantum harmonic oscillator s wave function This paper demonstrates the uncertainty relationship between global searching accuracy and local searching accuracy and defines the wave function of MQHOA according to quantum model Quantum harmonic oscillator convergence and multi scale convergence are nested and are the basic convergence processes of MQHOA to gradually approach the global optimal solution The comparison experiments with quantum behaved particle swarm optimization QPSO and simulated annealing SA on 15 benchmark functions show that MQHOA has good performance in adaptability stability and accuracy when tackling with function global optimization algorithm Key words multi scale quantum harmonic oscillator optimization algorithm MQHOA optimization algorithm uncertainty relationship Gauss random number The National Natural Science Foundation of China under Grant No 60702075 国家自然科学基金 the Postdoctoral Science Foun dation of China under Grant Nos 20090451420 20070410385 中国博士后科学基金 the Youth Science Technology Foundation of Sichuan Province under Grant No 09ZQ026 068 四川省青年科学基金 Received 2015 01 Accepted 2015 03 CNKI网络优先出版 2015 04 14 Journal of Frontiers of Computer Science and Technology计算机科学与探索2015 9 10 1引言 利用物理模型构造优化算法是一种非常有效的 算法构造方法 其中最著名的优化算法是基于1953 年提出的Metropolis选择准则 1 构造的模拟退火算法 simulated annealing SA 后来Kirkpatrick等人将其 成功地应用于组合优化问题 2 3 模拟退火算法通过 多次等温迭代使算法达到低温条件下的平衡态 但 是该算法计算时间较长 控制参数较多 并且对参数 敏感 其参数的变化本身就是一个需要进行研究的 课题 4 因此在实际应用时多与其他优化算法结合使 用 基于量子理论的退火算法 量子退火算法 quantum annealing QA 于20世纪90年代被提出 5 并引起了物理学界和计算机科学界的广泛关注 文 献 6 分析了量子退火算法在DMC diffusion Monte Carlo 过程中通过量子隧道效应跳出局部最优区域 的过程 对于量子隧道效应的利用是不少量子算法 实现全局优化的重要方法 文献 7 对比了经典退火 算法和量子退火算法对谐振子势能 双阱势能和抛 物线势能函数的优化性能 文献 8 利用Ising模型这 一描述相互作用粒子最简单的模型 并利用材料在 温度降低后系统从混乱到有序 在外加磁场的作用 下呈现出顺磁性这一原理构造了优化算法 量子波 函数的概率解释与优化算法随机求解过程的相似 性 使得基于量子物理模型的优化算法成为未来构 造新的优化算法的一个重要研究方向 量子退火算 法利用了量子波函数的概率特性 物理模型较为完 备 但是模型的数学过程复杂 算法实现困难 并且 算法实际性能也未能得到有效的证实 9 因此应用 并不广泛 10 近年来还出现了一种新的量子粒子群 算法 quantum behaved particle swarm optimization QPSO 11 12 该算法利用 势阱下的量子波函数构造 粒子进化公式 通过不断减小特征长度逐步实现局 域化的新解采样 从而达到算法收敛的目的 该算 法需要人为指定迭代次数 并且由于使用的Bi t U 势阱对应的波函数收敛速度过快 对算法求解精度 造成了影响 文献 13 使用了谐振子势阱构造算法 但是该算法并未有效利用量子谐振子的波函数完整 模型 对于多个函数的测试表明算法的稳定性和精 度都不高 2010年作者在文献 14 中提出了利用谐振子构 造算法的初步设想 当时称为模拟谐振子算法SHO 算法提出后引起了一些研究者的关注 文献 15 提出 用模拟谐振子算法来解决资源受限的多项目调度问 题 通过对比模拟谐振子算法和粒子群算法所得结 果 验证了前者的有效性 文献 16 基于模拟谐振子 提出了一种优化K means聚类算法 该算法克服了 K means聚类算法对初始聚类中心选择敏感的问题 能够获得全局最优的聚类划分 文献 17 利用有限马 尔科夫链理论对模拟谐振子算法的解状态矩阵变化 进行了分析 证明了当运算时间趋于无穷时 算法会 逐渐收敛于全局最优解 文献 18 将模拟谐振子算法 应用于求解整数规划问题 通过实验结果说明了该算 法在问题规模较大时具有高质量的搜索效率和精度 文献 19 给出了多尺度量子谐振子优化算法 multi scale quantum harmonic oscillator optimization algorithm MQHOA 的完整实现方法 并成功应用于高维函数 优化问题 对于15种标准测试函数进行实验均能以 指定的精度 0 000 001 100 的概率获得全局最优解 摘要 依据谐振子物理模型及量子谐振子波函数的概率解释构造了一种新的全局优化算法 多尺度量子 谐振子优化算法 multi scale quantum harmonic oscillator optimization algorithm MQHOA 定义了算法的 波函数 并利用算符方法证明了全局搜索精度和局部搜索精度之间的测不准关系 指出算法必须包含量子谐 振子收敛和多尺度收敛两个嵌套的基本收敛过程 才能实现对全局最优解的逐步逼近 通过与量子粒子群算 法和模拟退火算法对15种标准测试函数进行实验比对 证明了MQHOA在求解函数全局优化问题时具有更好 的适应性 稳定性和精确性 关键词 多尺度量子谐振子优化算法 MQHOA 优化算法 测不准关系 高斯随机数 文献标志码 A中图分类号 TP18 1272 王鹏 等 多尺度量子谐振子优化算法物理模型 MQHOA算法利用谐振子运动的物理含义与优 化问题之间的对应关系 根据量子谐振子波函数的 概率解释构造出了一种新的具有简单数学结构和明 确物理含义的优化算法 本文重点对这一算法的物 理模型进行研究 并针对复杂函数优化问题将 MQHOA算法的结果与SA算法和QPSO算法的结果 进行对比 2MQHOA算法流程和数学描述 2 1MQHOA算法的基本流程 MQHOA算法的基本过程如下 一维目标函数 步骤1 初始化k m min 在目标函数定义域范 围内随机生成k个初始采样中心位置ki 并设定初始 尺度 s MAX MIN MIN MAX 为目标函数搜索 定义域 步骤2 按k个高斯分布N ki 2 s 在目标函数定 义域各生成m个采样位置 根据采样位置对应的目 标函数值从新生成的k m个采样位置中选出k个较 优的采样位置更新ki 步骤3 如果k个较优采样位置ki之间的标准差 k满足 k s 则返回步骤2 QHO迭代 步骤4 如果 s min 则尺度减半为 s s 2 并返 回步骤2 M迭代 步骤5 依据目标函数取k个采样中心位置ki中 的最优位置为结果输出 其中k为群体参数 m为采样参数 算法在初 始化时通常将目标函数定义域作为初始采样尺度开 始迭代 s为s尺度下高斯采样的 值 它在进行尺 度迭代时逐次减半 直到搜索尺度 s小于预设的最 小尺度 min时停止 min事实上就是求解精度 文中 通常取为0 000 001 迭代进行时当前k个较优解采 样位置的标准差为 k i 1 k ki k 2 MQHOA算法的收敛过程包含两个迭代步骤 一 个是在同一尺度下的量子谐振子收敛过程 quantum harmonic oscillator QHO收敛 一个是多尺度收敛 过程 multi scale M收敛 QHO收敛过程实现对搜 索空间的逐步收缩定位 M收敛过程实现对采样精 度的逐步提高 MQHOA算法从数学的角度也可以 认为是一种多尺度高斯邻域采样群体算法 对高维 函数进行优化时只需要对各个方向的坐标分别执行 QHO收敛过程 待所有坐标方向上的QHO迭代都分 别达到收敛条件后 再减小尺度进入下一轮QHO收 敛过程 2 2MQHOA算法流程的数学描述 MQHOA算法迭代时的数学过程非常简洁 最基 本的迭代动作就是对目标函数利用k个以ki为中心 位置的高斯分布分别进行m次随机采样 这种采样 方式是非均匀采样中的重要性采样法 importance sampling 采用重要性采样法可以使重要区域的采 样密度相对较高 靠近较优解的采样密度相对较高 从而大大地提高采样效率 减小采样次数 可以用 随机变量来描述每一次的迭代过程 算法在尺度 s下每次迭代过程中 在目标函数 f x 的定义域构造k个独立的随机变量X1 X2 Xk Xi服从参数为ki和 s的高斯分布 Xi N ki 2 s 分别对k个随机变量Xi独立生成m个样本 高斯邻 域采样 每次迭代在目标函数定义域上的样本总数 为k m个 计算这k m个定义域样本点所对应的 目标函数值 选择其中对应目标函数值最优的前k个 样本点更新之前的ki 从而使下一次迭代时k个独立 的随机变量X1 X2 Xk所服从的概率密度函数 N ki 2 s 也同时得到更新 直到k 个概率密度函数的 中心位置ki的标准差 k s时结束尺度 s下的 QHO迭代 尺度减半进入下一个尺度的QHO迭代 算法的整个采样过程和收敛过程都是以高斯函数为 基础 数学结构简洁 控制参数较少 通常不需要太 多人为的设定 3MQHOA算法过程的物理模型 3 1MQHOA算法与经典谐振子物理模型的 对应关系 自然界中任何体系在平衡位置附近的小振动 1273 Journal of Frontiers of Computer Science and Technology计算机科学与探索2015 9 10 如分子振动 晶格振动 原子核表面振动 都可以被 分解为一维简谐振动 因此将优化问题在最优解附 近的搜索运动与一维谐振子在平衡位置附近的简谐 振动相比较 质量为m的弹簧振子所受到的恢复力F x Kx 其中K为简谐力强度参数 x为谐振子离开平衡位 置的位移 根据牛顿第二定理 有 md 2x dt2 Kx 1 这一方程的通解为经典谐振子的运动方程 x Asin t 其中 K m A和 分别是振幅和位 相 根据一维谐振子受力与势能之间的关系F x V x x 可以得到一维谐振子的势能曲线V x 1 2 Kx2 势能在平衡位置处获得最小值 如图1所示 在算法的物理模型中谐振子的振动 范围与目标函数的求解定义域对应 横坐标x 谐振 子的运动受到势阱V x 的约束 谐振子的平衡位置 x0和势阱V x 最低点都对应于目标函数f x 最优解 通常是求目标函数的最小值 的位置x0 f xmin 谐振子一旦偏离平衡位置就会受到指向平衡位置回 复力F的作用 谐振子在振动过程中能量逐步下 降 最终会在平衡位置x0停下 在算法每次迭代时 将保留采样到的当前最优的k个采样位置 从而将谐 振子振动的平衡位置在每次迭代时都修正为当前最 优解x0出现概率最大的位置 从而使算法体系的运 行方向一直指向当前最优解方向 并受到以当前最 优解位置为势阱最低点的谐振子势阱V x 的约束 这样就能确保算法收敛时能在最优解的位置 谐振 子的平衡位置 停止 对于复杂的目标函数只用一种谐振子势能是无 法进行逼近的 需要用多个不同K值的谐振子势阱 对复杂函数的最小值位置进行逼近 K较小时势阱 对谐振子的约束小 对最小值位置只能粗略定位 K 较大时势阱将谐振子的运动约束在较小的范围 可 以精确地定位最小值位置 如图2所示K2 K1 K1 对应的势阱V1 x 1 2 K1 x x1 2最低点为靠近理论最 小值的位置x1 而K2对应的势阱V2 x 1 2 K2 x x0 2 最低点为理论最小值的位置x0 MQHOA算法的多 尺度机制正是利用了不同K值的谐振子势阱对目标 函数的最小值进行逐步逼近 3 2MQHOA算法与量子谐振子物理模型的 对应关系 将谐振子势能代入薛定谔方程解出的能级和波 函数概率密度如下 第n个能级的能量函数 En n 1 2 h 波函数概率密度 n x 2 1 2nn m 1 2 e 2x2 2 Hn x 2 h 其中Hn x 为Hermite多项式 能量较低的3个波函数如下 V x 1 2 Kx2 f x x0 x F K Fig 1Correspondence between harmonic oscillator model and optimization problem 图1谐振子模型与优化问题的对应关系 V2 x 1 2 K2 x x0 2 V1 x 1 2 K1 x x1 2 f x f x x0 x1 x O Fig 2Harmonic oscillator potential approaching to the minimum of objective function 图2谐振子势能对目标函数最小值的逼近 1274 王鹏 等 多尺度量子谐振子优化算法物理模型 0 x 1 4 e 2x2 2 2 1 x 2 1 4 xe 2x2 2 3 2 x 1 1 4 2 2 2x2 1 e 2x2 2 4 可以证明谐振子的波函数是相互正交的 即 m x n x dx mn 其中 2 mK C K C h 为常数 波函数概率密度随能级的变化曲线如图3所示 在量子力学中波函数具有概率含义 波函数代 表相关粒子出现在该位置的概率 图3为随着能级 的变化谐振子概率密度的变化过程 从图3中可以 观察到 谐振子的波函数从高能态向基态的变化是 一个逐渐收敛的过程 从高能态多个高斯概率函数 的叠加 逐步收敛到基态单一高斯分布的稳定状态 0 x 1 4 e 2x2 2 量子谐振子波函数中的x为偏离 平衡位置的距离 在MQHOA算法中将目标函数的 最优解出现的位置定为平衡位置 使谐振子的振动 总是以最优解位置为中心进行 这种情况下谐振子 波函数中的x将替换为x x0 x0为目标函数的最优 解在定义域上的位置 此时的基态波函数变为 0 x 1 4 e 2 x x0 2 2 其他能级波函数变化以此类推 根据 这一物理模型算法在每次迭代时均需要保留当前较 好解的位置 并更新采样时的概率分布 量子谐振子波函数中 和K的关系如下式 2 1 2 1 C K 5 K与 成反比关系 根据K值与目标函数最小 值位置的逼近关系 在多尺度迭代中K应逐步增 大 因此在MQHOA算法中 值是以2的倍数逐步 减少的 从而实现对目标函数从全局到局部的多尺 度搜索 3 3波函数 定义MQHOA算法在尺度 s下的波函数为k个 以ki为中心的高斯概率密度函数的迭加 QHO x i 1 k 1 2 s e x ki 2 2 2 s 6 MQHOA算法中QHO迭代时的波函数 QHO x 也是概率波函数 它近似代表了目标函数最优解出 现位置在目标函数定义域上的概率密度 MQHOA 算法的核心就是使最优解的位置一直位于波函数的 概率密度分布函数的中心 从而使算法以最大的概 率获得全局最优解 图4中算法波函数 QHO x 随迭 代的变化过程直观地反映了这一过程 图 4 是两个变量的 Griewank 函数在 s 0 625 定义域为 10 10 时的波函数收敛过程 从上到下 分别为在该尺度迭代次数n分别为0 200 400 600 902时的波函数 第一列为波函数在搜索空间中的等 高投影 第二列为波函数在搜索空间中的投影 这些 投影和量子波函数一样都具有概率含义 波函数的 具 体 图 像 与 测 试 函 数 有 关 图 4 a1 b1 为 s 0 625时的初始态 高能态 这时高斯采样区域 近似随机分布搜索空间中 随着迭代的进行采样区 域会收敛到多个局部最优区域 如图4 a2 a3 a4 b2 b3 b4 最后高斯采样区域会在全局 最优解附近迭加聚集 如图4 a5 b5 为 s 0 625 时的基态波函数 当收敛到基态时 k s 搜索区 域被缩小到全局最优解附近标准差为 s的高斯采样 区域 同时采样函数的尺度被改变为 s 2 进入下一 个尺度的QHO收敛过程 En E10 E9 E8 E7 E6 E5 E4 E3 E2 E1 E0 x x 2 O Fig 3Variation of probability density of harmonic oscillator wave function with energy level 图3谐振子波函数概率密度随能级变化图 1275 Journal of Frontiers of Computer Science and Technology计算机科学与探索2015 9 10 3 4量子隧道效应 MQHOA算法避免陷入局部最优区域的机制利 用了量子隧道效应 如图5所示 a b 为全局最优区 域 在尺度 s时落入局部最优区域的一个高斯采样 N ki 2 s 实线 在每次迭代过程中都会有一定的概 率跳出局部最优区域 从而使采样中心位置进入全 局最优区域 虚线 根据图5中所示 N ki 2 s 的采样位置在每次迭 代中进入全局最优区域的采样个数Nk i 可以由下式 计算 Nk i m a b 1 2 s e x ki 2 2 2 s dx 7 k个采样区域在尺度 s迭代时依据量子隧道效 应落入全局最优区域的采样点数目N可以由波函数 计算得出 N m a b QHO x dx m a b i 1 k 1 2 s e x ki 2 2 2 s dx 8 MQHOA算法结构就是保证N值尽可能大 从 而使算法收敛于全局最优位置 3 5测不准原理 MQHOA算法的物理模型源于量子谐振子模型 因此也存在测不准关系 引理1 如果物理量A和B对应的算符分别为A 和B 算符A 和算符B 的对易式 commutator 为 A B A B B A 如果 A B 0 则认为算符A 和算 符B 对易 如果两个量A和B的算符A 和B 不对 易 则A和B不能被同时精确测定 物理量A和B的 误差 A和 B的绝对值乘积大于零 即 Fig 4Two dimensionQHO convergenceprocess s 0 625 图4二维QHO收敛过程 s 0 625 5 4 3 2 1 0 10 5 0 5 10 10 5 0 5 10 x y z 0 5 0 4 0 3 0 2 0 1 0 10 5 0 5 10 10 5 0 5 10 x y z QHO 1 2 1 0 0 8 0 6 0 4 0 2 0 10 5 0 5 10 10 5 0 5 10 x y z QHO 2 0 1 5 1 0 0 5 0 10 5 0 5 10 10 5 0 5 10 x y z QHO 3 2 1 0 10 5 0 5 10 10 5 0 5 10 x y z 10 50510 10 5 0 5 10 x y 10 50510 10 5 0 5 10 x y 10 50510 10 5 0 5 10 x y 10 50510 10 5 0 5 10 x y 10 50510 10 5 0 5 10 x y a1 n 0 2D b1 n 0 3D a2 n 200 2D b2 n 200 3D a3 n 400 2D b3 n 400 3D a4 n 600 2D b4 n 600 3D a5 n 902 2D b5 n 902 3D f x f x abx O Fig 5Quantum tunnel effect 图5量子隧道效应 1276 王鹏 等 多尺度量子谐振子优化算法物理模型 A 2 B 2 1 2 A B 9 QHO收敛过程中定义全局搜索物理量为l 相应 的算符和测量误差为l 和 l 局部搜索物理量为s 相应的算符和测量误差为 s 和 s 在函数优化问题 中 全局搜索的作用就是找到所有可能的局部最优 位置 对应的数学操作就是对目标函数f x 进行微 分并求出微分结果等于0的位置 因此函数全局搜 索算符l 可以表示为作用于目标函数f x 的微分操 作 即l d dx 而局部搜索就是找到目标函数最优值 所对应的准确位置x 这个x也可能是局部最优的位 置 于是局部搜索算符 s 可以表示为s x 将两个 算符的对易式作用于目标函数f x l s s l f x d dx x x d dx f x dxf x dx x df x dx x df x dx f x x df x dx f x 10 由此可得两个算符l 和 s 的对易 l s 1 根据引理1可得 l 2 s 2 1 2 l s 1 2 1 1 2 由此可以得到MQHOA算法的测不准关系定理 定理 算法测不准定理 单一尺度的QHO收敛 过程无法同时获得精确的全局搜索精度和局部搜索 精度 对于函数优化问题测不准关系是一个普遍适用 的定理 全局搜索精度和局部搜索精度对于优化算 法来说通常都是不能完全兼顾的 QHO收敛过程中 的测不准关系预言了MQHOA算法不能仅仅依靠单 一尺度下的QHO收敛过程获得全局最优解 单一尺 度的QHO收敛过程中最优解的宏观位置 全局搜索 和微观位置 局部搜索 是不能同时被精确测定的 测不准关系正好说明了MQHOA算法采用QHO收敛 过程和M收敛过程相互嵌套迭代的原因 这个做法 在其他基于物理模型的算法中也是非常常见的 如 SA算法通过降低温度实现搜索尺度的变化 QPSO 算法通过改变特征长度实现搜索尺度的变化 4MQHOA QPSO和SA算法性能的实验对比 为了验证MQHOA算法的性能 将MQHOA算 法与同样是基于物理模型构造的QPSO算法和SA算 法进行比对 为了公平起见3种算法均是在固定参数 条件下采用经典的基础算法 表1为MQHOA算法和QPSO算法对15种不同 的标准测试函数求最小值的对比实验 MQHOA算 法对于所有 15 种函数均采用相同的参数k 20 m 200 QPSO算法的收缩 扩张系数 取值区间为 1 0 0 5 群体参数 粒子数 m 80 最大迭代次数 基准测试函数情况 基准函数名 Griewank Matyas Easom Beale Bohachevsky Booth Sum square Levy Zakharov Schaffer Rastrigin Rosenbrock Dixon Price Sphere Ackley 变量数 2 4 2 2 2 2 2 2 10 2 10 2 10 2 2 5 2 4 2 4 2 10 2 10 MQHOA 实验次数 S1 30 28 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 S2 30 28 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 19 30 30 30 30 30 30 S3 30 28 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 19 30 30 30 30 30 30 t s 0 017 1 745 0 009 0 010 0 017 0 012 0 009 0 011 0 266 0 013 0 465 0 010 0 255 0 015 0 012 0 917 0 017 2 498 0 168 1 349 0 008 0 149 0 100 0 205 QPSO 实验次数 S1 30 17 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 S2 30 10 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 1 30 30 30 30 30 30 S3 11 0 30 30 30 30 30 30 30 30 30 30 30 2 30 19 30 0 30 23 30 30 30 30 t s 0 035 0 080 0 029 0 039 0 040 0 033 0 030 0 031 0 139 0 040 0 185 0 046 0 156 0 034 0 032 0 085 0 030 0 056 0 028 0 055 0 032 0 135 0 037 0 168 Table 1Experiment results comparison between MQHOAand QPSO 表1MQHOA和QPSO算法的实验结果对比 1277 Journal of Frontiers of Computer Science and Technology计算机科学与探索2015 9 10 为2 000次 QPSO算法的程序代码来自于文献 11 参数取值依据参考文献 12 表2为SA算法对15种标准函数求最小值的计 算结果 算法中采用高斯邻域法产生新解 等温过程 迭代次数为10 000次 降温速度为0 95 初始温度为 100 表中所有数据均是在相同的计算机软硬件系统 下 操作系统为Linux CPU为Intel CoreTMi5 4570S 主频为2 90 GHz 重复计算运行30次统计所得到的 值 变量的定义域均取 10 10 表头中S1 0 1 S2 0 001 S3 0 000 001 为算法逼近最优解的精度 如 S3 0 000 001表明求得的最优解位置每一维度的坐 标x与该测试函数理论最优解位置x0在小数点后5 位都是完全相同的 即 x x0 0 000 01 表中对应 的数据就是30次重复实验满足这一精度要求的实验 次数 表中的t为30次重复计算后每次计算平均需 要消耗的时间 对比表1和表2 3种算法在精度为0 1的较低精 度标准下对于大多数函数 对于Rosenbrock函数SA 未能获得全局最优解 均能获得全局最优解 MQHOA算法和QPSO算法在计算精确度和计算时 间上都远远胜过了SA的基础算法 同时SA算法参 数之间耦合性非常强 不容易找到一个合适的计算 参数 因此SA算法通常需要与遗传算法等其他算 法结合使用才能有较好的效果 MQHOA和QPSO 算法都具有群体算法的数学特征 这一点是其优于 基本SA算法的重要原因之一 对比表1中MQHOA算法和QPSO算法的结果 可以看到 目标函数变量个数为2时MQHOA算法的 计算速度和计算精度都要好于QPSO算法 当目标函 数的变量个数增加后MQHOA算法的计算速度会略 慢于QPSO算法 但计算精度仍然高于QPSO算法 特别是对于Rosenbrock函数 在0 000 001精度条件 下QPSO找到正确解的概率为0 而MQHOA算法在 30次实验中仍然有19次能正确地找到理论最优解 对于Griewank这类较为复杂的目标函数 MQHOA 算法明显表现出比 QPSO 算法更好的寻解能力 MQHOA算法通过对 min参数的指定可以精确地控 制寻解的精度 算法根据QHO和M两个收敛过程的 收敛条件自适应地控制迭代次数 几乎不需要人为地 对参数进行设定 而QPSO算法需要对迭代次数进 行人为设定 由于其过快的收敛速度 会导致在高维 函数优化和复杂函数优化问题中计算精度下降 表 1中对Griewank函数的优化 QPSO算法在两个变量 情况下就出现了无法获得高精度优化结果的问题 在对4个变量的Rosenbrock函数优化时完全无法获得 高精度最优解 对Schaffer Dixon Price函数的求解 也出现了类似的情况 而MQHOA算法针对不同 的函数和高维函数均能稳定地获得高精度解 MQHOA算法在对复杂函数和高维函数进行处理时 可以自适应地调整迭代次数以保证求解的精度 避 免算法早熟退出 这一点是QPSO算法和SA算法不 具备的 综合来看MQHOA算法控制参数和收敛条 件简单 通常不需要人为通过尝试来设定 收敛过程 由收敛条件根据目标函数进行自适应调整 在计算 速度和计算精度上取得了很好的折衷性能 基准测试函数情况 基准函数名 Griewank Matyas Easom Beale Bohachevsky Booth Sum square Levy Zakharov Schaffer Rastrigin Rosenbrock Dixon Price Sphere Ackley 变量数 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 SA 实验次数 S1 30 30 30 30 30 30 30 30 30 30 30 0 30 30 30 S2 11 5 0 8 30 22 27 20 17 10 30 0 15 20 30 S3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 t s 0 326 0 104 1 829 0 614 3 577 0 718 0 140 0 269 0 559 0 679 2 906 0 028 0 265 0 283 7 069 Table 2Experiment results of SA 表2SA算法的计算结果 1278 王鹏 等 多尺度量子谐振子优化算法物理模型 5结束语 MQHOA算法的物理模型直接来源于谐振子的 物理过程 在物理模型上不属于群体模型 但在具体 实现上与群体算法具有相似性 本文利用经典谐振 子和量子谐振子模型对MQHOA算法进行了分析和 研究 并证明了具有普遍意义的算法测不准原理 认 为单一尺度的量子谐振子迭代无法同时实现全局和 局部搜索精度 相比SA和QPSO算法 MQHOA算 法的计算收敛过程与物理模型之间的吻合度更高 MQHOA算法的整个收敛过程只需要不断地生成高 斯随机数 其两层收敛循环的收敛条件也是由k个高 斯中心的标准差所决定 通过M收敛过程收敛条件 的设定 算法可以精确地设定计算精度 因此 MQHOA算法的数学结构非常简洁 与其他两种重 要的基于物理模型的优化算法 QPSO算法和SA算 法 进行对比实验 证明了MQHOA算法具有良好的 稳定性 计算速度和计算精度 更重要的是MQHOA 算法的参数通常都不需要人为进行设定 面对复杂 目标函数和高维目标函数时算法能自动进行迭代调 整 从而保证精确获得全局最优解 由于MQHOA 算法所具有的优点 目前已引起部分研究者的注意 有望在函数优化 组合优化及其他应用领域获得广 泛的应用 References 1 Metropolis N Rosenbluth A W Rosenbluth M N et al Equation of state calculations by fast computing machines J The Journal of Chemical Physics 1953 21 6 1087 1092 2 Kirkpatrick S Gelatt C D Vecchi M P Optimization by sim mulated annealing J Science 1983 220 4598 671 680 3 Kirkpatrick S Toulouse G Configuration space analysis of travelling salesman problems J Journal de Physique 1985 46 8 1277 1292 4 Munakata T Nakamura Y Temperature control for simulated annealing J Physical Review E 2001 64 4 046127 5 Ghosh A Mukherjee S Quantum annealing and computa tion a brief documentary note J Science and Culture 2013 79 1 485 500 6 Finnila A Gomez M Sebenik C et al Quantum annealing a new method for minimizing multidimensional functions J Chemical Physics Letters 1994 219 5 343 348 7 Stella L Santoro G E Tosatti E Optimization by quantum annealing lessons from simple cases J Physical Review B 2005 72 1 014303 8 Brooke J Bitko D Aeppli G Quantum annealing of a disor dered magnet J Science 1999 284 5415 779 781 9 Du Weilin Li Bin Tian Yu Quantum annealing algorithms state of the art J Journal of Computer Research and Devel opment 2008 45 9 1501 1508 10 Marto k R Santoro G E Tosatti E Quantum annealing of the traveling salesman problem J Physical Review E 2004 70 5 057701 11 Sun Jun Quantum behaved particle swarm optimization principle and application M Beijing Tsinghua University Press 2011 12 Fang Wei Sun Jun Xie Zhenping et al Convergence analy sis of quantum behaved particle swarm optimization algo rithm and study on its control parameter J Acta Physica Sinica 2010 59 6 3686 3694 13 Feng Bin Xu Wenbo Quantum oscillator model of particle swarm system J Computer Engineering 2006 32 20 18 21 14 Wang Peng Key technology and application examples of cloud computing M Beijing Posts Telecom Press 2010 15 Zhong Hui Ni Duan Multi project scheduling based on simulated harmonic oscillator algorithm J Journal of Com puterApplications 2011 31 9 2559 2562 16 Yu Haitao Wang Huiqiang Li Zi et al Optimized K means clustering algorithm based on simulated harmonic oscillator J ComputerEngineering