Simulating Complex Systems by Cellular Automata

✍ Scribed by Hoekstra, Alfons G(Editor);Sloot, Peter M A(Editor);Hoekstra, Alfons(Editor)

• Publisher: Springer
• Year: 2010
• Tongue: English
• Leaves: 392
• Series: Understanding Complex Systems 0
• Category: Library

✦ Synopsis

Deeply rooted in fundamental research in Mathematics and Computer Science, Cellular Automata (CA) are recognized as an intuitive modeling paradigm for Complex Systems. Already very basic CA, with extremely simple micro dynamics such as the Game of Life, show an almost endless display of complex emergent behavior. Conversely, CA can also be designed to produce a desired emergent behavior, using either theoretical methodologies or evolutionary techniques. Meanwhile, beyond the original realm of applications - Physics, Computer Science, and Mathematics CA have also become work horses in very different disciplines such as epidemiology, immunology, sociology, and finance. In this context of fast and impressive progress, spurred further by the enormous attraction these topics have on students, this book emerges as a welcome overview of the field for its practitioners, as well as a good starting point for detailed study on the graduate and post-graduate level. The book contains three parts, two major parts on theory and applications, and a smaller part on software. The theory part contains fundamental chapters on how to design and/or apply CA for many different areas. In the applications part a number of representative examples of really using CA in a broad range of disciplines is provided - this part will give the reader a good idea of the real strength of this kind of modeling as well as the incentive to apply CA in their own field of study. Finally, we included a smaller section on software, to highlight the important work that has been done to create high quality problem solving environments that allow to quickly and relatively easily implement a CA model and run simulations, both on the desktop and if needed, on High Performance Computing infrastructures."

✦ Table of Contents

Cover......Page 1
Foreword......Page 7
Preface......Page 10
Acknowledgements......Page 13
Contents......Page 14
Contributors......Page 16
Alfons G. Hoekstra, Jirí Kroc, and Peter M.A. Sloot......Page 19
1.2 Modeling......Page 20
1.3 Complex Systems......Page 21
1.4 Cellular Automata......Page 23
1.5 Classical Cellular Automata......Page 24
1.6 The Game of Life......Page 28
1.7 Advanced Cellular Automata......Page 30
1.8 Book Organization......Page 31
References......Page 33
Part I Theory of Cellular Automata......Page 35
2.1 Introduction: ``one more soul''......Page 36
2.2 Modeling Bioinformatic Systems......Page 37
2.3 Multiscale Processes in Standard CA Models: Examples from Ecology......Page 38
2.4 Emergent Microscale Entities in Evolutionary CA Models: An Example......Page 39
2.5 Evolutionary CA and Evolutionary Computation......Page 43
References......Page 44
3.1.1 Introduction......Page 46
3.2.1 A Definition......Page 48
3.2.2 The Scale Separation Map......Page 49
3.2.3 The Sub-Model Execution Loop......Page 53
3.2.4 CxA Multi-scale Coupling......Page 54
3.2.5 Multiscale Modeling Strategies......Page 56
3.2.6 Execution Model......Page 57
3.2.7 Formalism......Page 63
3.2.8 Scale-Splitting Error......Page 66
3.3.1 Reaction Diffusion......Page 67
3.3.2 In Stent Restenosis......Page 71
References......Page 73
4.1 Introduction......Page 75
4.2 Structure of Hierarchical CA......Page 76
4.2.1 Isotropic Propagation and CA......Page 77
4.2.2 Structural Definitions......Page 82
4.2.3 Building Structures with Heterogeneous Data......Page 84
4.3 Behaviour of Hierarchical CA......Page 87
4.3.1 A Probabilistic Update Method......Page 88
4.3.2 Processes with Heterogeneous Behaviour......Page 91
4.4 Discussion and Summary......Page 93
References......Page 95
5.1 Introduction......Page 97
5.2 Main Concepts and Formal Problem Statement......Page 99
5.2.1 Formal Definition of a CA-model......Page 100
5.2.2 Correctness of CA Simulation Process......Page 104
5.2.3 Operations on Cellular Arrays......Page 105
5.3.1 Global Superposition......Page 109
5.3.2 Local Superposition......Page 114
5.4 The Parallel Composition Techniques......Page 116
5.4.1 Global Parallel Composition......Page 117
5.4.2 Local Parallel Composition......Page 119
5.4.3 Mixed Composition......Page 121
5.5.1 Accuracy of the Composed CA......Page 123
5.5.2 CA Composition Stability......Page 125
5.5.3 Composition Complexity......Page 128
References......Page 129
6.1 Introduction......Page 132
6.2 One-Bit-Communication Cellular Automata......Page 133
6.3.1 FSSP with a General at One End......Page 134
6.3.2 Generalized FSSP with a General at an Arbitrary Point......Page 139
6.4 Prime Sequence Generation Problem......Page 142
6.5 Early Bird Problem......Page 145
6.6.1 Synchronization Algorithm on Square Arrays......Page 148
6.6.2 Synchronization Algorithm on Rectangle Arrays......Page 149
6.7.2 Parallel Shrinking Transformation......Page 151
6.7.3 One-Bit Implementation of Connectivity-Preserving Transformation......Page 153
References......Page 157
7.1 Introduction......Page 160
7.2 Cellular Automaton Model......Page 162
7.3 Mutualism......Page 163
7.5 Parasitism......Page 167
7.6 Competition......Page 172
7.7 Discussion......Page 175
References......Page 178
8.1.1 Representation......Page 181
8.1.3 The Evolutionary Cycle......Page 182
8.2 Cellular Evolutionary Algorithms......Page 183
8.2.2 Brief Historical Background......Page 185
8.3 Selection Pressure......Page 186
8.3.2 Asynchronous Updating......Page 187
8.3.3 Mathematical Models......Page 188
8.3.4 Experimental Validation......Page 192
8.4 Benchmarking CEAs......Page 196
8.4.1 The Algorithm......Page 197
8.4.2 Test Suite: Discrete Optimization Problems......Page 198
8.5 CEAs and Real-World Problem Solving......Page 202
8.5.1 Vehicle Routing Problem......Page 203
8.6 Conclusions......Page 204
References......Page 205
Zhijian Pan and James A. Reggia......Page 206
9.2 Universal Constructors in CA Spaces......Page 207
9.3 Self-Replicating Loops......Page 208
9.4 Evolution of CA Rules......Page 211
9.5 Evolution of Self-Replicating Structure Using Genetic Programming......Page 212
9.5.1 S-tree Encoding and General Structure Representation......Page 213
9.5.2 R-tree Encoding and Rule Set Representation......Page 214
9.5.3 Genetic Programming with S-tree and R-tree Encoding......Page 218
9.5.4 The Replicator Factory Model and Experimental Results......Page 222
9.6 Discussion......Page 226
References......Page 228
Part II Applications of Cellular Automata......Page 230
10.1 Introduction......Page 231
10.1.1 Migration, Game Theory, and Cooperation......Page 232
10.1.2 Co-evolution of Social Structure and Cooperation......Page 233
10.2.1 Classification......Page 234
10.2.2 Individual Decision Making and Migration......Page 235
10.2.3 Learning......Page 237
10.3.1 Spontaneous Pattern Formation and Population Structure......Page 238
10.3.2 Promotion of Cooperation in the Prisoner's Dilemma......Page 241
10.4 Conclusions......Page 249
References......Page 250
11.1 Introduction......Page 252
11.2.1 Thermodynamics of the Fluid......Page 254
11.3 Hydrodynamics of the Fluid......Page 257
11.4 The Lattice Boltzmann Algorithm......Page 258
11.4.1 The Multiple Relaxation Time Algorithm......Page 261
11.4.2 Boundary Conditions......Page 263
11.5.1 Capillary Filling......Page 266
11.5.2 Viscous Fingering......Page 269
11.6 Chemical Patterning......Page 270
11.6.1 Spreading on a Chemically Striped Surface......Page 271
11.6.2 Using Chemical Patterning to Control Drop Positioning......Page 272
11.6.3 Using Chemical Patterning to Sort Drop by Size......Page 273
11.7 Topographical Patterning: Superhydrophobic Surfaces......Page 274
11.7.1 Contact Line Pinning and Contact Angle Hysteresis......Page 276
11.7.2 The Slip Length of Superhydrophobic Surfaces......Page 278
11.7.3 The Transition from the Suspended to the Collapsed State on Superhydrophobic Surfaces......Page 280
11.8 Discussion......Page 282
References......Page 283
12.1 Introduction......Page 286
12.2 A Model of Unidirectional Traffic on a Single-Lane Ant Trail......Page 287
12.2.1 Computer Simulation Results......Page 289
12.2.2 Analytical Results......Page 291
12.3.1 Experimental Setup......Page 296
12.3.2 Observations......Page 297
12.4.1 Extensions of the Uni-Directional Model......Page 299
12.5 A Model of Bidirectional Traffic on a Single-Lane Ant Trail......Page 301
12.6 Empirical Results......Page 305
12.7 Concluding Discussions......Page 309
References......Page 310
13.1 Introduction......Page 312
13.2 Lattice-Gas Cellular Automata......Page 314
13.2.1 Dynamics in Lattice-Gas Cellular Automata......Page 315
13.3.1 Definition of the LGCA Model......Page 317
13.3.2 Microdynamical Equations......Page 318
13.3.3 Simulations......Page 319
13.4.2 Macroscopic Dynamics......Page 321
13.4.3 Traveling Front Analysis......Page 324
13.5.1 Cell Migration Strategies......Page 326
13.5.2 LGCA Models of Cell Motion in a Static Environment......Page 327
13.5.4 Model II......Page 328
13.6 Analysis of the LGCA Models for Motion in Static Environments......Page 332
13.6.1 Model I......Page 333
13.6.2 Model II......Page 336
13.7 Discussion......Page 338
References......Page 341
14.1 Introduction......Page 343
14.2.1 Truss Domain......Page 346
14.2.2 Isotropic Continuum Domain......Page 347
14.3.1 Truss Structures......Page 349
14.3.2 Isotropic Continuum Structures......Page 350
14.3.3 Composite Lamina Continuum Structures......Page 351
14.4.2 Continuum Structures......Page 352
14.4.3 Composite Lamina Continuum Structures......Page 354
14.5.1 Truss Structures......Page 355
14.5.2 Continuum Structures......Page 356
14.6.1 Example 1: 2-D Plate Topology Design......Page 357
14.6.2 Example 2: 2- and 3-D Compression Bridge......Page 359
14.6.3 Example 3: Fiber Reinforce Cantilever Plate......Page 360
References......Page 362
Part III Cellular Automata Software......Page 364
15.1 Introduction......Page 365
15.2 Cellular Automata Systems......Page 366
15.3 Parallel CA Languages......Page 373
15.3.1 Programming Approach......Page 374
15.3.4 Neighborhood......Page 375
15.3.6 CA Mapping......Page 376
15.4 Cellular Automata Based Problem-Solving Environment Case Study: CAMELot and CARPET......Page 377
15.4.1 Examples of Cellular Programming......Page 379
15.5.1 Cellular Automata Based Computational Experiment Decomposition......Page 382
15.5.2 Software Design......Page 383
15.5.3 Usage Example. Tumor Growth Modeling......Page 384
References......Page 390