« Various Sorting Methods by CCM, a Computational Model Based on Production Rules and Local Evaluation Functions | Main | Symbolic Random Tunneling Based on Composing Production Rules -- Constraint Satisfaction and Optimization Using Computation Model CCM -- »

Stochastic Problem Solving by Local Computation based on Self-organization Paradigm

Kanada, Y., and Hirokawa, M., 27th Hawaii International Conference on System Sciences (HICSS-27), 82-91, 1994.

[ 日本語のページ ]
[ Paper PDF file, (C) Copyright by IEEE ]
[ Paper in hypertext format (Figures are not available now) ]
[ Paper postscript file, (C) Copyright by IEEE ]
[ OHP postscript file: Slides, Handout ] [ OHP PDF file: Slides, Handout ]
[ IEEExplore Paper page ]

[ N queens problem and sort demo in Java ]

Abstract: We are developing a new problem-solving methodology based on a self-organization paradigm. To realize our future goal of self-organizing computational systems, we have to study computation based on local information and its emergent behavior, which are considered essential in self-organizing systems. This paper presents a stochastic (or nondeterministic) problem solving method using local operations and local evaluation functions. Several constraint satisfaction problems are solved and approximate solutions of several optimization problem are found by this method in polynomial order time in average.

Major features of this method are as follows. Problems can be solved using one or a few simple production rules and evaluation functions, both of which work locally, i.e., on a small number of objects. Local maxima of the sum of evaluation function values can sometimes be avoided. Limit cycles of execution can also be avoided. There are two methods for changing the locality of rules. The efficiency of searches and the possibility of falling into local maxima can be controlled by changing the locality.

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

Keywords: CCM, Constraint satisfaction problem, Emergent Computation, Randomized computation, Randomized problem solving, Rule-based computation, Rule-based problem solving, Local information, Localized computation, Stochastic process, Local evaluation function, Production system, Production rule

Post a comment


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