EEL 4818 (Lectures on Genetic Algorithms)

Fall 2008

Lecture 1, November 18, 2008

• Topics Covered:
  • Evolutionary Computation
  • Historical Perspective
  • Basic Evolutionary Process
  • Simplest Evolutionary Algorithm: EV
  • Simulation of EV
• Materials:
  • Introduction to Genetic Algorithms (Lecture 1 handout 1)
• Deadlines:

Lecture 2, November 20, 2008

• Topics Covered:
  • Simulation of EV
  • Genetic Algorithms (GAs): What are they?
  • Darwinian Evolution, Mendelian Genetics, Turing's Genetic Search, and Holland's Genetic Algorithms.
  • Stochastic Search and Evolutionary Computation
  • GA components: problem representation, selection function, fitness function, and genetic operators.
  • GA pseudocode
  • GAs: How do they work?
  • GA Optimization: One Max Problem: our class becomes a random number generator for running a single GA loop by hand
  • Tournament Selection
  • One-point Crossover
  • Bit-flip Mutation
  • Analysis of One Max Problem's experimental results.
• Materials:
  • GA Homework Assignment
  • Basic GA Java Code to be used on the GA Homework: (tar.gz format) (zip format) . Code instructions: (1) Unzip/Untar-ungzip; (2) compile "javac Search.java"; (3) run "java Search onemax.params".
  • Introduction to Genetic Algorithms (Lecture 2 presentation)
  • Genetic Algorithms: Learning by Evolution (Lecture 2 handout 1)
• Deadlines:
  • GA Homework Assignment Due: December 4th, 2008
  • GA section written evaluation: Devember 4th, 2008.

Lecture 3, November 25, 2008

• Topics Covered
  • GAs: Why do they work? (stochastic search answer)
  • Universal limits of search: No Free Lunch Theorems
  • Search Spaces, Fitness Landscapes
  • Random, Needle-in-a-haystack, and one-max fitness landscapes
  • Search Algorithms and Stochastic Search
  • Why stochastic search works? Key property
  • Schemas

Lecture 4, December 2nd, 2008

• Topics Covered:
  GAs: Why do they work? (GA schema analysis answer)
  • Building Block Hypothesis
  • Schema Theorem (Holland, 1975)
  • How does GA process schemata?
  • GA implicit parallelism
  • Schema Theorem with only selection
  • Destructive and Constructive Effects of Crossover and Mutation on Schemata
  • Probabilities of Schema Surviving Crossover and Surviving Mutation
  Complete Schema Theorem (selection, crossover and mutation)

Lecture 5, December 4th, 2008

• Evaluation (mini-test) covering the four previous lectures including all material handed out in class