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.
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.
Lectures and readings will cover some or all of these topics:
- Optimization background and terminology: Gradient optimization methods, sampling methods, linear programming, combinatorial optimization.
- 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.
- Genetic Algorithms: Representation, operators, and standard algorithm. The building block hypothesis and the schema theorem.
- Evolutionary strategies: Evolution in continuous variables. Transformations.
- Genetic Programming. Building blocks and architecture-altering operators. Libraries and Trees
- Selection mechanisms: Fitness proportionate, rank, tournament, Stochastic Universal Sampling and Boltzman selection methods. Niching methods. Spatial methods. Consequences of selection models.
- 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.
- 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.
- Evolutionary dynamics and game-theoretic models: Evolutionary stable states, cycles and chaos. The iterated prisoners dilemma. Evolution of cooperation.
- Evolution and learning: Plasticity and life-time learning. Lamarckian learning, How learning can guide evolution. The Baldwin effect.
- Symbiosis as a source of evolutionary innovation. Macro-mutations, Major transitions in evolution, symbiosis and symbiogenesis. How symbiosis can guide evolution.
- Evolutionary algorithms as models: Modeling sexual selection, modeling ecosystems, artificial life.
- 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.
- Modularity and regularity in evolution. The scaling problem and the curse of dimensionality. Evolvability. Module acquisition. Developmental models. Compositional and hierarchical approaches.
- Swarm intelligence, particle swarm optimization
- 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
- Melanie Mitchell, (1996) An introduction to genetic algorithms, MIT Press
|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|
The syllabus page shows a table-oriented view of the course schedule, and the basics of course grading. You can add any other comments, notes, or thoughts you have about the course structure, course policies or anything else.
To add some comments, click the "Edit" link at the top.