Graphinder – Genetic Algorithm – Mutation


About Genetic algorithm mutation strategies

Genetic Algorithm Selection

Last but not least part in our poor little jigsaw of creating Genetic Algorithm is a way to transform newly bred individual’s solution.
Well… first thought would be – why on earth would I transform somehow a new solution I’ve got? Indeed, new solution is already made up of two different ones, therefore it adds some diversity to our new generation.
But, sometimes it’s not enough. Sometimes we need to make a one step further and transform, ie. mutate achieved solution, to make sure we our coverage of possible solution is wider (or at least different) from previous generation of individuals.
Of course, we would like to not go so far with it so that our Genetic Algorithm Mutation won’t mutate every damn thing we breed.
That’s why in every Genetic Algorithm implementation, there is a certain probability of mutation occurrence, to make sure it gives us some diversity but nor total randomness.

Mutation strategy contract

I really don’t want to bore to death any of you, my outnumbered yet faithful readers, but as always, we will start with defining a contract. I might be a little too into Design By Contract but it makes prefect sense when you want to stay SOLID and keep operating on abstractions instead of final implementations.
Now, back to business! As we mentioned few sentences before, what we would like to achieve is to take newly bred Individual and Mutate it. That leaves us with very minimal contract, but that’s fine as it defines everything we want it to be:

Binary Transformation Mutation strategy

Alright, so we already know that our strategy needs to somehow transform solution provided by Individual. As current implementation of Individual offers us only a binary encoded solution, I’ve decided to go with simple implementation that would offer ways of flipping bit (or bits) inside of it. Generally, process would look – for each mutation attempt – like this:

Genetic Algorithm Mutation - Bit Flip

Of course we might think of flipping more than one bit, flip bits in certain pattern and so on. That might generate too random outcomes though, as average Genetic Algorithm Mutation occurs once per 3-4 bred Individuals, not to count that not every chosen couple will end up having an offspring. Having situation that occurs quite rarely and suddenly changes solutions drastically would make the process much less predictable.

Implementation

Since our solution is a simple bool[], all we need to do is take it, roll for a random element index and then just iterate until we reach our chosen index. Then, we just flip the bool value, ie. bit = !bit and that’s it.
For my current implementation, I’m using simple Action delegate and factory, that will produce appropriate delegate on demand.
Mutate will end up being a simple invoker like this:

And our Action delegate will end up looking like this:

That’s complete implementation for our Genetic Algorithm Mutation, or at least the very essence of it.
Provided we have Selection, Crossover and Mutation strategies in place, we can finally move on to wrapping everything up for complete genetic algorithm. In next article, besides having everything wrapped up, we’ll also think of simple ways of improving our implementation, with – for example – Elitist Selection.

For everything discussed today, take a look at GitHub repository below:

3 thoughts on “Graphinder – Genetic Algorithm – Mutation”

  1. Mr Michal…

    Where is KISS? :)

    Simpler, right? :)

    And.. should mutation occur always? Did you consider a test (f.e 50/50) wheter mutation should occur or not? I think that in real life mutation is not obligatory.

    1. Aaaaaaaaaaa, shame on meeee! You are of course right, refactoring right away!
      As for mutation probability, it is decided on GeneticAlgorithm level, whether it will mutate or not.
      That’s probably questionable choice and I’ve been thinking this over recently, but for now it will stay as it is.
      Thanks for pointing out my wall of shame! ;)

Leave a Reply

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