![[CS logo]](../t.png)
CMSC 25000 - Artificial Intelligence
Winter 2007
Homework #4: Due February 1, 2007
Goals
Through this assignment you will:
- Explore the use of simulated evolution to search complex spaces for optimal solutions.
- Analyze the effect of different evolution strategies and fitness measures
on genetic algorithm success
- Learn how to formulate search problems as genetic algorithms.
Background:
Genetic algorithms are inspired by a biological analogy
with Darwin's theory of evolution as a mechanism for local search and learning. In evolution, variation arises through random mutation and
also through crossover which mixes chromosomal material from
two parents. Individuals, or in Dawkins' view genes, are filtered
through the process of natural selection or "survival of the fittest."
Genetic algorithms map the structure of the search problem onto
evolutionary analogs. The parameters of the search space correspond to
genes and together form chromosomes. Mutation randomly changes
randomly selected feature values, and crossover combines subsets of
parameters from two existing chromosomes. Selection is elemented
through a fitness measure which biases the choice of chromosomes to
appear in the next generation. We presented three different fitness
functions - the standard method, the rank method, and the rank-space
method - which incorporate measures of quality, and possibly additionally
diversity.
Problem 1: Mastermind
Mastermind is a game in which one player constructs a sequence of
colored pegs, which are not seen directly by the other player. The other
player's goal is to reconstruct the sequence of colored pegs based on
limited feedback (number of correct colors, number of correctly
positioned pegs). Here we will use GAs to evolve a solution to
Mastermind.
In this variant of the game, the pegs will take on the colors of
the rainbow: red, orange, yellow, green, blue, indigo, violet.
Since we have all the processing power of a computer to solve
this problem, we will try to guess a longer than typical string,
20 pegs in length, "rgybvgbiyoroggviiybo".
You will find the code to implement a genetic algorithm in
ga.scm.
Running the GA involves setting up the problem and then
using genetic_algorithm to run the GA search.
This function requires:
- An initial population
- Total number of generation to run
- Probability of (non)mutation
Part A
Formulate mastermind as a GA. Specifically, specify the
mapping to genes and chromosomes. Describe a quality measure.
Part B
Define the alphabet as a list of symbols. Now you need to
define an initial random population of a specific size.
Create a procedure create-initial-population that
generates a new population of a given size.
Part C
Genetic algorithms exploit two sources of variation - crossover
and mutation. The code already contains a procedure implementing
crossover, called reproduce. Implement a new procedure
mutate which takes an individual and returns
a new mutated individual.
Part D
Genetic algorithms implement natural selection via variants of
"survival of the fittest". Develop a function fitness
to compute the quality measure you defined in Part A.
Demonstrate the execution of your GA on two different initial population
sizes created using create-initial-population as the
first parameter to your GA and fitness as the second.
How many generations does it take for the first individual solving
the mastermind puzzle to appear?
Part E
The code currently implements the "standard method" to select parents
for crossover. Implement the "rank method".
Compare the GA effectiveness using the rank method to that with the
standard method. Explain.