Course Syllabus

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)

40% Term project

30% 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 existing code libraries must be approved the instructor prior to use, and usage 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, (1996) An introduction to genetic algorithms, MIT Press

 

Tentative Schedule

 
Week Lecture date Topics Assigment due on Friday
1 Mon, Sep 10 Introduction to Evolutionary Algorithms
2 Mon, Sep 17 Parametric optimization
3 Mon, Sep 24 Genetic algorithms The building Block Hypothesis Asssignment 1 due (GA) Fri, Sep 28
4 Mon, Oct 01 Genetic programming  Applications: Kinematics, Photonics
5 Mon, Oct 08 Genetic Linkage and Epistasis   Selection Mechanisms
6 Mon, Oct 15 Multiobjective optimization Diversity Maintenance Assignment 2 due (GP) Fri, Oct 19
7 Mon, Oct 22 Robot Simulation Evolutionary Hardware and Robotics
8 Mon, Oct 29 Coevolutionary dynamics Assignment 3 due (Project) Fri, Nov 02
9 Mon, Nov 05 Break
10 Mon, Nov 12 Generative and Developmental encodings Neuroevolution Assignment 3 due (Project) Fri, Nov 16
11 Mon, Nov 19 Estimation of Distribution Algorithms Artificial Life
12 Mon, Nov 26 Mock exam Particle Swarm Optimization Assignment 3 due (Project) Fri, Nov 30
13 Mon, Dec 03 Fundamentals: Population sizing, deceptive problems, and linkage Hybrid models: Learning & Evolution
14 Mon, Dec 10 Project final presentations Project final reports due Fri, Dec 14
15 Mon, Dec 10 Final exam (tentative. 1-4pm) See registrar

Course Summary:

Date Details