Tuesday, 7 December 2010

Experiments With A Simple Evolutionary Algorithm (1)

In Richard Dawkin's 'The Blind Watchmaker'he describes a program that he built to mutate a random string into a given target string ('Methinks it is like a Weasel'), so I thought I'd try and build one myself. In version one I have three core functions fit(), breed() and make_child().  In each generation one breeds by making a number of children, the fittest of which is returned to be the parent of the next generation. Here are the guts of the functions :

fit(string1, string2)
compare the strings and return the difference between them as a number. 0 is a perfect fit. In version 1 the difference is the alphabetic distance between each individual character in each string :
        for i in range(len(t)):
                f = f + abs(t[i] - s[i])

randomly changes some of the characters in the parent string and returns the new string as the child :
.         for i in range(len(parent)):
                if(random.random() > 0.9):
                        child.append(random.choice('abcdefghijklmnopqrstuvwxyz '))
                else :

create a number of children, compare them with each other and the parent for fitness and return the best to be used as the parent for the next generation. You don't need code for this -it's trivial.

How does it do?
It works! See update.

Questions and Improvements
  •  How good is the measure of fitness?
  • How good is make_child?
  • Is there an ideal combination of generations, offspring and 'variation'
  • Is only having 1 parent OK?
Based on nothing at all, I think that make_child has the most fundamental problem, I think that it should be tweaked to take into account current fitness of the parent. As the fit gets better then the changes should get smaller, as any organism that changed a lot between generations is quite likely to 'evolve' right out of its niche.


Well, I was right, make child did have a fundamental problem. I thougth I was calling a random() function but instead seemed to be instantiating (or perhaps defining) some sort of random object -at least the Python interpreter wasn't complaining, this meant that all the strings were randomized every time and there was no generational inheritance. Fixed this and it worked.  

No comments:

Post a Comment