Cargando…

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...

Descripción completa

Detalles Bibliográficos
Autores principales: Molnár, Botond, Ercsey-Ravasz, Mária
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Public Library of Science 2013
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3774769/
https://www.ncbi.nlm.nih.gov/pubmed/24066045
http://dx.doi.org/10.1371/journal.pone.0073400
_version_ 1782284516855906304
author Molnár, Botond
Ercsey-Ravasz, Mária
author_facet Molnár, Botond
Ercsey-Ravasz, Mária
author_sort Molnár, Botond
collection PubMed
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.
format Online
Article
Text
id pubmed-3774769
institution National Center for Biotechnology Information
language English
publishDate 2013
publisher Public Library of Science
record_format MEDLINE/PubMed
spelling pubmed-37747692013-09-24 Asymmetric Continuous-Time Neural Networks without Local Traps for Solving Constraint Satisfaction Problems Molnár, Botond Ercsey-Ravasz, Mária PLoS One Research Article 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. Public Library of Science 2013-09-16 /pmc/articles/PMC3774769/ /pubmed/24066045 http://dx.doi.org/10.1371/journal.pone.0073400 Text en © 2013 Molnár and Ercsey-Ravasz http://creativecommons.org/licenses/by/4.0/ This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are properly credited.
spellingShingle Research Article
Molnár, Botond
Ercsey-Ravasz, Mária
Asymmetric Continuous-Time Neural Networks without Local Traps for Solving Constraint Satisfaction Problems
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
topic Research Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3774769/
https://www.ncbi.nlm.nih.gov/pubmed/24066045
http://dx.doi.org/10.1371/journal.pone.0073400
work_keys_str_mv AT molnarbotond asymmetriccontinuoustimeneuralnetworkswithoutlocaltrapsforsolvingconstraintsatisfactionproblems
AT ercseyravaszmaria asymmetriccontinuoustimeneuralnetworkswithoutlocaltrapsforsolvingconstraintsatisfactionproblems