Playing around with some genetic algorithms.

SimpleGA.cs

/*
  Copyright (c) 2017 Shane Celis

  Just playing around with some genetic algorithms.
 */
using System;
using System.Collections.Generic;
using System.Linq;
using System.Reflection;

public class SimpleGA<TGenotype, TFitness> {
  // Evaluate fitness (currently framed as a maximization problem)
  public Func<TGenotype, TFitness> evaluate;
  // Func<TPhenotype, TPhenotype, TFitness> bievaluate;
  // Func<List<TPhenotype>, TFitness> coevaluate;
  // Select
  public Func<int,
    IEnumerable<Pair<TGenotype, TFitness>>,
    IEnumerable<Pair<TGenotype, TFitness>>> select; // Second list is smaller
  // Tweak
  public Func<TGenotype, TGenotype> mutate;
  // Func<List<TGenotype>, List<TGenotype>> crossover;
  public Func<TGenotype, TGenotype, TGenotype> crossover;
  // generate
  public Func<TGenotype> generate;
  public Func<TGenotype, string> toString = x => x.ToString();
  public Func<TFitness, string> fitnessToString = x => x.ToString();
  public Func<TFitness, bool> terminateP = _ => false;
  public Action<int> endGeneration = i => { };

  public double mutationProbability = 0.7;
  public int lambda = 5;               // number of parents
  public int mu = 5;                   // number of children
  public int nu = 0;                   // number of swamp things (randomly generated)
  protected Random random = new Random();
  /* This is to stop the evolutionary stream from going on endlessly,
     accidentally. The client really should just add a .Take(n) to limit to n
     generations. */
  int maxGenerations = 100;

  /*
    Algorithm 19: The (\mu + \lambda) Evolutionary Strategy

    Sean Luke, 2013, Essentials of Metaheuristics, Lulu, second edition
    http://cs.gmu.edu/~sean/book/metaheuristics/
  */
  public IEnumerable<IEnumerable<Pair<TGenotype,TFitness>>>
    EvolutionaryStrategy(int mu, int lambda) {

    var pop = Enumerable.Range(0, lambda)
      .Select(_ => generate());
    return EvolutionaryStream(pop, mu, 0);
  }

  public IEnumerable<IEnumerable<Pair<TGenotype, TFitness>>> EvolutionaryStream() {
    return EvolutionaryStream(mu, lambda, nu);
  }

  public IEnumerable<IEnumerable<Pair<TGenotype, TFitness>>>
    EvolutionaryStream(int childrenProduced,
                       int parentsSelected,
                       int newlyMade) {
    int mu = childrenProduced;
    int lambda = parentsSelected;
    return EvolutionaryStream(Enumerable.Range(0, lambda).Select(_ => generate()), mu, newlyMade);
  }

  public IEnumerable<IEnumerable<Pair<TGenotype,TFitness>>>
    EvolutionaryStream(IEnumerable<TGenotype> pop, int? mu = null, int nu = 0) {

    int lambda = pop.Count();   // Count of parents selected
    if (! mu.HasValue)
      mu = lambda;              // Count of children produced
    // Evaluate initial population.
    var evaluated = pop
      .Select(g => new Pair<TGenotype, TFitness>(g, evaluate(g)))
      .ToList();                // This .ToList() is important.

    endGeneration(0);
    for (int i = 0; i < maxGenerations
                    && ! evaluated.Any(gf => terminateP(gf.fitness)); i++) {
      // Return the last evaluated generation.
      yield return evaluated;
      // Select the parents.
      var parentsWithFitness = select(lambda, evaluated);
      var parents = parentsWithFitness.Select(gf => gf.genotype).ToList();
      // Generate the children.
      var children = Enumerable.Range(0, mu.Value)
        .Select(_ => (random.NextDouble() < mutationProbability)
                     ? mutate(parents.Random())
                     : crossover(parents.Random(), parents.Random()));
      // Insert newly generated individuals into the population.
      var newlyMade = Enumerable.Range(0, nu)
        .Select(_ => generate());
      // Mix together and evaluate the next population.
      evaluated = children
        .Concat(newlyMade)
        .Select(g => new Pair<TGenotype, TFitness>(g, evaluate(g)))
        .Concat(parentsWithFitness) // Exclude this line for a (\mu, \lambda) algorithm.
        .ToList();              // This .ToList() is important. If it's not
                                // here, evaluated.Any() above will be silently
                                // produce a new generation.
      endGeneration(i);
    }
    // Return the last generation.
    yield return evaluated;
    // Return the best individual.
    yield return select(1, evaluated);
  }


  public void PrintPopulationWithFitness(string header, IEnumerable<Pair<TGenotype, TFitness>> pop) {
    Console.Out.WriteLine(header + string.Join(" ",
                                               pop.Select(gf => new Pair<string, string>(toString(gf.genotype),
                                                                                         fitnessToString(gf.fitness)))));
  }

  public void PrintPopulation(string header, IEnumerable<Pair<TGenotype, TFitness>> pop) {
    Console.Out.WriteLine(header + string.Join(" ",
                                               pop
                                               .Select(i => toString(i.genotype))));
  }

  public static Pair<TGenotype, TFitness>
    TournamentSelection(int k, IEnumerable<Pair<TGenotype, TFitness>> pop) {
    // return pop.Random(k).MaxBy(i => i.fitness);
    return pop.Random(k).OrderByDescending(i => i.fitness).First();
  }

}

public class IntGA : SimpleGA<int, int> {
  public IntGA() {
    evaluate    = x => x;
    select      = (c, xs) => xs.OrderByDescending(gf => gf.fitness).Take(c);
    mutate      = x => x + (random.Next(10) - 5);
    crossover   = (x, y) => x + y;
    generate    = () => random.Next(3);
    terminateP  = x => x > 100;
  }
}

public class BoolGA : SimpleGA<bool[], int> {
  int geneCount = 5;
  public BoolGA() {
    evaluate    = x => x.Count(y => y);
    select      = (c, xs) => xs.OrderByDescending(gf => gf.Item2).Take(c);
    mutate      = x => x.Select(y => (mutationProbability < random.NextDouble()) ? ! y : y).ToArray();
    crossover   = (x, y) => {
      var i = random.Next(geneCount);
      return x.Take(i).Concat(y.Skip(i)).ToArray();
    };
    generate    = () => Enumerable.Range(0, geneCount).Select(i => random.Next(2) == 1).ToArray();
    toString    = x => string.Join("", x.Select((bool y) => y ? '1' : '0'));
    terminateP  = f => f == geneCount;
  }
}

public class IntHillClimber : SimpleGA<int, int> {
  public IntHillClimber() {
    lambda     = 1;
    mu         = 1;
    evaluate   = x => x;
    select     = (c, xs) => xs.OrderByDescending(gf => gf.Item2).Take(c);
    mutate     = x => x + (random.Next(10) - 5);
    crossover  = (x, y) => (x + y)/2;
    generate   = () => random.Next(3);
    terminateP = x => x > 100;
  }
}

public class AgeFitnessPareto : SimpleGA<int[], int[]> {
  public Func<int[], int[], bool> dominates;
  public AgeFitnessPareto() {
    int gaTime               = 0;
    int paretoTournamentSize = 5;
    nu              = 2;
    evaluate        = x => new [] { x[0], gaTime - x[1] };                           // (fitness, age)
    select          = (c, xs) => Nondominated(xs.Random(paretoTournamentSize)).ToList();
                                                                                     // select = (c, xs) => Nondominated(xs).ToList();
    mutate          = x => new int[] { x[0] + (random.Next(10) - 5), x[1] - 1 };     // (genotype, birthday)
    crossover       = (x, y) => new int[] { (x[0] + y[0]), Math.Min(x[1], y[1]) - 1 };
                                                                                     // not actually called
    generate        = () => new int[] { random.Next(3), gaTime };                    // (genotype, birthday)
    terminateP      = x => x[0] > 100;
    dominates       = (x, y) => x[0] > y[0] && x[1] < y[1];                          // better fitness, lower age
    // toString     = x => new Pair<string, string>(string.Join(" ", x.genotype), string.Join(" ", x.fitness));
    toString        = x => Tuple.Create(string.Join(" ", evaluate(x))).ToString();
    fitnessToString = x => string.Join(" ", x);
    endGeneration   = i => gaTime = i;
  }

  public IEnumerable<Pair<int[], int[]>> Nondominated(IEnumerable<Pair<int[], int[]>> pop) {
    var poplist = pop.ToList();
    for (int i = 0; i < poplist.Count; i++) {
      for (int j = 0; j < poplist.Count; j++) {
        if (i == j)
          goto inner;
        if (dominates(poplist[j].fitness, poplist[i].fitness))
          goto outer;
        inner:
        ;
      }
      yield return poplist[i];
      outer:
      ;
    }
  }
}

public static class Program {

  public static int Main(string[] args) {
    if (args.Length != 1) {
      Console.Error.WriteLine("usage: SimpleGA <IntGA, BoolGA, IntHillClimber, AgeFitnessPareto>");
      return 2;
    }
    dynamic ga = Activator.CreateInstance(Type.GetType(args[0]));
    // var ga = new IntGA();
    // var ga = new BoolGA();
    // var ga = new IntHillClimber();
    // var ga = new AgeFitnessPareto();
    // var pop = Enumerable.Range(0, 1).Select(_ => ga.generate());
    var stream = ga.EvolutionaryStream();
    int i = 0;
    foreach (var popi in stream
             //.Take(5) // Limit to only 5 generations
             ) {
      // ga.PrintPopulationWithFitness("gen " + (i++) + ": ", popi);
      ga.PrintPopulation("gen " + (i++) + ": ", popi);
    }
    return 0;
  }
}

public static class Extensions {
  private static Random random = new Random();
  //$ cite -ma 21351230 -t excerpt -u \
  // http://stackoverflow.com/questions/3173718/how-to-get-a-random-object-using-linq
  public static T Random<T>(this IEnumerable<T> enumerable) {
    int index;
    return RandomWithIndex(enumerable, out index);
  }

  public static T RandomWithIndex<T>(this IEnumerable<T> enumerable, out int index) {
    var list = enumerable as IList<T> ?? enumerable.ToList();
    return list.ElementAt(index = random.Next(list.Count));
  }

  public static IEnumerable<T> Random<T>(this IEnumerable<T> enumerable, int k) {
    var list = new List<T>(k);
    using (var e = enumerable.GetEnumerator()) {
      for (int i = 0; i < k && e.MoveNext(); i++) {
        list.Add(e.Current);
      }
      for (int j, i = k + 1; e.MoveNext(); i++) {
        j = random.Next(i);
        if (j < k)
          list[j] = e.Current;
      }
      return list;
    }
  }
}

public class Pair<TGenotype, TFitness> : Tuple<TGenotype, TFitness> {
  public Pair(TGenotype genotype, TFitness fitness) : base(genotype, fitness) { }

  public TGenotype genotype {
    get { return Item1; }
  }
  public TFitness fitness {
    get { return Item2; }
  }

  public static Pair<T1, T2> Create<T1, T2>(T1 g, T2 f) {
    return new Pair<T1, T2>(g, f);
  }
}