CS 472/572

From CS Wiki
Jump to: navigation, search

Evolutionary Computation

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.

Total Credits: 3

Course Coordinator: Terry Soule

URL: http://marvin.cs.uidaho.edu/Teaching/CS472/index.html

Prereq: CS 210

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

Prerequisites by Topic:

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

Major Topics Covered

  • 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)

Course Outcomes

After taking CS 472/572, a student should:

  • Be able to write algorithms for:
    • Local search (e.g. simulated annealing)
    • A genetic algorithm
    • A genetic program
  • Understand:
    • Fitness functions
    • Search landscapes
    • Epistasis
    • The concept of search neighborhoods
    • Problem representations
  • Be able to take a complex problem and design an appropriate evolutionary algorithm to solve it (or recognize why an evolutionary algorithm is not an appropriate solution). Including:
    • Picking or designing an appropriate solution representation
    • Picking or designing an appropriate fitness function
    • Picking and designing an appropriate evolutionary algorithm
    • Picking or designing appropriate mutation, crossover, and selection operations