Genetic Algorithm and its Wide Spectrum
Genetic algorithms are a part of evolutionary algorithms used for searching and optimization problems. They are an algorithm inspired by the evolution happening naturally and work on the motto “Survival of the Fittest”. This article will cover some basic implementation of this algorithm but more importantly a wider view of its potential and applications.
Introduction
John Holland introduced this algorithm in 1960 and it has been famous ever since. The algorithm itself works in a way similar to the natural order of evolution, from parent to child.
Each individual can be distinguished by their physical characteristics which are defined by certain genes that vary for each person. These genes are passed on from the parent to their child and hence the child itself closely resembles their parent(s). Each gene in an individual, an animal, or plant has a certain role. For example, a certain gene may define red hair whereas the other of the same type, brown hair. Also, the number of genes that define every living being is different. Humans are said to have about 20,000–25,000 genes.
If you understand the above paragraph then be assured the algorithm itself is not very difficult. We will go through all details step by step’.
Evolutionary Algorithms
Genetic algorithms are a small part of the group of evolutionary algorithms. These algorithms all get their inspiration from nature or the biodiversity around us. Some are inspired by groups/swarms of birds and insects and help solve mathematical problems relating to such issues, PSO(Particle Swarm Optimization) algorithm being a good example. Another good example is the ABC(Artificial Bee Colony Algorithm) which was inspired by the colony of honey bees and helps solve problems like the XOR problem. These types of algorithms are mainly categorized under Swarm Intelligence.
Some algorithms like the Selfish Gene algorithm are very similar to the genetic algorithm but vary in methodology. GA focuses on an individual solving the problem but selfish gene as the name suggests concentrates more on the genes. Unlike GA it does not have a real population and only constitutes of genes.
Cuckoo Search is yet another such example. It is an optimization algorithm that was found in 2009, inspired by the awkward behavior of the cuckoo to lay eggs in other bird’s nest. Theoretically, the best nest carries forward the egg to produce a better generation of the cuckoo, and the process continues.
The Algorithm
The genetic algorithm starts with an initial population. A population is a group of individuals where each individual tries to solve a certain problem and overcome it. Every individual is distinguished by the genes it contains. Every gene has a particular role in completing the problem.
A population at a certain point in time is called a generation. It consists of individuals with similar problem-solving capabilities yet variable characteristics. If a particular generation cannot solve the problem, a new one is created from the experiences(genes) of the past ones through mating. Mating or Cross-over is the process of forming a new individual using two parents from the past generation.
Some individuals of the old generation who are exceptional at solving the problem are directly promoted to the next, these individuals are called Elites and the process, Elitism. After forming the new generation, each individual is mutated. The mutation is the process of randomizing some genes in order to adapt better in the future.
After every generation tries to solve the problem, some excel, some don't. The ones who do, are selected to mate and form the new generation. These parents are chosen since they have good fitness or a good ability to solve the problem.
This ends the basic implementation of the code in python of genetic algorithm. I hope you understood some of the key terminologies required to work on these algorithms.
Applications
The two main applications of genetic algorithms can be categorized as optimization problems and searching problems. It may not seem like much but these two domains cover so many events around us. Take an example of the school/college timetable that you follow. It is no more manually generated but done using algorithms that can easily be optimized by genetic algorithms. Now we will go over some concepts and examples of where genetic algorithms are used.
Optimization
Optimization is a very common and general issue that is required in every field today. Imagine you build an algorithm that takes an hour to perform the job or performs it incompletely. Optimization can be plainly stated as the search for certain parameters and flows to make work smoother and faster.
Multimodal Optimization
Multimodal functions are functions which have various local optima. A local optimum is a solution local to that are. These functions have more than one local as well as global solutions. This property makes it harder to find good solutions to problems but let's look at it with an example.
A college staff committee needs to build a time table for their new session. Manual methods are no longer used but algorithms that do the same task but much better and faster. There can be many time tables which are suitable and manually a team can produce a good 1 but running a genetic algorithm the staff could obtain many suitable ones within no time.
Mathematical Optimization
Mathematical optimization is a field of applied mathematics that mostly deals with real-life problems such as optimization of industrial processes, scheduling processes, manufacturing processes, and also in revenue optimization. Many operators throughout the globe use genetic algorithms to optimize the generation and delivery of power.
Route Optimization
Route Optimization is the process of finding the most cost-effective route from a source to destination with certain parameters. The path with the least traffic, least pollution could be some of the factors affecting the cost of the road.
The Travelling Salesman Problem using a genetic algorithm is the best example of such optimization. This problem asks a simple optimization question “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?”. This problem has been optimally solved by genetic algorithm and problems like these can also be done in a similar manner.
Neuroevolution
Neuroevolution is probably the most used filed off genetic algorithms. It is a major field of AI that combines neural networks with genetic algorithms. The role of the neural networks is to act as the brain of the application while the GA acts as the optimizer, optimizing the training process.
Have you heard of NEAT? NeuroEvolution of Augmenting Topologies is a famous algorithm that uses Artificial Neural networks with genetic algorithms to perform several AI-related projects today. Flappy birds or the google T-rex game have been reproduced using this NEAT by many developers.
Searching
In computational complexity, searching is a computational problem that requires finding a path from start to the end, generally in a directed graph. It may sound similar to route optimization but the aim of both is completely different and hence the approach too.
Genetic Algorithms have been seen as search procedures that can quickly locate high-performance regions of vast and complex search spaces, but the output may not be very accurate. In many pieces of research today it has been used in local search approaches and is called Local Genetic Algorithms.
Evolutionary Heuristic A* Search is a great example of genetic algorithms in heuristic searches. Search algorithms like A* need a good heuristic function to perform optimally but these functions tend to get very complex to get accurate results and give huge time delays. Genetic Algorithms come in very handy in these cases as they can automatically be optimized to provide good accuracy as well as low computation.
