-
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
Crossover
on them until new generation is bred (humans, swans etc.) - We can choose new couple for each
Crossover
and end up withIndividual
being parent with more than one otherIndividual
(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:
1 2 3 4 5 6 |
public interface ISelectionStrategy { Individual Next(); Tuple<Individual, Individual> NextCouple(); void Set(ICollection<Individual> newPopulation); } |
Quick note on TupleIndividualCouple
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…
Implementation
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
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(); InitializeRoulette(); } |
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 Graph
.
Then, if provided population is not a SortedSet
(we might want to check for SortedList
here too), let’s sort and assign it.
Finally, let InitializeRoulette()
do the rest of job, that is mapping.
As for the mapping:
1 2 3 4 5 6 7 8 9 10 11 12 |
private void InitializeRoulette() { _individualsWeight.Clear(); 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!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
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; } return previous; } |
Let’s iterate through entire population looking for first Individual
, which values is greater than rolled random value. That’s our pick.
As for 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:
Algorithms/GeneticAlgorithm/SelectionStrategies/ @ GitHub.com