Simulating Complex Systems by Cellular Automata

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