« Constraint Satisfaction by Parallel Optimization of Local Evaluation Functions with Annealing | Main | Methods of Parallel Processing of Constraint Satisfaction Using CCM -- A Model for Emergent Computation »

Constraint Satisfaction Using Neural Networks with a Local and Autonomous Annealing Technique

Kanada, Y., not yet published, 1996.

[ 日本語のページ ]
[ Paper PDF file ] [ Paper postscript file ]

Abstract: A method for solving large-scale constraint satisfaction problems using an annealed symmetrically-connected neural network, which is called DSN-FAM, is proposed in the present paper. Some conventional methods, such as Hopfield networks, often fail to find a solution. Some others, such as Boltzmann Machines, take too much time. These difficulties are solved by a type of annealing technique, which we call the frustration accumulation method (FAM). DSN-FAM works only with local information, and no global functions or global parameters such as a temperature are used. DSN-FAM thus works autonomously. That is, no external control is necessary while operating. Experiments show that this method does not fail to find a solution and the execution time is less than one tenth of Boltzmann Machines. The performance can be easily and almost linearly improved by parallel processing using tens of processors.

Introduction to this research theme: CCM: Chemical-Computation Model

Keywords: CCM, Constraint satisfaction problem, Neural networks, Randomized computation, Randomized problem solving, Annealing, Rule-based computation, Rule-based problem solving, FAM, Frustration accumulation method

Post a comment


This page contains a single entry from the blog posted on January 1, 1996 12:00 AM.

Many more can be found on the main index page or by looking through the archives.

(C) Copyright 2007 by Yasusi Kanada
Powered by
Movable Type 3.36