GenesisCube

Genetic Algorithm in Machine Learning

Current methods in machine learning provide approaches for solving challenging, multiple constraint design problems. While neural networks methods have state-of-the-art performance, their vulnerability in decision making processes leading to irrational outcomes is a major concern for their implementation.
Genetic Algorithm is a type of Evolutionary Algorithm (EA), a subset of machine learning. EAs are used to discover solutions to problems humans do not know how to solve.

Free of human preconceptions or biases, the adaptive nature of EAs can generate solutions that are comparable to, and often better than the best human efforts.

What is Genetic Algorithm?

Genetic algorithm is a search heuristic that is inspired by Charles Darwin’s theory of natural selection. This algorithm mimics the process of natural selection in order to find the fittest solution to a problem.
There are several natural algorithms, such as Particle Swarm Optimization, which tries to mathematically simulate the social behavior of flocks of birds, and Ant Colony Optimization, which seeks to find the best paths in a graph simulating the behavior of ants when moving. Genetic algorithm (GA) is one of the most famous natural computing algorithms.

The GA starts with a population of randomly generated solutions called genotypes. These solutions are then evaluated, and the best ones are selected to be parents for the next generation. The new generation of solutions is created by applying genetic operations such as crossover and mutation to the parent solutions. The process continues until a solution with a sufficiently high fitness is found, or until some other termination criterion is met.

These types of algorithms are used to solve optimization problems, where you want to find optimal values within a search space. In the GA, transformations are applied to data that aim to try to replicate events such as mutation, natural selection, and cross-over. It is important to bear in mind that to correctly execute the GA, it is essential to have a well-defined problem to be solved, and the evaluation metric to be used.

Basic Terminologies of Genetic Algorithm

Let’s first understand the basic terminologies of genetic algorithm:

• Population
  • Population is the subset of all possible or probable solutions, which can solve the given problem.
• Gene
  • This is an element in a chromosome.
• Chromosomes
  • A chromosome is one of the solutions in the population for the given problem, and the collection of gene generate a chromosome. Chromosomes are derived by the technique of random binary strings.
• Allele
  • This is the value given to a gene in a specific chromosome.
• Fitness Function
  • The fitness function is used to determine the individual’s fitness level in the population. It uses a specific input to produce an improved output. The solution is used as the input while the output is in the form of solution suitability, and in every iteration, individuals are evaluated based on their fitness function.
• Individual
  • A member of the population that represents a single possible solution to the problem. It can be represented as an array, where each value in the array is a coefficient linked to the response equation of the analyzed problem.
• Tournament
  • It is the method of selecting the fittest individuals in the population. it compares the results of two or more individuals from the population and selecting the one that obtains the best result.
• Cross-Over
  • Operation of recombination of genes, where the genetic code of the parents is combined to generate the child. One or more cutoff points are defined, where the child receives all genes from the beginning of the genetic code to the cutoff point from the parent 1 and all genes from the cutoff point to the end of the genetic code from the parent 2.
• Mutation
  • Operation that modifies the value of a gene to a value different from the original.
• Genetic Operators
  • In GA, the best individual’s mate to reproduce an offspring that is better than the parents. Here genetic operators play a role in changing the genetic composition of the next generation.

How does Genetic Algorithm work?

Genetic algorithms follow the following phases to solve complex problems:

1. Initialization
   • The working of genetic algorithms starts with generating a set of individuals that we refer to as population. It contains a set of parameters called genes that are combined into a string and generate chromosomes.
2. Fitness assignment
   • The fitness function determines an individual’s ability to compete with other individuals. It provides the score to each individual that determines its probability of being selected for the process of reproduction. Higher the fitness score, greater are the chances of an individual getting selected for reproduction.
3. Selection
   • This phase involves the selection of individuals for the reproduction of offspring. All the selected individuals are then arranged in a pair of two to increase reproduction. Then these individuals transfer their genes to the next generation. There are three types of Selection methods available, which are:
     • Rank based selection
     • Tournament selection
     • Roulette wheel selection
4. Reproduction
   • In this step, the genetic algorithm leverages two variation operators. These are applied to the parent population. These two operators are:
     • Crossover
       • In this process, a crossover point is selected within the genes randomly. This operator then swaps the genetic information of the two selected parents or say individuals from the current generation to produce an offspring. The genes of the chosen fittest parents are exchanged until the crossover point is met. When the process ends, an offspring is produced that includes genes from both the parents.
     • Mutation
       • In this process, a random gene is inserted in the offspring in order to maintain the diversity in the population. There are three types of mutation styles available namely flip bit mutation, gaussian mutation, exchange mutation.
5. Replacement
   • Generation replacement takes place in this phase, which is a replacement of the old population with the new child population. The new population consists of higher fitness scores than the old, which is an indication that an improved solution has been generated.
6. Termination
   • After the reproduction phase, a stopping criterion is applied. The algorithm terminates after the threshold fitness solution is reached. It identify the final solution as the best solution in the population.

Applications of Genetic Algorithms

• Medical science
  • The areas of predictive analysis include protein prediction, RNA structure prediction, operon prediction.
• Neural networks
  • It is used for ‌genetic optimization in neural networks or use cases like inheriting qualities of neurons, neural networks pipeline optimization, finding the best fit set of parameters for a given neural network.
• Data mining
  • Data mining uses genetic algorithms to find out the centre point of the clusters with an optimal error rate given to its great searching capability for an optimal value.
• Task scheduling
  • Genetic algorithms are used to derive optimal schedules that satisfy certain constraints related to a problem.
• Economics
  • Genetic algorithms create models of demand and supply that derive asset pricing, game theory, and others.
• Robotics
  • Genetic algorithms contribute to the robotics field by providing the necessary insight into the decisions made by the robot. It generates optimal routes for the robot so that it can use the least number of resources to get to the desired position.

Genetic Algorithm is applied to software engineering through code synthesis, genetic improvement, automatic bug fixing, in developing game strategies, and more.

Advantages of Genetic Algorithms

In this segment we get acquainted with advantages of GA

1. Genetic algorithms provide solutions that improve over a period.
2. It has excellent parallel capabilities.
3. It optimizes several problems, such as continuous functions, discrete functions, and multi-objective problems.
4. It is the best choice for a wide variety of optimization problems.
5. It has a broad space for solutions search.

Disadvantages of Genetic Algorithms

1. They are not efficient algorithms for solving simple problems.
2. Repetitive calculation of fitness values may generate some computational challenges.

Infographics

The images of two operators involved in the reproduction phase are given below:

Recommended for you:

• Recurrent Neural Network
• LSTM Neural Network
• Clustering in Machine Learning