« The Effects of Randomness in Asynchronous 1D Cellular Automata | Main | The Features and Implementation of SOOC: A Language for Emergent Computation -- Using the Magic Square Problem for An Example -- »

Methods of Controling Locality in Problem Solving using CCM: A Model for Emergent Computation

Kanada, Y., SWoPP '94 (SIG Note of Artificial Intelligence, Information Processing Society of Japan), 94-AI-95-4, pp. 29-38, 1994, Published by IPSJ.

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ Paper postscript file (in Japanese) ]
[ OHP postscript file: Slides, Handout ] [ OHP PDF ファイル: Slides, Handout ]

[ Several constraint satisfaction problem demos in Java (You can change catalysts, rules, and frustration.) ]

Abstract: CCM (Chemical Casting Model) is a model of nondeterministic, or random, computation. CCM is developed toward establishing a problem solving methodology based on emergent computation, which is open to continually varying environment. Computation in CCM is based on local information. However, a solution cannot be found if the locality is at the limit. Thus, the locality of computation, especially computation of the evaluation functions, must be controlled properly, and the locality in the search space must be controlled properly not to fall into local optima. Four methods of controlling locality are shown in this report. They are addition or removal of catalysts, composition of reaction rules (or tunneling), simulated annealing (SA) and frustration accumulation method (FAM). We found that catalysts and FAM are effective in constraint satisfaction, but that the performance is worse than conventional methods when only using these methods in a case. We also found that tunneling, or dynamical composition of reaction rules, is effective in optimization.

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

Keywords: CCM, Emergent computation, Randomized computation, Randomized problem solving, Rule-based computation, Rule-based problem solving, Local information, Localized computation, Local evaluation function, Production system, Production rule, Local information, Localized computation, Local evaluation function, Graph coloring

Post a comment

About

This page contains a single entry from the blog posted on August 1, 1994 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