Homework 6

Exploring Genetic Algorithms


Due: Wednesday, November 28, 10:00 AM


Disclaimer

It is difficult to find a domain where the chromosome and fitness function needed to solve a Genetic Algorithm problem are small enough and applicable for a "simple" weeklong homework assignment. Therefore, I am providing you with a fitness function that I do not expect you to understand - in fact, I don't want you to understand it. Instead you will simply work with this fitness function to find and trust its results.

Having said that, this homework is very manageable in size and difficulty and therefore makes a good chance for you to explore the key ideas of Genetic Algorithms easily.

 

Instructions

For this homework you should write a program that fits the following requirements

  1. Is written in python and uses the following starter file GA.py
  2. Contains two functions that you will create
    1. gaInputs()
    2. gaParameters(......)
  3. The input version should use a series of input() function calls to dynamically ask the user for, IN THIS ORDER:
    1. the number of chromosomes in the population
    2. the number of chromosomes that should undergo selection (mutation rate of 0) per generation
    3. the number of chromosomes that should undergo mutation (mutation rate of 1) per generation
    4. the number of "newblood:" chromsomes (mutation rate of 24) that should be introduced per generation
    5. the number of "crossover pairs" that should be introduced per generation (1 pair uses and produces two unique chromosomes).
      • Note that #1 should equal #2 + #3 + #4 + 2*#5
    6. the number of generations the process should run
    7. the key value to be used by the fitness function
      • This is a number given to the fitness function to allow different runs to focus on different problems
  4. Conducts the genetic search that was described by the user's inputs
  5. Prints the fitness function value of the best member of the population after each generation.
  6. Prints the value of the best chromosome found after the process is completed.

 

For example, one sample run is illustrated below.

 

Some things to note:

 

You should also produce a version called gaParameters() that allows this to be launched with out the dynamic inputs. The example below is the exact same values as used above.

NOTE: You should program gaInputs() to take advantageof gaParameters().

 

 

Details on how to generate new chromosome's from population to population

In the reading from your textbook you read about three genetic operators - methods for moving chromosomes from one generation to the next.

  1. Crossover - two DIFFERENT chromosomes produce two children through a process of "mating" A random cross point is selected and the front "half" of one of the pair is merged with the back "half" of the other one of the pair. Two pairs of examples are shown here
  2. Mutation - a chromosome is moved from generation N to generation N+1 with one or more of the elements of the chromosome are "mutated" (in our case, a bit is changed from 0 to 1 or 1 to 0). The mutation rate can be adjusted from low mutation (only 1 gene/bit is modified) to high mutation (up to every element of the bit string). We will start by only considering mutation rate of 1.
  3. Selection - a chromosome is moved from generation N to generation N+1 with no changes at all. This is actually just a special case of mutation with a mutation rate of 0.

The first two are almost always used. The third one is used in certain situations. I am also going to ask you to consider one additional operator:

  1. New Blood - This is really just an adaptation of Mutation with a mutation rate of length N.

 

Selecting a Chromosome to modify

In order to mimic nature and the concept of "survival" of the fittest" we need to come up with a technique which allows every chromosome at least a limited chance of being picked to undergo a genetic change through one of the methods explained above. But those chromosomes that are "fittest" (in our case, close to the target color) should have a much higher chance than those that aren't (those that are farther away).

For this particular assignment I would like you to use a technique known as "tournament selection" The concept is easy, although the implementation may be a bit harder.

To put this in an easy to understand context, let's consider five people who have just bowled a game of bowling. First, rank your bowlers (or, in the context of your GA, your chromosomes) based on their fitness. In this context the fitness is their score in the last round of the game.

Rank Bowler Score
1 Ringo 224
2 Paul 202
3 George 185
4 Yoko 171
5 John 155

Now, we want to select one of these bowlers, but we want to give preference for Ringo over John. The way we do this is:

  1. randomly pick a number from 1-N (in this case, 5)
  2. do it again, paying no attention to what number you picked the first time
  3. Select whichever bowler has the higher rank. If you actually picked the same bowler both times than you have your selection.

If you think about this, you have 25 possible pairs of bowlers (5x5) and among this 25 pairings each bowler is selected at least once, although Ringo is going to be selected 9 of the 25 times while John will only be selected once.

  First Bowler Picked
Ringo Paul George Yoko John
Second Bowler Picked Ringo R R R R R
Paul R P P P P
George R P G G G
Yoko R P G Y Y
John R P G Y John

 

You should use this technique for picking which chromosomes are used for selection and new blood. You should perform this techinique twice to see which two chromosomes are selected for crossover.

Submitting Your Work

Prior to the deadline, use the homework submission system (https://www.cs.uni.edu/~schafer/submit/which_course.cgi) to upload any files you have produced.  Make sure you submit all of the files needed to use your code.

In addition please submit to me a paper copy of your read me file at the start of the class on the due date.