Overview of Genetic Algorithm
Optimization techniques are the techniques that are used to discover the best solution out of all the possible solutions available under the constraints present. So the Genetic algorithm is one such optimization algorithm that is built on the basis of the natural evolutionary process of our nature. The idea of Natural Selection and Genetic Inheritance is used here. It uses guided random search, unlike other algorithms, i.e., finding the optimal solution by starting with a random initial cost function and then searching only in the space which had the least cost (in the guided direction). Suitable when you are working with huge and complex datasets.
What is a Genetic Algorithm?
The genetic algorithm is based on the genetic structure and behavior of the chromosome of the population. The following things are the foundation of genetic algorithms.
- Each chromosome indicates a possible solution. Thus the population is a collection of chromosomes.
- Each individual in the population is characterized by a fitness function. Greater fitness better is the solution.
- Out of the available individuals in the population, the best individuals are used for the reproduction of the next generation offsprings.
- The offspring produced will have features of both the parents and is a result of mutation. A mutation is a small change in the gene structure.
Phases of Genetic Algorithm
Below are the different phases of the Genetic Algorithm:
1. Initialization of Population(Coding)
- Every gene represents a parameter (variables) in the solution. This collection of parameters that forms the solution is the chromosome. The population is a collection of chromosomes.
- Order of genes on the chromosome matters.
- Most of the time chromosomes are depicted in binary as 0’s and 1’s, but there are also other encodings possible.
2. Fitness Function
- Out of the available chromosomes, we have to select the best ones for the reproduction of offsprings, so each chromosome is given a fitness value.
- The fitness score helps to select the individuals which will be used for reproduction.
3. Selection
- The main goal of this phase is to find the region where the chances of getting the best solution are more.
- Inspiration for this is from the survival of the fittest.
- It should be a balance between exploration and exploitation of search space.
- GA tries to move the genotype to higher fitness in the search space.
- Too strong fitness selection bias can lead to sub-optimal solutions.
- Too little fitness bias selection results in unfocused search.
- Thus Fitness proportionate selection is used, which is also known as roulette wheel selection, is a genetic operator used in genetic algorithms for selecting potentially useful solutions for recombination.
4. Reproduction
Generation of offsprings happen in 2 ways:
- Crossover
- Mutation
a) Crossover
Crossover is the most vital stage in the genetic algorithm. During crossover, a random point is selected while mating a pair of parents to generate offsprings.
There are 3 major types of crossover.
- Single Point Crossover: A point on both parents’ chromosomes is picked randomly, and designated a ‘crossover point’. Bits to the right of that point are exchanged between the two parent chromosomes.
- Two-Point Crossover: Two crossover points are picked randomly from the parent chromosomes. The bits in between the two points are swapped between the parent organisms.
- Uniform Crossover: In a uniform crossover, typically, each bit is chosen from either parent with equal probability.
The new offspring are added to the population.
b) Mutation
In a few new offspring formed, some of their genes can be subjected to a mutationwith a low random probability. This indicates that some of the bits in the bit chromosome can be flipped. Mutation happens to take care of diversity among the population and stop premature convergence.
5. Convergence (when to stop)
Few rules which are followed which tell when to stop is as follows:
- When there is no improvement in the solution quality after completing a certain number of generations set before hand.
- When a hard and fast range of generations and time is reached.
- Till an acceptable solution is obtained.
Application of Genetic Algorithm
In this section, we will discuss some of the areas in which the Genetic Algorithm is frequently applied.
1. Traveling and Shipment Routing
Traveling salesman problem is one of the major application of the genetic algorithm. For example, when a trip planner is asked to plan a trip, he would take the help of a genetic algorithm which not only helps to reduce the overall cost of the trip but also in reducing the time.GE is also used for planning the delivery of products from place to place in the best efficient way.
4.7 (4,075 ratings)
View Course
2. Robotics
The genetic algorithm is widely used in the field of Robotics. Robots differ from one another by the purpose they are built for. For example, few are build for a cooking task, few are built for teaching tasks, etc.
- Selection of important features in the given dataset.
- In the traditional method, the important features in the dataset are selected using the following method. i.e., You look at the importance of that model, then will set a threshold value for the features, and if the feature has importance value more than a threshold, it is considered.
- But here we use a method called a knapsack problem.
- We will again start with the population of a chromosome, where each chromosome will be binary string. 1 will denote the “inclusion” of feature in model and 0 will denote the “exclusion” of feature in the model.
- The fitness function here will be our accuracy metric of the competition. The more accurate our set of chromosomes in predicting value, the more fit it will be.
- There are many other applications of genetic algorithms like DNA analysis, scheduling applications, Engineering design.
Conclusion
In the current scenario, GE is being used in large manufacturing companies like aircraft etc in order to optimize the time and resources usage. Further scientists are working on finding new ways to combine genetic algorithms with other optimization techniques.
Recommended Articles
This is a guide to What is Genetic Algorithm? Here we discuss the introduction, phases, and applications of Genetic Algorithm. You can also go through our other suggested articles –
