Cellular Automata

History

The mathematical description of CA was partially postulated by D'Arcy Thompson (1917), then further developed by Von Neumann (1966) in his work on self-reproducing systems. The work of Von Neumann was motivated by Alan Turing's groundbreaking developments in algorithms and digital computing as well as Stanislaw Ulam's work on the growth of crystals in the 1940s and 1950s. CA concepts were further explored by Conway's Game of Life and popularized by Gardner in a 1970 article published in the journal Scientific American. Later, CA studies were linked to the theory of complex systems and were further elaborated by Wolfram (1984). Since then, CA theory and applications have gained rapid popularity in various scientific fields, such as physics, medicine, chemistry, biology, ecology, forestry, geography, and atmospheric and Earth sciences, among others.

Mathematical Formalism

The main components of CA are the cell spaces represented by a regular grid; cell states, S; neighborhood of the cell, N; functions of cell transition rules, R; and discrete time increments, ?T. The cell state S(x, y)T at time T can be represented as function F depending on CA elements at previous time T − 1 and can be formalized as

where S(x, y)T-1 is the cell state at location (x, y).

Each discrete time step represents the CA model iteration. During the iteration, an update of the state of each cell in the grid is provided using transition rules and the states of other cells in its local neighborhood. Figure 1 shows the various types of neighborhoods used in the CA modeling procedures. The Von Neumann, Moore, extended Moore, displaced von Neumann, Moore von Neumann, and H neighborhoods are the more popular ones that are used in modeling studies. The shape and the size of the neighborhoods may vary, from those with symmetric, asymmetric, rectangular, and circular shapes and distinct values to those that consider cells from different locations in the neighborhoods with gradual values of different importance based on distance-distance decay of a given variable.

The transition rules form an important part of the CA model. They define the way in which the cell will develop over time and hence mimic the overall change process of the cells over space and [Page 370]time. The rules can be deterministic, probabilistic, stochastic, or fuzzy and, therefore, imply a bottom-up modeling process from the local scale to global scales. The model calibration and validation procedures are key phases of the CA model development. Calibration and validation allow fine tuning of the model parameters, and model testing determines how closely the final model can simulate or represent the spatial patterns found in the real world.

Cellular Automata and Geography

Geographic phenomena are inherently dynamic and complex and can therefore be studied using complex systems theory. During the geographic change process, elements of the system may evolve, interact, and bifurcate over space and time. These interactions are usually nonlinear and self-organizational, so CA theory is suitable to represent them.

...