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();

        Console.ReadKey();
    }
}

Using as many interfaces as I have and using generic types may seem a little like overkill but, as I said, I am hoping to complete a project using some alternate implementations for a more interesting purpose. Stay tuned :)