-
Notifications
You must be signed in to change notification settings - Fork 0
Genetic Algorithm Tutorial
Although none of the others have been published, this is my 3rd time writing this tutorial. I hope this time I've simplified it as much as possible to present to a general readership (fluent in Java).
This is based on a final project that I did in Computer Science 136 at Williams College in Spring 2013. The main project was to implement a game called Darwin in which virtual creatures, running on a special machine code would battle each other. An example creature would be the Flytrap, which has the following instructions:
ifenemy 4
left
go 1
infect
go 1
.
This reads: "Check if the creature in front of you is an enemy, if so, go to instruction 4, which is infect, and then jump (go) to instruction 1, which starts the loop over. If there is no enemy, rotate left, and jump to instruction 1."
This tutorial is designed to avoid the details of the Darwin Machine Code, we're most concerned about getting a genetic algorithm working, but it is pretty cool. If you want to look at some more examples, they are in the Creatures/ directory. A formidable opponent is Frankenstein.txt built by Alex Wheelock and Donnie (?last name?). It will beat most creatures pretty handily (although there is a simple < 20 line solution that beats it). If you are wondering why it is so huge, it was made by a computerrr.
To run any of these examples, cd into Starter and run something like:
java -cp ./structure5.jar; Darwin Flytrap.txt Rover.txt Frankenstein.txt
(structure5 contains some utility classes that Darwin needs). The command line arguments are the file names of the creatures you want to duke it out. You'll then be prompted by a couple questions: the number of creatures of each race present on the field, the number of "rounds" which is really the number of steps executed before a winner is chosen, and whether you want graphics to be shown. The game is much faster without graphics of course.
When I first started writing this genetic algorithm I was really pumped about the idea. It was for a competition at the end of the year to see who could build the best creature and the spawn of my genetic algorithm was going to be the secret to my success! But at first I tried a linear approach, basically instructions that say "Do this, then this, then this, then this, then..." mutating each "this" (to "left", "right" or "hop"). It sucked! There is no one sequence of moves that is going to work in every situation and my Creatures kept evolving to Flytrap, which is apparently some kind of maximum (that fact is actually pretty cool).
However the TA, Alex Wheelock, caught on to the GA fervor, a made his own solution, where the instructions have a tree structure that branches on Darwin's branching instructions ifenemy, ifsame, ifwall, infect, and the default path. It was really cool and it worked really well so now I'm trying to do the same thing. So.. that data structure we will be "mutating" is going to be a Tree! Tree.java in the Starter directory is your data structure. Each of our Tree's will have a value of "h", "l", or "r" (for the corresponding movement instruction) and 5 children tree's, one for each branch. They'll be constructed with a specific fixed depth, and mutations will be changes in the values of the nodes. And that's it!
Now to start actually doing some coding, I know you can't wait. Our code is going to be in Evolution.java where there should be some methods already completed for you. decodeTree will compile a tree into Darwin Machine code. It was really fun to build, but going through the whole process of making it is complicated, technical, and in the end irrelevant to the thing we're trying to do which is evolve. decodeString takes one of "h", "l", or "r" and outputs the corresponding instruction, also not totally relevant. randomTree creates a random tree of a specified depth, it's just a nice utility for initialization. Finally calculateFitness runs Darwin games and returns the fitness as the number of wins. I'll admit that it takes away some of the fun to not specify the fitness function, so I'm going to think about updating the tutorial with more of the Darwin Interface so you can get creatures that evolve the way you want... but for now the fitness is the number of wins.
We only really need to initialize a population to start with, which can be some Tree arrays. There are a lot of ambiguous decisions to be made when making a building a genetic algorithm, two of them are: the size of the population (I chose 100 Trees in my implementation) and how deep each Tree is going to be (I chose 4). There's a whole lot of parameters to choose. We should make... a genetic algorithm... to optimize genetic algorithms... Anyways my constructor for Evolutions looks like this:
// parameters you eventually have to choose
private int matchesPerIndividual = 20;
private int generations = 100;
private double mutationRate = .01;
private Random randy;
private Tree[] population;
private String[] letters = {"h", "l", "r"};
private String name = "Genie";
private String color = "blue";
private Vector<Species> enemies;
public Evolution(Vector<Species> enemies) {
population = new Tree[100];
randy = new Random();
this.enemies = enemies;
}
and in my main I read in some enemies from the command line and run the algorithm:
public static void main(String args[]) {
Vector<Species> enemies = new Vector<Species>();
for(String s : args) {
//Species just takes a file name as a parameter and makes creatures from it
enemies.add(new Species(s));
}
Evolution evo = new Evolution(enemies);
evo.run();
}
I actually initialize the random trees in a method called run:
public void run() {
// intialize population
System.out.println("Initializing population...");
for(int i=0; i<100; i++) {
population[i] = randomTree(4);
}
// rest of code goes here
We now need keep the rest of the code in a loop, calculating the fitness of each individual and choosing who survives to reproduce. We'll stop when we've decided the fitness of our individuals is "good enough", another vague parameter to set when doing genetic algorithms, I chose to stop when any creature wins 100% of its matches against a chosen enemy. When calculating the fitness for an individual in the population, I simply use the calculateFitness function that comes in the starter code. For the next generation, I choose to keep the top 50 from each population. Each creature will look at his brother and know that only one will survive. That's a high percentage of the original to make sure we don't lose good genes to random noise in the game outcomes. The next 50 are random mutations created by the function mutate, which recursively goes through the Trees mutating values at a probability mutationRate. I put my mutationRate very low, because slow progress is typically better than fast. In my implementation, I also store and print out a lot of debugging information, to show the progress.
Here's mutate:
public void mutate(Tree t) {
if(randy.nextDouble() < mutationRate) {
t.setValue(letters[randy.nextInt(3)]);
}
for(Tree child : t.getChildren()) {
mutate(child);
}
}
The full run method ends up looking something like this:
public void run() {
// intialize population
System.out.println("Initializing population...");
for(int i=0; i<100; i++) {
population[i] = randomTree(4);
}
Tree bestTree = new Tree("l");
double best_ever = 0;
System.out.println("Running algorithm...");
int generation = 1;
while(best_ever < matchesPerIndividual) {
// calculate fitness for each
double[] fitnesses = new double[100];
for(int i=0; i<100; i++) {
System.out.print(i);
fitnesses[i] = calculateFitness(population[i]);
if(i <= 99) {
if(i <= 9) {
System.out.print("\b");
} else {
System.out.print("\b\b");
}
} else {
System.out.print("\b\b\b");
}
}
// average the fitnesses and print them out for debugging
double sum = 0;
double best = 0;
for(int k=0; k<100; k++) {
sum += fitnesses[k];
if( fitnesses[k] > best_ever ) {
best_ever = fitnesses[k];
bestTree = population[k];
}
if (fitnesses[k] > best) best = fitnesses[k];
}
sum = sum/100;
System.out.println("[GENERATION " + generation + "] Average fitness: " + sum + ", Best Fitness: " + best);
generation++;
// save the top 50 for the next generation
// lazy implementation...
Tree[] nextGen = new Tree[100];
int index = 0;
int rank;
for(int i=0; i<100; i++) {
rank = 0;
// for each member of the population
for(int j=0; j<100; j++) {
// count the number of members that member i is greater than
if(fitnesses[i] >= fitnesses[j]) {
rank++;
}
}
if(rank > 50) {
nextGen[index] = population[i];
index++;
}
if(index >= 50) break;
}
// mutate for the 50 "offspring" and run the algorithm again
for(int i=50; i < 100; i++) {
Tree childTree = nextGen[i-50].copy();
mutate(childTree);
nextGen[i] = childTree;
}
population = nextGen;
}
try {
Species bestSpec = new Species(name, color, decodeTree(bestTree));
String machineCode = bestSpec.programToString();
String filename = ".\\Creatures\\" + name + generation + ".txt";
File file = new File(filename);
FileWriter fw = new FileWriter(file.getAbsoluteFile());
BufferedWriter bw = new BufferedWriter(fw);
bw.write(machineCode);
bw.close();
System.out.println("Wrote to " +".\\Creatures\\" + name + generation + ".txt");
} catch (IOException e) {
e.printStackTrace();
}
}
And there you have it, this should run and come up with some cool solutions. It can take a while, but seeing the cool behavior that results without any input from you can be extremely rewarding. Take a look at a lattice-like behavior in AntiRover.txt or the "chasing" mechanic in "AntiFrankenstein.txt". I would never have been able to think of those, but they came out of the genetic algorithm via selection.
To run the algorithm against say, Rover.txt, type the following input into the console:
javac -cp ./structure5.jar; *.java
java -cp ./structure5.jar; Evolution Rover.txt