智能优化算法的量子理论纲要

王鹏; 辛罡

doi:10.16383/j.aas.c190761

智能优化算法的量子理论纲要

doi: 10.16383/j.aas.c190761

王鹏^1,,
辛罡^{2, 3,}

1.
西南民族大学计算机科学与技术学院成都 610225
2.
中国科学院成都计算机应用研究所成都 610041
3.
中国科学院大学北京 100049

基金项目: 西南民族大学中央高校基本科研业务费专项资金项目(2020NYB18)资助

详细信息

作者简介:
王鹏：西南民族大学计算机科学与技术学院教授. 2001年获四川大学核技术及应用专业硕士学位. 2004年获中国科学院成都计算机应用研究所计算机软件与理论专业博士学位. 主要研究方向为量子理论, 量子启发式算法, 计算智能与高性能计算. 本文通信作者. E-mail: qhoalab@163.com

辛罡：中国科学院成都计算机应用研究所博士研究生. 2011年获德累斯顿工业大学微电子与固体电子专业硕士学位. 主要研究方向为量子启发式算法, 高性能计算. E-mail: xin_gang@vip.126.com

计量
- 文章访问数: 497
- HTML全文浏览量: 255
- PDF下载量: 218
- 被引次数: 0
出版历程
- 收稿日期: 2019-11-03
- 录用日期: 2020-02-07
- 网络出版日期: 2023-10-19
- 刊出日期: 2023-11-22

Quantum Theory of Intelligent Optimization Algorithms

WANG Peng^1
,,
XIN Gang^{2, 3
,}

1.
School of Computer Science and Technology, Southwest Minzu University, Chengdu 610225
2.
Chengdu Institute of Computer Application, Chinese Academy of Sciences, Chengdu 610041
3.
University of Chinese Academy of Sciences, Beijing 100049

Funds: Supported by Fundamental Research Funds for the Central Universities, Southwest Minzu University (2020NYB18)

More Information

Author Bio:
WANG Peng　Professor at the School of Computer Science and Technology, Southwest Minzu University. He received his master degree in nuclear technology and applications from Sichuan University in 2001 and Ph.D. degree in computer software and theory from Chengdu Institute of Computer Application, Chinese Academy of Sciences in 2004. His research interest covers quantum mechanics, quantum inspired algorithm, computational intelligence, and high performance computing. Corresponding author of this paper

XIN Gang　Ph.D. candidate at Chengdu Institute of Computer Application, Chinese Academy of Sciences. He received his master degree in microelectronics and solid state electronics from Dresden University of Technology, Germany in 2011. His research interest covers quantum inspired algorithm and high performance computing

摘要

摘要: 针对一些智能优化算法缺乏完备数学物理理论基础的现状, 利用优化问题和量子物理在概率意义上的相似性, 建立优化问题的薛定谔方程, 将优化问题转化为以目标函数为约束条件的基态波函数问题, 同时利用波函数定义了算法的能量、隧道效应和熵, 实现了以波函数为中心的优化问题量子模型. 这一纲要利用了量子物理完备的理论框架, 建立起了优化问题与量子理论广泛的内在联系. 从量子物理的角度回答了优化问题解的概率描述, 邻域采样函数的选择, 算法演化的过程设计, 多尺度过程的必要性等问题. 智能优化算法的量子理论纲要可以作为研究与构造算法的理论工具, 其有效性已得到初步验证.
- 优化问题 /
- 优化算法 /
- 量子理论 /
- 波函数 /
- 基态
Abstract: Many metaheuristics, which are based on the metaphor of natural phenomena, are lacking the support of a complete mathematical or physical theory. In this paper, the Schrödinger equation of optimization problems is proposed based on the basic probabilistic similarities between an optimization problem and a quantum system. It transforms the optimization problem into a quantum physics problem with the objective function as the constrained conditions. Meanwhile, the algorithm energy, quantum tunnel effect, and entropy are defined based on the probabilistic interpretation of the wave function. This wave function based quantum physical model establishes a comprehensive internal relationship between optimization problems and quantum theory, and theoretically answers the following questions: probabilistic description of solution of optimization problems, selection of neighborhood function, evolutionary process of optimization, necessity of multi-scale process, etc. Those quantum theories of intelligent optimization algorithm can be used as a theoretical means for the analysis of optimization systems. Its effectiveness has been preliminarily verified.
- Optimization problem /
- optimization algorithm /
- quantum theory /
- wave function /
- ground state

HTML全文

图 1 量子隧道效应示意图

Fig. 1 Schematic diagram of quantum tunneling effect

下载: 全尺寸图片幻灯片

表 1 PVADE, SPSO2011, QPSO, LoTFWA和MPSS-MQHOA在30维CEC2013测试集下平均误差和标准差的对比实验, 所有算法的终止条件为MaxFES = 300000, 所有实验独立重复51次

Table 1 Comparison of mean errors and standard deviations of PVADE, SPSO2011, QPSO, LoTFWA, MPSS-MQHOA, under 30D CEC2013 benchmark functions. The stopping condition for all schemes is set at MaxFES = 300000. The experiments are repeated 51 times individually

	PVADE		SPSO2011		QPSO		LoTFWA		MPSS-MQHOA
F.	Mean	Std.	Mean	Std.	Mean	Std.	Mean	Std.	Mean	Std.
1	0.00E + 00	0.00E + 00	0.00E + 00	0.00E + 00	0.00E + 00	0.00E + 00	0.00E + 00	0.00E + 00	0.00E + 00	0.00E + 00
2	4.24E + 04	2.74E + 04	1.06E + 05	4.90E + 04	1.90E + 07	7.65E + 06	2.13E + 06	7.21E + 05	8.96E + 05	2.14E + 05
3	1.39E + 06	4.58E + 06	5.64E + 07	8.68E + 07	3.98E + 08	8.77E + 08	3.94E + 07	7.23E + 07	3.01E + 06	3.21E + 06
4	1.11E + 02	9.05E + 01	1.97E + 03	7.77E + 02	1.20E + 04	2.77E + 03	7.03E + 03	1.97E + 03	1.69E + 04	3.56E + 03
5	1.12E − 04	3.35E − 04	4.72E − 04	3.75E − 05	1.77E − 05	1.51E − 05	1.60E − 02	1.41E − 02	2.40E − 03	3.61E − 04
AR. 1 ~ 5	1.20	1.60	2.40	2.20	3.20	3.20	3.20	3.20	3.00	2.80
6	4.73E + 01	2.49E + 01	1.46E + 01	1.86E + 01	3.87E + 01	1.95E + 01	1.94E + 01	1.25E + 01	2.42E + 01	2.18E + 01
7	7.33E + 00	5.53E + 00	4.32E + 01	1.44E + 01	4.79E + 01	1.57E + 01	5.40E + 01	1.23E + 01	2.63E + 01	1.04E + 01
8	2.09E + 01	4.64E − 02	2.09E + 01	6.31E − 02	2.10E + 01	4.03E − 02	2.09E + 01	6.20E − 02	2.09E + 01	6.50E − 02
9	1.05E + 01	2.37E + 00	2.37E + 01	4.41E + 00	2.55E + 01	8.37E + 00	1.55E + 01	2.03E + 00	1.59E + 01	1.78E + 00
10	5.36E − 01	6.07E − 01	2.47E − 01	1.32E − 01	2.86E + 00	1.61E + 00	5.60E − 02	2.89E − 02	4.48E − 02	3.76E − 02
11	6.12E + 01	1.07E + 01	6.96E + 01	2.36E + 01	1.66E + 02	1.97E + 01	6.59E + 01	1.47E + 01	3.41E + 01	9.77E + 00
12	1.01E + 02	1.53E + 01	5.65E + 01	1.52E + 01	2.04E + 02	1.49E + 01	7.71E + 01	1.64E + 01	3.36E + 01	8.56E + 00
13	1.22E + 02	1.59E + 01	1.19E + 02	2.76E + 01	2.03E + 02	1.21E + 01	1.45E + 02	2.62E + 01	7.36E + 01	1.69E + 01
14	3.20E + 03	3.77E + 02	4.34E + 03	7.89E + 02	6.20E + 03	5.36E + 02	2.69E + 03	3.13E + 02	2.57E + 03	3.32E + 02
15	5.29E + 03	3.90E + 02	4.30E + 03	5.99E + 02	7.25E + 03	3.07E + 02	2.81E + 03	3.89E + 02	2.50E + 03	3.16E + 02
16	2.32E + 00	3.06E − 01	1.74E + 00	3.06E − 01	2.50E + 00	2.78E − 01	6.74E − 02	2.44E − 02	1.36E − 01	3.84E − 02
17	9.39E + 01	1.24E + 01	1.32E + 02	3.20E + 01	2.36E + 02	1.61E + 01	6.60E + 01	1.05E + 01	5.56E + 01	5.96E + 00
18	1.67E + 02	1.13E + 01	1.20E + 02	1.65E + 01	2.42E + 02	1.42E + 01	6.82E + 01	1.01E + 01	5.55E + 01	6.94E + 00
19	6.48E + 00	2.62E + 00	6.95E + 00	3.36E + 00	1.76E + 01	1.74E + 00	3.48E + 00	7.68E − 01	2.24E + 00	5.63E − 01
20	1.34E + 01	1.93E + 00	1.30E + 01	1.94E + 00	1.24E + 01	4.08E − 01	1.32E + 01	9.99E − 01	1.36E + 01	1.04E + 00
21	3.26E + 02	8.62E + 01	3.35E + 02	6.63E + 01	2.86E + 02	7.88E + 01	1.98E + 02	1.41E + 01	3.02E + 02	3.46E + 01
22	2.53E + 03	5.87E + 02	3.97E + 03	8.07E + 02	6.37E + 03	4.79E + 02	3.08E + 03	3.59E + 02	3.07E + 03	4.17E + 02
23	5.21E + 03	4.82E + 02	4.32E + 03	7.14E + 02	7.25E + 03	3.01E + 02	3.30E + 03	4.26E + 02	3.32E + 03	5.49E + 02
24	2.24E + 02	1.23E + 01	2.46E + 02	9.15E + 00	2.46E + 02	9.01E + 00	2.43E + 02	9.81E + 00	2.19E + 02	4.58E + 00
25	2.49E + 02	2.12E + 01	2.77E + 02	9.40E + 00	2.59E + 02	8.05E + 00	2.80E + 02	8.07E + 00	2.66E + 02	1.12E + 01
26	2.49E + 02	6.12E + 01	2.69E + 02	7.02E + 01	2.96E + 02	6.60E + 01	2.00E + 02	3.48E − 02	2.00E + 02	3.55E − 02
27	5.21E + 02	8.32E + 01	7.31E + 02	1.03E + 02	7.52E + 02	1.03E + 02	7.21E + 02	1.15E + 02	5.38E + 02	4.34E + 01
28	2.73E + 02	1.80E + 02	3.22E + 02	1.57E + 02	3.93E + 02	3.18E + 02	2.84E + 02	5.47E + 01	3.00E + 02	8.96E − 09
AR. 6 ~ 28	2.87	3.43	3.35	4.13	4.48	3.04	2.43	2.30	1.87	2.09
AR. 1 ~ 28	2.57	3.11	3.18	3.79	4.25	3.07	2.57	2.46	2.07	2.21

下载: 导出CSV

表 2 优化算法与量子理论的对应关系

Table 2 The relationship between optimization algorithm and quantum theory

优化算法	量子理论	说明
优化问题的解	波函数$ \psi(x)$	优化问题的概率描述
优化问题	薛定鄂方程的约束条件	通过势阱等效将优化问题引入量子系统
优化系统的动态模型	含时薛定鄂方程	含时薛定鄂方程描述了随机搜索过程
多尺度过程	不确定性关系	通过算符的概念证明了多尺度过程的必要性
群体策略	波函数的叠加性	通过波函数的叠加性解释了算法种群的必要性
跳出局部最优	量子隧道效应	可以通过波函数来计算隧道效应概率
解的确定性	波函数熵	通过波函数定义优化算法的熵

下载: 导出CSV

参考文献(39)

[1]	Holland J H. Adaptation in Natural and Artificial Systems. Michigan: University of Michigan Press, 1975.
[2]	Metropolis N, Rosenbluth A W, Rosenbluth M N, Teller A H, Teller E. Equation of state calculations by fast computing machines. The Journal of Chemical Physics, 1953, 21(6): 1087-1092 doi: 10.1063/1.1699114
[3]	Kirkpatrick S, Gelatt Jr C D, Vecchi M P. Optimization by simulated annealing. Science, 1983, 220(4598): 671-680 doi: 10.1126/science.220.4598.671
[4]	Dorigo M. Optimization, Learning and Natural Algorithms [Ph.D. dissertation], Politecnico di Milano, Italy, 1992.
[5]	Dorigo M, Gambardella L M. Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 53-66 doi: 10.1109/4235.585892
[6]	Eberhart R, Kennedy J. A new optimizer using particle swarm theory. In: Proceedings of the 6th International Symposium on Micro Machine and Human Science. Nagoya, Japan: IEEE, 1995. 39−43
[7]	Kennedy J. Probability and dynamics in the particle swarm. In: Proceedings of the Congress on Evolutionary Computation. Portland, USA: IEEE, 2004. 340−347
[8]	Omran M G H, Engelbrecht A P, Salman A. Bare bones differential evolution. European Journal of Operational Research, 2009, 196(1): 128-139 doi: 10.1016/j.ejor.2008.02.035
[9]	Li J Z, Tan Y. The bare bones fireworks algorithm: A minimalist global optimizer. Applied Soft Computing, 2018, 62: 454-462 doi: 10.1016/j.asoc.2017.10.046
[10]	Sörensen K. Metaheuristics—the metaphor exposed. International Transactions in Operational Research, 2015, 22(1): 3-18 doi: 10.1111/itor.12001
[11]	Yang X S. Nature-inspired Optimization Algorithms. Amsterdam: Elsevier, 2014.
[12]	Weyland D. A rigorous analysis of the harmony search algorithm: How the research community can be misled by a “novel” methodology. International Journal of Applied Metaheuristic Computing, 2010, 1(2): 50-60 doi: 10.4018/jamc.2010040104
[13]	Griffiths D J, Schroeter D F. Introduction to Quantum Mechanics. Cambridge: Cambridge University Press, 2018.
[14]	Narayanan A, Moore M. Quantum-inspired genetic algorithms. In: Proceedings of the IEEE International Conference on Evolutionary Computation. Nagoya, Japan: IEEE, 1996. 61−66
[15]	Han K H, Kim J H. Quantum-inspired evolutionary algorithm for a class of combinatorial optimization. IEEE Transactions on Evolutionary Computation, 2002, 6(6): 580-593 doi: 10.1109/TEVC.2002.804320
[16]	Wang L, Niu Q, Fei M R. A novel quantum ant colony optimization algorithm. In: Proceedings of the International Conference on Life System Modeling and Simulation. Shanghai, China: Springer, 2007. 277−286
[17]	Sun J, Xu W B, Feng B. A global search strategy of quantum-behaved particle swarm optimization. In: Proceedings of the IEEE Conference on Cybernetics and Intelligent Systems. Singapore, Singapore: IEEE, 2004. 111−116
[18]	王鹏, 黄焱, 任超, 郭又铭. 多尺度量子谐振子高维函数全局优化算法. 电子学报, 2013, 41(12): 2468-2473 Wang Peng, Huang Yan, Ren Chao, Guo You-Ming. Multi-scale quantum harmonic oscillator for high-dimensional function global optimization algorithm. Acta Electronica Sinica, 2013, 41(12): 2468-2473
[19]	Wang P, Ye X G, Li B, Cheng K. Multi-scale quantum harmonic oscillator algorithm for global numerical optimization. Applied Soft Computing, 2018, 69: 655-670 doi: 10.1016/j.asoc.2018.05.005
[20]	Kennedy J. Swarm intelligence. Handbook of Nature-Inspired and Innovative Computing. Boston, USA: Springer, 2006. 187−219
[21]	Born M. Quantenmechanik der stoßvorgänge. Zeitschrift für physik, 1926, 38(11-12): 803-827 doi: 10.1126/science.122.3172.675
[22]	Finnila A B, Gomez M A, Sebenik C, Stenson C, Doll J D. Quantum annealing: A new method for minimizing multidimensional functions. Chemical Physics Letters, 1994, 219(5-6): 343-348 doi: 10.1016/0009-2614(94)00117-0
[23]	Kosztin I, Faber B, Schulten K. Introduction to the diffusion Monte Carlo method. American Journal of Physics, 1996, 64(5): 633-644 doi: 10.1119/1.18168
[24]	王鹏, 黄焱, 袁亚男, 都政, 安俊秀. 多尺度量子谐振子算法的收敛特性. 电子学报, 2016, 44(8): 1988-1993 Wang Peng, Huang Yan, Yuan Ya-Nan, Du Zheng, An Jun-Xiu. The convergence characteristics of multi-scale quantum harmonic oscillator algorithm. Acta Electronica Sinica, 2016, 44(8): 1988-1993
[25]	Li B, Wang P, Jin J. Multiscale quantum harmonic oscillator algorithm with strict metastability constraints for multi-modal optimization. IEEE Access, 2019, 7: 17377-17388 doi: 10.1109/ACCESS.2019.2895358
[26]	Ye X G, Wang P, Xin G, Jin J, Huang Y. Multi-scale quantum harmonic oscillator algorithm with truncated mean stabilization strategy for global numerical optimization problems. IEEE Access, 2019, 7: 18926-18939 doi: 10.1109/ACCESS.2019.2893200
[27]	Li B, Wang P. Multiscale quantum harmonic oscillator algorithm with multi-harmonic oscillators for numerical optimization. IEEE Access, 2019, 7: 51159-51170 doi: 10.1109/ACCESS.2019.2909102
[28]	Cheng K, Wang P. Analysis of multiscale quantum harmonic oscillator algorithm based on a new multimode objective function. IEEE Access, 2019, 7: 46295-46305 doi: 10.1109/ACCESS.2019.2907372
[29]	陆志君, 安俊秀, 王鹏. 基于划分的多尺度量子谐振子算法多峰优化. 自动化学报, 2016, 42(2): 235-245 doi: 10.16383/j.aas.2016.c150429 Lu Zhi-Jun, An Jun-Xiu, Wang Peng. Partition-based MQHOA for multimodal optimization. Acta Automatica Sinica, 2016, 42(2): 235-245 doi: 10.16383/j.aas.2016.c150429
[30]	Sun J, Fang W, Wu X J, Palade V, Xu W B. Quantum-behaved particle swarm optimization: Analysis of individual particle behavior and parameter selection. Evolutionary Computation, 2012, 20(3): 349-393 doi: 10.1162/EVCO_a_00049
[31]	Brooke J, Bitko D, Rosenbaum T F, Aeppli G. Quantum annealing of a disordered magnet. Science, 1999, 284(5415): 779-781 doi: 10.1126/science.284.5415.779
[32]	Stella L, Santoro G E, Tosatti E. Optimization by quantum annealing: Lessons from simple cases. Physical Review B, 2005, 72(1): 014303
[33]	Xin G, Wang P. Exploring superposition state in multi-scale quantum harmonic oscillator algorithm. Applied Soft Computing, 2021, 107: 107398 doi: 10.1016/j.asoc.2021.107398
[34]	dos Santos-Coelho L, Ayala H V H, Freire R Z. Population＇s variance-based adaptive differential evolution for real parameter optimization. In: Proceedings of the IEEE Congress on Evolutionary Computation. Cancun, Mexico: IEEE, 2013. 1672−1677
[35]	Zambrano B M, Clerc M, Rojas R. Standard particle swarm optimisation 2011 at CEC-2013: A baseline for future PSO improvements. In: Proceedings of the IEEE Congress on Evolutionary Computation. IEEE, 2013. 2337−2344
[36]	Li J Z, Tan Y. Loser-out tournament-based fireworks algorithm for multimodal function optimization. IEEE Transactions on Evolutionary Computation, 2018, 22(5): 679-691 doi: 10.1109/TEVC.2017.2787042
[37]	Liang J, Qu B Y, Suganthan P N, Hernández-Díaz A G. Problem Definitions and Evaluation Criteria for the CEC 2013 Special Session on Real-parameter Optimization, Technical Report 201212, Computational Intelligence Laboratory, Zhengzhou University, China, Nanyang Technological University, Singapore, 2013.
[38]	Bertoni A, Dorigo M. Implicit parallelism in genetic algorithms. Artificial Intelligence, 1993, 61(2): 307-314 doi: 10.1016/0004-3702(93)90071-I
[39]	王鹏, 常征. 算法隐含并行性的物理模型. 电子科技大学学报, 2009, 38(4): 588-591 Wang Peng, Chang Zheng. Physical model of implicit parallelism in algorithms. Journal of University of Electronic Science and Technology of China, 2009, 38(4): 588-591