随机驱动非线性动力学系统在组合优化中的直接比较

Direct comparison of stochastic driven nonlinear dynamical systems for combinatorial optimization

摘要 Abstract

组合优化问题是工业应用中无处不在的问题。然而,找到最优或接近最优的解常常极其困难。由于这些问题可以映射到伊辛模型的基态搜索问题,过去几十年里投入了大量精力开发伊辛型问题的求解器。近年来,对量子和经典系统的控制和操控的进步使得量子模拟器和相干伊辛机等新型计算范式得以发展,用于解决复杂的优化问题。本文考察并评估了几种基于物理学的优化算法,包括相干伊辛机、增益-耗散算法、模拟分岔机和Hopfield神经网络,我们将这些统称为随机驱动的非线性动力学系统。最重要的是,我们以包含已知解的随机伊辛问题为基准,将这些算法与模拟退火算法进行对比,并利用相同的软件堆栈对所有求解器进行评估。此外,我们还研究了不同的数值积分技术和图连通性对性能的影响。这项工作概述了一系列新的优化范式。

Combinatorial optimization problems are ubiquitous in industrial applications. However, finding optimal or close-to-optimal solutions can often be extremely hard. Because some of these problems can be mapped to the ground-state search of the Ising model, tremendous effort has been devoted to developing solvers for Ising-type problems over the past decades. Recent advances in controlling and manipulating both quantum and classical systems have enabled novel computing paradigms such as quantum simulators and coherent Ising machines to tackle hard optimization problems. Here, we examine and benchmark several physics-inspired optimization algorithms, including coherent Ising machines, gain-dissipative algorithms, simulated bifurcation machines, and Hopfield neural networks, which we collectively refer to as stochastic-driven nonlinear dynamical systems. Most importantly, we benchmark these algorithms against random Ising problems with planted solutions and compare them to simulated annealing as a baseline leveraging the same software stack for all solvers. We further study how different numerical integration techniques and graph connectivity affect performance. This work provides an overview of a diverse set of new optimization paradigms.

随机驱动非线性动力学系统在组合优化中的直接比较 - arXiv