Faculty of Physics, Babeş-Bolyai University, Cluj-Napoca, RO-400084, Romania.
PLoS One. 2013 Sep 16;8(9):e73400. doi: 10.1371/journal.pone.0073400. eCollection 2013.
There has been a long history of using neural networks for combinatorial optimization and constraint satisfaction problems. Symmetric Hopfield networks and similar approaches use steepest descent dynamics, and they always converge to the closest local minimum of the energy landscape. For finding global minima additional parameter-sensitive techniques are used, such as classical simulated annealing or the so-called chaotic simulated annealing, which induces chaotic dynamics by addition of extra terms to the energy landscape. Here we show that asymmetric continuous-time neural networks can solve constraint satisfaction problems without getting trapped in non-solution attractors. We concentrate on a model solving Boolean satisfiability (k-SAT), which is a quintessential NP-complete problem. There is a one-to-one correspondence between the stable fixed points of the neural network and the k-SAT solutions and we present numerical evidence that limit cycles may also be avoided by appropriately choosing the parameters of the model. This optimal parameter region is fairly independent of the size and hardness of instances, this way parameters can be chosen independently of the properties of problems and no tuning is required during the dynamical process. The model is similar to cellular neural networks already used in CNN computers. On an analog device solving a SAT problem would take a single operation: the connection weights are determined by the k-SAT instance and starting from any initial condition the system searches until finding a solution. In this new approach transient chaotic behavior appears as a natural consequence of optimization hardness and not as an externally induced effect.
神经网络在组合优化和约束满足问题中有着悠久的应用历史。对称 Hopfield 网络和类似的方法使用最陡下降动力学，它们总是收敛到能量景观的最近局部最小值。为了找到全局最小值，需要使用额外的参数敏感技术，例如经典的模拟退火或所谓的混沌模拟退火，通过向能量景观中添加额外项来诱导混沌动力学。在这里，我们展示了非对称连续时间神经网络可以解决约束满足问题，而不会陷入非解决方案吸引子中。我们集中研究了一个解决布尔可满足性（k-SAT）的模型，这是一个典型的 NP 完全问题。神经网络的稳定平衡点与 k-SAT 解之间存在一一对应关系，我们通过数值证据表明，通过适当选择模型的参数，也可以避免极限环。这个最佳参数区域与实例的大小和难度相当独立，这样就可以独立于问题的性质选择参数，并且在动态过程中不需要进行调整。该模型类似于已经用于 CNN 计算机的细胞神经网络。在模拟设备上，解决 SAT 问题只需要一个操作：连接权重由 k-SAT 实例确定，并且从任何初始条件开始，系统会一直搜索，直到找到解决方案。在这种新方法中，瞬态混沌行为是优化难度的自然结果，而不是外部诱导的效果。
