# Methinks it is like a Weasel

I'm posting this older code example of a simple evolutionary algorithm to get it off my hard drive :)

I've been interested in evolutionary algorithms for a while now with an idea of using them to solve some interesting puzzles (more of that in a later post, honest).

This is the canonical example provided by Richard Dawkins in his book The Blind Watchmaker which attempts to start with a random series of letters of the right length and by random mutation, generates a quote from Act 3 Scene 2 of Hamlet:

HAMLET

Do you see yonder cloud that’s almost in shape of a camel?

POLONIUS

By th' mass, and ’tis like a camel indeed.

HAMLET

Methinks it is like a weasel.

## Interfaces

``````
﻿public interface ICrossover<T>
{
T Mutate(T instance, double rate);
}

``````
``````
﻿public interface IMutator<T>
{
T Mutate(T instance, double rate);
}
``````
``````
﻿public interface IPopulationFactory<T>
{
T Create();

Collection<T> Create(int populationSize);

Collection<T> CreateFrom(Collection<T> generation);
}
``````
``````
﻿public interface IFitnessScore<T>
{
int Score(T instance);
}
``````
``````
﻿public interface IMatchesTarget<T>
{
bool MatchesTarget(T instance);
}
``````

## Implementations

``````
﻿public class WeaselMutator : IMutator<string>
{
private Random _rng;

public WeaselMutator()
{
this._rng = new Random((int)DateTime.Now.Ticks);
}

public string Mutate(string current, double rate)
{
return String.Join("", from c in current
select _rng.NextDouble() <= rate ? _rng.NextCharacter() : c);
}
}
``````
``````
﻿public class WeaselPopulationFactory : IPopulationFactory<string>
{
private Random _rng;

public WeaselPopulationFactory(int length)
{
this.Length = length;
this._rng = new Random((int)DateTime.Now.Ticks);
}

private int Length { get; set; }

public string Create()
{
return this._rng.NextString(this.Length);
}

public Collection<string> Create(int populationSize)
{
throw new NotImplementedException();
}

public Collection<string> CreateFrom(Collection<string> generation)
{
throw new NotImplementedException();
}
}
``````
``````
﻿public class WeaselFitnessScore : IFitnessScore<string>, IMatchesTarget<string>
{
public WeaselFitnessScore(string target)
{
this.Target = target;
}

public string Target { get; set; }

public int Score(string current)
{
return this.Target.Zip(current, (a, b) => a == b ? 1 : 0).Sum();
}

public bool MatchesTarget(string instance)
{
return this.Target == instance;
}
}

``````

## Extension Methods

``````
﻿public static class RandomExtensions
{
public static char NextCharacter(this Random self)
{
const string AllowedChars = " ABCDEFGHIJKLMNOPQRSTUVWXYZ";
return AllowedChars[self.Next() % AllowedChars.Length];
}

public static string NextString(this Random self, int length)
{
return String.Join("", Enumerable.Repeat(' ', length)
.Select(c => self.NextCharacter()));
}
}
``````

## Events

``````
﻿public class InitialConditionEventArgs<T> : EventArgs
{
public InitialConditionEventArgs(T initial, int score)
{
this.InitialCondition = initial;
this.Score = score;
}

public T InitialCondition { get; set; }

public int Score { get; set; }
}
``````
``````
﻿public class FitnessProgressEventArgs<T> : EventArgs
{
public FitnessProgressEventArgs(int attempt, T best, int score)
{
this.Generation = attempt;
this.Best = best;
this.Score = score;
}

public int Generation { get; set; }

public T Best { get; set; }

public int Score { get; set; }
}
``````
``````
﻿public class FinalConditionEventArgs<T> : EventArgs
{
public FinalConditionEventArgs(int attempt, T final, int score)
{
this.Generation = attempt;
this.FinalCondition = final;
this.Score = score;
}

public int Generation { get; set; }

public T FinalCondition { get; set; }

public int Score { get; set; }
}

``````

## Algorithm

``````
﻿public class GeneticAlgorithm<T>
{
public event EventHandler<InitialConditionEventArgs<T>> Start;

public event EventHandler<FitnessProgressEventArgs<T>> Progress;

public event EventHandler<FinalConditionEventArgs<T>> Finish;

public IPopulationFactory<T> Population { get; set; }

public IMatchesTarget<T> TargetMatch { get; set; }

public IMutator<T> Mutator { get; set; }

public IFitnessScore<T> FitnessScore { get; set; }

public GeneticAlgorithm()
{
this.PopulationSize = 100;
this.MutationRate = 0.05;
this.GenerationLimit = 100;
}

public int PopulationSize { get; set; }

public double MutationRate { get; set; }

public int GenerationLimit { get; set; }

public void Run()
{
T parent = this.Population.Create();

if (this.Start != null)
this.Start(this, new InitialConditionEventArgs<T>(parent, this.FitnessScore.Score(parent)));

int attempt = 0;

while (!this.TargetMatch.MatchesTarget(parent) && attempt < GenerationLimit)
{
// Create C mutated strings + the current parent.
var candidates = (from child in Enumerable.Repeat(parent, PopulationSize)
select this.Mutator.Mutate(child, MutationRate))
.Concat(Enumerable.Repeat(parent, 1));

// Sort the strings by the fitness function.
var sorted = from candidate in candidates
orderby this.FitnessScore.Score(candidate) descending
select candidate;

// New parent is the most fit candidate.
parent = sorted.First();

++attempt;

if (this.Progress != null)
this.Progress(this, new FitnessProgressEventArgs<T>(attempt, parent, this.FitnessScore.Score(parent)));
}

if (this.Finish != null)
this.Finish(this, new FinalConditionEventArgs<T>(attempt, parent, this.FitnessScore.Score(parent)));
}
}

``````

## Main

``````
﻿class Program
{

static void Main(string[] args)
{
GeneticAlgorithm<string> algo = new GeneticAlgorithm<string>
{
PopulationSize = 100,
MutationRate = 0.05,
GenerationLimit = 100
};

string target = "METHINKS IT IS LIKE A WEASEL";

algo.Mutator = new WeaselMutator();

var scorer = new WeaselFitnessScore(target);
algo.FitnessScore = scorer;
algo.TargetMatch = scorer;

algo.Population = new WeaselPopulationFactory(target.Length);

algo.Start += (obj, e) =>
{
Console.WriteLine("START:       {0,20} fitness: {1}", e.InitialCondition, e.Score);
};

algo.Progress += (obj, e) =>
{
Console.WriteLine("     #{0,6} {1,20} fitness: {2}", e.Generation, e.Best, e.Score);
};

algo.Finish += (obj, e) =>
{
Console.WriteLine("END: #{0,6} {1,20}", e.Generation, e.FinalCondition);
};

//const string target = "METHINKS IT IS LIKE A WEASEL";

algo.Run();