Contents
List of Tables ix
List of Figures xi
Preface xvii
1 Introduction 1
1.1 What is simulation? . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Simulation of intelligence . . . . . . . . . . . . . . . . . . . . 3
1.3 Criticism of simulation . . . . . . . . . . . . . . . . . . . . . 6
1.4 Swarm and the Santa Fe Institute . . . . . . . . . . . . . . . 8
2 Evolutionary Methods and Evolutionary Computation 13
2.1 What is evolutionary computation? . . . . . . . . . . . . . . 13
2.2 What are genetic algorithms? . . . . . . . . . . . . . . . . . . 14
2.2.1 Data representation . . . . . . . . . . . . . . . . . . . 14
2.2.2 Selection . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2.3 Genetic operations . . . . . . . . . . . . . . . . . . . . 16
2.2.4 Flow of the algorithm . . . . . . . . . . . . . . . . . . 19
2.2.5 Initialization . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.6 Extension of the GA . . . . . . . . . . . . . . . . . . . 20
2.2.7 Traveling salesman problem (TSP) . . . . . . . . . . . 21
2.3 What is genetic programming? . . . . . . . . . . . . . . . . . 25
2.3.1 Description of individuals in GP . . . . . . . . . . . . 25
2.3.2 Flow chart of GP . . . . . . . . . . . . . . . . . . . . . 27
2.3.3 Initialization of tree structures . . . . . . . . . . . . . 29
2.3.4 Fitness evaluation . . . . . . . . . . . . . . . . . . . . 31
2.3.5 Cro ssover and mutation . . . . . . . . . . . . . . . . . 31
2.3.6 Simulating wall following robots . . . . . . . . . . . . 33
2.4 What is interactive evolutionary computation? . . . . . . . . 35
2.4.1 Interactive music composition based on Swarm simula-
tion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3 Multi-Agent Simulation Based on Swarm 45
3.1 Overview of Swarm . . . . . . . . . . . . . . . . . . . . . . . 45
3.2 Tutorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
v
vi Contents
3.2.1 simpleCBug . . . . . . . . . . . . . . . . . . . . . . . . 50
3.2.2 simpleObjCBug and simpleObjCBug2 . . . . . . . . . 51
3.2.3 simpleSwarmBug . . . . . . . . . . . . . . . . . . . . . 54
3.2.4 simpleSwarmBug2 . . . . . . . . . . . . . . . . . . . . 57
3.2.5 simpleSwarmBug3 . . . . . . . . . . . . . . . . . . . . 59
3.2.6 simpleObser verBug . . . . . . . . . . . . . . . . . . . . 60
3.2.7 simpleObser verBug2 . . . . . . . . . . . . . . . . . . . 64
3.2.8 simpleExperBug . . . . . . . . . . . . . . . . . . . . . 68
4 Evolutionary Simulation 73
4.1 Simulation of sexual selection . . . . . . . . . . . . . . . . . . 73
4.1.1 Sexual selection in relation to markers, handicaps, and
parasites . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.1.2 The Kirkpatrick model . . . . . . . . . . . . . . . . . . 77
4.1.3 Simulation using GAs . . . . . . . . . . . . . . . . . . 79
4.2 Swarm-based simulation of sexual selection . . . . . . . . . . 82
4.3 Simulation of the prisoner’s dilemma . . . . . . . . . . . . . 84
4.3.1 The prisoner’s dilemma . . . . . . . . . . . . . . . . . 84
4.3.2 Iterated prisoner’s dilemma . . . . . . . . . . . . . . . 87
4.3.3 IPD using GAs . . . . . . . . . . . . . . . . . . . . . . 94
4.3.4 IPD simulation by Swarm . . . . . . . . . . . . . . . . 97
4.3.5 IPD as spatial games . . . . . . . . . . . . . . . . . . . 102
4.4 Evolving artificial creatures and artificial life . . . . . . . . . 103
4.4.1 What is artificial life? . . . . . . . . . . . . . . . . . . 103
4.4.2 Artificial life of Kar l Sims . . . . . . . . . . . . . . . . 104
4.4.3 Evolutionary morphology fo r real modular robots . . . 105
5 Ant Colony–Based Simulation 111
5.1 Collective b e haviors of ants . . . . . . . . . . . . . . . . . . . 111
5.2 Swarm simulation of the pheromone trails of ants . . . . . . 114
5.3 Ant colony optimization (ACO) . . . . . . . . . . . . . . . . 116
5.4 Ant-clustering algorithms . . . . . . . . . . . . . . . . . . . . 118
5.5 Swarm-based simulation of ant-clustering . . . . . . . . . . . 120
5.6 Ant colony–based approach to the network routing problem . 121
5.7 Ant-based job separation . . . . . . . . . . . . . . . . . . . . 124
5.8 Emergent cooperation of army ants . . . . . . . . . . . . . . 126
5.8.1 Altruism of army ants . . . . . . . . . . . . . . . . . . 126
5.8.2 Defining the problem . . . . . . . . . . . . . . . . . . . 127
5.8.3 Judgment criteria for entering the altruism state . . . 127
5.8.4 Judgment criteria with refere nce to chain formation . 132
5.8.5 Changes in strategy based on number of agents . . . . 135
5.8.6 Comparative experiment . . . . . . . . . . . . . . . . . 135
5.8.7 Simulation with fixed role ass igned . . . . . . . . . . . 137
Contents vii
6 Particle Swarm Simulation 139
6.1 Boids and flocking behaviors . . . . . . . . . . . . . . . . . . 139
6.2 Simulating boids with Swarm . . . . . . . . . . . . . . . . . . 143
6.3 Swarm Chemistry . . . . . . . . . . . . . . . . . . . . . . . . 146
6.4 PSO: particle swarm optimization . . . . . . . . . . . . . . . 148
6.4.1 PSO algorithm . . . . . . . . . . . . . . . . . . . . . . 149
6.4.2 Comparison with GA . . . . . . . . . . . . . . . . . . 150
6.4.3 Examples of PSO applications . . . . . . . . . . . . . 154
6.5 ABC algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 15 6
6.6 BUGS: a bug-based search strategy . . . . . . . . . . . . . . 163
6.6.1 Evolution of predatory behaviors using ge netic search 164
6.6.2 A bug-based GA search . . . . . . . . . . . . . . . . . 170
6.7 BUGS in Swarm . . . . . . . . . . . . . . . . . . . . . . . . . 175
7 Cellular Automata Simul ation 179
7.1 Game of life . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
7.1.1 Rule 18 4 . . . . . . . . . . . . . . . . . . . . . . . . . . 186
7.2 Conway class with Swarm . . . . . . . . . . . . . . . . . . . . 188
7.3 Program that replicates itself . . . . . . . . . . . . . . . . . . 196
7.4 Simulating forest fires with Swarm . . . . . . . . . . . . . . . 197
7.4.1 Simulation of fores t fires . . . . . . . . . . . . . . . . . 198
7.5 Segregation model simulation with Swarm . . . . . . . . . . 200
7.5.1 Swarm-based simulation o f segregation model . . . . . 202
7.6 Lattice gas automaton . . . . . . . . . . . . . . . . . . . . . . 203
7.6.1 LGA simulation with Swarm . . . . . . . . . . . . . . 207
7.7 Turing model and morphogenesis simulation . . . . . . . . . 208
7.7.1 Simulation of morphogenesis by the Turing model . . 210
7.8 Simulating percolation with Swarm . . . . . . . . . . . . . . 212
7.9 Silicon traffic and its control . . . . . . . . . . . . . . . . . . 215
7.9.1 Simulating traffic jams with Swarm . . . . . . . . . . . 216
7.10 The world of Sugarscape . . . . . . . . . . . . . . . . . . . . 218
7.10.1 A simple Sugarscape model . . . . . . . . . . . . . . . 219
7.10.2 Life and birth . . . . . . . . . . . . . . . . . . . . . . . 222
7.10.3 Breeding . . . . . . . . . . . . . . . . . . . . . . . . . . 222
7.10.4 Environmental changes . . . . . . . . . . . . . . . . . 225
7.10.5 Introduction of culture . . . . . . . . . . . . . . . . . . 230
7.10.6 Introduction of combat . . . . . . . . . . . . . . . . . 233
7.10.7 Introduction of trade . . . . . . . . . . . . . . . . . . . 237
7.10.8 Swarm simulation in Sugarscape . . . . . . . . . . . . 243
8 Conclusion 249
viii Contents
A GUI Systems and Source Code 257
A.1 Intr oduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
A.2 PSO simulator and benchmark functions . . . . . . . . . . . 258
A.3 TSP simulator by a GA . . . . . . . . . . . . . . . . . . . . . 261
A.4 Wall-following simulator by GP . . . . . . . . . . . . . . . . 262
A.5 CG s ynthesis of plants based on L -systems . . . . . . . . . . 263
A.6 LGPC for art . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
B Installing Swarm 267
B.1 Installation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
B.1.1 Java2 SDK installation . . . . . . . . . . . . . . . . . 267
B.1.2 Installing the Swarm packag e . . . . . . . . . . . . . . 268
B.1.3 Setting environment variables . . . . . . . . . . . . . . 268
B.1.4 Compiling . . . . . . . . . . . . . . . . . . . . . . . . . 268
B.1.5 Confirming operation . . . . . . . . . . . . . . . . . . 269
B.2 Objective- C version . . . . . . . . . . . . . . . . . . . . . . . 269
B.2.1 Objective-C and Swarm . . . . . . . . . . . . . . . . . 269
B.2.2 Material related to the O bjective-C version o f Swarm 270
B.2.3 Running Swarm under various environments . . . . . 270
B.3 Useful online resources . . . . . . . . . . . . . . . . . . . . . 271
References 273
Index 287
Swarm Index 295
Name Index 297
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.