Close

Turning Chaos Into Code

A project log for IQ Zero: Evolving Unprogrammed Robots

Clueless, broken robots thrive on Genetic Algorithms and Procedural Generation

Die, Master Monkey!Die, Master Monkey! 02/27/2016 at 21:140 Comments

Flattening Evolution

Yay, finally a diagram! Opening it in a new window might make the following discussion easier. I'm going to start with the left-side, a simplified workflow of Zero's version of evolution.


Firstly, let me disclaim that the Evolutionary model used in this project is simplistic in the extreme. That's mostly by design: It's on an ATTiny85, and that certainly demands we make the most of limited resources. More importantly, this is not a simulation of biological Evolution for research purposes but rather an emulation of only those mechanisms of Evolution which I deem conducive to emergent, productive behavior in a hardware control program (i.e. robot).

In the diagram, think of the shapes as representing different forms Zero's program might take: Say, a rounded surface represents a sequence of code that increments one of its registers, and the blue-ness of a shape represents its likelyhood of that register being used as an analog output. Other colors and shapes represent other facets - and we'll get to where those come from in a bit.

Imagine also that the number of shapes represent the complexity of the program. For instance, the pseudocode for one of the Generation 0 might be:

Read From InPin to InReg
Increment OutReg
Repeat

That's a very simple (and probably not very productive) program. If we checked its sibling we'd find something slightly different (we'll get to mutation, hold on). Something like:

Read From OutPin to InReg
Increment OutReg
Repeat

There's only one tiny difference (in bold), but there can also be several - or none. But siblings of one generation will tend to be very similar because they're all derived from the same (parent) DNA.

Nature's a Playa

I say siblings tend to be similar because mutations can have consequences to an organism that are benign, subtle or profound - depending on where the mutation occurs in the DNA and how that gene is expressed. Sheesh, is this helping explain anything? Okay, let's take another hypothetical Generaion 0 sibling:

Read From OutPin to InReg
Increment OutReg
Increment OutReg

Okay, this one too is "slightly different" - again only one line was mutated. It's harmless that "OutReg" is incremented again, as the program does nothing with it anyways. However, the replacement of "Repeat" (with anything else) will prove disastrous and this sibling will have the shortest robotic lifetime ever - a single execution.

So while the diagram "fast forwards" through generations, but that doesn't mean only "time" can introduce big changes to an genetic line. Major changes to any part can happen suddenly through several mechanisms, just of one of which is illustrated above.

In our particular implementation, the "seed" value provided to the PRNG is a crucial part of the DNA, but it is also subject to mutation: Since the PRNG generates all instructions for its program, the slightest change to it drastically alters the resulting offspring.

If it seems to you that there is a high chance that mutations will result in unproductive behavior (i.e. "dead babies"), then you are paying attention and get a cookie! You are correct - and dying is not good performance. So those genes are not selected to go on to the next generation.

That sounds a lot like two steps forward, one step back. Maybe two steps back, sometimes!

It is - but Nature is also waiter. Not like "try the wine" but like - well you get it.

And while time is the limiting factor in this process, time in Evolution is not time in the way watches measure it.

{Sheesh, that's a lot for ya'all to read at once - I think I'd better pick this up in the next post, where I'll explain wth I mean time is not time that's crazy talk. Thanks for tuning in!}

Discussions