Course Syllabus

Mondays 1:10pm - 3:40pm, 415 Schapiro Cepser

Synopsis

This course will cover topics in evolutionary algorithms and their application to open-ended optimization and design. The field of evolutionary computation tries to address large-scale optimization and planning problems through stochastic population-based methods. It draws inspiration from evolutionary processes in nature and in engineering, and also serves as abstract models for these phenomena. Evolutionary processes are generally weak AI methods that require little information about the problem domain and hence can be applied across a wide variety of applications with relatively little upfront investment. They are especially useful for open-ended problem domains for which little prior formal knowledge exists and the number of parameters is undefined, such as for the general engineering design process. This course will provide insight to a variety of evolutionary computation paradigms, such as genetic algorithms, genetic programming, and evolutionary strategies, as well as governing dynamics of co-evolution, arms races and stable states. New methods involving symbiosis models and pattern recognition will also be presented. The material will be intertwined with discussions of representations and results for design problems in a variety of problem domains including software, electronics, and mechanics.

Prerequisites

Programming experience. For example, you should be comfortable writing a breadth first search on a binary tree. If you don't know what that means, you may need to take a Data Structures and Algorithms course first, or study a classic text book like Cormen's Introduction to Algorithms.

Homeworks and projects can be done in any language of your choice. Use of efficient (compiled) language is recommended.

Grading and requirements

Grading will be based on

  • 30% Two homework assignments (15% each)
  • 50% Term project
  • 20% Final exam

In the project, students will be asked to examine some aspect of evolutionary processes or apply evolutionary methods to an interesting problem of their choice.

Academic integrity: Students can discuss concepts but are expected to write their own code and acknowledge the work of others. Use of any open source library is permitted, but source and content must be acknowledged.

Syllabus

Lectures and readings will cover some or all of these topics:

  1. Optimization background and terminology: Gradient optimization methods, sampling methods, linear programming, combinatorial optimization.
  2. Evolutionary Biology background and terminology: Genotype and phenotype, unit of selection, genes and traits, chromosomes, alleles, diploid and haploid, fitness, mutation and recombination. Selection, variation and landscapes. The strengths and weaknesses of the evolutionary model. Inductive bias. The “No free lunch” theorem.
  3. Genetic Algorithms: Representation, operators, and standard algorithm. The building block hypothesis and the schema theorem.
  4. Evolutionary strategies: Evolution in continuous variables. Transformations.
  5. Genetic Programming. Building blocks and architecture-altering operators. Libraries and Trees.
  6. Selection mechanisms: Fitness proportionate, rank, tournament, Stochastic Universal Sampling and Boltzman selection methods. Niching methods. Spatial methods. Consequences of selection models.
  7. Artificial landscapes and test functions: The Two-armed bandit problem. Multi-modal and deceptive functions. Royal roads. N-k landscapes. Hierarchical and fractal functions. Pareto evolution.
  8. Co-evolution: Multiple populations and single-population co-evolution, relative and absolute fitness, engagement and gradient loss, the red queen effect. The credit assignment problem.
  9. Evolutionary dynamics and game-theoretic models: Evolutionary stable states, cycles and chaos. The iterated prisoners dilemma. Evolution of cooperation.
  10. Evolution and learning: Plasticity and life-time learning. Lamarckian learning, How learning can guide evolution. The Baldwin effect.
  11. Symbiosis as a source of evolutionary innovation. Macro-mutations, Major transitions in evolution, symbiosis and symbiogenesis. How symbiosis can guide evolution.
  12. Evolutionary algorithms as models: Modeling sexual selection, modeling ecosystems, artificial life.
  13. Evolutionary robotics and evolutionary hardware: Evolving control. Evolving morphology. Body-brain co-evolution. Evolution in simulation and in reality. The case for and against simulation.
  14. Modularity and regularity in evolution. The scaling problem and the curse of dimensionality. Evolvability. Module acquisition. Developmental models. Compositional and hierarchical approaches.
  15. Swarm intelligence, particle swarm optimization
  16. Estimation exploration approaches for model inference

The topics above will include also examples for a variety of domains, such as robotics, scheduling, structural and architectural design, neural networks, electronics, software and games.

Textbooks and references

  1. Melanie Mitchell An introduction to genetic algorithms MIT Press

Tentative Schedule 

Week Lecture date Topics Assigment due on Friday
1 Mon, Sep 11 Introduction to Evolutionary Algorithms Parametric optimization
2 Mon, Sep 18 Genetic algorithms The building Block Hypothesis
3 Mon, Sep 25 Genetic Linkage and Epistasis   Selection Mechanisms Asssignment 1 due (GA)
4 Mon, Oct 02 Genetic programming  Diversity Maintenance
5 Mon, Oct 09 Generative and Developmental encodings Multiobjective optimization Assignment 2 due (GP)
6 Mon, Oct 16 Coevolution concepts Coevolutionary dynamics
7 Mon, Oct 23 Project proposal presentations Project Proposals Due
8 Mon, Oct 30 Applications: Kinematics, Photonics Evolutionary Hardware and Robotics
9 Mon, Nov 06 Break
10 Mon, Nov 13 Particle Swarm Optimization Estimation of Distribution Algorithms Project interim report 1 due
11 Mon, Nov 20 Neuroevolution Artificial Life
12 Mon, Nov 27 Mock exam Project Updates Project interim report 2 due
13 Mon, Dec 04 Fundamentals: Population sizing, deceptive problems, and linkage Hybrid models: Learning & Evolution
14 Mon, Dec 11 Project final presentations Project final reports due
15 Mon Dec 18, 1:10-4pm Final exam (tentative) See registrar

Course Summary:

Date Details