EEL 4818 (Lectures on Genetic Algorithms)

Fall 2006

Lecture 1, September 21, 2006

• Topics Covered:
  • 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
• Materials:
  • Introduction to Genetic Algorithms (Lecture 1 handout 1)
  • Introduction to Genetic Algorithms (Lecture 1 presentation)
  • Genetic Algorithms: Learning by Evolution (Lecture 1 handout 2)
• Deadlines:
  • GA section written evaluation: October 5th, 2006.

Lecture 2, September 26, 2006

• Topics Covered:
  • 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.

Lecture 3, September 28, 2006

• 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, October 3, 2006

• 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)
• 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".
• Deadlines:
  • GA Homework Assignment Due: October 17th, 2006

Lecture 5, October 5, 2006

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