Genetic Algorithm

12
 min reading

An evolutionary algorithm (EA) uses mechanisms inspired by nature and solves problems through processes that emulate the behaviors of living organisms. Genetic algorithm (GA) is one of the simplest random-based EAs. It’s inspired by Charles Darwin’s theory of natural evolution “survival of the fittest”.

Genetic Algorithm

This type of algorithm is commonly used to generate high-quality solutions to optimization and search problems. It works by making slight changes to its solution until getting the best one. So, to do this, the algorithm performs four tasks: initialization, selection, reproduction and mutation. Next, we will understand each one of these steps

Initialization

First, a population of a fixed size of random bit-strings is created. Population can be defined as a subset of solutions in the current generation. The population size depends on the nature of the problem. Each bit-string represents one individual solution and each individual has a chromosome that defines the individual. The chromosome is coded as a finite length vector of components. These components are analogous to genes. So, each chromosome has a set of genes, as shown in the following image. These genes can represent the individual in different ways, as letters or binary numbers. In most cases, the initial population is generated randomly.

Selection

The next step is to calculate the fitness of each element of the population which shows the ability of an individual to compete. Thus the fitness function represents the quality of the solution. The goal of these task is to select the parents that will be the basis to breed the next generation. The individuals that have the higher fitness are more likely to be selected. There are six methods of selection: Roulette Wheel Selection, Rank Selection, Steady State Selection, Tournament Selection, Elitism Selection and Boltzmann Selection. The fitness expression can also be defined in different ways. As we can see in the figure below, one way is to sum all the times that components are in the same position as in compared object.

Reproduction

Later, the next task is to generate a second generation of solutions. This step is known as crossover and it’s the most significant phase in a genetic algorithm. Two parents selected in the previous step will have their genes combined to breed new chromosomes. The selection of each two parents may be by selections sequentially or by random selection. Besides, some research suggests that more than two parents generate higher quality individuals. Generally, the average fitness for the new population have increased when compared with the initial generation, since only the best organisms from the first generation are selected for breeding. Thus each new generations have better partial solutions than previous generations.

Recombination is performed using crossover operator. There are many variations of this operator. One way is called point crossover. It consists of two parents, then two children will be created. This involves selecting a random split point on the bit string, then creating two children. The first one will be made by the first part of the first parent and the second part of the second parent. This process is then inverted for the second child, as can be seen in the following image.

Mutation

The last step is mutation. The key idea is to insert random genes in offspring to maintain the diversity in the population. By doing this, we avoid to get stuck in a local minimum. There are many mutation operators. If the encoding is binary, we can use the operator called as Bit Flip Mutation, where we flip the bit value of genes. If not, it can be used the Random Resetting, where a random value is assigned to a randomly chosen gene. Although, there are others operators, as Swap Mutation, Scramble Mutation and Inversion Mutation. The mutation rate can be set. A very small mutation rate may lead to genetic drift. Otherwise, if it’s too high, may lead to loss of good solutions. Frequently, the mutation rate is set to 1/L, where L is the length of the chromosome, yielding an average of one mutation per child chromosome.

The children are added to a new population. So, old population are replaced by the new population. At the end, we return to the selection step. The process is repeated until a termination condition has been reached. There are many conditions that end the process, or the set of some of them. Some examples are: when a solution is found that satisfies minimum criteria, when the fixed number of generations is reached or if the population does not produce offspring which are significantly different from the previous generation.

Conclusion

At the end, we can see how simple and effective genetic algorithm is. This algorithm performs methods that are biology inspired to generate better solutions, as selection, crossover and mutation. In genetic algorithms, the population has a fixed size. So, as new generations are formed, individuals with least fitness die, providing space for new offspring. The goal is to breed a population consisting of the fittest individuals. Genetic algorithm can be used in many areas, as Travelling Salesman Problem, engineering design and optimization problems.

Given below is an example implementation of a genetic algorithm in Python. Feel free to play around with the code. The intention to write it was just to get the idea. The target object is the word “banana” and the population size is ten chromosomes with 6 letters each.