Evolutionary Computation
אלגוריתמים אבולוציוניים
אתר בבנייה
202-2-5651, Spring 2021 סמסטר ב
Lecturer: Prof. Moshe Sipper
Administrative Details
- Prerequisites: Automata, Systems Programming, Algorithms, PPL
- Credits: 4
- Grade:
- 18%: Midterm A
- 19%: Midterm B
- 29%: Presentation
- 34%: Project
- You must pass all above 4 course components in order to pass the course.
- Midterm:
- If you miss a midterm due to a valid reason according to the university regulations (see Section 7.2), then you will take an oral makeup exam at the lecturer's office, at a date and time decided by the lecturer.
- If you miss a midterm due to an invalid reason then the midterm's grade will count as 0.
- Presentation:
- Each student will present, on their own, a topic/paper from the research literature.
- The presentation topic/paper must be approved by the lecturer.
- You must make a selection by April 4, otherwise 10 points will be taken off the final grade.
- If you do not make a selection by April 11, your presentation grade will be zero.
- Timeslots will be assigned by the lecturer.
- Presentation length: 12-15 minutes.
- Scoring rubric: Organization (6), Knowledge (6), Text (6), Graphics (6), Elocution (4), Eye Contact (1).
- Project:
- The project must be done in pairs or threesomes.
- The topic must be approved by the lecturer.
- A report must be submitted by the end of the semester (June 18).
- The report must include the following seven sections:
- A short introduction of the domain being investigated.
- A description of the problem or phenomenon studied.
- An explanation of the methods and algorithms employed.
- An overview of the software (not a listing of the code).
- An account of the results obtained.
- Some interesting conclusions.
- Bibliographic references.
- Language: English or Hebrew.
- Length: 6-8 pages.
- Don't include the code in the report.
- Send the report by e-mail as a PDF file.
Schedule (dates might change!)
- Mar .. / lecture
Lessons (subject to dynamic changes...)
- Introduction to Evolutionary Computation
- What is an Evolutionary Algorithm?
- Genetic Algorithms
- GA Theory: Theory, Holland's Schema Theorem, Exact Schema Theorem
- Local Search Algorithms
- Working with Evolutionary Algorithms
- Introduction to Genetic Programming: What is GP? (Koza's vid), GP (Koza), GP (Eiben & Smith), GP Tutorial (Koza), GP Tutorial (Koza & Poli)
- Evolution of Emergent Cooperative Behavior
- Koza's vids
- GP Theory: Poli's Tutorial (see Field Guide, Ch. 11)
- Game Playing: Adversarial Search
- Evolving Game-Playing Strategies: Attaining Human-Competitive Game-Playing with GP, GP-Robocode, GP-RARS, GP-Rush & GP-FreeCell
- Machine learning: Python, evaluation, dataset splits, cross-validation, performance measures, bias/variance tradeoff, visualization, ROC-AUC
- Supervised learning: models, features, objectives, model training, overfitting, regularization, classification, regression, gradient descent, KNN, linear/logistic regression, decision trees, bagging, ensembling, boosting
- Unsupervised learning: clustering, k-means
- ML as part of (the) data science (pipeline)
- Darwinian Software Engineering
- Varieties of GP
- Architecture-Altering Operations
- Coevolving Sorting Networks
- Competitive Coevolution
- Coevolving Solutions to the SCS Problem
- Parameter Control
- Evolution Strategies
Sample midterm questions:
1. TSP: Use order crossover to cross the parents:
(1 2 3 4 5 6 7 8 9)
(7 8 9 1 2 3 4 5 6)
2. What does the schema theorem say about the results of a GA run over several generations?
3. What is a coevolutionary algorithm? What are its advantages? Write the pseudocode.
4. What is "ramped half-and-half"?
5. We wish to solve the N-Queens Problem with a GA. Define a fitness function and a crossover operator for this problem.
1. TSP: Use order crossover to cross the parents:
(1 2 3 4 5 6 7 8 9)
(7 8 9 1 2 3 4 5 6)
2. What does the schema theorem say about the results of a GA run over several generations?
3. What is a coevolutionary algorithm? What are its advantages? Write the pseudocode.
4. What is "ramped half-and-half"?
5. We wish to solve the N-Queens Problem with a GA. Define a fitness function and a crossover operator for this problem.