« Constraint Satisfaction Using Neural Networks with a Local and Autonomous Annealing Technique | Main | Web Pages That Reproduce Themselves by JavaScript »

Methods of Parallel Processing of Constraint Satisfaction Using CCM -- A Model for Emergent Computation

Kanada, Y., SIG PPAI, Japan Society for Artificial Intelligence, Feb, 1996, Published by JSAI.

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ Paper postscript file (in Japanese) ]
[ Paper DVI file (except figures) (in Japanese) ] [ Figures in EPSF format : 1, 2, 3, 4, 5, 6, 7, 8 ]

Abstract : Two methods for solving large-scale constraint satisfaction problems using parallel processing are surveyed in the present paper. These methods are based on CCM, which is a model for emergent computation. The number of constraint violations is minimized in these methods. The minimization is performed by optimization of local functions. The computation is stochastic and no global information is used. An annealing method called FAM has been introduced to avoid ``local maxima.'' FAM also works only with local information. Two types of parallel processing of CCM-based constraint satisfaction using FAM has been tested. One is a parallel search and the other is a cooperative search. Our experiments has shown that both methods improve performance almost linearly in large-scale graph coloring problems when the number of processors is ten or so.

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

Keywords: CCM, Constraint satisfaction problem, Parallel processing, Randomized computation, Randomized problem solving

Post a comment

About

This page contains a single entry from the blog posted on February 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