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…

Efficiency Over Time

This graph shows the average efficiency of the top performing genome over time.  As you can see, the sim starts with the most efficient individual scoring about 2200 steps per test, this is Facto-f, the baseline genome.  Through random mutation and natural selection the efficiency rapidly improves to a point where the average is around 600.  Then over a long period of time, there are three notable small steps downward until the efficiency is averaging around 500.

And then, disaster!  The steps per test spikes back up over 2000… what happened?  The short answer is evolution, and a little too much of it.  At tick #3036 (note, numbers along the bottom of the above graph are not tick numbers, sorry, 3036 is a few ticks before the big spike), the strongest genome is called “h33″.  There are over 400 genomes in the genome bank at this time so the world has been busy.  h33 has a mutant child called H40, and H40 is so well adapted to his environment, he's even faster than h33. As a result h33 dies out over a few generations, replaced by H40.  But H40 is too well adapted to his environment, which is to say he's very fast given the batches of numbers he happened to be given to test, but his speed came at the cost of a computational flaw which would only occur in rare situations.  Maybe he couldn't handle square numbers, or numbers that happened to be prime, or multiples of 31, but one thing is certain — he was very good at factoring most numbers, but he couldn't factor them all.  Like a dinosaur adapted to a hot tropical environment, he ruled the grid… but then it got cold.

Any inaccurate result immediately causes the Weelander to die, so H40 persisted for a few generations before being handed the fateful batch of numbers containing the poison pill that completely wiped out his kind on tick 3061, leaving behind only the baseline Facto-f genome that I infuse into each generation to prevent a drift toward inaccuracy:

T003061 -------------------------------------------------------------------------------------------
Most efficient individual f-003061: 2005.560
Births: 220 Deaths: 230 (182 culled for inaccuracy, 48 culled for inefficiency, 0 exhausted)

Essentially, the sim was starting over at baseline, which is why you see the enourmous spike in computation time on the graph.  Then evolution again pushes the execution time down, leading to more and more efficient creatures until a similar problem occurs again resulting in another mass extinction and a spike in execution steps as the sim returned to Facto-f again.  Without the Facto-f infusions, the sim would simply have halted with all creatures having died out.  Evolution –> extinction.  How interesting!

Genome h33 — Analysis

In the entire history of my first simulation, my top 10 genomes were:

H40 509.5428571
h33 522.3523618
Y29 523.6892308
d28 536.1935
927 550.5888372
T25 566.3514286
E66 566.9955556
O23 570.307907
z21 571.4323636
w26 572.064

The number on the right is average execution steps per test value.  Obviously H40 is on top, but he was flawed in a way that his parent, h33 was not. H40 was efficient, but h33 was robust and efficient.  Sadly, H40 didn't last long enough for the genome bank to save him to disk, so I don't know exactly what his flaw was.  So let's skip H40, and look at h33, the product of many evolutionary changes, as evidenced by his ancestry graph:

Extinct h33 - 648 generations. First birth: T002408. Last death: T003055.  Lifespan: 647.              Lineage:  --> Y29 --> d28 --> 927 --> w26 --> T25 --> O23 --> z21 --> e21                        --> 820 --> F13 --> O12 --> q11 --> x9  --> Y9  --> G8  --> U7                        --> J7  --> 77  --> (lost)

The (lost) indicates that whatever the progenitor of genome 77 was, it was such a minor genome (very few births) that the genome bank threw it away to conserve memory.  Nonetheless all mutations lead back to Facto-f ultimately, which indicates that h33 contains at least 19 mutations and possibly more.

The genome for the factoring Weelanders is pretty small, just 6 chromosomes of which only 4 can mutate.  Those 4 are [Main Loop], [Compute Root], [Is Prime], and [Next Prime].  [Main Loop] actually performs the factoring, dividing the test number by a series of primes starting at 2.  [Main Loop] calls [Next Prime] to get the next prime number to test with, and [Next Prime] in turn repeatedly calls [Is Prime] as it searches for the next prime number.  [Compute Root] is used both by [Main Loop] and [Is Prime] to set an upper limit on how far to go when testing a number by computing the number's square root using the Babylonian Method.  Remember, when factoring, there's no reason to test values above the square root of the number you are factoring, any value greater than the square root which happens to be a factor, would be multiplied by a factor smaller than the square root which you already should have found earlier.  Like this: SQRT(24) = 4.9, 24 = 1 x 24, 2 x 12, 3 x 8, 4 x 6, if I keep going the next factor is 6 as in 6 x 4 = 24, but I already determined that earlier.

Not surprisingly, h33 has mutations in all 4 of these chromosomes.

[Main Loop]

The code on the left is the original Facto-f genome, and the code on the right is the Facto-h33 genome. Lines highlighted in gray with blue text are present in f, but missing in h33.

Lines 3 & 10: Both of these were intended to be timesavers.  On line 3, if a number is < 4 then it is either 1, 2, or 3 all of which factor trivially and therefore don't need to run through the formal factoring process.  But then how often is one of those going to be in the test sample?  h33 has discarded this test.  On line 10 I check to see if the value to factor has become 1 and if it has I bail to the end, as there is no reason to continue.  But line 11 would also capture this condition, and therefore there is no reason to have line 10.  h33 therefore ditches line 10 as well.

Lines 4, 8, 12, 15, 30: The original code contained comments and blank lines which are interpreted as NOP commands by the container class.  NOP = No OPeration.  Executing this line does nothing at all… except consume one execution step.  Most of the NOP's in [Main Loop] have been ditched by h33.  Resulting in slightly more efficient code.

[Compute Root]

Lines highlighted in ochre are changed in h33 from the original code in f.  This is the most heavily modified chromosome.

Line 8: Facto-f uses the target value divided by 2 as the first root to test, instead h33 simply uses the value 16/4 (a.k.a. 4).  Strangely, running the Babylonian method myself I discovered that using 4 instead of target/2 tended to require 1 fewer iterations of the method to get to the root.  This lucky mutation saves the Weelander time.

Line 9: The baseline requires that the loop keep iterating 3 times once the value of _R and _SquareRoot have become equal.  This is a just-in-case thing I added to make sure that the values stayed equal and didn't change (I'm testing them for equality as integers, and ignoring the fractional part).  So I set a convergence counter, and then on line 21 if the values are equal, I jump to line 25 where I add one to the counter, and if the counter = 3 then I exit the method, otherwise I continue processing the loop.  The modified Weelander exits immediately upon convergence.  It has thrown away lines 9 and 22 where it would set the counter value, which would be wasted execution steps if it isn't going to execute the convergence code.  As soon as the values are equal, it attempts to JUMP to the @CONVERGENT line… but there is no @CONVERGENT line anymore, and in Weelander code, a jump to a line that doesn't exist is interpreted as a jump to the closing brace and out of the function.  This means all the code from lines 17 to 23 in the modified Weelander never execute, and it's a good thing to because there is some weird mutated code in there.

Line 10: The modified Weelander has discarded the NOP's on lines 10, 15-17, and 20, all through random mutation and natural selection.

Summary:
The resulting code is several lines shorter, the execution loop has 8 steps instead of 13, and the changes to the starting value of _R and the convergence test code makes the more efficient Weelander execute the loop approximately 4 fewer times.  In its current configuration the Weelander could drop lines 17-24 and the function would continue to operate, although this would not result in a faster function, and therefore offers no evolutionary advantage.

[Is Prime]

Line 6: Okay this is baffling.  Line 6 of the original code has been moved up to line 3 in the new code, and the = test has become >=.  Basically lines 6 to 13 were timesavers allowing the Weelander to immediately identify the primes <= 19 without having to actually test them for primality.  Any value over 19 would be subjected to the test.  The new code simply says, if a number is >= 2, then it is prime.  Essentially the [Is Prime] chromosome is completely broken in the h33 Weelander.  Since h33 passes accuracy tests, there must be something about the way it operates that allows it to get to the correct answer without being able to identify primes.  I can't wait to see how this works.  There are other mutations, but since they don't execute, there's not much point in discussing them.

[Next Prime]

Lines 3 & 21: this method attempts to find the next prime number to divide the value to be factored.  In order to do this it adds 1 or 2 to the last value used as a test factor and then calls [Is Prime] to test the value.  [Is Prime], as originally coded might have potentially overwritten the current value of _SquareRoot (remember all values are global) and so lines 3 & 21 preserved and restored the value so that the calling function would still have it.  But now [Is Prime] does nothing but say whatever you gave it is prime, and therefore it never molests the _SquareRoot global.  Therefore lines 3 & 21 are wasted execution steps and mutated away to the benefit of the Weelander.  The ultimate effect of the changes to [Is Prime] mean that now instead of dividing by 2, 3, 5, 7, 11, 13, 17, 19, 23… the genome will divide by 2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23… essentially 2 and all the odd numbers.  Even though this amounts to more divisions, for the Weelander it's faster than trying to figure out if N is prime, and it has no impact on accuracy.  If you tested for divisibility by 3, testing for divisibility by 9 only costs you time, the value will not be divisible by 9 because you already factored out 3 as many times as possible.

Lines 5 & 12: As in other chromosomes, the NOP's have been dropped.

Not Bad!

All in all, I'm very happy with this simulation.  If the Weelanders relied on the container class to perform the IsPrime, NextPrime, and ComputeRoot functionality, then these mutations would never have occurred, but because these operations are handled in native Weelander code, it's actually faster to do more divisions than it is to find the next prime to divide by.  h33 represents a very strong improvement over f, and every bit of that improvement is the result of random mutation and natural selection.  Some of the methods look like a computer programmer went through them and cleaned them up, dropping unnecessary tests and removing no-ops, but this was the result of mutation and natural selection instead.  Darwin wins, again.

Obviously the next sim should involve starting from h33 and using infusions of h33 to prevent drift.  Is there anything else the Weelanders can do to improve on this?  If you're not going to bother with primality tests, [Next Prime] could probably be simplified further.  Whatever happens, I'm quite certain I'll be surprised!