• 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 mutation strategies

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:

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:

Algorithms/GeneticAlgorithm/MutationStrategies/ @ GitHub.com