Graphinder – Genetic Algorithm – Selection


About Genetic algorithm selection strategies

Genetic Algorithm Selection

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:

Genetic Algorithm Selection - Roulette Wheel


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:

Leave a Reply

Your email address will not be published. Required fields are marked *