Fall 2008 · CS 7726 / MAE 6500

Evolutionary Computation and Design Automation

 

Tue Thu 2:55-4:10 / Upson 111  / Hod Lipson  

See Schedule / Readings

 

Synopsis

Seminar course in optimization and evolutionary algorithms, and their application to open-ended computational design. The course provides insight to a variety of evolutionary computation paradigms, as well as governing dynamics of co-evolution, arms races and symbiosis. Includes topics artificial life, evolutionary robotics and applications in a variety of domains in engineering, science, and art. Suitable for students interested in computational techniques for addressing open-ended design problems and for those interested in computational models of evolutionary discovery. Course will be comprised of lectures, paper readings and discussions. Grading based on critical paper reviews and optional individual projects. Prerequisites: programming or permission of instructor.

 

This course will cover advanced topics in evolutionary algorithms and their application to open-ended computational 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 methods that require little information about the problem domain and hence can be applied across a wide variety of applications. They are especially useful for open-ended problem domains for which little 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 mediocre 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.

Grading and requirements

The course will be a combination of lectures and paper reviews followed by critical discussions. Grading will be based on (a) some homework assignments, and (b) individual term projects in which students will be asked to examine some aspect of evolutionary processes or apply evolutionary methods to an interesting problem of their choice (often thesis-related). Academic integrity: Students can discuss concepts but are expected to write their own code and acknowledge the work of others. See Cornell's full set of academic integrity rules.

One-on-one project advising will take place on certain dates. Please sign up to secure a spot. (NetID required)

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, (1996) An introduction to genetic algorithms, MIT Press  [link accessible only from within Cornell]
  2. John Koza et al, (2003) Genetic Programming IV - Routine Human-Competitive Machine Intelligence, Morgan Kaufmann
  3. Various old and recent papers.
Revised: October 27, 2008