A Fitness Landscape Exploration Algorithm Simulating Adiabatic Quantum Computation

YANG Guo-song; WANG Peng; YIN Xin-yu

doi:10.12263/DZXB.20230832

您当前的位置：

首页 >

文章列表页 >

A Fitness Landscape Exploration Algorithm Simulating Adiabatic Quantum Computation

PAPERS | 更新时间：2025-12-08

- A Fitness Landscape Exploration Algorithm Simulating Adiabatic Quantum Computation
- ACTA ELECTRONICA SINICA Vol. 52, Issue 4, Pages: 1330-1336(2024)
- 作者机构：
  
  1.中国科学院成都计算机应用研究所,四川成都 610299
  2.西南民族大学计算机科学与工程学院,四川成都 610225
  3.中国科学院大学计算机科学与技术学院,北京 101408
- 作者简介：
- 基金信息：
  
  National Natural Science Foundation of China(60702075);Sichuan Science and Technology Program(2019001)
- DOI：10.12263/DZXB.20230832
  CLC： TP301.6
- Received：01 September 2023，
  
  Revised：2024-01-06，
  
  Published：25 April 2024
- 稿件说明：
移动端阅览
杨国松,王鹏,尹鑫钰.一种模拟绝热量子计算的适应度地形探索算法[J].电子学报,2024,52(04):1330-1336.

YANG Guo-song, WANG Peng, YIN Xin-yu.A Fitness Landscape Exploration Algorithm Simulating Adiabatic Quantum Computation[J].Acta Electronica Sinica, 2024, 52(04): 1330-1336.
杨国松,王鹏,尹鑫钰.一种模拟绝热量子计算的适应度地形探索算法[J].电子学报,2024,52(04):1330-1336. DOI：10.12263/DZXB.20230832

YANG Guo-song, WANG Peng, YIN Xin-yu.A Fitness Landscape Exploration Algorithm Simulating Adiabatic Quantum Computation[J].Acta Electronica Sinica, 2024, 52(04): 1330-1336. DOI：10.12263/DZXB.20230832

摘要

将优化问题抽象成目标函数后，目标函数和启发式优化算法的匹配程度决定了优化求解的效率.为反映目标函数的优化特征并指导优化算法及其参数的选择，本文模拟绝热量子计算中的多基态演化，提出了一种适应度地形探索算法.根据基态波函数倾向于向势能较小处收敛且收敛程度受量子效应强度影响的特性，用目标函数编码势能场后算法引入了一个量子效应递减的多基态演化过程，用其持续收敛的基态波函数簇反映目标函数的适应度地形.根据量子路径积分，算法由尺度递减的扩散蒙特卡罗（diffusion Monte Carlo，DMC）实现.实验表明算法综合直观地反映了适应度地形的众多特征，所得信息能直接指导后续优化，其计算模式和启发式优化相似，无需引入其他计算，这为适应度地形研究引入了新的视角.

Abstract

After transforming an optimization problem into an objective function

the degree of matching between the objective function and the chosen heuristic optimization algorithm determines the efficiency of the following optimization. By simulating multi-ground states evolution in adiabatic quantum computation

a fitness landscape exploration algorithm is proposed to reflect the optimization characteristics of the objective function and guide the selection of optimization algorithms and their parameters. In quantum ground state evolution

the ground state wave function of a particle tends to converge towards regions with lower potential energy

and the extent of convergence is influenced by the quantum effect strength. Using these features

we encode the potential energy field by the objective function in a multi-ground states evolution with diminishing quantum effect

and consequently the fitness landscape of the objective function is reflected by the distributions of a set of converging ground state wave function in this adiabatic evolution. Based on the quantum path integral

the algorithm is implemented using a downscaling diffusion Monte Carlo (DMC). Experiments illustrated that the algorithm comprehensively and intuitively reflected numerous features of the fitness landscape

and the obtained information could directly guide optimization thereafter. Its computational mode resembles that of heuristic optimization

as it does not introduce other computations during optimization. These features introduce a novel perspective to the study of fitness landscape.

关键词

Keywords

references

WOLPERT D H , MACREADY W G . No free lunch theorems for optimization [J ] . IEEE Transactions on Evolutionary Computation , 1997 , 1 ( 1 ): 67 - 82 .

李亚欣 , 梁静 , 岳彩通 , 等 . 基于适应度地形分析的进化计算研究综述 [J ] . 陕西师范大学学报(自然科学版) , 2021 , 49 ( 5 ): 39 - 53 .

LI Y X , LIANG J , YUE C T , et al . A survey of evolutionary computing based on fitness landscape analysis [J ] . Journal of Shaanxi Normal University (Natural Science Edition) , 2021 , 49 ( 5 ): 39 - 53 . (in Chinese)

WRIGHT S . The roles of mutation, inbreeding, crossbreeding, and selection in evolution [C ] // Proceedings of the 6th International Congress on Genetics . Menasha : George Banta Publishing Company , 1932 : 356 - 366 .

KAUFFMAN S , LEVIN S . Towards a general theory of adaptive walks on rugged landscapes [J ] . Journal of Theoretical Biology , 1987 , 128 ( 1 ): 11 - 45 .

WEINBERGER E . Correlated and uncorrelated fitness landscapes and how to tell the difference [J ] . Biological Cybernetics , 1990 , 63 ( 5 ): 325 - 336 .

JONES T , FORREST S . Fitness distance correlation as a measure of problem difficulty for genetic algorithms [C ] // Proceedings of the 6th International Conference on Genetic Algorithms . New York : ACM Press , 1995 : 184 - 192 .

VASSILEV V K , FOGARTY T C , MILLER J F . Smoothness, ruggedness and neutrality of fitness landscapes: From theory to application [M ] // Advances in Evolutionary Computing , Natural Computing Series. Berlin : Springer , 2003 : 3 - 44 .

HARVEY I , THOMPSON A . Through the labyrinth evolution finds a way: A silicon ridge [C ] // Proceedings of the 1st International Conference on Evolvable Systems: From Biology to Hardware . Berlin : Springer , 1997 : 406 - 422 .

VEREL S , OCHOA G , TOMASSINI M . Local optima networks of NK landscapes with neutrality [J ] . IEEE Transactions on Evolutionary Computation , 2011 , 15 ( 6 ): 783 - 797 .

ALTENBERG L . The evolution of evolvability in genetic programming [M ] // Advances in Genetic Programming . Cambridge : MIT Press , 1994 : 47 - 74 .

DAVIDOR Y . Epistasis variance: A viewpoint on GA-hardness [M ] // Foundations of Genetic Algorithms . Amsterdam : Elsevier , 1991 : 23 - 35 .

路辉 , 周容容 , 石津华 , 等 . 智能优化技术: 适应度地形理论及组合优化问题的应用 [M ] . 北京 : 机械工业出版社 , 2021 .

曾谨言 . 量子力学 [M ] . 第5版 . 北京 : 科学出版社 , 2014 .

KOSZTIN I , FABER B , SCHULTEN K . Introduction to the diffusion Monte Carlo method [J ] . American Journal of Physics , 1996 , 64 ( 5 ): 633 - 644 .

ROTHSTEIN S M , OSPADOV E , BRUZZESE C . Introduction to fixed-node quantum Monte Carlo [M ] // Mathematical Physics in Theoretical Chemistry . Amsterdam : Elsevier , 2019 : 189 - 217 .

赵凯华 . Adiabatic的含义是怎样从“绝热”变成“无限缓慢(寖渐)”的? [J ] . 物理 , 2010 , 39 ( 1 ): 56 - 57 .

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 ): 343 - 348 .

KADOWAKI T , NISHIMORI H . Quantum annealing in the transverse Ising model [J ] . Physical Review E , 1998 , 58 ( 5 ): 5355 - 5363 .

FARHI E , GOLDSTONE J , GUTMANN S , et al . A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem [J ] . Science , 2001 , 292 ( 5516 ): 472 - 475 .

GRIFFITHS D J , SCHROETER D F . Introduction to Quantum Mechanics [M ] . 3rd edition . Cambridge : Cambridge University Press , 2018 .

YANG G S , WANG P , XIN G , et al . A quantum simulation method with repeatable steady-state output using massive inferior solutions [C ] // Proceedings of the 19th International Conference on Intelligent Computing: Advanced Intelligent Computing Technology and Applications . Singapore : Springer Nature Singapore , 2023 : 674 - 684 .

JOHNSON M W , AMIN M H S , GILDERT S , et al . Quantum annealing with manufactured spins [J ] . Nature , 2011 , 473 : 194 - 198 .

MCMAHON P L , MARANDI A , HARIBARA Y , et al . A fully programmable 100-spin coherent Ising machine with all-to-all connections [J ] . Science , 2016 , 354 ( 6312 ): 614 - 617 .

CEPERLEY D , ALDER B . Quantum Monte Carlo [J ] . Science , 1986 , 231 ( 4738 ): 555 - 560 .

FEYNMAN R P , HIBBS A R , STYER D F . Quantum Mechanics and Path Integrals [M ] . Emended edition . New York : Dover Publications , 2010 .

THIJSSEN J . Computational Physics [M ] . Cambridge : Cambridge University Press , 2007 .

张映玉 , 付樟华 . 绝热量子优化算法研究进展 [J ] . 计算机工程与科学 , 2015 , 37 ( 3 ): 429 - 433 .

ZHANG Y Y , FU Z H . Survey of adiabatic quantum optimization algorithms [J ] . Computer Engineering and Science , 2015 , 37 ( 3 ): 429 - 433 . (in Chinese)

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

No data

Related Author

YIN Xin-yu

Related Institution

No data

⁰