 |
|
ISSN 1320-0682 | ||||
| Volume 3 | April 1996 | ||||
Tokufumi Yamamoto
We constructed cellular automata (CA) with heterogenous rules that interact with each other. This model showed the different patterns in the landscape under some conditions. Although the model is constructed only by deterministic rules except an initial condition, chaotic as well as ordered states can co-exist in the process of evolution. This outcome suggests to us that the set of heterogeneous rules in the model is essential to construct complex systems without random noise, in order to demonstrate the behaviour of complex systems.
The problem often encountered in complex systems research is the difficulty of detecting the precise mechanism that alters the system's state from chaotic to ordered state or vice versa. This difficulty frequently forces us to have the idea that, in complex systems, there is a deterministic mechanism and random noise. This perspective gives us a fairly plausible idea; that is, there are order and chaos in the world which produce complexity. This hypothesis, however, relies on the belief that it is possible to bisect the system into the part that is totally regulated and organised, and noise [7]. In other words, this assumption claims that complexity is the mixture of chaos and order. Although no theorists claim that complexity is a simple mixture of chaos and order [9], it is hard, in literature, to distinguish the above claim from the claim that complexity is between chaos and order. As a matter of fact, it has not been examined whether complexity is really the mixture of chaos and order.
The intuition that complexity may well be the mixture of order and chaos, consequently forces us to make the model, in order to simulate complex systems, consisting of a combination of deterministic mechanisms and random functions. This plot is so prevalently used that we are hardly aware of the fact that most of the simulations of complex systems we have made belong to this type. However, it is too early to assert that all the behaviours of complex system originate from the combination of deterministic mechanism and unpredictable noise.
Until the advent of the theory of deterministic chaos, it has been said that if unpredictable noise was removed from the data, we could reveal the deterministic mechanism. In other words, the idealised condition can be defined as a limit of the sequence of imaginary systems with less and less noise. This argument, however, cannot be carried out for describing complex systems, since we have no way of knowing whether the small fluctuation is really noise or not. For example, in population dynamics, most people used to believe that the fluctuation in the population of wild species originated from external factors such as weather, food supply and so forth. It was then found that even if the external factors are kept constant, still the population fluctuates [13]. This implies that the dynamics must have an intrinsic force to fluctuate.
Regarding these circumstances, it is natural for many researchers to focus on heterogeneity in complex systems - for example, in ecosystem [12], [4]. Constructing the model consisting of the heterogeneous structure has a significant advantage over the model made by the combination of order and random noise, because the latter always leaves something unexplained as noise, while the former can possibly demonstrate what happens in complex systems.
In the following section, the details of the model construction are discussed. The implementation of the model is then formalised. Next, the results from our model are shown and the discussion of the results is presented, as compared with the results from other related simulations.
It is evident in ecosystem or economic activity that the different agents use the different strategy to get ahead of others. Although altruism is the way to help others in a community, it is also the way to overcome predators [11]. The agents can think of the strategy that the others never think of [1]. These situations have been implemented on many computer simulations such as "prisoners' dilemma" or genetic algorithm (GA) [5]. However, it is important to be aware of the fact that in GAs, the solution is obtained by an accident (mutation) or given by others (crossover at reproduction). Moreover, crossover can be interpreted as another version of mutation since, in most GAs, the point where the crossover happens is determined randomly. Thus, GA feeds the power of evolution from randomness. Although this architecture of GAs has been considered as successful for problem-solving architecture, there are some doubts about using them as a simulation of evolutionary process.
Procedures in GAs that rely on randomness may not be able to model evolution since there have been found a number of facts that show that the mutation can happen in a specific direction to adapt to environments quickly [2]. For a similar reason, they may not be appropriate to model ecosystems, because strategy for survival is not entirely acquired by accidents. In other words, the basic GA architecture lacks the ability to understand environments. Although there may be many issues for directed mutation to be proved [3], it is crucial to pay attention to the fact that adaptation happens quicker than random searching.
In principle, one needs to understand the environment to find a relationship between cause and effect that are seen in a neighbourhood. However, it is never easy in complex systems, to identify the deterministic functions that always yield one-to-one mapping between cause and effect. If the definite rule possible is required, then it is desired that different causes have different effects, because when all the different causes yield different effects, it would be said that the rule to describe the event is deterministic.
In reality, however, we do not always have an ideal situation to find the deterministic function, especially in complex systems, since the connection between the elements is too complicated and an error in measurement or noise in the data is inevitable; sometimes it is impossible to sort out the responsible causal relationship. As a result of this difficulty, misunderstanding would happen both inside and outside the system concerned. What we have to be careful about is that misunderstanding happens in the description by the observer outside the system and observation between the agents in the system. In economics, for example, this kind of misunderstanding happens in the form of misforecast by the manager of a company or bank, as well as in the description by an economist [8]. It is an everyday event not only for the manager of banks and companies to miscalculate the move of the price or act of consumers, but also for the economist to predict the trends in economics at large.
To improve the model - in other words, to employ more and more parameters in the model - relies on the belief that the different effects must have different causes, because increase of the degree of freedom in the system would enable the observer to define the deterministic function for the system's behaviour that used to seem unpredictable. One might think that if the agents had the infinite degree of accuracy in their measurement, all misunderstanding would disappear and they would have the unique description of the model. This kind of argument, however, simply ignores the upper bound of the energy available per agent to perform the measurements [14]. Also, in an ecosystem, it is not wise to observe the environment, such as weather or predators' behaviour, with an infinite accuracy because such ultimate observation, even if it were possible, must have an excessive amount of unnecessary information. Living things then have to survive, since the compromising of accuracy of measurement and the taking of risks is required in order to save energy consumption.
By the decision made from an imprecise measurement, it seems as if the different outcomes are produced by the same input. To be precise, in the short-term, the system behaves deterministically, but randomly in a long-run. This is, in fact, the informal definition of chaos. The problem then is how to implement this mechanism into formal computing. As long as the short-term behaviour is deterministic, the rule that produces the immediate outcome must be deterministic. However, in order to have chaotic behaviour, that rule must change. To do this, there are some different methods [17]. Here, the neighbours' behaviours are employed to change the rule. The agents in ecosystems, economics and related systems are not interacted with all the others in the system, but certainly interacted with others nearby. The agents in some regions then reached agreement on strategy or behaviour (that is, reached an attractor in a dynamics term), while they found different agreements in different parts in the landscape.
The crucial issue here is the inconsistency in the individual's behaviour that seems to preduce different outcomes for the same input once in a while [6]. Our aim is not to model a particular real system, but to demonstrate the individual's behaviour when the individual does not know what happens in their vicinity. In the following section, we formalise this evolution process with changes of rule in 2-D cellular automata.
CA is a simple computation template that is capable of producing complex behaviour [15]. Here, we define the CA rules briefly, and formulate the rule replacement procedure used in our system.
Time evolution is defined only by the number of the living cells surrounding
(a "totalistic rule" [10]).
Here, the living cells are denoted by 1; "dead" by 0.
Formally, regarding
, as the
finite set of the state of a cell at (t )-th step with a location at (i,
j ) in a 2-D grid and an index of configuration,
as the number
of the living cells surrounding the cell concerned, the function for time
evolution, F, is
where is
defined by
The cell's state at (t+1 )-th step is determined by
whereas the subscripts i and j indicate that this can vary from one location to another. This F, consisting of ten sub-rules, is the set that each cell has. We write these sub-rules, f , by
The rule replacement is performed between these f 's. In order to decide whether a sub-rule is changed, we define the number of incidents that the sub-rule yields the same outcome from the different configuration. This number is defined by
where T(P) is a truth function that gives 1 when P is true, 0
otherwise. Since
, changing
f is interpreted as a negation of fs. In this formula, k is a
scope of the observation. This means the cell can see (uk +1) cells
surrounding, including itself. The results shown in the paper have been obtained
from the system with k=1.
Regarding the
at t-th
step 
,
replacement of the rules is defined by
In the formula (6), h determines how many different outcomes from the same input are ignored. For a low h, the rules are replaced more frequently than they are for a high h. This is, however, not a precise explanation of the role of h, because the number of the same outcomes from the different configurations is compensated by the number of the different outcomes from the different configurations in Equation (5). In other words, if there are more incidents from the same outcome from different configurations than incidents from different outcomes from different configurations, then the rule that leads the outcome is subject to change. This completes the definition of the model.
Usually, prime numbers are used for the size of the system in order to avoid a periodic behaviour, since the rule for updating cells states and the procedure for replacement of rules depends on 3 by 3 grid and (2k +1) by (2k +1) grid, respectively. Initial conditions for the cells states and sub-rules are random, which is the only random function in this model. Randomly distributed initial condition is supposed to give the minimum information structure or gradient at the initial stage. A periodic boundary condition has been used. This prevents the system from receiving any information and energy supplies from outside during the time evolution.
One of the measurements to detect the complexity is entropy. In this paper, spatial measure entropy is used to measure the complexity of the system's behaviour. Spatial measure entropy is defined in general form in [10]. The specific definition for 2-D CA is found in [18]
Figure 1 shows the landscape of the system with h = 0. Four pictures in the upper row of the figure show the time evolution of the configuration of the cells' state; state 1 cells are shown as dots, and state 0 cells blank. In the lower row, the stable cells that showed the same state, whichever 1 or 0, for the last five or more steps, are shown as dots, blank otherwise. These two rows correspond vertically. These pictures clearly show that the degree of order increases as the system develops. The stable area, which has a stripe pattern in the upper row pictures, gradually spreads its territory. Between these stable regions, there are unstable chaotic regions. The chaotic behaviour between the stripe pattern, however, does not last long. As the stripe pattern spreads, the chaotic behaviour is confined between the stable region, then there remains only threads of chaotic behaviour. This seems to be some kind of crystallisation. But this crystallisation does not stop there. Two different kinds of stripe patterns, which are horizontal and vertical patterns, still contest to gain larger and larger territory of their own. However, this conflict ends soon because the system size is small. Since the stripe pattern has period two in space, the chaotic thread cannot be removed entirely, if the system size is not a multiple of two. When the system has a size of 47, as seen in Figure 1, the chaotic region, that seems like a crack in the stripe pattern, remains.
Figure 1: The landscape of 2-D CA with heterogeneous rules. In
the upper row, the configuration of living cells is shown as dots. The
distribution of stable cells is shown in the lower row. System Size is 47 by 47.
Figure 2: Spatial measure entropy in the 2-D CA with
heterogeneous rules.
Spatial measure entropy is plotted in Figure 2. The diagram shows a relatively smooth decrease in entropy, compared to CA with a homogeneous rule. Rapid decrease in entropy can be seen in class I and II CA in Wolfram's classification [16]. Class I CA, however, shows a very steep decrease in entropy; usually a few steps brings it to 0. Class II CA, on the other hand, shows a relatively gradual decrease, compared to Class I, but in most cases it is accompanied by a heavy fluctuation because many Class II CAs have periodic behaviours. In our system, fluctuations cannot be seen very much. This probably relies on the fact that the chaotic behaviour is enclosed in a limited region between stable patterns and that the rule replacement happens mostly outside the stable region.
When the values of h are changed, our model exhibits different behaviours. This can be seen in Figure 3. It is easy to detect that complexity of the pattern that emerged in the system varies with different values of h. It seems that the size of the crystallised pattern decreases as the value of h decreases.
Figure 3: The landscapes after 5,000 steps. The systems with
the low h values still show chaotic behaviours, while the high h
show stable states.
Figure 4: The distribution of cluster size and frequency taken
from the system with h =-6 and k =1 for 2369 steps. The
distribution is very close to the lognormal structure.
Interestingly, the relation between cluster size and frequency in the model approximately shows a lognormal distribution, as seen in Figure 4. This implies that the system's behaviour is highly structured, although it seems to be very complex. It is encouraging to have this outcome because we have made different models that showed the same structure [17], [18].
Firstly, the question is what does the result that shows more diverse patterns that appeared in the system with a low h value mean? Having paid attention to the condition that the high h value means that the fewer differences between adjacent cells cause the cell to change its rule, there must be more rule replacements between elements in the high h model than that of low h . On the other hand, with a low h value model, there are less rule changes between neighbours. It seems that the value of h roughly corresponds to the accuracy of measurement. In the model with low h, it would be said that the agents in the system ignore small amounts of disagreement between neighbours. On the other hand, the agents are relatively sensitive to the different behaviour of their neighbours in the high h model.
In a sense, we have seen a similar result to the spatialised prisoners' dilemma model [11]. In their model, it has been observed that pure defectors and pure co-operators co-exist in a different location when the interaction is restricted within adjacent neighbours. This co-existence roughly corresponds to the landscape with many different patterns in our model.
In our model, the condition (6) decides the fixed point of the behaviour, which is obtained when neither of the cells state and rules change. As a result, we have seen a stripe pattern in the landscape. However, this stripe pattern is not the most stable configuration, because there are two different configurations in the 3 by 3 grid. Ultimately, when all the cells have the same state, the system has the most stable pattern, since Equation (6) ignores the cells that are surrounded by the same configuration. This means that when the adjacent configurations are different, as in the stripe pattern, there is a possibility of rule replacement. The fact that the system does not show the most stable state implies that the system has to have the opportunity to evolve rather than settling down at the most stable state. As a result, the system cannot reach the most stable state.
This fact has a significant implication for evolutionary systems; that is, in order to evolve, the system has to be out of the fixed point in a dynamics term. Consequently, the system has to fail or make a mistake in order to evolve. This sounds trivial; however, the implication is that the evolutionary system has to have a mechanism to keep away from the stable state. In most GAs, this mechanism is simulated annealing that puts that system from the local minimum. However, what we have to find out is, the mechanism that keeps the system away from a fixed point, not employing ad hoc external perturbations like simulated annealing.
The idea behind the condition formalised as (6) was to make a one-to-one mapping between a pair of time slices. When the outcomes fail to construct the one-to-one mapping, the rules associated with that mapping are changed. Since the cell has only two states, in order to accomplish the one-to-one mapping between any time slices, the domain of the function has to have only two states as well.
This model is potentially a prototype to simulate the systems which has a heterogeneous structure, including ecosystem, linguistic system, economics and related complex systems. These fundamental, abstract models will reveal the way to deal with complex systems that have been observed broadly in nature. We believe that heterogeneous rules that interact with each other and sometimes even contradict themselves, have the key to describing the systems that are so intricate that we have considered them as a concoction of deterministic mechanism and unpredictable noise.
The author is grateful to Professor David G. Green for his comments on the manuscript at various stages. The models were implemented on the Connection Machine at South Australian Centre for Parallel Computing (formerly NSW Centre for Parallel Computing). Dr Russell K. Standish gave important suggestions in using the machine.
Order and Disorder in 2-D Cellular Automata with Heterogeneous Rules
This document was generated using the LaTeX2HTML translator Version 96.1 (Feb 5, 1996) Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html yamamoto.
The translation was initiated by Pam Milliken on Fri Jan 17 17:02:04 EST 1997