Preface
This book provides a methodology for a multi-agent based modeling approach
with the integration of co mputatio nal techniques, e.g., artificial life, cellular
automata, and bio -inspired optimization. The development of such tools con-
tributes to better modeling when addressing tasks from such a reas as biology,
sociology, civil engineering, economics, granular physics, and art. This attracts
attention as a method of understanding complica ted phenomena which cannot
be solved analytically, in material sciences, ecology, and social science.
In this book, the method of constructing a simulation program is intro-
duced kindly and carefully. Several simulation models with a common theme
are treated in each chapter. Each chapter consists of how to assemble the algo-
rithm for realizing a simulation model, a program, a method for visualization,
and further resea rch tasks, etc. These models can b e automatica lly lea rned
step by step. While most of the multi-agent simulation is described using the
Swarm system, i.e., a commonly used multi-agent simulator, the description is
general enough so that the reader ca n model and develop the same simulation
with his own simulator.
The book will provide an overv iew of multi-agent simulation and support-
ing materials, org anized into seven chapters. Each chapter begins w ith an
overv iew of the problem and of the current state-of-the-art of the field, and
ends with a detailed discussion about multi-agent frameworks. In addition, the
appendices provided at the end of this book contain a description of available
multi-agent simulation based on such simulators as PSO, ACO, and Swarm
systems and source codes available to readers for download.
Chapter 1 provides the background and a basic introduction to simulation
and complex systems. It also gives pros and cons of simulation. The limitations
of simulation are the subject of lengthy discussions in the field of rob otics. We
will explain some of these criticisms of simulation.
Chapter 2 provides background and basic introduction to evolutionary
computation, i..e., genetic algorithms (GAs), genetic programming (GP), and
interactive evolutionary computation (IEC). These are key techniques of sim-
ulating multi-agent systems described in the following chapters.
In Chapter 3, we describe the Swarm system, which has been developed
by the Santa Fe institute and has been widely used for simulating complex
systems. Swarm is a bottom-up model based simulator which consis ts of bio-
logical agents (such as bugs) and abiotic agents (such as a wall or an obstacle)
in an artificial world. The motions of the agents are describ ed by simple rules,
xvii
xviii Preface
and the emergence of complex phenomena due to the interaction between the
agents is observed. This chapter focuse s mainly on the Java library for the
Windows edition and gives a tutorial on how to use Swarm, aiming to imple-
ment a practical simulation. In later chapters, we w ill explain the programs
of complex systems simula tion implemented in Swarm. All software sources
described in the text are available from our on-line server for educational
purposes.
Chapter 4 describes evolutionary simulation examples by means of GA.
Most of them are provided with supplementary demonstration based upon
our multi-agent simulation. First, we present a simulation o f sexual selection.
In this chapter, we pre sent several hypotheses expla ining the excessive be auty
of certain animals, toge ther with verification expe riments bas e d on GAs. This
exp e riment is a remarkable demonstration of the power of female preferences
and sexual selection. We also explain an extended version of the prisoner’s
dilemma known as the “iterated prisoner’s dilemma” (IPD), in which the pris-
oner’s dilemma is repeated a number of times with the same participants,
and a final score is obtained as the sum of the scores in all iterations. In this
section, we first give a detailed discussion of the evolution of cooperation in
IPD. Next, we explain the concept of an evolutionarily stable state (ESS),
whereby once a ce rtain strategy becomes dominant in a population, invasion
by another strategy is difficult. Then we describe an experiment based on re-
search conducted by Co hen, where an IPD strategy evolves using a GA. With
these experiments, we have obs e rved that a cooperative relationship emerges
in a certain network structure. Subsequently, we give a brief explanation of
A-life a nd its philosophy. Finally, we give a detailed description of remarkable
examples, i.e., artificial cr e atures evolved by Karl Sims.
Marching is a cooperative ant behavior that can be explained by the
pheromone trail mode. Many of the ants return to the shorter p ath, secreting
additional pheromones; therefore, the ants that follow also take the shorter
path. This model can b e applied to the search for the shortest path and is
used to solve the traveling salesman problem (TSP) and routing of networks.
In Chapter 5, we give a detailed description of ant trail simulation and ant
colony optimization (ACO). We also give an advanced topic on the simulation
of cooperative behavior of ar my a nts. Army ants build br idges using their
bodies along the route from a food source to the nest. Such altruistic b e havior
helps to optimize the food ga thering performance of the ant colony. We present
a multi-agent simulation inspired by army ant behavior in which interesting
cooperation is observed in the form o f philanthropic activity. As a real-world
application, we describe an ACO-based approach to solving network routing
problems.
In Chapter 6, we describe flocking behaviors of bir ds or fis h (called “boids”).
Microscopica lly, the behavior is very simple and can be modeled using cellu-
lar automata; however, macroscopically, the behavior is chaotic and very com-
plex. The models are dominated by interactions be tween individual birds, and
their collective behavior is the result of rules to keep the optimum distance
Preface xix
between an individual and its neighbor s. Recently researchers designed an
effective optimization algorithm using the mechanism behind this collective
behavior. This is called particle swarm optimization (PSO), and numerous
applications of PSO are reported. In this chapter, details of these methods
are provided with several multi-agent simulation examples. Finally, we ex-
plain “Swarm chemistry” by Hiroki Sayama. Swarm chemistry is an artificial
chemistry framework that e mploys artificial swarm populations as chemical re-
actants. Swarm agents steer their motion according to a set of simple kinetic
rules, similar to those in boids. We give some simulation results of Swarm
chemistry and re port on the research results about the application of IEC
(interactive evolutionary c omputation) to evolving desirable motions.
Simulations based on cellular automata (CA) are applied in various fields.
These simulations are considered to be an effective method for observing crit-
ical behavior in phase transitions. Chapter 7 provides a variety of application
examples of cellular automata, e.g., game of life, segregation model, lattice gas
automata, Turing model, percolation, tra ffic simulation, and the Sugarscape
model. For insta nce , we explain the game of life, in which self-or ganizing ca-
pabilities can be used to configure a universal Turing machine. In the area of
the game of life, re search has been done to find effective rules through GA or
GP. The concept of Boolean functions is applied when GP is used. The fitness
value is defined by the percentage of correctly proces sed sequences. Here, the
rules obtained using GP were very effective . We give a detailed discussion of
this evolutionary learning process. We also discuss the con c e pt of the “edge
of chaos” from the b e havior of CA proposed by Kauffman and Packard. This
concept represents “Class IV” patterns where pe riodic, aperiodic, and chaotic
patterns are r e peated. The working hypothesis in artificial life is “life on the
edge of chaos.” The CA model has been extensively studied for the purpose
of simulating emergent properties resulting from multi-agent modeling. We
provide a wide range of experimental results based on Swarm in this chapter.
Chapter 8 provides conclusions obtained from the simulation results based
on Swarm. We describe a “constructive approa ch” to “create and understand”
complex systems and categorize various multi-agent simulation tests imple-
mented in this book. The significa nce of bottom-up simulation is analyzed in
the summary of the book.
We hope that the multi-agent simulations disc ussed in this book will con-
tribute to the understanding of complex systems and artificial life.
Hitoshi Iba
Tokyo, Japan
Acknowledgments
To all those wonderful people, the author owes a deep sense of gratitude
especially now that this book project ha s been completed. Especially, the
author a ppreciates the pleasant research atmospher e created by colleagues and
students from the resea rch laboratory a ssociated with the Graduate School of
xx Preface
Frontier Sciences and Information Science and Technology at the University
of Tokyo.
The author is grateful to his previous group at the Electro-Technical Lab-
oratory (ETL), where he worked for ten years, and to his curr e nt colleagues
at the Graduate School of Engineering of the University of Tokyo. Particular
thanks are due to Dr. Hirochika Inoue and Dr. Taisuke Sato for providing pre-
cious comments and advice on numerous occas ions. He also wishes to thank Dr.
Benedikt Stefansson. The tutoria l in Chapter 3 is based on his material from
the Swarmfest of 1999. His original version was implemented in Objective-C.
We re-implemented this system in Java and modified his materials in accor-
dance with our purpose. However, the author takes full responsibility for any
errors in the text and source code.
The author gratefully acknowledges permission from MIT Press to use
Figures 4.4, 4.5, 4.6, 4.7, and 4.15, from Prof. Salvacion P. Angtuaco to use
Figure 5.12 , fr om Springer-Verla g GmbH to use Figures 5.2 and 5.3, and fr om
Oxford University Press to use Figures 7.1, 7.2, and 7.3.
And last, but not least, he would like to thank his wife Yumiko and his sons
and daughter, Kohki, Hirono, and Hiroto, for their patience and assistance.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.