Salcido A. (ed.) Cellular Automata - Simplicity Behind Complexity

Подождите немного. Документ загружается.

CELLULAR AUTOMATA ͳ

SIMPLICITY BEHIND

COMPLEXITY

Edited by Alejandro Salcido

Cellular Automata - Simplicity Behind Complexity

Edited by Alejandro Salcido

Published by InTech

Janeza Trdine 9, 51000 Rijeka, Croatia

All chapters are Open Access articles distributed under the Creative Commons

Non Commercial Share Alike Attribution 3.0 license, which permits to copy,

distribute, transmit, and adapt the work in any medium, so long as the original

work is properly cited. After this work has been published by InTech, authors

have the right to republish it, in whole or part, in any publication of which they

are the author, and to make other personal use of the work. Any republication,

referencing or personal use of the work must explicitly identify the original source.

Statements and opinions expressed in the chapters are these of the individual contributors

and not necessarily those of the editors or publisher. No responsibility is accepted

for the accuracy of information contained in the published articles. The publisher

assumes no responsibility for any damage or injury to persons or property arising out

of the use of any materials, instructions, methods or ideas contained in the book.

Publishing Process Manager Iva Lipovic

Technical Editor Teodora Smiljanic

Cover Designer Martina Sirotic

Image Copyright Shebeko, 2010. Used under license from Shutterstock.com

First published March, 2011

Printed in India

A free online edition of this book is available at www.intechopen.com

Additional hard copies can be obtained from orders@intechweb.org

Cellular Automata - Simplicity Behind Complexity, Edited by Alejandro Salcido

p. cm.

ISBN 978-953-307-230-2

free online editions of InTech

Books and Journals can be found at

www.intechopen.com

Part 1

Chapter 1

Chapter 2

Chapter 3

Chapter 4

Chapter 5

Chapter 6

Chapter 7

Preface IX

Land Use and Population Dynamics 1

An Interactive Method to Dynamically

Create Transition Rules in a Land-use

Cellular Automata Model 3

Hasbani, J.-G., N. Wijesekara and D.J. Marceau

Cellular-Automata-Based Simulation

of the Settlement Development in Vienna 23

Reinhard Koenig and Daniela Mueller

Spatial Dynamic Modelling

of Deforestation in the Amazon 47

Arimatéa C. Ximenes, Cláudia M. Almeida,

Silvana Amaral, Maria Isabel S. Escada

and Ana Paula D. Aguiar

Spatial Optimization and Resource Allocation

in a Cellular Automata Framework 67

Epaminondas Sidiropoulos and Dimitrios Fotakis

CA City: Simulating Urban Growth

through the Application of Cellular Automata 87

Alison Heppenstall, Linda See,

Khalid Al-Ahmadi and Bokhwan Kim

Studies on Population Dynamics

Using Cellular Automata 105

Rosana Motta Jafelice and Patrícia Nunes da Silva

CA in Urban Systems and Ecology:

From Individual Behaviour to Transport

Equations and Population Dynamics 131

José Luis Puliafito

Contents

Dynamics of Traffic and Network Systems 157

Equilibrium Properties of the Cellular Automata

Models for Traffic Flow in a Single Lane 159

Alejandro Salcido

Cellular Automata for Traffic Modelling and Simulations

in a Situation of Evacuation from Disaster Areas 193

Kohei Arai, Tri Harsono and Achmad Basuki

Cellular Automata for Bus Dynamics 219

Ding-wei Huang and Wei-neng Huang

Application of Cellular Automaton Model

to Advanced Information Feedback

in Intelligent Transportation Systems 237

Chuanfei Dong and Binghong Wang

Network Systems Modelled

by Complex Cellular Automata Paradigm 259

Pawel Topa

Cellular Automata Modeling

of Biomolecular Networks 275

Danail Bonchev

Simulation of Qualitative Peculiarities of Capillary

System Regulation with Cellular Automata Models 301

G. Knyshov, Ie. Nastenko, V. Maksymenko and O. Kravchuk

Dynamics of Social and Economic Systems 321

Social Simulation Based on Cellular Automata:

Modeling Language Shifts 323

Francesc S. Beltran, Salvador Herrando, Violant Estreder,

Doris Ferreres, Marc-Antoni Adell and Marcos Ruiz-Soler

Cellular Automata Modelling

of the Diffusion of Innovations 337

Gergely Kocsis and Ferenc Kun

Cellular Automata based Artificial Financial Market 359

Jingyuan Ding

Some Results on Evolving Cellular Automata Applied

to the Production Scheduling Problem 377

Tadeusz Witkowski, Arkadiusz Antczak,

Paweł Antczak and Soliman Elzway

Part 2

Chapter 8

Chapter 9

Chapter 10

Chapter 11

Chapter 12

Chapter 13

Chapter 14

Part 3

Chapter 15

Chapter 16

Chapter 17

Chapter 18

Contents

VII

Statistical Physics and Complexity 399

Nonequilibrium Phase Transition of Elementary Cellular

Automata with a Single Conserved Quantity 401

Shinji Takesue

Cellular Automata – a Tool for Disorder,

Noise and Dissipation Investigations 419

W. Leoński and A. Kowalewska-Kudłaszyk

Cellular Automata Simulation

of Two-Layer Ising and Potts Models 439

Mehrdad Ghaemi

Propositional Proof Complexity and Cellular Automata 457

Stefano Cavagnetto

Biophysical Modeling using Cellular Automata 485

Bernhard Pfeifer

Visual Spike Processing based on Cellular Automaton 529

M. Rivas-Pérez, A. Linares-Barranco and G. Jiménez, A. Civit

Design and Implementation of CAOS: An Implicitly

Parallel Language for the High-Performance

Simulation of Cellular Automata 545

Clemens Grelck and Frank Penczek

Part 4

Chapter 19

Chapter 20

Chapter 21

Chapter 22

Chapter 23

Chapter 24

Chapter 25

Pref ac e

In the early 1950s, at the suggestion of Stanislaw Ulam, John Von Neumann introduced

the cellular automata as simple mathematical models to investigate self-organisation

and self-reproduction. Cellular automata make up a very important class of completely

discrete dynamical systems. The physical environment of cellular automata is consti-

tuted of a ﬁ nite-dimensional la ice, with each site having a ﬁ nite number of discrete

states. The evolution in time of a cellular automaton goes on in discrete steps, and its

dynamics is speciﬁ ed by some local transition rule, ﬁ xed and deﬁ nite. In spite of their

conceptual simplicity, which allows for an easiness of implementation for computer

simulation, and a detailed and complete mathematical analysis in principle, the cel-

lular automata systems are able to exhibit a wide variety of amazingly complex be-

havior. This feature of simplicity behind complexity of cellular automata has a racted

the researchers’ a ention from a wide range of divergent ﬁ elds of study of science,

which extends from the exact disciplines of mathematical physics up to the social ones,

and beyond. In fact, nowadays, cellular automata are a core subject in the sciences

of complexity. Thus, numerous complex systems containing many discrete elements

with local interactions, and their complex collective behaviour which emerge from the

interaction of a multitude of simple individuals, have been and are being conveniently

modelled as cellular automata. For example, the dynamical Ising model, gas and ﬂ uid

dynamics, traﬃ c ﬂ ow, various biological issues, growth of crystals, nonlinear chemical

systems, land use and population phenomena and many others. Moreover, cellular

automata are not the only models in natural sciences such as biology, chemistry and

physics, but they are also, thanks to their complete space-time and state discreteness,

appropriate models of parallel computation. Thus, cellular automata permit descrip-

tions of natural processes in computational terms (computational biology, computa-

tional physics), but also of computation in biological and physical terms (artiﬁ cial life,

physics of computation).

In this book the versatility of cellular automata for modelling a wide diversity of com-

plex systems is underlined through the study of a number of outstanding problems

with the cellular automata innovative techniques. This book comprises twenty ﬁ ve

contributions organized in four main sections: Land Use and Populations Dynamics; Dy-

namics of Traﬃ c and Network Systems; Dynamics of Social and Economic Systems; and Statis-

tical Physics and Complexity. Brief descriptions of the book chapters are presented in the

following paragraphs.

Land Use and Populations Dynamics. Chapter 1 describes a semi-automated, inter-

active method that was designed and implemented to dynamically create transition

Preface

rules and calibrate a land-use CA model. The proposed method combines the beneﬁ ts

of conditional and mathematical rules and is adaptable in terms of number of land-

use classes, and spatial and temporal scale of the input data. Chapter 2 presents and

describes a cellular automata model for simulating the population distribution of the

city of Vienna from 1888 to 2001. It has also developed a sensible and robust concept

for the explanation of the driving forces of urban development processes, and it was

shown that the development of the population density can be essentially regulated

by infrastructure investments. In Chapter 3, the deforestation processes in a region

called São Félix do Xingu, located in east-central Amazon, are simulated with a cellular

automata model called Dinamica EGO. It consists of an environment that embodies

neighbourhood-based transition algorithms and spatial feedback approaches in a sto-

chastic multi-step simulation framework. The modelling experiment demonstrated the

suitability of the adopted model to simulate processes of forest conversion, unravelling

the relationships between site a ributes and deforestation in the area under analysis.

Chapter 4 demonstrates that the heuristic search methods for the solution of spatial

optimization problems have to be designed in accordance with the spatial character of

the ﬁ eld under study, which can be ﬁ  ingly modelled by means of cellular automata.

Two basic approaches are presented in this chapter to pursue a balance between local

and global characteristics. Chapter 5 demonstrates the potential of cellular automata

as a tool for urban planning and development using two models and case studies, one

from Saudi Arabia and the other from the Republic of Korea. The strengths and weak-

nesses of the models are discussed, including areas for further development. Chapter 6

presents three cellular automata that simulate the behavior of the population dynamics

of three biological systems. The ﬁrst one deals with artiﬁcially-living ﬁsh divided into

two groups: sharks (predators) and ﬁsh that are part of their food chain (preys). The

second model introduces a simulation of the HIV evolution in the blood stream of posi-

tive individuals with no antiretroviral therapy. The last model extends the previous

one and considers the HIV dynamics in individuals subject to medical treatment and

the monitoring of the medication potency and treatment adhesion. Finally, Chapter 7

explores some of the fundaments of cellular automata models and the reasons why

these are being so widely applied nowadays, particularly to urban systems and ecol-

ogy, all of which seem to be connected directly to the fact that the transport equations

are common as much to the socioeconomic phenomena as to physics.

Dynamics of Traﬃ c and Network Systems. Chapter 8 presents an overview of the ba-

sic cellular automata models for traﬃ c ﬂ ow. A maximum entropy approach for analyz-

ing the equilibrium properties of the cellular automata models for multi-speed traﬃ c

ﬂ ow in a single lane highway is also proposed and discussed. It is shown, in particular,

that the traﬃ c cellular automata models of Nagel-Schreckenberg and Fukui-Ishibashi

evolve rapidly towards steady states very close to equilibrium. In Chapter 9, a modiﬁ ed

model of the car-following Nagel-Schreckenberg model is proposed by incorporating

the agent and diligent driver into it. The modiﬁ ed evaluation of the proposed param-

eter, the fundamental diagram, spatio-temporal pa erns, eﬀ ect of lane-changing and

car-following with respect to the evacuation time, combination parameter of diligent

and agent driver in the case of evacuation time and the eﬀ ectiveness are investigated.

Chapter 10 presents a simple cellular automaton model to study the typical bus dynam-

ics in a modern city. At a ﬁrst stage, the nontrivial ﬂuctuations are prescribed by the

stochastic moving of bus interacted with the stochastic arrival of passengers, and at a

second stage, the bus schedule interrupted by the traﬃ c lights is examined. The city