-
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!