Genetic Algorithm (AI)

Genetic algorithm is a searching technique using artificial intelligence.

5 min readMay 27, 2020

Introduction:

Whenever we listen the term ‘Search’ we committed to think about graph search algorithm like DFS, BFS or Dijkstra etc. Those graph search algorithm will survive in a small scale of search space. But when we need to work with millions/billions of nodes what can we do then?

let’s see the map(Banani, Dhaka). There are many road connections and we can think each road connection is a node. We have almost 90 to 95 nodes (red marked and I haven’t marked all road connections) in a small area. What if we think about Dhaka (The capital of Bangladesh) or what if we think about our Bangladesh. We just can’t imagine how many nodes we are going to deal with. When the search space is much bigger we can’t use normal searching technique, we can shift to some AI technique (i.e local search or any other). Genetic Algorithm is also a local searching technique.

===================================

Problem:

We got a black box and the box contain a key to get success in our life. We have to find out what the key is. We have all the elements in a random order {N, U, T, E, I, D, A, C, O} with what the key is made of . We have to rearrange them so that our arrangement will match exactly to the key. One thing more if we send our arranged order to the black box, it will return that how many positions of the elements are matched with the positions of the elements of that key.

How can we solve it? Well we can think about go through all the permutations of the given order and send it to the box and check it matched or not with that key. But can we think about it’s time complexity? We have 9 elements {N, U, T, E, I, D, A, C, O} in the given order. It has 9! (Factorial) permutations. If the key contain 15 elements then it will be 15! (Factorial), what if the key contain 100 element can we go for 100! (Factorial)? Obviously no…

In this manner we may think about the “Touring Machine” right? Almost we will do same as the “Touring Machine” but in a smart way, in an intelligent way. Let’s see how can we apply “Genetic Algorithm” here.

Steps of Genetic Algorithm:

Population Generation
Fitness Calculation
Selection
Crossover
Mutation
Repeat the process from 1 again and again while we do not satisfy with the outcome.

Population Generation:

Population generation is a process to generate some random permutations of the given order. Here we have only 5 random permutations. Together all the permutation we call it population. If we have large amount of population we can get our desire outcome easily but it will take too much time. Think about if we have 100 person and we have to find one we have to do a lot of task but if we have only 10 person, it will be very easy. But the problem is the probability of existence of that person in 100 person is higher than 10 person. Hey common.. It’s a massive confusion right. Any way we can go to the next section of our algorithm.

Fitness Calculation:

Well, here we will define our orders from the population how good or bad it is. We can say we are going to give some mark each of the order in real numbers so that we can take some decision based on the given mark.

Remember the problem says that if we send an order to the black box it will return us how many positions of the elements are matched with the positions of the elements of that key. Let assume order1: get f =1(as fitness, it means one of the element has matched with the key according to their position), order2: f=0, order3: f=1, order4: f=2, order5: f=1. Now we will take some decision in the next step.

Selection:

In here we will select the best orders according to their fitness. The probability of selecting those orders which has better fitness is higher than those orders which has lower fitness. From our population we can select all the order except order2 because it has the lowest fitness among them.

Crossover:

Crossover is a process of interchanging elements between the orders. If we take order3: f=1 and order4: f=2 and we apply cross over between them we can get an order which fitness is 3, which is better than previous.

Mutation:

Mutation is some internal changes in a particular order. Here we take “N” and “E” and changed their position and got an order which has a better fitness value. Which is good for us. We are going towards the solution. Let’s jump into the final step.

Final Judging Round:

Doing all the above process we will get the best outcome. But we are not sure that is it the global best result or the local best result. So in order to get the global best result we can go to the step 1 and generate the population again from out local best result. And follow these process over and over while we do not satisfy with the outcome.

One thing is that we may not get 100% accurate result in our real life problem. We may have to sacrifice something.