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