About two years ago Greg showed me an amazing piece of work by wreck@devisland, a genetic algorithm for evolving a 2D car. The computer was using the rules of natural processes to “evolve” little cars, completely autonomously, right before my eyes! I was completely mesmerised.

Later I continued to think about it, and soon realised that I couldn’t just let it be. A computer, all on its own, creating solutions through evolution! Its like having Darwin in a box. A slightly different, very limited version of Darwinism, granted, but nevertheless an amazing concept.

Charles Darwin, image from Wikipedia

I decided to look into these things called genetic algorithms, and made an attempt to write my own. There are plenty of online tutorials, and Wikipedia is always a good place to start, but the rudimentary concept of a genetic algorithm is easy enough to explain.

Creatures are described by their DNA: In biological, “real,” evolution, creatures each have a set of DNA in their cells which encode what they are. This genetic code describes traits such as height, gender, hair color, number of fingers, etc. When an organism, such as yourselves, is created, your cells grow and develop following the blueprint embedded in your DNA.

Survival of the fittest: Once a critter is born, it needs to survive. The world is a big place, with, presumably, lots of other critters around who would love to get the longer end of the stick. Naturally, all critters must fight for resources, shelter, and dibs on shotgun, the ones which are more suited for their environment have a better chance of being the ones on top.

Being the fittest means you have more children: Those critters who excel are able to have more children than those who are weaker. The fit DNA lives on and is duplicated, whereas the weak DNA slowly dies off.

Changes happen in reproduction: However, if DNA never changed, then the fit would soon be the only ones left, and then the population would be comprised of clones. If a population of blue and red birds required hiding in blue bushes, blue would be better and the red would all die. However, if suddenly red bushes were the place to be, there would be no red birds to take advantage of it, and all of the blue birds would die. End of story. Thankfully, nature doesn’t work like that. Instead, when two critters mate and create a new set of DNA, the parent DNAs splice together, creating a new being. Also, there is a small chance that any small section in that DNA is mutated, removed, or a new sequence added in.

Mutations are random: This is a very important thing to note. Mutations are entirely random. They are not a conscious decision to make the critter better. When your parents had you, they didn’t decide to flip a gene and mutate you to have <insert trait here>. Instead, by complete and utter random chance, a gene was flipped to give you, or our theoretical critter, or any DNA string, a new gene sequence.

Species change: So a population of all 100% blue birds is extremely unlikely. Odds are, some of them will be slightly off color, giving them a better chance of hiding in a red bush. These will survive, and odds are that some of their offspring will have an even closer color to red, and slowly the population color will shift. End result: evolution!

A genetic algorithm does the same thing. A computer essentially runs through the same process, but digitises everything. DNA becomes a string of 0’s and 1’s. DNA can then be decoded to create a digitised critter in the computer (such as a 2D car). The cars are run through a fitness function to determine how fit they are (such as how long they survive on a track before letting a blue circle hit the ground). The more fit the car, the better the chance it has of passing its DNA to the next generation. During reproduction, the DNA is spliced between two parents, and mutations randomly occur. Rinse, lather, repeat, and you get evolution!

So, genetic algorithms continue to blow my mind, but are not too hard to understand. I eventually was able to write a Java program very similar to devisland’s car. You can find the code here (NOTE: there is no crossover, just one parent per individual)

Genetic algorithms have a ton of applications, ranging from satellite antennas to training neural networks. Pretty much, if it has more unknowns than you can logically work through, do it with a genetic algorithm!