F# News

An interesting challenge is called Evolutionary Algorithm and draws upon a famous computer simulation written by Richard Dawkins to demonstrate the power of random variation and non-random cumulative selection in natural and artificial evolutionary systems, and how this process differs from chance.

The program begins with a random string of letters and spawns a generation of 200 random mutations of the parent string, selects the fittest mutation (by similarity to an "ideal" string) and uses that individual to spawn the next generation. The ideal string used is "METHINKS IT IS LIKE A WEASEL".

The results of this program clearly demonstrates how selection can drive random processes to solve problems extremely efficiently: only 6 generations were required to reproduce the ideal string exactly. In fact, randomized algorithms are of great practical importance and a similar technique, simulated annealing, is used as an example in our F# for Technical Computing book.

Our F# solution is as follows:

let target = "METHINKS IT IS LIKE A WEASEL"
let charset = "ABCDEFGHIJKLMNOPQRSTUVWXYZ "
 
let rand = System.Random()
 
let fitness (trial: string) =
  Seq.zip target trial
  |> Seq.fold (fun d (c1, c2) -> if c1=c2 then d+1 else d) 0
 
let mutate parent rate _ =
  String.mapi (fun _ c ->
    if rand.NextDouble() < rate then c else
      charset.[rand.Next charset.Length]) parent
 
do
  let mutable parent =
    String.init target.Length (fun _ ->
      charset.[rand.Next charset.Length] |> string)
  let mutable i = 0
  while parent <> target do
    let pfit = fitness parent
    let best, f =
      Seq.init 200 (mutate parent (float pfit / float target.Length))
      |> Seq.map (fun s -> (s, fitness s))
      |> Seq.append [parent, pfit]
      |> Seq.maxBy (fun (_, f) -> f)
    if i % 100 = 0 then
      printf "%5d - '%s'  (fitness:%2d)\n" i parent f
    parent <- best
    i <- i + 1
  printf "%5d - '%s'\n" i parent

This program produces the following output:

    0 - 'CEUMIDXSIXOOTSEHHXVMD IHTFWP'  (fitness: 6)
  100 - 'PEPHIZLB NGSIO LCWE AQEKCSZQ'  (fitness:11)
  200 - 'MESHIZHB IQ IO LTWGGAQWMKSRX'  (fitness:13)
  300 - 'MESHIZHB IQ IO LTWGGAQWMKSRX'  (fitness:13)
  400 - 'METHIVKS ITLIN LYKJPABWDASEU'  (fitness:19)
  500 - 'METHINKS IT IB LIKEFA WDASEL'  (fitness:25)
  518 - 'METHINKS IT IS LIKE A WEASEL'

Labels: evolutionary algorithm, mutation, natural selection, rosetta code, survival of the fittest, weasel program

# posted by Jon Harrop @ 16:38