Genetic Algorithms — I

Chirag Sharma
Aug 9 · 6 min read
Photo by Gabriel Peter from Pexels

I never knew how strong I was until I had to do biology to make my programming better. I thought that programming was a single discipline with mathematics staring at me with disgusting grim on it’s face. Mathematics is one of the noble pursuit but as you mature up in a field you began to realize all other fields are quite informative and really running the world. Biology for once I never thought would be implementable in the field of mathematics but boy was I wrong! Right now I am going crazy over the in depth analysis of Genetic Algorithms as I never thought they had so much mathematical significance in them.

So let’s begin the ride for today! I promise you that this one is going to be interesting and you promise me If you develop something over it you will let me know because there is nothing more fun than watching someone create something fabulous.

What’s the fuss about?

Machine Learning, Artificial Intelligence and other fields of study where we are creating the human vs robot debate is being charged to full extent by usage of algorithms and patterns that exist among the nature and yes you guessed it right! Genetic Algorithms are part of this whole circus for which everyone wants ticket to.

Famous Usage of Genetic Algorithms:

Let’s start, shall we?

  • Importing all the necessary libraries and fixing the amount of individuals I will keep at max in any generation i.e 100:
  • For this whole session my target would be to achieve the final goal as PYTHON but with a little bit of twist -> Achieve PYTHON’s binary equivalent combination i.e. ‘1010000 1011001 1010100 1001000 1001111 1001110’.
  • GENES: Possible Set of Achievable Points. In this case only 0 1 and “ “ are achievable so I am using them otherwise you can add others as a noise to balance out the early convergence (will talk about this term later).
  • Keep this in mind. TARGET = ‘1010000 1011001 1010100 1001000 1001111 1001110’
  • Chromosome Function : Creates an individual from the genes provided. Here they are only three : 0,1,’ ‘.
  • Mutation Function : Function with a twist. It helps to prevent early convergence(will talk about this later for love of god believe me!). This is like as I have explained before in my previous article that it helps to abruptly break the stupidity out of the children(bad genes) and can be harmful to break the great sensible habits from the children(good genes). We will see what it is and why it matters very soon.
  • DNA_mismatch Function: This will calculate how much of the population’s individuals differ from the actual target to achieve. It just zips their error and the individual together.

What’s happening?

Genetic Algorithms mainly defer by the way new off springs are created and how mutations are introduced in the generation. Crossover is the process of creating off springs and we will different kind of mutations and strategies within it to create the superior individual.

1. Cross Over Without Mutation

This means we are reproducing new offsprings but without introduction of new mutations. If A,B,C ∈ P1 and 1,2,3 ∈ P2 then C1 and C2 will be produced by using CrossOverWithoutMutation from P1 and P2 only if they have any of the six genes but none of the genes x ∈ C1 , C2 but ∉ P1,P2.

  • Plan of Attack : Create a random population. Assign DNA mismatch error in it. Select the top 10% and they will go to the next generation since they are most fit and cross breed the top 50% to create 90% offsprings which will compete with their parents for the next turn and keep doing that until you find your own homegrown evil AI created individual.

Here’s the code for it:

When you run this the output will be:

Output produced by the code above. It’s random can be different when you run it.

See this converged.

So what is this Convergence?

Convergence means when you reach your expected goal instead of compromising in mid between due to the bad genes being passed into the next generation or the good ones being eliminated from the generation.

Let’s plot this one and see it more clearly how it happened:

It found the best individual very quickly! Damn dude.

Is this the best we can do?

Certainly no and let me tell you one more thing. This thing worked only and only because of the lack of noise in the genes. We had only three options and they were repetitive there were very very less chance of missing some important gene and converging before reach the right point. So if you know that your task is controlled and you are pretty sure that genes won’t be lost(which will be no matter how hard you try, this is something you cannot control to full extent) then go for it otherwise stay and explore the mutation ones with me.

2. CROSS OVER WITH MUTATION

This means we are reproducing new off springs but without introduction of new mutations. If A,B,C ∈ P1 and 1,2,3 ∈ P2 then C1 and C2 will be produced by using CrossOverWithMutation from P1 and P2 only if they have any of the six genes but none of the genes x ∈ C1 , C2 but ∈ or ∉ P1,P2.

  • Plan of Attack : Create a random population. Assign DNA mismatch error in it. Select the top 10% and they will go to the next generation since they are most fit and cross breed the top 50% to create 90% offspring which will compete with their parents for the next turn and keep doing that until you find your own homegrown evil AI created individual. (Same as the above case but this time we use different crossing technique keep that in mind).

Here’s the code for it:

When you run this the output will be:

This one converged too. This is not just random, mutation makes sure that you reach your goal but sometimes on the cost of more iterations.

Plotting this one:

If you compare it, it’s better.

3. ONE POINT CROSS OVER

We will try one more approach now. Let’s see how about we try to create children purely out of parents?

We will take two parents and swap certain bits of them. Let’s say we get a random number c and we will swap every bit of two parents from index 0 to c and name the new entities as their offspring.

Here’s the code for it:

I cannot paste it’s output since it didn’t converge but I will show you it’s plot:

Why this happened?

We kicked some of the greatest genes that were necessary to reach our perfect individual by not having enough mutations in it. For example: if you can pick superpowers from your father and mother and they both chose the power to take naps whenever they want. How can you possibly inherit the power to lift ships and planes without having drastic mutations. This is what happened here. Here parents lacked some info, we created off springs out of them and lack of info kept on going and at some stage none of the powerful off springs had the almighty genes to become predecessor of our almighty individual.

Similarly you can create Two Point Cross Over and Uniform Cross Over by yourself. If you need any help in that reach to my Github Repo and leave a star if you like it. See ya again keep learning till then.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade