Evolutionary

A small toolbox library for evolutionary algorithms. It does not implement one or more evolutionary algorithms for you, but gives you the data types and operators at hand to write it yourself.

The main logic uses only two immutable types that are transformed by operators. All operators are implemented as extension methods, hence it is easy to add custom operators.

• Population<TIndividual> – an immutable snapshot of all individuals and their fitness function.
• Offspring<TIndividual> – besides a reference to the parent population, it owns the random number generator, offers a random enumeration of the parent individuals and an enumeration of the children generated so far.

For the individuals, the library ships three ready-made types — Permutation for permutation-encoded, BitString for binary-encoded and RealVector<T> for real-encoded problems. But you can add with little effort your own implementation for the individuals.

A complete example

In this example the square root of 2 is calculated. Of course, there are better methods to do this, but it gives a good impression how the Evolutionary library is used.

//
// In this example we calculate the square root of 2.
//
using Evolutionary;
using System;

// The data set is the square value of the value we are looking for. If you
// want for example calculate the square root of 5, change the value of the
// data set to 5.
double dataSet = 2;

// The fitnes function calculates how close we are to the exact solution.
Func<double, double> fitness = x => Math.Abs(dataSet - x * x);

// We start with a population of 20 random individuals. Individuals are
// generated by the lambda expression and are uniformly distributed
// between 0 and d, here 2.
var random = new Random();

var population = Population
    .Create(fitness)
    .AddIndividuals(20, () => random.NextDouble(0, dataSet));

// We will iterate here over 50 generations. A more sophisticated approach
// would be to consider the development of the fitness value of the best
// individual or the whole population. One could also define an upper limit
// of the calculation time, or a combination of several conditions.
for (int i = 0; i < 50; i++)
{
    population = population
        .SelectParentsByRank(random)  // This generates an offspring of the population
        .Recombine(
            20,                 // 20 children are created by recombination
            (a, b, rnd) =>      // Two parents, a and b, will create a new child
            {
                // The new child will be located somewhere
                // "between" the parents. Since we use a
                // random value normally distribute around
                // the parents mean value (mu), the child will
                // infact lay in around 30% of the cases
                // outside of the parents' range.
                var mu = (a + b) / 2;
                var sigma = (a == b) ? 1.0E-6 : Math.Abs(a - b) / 2;

                return Math.Abs(rnd.NextNormal(mu, sigma));
            })
        .SelectElite(2)         // We preserve the two best individuals
                                // of the parent generation.
        .SelectSurvivors(20)    // We have 22 children in this offspring,
                                // but only the best 20 will survive.
        .ToPopulation();        // This will convert the offspring to
                                // a new population.

    // The individuals of a population are always sorted by their fitness.
    // Hence selecting the first individual will give you the currently best
    // fitting individual.
    var best = population.Individuals[0];
    var f = fitness(best);

    Console.WriteLine(
        $"({i}) " +
        $"Best: {best:G17} " + 
        $"Fitness: {f:G5} " +
        $"Expected: {Math.Sqrt(dataSet):G17}");
}

More examples

• The OneMax example is the "hello world" of evolutionary algorithms: it maximizes the number of set bits in a bit string with the BitString individual. It also shows how a maximization problem is expressed with the minimize-oriented fitness of the library.
• The Sphere example minimizes the Sphere function f(x) = sum(x_i^2) with the real-encoded RealVector<T> individual and shows how a decreasing mutation strength avoids the convergence plateau of a fixed sigma.
• The EightQueens example is a WPF application that visualizes how a population of queen permutations evolves towards a solution of the eight queens puzzle.