Skip to content

A genetic algorithm example in JavaScript

by Connorhd on October 9th, 2010

So, after several months of neglect I have finally decided to force myself to update my blog. This is the first of what will hopefully be several posts detailed the various projects I have been working on over the past few months. This is the smallest and potentially least useful of these projects, but something I recently made (and therefore easiest for me to write about) and hopefully mildly interesting.

In the 2nd year of my computer science degree a module called “Artificial Intelligence” briefly touched on the idea of Genetic Algorithms. After discussion with a housemate as to how these could be used in a 3rd year project I decided to look into making a simple example of such an algorithm to run using JavaScript in the browser.

After a quick Google the best example I could find (that would be visual enough to be interesting to see and simple enough to write in JavaScript quickly) was to generate the string “Hello, World!”. Starting with randomly generated strings and genetically evolving them based on a fitness function of how close they were to the string I wanted. A little bit more detail on how that is achieved shortly, but first the result is shown below (click on “Hello, World!” to replay the demo) a more detailed output can be seen here.

a
a

So, what is this actually doing? Viewing the detailed output you can see all of the strings generated, how they were combined (the algorithmic equivalent of reproduction) and the mutatations after they reproduced. To start 20 random strings are generated, then the top 2 strings (measured by number of letters that are correct, and then closeness of incorrect letters) are taken. It is worth noting this is perhaps not the best way for a genetic algorithm to work, and strictly all of the strings should have a chance of “reproducing” based on their fitness score, but this works well enough for a simple example. Once the top 2 are taken, they are split at a random point 20 times and combined (shown by the red and green colouring on the detailed output), these resulting strings then have a 75% chance of one of their characters randomly changing (shown with a yellow highlight on the detailed output) and we have 20 (potentially) completely new strings. The scoring process then repeats and more strings are created until we reach the goal string.

The result is we very quickly get a string very close to what we want, which eventually mutates to become exactly what we want, with a nice visual demonstration of what is happening, and hopefully a better understanding of how genetic algorithms work.

From → Projects

  • http://elis.ws/ Eli

    I really liked this demo, but I wonder if there is any chance you would package that in a useful object so it can be reused?

  • Connorhd

    I’m not sure I can really abstract the code for this in a useful way, its fairly short so I would suggest the most useful way to use it would be to take a look at the source and see what it does.