Current software development methods are mostly top-down and are based on a type of divide-and-concur method. Expert systems are developed in a more flexible way, but are essentially the same. They depend on the illusion that the system is reductionistic and can be divided into ``independent'' functional modules. Current methods assert that the complete specification can be described. However, it is impossible to describe when the systems include or are interfaced to autonomous and nondeterministic systems. The reductionistic programming paradigm has failed to develop real-world systems.
Thus, we must find another paradigm. A most promising solution is the self-organization paradigm. The self-organization paradigm holds that computational systems are constructed without a whole and complete plan of computation and that they work basically in a bottom-up manner using local information only but generating global results via emergent behavior [For 91]. Thus, they work autonomously and nondeterministically.
However, extensive research is required to establish a methodology based on self-organization paradigm. We are only beginning research on this topic. Our current major research target is to establish a bottom-up computation mechanism and methodology based on local information. This paper presents a computation model called the chemical casting model (CCM) for problem solving using randomized applications of local operations and local evaluation functions, gives an example, and analyzes them. A major feature of this problem-solving method is that 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. Constraint satisfaction problems, such as graph coloring or the N queens problem, are solved, or approximate solutions of optimization problems, such as traveling salesperson problems, are found by this method.
To clarify the meaning of local operations and local evaluation functions, a general framework of problem solving is briefly introduced. Problem solving, such as optimization or constraint satisfaction, can be regarded as a state-space search. The initial state represents the problem and the final state of a solution.[*1.1] A problem can be solved by moving the current state from the initial to final state by applying operators in an appropriate order. The operators may be local or global. A local operator works on a small number of elements in the current state and moves it to a similar state in the search space. A global operator, such as a crossover in genetic algorithms, works on all the elements in the current state and moves it to a quite different state. A search in CCM is a (not completely) randomized walk in a state-space using local operators.
Evaluation functions are used in several problem solving methods. They are not used in blind search methods, such as depth-first or random searches. Global evaluation functions are used in hill-climbing methods and genetic algorithms. ``Global'' means that the value of the evaluation depends on all the elements in the current state. Search methods that do not use evaluation functions are usually inefficient. However, it is not easy for humans to define global evaluation functions when the problem is complex or multi-purposed. The current state often falls into a local maximum by methods that use local operators and global evaluation functions, such as hill-climbing methods. Local evaluation functions bias the randomized walk in CCM.
The basic paradigm of self-organization, which is the philosophical basis of this work, is explained in Section 2. CCM is explained in Section 3. An example based on CCM, the N queens system, is given in Section 4. The characteristics of CCM-based systems are analyzed in Section 5. Related works are mentioned in Section 6. Finally, we summarize our conclusions.