Journal
FRONTIERS IN NEUROSCIENCE
Volume 11, Issue -, Pages -Publisher
FRONTIERS MEDIA SA
DOI: 10.3389/fnins.2017.00714
Keywords
SpiNNaker; constraint satisfaction; spiking neural networks; stochastic search; spiking neurons
Categories
Funding
- UK Engineering and Physical Sciences Research Council - EPSRC [EP/G015740/1, EP/G015775/1]
- ARM Ltd.
- Silistix Ltd.
- European Research Council under the European Union's Seventh Framework Programme (FP7)/ERC grant [320689]
- EU Flagship Human Brain Project (H)
- Brazilian National Council for Scientific and Technological Development-CNPq [205570/2014-3]
- EPSRC [EP/G015740/1, EP/G015775/1] Funding Source: UKRI
Ask authors/readers for more resources
Constraint satisfaction problems (CSP) are at the core of numerous scientific and technological applications. However, CSPs belong to the NP-complete complexity class, for which the existence (or not) of efficient algorithms remains a major unsolved question in computational complexity theory. In the face of this fundamental difficulty heuristics and approximation methods are used to approach instances of NP (e.g., decision and hard optimization problems). The human brain efficiently handles CSPs both in perception and behavior using spiking neural networks (SNNs), and recent studies have demonstrated that the noise embedded within an SNN can be used as a computational resource to solve CSPs. Here, we provide a software framework for the implementation of such noisy neural solvers on the SpiNNaker massively parallel neuromorphic hardware, further demonstrating their potential to implement a stochastic search that solves instances of P and NP problems expressed as CSPs. This facilitates the exploration of new optimization strategies and the understanding of the computational abilities of SNNs. We demonstrate the basic principles of the framework by solving difficult instances of the Sudoku puzzle and of the map color problem, and explore its application to spin glasses. The solver works as a stochastic dynamical system, which is attracted by the configuration that solves the CSP. The noise allows an optimal exploration of the space of configurations, looking for the satisfiability of all the constraints; if applied discontinuously, it can also force the system to leap to a new random configuration effectively causing a restart.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available