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:
    1. A short introduction of the domain being investigated.
    2. A description of the problem or phenomenon studied.
    3. An explanation of the methods and algorithms employed.
    4. An overview of the software (not a listing of the code).
    5. An account of the results obtained.
    6. Some interesting conclusions.
    7. 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

Literature, vids, datasets, and other resources

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.