Graphinder – Genetic Algorithm – Wrap up

Straight to Genetic Algorithm wrap up

Genetic Algorithm Selection

So we’re past Selection, Crossover and Mutation strategies. We came up with idea of how to encode a single Individual of our algorithm’s population. We have every piece needed to search for solution to our problem, so let’s move on to wrapping things up!
First of all, quick reminder of how our algorithm will search for solution:

  • When building our Genetic Algorithm, we decide on how many generations of Individuals it will breed
  • Our algorithm will for each generation proceed with process of breeding new population from current one
  • Process will start with selecting couple of Individuals to perform crossover, ie. breed new offspring
  • Based on probability* chosen for algorithm, couple will either crossover and produce an offspring or not
  • If crossover produced offspring, we will decide whether to mutate its solution or not, based on chosen probability**
  • If crossover produced offspring, no matter if we mutated it or not, we will add it up to new population
  • We will keep on repeating the above parts until new generation is born with same amount of Individuals***
  • On new generation born, we will select Individual with best solution and use it as our current solution to a problem
  • Finally, we will keep on repeating the whole process of breeding new generations, until we meet the last generation criteria

*As noted by Patryk from sometimes designers decide to always crossover couples
**Most Genetic Algorithms use probability of mutation to avoid total randomness
***Sometimes designers decide to breed population of smaller size than before, for example 90% of previous generation, not 100%

So – in general – we’ve added probabilities for both Crossover and Mutation strategies to reduce randomness from one side but to still keep some entropy on board.
If those few points are still uncertain for you, you can still go back to my previous post Genetic Algorithm – Introduction where I’ve provided an easy flow chart to follow.

Pieces put together

Alright, so let’s put all of the pieces together.
I’ve went with pretty easy to understand, close-to-natural naming conventions, so I hope you understand everything, provided comments are also there.

It’s worth noting that I’ve decided to move from HashSet to SortedSet, so I’ve made Individual implement IComparable interface as its a must for properly working SortedSet.
For quick info about the changes, please take a look on current state of Individual.cs on Github:

Room for improvement?

Alright. So we have our genetic algorithm wrap up running, looking for possible solution to our problem.
Can we do anything to improve how it works though?
Of course we can! The most popular way of doing so is through so called Elitist Selection.
Easiest way to describe it, is to imagine a situation, when strongest or the most intelligent humans can somehow have their life extended beyond normal lifespan.
Easy? In real life: not easy. In Genetic Algorithm: a no-brainer.

Let’s take a look on how we could implement it:

Provided we already have a SortedSet, its boringly easy. We just Reverse() the order of our set and Take first N Individuals from current population, where N is how many elite survivors there should be – a value set up when building settings for Genetic Algorithm.

Now, let’s edit our SearchForSolution() method a little:

Now we’ll have the best individuals of population to live up to next generation.
Will they live up for long? It depends how good their solution is compared to future generations.

Full code for everything related to – currently wannabe completed – topic of Genetic Algorithm can be found here:

Leave a Reply

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