Admittedly, this isn't the BEST example of a domain in which to use genetic algorithms because they are most often used in situations where we don't know what the "right" answer is. In this problem we will.
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.
There are several ways to encode the value of a particular color on the computer. One of these is the RGB method. In this method each of the three color channels (Red, Green, and Blue) is stored in a single byte or 8 bits. Since a byte stores 256 different values this means that each of the color channels is represented with a value from 0 to 255 representing none of that color at 0 to "full on" at 255.
Thus, Black is (0,0,0), pure red is (255,0,0) and medium gray would be (128,128,128).
If you want to learn a little bit more about this idea you can play with the simple applet at:
Simply change the values of R, G, and B to be in the range of 0-255 and see what color comes out. Alternately, play with the color picker tools (the slider and "pointer" on the left side) to see the RGB values of a given color.
These colors are actually stored as a length 24 bit string. 8 bits (one byte) for Red, 8 bits for Green, and 8 bits for Blue. Thus, Black would be stored as 000000000000000000000000, full on red would be stored as 111111110000000000000000 and medium gray would be stored as 100000001000000010000000.
This bit string is an ideal mechanism to explore a genetic algorithm as it is a very manageable yet meaningful chromesome.
A Fitness Function
In this assignment you will be attempting to build a target bit string (a target color) using a population of bit strings (other colors) and the genetic algorithm process.
One of the key elements of any genetic algorithm is a "fitness function" This is a function which provides a score that we use to assess the "quailty" of any given chromosome in the population. Of course, quality is an assesment of how "close" you are to the "goal." In many GA sitautions, where the actual goal isn't fully understood, this is some sort of score where a high score means you are performing better than other chromsomes. BUT, in this situation we have a known, target color. In this case we want to know how close we are to that color. There is actually a formula for determining the distance between two colors
Notice that this is simply a three dimensional extension of Euclidean distance formula (related to Pythagorean's theorem).
Thus, pure red (255,0,0) and medium gray (128,128,128) are a bit larger than 221 units apart. (Check my math and let me know if you disagree).
Also note that if we are storing our chromsomes as bit strings you will need to provide code that converts a length 24 bit string into it's three integer components (converts "1111111110000000010000000" to (255, 0, 128) to make these calculations).
Ways 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.
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:
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.
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:
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|
|Second Bowler Picked||Ringo||R||R||R||R||R|
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.
For this homework you should write a program that fits the following requirements
For example, one run might look like this:
You must also produce a short "read me" file (readme.txt) which explains to me, the tester, how to use your program.
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.