Creating a Simple Search

Let's see how we can use a Genetic Algorithm to solve a (very simple) optimization problem.

Defining the Problem

Consider arrays of integer numbers. In this tutorial we'll try to find an array in which the sum of the integers is as big as possible.

This is a very simple problem, and there's no real value in applying a Genetic Algorithm to it. Nevertheless, it demonstrates how to use GA.

Creating the Chromosomes

Each chromosome will hold a array of integers. Evaluate will return the sum of the numbers in the array. Mutate will randomly change the value of some of the numbers in the array.

    class NumberVectorChromosome : IChromosome
    {
        private readonly int[] vector;

        public NumberVectorChromosome(int[] vector)
        {
            this.vector = vector;
        }

        public double Evaluate() => vector.Sum();

        public void Mutate()
        {
            var random = new Random();
            for (int i = 0; i < vector.Length; i++)
                if (random.NextDouble() < 0.1)
                    vector[i] += random.Next(0, 10);
        }
    }

Creating the PopulationGenerator

The engine uses the PopulationGenerator to create its initial population. The PopulationGenerator will also renew the population when needed (see IPopulationRenwalManagers).

PopulationGenerators must implement the IPopulationGenerator interface.

Let's create a PopulationGenerator for our chromosomes. Our PopulationGenerator will create an chromosomes with their arrays full of random zeros or ones.

    class NumberVectorPopulationGenerator : IPopulationGenerator
    {
        private readonly Random random = new Random();
        public const int VECTOR_SIZE = 10;

        public IEnumerable<IChromosome> GeneratePopulation(int size)
        {
            var population = new IChromosome[size];

            for (int i = 0; i < size; i++)
                population[i] = GetChromosome();

            return population;
        }

        private NumberVectorChromosome GetChromosome()
        {
            var vector = new int[VECTOR_SIZE];
            for (int i = 0; i < VECTOR_SIZE; i++)
                vector[i] = random.NextDouble() < 0.5 ? 0 : 1;
            
            return new NumberVectorChromosome(vector);
        }

Creating the CrossoverManager

The CrossoverManager tells the engine how to perform crossovers for your chromosomes. In our implementation of CrossoverManager we'll marge two chromosomes into one by randomly selecting a point on one of them, and then connecting the two halves. For more information about crossovers please see this.

CrossoverManagers must implement the ICrossoverManager interface.

    class NumberVectorCrossoverManager : ICrossoverManager
    {
        private readonly Random random = new Random();

        public IChromosome Crossover(IChromosome chromosome1, IChromosome chromosome2)
        {
            var numberChromosome1 = (NumberVectorChromosome) chromosome1;
            var numberChromosome2 = (NumberVectorChromosome) chromosome2;

            var splitLocation = random.Next(0, numberChromosome1.VectorSize + 1);
            var newVector = new int[numberChromosome1.VectorSize];
            for (int i = 0; i < numberChromosome1.VectorSize; i++)
                newVector[i] = i < splitLocation ? numberChromosome1[i] : numberChromosome2[i];

            return new NumberVectorChromosome(newVector);
        }
    }

Running the Search

Now that everything's ready, lets run an actual search.

// Create the engine
var searchEngine = new GeneticSearchEngineBuilder(POPULATION_SIZE, MAX_GENERATIONS, new NumberVectorCrossoverManager(),
      new NumberVectorPopulationGenerator()).SetMutationProbability(0.1).Build();

// Run the search
var result = searchEngine.Run();