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.