Research on A Computational Model for Emergent Computation

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].

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.

References

[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.