• Github
  • https://github.com/m-wilczynski/Localwire.Graphinder
• 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 with Individual being 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:

Quick note on Tuple usage here. I know that many OOP hardcore evangelists would call for a complex attribute here (possibly a 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…

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:

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:

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!

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