Complex Adaptive Systems
P747
Professor Robert Goldstone
Psychology, computer science, economics, biology, and neuroscience depend upon a deeper understanding of the mechanisms that govern adaptive systems. A common feature of these systems is that organized behavior emerges from the interactions of many simple parts. Individual cells interact to form differentiated body parts, ants interact to form colonies, neurons interact to form intelligent systems, and people interact to form social networks. The goals of the course are to: 1) give students an intuitive appreciation for the behavior of complex adaptive systems, 2) present the student with specific case studies of these systems, and 3) describe the formal underpinnings for the complex behavior of these systems. Properties shared by many complex systems are emergent behavior, self-organization, adaptation, the development of specialized parts, patterns of cooperation and competition, and decentralized control.
To address the essential question of 襑hat are the properties of complex adaptive systems?, case studies of several systems will be explored: chaotic growth in animal populations, human learning, cooperation and competition within social groups, social networks, cellular automata, the development of stable and globally coherent perceptual representations, and the evolution of artificial life. A central thesis will be that apparently dissimilar systems (businesses, ant colonies, and brains) share fundamental commonalities. These commonalities will be described in terms of mathematical and computational formalisms. Good algebra skills are required, and some experience with calculus and a computer programming language is recommended. During the course, students will become familiar Netlogo, a high-level computer language for developing complex systems.
The topics will be explored by hands-on use of interactive computer simulations. In the first half of the course, students will be evaluated by their performance on laboratory assignments (some of the laboratories will be based on the computer simulations accessible at http://cognitrn.psych.indiana.edu/rgoldsto/complex/). In the second half of the course, students will lead a class on a reading of their own choosing, and will execute and describe their own individual projects. Projects could involve devising a complex adaptive system model of a natural phenomenon, fitting an existing model to data, conducting an experiment, or providing a novel critique or assessment of a complex adaptive system. Relevant topics for individual projects include but are not limited to: dynamical systems, artificial life, chaotic systems, biological growth and development, group and collective behavior, bottom-up models of economies, swarm intelligence, game theory, learning, resource utilization in a population, pattern formation, pattern recognition, neural networks, genetic algorithms, emergent organization in social systems, and evolutionary theory. Each student is expected to lead one class period, centered on a specific, well-contained literature (or even a single article), and another class period on their own project.
Click here for the course syllabus
Weekly Topics
Week 1: Overview on Complex Adaptive Systems
Topics
Properties of Complex Adaptive Systems
Emergent behavior
Adaptation
Specialization
Dynamic Change
Competition and Cooperation
Decentralization
What makes a good computer simulation?
Orientation to Sub-topics
Reading:
Wilensky
& Resnick (1999)
Optional reading: Macy & Willer (2002). From factors to actors: Compuational sociology and agent-based modeling.
Week 2: Starlogo & Netlogo
Topics
Ontology: Agents and Patches
Programming Constructs
Examples
Conway誷 Game of Life
Langton誷 Virtual Ants
Path Finder
Slime Mold
Segregration
Readings: Resnick (1994) Chapters 2 and 3 (Password: Agent)
Resources
Starlogo This is the newest version of the Starlogo simulation environment developed at MIT by Mitchell Resnick and his collaborators.
StarlogoT The version of Starlogo originally developed at Tufts University by Uri Wilensky誷 team. It is a Macintosh-only version of Starlogo. Version 2 runs native in OS X. See StarlogoT誷 page of models to see many examples. Check out the User誷 guide, and the comprehensive reference manual with all programming commands.
Netlogo
This is a cross-platform simulator very similar in its language to StarlogoT
(and Starlogo). It is developed by
Uri Wilensky誷 group,
and includes a programming
environment (Hubnet)
for developing multi-user participatory simulations where the individual agents
are operated by individual human users!
Check out Netlogo誷 page
of models to see some of the simulations developed for it. Here are the all-important user誷 guide and dictionary of all programming
commands.
Exercise: Programming in Starlogo
Week 3: Cellular Automata (CAs)
Topics
Properties of Cellular Automata
Classification of Cellular Automata
Substitution Systems
Mobile automata
CA Turing machines
Plant Growth
Morphogenesis
Applications in biology
Pine Cone Phyllotaxis
Oscillations in Firefly Populations
Spots and Stripes in biological development
Bridges Explanations in the Chaos Game and Replicating Game of Life
Readings: Wolfram (2002), Chapters 3 and 8, Douady & Couder (1992), Ball (1999)
Mathematica notebooks for code examples from the book
A New Kind of Life Explorer: Interactive software for demonstrating many of the examples from Wolfram誷 book
Fequently Asked Questions about Cellular Automata
Java Applets demonstrating several species of Cellular Automata
Life-lab: A Macintosh program for exploring cellular automata including variants of Conway誷 Game of Life. This is recommended software for completing the exercise.
StarlogoT example of a one-dimensional cellular automata
StarlogoT version of the Conway誷 game of Life
There are hundreds of cellular automata simulators of different stripe (and spot). Check out Zooland for a mere sampling.
Pine Cone Simulator A Macintosh simulation of the development of pine cone and other plant leaves.
Firefly A StarlogoT simulation of the emergence of flash synchrony in fireflies
Exercise: Bridging Explanations
Week 4: Applications of Cellular Automata in the Social Sciences
Topics
Propagation of beliefs in a spatially distributed community
Attitude formation
Schelling誷 segregation model
Sugarscape
Distribution of wealth
Cultural transmission
Readings: Nowak, Szamrej, & Latane (1990), Nowak & Lewenstein (1996), Epstein & Axtell (1996) Chapters 2 and 3
Resources
Segregation A StarlogoT simulation of Schelling誷 segregation model
Sitsim A simple Netlogo simulation of Latane誷 work on social influence
Rauch, Jonathan, 襍eeing Around Corners, Atlantic, April 2001.
Poletta & Jasper (2001). Collective identity and social movements
Wealth ditribution A StarlogoT version of the Epstein and Axtell model of wealth distribution
The home for Sugarscape, at the Brookings Institute
Movies of Sugarscape simulations
Week 5 Adaptation in communities
Topics
Predator-prey dynamics the Lotka-Volterra model
Chaotic growth in a population with the logistic function
Prisoner誷 dilemma: simple, iterated, spatial
Diffusion limited aggregation
Frequency-dependent selection
Reading: Ball (1999) Communities chapter, Flake (1998) Chapter 10
Resources
Predators & Prey a Macintosh simulation of population dynamics
Background information on the Prisoner誷 Dilemma
A spatial Prisoner誷 Dilemma and other links
Useful Prisoner誷 Dilemma links
A Netlogo version of Diffusion limited aggregation
Week 6: Student-led Discussions (see potential topics below)
Information Diffusion (led by Winter Masson)
A Dynamic Field Model of the A-Not-B Error (led by Joseph Anderson)
Week 7: Student-led Discussions
Reinforcement Learning (led by Michael Roberts)
The Evolution of Language (led by Brianna Conrey)
Week 8: Student-led Discussions
Conceptual Role Semantics(led by Ellie Hua Wang)
The Ultimatum Game (led by Shakila Shayan)
Week 9: Student-led Discussions
The Baldwin Effect(led by Georg Theiner)
Small World Phenomena(led by Abhijit Mahabal)
Week 10 Genetic Algorithms
Topics
Search algorithms for rough landscapes
Fundamental schema theorem
K-armed bandit problems
Tradeoffs between Exploitation and Exploration
Genetic programming
Readings: Goldberg (1989), Holland (1992)
Resources
An interactive overview of Genetic algorithms
Genetic algorithm and artificial life resources
The
genetic algorithms archives
Week 11 Swarm Intelligence (Guest visit by Russ Eberhart on April 1)
Topics
Axelrod誷 Adaptive Culture Model
Particle Swarms, compared to Genetic Algorithms
Imitation
Memetic algorithms
Reading: Kennedy & Eberhart (2001), Chapters 6 and 7
Optional
readings
A comparison of genetic algorithms and particle swarms (Eberhart & Shi)
A concise overview of particle swarms (Eberhart & Shi)
Resources
The official site
for the book Swarm Intelligence
Xiaohui
Hu誷 Particle Swarm site
Maurice Clerc誷
Particle Swarm site
Week 12 Emergent organization in perception and cognition
Topics
Constraint satisfaction networks for the perception of ambiguous objects
Apparent motion
Stereo vision and depth perception
The dynamics of perceptual organization
Neural networks for constraint satisfaction
Semantic networks
Readings: Dawson (1991), Ramachadran & Anstis (1986)
Resources:
Apparent motion experiment and model. This Macintosh software will allow you to run yourself in apparent motion perception experiments. It will also let you compare your perceptions to a neural network model誷 襭erceptions.
Computational stereo vision. This site evaluates models that take as input two side-by-side pictures of the same scene, and outputs a 3D representation of the scene.
Research from Bremen University on human and computer stereo perception
Week 13 Social Networks
Topics
Small world graphs
The strength of weak ties
Scale free networks
Hubs and authorities
Preferential attachment models
Readings: Watts & Strogatz (1998), Barabasi & Albert (1999)
Resources
Articles by Mark Newman on graph structures and dynamics
Albert-Laszlo Barabasi誷 Networks Laboratory
Week 14 Student project descriptions
Week 15 Student project descriptions
Evolution of cooperation
Altruism in communities
Prisoner誷 Dilemma
The Minority Game (Here is Savitt誷 work on this)
The Ultimatum Game
The diffusion of beliefs (see, Wejnert (2002))
The Baldwin effect (and Hinton & Nowlan誷 [1987] computer simulation of it)
Waddington canalization of acquired characteristics
Information propagation in a community
Chaotic population change
Wilson and Sober誷 view on group selection models
Per Bak誷 work on Self-organized criticality
Computation at the edge of chaos
Speciation and niche creation
Models of invention and innovation
Stuart Kauffman誷 NK systems the Origins of Order
James Crutchfield誷 Finite State Automata for pattern discovery
Kirby and Hurford誷 model of the evolution of language in a community
1/f noise in cognition
Goldstone & Rogosky誷 work on cross-system translation using within-system relations
Latent Semantic Analysis for using word co-occurrences to determine meaning
Social clustering and clique formation (Here's a Physica A by Plewczyinksi)
Coalition formation
Bikhchandani et al誷 work on fads and
cultural change
Valente誷 work on the diffusion
of innovations in a community
Tuevo Kohonen誷 work on Self-organized
Maps
Auto-encoder networks
Hopfield誷 work on attractors in
neural networks
Internal representations in neural
networks
Simulated annealing
Scott Camazines work on self-organization in biological systems
Bernd Fritske誷 work on growing self-organizing networks
L-systems for modeling growth
Langton誷 Lambda parameter for characterizing cellular automata
Flocking, herding, and schooling behavior
Other papers by Albert-Laszlo Barabasi誷 lab on network structure
Percolation theory (see an introduction here)
Reinforcement learning
Minimum description length
Lyapunov stability
Sparse distributed memory
Support vector machines
Competitive learning
Course Readings
Ball, P. (1999). The self-made tapestry. Oxford, England: Oxford University Press.
Barab噑i, A., & Albert, R.
(1999). Emergence of scaling in
random networks, Science, 286, 509-512
Dawson, M. R. W. (1991). The how and why of what went where in
apparent motion: Modeling solutions to the motion correspondence problem. Psychological Review, 98,
569-603.
Douady, S., & Couder, Y. (1992). Phyllotaxis as a physical
self-organized growth process. Physical
Review Letters, 68, 2098-2101.
Epstein, J. M., & Axtell, R.
(1996). Growing artificial
societies: Social science from the bottom up. Washington, D.C.: Brookings Institute Press.
Flake, G. W. (1998). The computational beauty of nature. Cambridge, MA: MIT Press.
Goldberg, D. E. (1989). Genetic Algorithms. Reading, MA: Addison-Wesley. (Chapter 1. pp. 1-23).
Holland, J. H. (1992). Genetic algorithms. Scientific American, July,
66-72.
Kennedy, J., & Eberhart, R. C.
(2001). Swarm intelligence. San Francisco, CA: Morgan Kaufmann.
Nowak, Andrzej and Lewenstein, Maciej. (1996). Modeling Social Change with Cellular
Automata.
Pp 249-285 in Modeling & Simulation
in the Soc. Sciences from a Philosophical Point of View.
Hegselmann et al., eds. Kluwer, Boston.
Nowak, A., Szamrej, J., & Latane, B.
(1990). From private attitude to
public opinion: A dynamic theory of social impact. Psychological Review, 97, 362-376.
Resnick, M. R. (1994). Turtles, Termites, and Traffic
Jams. Cambridge, MA: MIT Press.
Ramachandran, V. S., & Anstis, S. M.
(1986). The perception of apparent
motion. Scientific American,
June, 102-109.
Watts D. J. and Strogatz S. H.
Collective dynamics of
'small-world' networks.
Nature 393, 440-442 (1998).
Wilensky, U., and Resnick, M.
(1999). Thinking in
Levels: A Dynamic Systems Approach to Making Sense of the World. Journal of Science Education and
Technology, vol. 8, no.
1, pp. 3-19.
Wolfram, S. (2002). A new kind of Science. Champaign, IL.: Wolfram Media.
Related Courses Around the World
Additional Web Resources on Complex Adaptive Systems