____________________________________________________________

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

Web site: http://cognitrn.psych.indiana.edu/rgoldsto/complex/p747description.htm

____________________________________________________________

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%

 

Class readings

Many of the readings for the class are available  on-line from the courseÕs web site, http://cognitrn.psych.indiana.edu/rgoldsto/complex/p747description.htm.  Some of these on-line readings come to us courtesy of IUÕs Electronic Reserved Papers service.  To access these papers, you will need to enter in the password for the course: agent.  If the papers are not available on-line, then they are contained in the course pack.  The course pack can be obtained from the IMU Bookstore.

 

Class presentations

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.

 

Class projects

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

 

 

Spring Break

 

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.