Graphinder – Genetic Algorithm – Crossover


About Genetic algorithm crossover strategies

Genetic Algorithm Selection

Second part for breeding a new individual for upcoming generation is to perform Crossover. Let’s think of it as a simple reproduction process, when couple of Individuals give birth to their offspring. As other genetic operators, we can easily see an attempt to mimic nature here. General idea of Crossover will be to take genetic material (ie. CurrentSolution) and cut it into pieces that will then be connected into new solution, that offspring will hold.
Same as in Selection case, Genetic Algorithm Crossover offers multiple strategies on how new Individual can be bred.
For Graphinder project I’ve decided to go for simple, One Point Crossover. It means that provided we have two parents of new child, we will take solutions they hold, split them in one, exact same point, for example halfway, and then connect outcomes into new solution.
Other interesting strategies are Uniform Crossover and Half Uniform Crossover. Provided we have solution of greater length, they can offer greater diversity of produced solutions.

Crossover strategy contract

As always, we’ll try to think of contract that Genetic Algorithm Crossover strategy should fullfill.
Generally, there are two things needed for performing crossover. We need couple, that will be parents for PerformCrossover and – possibly – CrossoverPointIndex chosen once for entire Genetic Algorithm lifetime.

Let’s take a look on our short contract:

No rocket science here, right? Let’s move on then!

One Point Crossover strategy

Few sentences up, I’ve mentioned that we’ll use the most simple crossover strategy possible: One Point Crossover.
Idea is quite easy to understand, if you recall how actually our Individual and its solution look like. That’s right: it’s chain of 0s and 1s, because we encoded it binary. If you think of connecting part of one chain and part of other chain, what would you do if you want to preserve the length?
You cut them both in same point and then – connect outcomes. Let’s see how would it look like in our case:

Genetic Algorithm Crossover - One Point

We can choose any point of crossover provided we choose it once and for all future crossovers. Obvious thought here is to do so in .ctor. Speaking of the devil, let’s move on to implementation.

Implementation

Let’s start with choosing our CrossoverPointIndex. It should be random and chosen once, yet we should think of some boundaries for it. I’ve decided to make them constant for any instance of OnePointCrossoverStrategy. You might think of going other way round and that’s fine. Just besides thinking, make sure to also try it out! :)

Alright. We have crossover point for every crossover to come. Straight to performing crossover then!

There’s a lot of crap-out checking before actual crossover. Then, we just take bits from left parent’s solution until we reach the point of crossover. Next, we take bits from the right parent’s solution that occurr after point of crossover.
Finally, we take newly created solution encoded binary and we create new Individual with brand new solution to provide.

As always, everything you need to know, find, check and blame is located on GitHub. Down below:

6 thoughts on “Graphinder – Genetic Algorithm – Crossover”

  1. There is an Assert class in C#. Code is cleaner after you delete all that nasty if’s and use onliners. Or you can provide Assert’s by your own, like:
    func AssertAlgorithm(bool element, string message)
    {
    if !(element) throw new AlgorithmException(message);
    }
    Great job by the way :)

      1. Problem with CuttingEdge.Conditions is that it needs to extend further if I want to either use my own Exception or pass some particular params to Exception.
        Tbh I’m not kind of a guy to throw empty Exception around but I’d rather go with some message instead. :)
        Great thing about CuttingEdge.Conditions and Microsoft’s CodeContracts is their ability to easily check both pre- and post- conditions.
        Another great thing is static code analysis that can be useful but not error-proof. Also it can produce wall-of-warnings. :)
        In the end, neither Conditions, nor CodeContracts bought me in. If I were to choose, I would choose CodeContracts because they’re part of .NET 4.0.

  2. – that condition makes no sense – it is always true.. why? Try figure out!

Leave a Reply

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