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

doi:10.11772/j.issn.1001-9081.2023040553

Journal of Computer Applications ›› 2024, Vol. 44 ›› Issue (4): 1180-1186.DOI: 10.11772/j.issn.1001-9081.2023040553

Special Issue: 先进计算

• Advanced computing • Previous Articles Next Articles

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)

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

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

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

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

Abstract

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

摘要：

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

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

CLC Number:

TP301.6

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.

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

Figures/Tables 10

Fig. 1 Schematic diagram of barrier tunneling process of particles

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$

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$

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

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

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

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

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

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

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

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

References 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]	Kaiwen ZHAO, Peng WANG, Xiangrong TONG. Two-stage search-based constrained evolutionary multitasking optimization algorithm [J]. Journal of Computer Applications, 2024, 44(5): 1415-1422.
[2]	Xiuxi WEI, Maosong PENG, Huajuan HUANG. Node coverage optimization of wireless sensor network based on multi-strategy improved butterfly optimization algorithm [J]. Journal of Computer Applications, 2024, 44(4): 1009-1017.
[3]	Lingling GUO, Zhiqiang LI, Menghuan DUAN. Application of quantum approximate optimization algorithm in exact cover problems [J]. Journal of Computer Applications, 2024, 44(3): 849-854.
[4]	Bona XUAN, Jin LI, Yafei SONG, Zexuan MA. Malicious code classification method based on improved MobileNetV2 [J]. Journal of Computer Applications, 2023, 43(7): 2217-2225.
[5]	Lin SUN, Jinxu HUANG, Jiucheng XU. Feature selection for imbalanced data based on neighborhood tolerance mutual information and whale optimization algorithm [J]. Journal of Computer Applications, 2023, 43(6): 1842-1854.
[6]	Zhihui GAO, Meng HAN, Shujuan LIU, Ang LI, Dongliang MU. Survey of high utility itemset mining methods based on intelligent optimization algorithm [J]. Journal of Computer Applications, 2023, 43(6): 1676-1686.
[7]	Heming JIA, Shanglong LI, Lizhen CHEN, Qingxin LIU, Di WU, Rong ZHENG. Remora optimization algorithm based on chaotic host switching mechanism [J]. Journal of Computer Applications, 2023, 43(6): 1759-1767.
[8]	Haitao TANG, Hongjun WANG, Tianrui LI. Discriminative multidimensional scaling for feature learning [J]. Journal of Computer Applications, 2023, 43(5): 1323-1329.
[9]	Junxing XIANG, Yonghong WU. Hybrid salp swarm and butterfly optimization algorithm combined with neighborhood centroid opposition-based learning [J]. Journal of Computer Applications, 2023, 43(3): 820-826.
[10]	Lei TIAN, Lina GE. Advertising recommendation algorithm based on differential privacy [J]. Journal of Computer Applications, 2023, 43(11): 3346-3350.
[11]	MA Yanfang, ZHANG Wen, LI Zongmin, YAN Fang, GUO Lingyun. Two-echelon location-routing model and algorithm for waste recycling considering obnoxious effect [J]. Journal of Computer Applications, 2023, 43(1): 289-298.
[12]	ZHENG Sai, LI Tianrui, HUANG Wei. Federated learning algorithm for communication cost optimization [J]. Journal of Computer Applications, 2023, 43(1): 1-7.
[13]	ZHAO Peiwen, ZHANG Damin, ZHANG Linna, ZOU Chengcheng. Bald eagle search optimization algorithm with golden sine algorithm and crisscross strategy [J]. Journal of Computer Applications, 2023, 43(1): 192-201.
[14]	Jun CHEN, Qing HE, Shouyu LI. Archimedes optimization algorithm based on golden Levy guidance mechanism [J]. Journal of Computer Applications, 2022, 42(9): 2807-2815.
[15]	Xinming ZHANG, Shaochen WEN, Shangwang LIU. Differential disturbed heap-based optimizer [J]. Journal of Computer Applications, 2022, 42(8): 2519-2527.

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

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 24

Related Articles 15

Recommended Articles

Metrics