Graphinder – Genetic Algorithm – Wrap up

Straight to Genetic Algorithm wrap up

Genetic Algorithm Selection

So we’re past Selection, Crossover and Mutation strategies. We came up with idea of how to encode a single Individual of our algorithm’s population. We have every piece needed to search for solution to our problem, so let’s move on to wrapping things up!
First of all, quick reminder of how our algorithm will search for solution:

When building our Genetic Algorithm, we decide on how many generations of Individuals it will breed
Our algorithm will for each generation proceed with process of breeding new population from current one
Process will start with selecting couple of Individuals to perform crossover, ie. breed new offspring
Based on probability* chosen for algorithm, couple will either crossover and produce an offspring or not
If crossover produced offspring, we will decide whether to mutate its solution or not, based on chosen probability**
If crossover produced offspring, no matter if we mutated it or not, we will add it up to new population
We will keep on repeating the above parts until new generation is born with same amount of Individuals***
On new generation born, we will select Individual with best solution and use it as our current solution to a problem
Finally, we will keep on repeating the whole process of breeding new generations, until we meet the last generation criteria

*As noted by Patryk from http://pewudev.pl/ sometimes designers decide to always crossover couples
**Most Genetic Algorithms use probability of mutation to avoid total randomness
***Sometimes designers decide to breed population of smaller size than before, for example 90% of previous generation, not 100%

So – in general – we’ve added probabilities for both Crossover and Mutation strategies to reduce randomness from one side but to still keep some entropy on board.
If those few points are still uncertain for you, you can still go back to my previous post Genetic Algorithm – Introduction where I’ve provided an easy flow chart to follow.

Pieces put together

Alright, so let’s put all of the pieces together.
I’ve went with pretty easy to understand, close-to-natural naming conventions, so I hope you understand everything, provided comments are also there.

protected override void SearchForSolution()
{
    RestartSystem();

    var startTime = DateTime.Now.Ticks;

    //Look for solution until it reaches last generation
    while (CanContinueSearching())
    {
        SortedSet<Individual> newGeneration = new SortedSet<Individual>();
        SortedSet<Individual> populationToMutate = new SortedSet<Individual>(CurrentPopulation);

        //Refresh generation in selection strategy with actual one
        GeneticOperators.SelectionStrategy.Set(populationToMutate);

        //Build new generation of size of previous one
        while (newGeneration.Count < CurrentPopulation.Count)
        {
            //Choose couple for crossover
            var couple = GeneticOperators.SelectionStrategy.NextCouple();

            //Should crossover?
            Individual newIndividual = null;
            if (_random.NextDouble() < Settings.CrossoverProbability)
                //Crossover!
                newIndividual = GeneticOperators.CrossoverStrategy.PerformCrossover(couple.Item1, couple.Item2);
            else
                continue;

            //Should mutate?
            if (_random.NextDouble() < Settings.MutationProbability)
                //Mutate!
                GeneticOperators.MutationStrategy.Mutate(newIndividual);

            if (newIndividual != null)
                newGeneration.Add(newIndividual);
        }
        
        CurrentGeneration++;
        //Swap generation to new one
        CurrentPopulation = newGeneration;
        
        //Pick best individual from current solution and if it can be accepted, set its solution as new one
        var solutionAsNodes = BestIndividualSolution();
        if (CanAcceptAnswer(solutionAsNodes))
            Problem.SetNewSolution(solutionAsNodes);

    }
    _processorTimeCost = DateTime.Now.Ticks - startTime;
}

protected override void SearchForSolution()

{

RestartSystem();

var startTime = DateTime.Now.Ticks;

//Look for solution until it reaches last generation

while (CanContinueSearching())

{

SortedSet<Individual> newGeneration = new SortedSet<Individual>();

SortedSet<Individual> populationToMutate = new SortedSet<Individual>(CurrentPopulation);

//Refresh generation in selection strategy with actual one

GeneticOperators.SelectionStrategy.Set(populationToMutate);

//Build new generation of size of previous one

while (newGeneration.Count < CurrentPopulation.Count)

{

//Choose couple for crossover

var couple = GeneticOperators.SelectionStrategy.NextCouple();

//Should crossover?

Individual newIndividual = null;

if (_random.NextDouble() < Settings.CrossoverProbability)

//Crossover!

newIndividual = GeneticOperators.CrossoverStrategy.PerformCrossover(couple.Item1, couple.Item2);

else

continue;

//Should mutate?

if (_random.NextDouble() < Settings.MutationProbability)

//Mutate!

GeneticOperators.MutationStrategy.Mutate(newIndividual);

if (newIndividual != null)

newGeneration.Add(newIndividual);

}

CurrentGeneration++;

//Swap generation to new one

CurrentPopulation = newGeneration;

//Pick best individual from current solution and if it can be accepted, set its solution as new one

var solutionAsNodes = BestIndividualSolution();

if (CanAcceptAnswer(solutionAsNodes))

Problem.SetNewSolution(solutionAsNodes);

}

_processorTimeCost = DateTime.Now.Ticks - startTime;

}

It’s worth noting that I’ve decided to move from HashSet to SortedSet, so I’ve made Individual implement IComparable interface as its a must for properly working SortedSet.
For quick info about the changes, please take a look on current state of Individual.cs on Github:

Algorithms/GeneticAlgorithm/Individual.cs @ GitHub.com

Room for improvement?

Alright. So we have our genetic algorithm wrap up running, looking for possible solution to our problem.
Can we do anything to improve how it works though?
Of course we can! The most popular way of doing so is through so called Elitist Selection.
Easiest way to describe it, is to imagine a situation, when strongest or the most intelligent humans can somehow have their life extended beyond normal lifespan.
Easy? In real life: not easy. In Genetic Algorithm: a no-brainer.

Let’s take a look on how we could implement it:

private ICollection<Individual> ElitistSelection()
{
    if (!Settings.WithElitistSelection) return null;
    if (Settings.EliteSurvivors > int.MaxValue) return null;
    return CurrentPopulation.Reverse().Take((int)Settings.EliteSurvivors).ToList();
}

private ICollection<Individual> ElitistSelection()

{

if (!Settings.WithElitistSelection) return null;

if (Settings.EliteSurvivors > int.MaxValue) return null;

return CurrentPopulation.Reverse().Take((int)Settings.EliteSurvivors).ToList();

}

Provided we already have a SortedSet, its boringly easy. We just Reverse() the order of our set and Take first N Individuals from current population, where N is how many elite survivors there should be – a value set up when building settings for Genetic Algorithm.

Now, let’s edit our SearchForSolution() method a little:

protected override void SearchForSolution()
{
    //(...)

    //Look for solution until it reaches last generation
    while (CanContinueSearching())
    {
        SortedSet<Individual> newGeneration = new SortedSet<Individual>();
        SortedSet<Individual> populationToMutate = new SortedSet<Individual>(CurrentPopulation);

        //Elitist selection
        var elite = ElitistSelection();
        if (elite != null)
        {
            foreach (var element in elite)
            {
                newGeneration.Add(element);
                populationToMutate.Remove(element);
            }
        }


        //Refresh generation in selection strategy with actual one
        GeneticOperators.SelectionStrategy.Set(populationToMutate);

        //(...)
}

protected override void SearchForSolution()

{

//(...)

//Look for solution until it reaches last generation

while (CanContinueSearching())

{

SortedSet<Individual> newGeneration = new SortedSet<Individual>();

SortedSet<Individual> populationToMutate = new SortedSet<Individual>(CurrentPopulation);

//Elitist selection

var elite = ElitistSelection();

if (elite != null)

{

foreach (var element in elite)

{

newGeneration.Add(element);

populationToMutate.Remove(element);

}

//Refresh generation in selection strategy with actual one

GeneticOperators.SelectionStrategy.Set(populationToMutate);

//(...)

}

Now we’ll have the best individuals of population to live up to next generation.
Will they live up for long? It depends how good their solution is compared to future generations.

Full code for everything related to – currently wannabe completed – topic of Genetic Algorithm can be found here:

Algorithms/GeneticAlgorithm @ GitHub.com

Michał Wilczyński

Straight to Genetic Algorithm wrap up

Pieces put together

Room for improvement?

Leave a Reply Cancel reply