Genetic Algorithms: The Scitter Combiner

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:

target: booga
chromo0: xooga
chromo1: tooga

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)
Advertisements

Leave a comment

Filed under computer algorithms, utility

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s