-
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:
1 2 3 4 |
public interface IMutationStrategy { void Mutate(Individual individual); } |
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:
1 2 3 4 5 6 7 8 |
private Action<bool[]> _binaryTransformation; public void Mutate(Individual individual) { if (individual == null) throw new ArgumentException(nameof(individual)); _binaryTransformation(individual.CurrentSolution); } |
And our Action
delegate will end up looking like this:
1 2 3 4 5 |
public void RandomBitFlip(bool[] array) { var randomIndex = _random.Next(array.Length); array[randomIndex] = !array[randomIndex]; } |
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
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.
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! ;)
Ah see, I ‘ve missed a statement about mutation probability, my bad :)
Anyway – to much coffee? ^^