Genetic Algorithms Tutorial - Part I

 "Survival of the fittest." - Charles Darwin

We have been hearing since childhood that we have evolved from the apes. "What is evolution?", we then ask and we are told that it is the gradual development of species. But we aren't geneticists, we are programmers and we try to code whatever we see around us. Today we will code a genetic algorithm. 

Genetic algorithms are usually used when you want 'a' to evolve it into 'b'. We will basically mimic evolution. These type of algorithms can very handy in solving some problems. Today we will solve the problem of reaching the desired output 'Original Coding Cult' from a randomized string. The algorithm is broken into four part: Seed, Weed, Breed, Mutate and Repeat.

Seed

In this step we randomly generate anything. For this project we need to generate a random string of characters. Lets call this 'parent'. In some cases we seed a bunch of parents, but for our convenience we will only seed one parent.

Weed

We have our desired output 'Original Coding Cult' and we have a random string parent. In this step we need to weed out the "weak" parents. How do we it? We find out their 'fitness'. The fitness function varies and depends on the problem you are addressing. In our case, the fitness function can find the number of similarities between the parent and our desired output. Only those will proceed to the next step, if they have a higher fitness than their predecessor.

Breed

We will be skipping this step because we have only one parent. But essentially, in this step we breed two children to get their child.

Mutate

Now we take the child and mutate it. In our case we will mutate it by randomly changing a character in the child. Higher mutation rates can lead to never reaching the desired output only. Therefore, we must always wisely chose the mutation rate.

Repeat

Now we repeat the process, exclusive of the first step. We take the children, weed out the weaklings, mutate them, breed them and mutate their children. And when we will reach our desired output we stop the algorithm.

If we run our algorithm, our output would be something like this. 

lEdZ3BOAbVlNmSWkquCH    1      
lEdZ3nOAbVlNmSWkquCH    2     
lEdZ3nOAbVlNmSWkquCt    3   
lEdZ3nOlbVlNmSWkquCt    4       
lEdZinOlbVlNmSWkquCt    5       
lEdZinOlbVldmSWkquCt    6       
lEiZinOlbVldmSWkquCt    7    
lEiZinOlbVldmnWkquCt    8       
lEiZinOlbVldmnWkCuCt    9       
lEiZinOlbVldmnW CuCt    10     
lEiZinOlbCldmnW CuCt    11   
lEiZinOlbCldinW CuCt    12    
lEiZinOlbCldinW Cult    13    
lEiZinOlbCodinW Cult    14   
OEiZinOlbCodinW Cult    15   
OEiZinOlbCoding Cult    16  
OEiZinOl Coding Cult    17    
OEiginOl Coding Cult    18   
OriginOl Coding Cult    19    
Original Coding Cult    20     

(Please forgive me for the weird formatting of the code)

Viola! Genetic Algorithm. In my next blog, I will explore on coding this algorithm. Till then, bye!!