基于优化算法量子动力学框架的势垒估计准则

doi:10.11772/j.issn.1001-9081.2023040553

《计算机应用》唯一官方网站 ›› 2024, Vol. 44 ›› Issue (4): 1180-1186.DOI: 10.11772/j.issn.1001-9081.2023040553

所属专题：先进计算

基于优化算法量子动力学框架的势垒估计准则

陈雅琴¹, 王鹏¹^,²()

^1.西南民族大学计算机科学与工程学院，成都 610225
^2.中国科学院成都计算机应用研究所，成都 610213

收稿日期:2023-05-09 修回日期:2023-07-19 接受日期:2023-07-25 发布日期:2023-12-04 出版日期:2024-04-10
通讯作者: 王鹏
作者简介:陈雅琴（1998—），女，内蒙古乌兰察布人，硕士研究生，CCF会员，主要研究方向：量子启发式算法、高性能计算
王鹏（1975—），男，四川乐山人，教授，博士，CCF高级会员，主要研究方向：量子理论、量子启发式算法、智能计算、高性能计算。
基金资助:
西南民族大学研究生创新型科研项目(ZY2023987)

Potential barrier estimation criterion based on quantum dynamics framework of optimization algorithm

Yaqin CHEN¹, Peng WANG¹^,²()

^1.School of Computer Science and Engineering，Southwest Minzu University，Chengdu Sichuan 610225，China
^2.Chengdu Institution of Computer Application，Chinese Academy of Sciences，Chengdu Sichuan 610213，China

Received:2023-05-09 Revised:2023-07-19 Accepted:2023-07-25 Online:2023-12-04 Published:2024-04-10
Contact: Peng WANG
About author:CHEN Yaqin， born in 1998， M. S. candidate. Her research interests include quantum heuristic algorithms， high performance computing.
Supported by:
Innovative Scientific Research Project for Postgraduates of Southwest Minzu University(ZY2023987)

摘要/Abstract

摘要：

量子动力学框架（QDF）是在优化算法量子动力学模型下得到的具有代表性和普遍意义的优化算法的基本迭代过程，差解接受是避免优化算法陷入局部最优、解决算法早熟问题的一种重要机制。为了在QDF中引入差解接受机制，以量子动力学模型为基础将差解视为粒子运动过程中遇到的势垒，利用量子隧道效应中的透射系数计算粒子穿透该势垒的概率，从而得到量子动力学模型下的差解接受准则：势垒估计准则（PBEC）。PBEC与势垒高度和宽度、粒子的质量均有关系，比经典的Metropolis接受准则更能全面地估计优化算法采样时遇到差解时的行为。实验结果表明，基于PBEC的QDF算法相较于基于Metropolis接受准则的QDF算法，在求解函数过程中算法跳出局部最优的能力更强、搜索效率更高，表明PBEC在量子优化算法中是一种可行且有效的差解接受机制。

关键词: 优化算法, 差解接受机制, 透射系数, 势垒估计准则, Metropolis接受准则

Abstract:

Quantum Dynamics Framework （QDF） is a basic iterative process of optimization algorithm with representative and universal significance， which is obtained under the quantum dynamics model of optimization algorithm. Differential acceptance is an important mechanism to avoid the optimization algorithm falling into local optimum and to solve the premature convergence problem of the algorithm. In order to introduce the differential acceptance mechanism into the QDF， based on the quantum dynamics model， the differential solution was regarded as a potential barrier encountered in the process of particle motion， and the probability of particles penetrating the potential barrier was calculated by using the transmission coefficient in the quantum tunneling effect. Thus， the differential acceptance criterion of quantum dynamics model was obtained： Potential Barrier Estimation Criterion （PBEC）. PBEC was related to the height and width of the potential barrier and the quality of the particles. Compared with the classical Metropolis acceptance criterion， PBEC can comprehensively estimate the behavior of the optimization algorithm when it encounters the differential solution during sampling. The experimental results show that， the QDF algorithm based on PBEC has stronger ability to jump out of the local optimum and higher search efficiency than the QDF algorithm based on Metropolis acceptance criterion， and PBEC is a feasible and effective differential acceptance mechanism in quantum optimization algorithms.

Key words: optimization algorithm, differential acceptance mechanism, transmission coefficient, potential barrier estimation criterion, Metropolis acceptance criterion

中图分类号:

TP301.6

陈雅琴, 王鹏. 基于优化算法量子动力学框架的势垒估计准则[J]. 计算机应用, 2024, 44(4): 1180-1186.

Yaqin CHEN, Peng WANG. Potential barrier estimation criterion based on quantum dynamics framework of optimization algorithm[J]. Journal of Computer Applications, 2024, 44(4): 1180-1186.

图/表 10

图1 粒子发生势垒隧穿过程示意图

Fig. 1 Schematic diagram of barrier tunneling process of particles

表1 4个测试函数的函数名、表达式和定义域

Tab. 1 Names， expressions， and definition domains of four test functions

函数名	类型	表达式	定义域
Ackley	多峰	$f 1 = - 20 e x p - 0.2 1 d ∑ i = 1 d x i 2 - e x p 1 d ∑ i = 1 d c o s (2 π x i) + 20 + e$	$- 32.77,32.77$
Griewank	多峰	$f 2 = 1 4 000 ∑ i = 1 d x i 2 - ∏ i = 1 d c o s x i / i + 1$	$- 100,100$
Lévy	多峰	$f 3 = s i n 2 (π ω 1) + ∑ i = 1 d - 1 (ω i - 1) 2 [1 + 10 s i n 2 (π ω i + 1)] + (ω d - 1) 2 [1 + s i n 2 (2 π ω d)]$	$- 10,10$
Sphere	单峰	$f 4 = ∑ i = 1 d x i 2$	$- 5.12,5.12$

表1 4个测试函数的函数名、表达式和定义域

Tab. 1 Names， expressions， and definition domains of four test functions

函数名	类型	表达式	定义域
Ackley	多峰	$f 1 = - 20 e x p - 0.2 1 d ∑ i = 1 d x i 2 - e x p 1 d ∑ i = 1 d c o s (2 π x i) + 20 + e$	$- 32.77,32.77$
Griewank	多峰	$f 2 = 1 4 000 ∑ i = 1 d x i 2 - ∏ i = 1 d c o s x i / i + 1$	$- 100,100$
Lévy	多峰	$f 3 = s i n 2 (π ω 1) + ∑ i = 1 d - 1 (ω i - 1) 2 [1 + 10 s i n 2 (π ω i + 1)] + (ω d - 1) 2 [1 + s i n 2 (2 π ω d)]$	$- 10,10$
Sphere	单峰	$f 4 = ∑ i = 1 d x i 2$	$- 5.12,5.12$

图2 f1基于两种接受准则的函数值的收敛曲线和PBEC的差解接受概率曲线

Fig. 2 Convergence curves of function value based on two acceptance criteria and differential acceptance probability curve of PBEC for f1

图3 f2基于两种接受准则的函数值的收敛曲线和PBEC的差解接受概率曲线

Fig. 3 Convergence curves of function value based on two acceptance criteria and differential acceptance probability curve of PBEC for f2

图4 f3基于两种接受准则的函数值的收敛曲线和PBEC的差解接受概率曲线

Fig. 4 Convergence curves of function value based on two acceptance criteria and differential acceptance probability curve of PBEC for f3

图5 f4基于两种接受准则的函数值的收敛曲线和PBEC的差解接受概率曲线

Fig. 5 Convergence curves of function value based on two acceptance criteria and differential acceptance probability curve of PBEC for f4

图6 f1随维度变化的函数最优解和搜索时间

Fig. 6 Function optimal solution and search time of f1 varying with dimension

图7 f2随维度变化的函数最优解和搜索时间

Fig. 7 Function optimal solution and search time of f2 varying with dimension

图8 f3随维度变化的函数最优解和搜索时间

Fig. 8 Function optimal solution and search time of f3 varying with dimension

图9 f4随维度变化的函数最优解和搜索时间

Fig. 9 Function optimal solution and search time of f4 varying with dimension

参考文献 24

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. 10.1063/1.1699114
2	KIRKPATRICK S， GELATT C D， Jr， VECCHI M P. Optimization by simulated annealing［J］. Science， 1983， 220（4587）： 671-680. 10.1126/science.220.4598.671
3	郭茂祖，王亚东，孙华梅，等. 基于Metropolis准则的Q-学习算法研究［J］. 计算机研究与发展， 2002， 39（6）： 684-688.
	GUO M Z， WANG Y D， SUN H M， et al. Research on Q-learning algorithm based on Metropolis criterion［J］. Journal of Computer Research and Development， 2002， 39（6）： 684-688.
4	田启川，潘泉，王峰，等. 基于Metropolis准则的BP神经网络学习算法研究［J］. 自动化技术与应用， 2003， 22（5）： 15-17. 10.3969/j.issn.1003-7241.2003.05.005
	TIAN Q C， PAN Q， WANG F， et al. Research on learning algorithm of BP neural network based on the Metropolis criterion［J］. Techniques of Automation and Applications， 2003， 22（5）： 15-17. 10.3969/j.issn.1003-7241.2003.05.005
5	林敏，刘必雄，林晓宇. 带Metropolis准则的混合离散布谷鸟算法求解旅行商问题［J］. 南京大学学报（自然科学）， 2017， 53（5）： 972-983.
	LIN M， LIU B X， LIN X Y. Hybrid discrete cuckoo search algorithm with Metropolis criterion for traveling salesman problem［J］. Journal of Nanjing University （Natural Science）， 2017， 53（5）： 972-983.
6	HASTINGS W K. Monte Carlo sampling methods using Markov chains and their applications［J］. Biometrika， 1970， 57（1）： 97-109. 10.2307/2334940
7	CHIB S， GREENBERG E. Understanding the Metropolis-Hastings algorithm［J］. The American Statistician， 1995， 49（4）： 327-335. 10.1080/00031305.1995.10476177
8	ROBERT C P， CASELLA G. Metropolis-Hastings algorithms［M］// Introducing Monte Carlo Methods with R. New York： Springer， 2010： 167-197. 10.1007/978-1-4419-1576-4_6
9	GROVER L K. A fast quantum mechanical algorithm for database search［C］// Proceedings of the 28th Annual ACM Symposium on Theory of Computing. New York： ACM， 1996： 212-219. 10.1145/237814.237866
10	BUHRMAN H， CLEVE R， WIGDERSON A. Quantum vs. classical communication and computation［C］// Proceedings of the 30th Annual ACM Symposium on Theory of Computing. New York： ACM， 1998： 63-68. 10.1145/276698.276713
11	HRADIL Z. Quantum-state estimation［J］. Physical Review A， 1997， 55： R1561. 10.1103/physreva.55.r1561
12	HRADIL Z， ŘEHÁČEK J， FIURÁŠEK J， et al. 3 maximum-likelihood methodsin quantum mechanics ［M］// Quantum State Estimation. Heidelberg： Springer Berlin， 2004： 59-112. 10.1007/978-3-540-44481-7_3
13	SUZUKI J， YANG Y， HAYASHI M. Quantum state estimation with nuisance parameters［J］. Journal of Physics A： Mathematical and Theoretical， 2020， 53： 453001. 10.1088/1751-8121/ab8b78
14	曾谨言. 量子力学教程［M］. 3版. 北京：科学出版社， 2014： 15-46.
	ZENG J Y. Course of Quantum Mechanics［M］. 3rd ed. Beijing： Science Press， 2014： 15-46.
15	HUDEDAGADDI D P， TRIPATHY B K. Quantum inspired computational intelligent techniques in image segmentation［M］// Quantum Inspired Computational Intelligence： Research and Applications. ［S.l.］： Morgan Kaufmann， 2017： 233-258. 10.1016/b978-0-12-804409-4.00007-3
16	DENG W， SHANG S， CAI X， et al. An improved differential evolution algorithm and its application in optimization problem［J］. Soft Computing， 2021， 25： 5277-5298. 10.1007/s00500-020-05527-x
17	王鹏，陈雅琴，辛罡，等. 优化算法的量子动力学探讨［J］. 西南民族大学学报（自然科学版）， 2021， 47（3）： 288-296. 10.11920/xnmdzk.2021.03.008
	WANG P， CHEN Y Q， XIN G， et al. A brief study on quantum dynamics of optimization algorithm［J］. Journal of Southwest Minzu University （Natural Science Edition）， 2021， 47（3）： 288-296. 10.11920/xnmdzk.2021.03.008
18	WICK G C. Properties of Bethe-Salpeter wave functions［J］. Physical Review， 1954， 96（4）： 1124-1134. 10.1103/physrev.96.1124
19	王鹏，王方. 量子视角下的智能优化算法综述［J］. 电子科技大学学报， 2022， 51（1）： 1-15. 10.12178/1001-0548.2021345
	WANG P， WANG F. Overview of intelligent optimization algorithms from the perspective of quantum［J］. Journal of University of Electronic Science and Technology of China， 2022， 51（1）： 1-15. 10.12178/1001-0548.2021345
20	FINNILA A B， GOMEZ M A， SEBENIK C， et al. Quantum annealing： a new method for minimizing multidimensional functions［J］. Chemical Physics Letters， 1994， 219（5/6）： 343-348. 10.1016/0009-2614(94)00117-0
21	XIN G， WANG P. Exploring superposition state in multi-scale quantum harmonic oscillator algorithm［J］. Applied Soft Computing， 2021， 107： 107398. 10.1016/j.asoc.2021.107398
22	CORANA A， MARCHESI M， MARTINI C， et al. Minimizing multimodal functions of continuous variables with the “simulated annealing” algorithm — Corrigenda for this article is available here［J］. ACM Transactions on Mathematical Software， 1987， 13（3）： 262-280. 10.1145/29380.29864
23	HOLLAND J H. Adaptation in Natural and Artificial Systems ［M］. Cambridge： MIT Press， 1975.
24	BERTONI A， DORIGO M. Implicit parallelism in genetic algorithms［J］. Artificial Intelligence， 1993， 61（2）： 307-314. 10.1016/0004-3702(93)90071-i

[1]	力尚龙, 刘建华, 贾鹤鸣. 融合多狩猎协调策略的爬行动物搜索算法[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2818-2828.
[2]	杨乐, 张达敏, 何庆, 邓佳欣, 左锋琴. 改进猎人猎物优化算法在WSN覆盖中的应用[J]. 《计算机应用》唯一官方网站, 2024, 44(8): 2506-2513.
[3]	高培根, 锁斌. 基于加权犹豫模糊集的实验设计与分阶段PSO-Kriging建模[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 2144-2150.
[4]	郑志强, 段海滨. 基于有限忍耐度鸽群优化的无人机近距空战机动决策[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1401-1407.
[5]	赵楷文, 王鹏, 童向荣. 基于双阶段搜索的约束进化多任务优化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1415-1422.
[6]	韦修喜, 彭茂松, 黄华娟. 基于多策略改进蝴蝶优化算法的无线传感网络节点覆盖优化[J]. 《计算机应用》唯一官方网站, 2024, 44(4): 1009-1017.
[7]	唐睿, 岳士博, 张睿智, 刘川, 庞川林. UAV协助下非正交多址接入使能的数据采集系统中能效优化机制[J]. 《计算机应用》唯一官方网站, 2024, 44(4): 1209-1218.
[8]	杜晓昕, 周薇, 王浩, 郝田茹, 王振飞, 金梅, 张剑飞. 智能算法的亚群优化策略综述[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 819-830.
[9]	郭玲玲, 李志强, 段孟环. 量子近似优化算法在精确覆盖问题中的应用[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 849-854.
[10]	任帅, 纪元法, 孙希延, 韦照川, 林子安. 基于改进灰狼优化与支持向量回归的滑坡位移预测[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 972-982.
[11]	王震, 张珊珊, 邬斌扬, 苏万华. 基于自适应粒子群优化算法的串联复合涡轮储能优化策略[J]. 《计算机应用》唯一官方网站, 2024, 44(2): 611-618.
[12]	刘勇, 杨锟. 新能源汽车电池回收网点竞争选址模型及算法[J]. 《计算机应用》唯一官方网站, 2024, 44(2): 595-603.
[13]	彭鹏, 倪志伟, 朱旭辉, 陈千. 改进萤火虫群算法协同差分隐私的干扰轨迹发布[J]. 《计算机应用》唯一官方网站, 2024, 44(2): 496-503.
[14]	余家宸, 杨晔. 基于裁剪近端策略优化算法的软机械臂不规则物体抓取[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3629-3638.
[15]	欧云, 周恺卿, 尹鹏飞, 刘雪薇. 双收敛因子策略下的改进灰狼优化算法[J]. 《计算机应用》唯一官方网站, 2023, 43(9): 2679-2685.

基于优化算法量子动力学框架的势垒估计准则

Potential barrier estimation criterion based on quantum dynamics framework of optimization algorithm

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 24

相关文章 15

编辑推荐

Metrics