Asymmetric continuous-time neural networks without local traps for solving constraint satisfaction problems.
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 glo...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Public Library of Science (PLoS)
2013-01-01
|
| Series: | PLoS ONE |
| Online Access: | http://europepmc.org/articles/PMC3774769?pdf=render |
| _version_ | 1818131686867599360 |
|---|---|
| author | Botond Molnár Mária Ercsey-Ravasz |
| author_facet | Botond Molnár Mária Ercsey-Ravasz |
| author_sort | Botond Molnár |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-11T08:24:53Z |
| format | Article |
| id | doaj.art-0f23693e6d944c3ba9a7d7f8be0cf9a6 |
| institution | Directory Open Access Journal |
| issn | 1932-6203 |
| language | English |
| last_indexed | 2024-12-11T08:24:53Z |
| publishDate | 2013-01-01 |
| publisher | Public Library of Science (PLoS) |
| record_format | Article |
| series | PLoS ONE |
| spelling | doaj.art-0f23693e6d944c3ba9a7d7f8be0cf9a62022-12-22T01:14:33ZengPublic Library of Science (PLoS)PLoS ONE1932-62032013-01-0189e7340010.1371/journal.pone.0073400Asymmetric continuous-time neural networks without local traps for solving constraint satisfaction problems.Botond MolnárMária Ercsey-RavaszThere 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.http://europepmc.org/articles/PMC3774769?pdf=render |
| spellingShingle | Botond Molnár Mária Ercsey-Ravasz Asymmetric continuous-time neural networks without local traps for solving constraint satisfaction problems. PLoS ONE |
| title | Asymmetric continuous-time neural networks without local traps for solving constraint satisfaction problems. |
| title_full | Asymmetric continuous-time neural networks without local traps for solving constraint satisfaction problems. |
| title_fullStr | Asymmetric continuous-time neural networks without local traps for solving constraint satisfaction problems. |
| title_full_unstemmed | Asymmetric continuous-time neural networks without local traps for solving constraint satisfaction problems. |
| title_short | Asymmetric continuous-time neural networks without local traps for solving constraint satisfaction problems. |
| title_sort | asymmetric continuous time neural networks without local traps for solving constraint satisfaction problems |
| url | http://europepmc.org/articles/PMC3774769?pdf=render |
| work_keys_str_mv | AT botondmolnar asymmetriccontinuoustimeneuralnetworkswithoutlocaltrapsforsolvingconstraintsatisfactionproblems AT mariaercseyravasz asymmetriccontinuoustimeneuralnetworkswithoutlocaltrapsforsolvingconstraintsatisfactionproblems |