I NetLogo 1
1 Introduction to NetLogo 3
1.1 Programming Environment . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.1 Model Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.2 Model Information . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.3 Model Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2 NetLogo Turtles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3 NetLogo Patches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4 NetLogo Links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
II Graphs 11
2 Modeling Graphs with NetLogo 13
2.1 Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3 Nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.4 Arcs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3 Graph Search 23
3.1 The A* Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.1.1 Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.1.2 Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.1.3 Simulating an A* Iteration . . . . . . . . . . . . . . . . . . . . . . 27
3.1.4 Movie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2 Dijkstra's Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4 Graph Coloring 37
4.1 Greedy Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.1.1 Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.1.2 Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.1.3 Simulating the Greedy Algorithms . . . . . . . . . . . . . . . . . . 44
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
5 Graph Layout 53
5.1 Tutte's Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.1.1 Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.1.2 Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.1.3 Simulating Tutte's Method . . . . . . . . . . . . . . . . . . . . . . 59
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
III Cellular Automata 63
6 Modeling Cellular Automata with NetLogo 65
6.1 History of Cellular Automata . . . . . . . . . . . . . . . . . . . . . . . . . 65
6.2 Components of a Cellular Automaton . . . . . . . . . . . . . . . . . . . . 66
6.2.1 Lattice of Cells . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
6.2.2 States of Cells . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
6.2.3 Transition Function . . . . . . . . . . . . . . . . . . . . . . . . . . 72
6.2.4 Updating Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
6.3 Second-Order Cellular Automata . . . . . . . . . . . . . . . . . . . . . . . 72
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
7 Elementary Cellular Automata 75
7.1 Modeling Elementary Cellular Automata . . . . . . . . . . . . . . . . . . . 76
7.2 Types of Elementary Cellular Automata . . . . . . . . . . . . . . . . . . . 82
7.3 Modeling Totalistic Elementary Cellular Automata . . . . . . . . . . . . . 84
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
8 Two-Dimensional Cellular Automata 91
8.1 Basic Two-Dimensional Cellular Automata . . . . . . . . . . . . . . . . . . 91
8.2 Modeling Two-Dimensional Cellular Automata . . . . . . . . . . . . . . . 95
8.2.1 The Totalistic Case . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
8.2.2 The Outer Totalistic Case . . . . . . . . . . . . . . . . . . . . . . . 102
8.3 Majority Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
8.4 Parity Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
8.5 Game of Life . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
9 Applications of Cellular Automata in Physics 119
9.1 Partial Differential Equations . . . . . . . . . . . . . . . . . . . . . . . . . 119
9.1.1 Diffusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
9.1.2 Reaction-Diusion . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
9.1.3 Waves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
9.1.4 Wavefronts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
9.2 Fluids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
9.2.1 Lattice Gas Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
9.2.2 Lattice Boltzmann Model . . . . . . . . . . . . . . . . . . . . . . . 139
9.3 Ising Spin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
9.4 Sandpile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
9.5 Diffusion-Limited Aggregation . . . . . . . . . . . . . . . . . . . . . . . . . 164
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
10 Applications of Cellular Automata in Excitable Media 169
10.1 Brian's Brain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
10.2 Greenberg-Hastings Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
10.3 Threshold Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
10.4 Cyclic Cellular Automata . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
10.5 Hodgepodge Machine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
11 Applications of Cellular Automata in Biology 187
11.1 Seashell Pigmentation Patterns . . . . . . . . . . . . . . . . . . . . . . . . 187
11.2 Bacterial Growth . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
11.3 Predator-Prey . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
12 Applications of Cellular Automata in Social Science 201
12.1 Schelling's Segregation Model . . . . . . . . . . . . . . . . . . . . . . . . . 201
12.2 Evacuation Dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
12.2.1 Floor Fields Based on Shortest Paths . . . . . . . . . . . . . . . . 206
12.2.2 Floor Fields Based on Quickest Paths . . . . . . . . . . . . . . . . 207
12.2.3 Fast Evacuation Method . . . . . . . . . . . . . . . . . . . . . . . . 208
12.2.4 NetLogo Model for Evacuation Dynamics . . . . . . . . . . . . . . 209
12.3 Game Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
12.4 Evolutionary Computation . . . . . . . . . . . . . . . . . . . . . . . . . . 228
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
IV Geometry 243
13 Fractals 245
13.1 Geometric Fractals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
13.2 Algebraic Fractals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
13.2.1 Julia Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
13.2.2 Mandelbrot Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
13.2.3 Visualization of Algebraic Fractals . . . . . . . . . . . . . . . . . . 262
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272
14 Clustering 273
14.1 Clustering Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273
14.2 The DBSCAN Clustering Algorithm . . . . . . . . . . . . . . . . . . . . . 274
14.3 Modeling DBSCAN with NetLogo . . . . . . . . . . . . . . . . . . . . . . 276
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282
15 Voronoi Diagrams 283
15.1 Modeling Voronoi Diagrams with NetLogo . . . . . . . . . . . . . . . . . . 284
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286
Bibliography 287
Index 301
CONTENIDO: NetLogo is an agent-based programming environment well suited for modeling and inspecting complex systems evolving over time. Since thousands of independent agents and their interactions can be simulated with NetLogo, emerging global patterns arising from the local behavior of these agents can be explored and analyzed.
This book deals with how to use NetLogo in order to design models of complex systems and models of intelligent systems. Specifically, just to mention a few examples, the tackled complex systems in the book are related to cellular automata, fractals, and visualization of graphs, while the addressed intelligent systems have to do with evacuation dynamics, evolutionary computation, and optimization in graphs.
Each of the fifteen chapters of this book includes a number of figures, bibliographic references, and exercises of interest to the reader. The book offers students, practitioners, and researchers a broad coverage of the main aspects of modeling problems with NetLogo in the context of complexity science and artificial intelligence. To that end, NetLogo code is included throughout the book for each presented model and for each addressed problem.
The author of this book is an associate professor in the Department of Artificial Intelligence at UNED (Spanish Open University). Since the middle 1990s, he has performed teaching and research activities within the field of artificial intelligence, mainly in the areas of Bayesian networks and evolutionary computation.
