Mondays 1:10pm - 3:40pm, 415 Schapiro Cepser
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)
- 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.
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 An introduction to genetic algorithms MIT Press
|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|
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.