Simple genetic algorithm

Today I took a few minutes to do a simple little genetic algorithm that works toward a given statement. This is a fairly simple concept where the program randomly reassigns the value of a random set of indexes repeatedly until the goal is met. I first started with a simple non-directed algorithm where a string is constructed by indiscriminately and randomly reassigning a set of indexes in the hopes that it would eventually reach the goal statement. Well needless to say this worked wonderfully, with the exception that it took forever(I let it run for about 2 hours before becoming impatient). I didn't much feel like waiting for possibly days to see if it would even come close. So I decided to add direction. to do this I simply added a check to see if the current state in any way matched the goal state and if so, the indexes of the 2 strings that matched wouldn't be altered. The result of doing this was instead of it taking more than the 2 hours, the algorithm would instead finish within a few seconds.

What is a genetic algorithm:

A genetic algorithm is based on the concept of evolutionary biology where a sequence is randomly mutated, either for better or worse. For example let's say that you have a binary string of 0's and 1's like so:

1010001010011101

you will randomly pick a number of indexes within the string to be flipped. So let's say that we only want to mutate a single value, we select a random index between 0 and 15 for this string and mutate it. In this scenario mutating is going to be defined as randomly selecting a random value to reassign that index to. Since we are working with binary, the available set of values for mutation is {0, 1}. So let's say we randomly choose index 3 and when we randomly select a value to replace it with we get a 1. When we do this the original string of

1010001010011101 -> 1011001010011101

As I said earlier, this method on its own lacks direction and it may take literally forever to reach your goal state. So to make the path a little shorter, you can check the current state against the goal and see if the index you have randomly chosen to modify matches the same index within your goal state and if so then you don't make any changes. This is a bit of a short cut way of saying that you already know that switching the given index will result in a state that is further from the goal state than the current state, thus behaving something like a tree pruning algorithm. This was a fun little exercise for me to do, and I hope you enjoy it too. You can find the code here.