Graphinder – Genetic Algorithm – Introduction

About Genetic algorithm

Genetic Algorithm

Genetic algorithm – as opposed to Simulated Annealing – is more universal algorithm intending to solve a much more wider range of problems than more specialized optimization algorithms. As the name states, this particular algorithm uses behavior very similar to how natural selection works in nature. Algorithm starts with basic population of individuals, each holding a solution to problem we’re aiming to solve, that will breed an offspring for next generation. The whole process continues until certain number of generation passed or until the solution is not improving at all.
As Genetic algorithm is a little more complex concept than Simulated Annealing, I’ve decided to divide it into separated articles to preserve readability and make sure that I’ve elaborated well enough on every each of them.

Process for each generation

Each generation is generated from previous one by:

  • Selecting couples for reproduction aka Crossing
  • If probability of Crossing is high, a new Individual for population is bred
  • If probability of Mutation is high, new Individual is mutated before adding to new population
  • Process repeats until new population is born and matches the size of previous one
  • Another generation proceeds provided it’s not the last generation for algorithm

To better understand the whole process I’ve prepared diagram on how it actually looks like:

Genetic Algorithm - process

Of course Genetic algorithm has several variations for each genetic operator. It can select individuals with different strategy, it may pick them once as couple or keep on rolling for new ones every time. It can also perform crossover in many different ways and can mutate solution that Individual holds with various strategies. To better understand that, we’ll talk more in depth about those strategies in next article.

Individual of population

We’ve been talking a lot about so called Individual and it would be a sin not to elaborate on what it is and how it’s used in GA.
An Individual is very atomic part of Genetic algorithm and its population. Every Individual holds a Solution to a Problem. What’s different from our previous algorithm is that solution here is always encoded (in this particular case in Binary (0 or 1)) and knows nothing about what it really represents. The only way to know if solution is correct is through Problem it attempts to solve.

One more thing that is characteristic for Genetic algorithm (but can be used for others, like Simulated Annealing) is SolutionFitness.
Its main role is to decide how highly we rank certain solution. The bigger fitness, the better (rarely opposite criteria are used).
You probably spotted it right – actually SolutionFitness should belong to IProblem instead and it’s on the top of my TODOs list now! I wanted to show the current state of code tough, so well… shame, shame.. ;)

Article wouldn’t be complete without describing how solution has been actually encoded. As I’ve mentioned before, Individual currently holds solution encoded binary.

For every node chosen from graph, let’s mark it as:

  • 0 – if we didn’t choose N-th node from graph
  • 1 – if we chose N-th node from graph

Let’s see how example solution would be encoded with below graphical representation:

Genetic Algorithm - process

And that’s it for today. In next article we’ll talk about our SelectionStrategy.
Code for discussed part is as always located on Github:

3 thoughts on “Graphinder – Genetic Algorithm – Introduction”

  1. In in opinion it is worth to consider elitism. That idea allows selected best organism from current generation to carry over next, unaltered. My benchmarks in project knapsackproblem shows you should give a try!

  2. Elitism is already implemented in my GA. I’ve not mentioned it in introduction, because it is not the most crucial and necessary part of GA. What’s more, if you look up closely on a Trello board of a project, ie. Graphinder – Trello, you’ll see that it’s also on a Bug Report list due to some unexpected outcomes on how sometimes it works. :)

Leave a Reply

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