Project 1: Genetic Algorithms

Due Date

This assignment is due at the beginning of the lecture on Friday, March 3^rd.

Partners

You are required to work with one other person on this assignment. Please submit just one solution with both of your names on it.

Purpose

The purpose of this assignment is to (1) help you better understand genetic algorithms and (2) help you learn how to write up the results of an investigation for a conference. You are welcome to use existing GA code that is available on the web or you are welcome to write your own GA.

Fitness Functions

The Royal Road is a well known fitness function in the GA literature. It is defined as R(x) = Σ (δ_i(x) * w_i) where x is the individual being evaluated. δ_i(x) is defined to be 1 if x is an instance of schema s_i and 0 otherwise. For our study, we will assume that x consists of 64 bits.

Royal Road 1 (8 schema to consider)

• s₁ = 8 1s, followed by 56 *s, w₁ = 1.0
• s₂ = 8 *s, followed by 8 1s, followed by 48 *s, w₂ = 1.0
• s₃ = 16 *s, followed by 8 1s, followed by 40 *s, w₃ = 1.0
• s₄ = 24 *s, followed by 8 1s, followed by 32 *s, w₄ = 1.0
• s₅ = 32 *s, followed by 8 1s, followed by 24 *s, w₅ = 1.0
• s₆ = 40 *s, followed by 8 1s, followed by 16 *s, w₆ = 1.0
• s₇ = 48 *s, followed by 8 1s, followed by 8 *s, w₇ = 1.0
• s₈ = 56 *s, followed by 8 1s, w₈ = 1.0

Royal Road 2 (14 schema to consider)

• The eight schema above and the six below
• s₉ = 16 1s, followed by 48 *s, w₉ = 2.0
• s₁₀ = 16 *s, followed by 16 1s, followed by 32 *s, w₁₀ = 2.0
• s₁₁ = 32 *s, followed by 16 1s, followed by 16 *s, w₁₁ = 2.0
• s₁₂ = 48 *s, followed by 16 1s, w₁₂ = 2.0
• s₁₃ = 32 1s, followed by 32 *s, w₁₃ = 4.0
• s₁₄ = 32 *s, followed by 32 1s, w₁₄ = 4.0

Experiment 1

• Fitness function = Royal Road 1 for experiment 1A.
• Fitness function = Royal Road 2 for experiment 1B.
• Population size = 128
• Number of runs = 100
• Number of generations = 1500
• Mutation rate (per bit) = 0.005
• Use fitness proportionate selection
• Crossover rate = 0.7 (use single point crossover)
• Copy the 10 fittest individuals from one generation to the next

Experiment 2

• Like experiment 1, but eliminate mutation.

Experiment 3

• Like experiment 1, but eliminate crossover.

Things to Study in the Three Experiments

• The percent of the runs that produce an optimal individual
• The mean number of generations to find an optimal individual
• The standard deviation of the number of generations to find an optimal individual
• The percent of strings in each generation that are an instance of s₈, s₁₂ and s₁₄.
• How well does the schema theorem predict increases in s₈, once s₈ is found?
• One more thing that you find of interest.

Paper

Write a paper that describes the above experiments and interprets the results. Use graphs where appropriate. Assume that the reader of your paper is conducting AI research, but is not taking this class. Make sure that your paper alone is informative enough to allow this reader to reproduce your results.

What to Submit

1. One printout of any source code that you write.
2. Eight copies of the paper. Pretend that this paper is to be submitted to an upcoming IASTED conference on Computational Intelligence. Use their final paper formatting requirements.

Grading

1. 90%. The quality of your report and the quality of any code that you write.
2. 10%. The quality of the reviews of your classmates' papers. You will be given your classmates' papers on March 3 and the reviews are due on or before Friday, March 10th at the start of class. More information about this aspect of the assignment will be provided at a later date.