This week's lab is a continuation of last week's. (You probably want to save a copy of the work that you did for that lab before you start modifying it.) The programming will be rather complicated. Depending on how things go, the lab might or might not be due next Tuesday. We can discuss this in class after the lab.
Last week, you generated random expressions and tested them to see how closely they would reproduce a set of sample data. Essentially, you were doing a random search through the space of all possible expressions, and keeping track of the best one that you happened to find. For many problems, there is a better way to search for a solution in a very large space of possible solutions. The genetic algorithm imitates some ideas from biological evolution to search more effectively than a purely random search. In outline, the genetic algorithm works like this (adapted from the Wikipedia article):
Mutation refers to making some random change to one individual. Crossover means combining parts (or traits) of two individuals to produce a new individual. The genetic algorithm does not work well for all problems, but for some, it can give much better results than random search.
Genetic programming is a variant of the genetic algorithm in which the individuals that are being evolved are computer programs, and their fitness is determined by how well they perform some specified task. Genetic programming often works with the LISP programming language, which has a particularly simple syntax. LISP programs can be represented as a certain kind of tree, and almost any such tree is a syntactically legal program. There are fairly easy ways to do mutation and crossover on trees. For mutation, just take a random node in the tree and make some random change to it. To do crossover between individuals A and B, pick random branches in A and B, and swap the selected branch in A with a the selected branch in B.
Although we aren't working with LISP programs, our expressions can be thought of as a simple kind of program, and we can try to apply genetic programming to them. This is an experimental lab. I can't predict what results you will get, and your results will depend very much on the details of your implementation. There are many ways to "tune" a genetic algorithm, and many decisions to be made. We will just have to see what happens.
Here are some ideas. You will find that you need to be able to sort an array of expressions according to their fitness values. (The fitness here is the RMSError.) In order to do this, it's useful to store the computed fitness value along with the expression. For this, you can use a class:
static class Individual {
ExpNode exp;
double fitness;
}
The population is than an array of Individual, and you can use the following methods to sort the array into order of increasing fitness by calling quickSort(population, 0 , population.length-1). (This assumes that none of the individuals have fitness that is infinite or NaN.)
static void quickSort(Individual[] array, int lo, int hi) {
int mid = quickSortStep(array, lo, hi);
if (mid - 1 > lo)
quickSort(array, lo, mid - 1);
if (mid + 1 < hi)
quickSort(array, mid + 1, hi);
}
static int quickSortStep(Individual[] array, int lo, int hi) {
Individual temp = array[lo];
while (true) {
while (hi > lo && array[hi].fitness > temp.fitness)
hi--;
if (hi == lo)
break;
array[lo] = array[hi];
lo++;
while (hi > lo && array[lo].fitness < temp.fitness)
lo++;
if (hi == lo)
break;
array[hi] = array[lo];
hi--;
}
array[lo] = temp;
return lo;
}
Here is an outline of one way to implement the algorithm, using a population size of 1000. (The population size would be a constant in your program.) Make an array that is big enough to hold two or three times as many individuals as the population size (because you will be discarding some after breeding). Fill the first 1000 spaces in the array with randomly created expressions, and compute their fitnesses, making sure that the fitness is an actual number (that is does not satisfy Double.isNaN(fitness) || Double.isInfinite(fitness)).
You will then go into the basic evolutionary loop: Breed the individuals in locations 0 through 999 of the array to fill the rest of the array. To do this, choose two random individuals for that range. Do a crossover between those two individuals. Then possibly apply mutation to the new individuals. (Too much mutation can be bad. You can experiment with the mutation probability.) Compute each new individual's fitness and place it into the array, but only if its fitness is an actual number. (You might also find it necessary to throw away individuals that have gotten too complex, to avoid having really huge expressions. To implement this, you can add a height() function to ExpNodes to compute the height of the expression.) Once you've filled the array, you can sort the array by fitness, so the fittest individuals are in the first part of the array. The next time through the loop, you will only use the first 1000 individuals for reproduction, and you will replace the other individuals in the array, which are less fit.
The hardest part is probably implementing mutation and crossover. There are several ways to implement this. For example... For mutation, you can select a random node in the expression and modify it. You can do this recursively: For constant nodes, you can change the constant; for operator nodes, you can change the operator or you can mutate one of the operands (or possibly even replace one of the operands with an entirely new random expression); and for variable nodes, you really can't do anything to mutate them. For crossover of two expressions, you could randomly select an operator node from each expression, and swap one of the operands of one node with one of the operands of the other node. If an expression has no operator nodes, you can't really do crossover with it.)
I wrote the following functions to test my mutate and crossover functions:
static void testMutate() {
int changed = 0;
int unchanged = 0;
for (int i = 0; i < 100; i++) {
ExpNode e = randomExpression(6);
ExpNode f = copy(e);
System.out.println(e);
mutate(f);
System.out.println(f);
System.out.println(f.equals(e) ? "equal" : "changed");
System.out.println();
if (f.equals(e))
unchanged++;
else
changed++;
}
System.out.println(changed + " changed; " + unchanged + " unchanged");
}
static void testCrossover() {
int changed1 = 0, changed2 = 0;
for (int i = 0; i < 100; i++) {
ExpNode e1 = randomExpression(6);
ExpNode e2 = randomExpression(6);
ExpNode f1 = copy(e1);
ExpNode f2 = copy(e2);
cross(e1,e2);
System.out.println(f1);
System.out.println(f2);
System.out.println(e1);
System.out.println(e2);
System.out.println();
if (!e1.equals(f1))
changed1++;
if (!e2.equals(f2))
changed2++;
}
System.out.println("crossover changed first expreesion " + changed1 + " times");
System.out.println("crossover changed second expreesion " + changed2 + " times");
}
For the ".equals" tests to work properly, you have to define the equals method in all your classes. Like toString, the equals method is defined in class Object, where it just defined to do the same comparison as "==". Classes often need to redefine the equals method. For example, here is the equals method from my BinOpNode class:
public boolean equals(Object o) {
return (o instanceof BinOpNode)
&& ((BinOpNode)o).op == op
&& ((BinOpNode)o).left.equals(left)
&& ((BinOpNode)o).right.equals(right);
}
In the previous lab, the expression that was used to make the test data was fairly easy for a random process to guess, especially if you made your random expressions with integers. To make it harder, you could change "double y = 2.5*x*x*x - x*x/3 + 3*x;" to "double y = 2.5345*x*x*x - x*x/3.112009 + 3.237*x;" or something even messier.