-
Graphinder series articles
- Graphinder – Project Introduction
- Graphinder – I don’t need this covered…
- Graphinder – Minimum Vertex Cover problem
- Graphinder – Simulated Annealing algorithm
- Graphinder – Code review yourself
- Graphinder – Genetic Algorithm – Introduction
- Graphinder – Genetic Algorithm – Selection
- Graphinder – Genetic Algorithm – Crossover
- Graphinder – Genetic Algorithm – Mutation
- Graphinder – Genetic Algorithm – Wrap up
- Graphinder – Monthly Progress Report – March
- Graphinder – Async IEnumerable with Rx.Net and IObservable
- Graphinder – Reporting progress with Rx.Net
- Graphinder – TDD and starting from red
- Graphinder – Domain models vs Persistence models
- Graphinder – Queries and Commands vs Repository pattern
- Graphinder – Encapsulating persistence layer
- Graphinder – Solution changes and nuget hell
- Graphinder – Monthly Progress Report – April
- Graphinder – Application architecture
- Graphinder – Resources planning on Azure
- Graphinder – Quick summary and what next
- Quick thoughts after Daj Sie Poznac 2016 finals
Straight to Genetic Algorithm wrap up
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
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:
1 2 3 4 5 6 |
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
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: