Evolutionary algorithm

Starting with:

The target string: "METHINKS IT IS LIKE A WEASEL".
An array of random characters chosen from the set of upper-case letters together with the space, and of the same length as the target string. (Call it the parent).
A fitness function that computes the 'closeness' of its argument to the target string.
A mutate function that given a string and a mutation rate returns a copy of the string, with some characters probably mutated.
While the parent is not yet the target:

copy the parent C times, each time allowing some random probability that another character might be substituted using mutate.
Asses the C+1 strings fitness to the target and make the most fit string the new parent, discarding the others.
repeat until the parent converges, (hopefully), to the target.

C.f: wp:Weasel_program#Weasel_algorithm and wp:Evolutionary algorithm

Note: to aid comparison, try and ensure the variables and functions mentioned in the task description appear in solutions

Python

Using lists instead of strings for easier manipulation, and a mutation rate that gives more mutations the further the parent is away from the target. <lang python>from string import ascii_uppercase from random import choice, random

target = list("METHINKS IT IS LIKE A WEASEL") charset = ascii_uppercase + ' ' parent = [choice(charset) for _ in range(len(target))] minmutaterate = .09 C = range(100)

perfectfitness = len(target) def fitness(trial):

   'Sum of matching chars by position'
   return sum(t==h for t,h in zip(trial, target))

def mutaterate():

   'Less mutation the closer the fit of the parent'
   return 1-((perfectfitness - fitness(parent)) / perfectfitness * (1 - minmutaterate))

def mutate(parent, rate):

   return [(ch if random() <= rate else choice(charset)) for ch in parent]

def que():

   '(from the favourite saying of Manuell in M-Python)'
   print ("#%-4i, fitness: %4.1f%%, '%s'" %
          (iterations, fitness(parent)*100./perfectfitness, .join(parent)))

iterations = 0 while parent != target:

   rate =  mutaterate()
   iterations += 1
   if iterations % 100 == 0: que()
   copies = [ mutate(parent, rate) for _ in C ]  + [parent]
   parent = max(copies, key=fitness)

print () que() </lang>

Sample output

#100 , fitness: 50.0%, 'DVTAIKKS OZ IAPYIKWXALWE CEL'
#200 , fitness: 60.7%, 'MHUBINKMEIG IS LIZEVA WEOPOL'
#300 , fitness: 71.4%, 'MEYHINKS ID SS LIJF A KEKUEL'

#378 , fitness: 100.0%, 'METHINKS IT IS LIKE A WEASEL'