Genetic brainfuck programming

There are so many things about our universe that are very non-random, such as the physical laws, and more specifically the spherical shapes of planets/stars, the flatness of their surfaces, the flow of energy from stars to planets, etc.

An analogy could be that life forms randomly evolving with these constraints are like water particles randomly floating through a river. There are plenty of variations in where the particles can go, but they flow in a general direction.

corvus -h 500 | corvus -h 300| corvus -h 200

So on and so forth as you get closer to [,.]

The dead code part was a organic artifact, and I actually don't think that I want to change that part. It sorta makes you wonder about how much dead code is in real DNA.

First, for anyone unaware of the difference, in Genetic Algorithms (GA) you have fixed-length strings of instructions. Genetic Programming (GP) is a superset in which you have ASTs, which can get arbitrarily large (which can be a problem if you're not careful). I find GP much more interesting than GA, but the practical issues with AST bloat are why you see a lot more GA examples.

Anyway, not wanting to run into overly large ASTs myself, I went ahead and prematurely optimised my GP implementation by having it always collapse functions into simpler forms where possible, e.g. (+ (+ 1 2) 3) becomes (+ 6).

It turns out that this causes huge problems, because all that "junk" code is actually useful during evolution. Each generation inherits parts of its parents (called "crossover"), but if you cut down the information available to inherit as-per the above optimisation, you get much less variety between the generations and become more reliant on random mutations. As a result, it's like falling back on bogosort to find your solution.

Once you get down into final generations you can start running optimisations like this and removing dead code, but if you do it too soon, you won't reach a solution convergence quickly, if at all.

Interestingly, this principle seems to apply to DNA too, but DNA doesn't come with an optimiser. Hence most DNA is "junk" but the junk is actually more important than it seems.

It also turns out that genetically optimising (as opposed to hand-coding the optimisation rules, like I did) is non-trivial too. You can either adjust your main cost function to account for code size/speed alongside the problem you're trying to solve, or you can do a second pass that aims to optimise the code after you've already found an acceptable solution. Either way, there's a certain amount of black magic involved to decide how many iterations to run, or what constitutes a "good enough" or "fast enough" or "small enough" solution so you can decide when to stop.

Code size is also irrelevant in GA because the code is always the same size, but different instructions might have different costs, with NOPs having the lowest cost. If you allow goto or recursion in your VM then you have to impose a runtime constraint to avoid infinite loops, and can also assign a cost per instruction executed or per microsecond of runtime.