CHAOPT

Chaotic Cellular Neural/Nonlinear Networks for Solving Constraint Satisfaction

 Partecipanti

Mappa

 Word cloud

Esplora la "nuvola delle parole (Word Cloud) per avere un'idea di massima del progetto.

 Obiettivo del progetto (Objective)

'Constraint satisfaction problems (such as Boolean satisfiability) constitute one of the hardest classes of optimization problems with many applications in technology and industry. In a recent paper the Fellow revealed a novel connection between these problems and chaotic dynamical systems. The paper provided an exact mapping of Boolean satisfiability (k-SAT) into a deterministic continuous-time dynamical system with a unique correspondence between its set of attractors and the k-SAT solutions. It was shown that optimization hardness is fundamentally equivalent to the phenomenon of chaos and turbulence: after a critical constraint density is reached, the trajectories become transiently chaotic before finding the solutions, signaling the appearance of optimization hardness. Numerical results have also shown that the presented dynamical system is very efficient in solving SAT problems. The system presented has the simplest possible form designed for fulfilling the mathematical requirements and is not yet suitable for direct implementation. However, the system is not necessarily unique. Using the same principles the goal of this project is to develop a deterministic continuous-time Cellular Neural/Nonlinear Network (CNN) model for solving constraint satisfaction. CNN models were already implemented in analog computers so this could result in a possible physical implementation of the model in the future, leading to numerous applications. The project will follow three major steps: 1) developing the CNN model and analyzing its mathematical properties. 2) Studying the efficiency of the CNN solver and properties of the transient chaotic behavior in hard problems. 3) Testing the robustness of the model to noise effects.'

Introduzione (Teaser)

Quantitative neuroscience has made it possible to understand signal processing in some parts of our nervous system. The revolutionary new way of computing that has arisen from this emerging field helped EU-funded scientists find a solution to problems of mathematical optimisation.

Descrizione progetto (Article)

Until recently, the position of processors had no significant role in computing. Today, several microprocessors placed on a single chip have become very similar to a layer of neurons. Imitating how our nervous system works, such large-scale non-linear circuits have helped overcome the speed bottleneck that conventional computation methods run into.

The many applications of these cellular neural networks (CNNs) like solving partial differential equations also result from their spatial structure. The aim of the EU-funded project 'Chaotic cellular neural/nonlinear networks for solving constraint satisfaction' (http://sirius.phys.ubbcluj.ro:33380/ercsey-ravasz/MarieCurie-IIF/index.html (CHAOPT)) was to design a CNN able to efficiently solve constraint satisfaction problems.

Computation models proposed in the past to solve this class of optimisation problems were vulnerable to noise. The asymmetric continuous-time CNN model developed within the CHAOPT project is stable to white noise as well as coloured noise. In addition, it has been experimentally demonstrated to tolerate higher noise levels than existing hardware.

Numerical experiments also helped CHAOPT scientists better understand the transient chaotic and overall behaviour of the network. Simulations were performed on thousands of random Boolean Satisfiability Problems (SATs)of different sizes and constraint densities. They revealed one-to-one correspondence between the fixed points of the CNN model and the SAT solutions.

The CHAOPT model can be implemented by analogue circuits, in which dedicated algorithms lead the network to a solution based on the initial condition. The operation of algorithms handling the CNN is based on the observation that beyond a critical value of constraint density its behaviour becomes chaotic.

Using these so-called chaotic algorithms on hardware is a revolutionary concept that can lay the groundwork for decision-making, task-scheduling and error-correction applications.