CS423/523: Complex Adaptive Systems - Spring 2017

Course Information

Adjunct Assistant Professor: Matthew Fricke
Email:
Website: http://www.cs.unm.edu/~mfricke
Office: Travelstead B09B
Office Hours: Monday 1:00-2:00pm and Thursday 9:00-10:00am.

Teaching Assistant: Bianca Cesina Bologa
Email:
Website:
Office: Travelstead B05A
Office Hours: Tu 4:00-5:00pm and Wed 1:00-2:00pm or by appointment

Mailing List:

Course Description

A graduate level introduction to selected topics in complex adaptive systems focusing on computational tools to simulate and measure complexity, and analysis of biological and social complex adaptive systems. Topics include definitions of complexity, cellular automata, networks, evolution and genetic algorithms, dynamical systems, scaling and fractals, ant colony algorithms and swarm intelligence.

Textbook

We don't have a textbook for this course, but we'll use as a guide Complexity, A Guided Tour. Each week we'll read journal articles to explore concepts from the book in more technical and intellectual depth.

Complexity: Title: Complexity: A Guided Tour
Author: Melanie Mitchell
Publisher: Oxford University Press

Paperback (2011):
ISBN-10: 0199798109
ISBN-13: 978-0199798100
or,
Hardcover (2009):
ISBN-10: 0195124413
ISBN-13: 978-0195124415

Course Topics and Reading list

Graduate and undergraduate students are to read the chapters assigned in Mitchell and Flake. Graduate Students are additionally expected to read all papers listed below unless marked "optional".

  1. Background (January 16, 2017 - January 22, 2017)

    2. Read the following by Jan 23rd.
    1. Mitchell, M. Complexity: A Guided Tour, Chapter 1, 2009
    2. Holland, J., Complex Adaptive Systems
    1. The Complex World
      1. Lecture 1: The Complex World

  2. Dynamical Systems and Chaos (Jan 23rd - Feb 5th)

    1. Mitchell, M. Complexity: A Guided Tour, Chapter 2, 2009 (Read by Jan 27th)
    2. Flake, G. The Computational Beauty of Nature: Computer Explorations of Fractals, Chaos, Complex Systems, and Adaptation, Chapter 10, 2000 (Read by Jan 30th)
    3. May, R. Simple Mathematical Models with Very Complicated Dynamics, 1976 (Read by Jan, 27th)
    4. Krivine, H., Discrete-time and continuous-time modelling: Some bridges and gaps, 2007 (Optional)
    1. Turing A., Chemical Basis of Morphogenesis (Optional)
    2. Lorenz, E., Computational Chaos(Advanced)(Mixon-Baca and Arefi, Feb 1st), Student Presentation
    1. Lectures
      1. Lecture 2: Basics
      2. Lecture 2: Chaos
      3. Lecture 4: Fixed Points
      4. Lecture 5 and 6: Fixed Point Analysis and Ergodicity
      5. Lecture 7: Order Out of Chaos

  3. Measures of Complexity (Feb 6th - Feb 12th)

    1. Mitchell, M. Complexity: A Guided Tour, Chapter 3, 2009
    2. Mitchell, M. Complexity: A Guided Tour, Chapter 4, 2009
    3. Mitchell, M. Complexity: A Guided Tour, Chapter 7, 2009
    4. Gell-Mann, M. What is Complexity?, Complexity, Vol 1, no. 1, 1995 (Read by Feb 12th)
    5. Crutchfield, J. Between Order and Chaos, Nature Physics, 2012(Read by Feb 12th)

    1. Lecture 8: Measuring Complexity

  4. Evolution and Genetic Algorithms (Feb 13th - Feb 26th)

    1. Mitchell, M. Complexity: A Guided Tour, Chapter 5, 2009
    2. Mitchell, M. Complexity: A Guided Tour, Chapter 6, 2009
    3. Mitchell, M. Complexity: A Guided Tour, Chapter 8, 2009
    4. Mitchell, M. Complexity: A Guided Tour, Chapter 9, 2009
    5. Hughes, A. The Central Dogma and Basic Transcription, 2003
    6. Losos, J. Evolutionary Biology for the 21st Century, 2013
    7. Wilson, E. Evolution and Our Inner Conflict, 2012 (Optional)
    8. Forrest, S. Genetic Algorithms: Principles of Natural Selection Applied to Computation, 1993
    9. Floreano, D. Evolution of Adaptive Behaviour in Robots by Means of Darwinian Selection, 2010
    10. Weimer, W. Automatically Finding Patches Using Genetic Programming, 2009

    1. Lecture 9: Genetic Algorithms
    2. Lecture 10: Genetic Algorithms
    3. Notes on creating figures for Project2: Genetic Algorithms

  5. Cellular Automata (Feb 27th - March 6th)

    1. Mitchell, M. Complexity: A Guided Tour, Chapter 10, 2009
    2. Neumann, J., Theory of Self Reproducing Automata, 1966(Ridens & Shubsda, March 1st) Student Presentation
    3. Wolfram, S. Cellular Automata as Models of Complexity, 1984(Collishaw & Kumar, March 3rd) Student Presentation
    4. Mitchell, M. Complexity: A Guided Tour, Chapter 11, 2009
    5. Mitchell M. Evolving Cellular Automata to Perform Computations: Mechanisms and Impediments, 1994

    1. Lecture 11: Modelling and Cellular Automata

    Midterm Review, March 6th

    Read Chapter 12 in Mitchell for Wednesday, March 8th

    Midterm on Friday, March 10th

    Spring Break (March 12th - March 19th)

    Grade Distribution at Midterm

  6. Modelling and Game Theory (March 20th - April 2nd)

    1. Mitchell, M. Complexity: A Guided Tour, Chapter 13, 2009
    2. Mitchell, M. Complexity: A Guided Tour, Chapter 14, 2009
    3. Axelrod, R. The Evolution of Cooperation Chapters 1, 2, and 9, 1981
    4. Press, W. Iterated Prisoner's Dilemma Contains Strategies that Dominate any Evolutionary Opponent, 2012(Terrell, March 22th)Student Presentation
    5. Ehlen, M., "The Effects of Bank Size on Equilibrium Price Dispersion", 2002(Kay, March 24th)Student Presentation
    6. Axelrod, R., Timing of Cyber Conflict(Cashin, March 29th)Student Presentation
    Speaker: Mark Ehlen, Ph.D., Research Scientist, Sandia National Labs, March 27th
    Speaker: Josh Hecker, Ph.D., UNM-NASA Swarmathon Technical Lead, March 31st. "Modeling Swarm Robotics as a Complex System".
    Presentation

  7. Networks and Scaling (April 3rd - April 16th)

    1. Mitchell, M. Complexity: A Guided Tour, Chapter 15, 2009
    2. Mitchell, M. Complexity: A Guided Tour, Chapter 16, 2009
    3. Mitchell, M. Complexity: A Guided Tour, Chapter 17, 2009
    4. Clauset, A. Power-law Distributions in Empirical Data, 2009
    5. Barabasi, A. Emergence of Scaling in Random Networks, 1999 (Optional)
    6. Tero A. Rules for Biologically Inspired Adaptive Network Design, 2010(Knez, April 10th)Presentation
    7. Meyers, C., Software systems as complex networks: Structure, function, and evolvability of software collaboration graphs, 2003(McIver & Liu, April 10th)Student Presentation
    8. West, G., Life's Universal Scaling Laws, 2004
    9. Seoane, L., Phase transitions in Pareto optimal complex networks, 2015 (Optional)
    Speaker: Melanie Moses, Ph.D., Associate Professor, UNM Computer Science, April 7th. "Scaling Laws in Nature and Computer Science".
    Presentation

    1. Lecture 12: Self Organised Criticality
    2. Lecture 13: Intro to Network Science

  8. Canonical Complex Systems (April 17th - May 14th)

    1. Forrest, S. Computer immunology, 2007(Smith & Macias, April 19th)Student Presentation
    2. Smith, D. Mapping the Antigenic and Genetic Evolution of Influenza Virus, 2004(Surjadidjaja & Cai, April 19th)Student Presentation
    3. Triani, V. Evolving Aggregation Behaviors in a Swarm of Robots, 2003(Tasnim & Siddiquee, April 26th)Student Presentation
    4. Dorigo, M. Swarmanoid: a Novel Concept for the Study of Hetrogeneous Robotic Swarms, 2011(Salmonson & Tashakkori, April 28th)
    5. Brooks, R. New Approaches to Robotics, 1991(Bojja, May 3rd)Student Presentation
    6. Williams, L. Evolution of Tail-Call Optimization in a Population of Self-Hosting Compilers, 2013
    7. Dorigo, M. Ant Colony Optimization: Artificial Ants as a Computational Intelligence Technique, 2006 (Optional)
    8. Marshall, J. On Optimal Decision-Making in Brains and Social Insect Colonies, 2009 (Optional)
    9. Doyle, J., Robustness and the Internet(Byrd, May 3rd)

    1. The Internet
    2. Immunology
    3. Social Systems and Economics
    4. Swarm Robotics
    5. Ant Colonies
    6. Cognition and Neural Networks
    7. Autocatalysis and Chemical Reaction Networks
    8. Software
    Speaker: Stephanie Forrest, Ph.D., Distinguished Professor, UNM CS, April 17th. Presentation
    Speaker: Lance Williams, Ph.D., Associate Professor, UNM CS, April 21st.
    Presentation
    Note: Instructor will be at Kennedy Space Center from April 15th to April 22nd. Guest lecturers will cover classes.

    1. Lecture 14: Canonical Complex Systems

    Assignments and Grading

    Grades will be posted at UNM Learn.

    Grade Breakdown

    1. Projects: 4x15%=60%
    2. Exams: 2x15%=30%
    3. Class participation: 10%
    All projects code will be maintained under github.

    Class Presentation (Graduate Students Only)

    A 20 minute group presentation on a paper listed on the course website.

    Projects

    You will be assigned to work groups.

    Project Format

    1. github.com commits: 35%
      2. You will be graded on:
      1. Commit message quality.
      2. Code organisation and readability.
      3. Code progression.
      Minimum requirements:
      1. A least 10 commits across at least 5 different days.
      2. Github readme describing how to compile the code under Ubuntu 14.04 or 16.04, including required packages.
    2. 5 page paper: 35%
      1. ACM Latex ToG Template
    3. Paper peer review: 30%
      1. You will be graded on how accurately you review the two papers you are assigned.
      2. Project Review Guidelinestex

    Paper Due Dates

    Papers will be downloaded from overleaf and code will be pulled from github on the paper due date specified for each project at 6:00pm Mountain Time.

    Review Due Dates

    Papers will be made available to review at 8:00pm on the paper due date and reviews are due at 6:00pm Mountain Time on the review due date specified.

    Late policy

    Projects will be downloaded as described above. Papers or project code that does not compile at 6:00pm on the due dates will receive a score of zero.

    Project 1: Dynamical Systems and Chaos

    Assignment.

    Assigned Jan 23th.

    Papers due on February 10th. Reviews due on February 17th.

    February 3rd is also the drop without a 'W' grade and full refund deadline.

    Project 2: Genetic Algorithms

    Assignment.

    Portable Memory Array Redcode Simulator: pmars
    and with support for graphics: pmarsx.
    Manual
    Don't forget to change permissions on pmars to make it executable: chmod +x pmars

    Wilkies Benchmark

    Fulvio C., Evolving Assembly Programs: How Games Help Microprocessor Validation, 2005 (Optional)

    Assigned Feb 20th.

    Papers due on March 10th. Reviews due on March 20th. In class competition on March 20th.

    Project 3: Cellular Automata and Modelling

    Assignment.

    Assigned March 21st.

    Papers due on April 14th. Reviews due April 21st.

    Project 4: Paper Review Notes

    Assigned April 21st.

    Papers due on May 5th. There will be no reviews for this project.

    April 14th is the last day to drop without dean's permission.

    Exams

    Content: there will be two versions of the exams. For undergraduate students the exams will cover material from the assigned readings in Complexity a Guided Tour. For graduate students the exams will also cover the papers listed on the course website. The questions will be designed to test whether students have read and understand the main ideas of the readings. All students will also be expected to be able discuss the ideas and tools they used in writing their projects.

    Format: short answer and multiple choice.

    Midterm Exam

    Graduate Sample Midterm

    Undergraduate Sample Midterm

    Graduate Midterm Solutions

    Undergraduate Midterm Solutions

    Date: March 10th

    O'Conner, K., "Should I Give the Exam Before or After the Break?", Teaching of Psychology Vol 41, Issue 1, pp. 63-65, 2013.

    Final Exam

    The final exam will cover the readings since the midterm exam.

    Graduate Sample Final

    Undergraduate Sample Final

    May 12th, 7:30-9:30am.

    Exam Make-ups

    There will be a single exam make up time for both the midterm and final exams. The make-up will be on Saturday, May 13th at 8:00am in my office. The make up exam will be different, but at least as difficult, as the regularly scheduled exams.