Koza’s Ant (A Modern Take on the Canonical Genetic Programming Problem)

Koza's Ant EvolverWe’ve all had those less-than-notable-at-the-time yet ultra-significant inflections in our world view that in later days loom large.

I had one of those “moments” in 1993, on an otherwise ordinary fall day when I’d squired my not-yet wife to an unmemorable building on the Northwestern campus, in Chicago.  Marie is a Set and Costume Designer so I have to imagine that we were there for some sort of rehearsal, or maybe a design meeting; something about Orpheus Descending at the Chicago Lyric Opera teases at my memory, although given the remove of 22 years the details have faded.

One thing I vividly remember, though, is reading Steven Levy’s “Artificial Life:  A Report from the Frontier Where Computers Meet Biology;” a book I picked up at the campus bookstore while waiting for Marie to finish whatever she was doing.  She must have been at it for hours because I managed to gulp down something like half of the thickish volume before she emerged from the building.

To say I was mesmerized, would be a world class understatement.  That one read changed my life, although it would take years for the full effect to take hold.  Even so, it affected me profoundly from the start.  Beforehand, I’d toyed around with the Genetic Algorithm (GA), and naively imagined that I knew what AI was all about, although as I learned on that day that I quite simply had no idea.  Whether it was the majesty of the ephemeral creatures in Larry Yaeger’s PolyWorld, or the inspiring lives and insights of such AI luminaries as John Holland, Chris LangtonDanny Hillis, John von Neumann and Hans Morevec—not to mention the incomparable John Koza—I was more than a little stunned.

If my life were a fairy tale I would have gone on to join my new-found heroes in their quest to roll back the latest AI Winter, but life being what it is, I took a bit of a detour.

In 2004, though, I had another one of those “moments,” and this one set me firmly back on the path.  Brian Connolly wrote an article for MSDN (“GENETIC PROGRAMMING – Survival of the Fittest: Natural Selection with Windows Forms“) that brought the whole thing together for me.  My previous dalliances with AI had all revolved around GA, the closely-related precursor to Genetic Programming (GP), but as I soon learned, GP was an infinitely more powerful tool; at least in my non-mathematician hands.

The article presented “…a simple GP problem from the seminal textbook on the subject: John Koza’s Genetic Programming: On the Programming of Computers by Means of Natural Selection (MIT Press, 1992).”  Importantly, it came with working source code; a most-welcome rarity.

Within weeks I adapted the code to address all sorts of problems, but most importantly, trade analytics.  Given the proprietary nature of such things, you’ll excuse me if I don’t detail my findings, but needless to say they were revelatory.  As Archimedes said, “Give me a place to stand and with a lever and I will move the whole world.”  Well, in GP, I found my lever.

One small detail was irksome, though.  The entire thing relied upon CodeDom—Microsoft’s less than salutary code generation option.  Unfortunately, CodeDom was more than a little clunky, but even worse, it didn’t compile into memory.  This led to all sorts of practical problems especially as I tried to scale out my efforts, and especially as I began to deploy GP into the Azure cloud.  Not a deal-breaker, but as I said: irksome!

This year, though, Microsoft gave us much better kit: the .NET Compiler Platform (aka Roslyn).  With Roslyn, all of the good adjectives apply: faster, easier, better, etc.

Needless to say, I started using Roslyn just as soon as I could.  Again, I can’t share most of my results, but as a sort of tribute to John Koza and Brian Connolly I decided that it was incumbent upon me to give something back.  To that end, I rewrote Brian’s “Koza’s Artificial Ant with CodeCom and Reflection” program.  It’d be fair to say that my own work shares very little source with Brian’s.  Even so, the inspiration (via John Koza, of course!) is entirely his, for which I will be eternally thankful.

You can download Koza’s Ant Evolver from GitHub.  If you’re so-inclined, I’d love to hear what you think.

Oh, one other thing.  I packaged the code in such a way that it should be easy to derive your own GP solutions based upon the KozasAnt.Engine (and related assemblies).  The main thing you need to do is to create your own problem-oriented Settings, Genome and Report classes.  A set of convenient base-classes abstract away all of the nasty bits which should make it super simple for you to dive in.  Enjoy…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s