I485/H400/I585: Biologically Inspired Computing
I601: Introduction to Complex Systems
Fall 2012
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, Informatics West Building, Room 107 (Tuesday) & Room 109 (Thursday Labs)
I585/I601 Class Location and Time: 9:30AM - 10:45AM, Informatics East Building, Tuesdays and Thursdays, Room 122
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.
- Lab Assignments: 35%
- I485 (H400) students will complete 4 (5) assignments using algorithms introduced in class.
- Project: 50%
- Students will tackle a real problem using bio-inspired algorithms. Students are expected to continuously consult with the instructor regarding the scope and depth of the project.
- Presentation and Discussion: 35%
- Students 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), 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.
I485/H400
I585/I601
Office Hours
- Luis Rocha
- Wednesdays: 10am – 12pm, Informatics East, 919 10th Street, Room #301
- Santosh Manicka
- Mondays: 1-3pm, Informatics East, 919 10th Street, Room #310A (or Room 001).
I485 Labs/Assignments
- Lab 1: Python review and Shannon entropy
- Lab 2: L-systems
- Lab 3: Cellular Automata & Boolean Networks
- Lab 4: Evolutionary 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
- Full Lecture Notes (pdf document)
- Lecture slides I485/H400
- Lecture 1 - What is Life?
- Lecture 2 - Life and Information
- Lecture 3 - The Logical Mechanisms of Life
- Lecture 4 - Systems and Biocomplexity
- Lecture 5 - Computation
- Lecture 6 - From Computation to Modeling Principles of Organization
- Lecture 7 - Self-Similarity and L-Systems
- Lecture 8 - Dynamical Systems and Attractor Behavior
- Lecture 9 - Dynamics, Chaos, and the Logistic Map
- Lecture 10 - Boolean Networks and Self-Organization
- Lecture 11 - Cellular Automata and the Edge of Chaos
- Lecture 12 - Cellular Automata: From the Edge of Chaos to Computation
- Lecture 13 - Information transmission: From emergent computation to the gene
- Lecture 14 - Turing's Tape, Self-Reproduction and Open-ended Evolution or why Life is Stranger than Fiction
- Lecture 15 - Self-Reproduction and Open-ended Evolution
- Lecture 16 - Genetic Algorithms
- Lecture 17 - Genetic Programming
- Lecture 18 - Collective Behavior
- Lecture 19 - Ant Clustering Algorithm
- Lecture 20 - Swarms, Stigmergy, and Collective Intelligence
- Lecture 21 - Collective Intelligence
- Lecture 22 - The Immune System
- Lecture 23 - The Adaptive Immune System and Artificial Immune Systems
- Lecture slides I585/I601
- Lecture 1 - What is Life?
- Lecture 2 - The Complexity Threshold of Life
- Lecture 3 - Life and Information
- Special Presentation - Jamie Murdock: Chris Langton's Artificial Life and discussion of Howard Pattee's Simulations, Realizations, and Theories of Life
- Lecture 4 - The Logical Mechanisms of Life
- Special Presentation - Paul Jenkins: 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 5 - Programming Life
- Lecture 6 - Computation
- Special Presentation - Eran Agmon: Varela, Maturana and Uribe's Autopoiesis and Varela's Patterns of Life
- Lecture 7 - Modeling Principles of Organization
- Lecture 8 - Self-Similarity and L-Systems
- Special Presentation - Karissa McKelvey: Hinton and Nowlan's "How learning can guide evolution" Paper
- Special Presentation - Ryland Sherman: Kristian Lindgren's "Evolutionary Phenomena in Simple Dynamics".
- Lecture 9 - Dynamical Systems and Attractor Behavior
- Lecture 10 - Chaos and The Logistic Map
- Lecture 11 - Boolean Networks and Self-Organization
- Lecture 12 - Cellular Automata and the Edge of Chaos
- Lecture 13 - Computation in Cellular Automata
- Lecture 14 - Information transmission and the gene
- Special Presentation - Nathaniel Rodriguez: Crutchfield and Mitchell's "The Evolution of Emergent Computation" Paper
- Special Presentation - Onur Varol: Schmidt and Lipson's "Distilling Free-Form Natural Laws from Experimental Data"
- Lecture 15 - Turing's Tape, Self-Reproduction and Open-ended Evolution or why Life is Stranger than Fiction
- Lecture 16 - Turing’s Tape, Von Neumann, and the design principle of open-ended complexity
- Lecture 17 - Self-Reproduction and Open-ended Evolution
- Lecture 18 - Genetic Algorithms
- Special Presentation - Alexander Barron:Petter and Saramäki's "Temporal Networks" Paper
- Special Presentation - Qing Kel: Yang-Yu, Slotine and Barabási's "Controllability of complex networks" Paper
- Lecture 19 - Genetic Programming
- Lecture 20 - Collective Behavior
- Lecture 21 - Swarms, Stigmergy, and Collective Intelligence
- Lecture 22 - The Immune System
- Printed Resources in OnCourse
- Class Readings
- Dennet, D.C. [2005]. "Show me the Science". New York Times, August 28, 2005
- Kanehisa, M. [2000]. Post-genome Informatics. Oxford University Press. Chapter 1, Blueprint of life, pp. 1-23.
- Langton, C. [1989]. "Artificial Life". In Artificial Life. C. Langton (Ed.). Addison-Wesley. pp. 1-47.
- Scientific American: Special Issue on the evolution of Evolution, January 2009.
- Adami, C. [2006]. "Digital Genetics: Unraveling the Genetic Basis of Evolution". Nature Reviews Genetics 7 (2006) 109-118
- Afek, Y., N. Alon, O. Barad, E. Hornstein, N. Barkai, and Z. Bar-Joseph. [2011]. “A Biological Solution to a Fundamental Distributed Computing Problem.” Science 331 (6014).
- Belew, R.K. [1990], "Evolution, Learning and Culture: Computational Metaphors for Adaptive Search," Complex Systems, 4 (1):11-49.
- 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.
- D. G. Gibson et al [2010]."Creation of a Bacterial Cell Controlled by a Chemically Synthesized Genome" Science. 329 (5987): 52-56
- Hinton, G.E. and S.J. Nowlan [1987]."How learning can guide evolution." Complex Systems. 1:495-502.
- Holme, Petter, and Jari Saramäki. 2012. “Temporal Networks”. Physics Reports. 519 (3): 97–125
- Kanehisa, M. [2000]. Post-genome Informatics. Oxford University Press. Chapter 1, Blueprint of life, pp. 1-23.
- Langton, C. [1989]. "Artificial Life". In Artificial Life. C. Langton (Ed.). Addison-Wesley. pp. 1-47.
- Lindgren, K. [1991]."Evolutionary Phenomena in Simple Dynamics." In: Artificial Life II. Langton et al (Eds). Addison-wesley, pp. 295-312.
- Liu, Yang-Yu, Jean-Jacques Slotine, and Albert-László Barabási. 2011. “Controllability of complex networks.” Nature 473 (7346): 167-173.
- Maccallum, R. M., Mauch, M., Burt, A., & Leroi, A. M. (2012). "Evolution of music by public choice". PNAS, 109 (30): 12081-12086
- Nature | Opinion [2010] "Life after the synthetic cell". Nature 465: 422–424
- 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.
- Szolnoki, A., Wang, Z., & Perc, M. (2012). "Wisdom of groups promotes cooperation in evolutionary social dilemmas". Scientific Reports, 2, 576.
- 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.
