CS423/523: Complex Adaptive Systems - Spring 2017

Course Information

Instructor: Matthew Fricke
Email:
Website: http://www.cs.unm.edu/~mfricke
Office: Travelstead B09B
Office Hours: Monday 1:00-3:00pm and Thursday 9:00-11: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 appointnent

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 Mitchel
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

  1. Background (January 16, 2017 - January 22, 2017)
    1. Mitchell, M. Complexity: A Guided Tour, Chapter 1, 2009
    2. Holland, J., Complex Adaptive Systems
    1. The Complex World
    2. Historical Context

  2. Dynamical Systems and Chaos (Jan 23rd - Feb 5th)
    1. Mitchell, M. Complexity: A Guided Tour, Chapter 2, 2009
    2. Flake, G. The Computational Beauty of Nature: Computer Explorations of Fractals, Chaos, Complex Systems, and Adaptation, Chapter 10, 2000
    3. Turing A., Chemical Basis of Morphogenesis
    4. Lorenz, E., Computational Chaos
    1. Basic Concepts
    2. Systems of Coupled Differential Equations
    3. Dynamical Systems
    4. Deterministic Chaos
    5. Computational 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
    1. Information Theory
    2. Algorithmic Complexity
    3. Generative Complexity

  4. Evolution and Genetic Algorithms (Feb 13th - Feb 19th)
    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

  5. Cellular Automata (Feb 20th - Feb 26th)
    1. Mitchell, M. Complexity: A Guided Tour, Chapter 10, 2009
    2. Neumann, J., Theory of Self Reproducing Automata, 1966
    3. Wolfram, S. Cellular Automata as Models of Complexity, 1984
    4. Mitchell, M. Complexity: A Guided Tour, Chapter 11, 2009
    5. Mitchell M. Evolving Cellular Automata to Perform Computations: Mechanisms and Impediments, 1994

  6. Modeling and Game Theory (Feb 27th - Marth 5th)
    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
    5. Axelrod, R., Timing of Cyber Conflict

    Miterm Review Lecture Notes

    Miterm from 2012

  7. Midterm Review, Read Chapter 12 in Mitchell for Wednesday, March 8th
  8. Midterm on Friday, March 10th

Spring Break (March 12th - March 19th)

  • Networks and Scaling (Mar 6th - Mar 26th)
    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
    6. Tero A. Rules for Biologically Inspired Adaptive Network Design, 2010
    7. Meyers, C. Software systems as complex networks: Structure, function, and evolvability of software collaboration graphs, 2003
    8. West, G. Life's Universal Scaling Laws, 2004
    9. Seoane, L., Phase transitions in Pareto optimal complex networks, 2015

  • Cannonical Complex Systems (March 27th-April 16th)
    1. Forrest, S. Computer immunology, 2007
    2. Smith, D. Mapping the Antigenic and Genetic Evolution of Influenza Virus, 2004
    3. Triani, V. Evolving Aggregation Behaviors in a Swarm of Robots, 2003
    4. Dorigo, M. Swarmanoid: a Novel Concept for the Study of Hetrogeneous Robotic Swarms, 2011
    5. Brooks, R. New Approaches to Robotics, 2010
    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
    8. Marshall, J. On Optimal Decision-Making in Brains and Social Insect Colonies, 2009
    9. Doyle, J., Robustness and the Internet

    1. Ant Colonies
    2. The Internet
    3. Immunolgy
    4. Social Systems and Economics
    5. Swarm Robotics
    6. Cognition and Neural Networks
    7. Autocatalisis and Chemical Reaction Networks
    8. Software

  • Complexity Revisited (Week 16)
    1. Mitchell, M. Complexity: A Guided Tour, Chapter 18, 2009
    2. Mitchell, M. Complexity: A Guided Tour, Chapter 19, 2009

    Assignments and Grading

    Grade Breakdown

    1. Projects: 4x15%=60%
    2. Exams: 2x15%=30%
    3. (Graduate Students) Class Presentation: 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.
    3. 5 page paper: 35%
      1. ACM Latex ToG Template
    4. 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 recieve a score of zero.

    Project 1: Dynamical Systems and Chaos

    Assigned Jan 18th.

    Papers due on February 3rd. Reviews due on February 10th.

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

    Project 3: Game Theory and Genetic Algorithms

    Assigned Feb 13th.

    Papers due on Feb 14th. Reviews due on March 6th.

    Project 2: Cellular Automata and Computation

    Assigned March 8th.

    Papers due on Mar 29th. Reviews due April 5th.

    February 27th is the last day to drop without dean's permission.

    Project 4: Network Science

    Assigned April 7th.

    Papers due on April 28th. Reviews due on May 5th.

    Exams

    Midterm Exam

    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

    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.