- Start with a random string of 28 characters
- Copy this string 100 times, with a 5% chance per character of that character being replaced with a random character
- Compare each new string with the target "METHINKS IT IS LIKE A WEASEL", and give each a score
- If any of the new strings has a perfect score, halt
- Otherwise, take the highest scoring string, and go to step 2
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.
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".