## 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.