Python Evolution – part 1


Sometime mid-December I read a blog with a brilliant little piece of genetic programming, wherein a set of pseudo-DNA is used to generate an image out of a set of, at maximum, fifty semitransparent, overlapping polygons, in an effort to “evolve” this pseudo-DNA toward looking as much as possible like the Mona Lisa.  The idea is, can something specific evolve through only a series of randomly generated mutations?

As genetic programming goes, this is a great example, however I have to take issue with the approach as being an example of “evolution” — by my understanding, at least, not that I’m a geneticist, biologist, or even a decent programmer.   The original program has a population of two, the original and the slightly-mutated “offspring”.  The offspring is compared to the target image, and if it is more like the target image than the original, then it replaces the original for the next iteration.  After almost a million iterations, as shown on his blog, the image looks significantly like the original.

More on my attempt at this same concept below the fold…

This is where the shortcoming comes in — that’s not how evolution works.  In my opinion, that’s far too much pressure being applied on the selection process, much more than any real environment would apply to an organism (except, I suppose, in extreme circumstances, and where the parent has unlimited tries to create the more-fit offspring at the risk of extinction).

In a real environment, the only analog to Alsing’s code that I could think of would be whether or not a creature’s appearance allows it to blend into its environment, and thus avoid predators.  In researching genetic programming when my interest was piqued by this project, I found a small Flash applet by scikidus, wherein “color creatures” are evolved through random mutation toward a specific background color, due to the population’s least-similar colors getting “eaten by predators”, leaving the more successful color creatures to cross-breed and repopulate.  The idea is sound, and while still a hill-climbing algorithm, it’s a better emulation of real evolution than Alsing’s example.  A larger population, with predators culling the most visible creatures, emulates a much more realistic, more “natural” scenario.  Forcing only the more-fit creature to survive, as Alsing’s experiment did, is more like “intelligent design that happens to use evolution as its mechanism” than it is true evolution.

So, being the do-it-yourself kind of geek, I decided to try my hands at crossing both examples together — making a population of polygon creatures that evolve toward looking as much like their “environment”, the target image, as possible, while not making it explicit or 100% certain that the more-fit creatures get selected.

Thus far, I have managed to duplicate Alsing’s original concept, even if my code is horribly unoptimized and ugly.  The random mutations that are possible include changing the background color, adding a randomly generated polygon, deleting a polygon, modifying a polygon by adding or removing points or changing its color, reshuffling the order in which the polygons are drawn, changing the percent likelihood that this creature will create a male as opposed to a female, and changing the creature’s current mutation drift rate (e.g., the number of mutations that happen in the next generation).  At the moment, since all I’ve implemented is a duplication of Alsing’s original concept, the gender of the offspring is not used, however it will be once I code the cross-breeding routine.

In a bit of a Murphy’s Law moment, however, my laptop’s power supply started beeping today, indicating that it took some kind of surge or something and would no longer provide power to my laptop.  I’m posting this from another computer, and I unfortunately didn’t manage to get my Python folder when I was panickedly copying everything of import from it to my portable drive while the laptop’s battery was slowly draining away.  So, sadly, I can’t post the code I have so far at the moment.  I swear this program exists — both Pickles and Jodi have seen it in action, and I even showed Abby the outcome of one of my tests.  Rest assured, I have every intention of posting it, along with complete instructions on how to set up a Python environment so you can run the program.  I also intend on making it so that you can pass it in the command line switches to make it run like Alsing’s original, like my new-and-improved version, and to generate optional, detailed debug logs if you happen to be skeptical that my code could actually be generating this stuff randomly, et cetera.

Tomorrow I should be able to either use a generic multi-laptop power supply, or at least put my laptop’s hard drive into another laptop in order to recover the files to my portable drive.  Either way, I’ll be able to post the code as it stands tomorrow.  And I’ll be back into my laptop within the week to be able to continue programming.  Though I’ll probably end up procrastinating more.

Here are some links to tide you over, if you’re actually actively interested in this project.

Wikipedia’s definition of Genetic Programming

GeneticProgramming.org

An attempt to evolve “painter programs” toward a portrait of Darwin, using many more paint tools than polygons, written in Java

Update:  I got another power supply for my laptop; luckily Staples carries HP power supplies.  The source code is here — right-click and save as.  You’ll need Pygame and Numeric, and a few other modules that should be included in Python’s default distribution, for this to work.  I used Python 2.5.2 and Pygame 1.8.1 (from repositories in Ubuntu), if it matters.  Fair warning — because I’m displaying all my output rather than just dumping to files, it makes it much slower than other implementations.  I managed to get to 400,000 iterations by leaving it running for ~10 hours on my laptop.  It expects fineartlego.jpg (which should show up to the right) to be in the same directory as the Python file.  Also, there’s a bunch of test stuff in there, just unused — if you feel like playing around with them, feel free.  Obviously this is an early release, so it’s version… let’s say… 0.5.  Enjoy!

Comments

  1. says

    What do you use to draw?  I’ve started on a Python version myself using aggdraw and PIL and get about 70 mutations per second (for a 200×200 pixel image) – I’d be curious to hear about the speed obtained using different approaches as they have an impact on exploring various algorithms or variation on a theme (like what you are apparently doing).

  2. says

    I’m using Pygame, drawing each polygon onto one surface then alpha-blitting them onto the main surface. It’s definitely a slow approach, as I’m getting maybe 40 iterations a second on my laptop. I haven’t tried yet on my much-beefier desktop.

    Speaking of which, I have the source code now — I’ll edit this post shortly to include it.

  3. says

    Hi there! I’m glad to see that you enjoyed my little flash application. I was slightly unlucky releasing it around the same time as the EvoLisa project, but no worries. I wrote all of the code from scratch, and from your post it seems that you’re having trouble on my sid eof code. I don’t know Python, but I’m willing to help out in any way I can. Feel free to e-mail me if you hit a roadblock. :)

    scikidus

  4. says

    Oops! I misremembered your app as being Java based. My apologies, I’ll fix the link.

    I remember getting to your app from a link in a Youtube video where a program is described that does much the same thing, only with the color being a shade of grey from 00 to FF. I’m guessing you built on that idea, just like I’m trying to build on the EvoLisa idea — we can only see farther than our predecessors because we stand on their shoulders, and all that. Hat tip to you, sir.

    Progress is stalled mostly due to work (again) getting in the way of the really important stuff, like blogging and coding random Python apps. By all means, grab the source and set ‘er up. Many eyes make all bugs shallow. Python is a very simple to understand and learn, and a very freeing overall, language — if you could code evolution in ActionScript, I’m sure learning Python will be a piece of cake.

Trackbacks

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>