____________________________________________________________
Complex Adaptive
Systems
P747, Section 3722
- Spring 2003
Room 228
Psychology
Meeting Time:
Tuesday, Thursday, 2:30-3:45
Instructor
Professor Robert
Goldstone
Office: 338
Psychology Building
Office Hours: arrange
by email
Phone: 855-4853
Email: rgoldsto@indiana.edu
____________________________________________________________
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 ÒWhat 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 simulations of 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 (such as a single article) and one period on their own project.
Evaluation
Students will be evaluated on the basis
of the two classes they lead, their general class participation throughout the
semester, the two small laboratory exercises, and their final project.
The breakdown of the grade will be:
Class
presentations: 25%
Laboratory
exercises: 20% (each is due within 2 weeks of when it was assigned)
Class
participation: 15%
Final
project: 40%
The goals of the seminar leader are two-fold - to review the fundamental points of the readings, and to generate and direct active discussion. About half of your time should be spent in instructional monologue, and the other half in open discussion. Overhead transparencies, powerpoint presentations, and handouts are encouraged. You may assume that everybody has read the material, but you may want to explain aspects of the paper that other students could have difficulty understanding. Do not attempt to cover all of the material in detail. Rather, select a handful of points that seem to be of fundamental importance. Consider time to be a precious resource; do not waste it on digressions. Two ingredients of a successfully run seminar are that the leader focuses his or her comments on critical themes in the material, and opens up discussion so that the seminar participants are actively involved.
Your final project is due May 6, 5:00 PM. The project should involve complex adaptive systems in some form. The topics in the ÒStudent-led discussionsÓ section give you some idea of some possible topics for a project. The form that your final project takes is up to you, but you should get permission for the format, particularly if it is unorthodox. Standard formats are:
- Experiment and write-up. This would involve designing, running, and analyzing an experiment and reporting the results. For example, you could run an experiment on the role of 1/f noise in human cognition. Your report would probably contain the following sections: introduction to the issue, background literature, experimental methods used, experimental results, and discussion.
- Computer simulation. Your final project could involve any of a variety of computer programs. Such programs might include: computer simulations of individual or group human behavior, simulations of natural processes, neural networks, artificial life, or data-mining systems. The program will often need to be supplemented by a document describing the theory behind the program and how it executes. Very often, your simulation will provide an implementation of a theory, and you will compare your simulation output to actual data. For the purposes of the project, the comparison may be qualitative rather than quantitative, although quantitative fits are typically important at some point in a modeling project.
- Archival research. Some questions about cognition are best asked not by conducting experiments, but by examining archives. For example, if you are interested in the network structure of scientific research communities, you might explored structures in the ÒScience Citation Index.Ó
- Construction. You may want to build a working model or demonstration of some phenomenon. You might, for example, construct a path-following robot, an artificial retina, or a swarm of simple devices. As with computer programs, in most cases, you will also need to prepare some written documentation describing the construction.
- Traditional research paper. In some cases, the best vehicle for describing your research may simply be to write a report that describes it.
Regardless of the format you use, the basis for evaluating
your final project will be the same: creativity, amount and quality of work,
clarity, and logic. For an
impressive final project, it is important to work consistently throughout the
semester rather than cramming in all of your work in the final few weeks.
It is possible for you to bite off too much or too little in your final projects, although I suspect that most studentsÕ impulse is to bite off too much. Here are some example of projects that are probably the right size:
Weekly Topics
Week 1 (1/14): Overview on Complex Adaptive Systems
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 (1/21): Starlogo & Netlogo
Ontology: Agents and Patches
Programming Constructs
Examples
ConwayÕs
Game of Life
LangtonÕs Virtual Ants
Path Finder
Slime Mold
Segregration
Reading: Resnick (1994) Chapters 2 and 3 (remember, the password is: agent)
Exercise: Programming in Starlogo
Week 3 (1/28): Cellular Automata (CAs)
Properties of Cellular Automata
Classification of Cellular Automata
Substitution Systems
Mobile automata
CA Turing machines
Applications of cellular automata in biology
Pine Cone Phyllotaxis
Oscillations in Firefly Populations
Spots and Stripes
Bridges Explanations in the Replicating Game of Life
Readings: Wolfram (2002), Chapters 3 and 8, Douady & Couder (1992), Ball (1999)
Exercise: Bridging Explanations
Week 4 (2/4): Applications of Cellular Automata in the Social Sciences
Propagation of beliefs in a spatially distributed community
Attitude formation
SchellingÕs segregation model
Sugarscape
Distribution of wealth
Cultural transmission
Readings: Nowak, Szamrej, & Latane (1990), Epstein & Axtell (1996) Ð Chapters 2 and 3
Optional reading: Nowak & Lewenstein (1996),
Week 5 (2/11) : Adaptation in communities
Predator-prey dynamics Ð the Lotka-Volterra model
Chaotic growth in a population with the logistic function
PrisonerÕs dilemma: simple, iterated, spatial, competitions
Diffusion limited aggregation
Frequency-dependent selection
Reading: Ball (1999) Communities chapter, Flake (1998) Chapter 10
Week 6 (2/18): Student-led Discussions (see potential topics below)
Week 7 (2/25): Student-led Discussions
Week 8 (3/4): Student-led Discussions
Week 9 (3/11): Student-led Discussions
Week 10 (3/25): Genetic Algorithms
Search algorithms for rough landscapes
Fundamental schema theorem
K-armed bandit problems
Tradeoffs between Exploitation and Exploration
Genetic programming
Readings:
Goldberg (1989), Holland (1992)
Week 11 ( 4/1) Swarm Intelligence
AxelrodÕs Adaptive Culture Model
Particle Swarms, compared to Genetic Algorithms
Imitation
Memetic algorithms
Readings: Kennedy & Eberhart (2001), Chapters 6 and 7
Week 12 (4/8): Emergent organization in perception and cognition
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)
Week 13 (4/15): Social Networks
Small world graphs
The strength of weak ties
Scale free networks
Hubs and authorities
Preferential attachment models
Readings: Watts & Strogatz (1998), Barabasi & Albert (1999)
Week 14 (4/22): Student projects
Week 15 (4/29) Student projects
Non-exhaustive List of Topics for Student-led Discussions
Evolution of cooperation
Altruism in communities
PrisonerÕs Dilemma
The Minority Game
The Ultimatum Game
The diffusion of beliefs
The Baldwin effect (and Hinton & NowlanÕs [1987] computer simulation of it)
Waddington canalization of acquired characteristics
Information propagation in a community
Chaotic population change
Wilson and SoberÕs views on group selection models
Per BakÕs work on Self-organized criticality
Computation at the edge of chaos
Speciation and niche creation
Models of invention and innovation
Stuart KauffmanÕs NK systems Ð the Origins of Order
James CrutchfieldÕs Finite State Automata for pattern discovery
Kirby and HurfordÕs model of the evolution of language in a community
1/f noise in cognition
Goldstone & RogoskyÕs 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
Coalition formation
Bikhchandani et alÕs work on fads and
cultural change
ValenteÕs work on the diffusion
of innovations in a community
Tuevo KohonenÕs work on Self-organized
Maps
Auto-encoder networks
HopfieldÕs work on attractors in
neural networks
Internal representations in neural
networks
Simulated annealing
Scott CamazinesÕ work on self-organization in biological systems
Bernd FritskeÕs work on growing self-organizing networks
L-systems for modeling growth
LangtonÕs Lambda parameter for characterizing cellular automata
Flocking, herding, and schooling behavior
Other papers by Albert-Laszlo BarabasiÕs lab on network structure
Percolation theory
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‡si, 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.