Skip to content

A Quick Introduction to Genetic algorithm (GA)

This strong and poweful algorithm originates from famous monograph called ‘Adaptation in Natural and Artificial Systems’ writted by John H.Holland. The main idea of this monograph is copying of biological process such as adaptation to solve the different tasks with dynamic parameters and it may be used to economics, physiological psychology, game theory, and artificial intelligence and etc.

In this way, John H.Holland presented a mathematical model that allows for the nonlinearity of such complex systems. The key elements in math model are coadaptation and coevolution: the emergence of building blocks, or schemata, that are recombined and passed on to succeeding generations to provide, innovations and improvements.

Indeed, you may say: “What is it? building blocks, schemata”. The meaning of these strange words you understand later! Anyway, to understand the main principle of genetic algorithm, it’s needed to imagine that nature evolution is process for finding the adapted individuals among biological organisms. For this reason, we might replace these biological entities with the solutions of equation as well as we might replace nature evolution with procedure for the solving equation. Indeed, what’s the difference between nature evolution and procedure for the solving equations?

On the one hand, we have decisions, which to have to survive in a decision space and a best decision must be founded by appropriate function or algorithm. On the other hand, the survival is the adaptation by saving the useful property of decision in search space. In short, you should note that best decision for some task is the adapted decision through appropriate function or algorithm for given decision space. Wow! It is time to show the concrete mechanism of adaptation with using GA.

The genetic algorithm has the tools for finding the optimal decisions in decision space. There are three main genetic operators such as selection, crossover and mutatuion. Let’s consider each of them. Selection is extraction of more appropriate items based on the calculation of a fitness-function. Actually, the fitness-function is mathematical formula in form of function or algorithm and one returns some decision (scalar, matrix, vectors and etc.).

Selection. If we want to recognize the adaptive decision, it’s needed to skip all decisions through the fitness-function and to be picked ones with maximum or minimum values. It’s easy and simple. In this case, we may face with the hidden problem. Yes, the adaptive decisions is our target, but who said it’s true? Probably the worst decisions are very important, because ones have arisen during the battle for survival. Therefore, the worst decisions should be used for reason of useful for future generations. Moreover, the best solutions might be selected by chance. Fortunately, selection uses the different methods for the protection against the random decisions, which seem best among others. We will consider the Roulette method to be more popular and applied to classical GA.

Let’s imagine a black box to be fitness-function to emulate the the Roulette method. The black box calculates some results based on input values. The adaptation criteria is to get the largest value for output results. Let’s calculate four toy parameters  x_1, x_2, x_3, x_4 by black box –  blackbox(x_i) to get results such as:

  •  blackbox(x_1)= 33;
  • blackbox(x_2)= 3;
  • blackbox(x_3) = 19;
  • blackbox(x_4)= 9.

Did you recall about the adaptation criteria? Yes, the higher value is more optimal. In our case,  blackbox(x_1), blackbox(x_3) are the adaptive decisions and have the good chance to survive in a decision space. At the same time, we should give the chance to  blackbox(x_2), blackbox(x_4) . Anyway, each chance will be proportional to blackbox values for x_i and is the roulette sector. Therefore, it’s needed to calculate the contribution of each x_i in the adaptation criteria ( proportion for each value ). We simply do two operations. Firstly, it should be summarized all blackbox values and each value divided by them amount (1). Secondly, the random digit is produced once or twice to pick up an item from the roulette; in this way, we simulate the roulette launch (2). That’s all you need! This simple idea is presented with using the formula (1).

Sector_i= \frac{blackbox(x_i)}{\sum_{i=1}^{4}x_i}

For our values:

  • Sector_1= \frac{33}{33+3+19+9}=\frac{33}{64}=0.51*100=51\% (33);
  • Sector_2= \frac{3}{33+3+19+9}=\frac{3}{64}=0.05*100=5\%(5);
  • Sector_3= \frac{19}{33+3+19+9}=\frac{19}{64}=0.3*100=30\%(30);
  • Sector_4= \frac{9}{33+3+19+9}=\frac{9}{64}=0.14*100=14\%(14);

And finally, the image below shows the calculated sectors with approprite values for each x_i.

After then, it should be used the roulette, which rotates and stops at a decision sector. In mathematical language, this process may be defined with using a random value in interval from 0 to 100. Let’s call a random function to calculate a random value – Roullete_i= rand_i(0, 100). One rotate will select an adaptive decisions. How many times must you rotate this roulette? It all depends on number of decisions in iteration and this one is setting parameter for GA. We need understand essential of this algorithm therefore theme about settings parameters will consider in next posts. We will rotate four times! The result is shown below.

The red arrow is the stopped roulette or value obtained via Roullete_i. In our case:

  • Roullete_1=rand_1(0, 100) = 25, 25\in [0;51] : 33;
  • Roullete_2= rand_2(0, 100) = 5, 5\in [0;51] : 33;
  • Roullete_3= rand_3(0, 100) = 90, 90\in [56;86] : 19;
  • Roullete_4= rand_4(0, 100) = 93, 93\in [86;100] : 9.

That’s all, the selection has finished and values obtained may be transferred to next step of the algorithm such as crossover.

Crossover. It’s very important feature. After the selection to be finished the values obtained should be divided into pair for crossover(pairing). The important thing you should know that scalar values are converted to binary code. If you have the vectors, you need use vector as is. In our case, the selection produced four scalar values, so ones are converted to binary code.

  • Binary_1=33_2 = 100001;
  • Binary_2= 33_2 = 100001;
  • Binary_3= 19_2 = 010011;
  • Binary_4= 9_2= 001001.

Now, we should choose a pair of values. It could be selected even and odd values. For example, Binary_1 pairing with Binary_3:

You can see the converted values are placed on top and named parents with crossing genes colored different colors. The genes are binary codes and each group of genes are involved in crossover. The brown group (10 00) passed on to a children2 as well as green group( 01 ) passed on to a children1. Similarly the blue group (01 00) of other parent passed on to a children1 as well as oringe group( 11 ) passed on to a children2. The crossover point of the group genes is defined randomly. Finally, two childern are new adaptive decisions with useful genes.

Let’s back to coadaptation and coevolution terms. The process by which two or more species, traits, organs, or genes undergo adaptation as a pair or group is called as coadaptation. In our example, we used coadaptation by saving the useful genes from parents to passed there for new generation. The coevolution occurs when two or more species reciprocally affect each other’s evolution through the process of natural selection. Therefore, crossover applies only for items were received via the adaptive tool (in our case, method Roulette). It’s OK! but we have new issue! From this time, GA is greedy algorithm!What is it? The greedy algorithms eat only tasty decisions, so it don’t have the protection from local decision. The nice explanation this topic – Basics of Greedy Algorithms. The local decision is good decision, but it may hide the global decision. From this reason, GA uses mutation!

Mutation is very simple tool for knocking out a local decision. Firstly, it should be defined the mutation probability and it is very small value 0.1 or 0.3. Secondly, it’s randomly defined the gene’s number for mulation or changing bit (0 with 1 and 1 with 0). For illustrative explanation, the decision 33 with binary value is 100001. The random value random(1, 6) = 4, and the gene with position 4 might be mutated. Again, the random value from 0 to 1 is needed extract to understand whether change the mutated gene. Now, we have random(0, 1) = 0.5, so 0.5>0.1 then mutated gen will be replaced to 1. Wow, that’s all!

Summarizing. Now, we have four main elements ( selection, crossover, mutation and fitness-function), which need join to GA. Below, you can see the classical GA with the mentioned operators such as roulette, crossing over, mutation and selection calculates the fitness function for evaluating the adaptive decision.

   % This quicksort algorithm is extracted from Chapter 7, Introduction to Algorithms (3rd edition)
\begin{algorithm}
\caption{Genetic algorithm}
\begin{algorithmic}
\STATE $cnt = $c
\STATE $epochs = $e
\STATE $new = $array()
\STATE $old = $array()
\STATE $t = $ \CALL{initGA}{x}
\FOR{$j = 0$ \TO $e - 1$}
   \STATE $new = t$
   \STATE $t = $ \CALL{roulette}{t}
   \STATE $t = $ \CALL{crossingover}{t}
   \STATE $t = $ \CALL{mutation}{t}
   \STATE $old = new + t$
   \STATE $t = $ \CALL{selection}{old}
\ENDFOR
\end{algorithmic}
\end{algorithm}

In the next post, we will develop the algorithm from scratch with using python. Please! Give me feedback and the cheerfulness for my blogging job.

Be First to Comment

Leave a Reply

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