Creating a Custom PopulationRenwalManager

It's well known that Genetic Algorithms tend to convergence. One way of dealing with this is by renewing a percentage of the population. This is what PopulationRenwalManagers are for.

In this tutorial, we'll create a PopulationRenwalManager that will renew some of the population when the improvement over X generations is smaller than Y. (For example, if the improvement over 3 generations is less then one).

Creating a Skeleton Class

Let's start be creating a skeleton class that implements the IPopulationRenwalManager interface. We'll call our class RenewIfNoImprovment.

    class RenewIfNoImprovment : IPopulationRenwalManager
    {
        public double ShouldRenew(Population population, IEnvironment environment, int generation)
        {
            throw new NotImplementedException();
        }

        public void AddGeneration(Population population)
        {
            throw new NotImplementedException();
        }
    }

MinImprovment, Generations and PrecentageToRenew Values

Let's give the user the ability to determine the precentageToRenew, minImprovment and generationsToConsider values (that is, the values that if the improvement over "generationsToConsider" generations is less then "minImprovment", we'll terminate the search). We'll let the user provide these parameters in the constructor.

        private readonly int generationsToConsider;
        private readonly double minImprovment;
        private readonly double precentageToRenew;

        public RenewIfNoImprovment(int generationsToConsider, double minImprovment, double precentageToRenew)
        {
            this.generationsToConsider = generationsToConsider;
            this.minImprovment = minImprovment;
            this.precentageToRenew = precentageToRenew;
        }

Implementing the AddGeneration Method

For this to work, we'll need to remember the best evaluation from previous generations. We'll do this by implementing the AddGenertion method. AddGenertion is called once per generation (after the ShouldRenew method for that generation). It lets the PopulationRenwalManager collect information about previous generations.

In this implementation, I'm going to remember all historical data (even though - technically - it's enough to only remember "generationsToConsider" generations back).

        private readonly List<double> oldEvaluations = new List<double>();

        public void AddGeneration(Population population)
        {
            oldEvaluations.Add(population.GetEvaluations().Max());
        }

Implementing the ShouldRenew Method

Finally, let's implement the ShouldRenew method. The method will return the percentage of the population to renew (0, if we should renew nothing).

        public double ShouldRenew(Population population, IEnvironment environment, int generation)
        {
            var currentEvaluation = population.GetEvaluations().Max();
            if (generation < generationsToConsider)
                return 0;
            
            var min = oldEvaluations.Skip(generation - generationsToConsider).Take(generationsToConsider).Min();

            return Math.Abs(currentEvaluation - min) <= minImprovment ? precentageToRenew : 0;
        }

The Full Code

    class RenewIfNoImprovment : IPopulationRenwalManager
    {
        private readonly int generationsToConsider;
        private readonly double minImprovment;
        private readonly double precentageToRenew;

        public RenewIfNoImprovment(int generationsToConsider, double minImprovment, double precentageToRenew)
        {
            this.generationsToConsider = generationsToConsider;
            this.minImprovment = minImprovment;
            this.precentageToRenew = precentageToRenew;
        }

        public double ShouldRenew(Population population, IEnvironment environment, int generation)
        {
            var currentEvaluation = population.GetEvaluations().Max();
            if (generation < generationsToConsider)
                return 0;

            var min = oldEvaluations.Skip(generation - generationsToConsider).Take(generationsToConsider).Min();

            return Math.Abs(currentEvaluation - min) <= minImprovment ? precentageToRenew : 0;
        }

        private readonly List<double> oldEvaluations = new List<double>();

        public void AddGeneration(Population population)
        {
            oldEvaluations.Add(population.GetEvaluations().Max());
        }
    }