Timescales of Boolean satisfiability solver using continuous-time dynamical system
Timescales of Boolean satisfiability solver using continuous-time dynamical system
复制标题
DOI：
10.1016/j.cnsns.2020.105183
复制
发表时间：
2020-05
期刊：
影响因子：
--
通讯作者：
H. Yamashita;K. Aihara;H. Suzuki
中科院分区：
文献类型：
--
作者：
H. Yamashita;K. Aihara;H. Suzuki
已经提出了用于解决组合优化问题的各种物理系统，其中，最近在[Ercsey-Ravasz & Toroczkai，2011]中提出的用于解决可满足性问题的动力系统也有望在物理实现中表现良好。该系统通过相对于目标函数的梯度下降来改进分配，该目标函数也随时间变化。这两个部分有自己的时间尺度，它们的平衡可以被认为在寻找解决方案方面发挥着重要作用。在本文中，我们开发了一个变种的系统，其中的平衡是明确表示的参数。使用所开发的系统，我们提出了一个自然的时间评估措施，并表明，适当选择的相对时间尺度，我们可以最大限度地提高性能相对于所提出的措施。
Various physical systems for solving combinatorial optimization problems have been proposed, and among them, the dynamical system recently proposed in [Ercsey-Ravasz & Toroczkai, 2011] to solve the satisfiability problem is also expected to perform well in a physical realization. This system improves the assignment by the gradient descent with respect to a target function, which is also changing in time. These two parts have their own timescales, and their balance can be considered to play an important role in finding a solution. In this paper, we develop a variant of the system, where the balance is explicitly represented by a parameter. Using the developed system, we propose a natural time measure for evaluation and show that with an appropriate choice of the relative timescale we can maximize the performance with respect to the proposed measure.