Mainly Tech projects on Python and Electronic Design Automation.

Friday, October 02, 2009

The Otter Algorithm

I was reading about a Richard Dawkins program that through random mutation and selection of best fit, would gradually converge a random string into a target string. It is called the Weasel Program,and a rough outline of it is:
  1. Start with a random string of 28 characters
  2. Copy this string 100 times, with a 5% chance per character of that character being replaced with a random character
  3. Compare each new string with the target "METHINKS IT IS LIKE A WEASEL", and give each a score
  4. If any of the new strings has a perfect score, halt
  5. Otherwise, take the highest scoring string, and go to step 2
After coding it up, I found it just would not converge to a final match for me. I suspected I had a mistake somewhere , but just did not like how long it was taking to converge.

I decided to change things.

It seemed to me that if you are further away from the ideal, then you should change more letters; and, after seeing the score for how good the current best string  is sometimes decrease, I made a modification to choose the best of the copies and the best string that they are mutations of.

With that modification, convergence was swift.

Oh, I call it the Otter program, as it is more than the Weasel.

The prog

 1 
 2 '''
 3 From: http://en.wikipedia.org/wiki/Weasel_program
 4       With modifications
 5 '''
 6 
 7 from string import ascii_uppercase
 8 from random import choice, random
 9 
10 target = list("METHINKS IT IS LIKE A WEASEL")
11 chance = .05
12 times  = 100
13 
14 charset      = ascii_uppercase + ' '
15 iterations   = 0
16 highscore    = [choice(charset) for _ in range(len(target))]
17 perfectscore = len(target)
18 
19 def score(trial):
20     return sum(t==h for t,h in zip(trial, target))
21 
22 while highscore != target:
23     thischance =  1-((perfectscore - score(highscore)) / perfectscore * (1 - chance))
24     #thischance = chance
25     iterations += 1
26     if iterations % 50 == 0:
27         print (iterations, score(highscore), ''.join(highscore))
28     copies = [ [(ch if random() <= thischance else choice(charset)) for ch in highscore]
29                for _ in range(times) ]  + [highscore]
30     highscore = max(copies, key=score)
31 print (iterations, ''.join(highscore))

Function score at line 19 uses the fact that booleans True and False are also numbers and calculates how many characters are in the right position as its result.

Line 23 modifies the amount of randomness injected, based on how bad the last highscore was: Change more if you are further away from the target - less as you approach.
Name thischance is used in  line 28. random returns a float between 0.0 and 1.0. if it is less than thischance then a particular character is not changed.

The function for thischance in line 23 is equal to chance when no characters match, and 1.0 if all characters were to match. This forces less change as you approach the target string.

Here is a little snippet to show how thischance varies with the score (sc):


>>> for sc in range(0,29,7):
        print( "score=%2i, thischance=%5.2f" % (sc,
                1-((perfectscore - sc) / perfectscore * (1 - chance))) )


score= 0, thischance= 0.05
score= 7, thischance= 0.29
score=14, thischance= 0.53
score=21, thischance= 0.76
score=28, thischance= 1.00 
 
In line 29 the addition of highscore into copies means that the max taken in line 30 can never decrease.

P.S. The post is only tangentially linked to Darwinism. I am secure in the knowledge that my children's school teaches it, and I am not really interested in it being mentioned in any comments. Treat it just as a way to go from a random choice of letters and home in on a target string by  repeated random alterations, and selection of the "best".




6 comments:

  1. hmm. Well, by running your code exactly as it is. I seem to be getting premature convergance to a non-ideal solution.

    Or basically its getting stuck with a score of 4 (or around that) and not moving.

    ReplyDelete
  2. Hi Dougal,
    Thanks for taking the time.

    I just re-checked and re ran my code. Did you remember that line 24 is commented?

    I got the following:

    Python 3.1 (r31:73574, Jun 26 2009, 20:21:35) [MSC v.1500 32 bit (Intel)] on win32
    Type "copyright", "credits" or "license()" for more information.
    >>> ================================ RESTART ================================
    >>>
    50 11 XCTHINIDJATDIR USKE MVWPLBQK
    100 12 MTTHINKHVRTHISSLICDVIQUWATPW
    150 12 MLTHTBGQBITLFEXLIKEWFLWXGSIL
    200 14 MABHUNKG OTDIUSLNKD NKWSAIEL
    250 14 MQOHYIJS IT IX LZUS AGWRENGL
    300 14 AHTHBNKSYIPMIS QULEHABWRADGL
    350 16 MQKHINKSHIF TS LIXQSY WRHYEL
    400 16 MWTC DKSSITZJF LIKKYA UGASEL
    450 17 MVYHQNKSRITQIS LW VJA WIASEH
    500 17 MJGMQNQS ITIIS LSCOWA WBASEL
    550 17 MJTMXNQS ITFIS LHEOHA WBCSEL
    600 18 IEBHMNPS IT IH LMUS A WDASEZ
    650 19 XRTTINOS IT IS LMMT A WEA ZL
    700 20 BETHINKS IT IS LILMRAVWTHSYL
    750 24 METHILKS IT IS LOKESA WOASEL
    800 27 METHINKS IT IS LEKE A WEASEL
    816 METHINKS IT IS LIKE A WEASEL
    >>>

    ReplyDelete
  3. The thing about evolutionary algorithms is that they are basically just a heuristically-directed search through a problem space by gradient descent. For this reason, they are susceptible to hit local minima, and it makes perfect sense that small improvements to the heuristic would make it converge faster or get it to skip over these local minima. In other words, there is really nothing magic about evolutionary algorithms; however they can be an efficient approach to solving a problem.

    ReplyDelete
  4. Your original program didn't converge because your mutation rate is way too high. The expression "(ch if random() <= chance else choice(charset))" where chance = 0.05 means there is 95% chance the character will be mutated. I think what you want is "(choice(charset) if random() < chance else ch)". With this change, the string converges to the solution within a hundred generations; so you don't need to vary the mutation rate.

    ReplyDelete
  5. Hi Steve,
    You're right about the lack of magic. Coding a small example soon dispels any such pretension.

    Hi Alexander,
    I took another look and the commented out line 24 should have been deleted as when I was using it, line 28 was the right way around, (I think). But really, writing this I now know that not only was I confused, I was eager to try and get something like line 23 in, so did not give the original enough time.

    I like to tinker, and sometimes the urge wins out.

    Thanks for your analysis though.

    - Paddy.

    ReplyDelete
  6. I transmuted the above into this Rosetta Code task. Check it out.

    - Paddy.

    ReplyDelete

Followers

Subscribe Now: google

Add to Google Reader or Homepage

Go deh too!

whos.amung.us