Evolving Genetic Algorithms in Lisp

Or, now with 100% more Genetic Algorithm!

I’ve been programming a lot recently (instead of blogging about programming!). I caught the genetic algorithm bug along with the rest of the internet, so I’m in the middle of writing a Lisp library to make it easier to develop genetic algorithms: Genesis [Github link].

I’ve made some progress in the past few weeks!

The first version of my program was only a genetic programming library, and barely. It produced a rule set that could be evaluated as a function, but it wasn’t anything different than hill-climbing (a phrase I learned from snobby Reddit commenters). It was inefficient, it was unwieldy, but it produced great results when it ran long enough.

I’ve added a population! An arbitrary number of critters evolve in parallel at the moment. Previously, the individual would just mutate. I also added a basic gene-sharing algorithm: random merging.

It’s faster! In my first version, I used two ‘eval’s per rule per round. Now I use 1, and I will cut it down to 2 per rule evaluation (instead of per round) soon.

It’s in a package! I finally decided to follow my own advice and namespace everything properly. The package layout still needs work, as I’ve been too busy coding to figure out the ASDF system for installing packages.

The package system in Lisp is a lot more flexible than most module systems I’ve ever used, so I’ve been reading a few other popular Lisp packages to see how they are organized before I jump off the deep end without my swimmies.

I started to add tests! Some of the functions are very fundamental in nature, so I’ve started to add solid tests for them.

I segregated the example! There are currently 2 different files: genesis.lisp and square-root-sample.lisp. square-root-sample shows the code necessary to produce a simple/stupid example: finding an algorithm to calculate square roots. As I’ve mentioned before, the results are very good:

All you need to do in order to run this example is load genesis.lisp and square-root-sample.lisp and call the following:

(square-root-sample <em>generations population-size</em>)

After it has finished (run a small number of generations to get a sense for the time it takes), you can call the following to get the best answer so far:

(funcall-best *CURRENT-POPULATION* #'sample-fitness-function 16)

Work Needed

A recent popular example of genetic programming is the production of the Mona Lisa using random polygons. My program should almost be able to handle this. I don’t allow for a “modify rule” function at the moment, only a “new rule” function. It would probably work, but convergence would be even slower than the example given.

I’m also not allowing for one of the most powerful methods of genetic algorithm development: binary serialization. Imagine: if you can represent your whole algorithm as a binary string, then crossover, reproduction, and mutation are all made trivial. I am instead using this idea for lists, which is convenient in Lisp, but I feel it lacks some of the punch.

On The Horizon

Of course, this is still in the toy phase. I still have a pretty substantial to-do list, but here are some of the high-notes:

• Finish writing tests for core functions.
• Multiple populations, including cross-breeding between populations.
• Add multithreading.
• Give the user much greater control over (genetic-algorithm) by allowing extra key arguments.
• Self-awareness: Gather statistics on which alterations produce better improvements, and make beneficial changes more likely to occur.

Popularity: 25% [?]