Genetic Algorithm in Machine Learning

Genetic algorithm

Genetic algorithms are basically search algorithms that are different from conventional search algorithms. Compared to conventional search algorithms, it is based on Darwin's theory of evolution.

It is used to get the solution to complex problems in less time, or we can say it searches for the best optimal solution from the set of all input features in less time.

It is based upon evolutionary computation.

Difference between traditional algorithms and genetic algorithms:

• Genetic algorithms are probabilistic and stochastic in contrast to conventional algorithms, which are deterministic.

• Genetic algorithms are more likely to provide optimal global solutions because of genetic operators like crossover and mutation, but they are not guaranteed to do so. Traditional algorithms are not more likely to produce global optimal answers.

• Real-world issues are multi-modal (have numerous locally optimal solutions), which standard algorithms can't handle well. However, because genetic algorithms have a very vast solution space, with the correct parameter settings, they can handle these problems quite well.

• Genetic algorithms just need one fitness function to determine an individual's fitness, whereas traditional algorithms need more data to do a search.

• Genetic algorithms can operate in parallel, whereas conventional algorithms cannot (calculating the fitness of the individuals are independent).

• Genetic algorithms act on potential solutions' representations (or coding), commonly known as chromosomes, as opposed to doing so directly. This is a significant difference.

According to Darwin's theory, those populations which are the fittest can survive in the environment, and they pass their traits to the next generation very easily.

The fitness of any population can be determined by how easily they adapt to the environment, and it can be determined by the fitness function of the environment.

In genetic algorithms, we produce new populations from old ones to get better results.

Gene

It is the single element in the individual or chromosome. We can represent it by 0 or 1. in generating a new generation, we will change the genes for getting better results.

Individual

It is also called a chromosome. It is the collection of genes, and it is represented in the form of binary strings like 0’s and 1s, where each bit represents the gene.

 Example: 10001010, 0010101 etc.

Population

The population is the collection of all the individuals or chromosomes, and the population is like a subset that contains the optimal solution for the problem.

Fitness function

Fitness function is the function that determines which individuals or chromosomes will give the best optimal solution according to their fitness value. If any chromosome has a higher fitness value, then there is a high chance that the first chromosome will give the better and optimal solution. In fitness function, we provide an individual chromosome as input, and it produces an output which is called fitness value.

Selection

Selection is the process in which we choose those individuals or chromosomes from the population to get the next generation with traits of its parent and additional quality to solve the problem in less time. We choose the individuals based on their fitness value and generate child individuals from them.

We have various methods to select the individuals from the population, like Roulette wheel selection, tournament selection, rank-based selection, etc.

Crossover

It is also known as mating. When we select two individuals from the population and change their genes to generate a new child chromosome, then this process is called crossover.

There are three types of crossover:

1. One point crossover
2. Two point crossover
3. Uniform crossover

Mutation

Mutation is also another way to generate a new generation from an individual. In this phenomenon, we change the bits of the binary string and generate new chromosomes.

There are the following methods of mutation:

1. Flip bit mutation
2. Gaussian mutation
3. Swap mutation

Replacement

When we generate child individuals from parents, and if the child has more fitness value than the parent, then it will replace the parent chromosome, and it is called replacement.

Termination

When after many stages of crossover, we generate that individual who has a fitness value greater than the required threshold, we will stop the process and terminate this whole phenomenon.