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

Masao Hirokawa
Advanced Research Laboratory, Hitachi Ltd.
Hatoyama, Saitama 350-03, Japan
E-mail: hirokawa@arl.hitachi.co.jp

This paper is a hypertext version of the following paper:
Y. Kanada, and M. Hirokawa: Stochastic Problem Solving by Local Computation based on Self-organization Paradigm, IEEE 27th Hawaii International Conference on System Sciences, pp. 82-91, 1994.

Notes

• Some of the figures in this paper were inaccessible or unavailable until recently. Sorry. Now all of them are accessible.
• Postscript version is here

Abstract

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.

Contents

• 1. Introduction
• 2. The Basic Paradigm of Self-organization
• 3. Computation Model CCM
  • 3.1 Working Memory and Data
  • 3.2 Reaction Rules
  • 3.3 Local Order Degrees
  • 3.4 Scheduling Strategies
• 4. Example: The N Queens Problem
  • 4.1 Reaction rule and local order degree
  • 4.2 Performance
  • 4.3 Other Examples
• 5. Characteristics of CCM-based Computation
  • 5.1 Global Order Degree and its Stochastic Process
  • 5.2 Conflict and Cooperation in CCM
  • 5.3 Variability of Locality
  • 5.4 Escaping from Local Maxima
• 6. Related Work
• 7. Concluding Remarks
• Acknowledgments
• References