CS 591 Spring 03

Course Topics

I. Introduction
Lecture:		What is a complex system? How do we measure the complexity of a system?
Discussion:		Elements of Complex Adaptive Systems

Readings:

J. Holland, Hidden Order, Ch. 1

II. Evolution and genetic algorithms

Biological underpinnings
Lecture:		Introduction to genetics (no assigned reading)
Discussion:		Origin of Species

Introduction to genetic algorithms
Lecture:		The simple GA and example applications (Mitchell, Ch. 1; Ch. 2 recommended)
Discussion:		Major Transitions in Evolution

Mathematical underpinnings
Lecture:		The central dogma of genetic algorithms and its criticisms (no assigned reading)
Discussion:		Finite populations induce metastability in evolutionary search

Genetic algorithms as scientific models
Lecture:		What is a model? Homomorphic theory of modeling (no assigned reading)
Presentations:		Classifier Systems and Echo

Background and discussion of programming assignment
Discussion:		GA software and other assignment details

Readings:

Origin of Species by C. Darwin. (Ch. 1-3)
An Introduction to Genetic Algorithms by M. Mitchell (Ch. 1, 2)
The Major Transitions in Evolution by J. Maynard Smith and E. Szathmary (Ch. 1)
E. van Nimwegen, et al. "Finite populations induce metastability in evolutionary search." Physics Letters A 229 (1997)
KO. Stanley and R. Miikkulainen. "Evolving neural networks through augmenting topologies." GECCO 2002.
KO Stanley and R. Miikkulainen. "Efficient reinforcement learning through neural network topologies." GECCO 2002.

Choose either Echo:
Hidden Order by J. Holland (Ch. 3)
P. Hraber, et al. "The Ecology of Echo." Artificial Life 3:3 (1997)

Or Classifier Systems:
Hidden Order by J. Holland Ch. 2
L. Booker, et al. "Classifier systems and genetic algorithms." Artificial Intelligence 40 (1989).

III. Computational immunology

Biological underpinnings
Lecture:		Overview of the adaptive immune system.
Lecture:		Immunology as information processing.

Biologically inspired approaches to computer security
Discussion:		Artificial Immune Systems I
		"Self-nonself discrimination in a computer"
		"A biologically inspired immune system for computers"
Disscussion:		Discussion: Artificial Immune Systems II
		"Architecture for an artificial immune system"
		"Coverage and Generalization in an Artificial Immune System"
Presentations:		Other definitions of self (system calls, JVMs)
Presentations:		Homeostasis and diversity
		Homeostasis: "Automated response using system call delays"
		Diversity: "Building diverse computer systems"
Presentations:		Epidemiology
		Virus epidemiology

Mathematical underpinnings
Lecture:		Positive and negative detection (no assigned reading)

Immunology modeling
Lecture:		Computational models of immunology (no assigned reading)

Readings:

Recommended: How the Immune System Works, Ch. 1 5
S. Hofmeyr "An interpretative introduction to the immune system." In L. Segel and I. Cohen Ed. Design Principles for the Immune system and Other Distributed Autonomous Systems (2001).
S. Forrest, et al. "Self-nonself discrimination in a computer." In Proc. of IEEE Symposium on Research in Security and Privacy (1994). (pdf, postscript)
J. Kephart "A biologically inspired immune system for computers." Artificial Life IV (1994).
S. Hofmeyr and S. Forrest "Architecture for an artificial immune system." Evolutionary Computation Journal 8:4 (2000). (pdf, postscript)
J. Balthrop et al. "Coverage and Generalization in an Artificial Immune System" GECCO 2002. (pdf, postscript)

Choose one of:
A. Somayaji and S. Forrest "Automated response using system call delays." Usenix 2000. (pdf, postscript)
H. Inoue and S. Forrest. "Anomaly intrusion detection in dynamic execution environments." New Security Paradigms Workshop. (pdf, postscript)
S. Forrest, et al. "Building diverse computer systems." HotOS 1997. (pdf, postscript)
J. Kephart and S. White "Directed Graph Epidemiological Models of Computer Viruses," Proc. IEEE Symposium on Security and Privacy (1991).
M. Newman, et al. "Email networks and the spread of computer viruses." Physical Review E 66, 035101 (2002). (pdf, postscript)

IV. Cellular automata and artificial life

Cellulax Automata and artificial life
Lecture:		Cellular automata and the game of life
Discussion/ Presentations:		Self reproducing CAs; Dynamics and computation in CAs
Lecture:		Tierra
Discussion:		Definitions of life

Modeling applications
Lecture:		Modeling cancer (no assigned reading)
		Sugarscape and extensions
Lecture:		Non zero sum games and the Iterated Prisoner's Dilemma (no assigned reading)

Mathematical underpinnings
Discussion:		The importance of being discrete

Readings:

M. Mitchell "Computation in cellular automata: A selected review." In Non standard Computation
J. Maynard Smith and E. Szathmary The Major Transitions in Evolution, Ch. 2-3.
R. Durrett and S. Levin "The importance of being discrete (and spatial)" Theoretical Population Biology 46:3 (1994)
J. M. Epstein and R. Axtell, Growing Artificial Societies, Ch 2.

V. Course Conclusion and Presentations

Discussion		How Nature Works
Discussion:		Catching Ourselves in the Act
Discussion:		Emergent Computation

Readings:
P. Bak How Nature Works Ch. 1 Springer Verlag (1996) H. Hendreiks-Jansen Catching Ourselves in the Act Ch. 1 MIT Press (1996). S. Forrest "Emergent Computation" Physica D 42:1 3 (1990)