So I’ve been playing with a genetic algorithm to find small neural networks for simple problems. Mostly I can’t get the damn things to converge, but it’s still fun to watch.
I noticed one thing; that when the list is getting close to a solution, the gene pool is filled with very similar results. The pool has mostly settled on a solution — one that scores very high — but it’s trying to find the last piece that will complete the picture. It can spend thousands or tens of thousands of cycles waiting for a mutation that corrects the last bit.
So I came up with a “scitter” combination for just that situation. The idea is that given two chromosomes, where the genes match I leave them alone. But where they differ is where the action is. So I just randomize those.
Hm. Maybe I should have called it “directed mutation”.
I was amazed at how rapidly it converges for certain types of problems. I’m in the process at trying it on more of an “artificial life” problem next.
There’s one catch. Let’s take a simple example where I’m using a genetic algorithm to guess a word. Let’s say the word is “booga”. Let’s say the gene pool selects these two words to combine:
Now, the scitter combiner is going to randomize the first gene (i.e. the first letter), and leave the rest alone. But if it randomly selects “x” or “t” instead of “b”, then instead of finding a solution, it will lose information. And it’s twice as likely to do that than guess right! I found that scitter can flood the gene pool with identical strings. What that happens, that, of course, is the end of that.
So what I do is, if I hand two identical strings to scitter, it returns a completely random string. It sort of re-rolls all the dice to try to figure out the one that counts.
In Python, scitter looks like this:
def scitter(brain0, brain1): """Randomize the genes that don't match. The idea is, as the solution converges, there will be a small number of holdouts that we need to guess. By keeping the matches the same and scrambling the mis-matches, we're taking a shot at guessing the correct values. """ if brain0 == brain1: # otherwise the pool becomes a single pattern return random() # build the new brain new_genes =  for i in xrange(length): if brain0[i] == brain1[i]: g = brain0[i] else: g = random_gene() new_genes.append(g) return ''.join(g for g in new_genes)