Strategy Pattern in .NET NeuroEvolution Algorithms

Getting back to the NeuroEvolution research after a couple of years of delay has turned out to be quite rewarding.

For example, while writing new implementation of the algorithm from scratch I just could not avoid leveraging some principles from the Lokad Shared (apart from using the core library). One of these patterns is about cleanly separating some logic in the delegates, and then combining these delegates to produce the desired effects.

We had Action Policies and Validation Rules in .NET enterprise development. In NeuroEvolution algorithms we can also apply these principles to mutation strategies.

By the way, I've created a separate page to serve as an index for these NeuroEvolution series. And there also is a NeuroEvolution RSS feed.

Strategy Pattern

Every evolutionary algorithm leverages operations like mutate or crossover that have certain probability of occuring. Additionally, NeuroEvolutional algorithms (being more specific) have to operate with the networks that can grow and thus they leverage strategies like AddConnection, RemoveConnection, Jiggle and some others.

Since such algorithms are being developed within the the research process, soon they turn into a mess of heuristics:

foreach (var genome in winners)
{
  if (Rand.NextDouble() < mutationChance)
  {
    // do mutation
  }
  if (Rand.NextDouble() < crossOverChance)
  {
    var parent = Rand.NextItem(winner);
    // do crossover    
  }
  if (Rand.NextDouble() < addSynapse)
  {
    // add synapse
  }
  // etc
}

Let's try to make everything slightly more extensible and fit for the research process.

We'll define our strategy as:

public delegate Genome MutationStrategy(Genome source, Genome parent,
  Context context);

where the Genome is just genocode, and Context class contains population-specific properties like PopulationAge or JiggleFactor.

Given that, we can cleanly define our strategies in C# like this:

public static Genome AddSynapse(Genome source, Genome parent, 
  Context context)
{
  // Rand is a class from Lokad Shared that makes it easier
  // to use various random generators
  var input = Rand.NextItem(source.Neurons).Index;
  var output = Rand.NextItem(source.Neurons).Index;
  var param = Rand.NextDouble();
  var newConnection = new SynapseGene(input, output, param);
  return Genome.AddConnection(source, newConnection);
}

public static Genome FastestWins(Genome source, Genome parent, 
  Context context)
{
  if (source.Synapses.Length < parent.Synapses.Length)
    return source;
  return parent;
}

or even reuse one strategy in another:

public static Genome RemoveSynapse(Genome source, Genome parent,
  Context context)
{
  var length = source.Synapses.Length;
  if (length > 1)
  {
    var idx = Rand.Next(length);

    return Genome.DropConnection(source, idx);
  }
  return FastestWins(source, parent, context);
}

Obviously, you could also create parametrized strategies as well.

Then these strategies could be combined together (with probabilities of happening) like this:

// Tuple is a class from Lokad Shared that makes it more
// simple to bind values together
var chances = new List<Tuple<int, MutationStrategy>>();

chances.Add(5, Strategies.AddSynapse);
chances.Add(10, Strategies.RemoveSynapse);
chances.Add(20, Strategies.DadWins);
chances.Add(10, Strategies.MutateSynapse);
chances.Add(20, Strategies.MutateNeuron);
chances.Add(5, Strategies.AddNeuron);
chances.Add(20, Strategies.Cross);

var strategies = CreateRoulette(chances);

where CreateRulette simply creates array of strategies, where each strategy has N number of entries (thus the probability of being applied is Pi = Ni/Sum(Ni)):

public static T[] CreateRoulette<T>(IEnumerable<Tuple<int,T>> source)
{
  return source.SelectMany(tuple => 
    Enumerable.Repeat(tuple.Item2, tuple.Item1)).ToArray();
}

With that we can apply random strategy to every item in the population pool like this (random item from the winners collection is being picked as the primary parent):

population = population.Convert(g =>
  Rand.NextItem(strategies)(Rand.NextItem(winners), g, context));

New .NET 3.5 features make wonders to these old C# algorithm implementations, do not they?

As the NeuroEvolution series go on, we'll see if it is possible to make it even more simple to write these machine-learning heuristics that leverage the latest technology.

PS: .NET F# can make wonders to the performance of these algorithms by making them as fast as pure C. Check out the latest update to the previous post for details.