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
About Genetic algorithm selection strategies
Previously we’ve been talking about general concept of Genetic Algorithm. First part in breeding new generation for every Genetic Algorithm starts with
Selection of individuals chosen for further
Crossover. While there are at least three popular strategies to select couples from population, I’ve used so called Roulette Wheel Selection for my case.
Please note, that also for particular Genetic Algorithm selection strategy there might be at least two ways of choosing couples:
- We can choose fixed couples and perform
Crossoveron them until new generation is bred (humans, swans etc.)
- We can choose new couple for each
Crossoverand end up with
Individualbeing parent with more than one other
Individual(Alpha approach seen in many species)
I’ve gone with second approach as it fitted my scenario better.
Selection strategy contract
Let’s think of what contract
ISelectionStrategy should fullfil.
Generally we would like to to provide our population and receive a couple of individuals for further genetic operations.
For each generation of algorithm we would like to
Set population from which Individual will be select. Then, we’d like to ask for
NextCouple or just call for
Next and build couple ourselves.
Provided such requirements, our Genetic Algorithm Selection strategy contract would look like this:
public interface ISelectionStrategy
Tuple<Individual, Individual> NextCouple();
void Set(ICollection<Individual> newPopulation);
Quick note on Tuple
IndividualCouple class) and that’s a thing I’m taking into consideration but it will stay as
Touple for now.
Roulette Wheel Selection strategy
Roulette Wheel selection strategy – as its name states – uses algorithm resembling roulette game.
First of all, we need to order population that was set. Then, from every
Individual provided to strategy we count what percentage it makes of total fitness of whole provided population. Finally, we map it to what range from 0.0 to 1.0 it occupies, based on its percentage.
Reminder: Fitness defines how good solution is. The bigger, the better!
Let’s take a look at simple, 3-Individual population:
Now, let’s roll good old
Random.NextDouble() and think of possible outcomes.
Let’s say we rolled 0.14 – we would pick first
Individual as a result.
Let’s say we rolled 0.77 – we would pick third
Individual as a result.
And so on…
Finally, going to implementation, we would need to provide three mechanics:
- Validating and setting incoming population
- Mapping it to its percentage share based on fitness
- Selecting new random individual
Let’s look on how we
Set a new population for our Genetic Algorithm selection:
public void Set(ICollection<Individual> newPopulation)
if (newPopulation == null)
throw new ArgumentException(nameof(newPopulation));
if (newPopulation.Count == 0)
throw new InvalidOperationException("Attempt to set empty population");
var problem = newPopulation.First().Problem;
var graph = newPopulation.First().Graph;
if (newPopulation.Any(i => i.Graph != graph || i.Problem != problem))
throw new AlgorithmException("Setting up new population", "Individuals in population represent either different graphs or different problems");
_population = newPopulation;
//In case is not SortedSet<T>
if (!(_population is SortedSet<Individual>))
_population = _population.OrderBy(p => p.SolutionFitness).ToList();
Nothing special here, right?
Basic check for invalid population provided to selection strategy, then checking if every individual in provided population represents same
Problem working on same
Then, if provided population is not a
SortedSet (we might want to check for
SortedList here too), let’s sort and assign it.
InitializeRoulette() do the rest of job, that is mapping.
As for the mapping:
private void InitializeRoulette()
var populationSum = _population.Sum(p => p.SolutionFitness);
var probabilitiesSum = 0d;
foreach (var element in _population)
var probability = (double)element.SolutionFitness / populationSum;
_individualsWeight.Add(element, probabilitiesSum + probability);
probabilitiesSum += probability;
As previously mentioned, our steps are:
- Sum whole population fitness
- Calculate what percentage of total fitness individual’s solution makes
- Map it with Individual as Key, probability range as Value (we could go the other way round with reasonable precision of probability)
Finally, we would like to roll for a random Individual!
public Individual Next()
if (_population == null || _population.Count == 0)
throw new InvalidOperationException("Selection strategy needs to have population set first!");
var randomWeight = _random.NextDouble();
Individual previous = null;
foreach (var element in _individualsWeight)
if (element.Value > randomWeight)
return previous ?? element.Key;
previous = element.Key;
Let’s iterate through entire population looking for first
Individual, which values is greater than rolled random value. That’s our pick.
NextCouple, I’ve decided to skip it as it’s simple
Touple creation from two rolled
Individuals and duplicate check.
As per every article for Graphinder Project, entire source code can be found on GitHub: