I485/H485/I585: Biologically Inspired Computing
I601: Introduction to Complex Systems
Fall 2011
Instructor: Luis M. Rocha, Center for Complex Networks and Systems, School of Informatics and Computing and Cognitive Science Program, Indiana University
Associate Instructor: Santosh Manicka.
I484/H400 Class Location and Time: 11:15AM-12:30PM, Room: Informatics West Building, Room 105 (Tuesday) & Room 109 (Thursday)
I585/I601 Class Location and Time: 9:30AM - 10:45AM, Tuesdays and Thursdays, Room: Informatics West Building, Room 107
Course Description
Biological organisms cope with the demands of their environments using solutions quite unlike the traditional human-engineered approaches to problem solving. Biological systems tend to be adaptive, reactive, and distributed. Bio-inspired computing is a field devoted to tackling complex problems using computational methods modeled after design principles encountered in nature. This course is strongly grounded on the foundations of complex systems and theoretical biology. It aims at a deep understanding of the distributed architectures of natural complex systems, and how those can be used to produce informatics tools with enhanced robustness, scalability, flexibility and which can interface more effectively with humans. It is a multi-disciplinary field strongly based on biology, complexity, computer science, informatics, cognitive science, robotics, and cybernetics.
Aims: Students will be introduced to fundamental topics in bio-inspired computing, and build up their proficiency in the application of various algorithms in real-world problems.
Pre-requisites: For I485/H485: INFO-I 211, or CSCI-C 212, or CSCI-H 212, or Instructor approval.
Syllabus
Lecture Outline
- What is Life?
- What is so cool about life?
- Life and Information
- The Logical Mechanisms of Life
- What is Computation?
- What is so cool about computation?
- Universal Computation and Computability
- Simulations and Realizations
- Imitation of Life
- Computational Beauty of Nature (fractals, L-systems, chaos)
- Bio-inspired computing
- Natural computing
- Biology through the lens of computer science
- Complex Systems and Artificial Life
- Complex Networks
- Self-Organization and Emergent Complex Behavior
- Cellular Automata
- Boolean Networks
- Development and Morphogenesis
- Open-ended evolution
- Evolutionary Algorithms
- Evolution and Adaptation
- Genetic Algorithms
- Genetic Programming
- Collective Behavior and Swarm Intelligence
- Social Insects, Stigmergy and Swarm Intelligence
- Competition and Cooperation
- Communication and Multi-Agent simulation
- Immunocomputing
- A distributed design for computational intelligence
- Engineering Application
Course Evaluation
- Participation: 15%.
- Based upon attendance and participation.
- Presentation and Discussion or Assignments: 35%
- Undergraduate students (sections I485/H485) will complete 4 assignments (5 for H485) using algorithms introduced in class. Graduate students (sections I585/I601) will present and lead the discussion of an article related to the class materials. This includes presenting concepts necessary to understand the article.
- Project or Term Paper: 50%
- Depending on background (e.g. CS, informatics, Cog Sci, Psychology) and program (undergraduate, Masters or Phd), students will either tackle a real problem using bio-inspired algorithms, or write a term paper. In either case, students are expected to continuously consult with the instructor regarding the scope and depth of the project or paper.
Office Hours
- Luis Rocha
- Wednesdays: 10am – 12pm, Informatics East, 919 10th Street, Room #301
- Santosh Manicka
- Fridays: 11:30am - 1.30pm, Informatics East, 919 10th Street, Room #310A.
I485 Labs/Assignments
- Lab 1: Introduction to bioinspired algorithms in Python
- Lab 2: L-systems
- Lab 3: Cellular Automata & Boolean Networks
- Lab 4: Genetic Algorithms
- Lab 5: Ant Clustering Algorithm
Course Materials
- Lecture notes
- 1. What is Life?
- 2. The Logical Mechanisms of Life
- 3. Formalizing and Modeling the World (pdf document)
- 4. Self-Organization and Emergent Complex Behavior
- 5. Reality is Stranger than Fiction (pdf document)
- 6. Von Neumann and Natural Selection (pdf document)
- 7. Modeling Evolution: Evolutionary Computation
- Lecture slides I485
- Lecture 1 - What is Life?
- Lecture 2 - Life and Information
- Lecture 3 - The Logical Mechanisms of Life
- Lecture 4 - Computation
- Lecture 5 - Modeling Principles of Organization
- Lecture 6 - Self-Similarity and L-Systems
- Lecture 7 - Dynamical Systems and Attractor Behavior
- Lecture 8 - The Logistic Map and Boolean Networks
- Lecture 9 - Cellular Automata and the Edge of Chaos
- Lecture 10 - Cellular Automata: From the Edge of Chaos to Computation
- Lecture 11 - information transmission: From emergent computation to the gene
- Lecture 12 - Fiction, Reality, and Information in Life
- Lecture 13 - Self-Reproduction and Open-ended Evolution
- Lecture 14 - Genetic Algorithms
- Lecture 15 - Genetic Encodings
- Lecture 16 - Genetic Programming
- Lecture 17 - Collective Behavior
- Lecture 18 - Ant Clustering Algorithm
- Lecture 19 - Swarms and Stigmergy
- Lecture 20 - Collective Intelligence
- Lecture 21 - The Immune System
- Lecture slides I585/I601
- Lecture 1 - What is Life?
- Lecture 2 - Life, Evolution, and Intelligent Design
- Lecture 3 - The Complexity Threshold of Life
- Special Presentation - Enrique Areyan: Chris Langton's Artificial Life and discussion of Howard Pattee's Simulations, Realizations, and Theories of Life
- Lecture 4 - Information
- Lecture 5 - Programming Life
- Lecture 6 - Computation
- Lecture 7 - Modeling Principles of Organization
- Special Presentation - Ian Wood: Chris Adami's Digital genetics: unraveling the genetic basis for evolution and discussion of Tom Ray's Evolution, ecology and optimization of digital organisms
- Lecture 8 - Self-Similarity and L-Systems
- Lecture 9 - Dynamical Systems and Attractor Behavior
- Lecture 10 - The Logistic Map and Boolean Networks
- Special Presentation - Scott McCaulay: Hinton and Nowlan's "How learning can guide evolution" Paper
- Special Presentation - Jonathan Frankel: Kristian Lindgren's "Evolutionary Phenomena in Simple Dynamics".
- Lecture 11 - Self-Organization
- Lecture 12 - The Edge of Chaos and Cellular Automata
- Lecture 13 - Computation and the Edge of Chaos
- Lecture 14 - Information transmission: From emergent computation to the gene
- Lecture 15 - Self-Reproduction and Open-ended Evolution
- Lecture 16 - Life is Stranger than Fiction
- Special Presentation - Shad Gross: Crutchfield and Mitchell's "The Evolution of Emergent Computation" Paper
- Special Presentation - Ikhyun Park: Steingrube et al's "Self-organized adaptation of a simple neural circuit enables complex robot behaviour".
- Lecture 17 - Genetic Algorithms
- Lecture 18 - Genetic Encodings and Genetic Programming
- Special Presentation - Alin Cosmanescu: Schmidt and Lipson's "Distilling Free-Form Natural Laws from Experimental Data"
- Special Presentation - Quan Zhang: Thompson and Gopal's Genetic algorithm learning as a robust approach to RNA editing site prediction
- Lecture 19 - Collective Behavior
- Lecture 20 - Ant Clustering Algorithm
- Special Presentation - Damion Junk: Varela, Maturana and Uribe's Autopoiesis and Varela's Patterns of Life
- Special Presentation - Brett Pfingston: Eschel Ben-Jacobl's Learning from Bacteria about Natural Information Processing
- Lecture 21 - Swarms, Stigmergy, and Collective Intelligence
- Special Presentation - Alexander Gates: Castellano et al's Statistical physics of social dynamics
- Lecture 22 - The Immune System
- Special Presentation - Christopher Volz : Bonachella et al's Universality in Bacterial Colonies
- Printed Resources in OnCourse
- Class Handouts
- Adami, C. [2006]. "Digital Genetics: Unraveling the Genetic Basis of Evolution". Nature Reviews Genetics 7 (2006) 109-118
- Belew, R.K. [1990], "Evolution, Learning and Culture: Computational Metaphors for Adaptive Search," Complex Systems, 4 (1):11-49.
- Ben-Jacob, Eshel. 2009. "Learning from bacteria about natural information processing." Annals of the New York Academy of Sciences 1178: 78-90.
- Bonachela, Juan A., Carey D. Nadell, João B. Xavier, and Simon A. Levin. [2011] "Universality in Bacterial Colonies" (pdf). Journal of Statistical Physics. 144 (2): 303-315.
- Castellano, Claudio, Santo Fortunato, and Vittorio Loreto [2009]. "Statistical physics of social dynamics". Reviews of Modern Physics 81 (2) (May): 591-646.
- Crutchfield, J.P. and M. Mitchell [1995]."The evolution of emergent computation." Proc. National Academy of Sciences, USA, Computer Sciences. Vol. 92, pp. 10742-10746.
- Dennet, D.C. [2005]. "Show me the Science". New York Times, August 28, 2005
- Glickman, Matthew, Justin Balthrop, and Stephanie Forrest. 2005. "A Machine Learning Evaluation of an Artificial Immune System." Evolutionary Computation 13(2): 179.
- Hinton, G.E. and S.J. Nowlan [1987]."How learning can guide evolution." Complex Systems. Vol. 1, pp.495-502.
- Kanehisa, M. [2000]. Post-genome Informatics. Oxford University Press. Chapter 1, Blueprint of life, pp. 1-23.
- Lindgren, K. [1991]."Evolutionary Phenomena in Simple Dynamics." In: Artificial Life II. Langton et al (Eds). Addison-wesley, pp. 295-312.
- Lipson, H. and J. B. Pollack [2000] "Automatic design and Manufacture of Robotic Lifeforms", Nature, 406: 974-978.
- Lipson, H. [2005] "Evolutionary Design and Evolutionary Robotics", Biomimetics, CRC Press (Bar Cohen, Ed.) pp. 129-155.
- Pattee, H.H. [1995]. "Summary of most significant points about biological systems".
- Ray, T. S. [1992]. "Evolution, ecology and optimization of digital organisms". Santa Fe Institute working paper 92-08-042.
- Schmidt, M. and H. Lipson [2009]. "Distilling Free-Form Natural Laws from Experimental Data". Science, 324: 81-85.
- Scientific American: Special Issue on the evolution of Evolution, January 2009.
- Steingrube, S., M. Timme, F. Worgotter and P. Manoonpong [2010]. "Self-organized adaptation of a simple neural circuit enables complex robot behaviour". Nature Physics. 6: 224 - 230.
- Thompson, James, and Shuba Gopal. 2006. "Genetic algorithm learning as a robust approach to RNA editing site prediction." BMC bioinformatics 7 (1): 145.
- Varela, Francisco J.; Maturana, Humberto R.; & Uribe, R. [1974]. �Autopoiesis: the organization of living systems, its characterization and a model�. Biosystems 5 187�196.
- Varela, F.J. [1996]. "The early days of autopoiesis". Systems Research, 13(3):407-416.
- Varela, F.J. [1997]. "Patterns of Life: Intertwining Identity and Cognition". Brain and Cognition, 34(1):72-87.
- Class Book
- Nunes de Castro, Leandro [2006]. Fundamentals of Natural Computing: Basic Concepts, Algorithms, and Applications. Chapman & Hall. On half.com. On Amazon.com. On Google Books.
- Recommended and Alternative Books
- Forbes, N. [2004]. Imitation of Life: How Biology is Inspiring Computing. MIT Press. Available in electronic format free of charge for IU students at 24x7 books Via the IU library.
- Flake, G. W. [1998]. The Computational Beauty of Nature: Computer Explorations of Fractals, Complex Systems, and Adaptation. MIT Press. Available in electronic format free of charge for IU students at MIT CogNet Via the IU library.
- Gleick, J. [2011]. The Information: A History, a Theory, a Flood. Random House.
- Mitchell, M. [2009]. Complexity: A Guided Tour. Oxford University Press. Available in electronic format free of charge for IU students.
- Mitchell, M. [1999]. An Introduction to Genetic Algorithms. MIT Press. Available in electronic format free of charge for IU students at 24x7 books Via the IU library or MIT CogNet
- Nunes de Castro, Leandro and Fernando J. Von Zuben [2005]. Recent Developments in Biologically Inspired Computing. MIT Press. Available in electronic format free of charge for IU students at 24x7 books Via the IU library.
