CS 472 Evolutionary Computation

Total Credits: 3 cr

Course Coordinator: Terry Soule

URL: http://www2.cs.uidaho.edu/~tsoule/cs472/cs472.html

Current Catalog Description: Solving computation problems by "growing" solutions; simulates natural evolution using analogies of mutation, crossover, and other genetic transformations on representations of potential solutions; standard EC techniques such as genetic algorithms and evolutionary programming, mathematical explanation of why they work, and a survey of some applications; the focus is on solving real-world problems using projects.

Textbook: Eiben and Smith, Introduction to Evolutionary Computing, Springer or equivalent text.

References: None.

Course Goals: Students who finish the course should have an understanding of search and optimization problems in general, an understanding of the common types of evolutionary computation (genetic algorithms, genetic programming, etc.) and how they differ, and some experience in applying these techniques to practical problems. Students who complete the course will also have experience in writing evolutionary algorithms and some exposure to current research topics in the field.

Prerequisites by Topic: CS 210 Programming Languages and the following specific topics:

• Basic graph theory
• Object-oriented programming skills
• Recursion
• Arrays and trees
• Search algorithms
• Parse trees and expression trees

Major Topics Covered in the Course:

• Search and optimization (5 hours) (IS2)
• Genetic algorithms (5 hours)
• Evolutionary strategies (3 hours)
• Genetic programming and evaluation trees (3 hours) (PL8)
• Algorithms optimization – parameter choice (3 hours)
• Evolutionary algorithm theory (3 hours)
• Performance measures (3 hours)
• Particle swarm optimization and hybrids algorithms (3 hours)
• Constraint problems (3 hours) (IS2)
• Agent teams (2 hours) (IS6)
• Co-evolution (3 hours)

Laboratory projects (specify number of weeks on each): There are five programming projects each of which extends over several weeks.

• Write hill climbing and simulated annealing programs to solve the maximum clique problem. (2 weeks)
• Write a genetic algorithm to solve the maximum clique problem and compare the results to the hill climbing and simulated annealing programs. (3 weeks)
• Modify a genetic program to solve one of several standard test problems. (3 weeks)
• Write a particle swarm optimizer program to solve a number of standard optimization problems. (2 weeks)
• Write an experimental research paper addressing a topic raised during the course. This typically includes modifying one of the previous programs or writing a new program and collecting and analyzing data, in addition to writing the paper. (4 weeks)

Estimated Curriculum Category Content:

Area	Core	Advanced	Area	Core	Advanced
Algorithms		1 cr.	Data Structures		1 cr.
Software Design			Prog. Languages
Computer Arch			Other		1 cr.

Oral and Written Communications: Every student is required to submit at least three written reports (not including exams, tests, quizzes, or commented programs) of typically eight pages.  No oral presentations are required.

Social and Ethical Issues: None.

Theoretical Content:

• Algorithm Complexity (1 hours)
• Schema theorem (2 hours)

Problem Analysis:

• Algorithm performance analysis, particularly time to solution versus quality of solution with approximation algorithms (3 hours)

Solution Design:

• Designing representations suitable for representing potential solutions (3 hours)
• Designing experiments to test relative algorithm performance (2 hours)

Course Outcomes: The following list documents the course outcomes and crossreferences them to the BSCS program outcomes. The letter at the beginning of each reference identifies the program outcome supported. The numbers sequentially identify the course outcome for this course. After completing CS 472 a student should be able to: