Created: 5/11/1995, Modified: 10/19/2003.

This brief report is part of a preliminary version of the 1995 RWC Symposium Report.

**See also**:
[Parent page (CCM home page)].
[Kanada's home page in English],
[Kanada's home page in Japanese].

Emergent computation is computation that only uses local information and that generates global and maybe partially inestimable result. Emergent computation is expected to make flexible computation with incomplete and time-varying information possible.

We have been developing a model for emergent and evolutionary
computation. This model is called
Chemical Casting Model (CCM)
[Kan 94a]. CCM is based on a so-called production system, which is usually
used for developing expert systems. However, CCM is analogous to
chemical reaction systems. The behavior of CCM-based systems is
controlled by *reaction rules*
(or forward-chaining production rules) and evaluation functions,
which is called *local order degrees* (LODs). Both
reaction rules and LODs work with local information, i.e., a small number of
data.

CCM has been applied to combinatorial problem solving, such as the *N*
queens problem [Kan 94a], graph/map coloring problems [Kan 95a] or
integer programming problems. Each problem can be solved using only one
reaction rule and one LOD, and the performance is much better than simple
branch-and-bound method. If the problem or environment is varied while or
after solving it, the system usually finds a new solution.

Recent research results are as follows. Firstly, Performance of constraint satisfaction, such as graph coloring, has been proved to be improved by the frustration accumulation method (FAM) [Kan 94b]. FAM is a method similar to simulated annealing but only uses local information. The performance is comparable to GSAT [Sel 92] in large-scale graph coloring problems [Kan 95c].

Secondly, CCM-based computation has been proved to be accelerated by
parallel processing by the following two methods. One is the *independent
parallel search method* [Kan 94c, Kan 95b]. A parallel computer
with *M*
processors is used in this method. The same set of reaction rules and LODs
are used in each processor, and the same or different initial data is used.
Even if the same data is used, the execution speed is improved nearly *M*
times under certain conditions. The performance of the *N*
queens problem is improved on the
Cray
Superserver 6400. The other method of parallel
processing is the *parallel reaction method* [Kan 95c].
This method enables
parallel processing with little mutual exclusion, which causes performance
degradation. The performance of graph coloring problems is improved on the
CS6400.

- [Kan 94a] Kanada, Y., and Hirokawa, M.: Stochastic Problem Solving by Local Computation based on Self-organization Paradigm, 27th Hawaii Int. Conf. on System Sciences, 82-91, 1994.
- [Kan 94b] Kanada, Y.: Methods of Controling Locality in Problem Solving using CCM: A Model for Emergent Computation, SWoPP '94, 94-AI-95-4, 29-38, 1994 (in Japanese).
- [Kan 94c] Kanada, Y.: A Method of Independent Parallel Processing of Constraint Satisfaction and Other Problems using CCM: A Model for Emergent Computation, 49th National Conference, Information Processing Society of Japan, 4-321 - 322, 1994 (in Japanese).
- [Kan 95a] Kanada, Y.: Fuzzy Constraint Satisfaction Using CCM -- A Local Information Based Computation Model, FUZZ-IEEE/IFES '95, 2319-2326, 1995.
- [Kan 95b] Kanada, Y.: Parallel Processing Method Local-Information-Based Stochastic Combinatorial Problem Solving, submitted for SuperComputing '95.
- [Kan 95c] Kanada, Y.: Constraint Satisfaction by Parallel Optimization of Local Evaluation Functions with Annealing, to be submitted.
- [Sel 92] Selman, B., Levesque, H. J., and Mitchell, D. G.: A New Method of Solving Hard Satisfiability Problems, AAAI '92, 440-446, 1992.

Y. Kanada (Send comments to kanada @ trc.rwcp.or.jp)