Okay this is going to be a lengthy article with a lot of graphics, so I am going to use an excerpt today. Basically it's a summary of the first run of my Genetic Factoring sim, and how it demonstrates that evolution can lead to extinction. It also includes a summary of the most efficient (and robust) genome to be generated by random mutation and natural selection, and how it compares to the original genome. Let's begin with a graph...   more »

I'm sure you remember the Weelanders... artificial life forms which lived on a grid and helped demonstrate that evolution through random mutation causes natural selection to kick in something fierce.  At the time I originally ran tests with the Weelanders, I hypothesized that the Weelander concept could be adapted to do more than just demonstrate natural selection.

And, a few months ago, I did just that.  I built a new version of the Genome application called "GeneticFactoring", and stripped out a ton of Weelander support code.  I wanted to make Weelanders that factored numbers and then reproduced based on how successful they were at factoring.  As a result they didn't need to search for and consume food, they didn't need sexual reproduction, they didn't need the ability to move, heck they didn't need chromosomes in pairs, as a result, all of the "critter emulation" code was unnecessary, resulting in a simpler Weelander support system.

What they did need was the ability to compute square roots, find primes, and factor numbers... this was the new code that needed to be added, and it was all going to be written in the native Weelander instruction set.  It took me awhile to code the genome "Facto-f", but eventually I had it working.  Then I modified the container and world code to invoke the Weelander factoring code in the following manner:

1. Populate: at the beginning of time, populate the grid so that it is completely full of the starting Weelander genome "f".
2. Setup: build a list of 50 numbers to factor, then factor each number using internal container code and store the results.
3. Execute:
   1. for each critter on the grid
   2. run through the 50 numbers
   3. call the Weelander's Execute method and pass it the number to factor.
   4. The Weelander factors the number and returns the results.
   5. If the Weelander goes into an infinite loop without returning results, terminate it.
   6. Otherwise, compare the Weelander's results to the original results.
   7. If they do not match, terminate the Weelander for inaccuracy.
   8. If they do match, note how many execution steps the Weelander needed to compute the result, and proceed to the next number.
   9. Once all the numbers have been factored, compute an efficiency value for this critter (total number of steps divided by total number of tests).
   10. Proceed to the next critter and repeat.
4. Cull: examine all the living critters on the grid and gather the top ten percent based on efficiency, and terminate all the others.
5. Repopulate: for the most efficient critters, allow each one to reproduce asexually (possibly with mutation).  If after processing them all, the grid is not filled, go back and run through them again.  Keep doing this until the grid is filled.
6. Loop: Jump to step 3.

An immediate problem which cropped up was that Weelanders would mutate in ways that made them faster at factoring this specific set of test numbers.  So if by random chance, none of the test numbers was a multiple of say, 7, the Weelanders might make themselves faster by throwing away the "divide by 7" test somehow.  Which is great until you hand them a multiple of 7 at which point they die from inaccuracy.

I solved this problem somewhat by changing step 6 to jump to step 2 instead of 3.  Thus on each "tick" of the world, a new set of test numbers would be created and then all the Weelanders would be tested against that set.  Makes sense really, and automatically weeds out Weelanders that made the grade last tick by "cheating".  I improved this further by making the first 10 test numbers a fixed set that didn't change and which exercised a lot of the conditions I wanted to make sure were covered.  The remaining 40 were random.

But another problem appeared, one that completely flummoxed me because the system appeared to drift toward less efficient creatures over time, instead of more efficient ones.  How could that be possible?  Natural selection should continue to hold true, and the creatures should be *more* efficient over time, not less efficient.

But nothing prepared me for the worst problem at all... hardware.  My computer, wonderful though it is, is experiencing a hardware problem.  The cooling system is no longer operating, or not operating well.  As a result, any operation that pins the CPU usage at 100% for a period longer than 10 minutes or so will cause an audible heat warning alarm to begin issuing.  It's an alternating two-tone klaxon which doesn't come from the computer speakers, it comes from somewhere inside the computer case.  And it is, needless to say, very alarming.  I like my CPU.  I don't want to cook it.

Needless to say factoring numbers is CPU/FPU intensive.  And I've got 230 Weelanders factoring 50 numbers each, over and over, ad infinitum.  After 10 minutes or so of runtime, the CPU gets too hot, and I have to shut the simulation down or risk damaging my computer.  This problem cropped up immediately after building the new GeneticFactoring code and caused me to terminate the experiment permanently months ago.

Then last night I broke the code out again and tried to figure out a way to get it to execute without pan-searing my CPU.  Eventually I came up with a rather simple solution.  The simulation executes for 20 ticks, pinning the CPU at 100% for about 60-90 seconds.  Then the simulation pauses, basically issuing a call to Thread.sleep for sixty seconds of downtime.  This drops CPU consumption to 0% or close to 0% for a minute, giving the CPU a chance to cool.  Resulting in a usage pattern like this:

I'm happy to say that having made this change I've been running the simulation for 3 hours with no overheat alarms.  At this point I feel safe walking away from the computer and letting it process the simulation.

Regarding the other problem, the problem of the population drifting toward inefficiency, I also managed to solve that.  I observed the changes to the Weelander genome over time.  After awhile I began to observe what I thought was the culprit.  Creatures weren't being selected based on their efficiency at factoring *all* numbers, just the 50 test numbers they had to factor.

So let's say a mutant does something weird like tests factors out of order... instead of 2, 3, 5, 7, 11 it goes 5, 3, 2, 7, 11.  It's still accurate, but it tests a different factor first.  If more of the numbers in the test set are multiples of 5 than 3, and more are multiples of 3 than 2, then this critter will in the end rate more efficient than the basic Facto-f genome, which is suitable for factoring any value.  As a result, genomes which aren't really more efficient at factoring any value, get selected ahead of the f genome, and over time, this exterminates the f genome.  After which the population becomes less efficient over time as more and more test sets are produced.

That was my hypothesis anyway.  To solve the problem, I decided to artificially inject the original genome into the list of critters during the repopulate stage, thus if the population ever drifted away from efficiency, there would always be some number of the original genome to tug it back.  Basically I grab my ten percent most efficient, and then tack 10 copies of the original genome to that list before I repopulate.  This makes sense since natural selection is only concerned about the environment you are in (i.e. the 50 numbers you happened to test) as opposed to my overall goal (more efficient factoring of ANY number.)  Now the top ten percent must always compete with the baseline.  If they drift away, the baseline will win and it will get selected for repopulation instead.  The only way to stay alive is to consistently beat the baseline.

Makes sense doesn't it?  Yes, yes, I know, brilliant.

It was right about that time I noticed that the code that was selecting genomes for propagation was selecting the least efficient ones instead of the most efficient ones.  Y'know, it takes a special kind of mind to come up with a brilliant explanation like the one above and still be completely wrong.  Needless to say selecting the least efficient members of the population will uh, tend to make the population drift toward inefficiency.  It's amazing what happens to the code when you say "greater than" but you meant to say "less than".  > versus <, baby... classic coding error.

Nonetheless, although the effect I hypothesized was ultimately not to blame for the drift, I still think the effect could occur, so I decided to keep the "baseline infusion" code in place.

So the factoring Weelanders are back in action, and I'm interested to see what they will do to become more efficient at factoring.  There are a lot of simple things I can think of that would lead to slightly more efficient code, but the Weelanders are always surprising me.

What I can tell you is that given a test sample, the Facto-f genome generally requires (on average) 1500 to 2200 execution steps per number.  After running the simulation for 3 hours, the top genomes are showing efficiencies on the order of 500 to 600 execution steps per number.  Ok I'm impressed.  Especially when you consider that these Weelanders have to produce accurate results to survive.  If they fail any single factoring test, they're gone.

I'm going to let the sim run for awhile longer and then take a peek at these efficient Weelanders.  I wonder what they are doing?