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

- Dr. Robert Axelrod, University of Michigan, Complexity Theory in the Social Sciences
- Dr. Katy Brner, Indiana University, Structural Data Modeling and Mining
- Dr. John D. Hey, University of York, Graduate Experimental Economics
- Dr. Leigh Tesfatsion, University of Iowa, Agent-based Computational Economics
- An entire curriculum in Complex Adaptive Systems for University of G歵eburg

Additional Web Resources on Complex Adaptive Systems

- Leigh Tesfatsion誷 Agent-based Computational Economics: A veritable cornucopia of overviews, readings, research groups, software, and much more.
- Complexity Digest: An excellent set of articles and other information on complex systems. It is updated every week and contains excellent pointers to recent articles in the field.
- Tilman Slemeck誷 links for experimental economists
- New England誷 Complex Systems Institute
- The Santa Fe Institute (SFI) Devoted to the formal understanding of complex systems
- The Swarm page A SFI system for developing mutl-agent simulations
- A portal for complex systems and complexity
- My own software for Complex Adaptive systems, originally programmed from Macintosh computers, but some of the simulations have been ported to Java.
- Repast: A Java software framework for creating agent based simulations
- Cormas: A programming environment dedicated to the creation of multi-agent systems, with a specialization in the domain of natural-resources management.
- Complexity International. A journal dealing with complex systems research.
- Complexity. Another journal dealing the same topic.
- Journal of Complexity. A mathematically-oriented journal.