An Insight to Genetic Algorithms — Part I
Let’s start with the famous quote by Charles Darwin:
“It is not the strongest of the species that survives, nor the most intelligent, but the one who is most adaptable to change.”
You must be wondering what this quote has to do with genetic algorithms? Actually, the entire concept of genetic algorithms lies on just the above quote!
Genetic Algorithms are a search-based optimization technique based on Darwin’s principle of Natural Selection. This is a novel AI technique introduced in 1970’s. This has the ability to solve questions that cannot be solved through any other techniques like Artificial Neural Networks.
Nature has always been a great source of inspiration to all mankind. Genetic Algorithms are search based algorithms based on the biological concepts of natural selection and genetics. Genetic Algorithms are a subset of a much deeper branch of computation known as Evolutionary Computation.
Genetic Algorithms were initially developed by John Holland and his students and colleagues at the University of Michigan. Remarkably David E. Goldberg has since been tried on various optimization problems with a high degree of success for Genetic Algorithms.
In genetic algorithms, we have a pool or a population of possible solutions to a given problem. These solutions then undergo some genetic operations, producing new children and the process is repeated over various generations. Each individual (or candidate solution) is assigned a fitness value based on an evaluation function value and the fitter individuals are given a higher chance to mate and yield more “fitter” individuals. This is in line with the Darwinian Theory of “Survival of the Fittest”.
In this way, we keep “evolving” better individuals or solutions over generations, till we reach a termination criterion.
Optimization
Optimization is the process of making something better.
Optimization refers to finding the values of inputs in such a way that we get the “best” output values. The definition of “best” varies from problem to problem, but in mathematical terms, it refers to maximizing or minimizing one or more objective functions, by varying the input parameters.
The set of all possible solutions or values which the inputs can take make up the search space. In this search space, lies a point or a set of points which gives the optimal solution. The aim of optimization is to find that point or set of points in the search space.
Evolutionary Algorithms
The main task performed by evolutionary algorithms is optimization. The difference between traditional algorithms and evolutionary algorithms is that evolutionary algorithms are dynamic and thus they can evolve over time and can be efficiently be used to represent frequently changing information.
Evolutionary algorithms have three main characteristics:
1. Population-Based: Evolutionary algorithms are to optimize a process in which the current set of solutions are bad/not optimal to generate new/ better/optimal solutions. The set of current solutions which is referred here is termed the population.
2. Fitness-Oriented: There is a fitness value associated with each individual solution which is calculated from a fitness function. This fitness value reflects what extent the solution is good.
3. Variation-Driven: If there is no acceptable solution in the current population according to the fitness function calculated from each individual, we should make adaptation to generate new better solutions. As a result, individual solutions will undergo a number of variations, simply iterations to generate new solutions.
Genetic Algorithms — Motivation
Genetic Algorithms have the amazing ability to provide “good enough” and “fast-enough” solutions. This makes genetic algorithms attractive for use in solving real-world problems. The reasons why Genetic Algorithms are needed are as follows −
1)Solving difficult problems
Think of a situation where there are a complex and large set of problems to be solved. Even the most powerful computing systems take a very long time (even years) to come across such difficult problems. In such a situation, Genetic algorithms prove to be an effective tool to provide usable near-optimal solutions in a short amount of time.
2) Getting a better/optimal solution fast
Some real-world problems may have a number of solutions. In real life, we meet conditions where we need only the most suitable answer in hand. For examples storing of containers of different sizes in a ship dock, arranging rooms in a house map such that at the end same house area is obtaining, storing of goods in a rack such that there is minimal space wasting can be taken. Pathfinding problems like the Travelling Salesmen Problem and VLSI Design also can be addressed by Genetic Algorithms.
3) Processing Dynamic information
Recall that Artificial Neural Network requires collected data of a long time and that data should have the ability to represent every state that the system tries to predict in future. The network is unable to work on strange information which was unavailable when the model was being developed. Genetic Algorithms address this issue by being able to provide solutions for dynamically changing data. Since Genetic Algorithms can be effectively used for Traffic light controlling systems, Weather forecasting and for predicting trends and patterns in the stock market.
4) Obtaining similar solutions
Have you ever thought to win lottery numbers by analyzing and finding a pattern in previously won lottery numbers? Genetic algorithms are able to provide solutions for such kind of situations where we need to discover some matching similar solutions. Magical! Isn’t it?
5) Discovering unforeseen solutions
We have come across situations where children have almost different characteristics from that of their parents. Following this genetic phenomenon, it is clear that Genetic algorithms can be utilized to discover unforeseen solutions. This feature can be adopted for situations like designing interior architecture of a house or a company.
6) Checking whether there is a solution
Genetic algorithms can be used in systems to check whether there is a solution for a given problem. For example, there are problems which were unable to solve by linear programming were able to be solved by genetic algorithms. Apart from that genetic algorithms has been used in determining the shape of the turbines in Boeing 747 Jumbo Jet. Earlier it has been calculated that it would approximately take 10 years for that purpose if only supercomputers, calculus, and linear programming was used.
7) Scientific solutions for random experiments
When there are a number of possible solutions for a given problem, we tend to use a random answer as the solution. But there is an uncertainty in that random answer not being the most optimal solution for the problem. Genetic algorithms can be used in providing more assured answers for this kind of random experiments. For example, think of a university lecturer preparing exam papers by selecting the questions from a large list of questions. If genetic algorithms are used he can prepare exam papers that contain questions of high quality.
Basic Terminology
Genetic Algorithms lie within the following basic principle terms, where you need to be familiar with.
*Population — It is a subset of all the possible (encoded) solutions for a given problem. Simply, this is the set of individuals and each individual is a solution to the problem we want to solve.
*Chromosomes − A chromosome is one such solution to the given problem.
*Gene − A gene is one element position of a chromosome. The individuals in a population are characterized by a set of parameters (variables) and they are particular, termed as Genes. Basically, Genes are joined into a string to form a Chromosome (solution).
*Allele − It is the value a gene takes for a particular chromosome.
*Genotype − Genotype is the population in the computation space. In the computation space, the solutions are represented in a way which can be easily understood and manipulated using a computing system.
*Phenotype − Phenotype is the population in the actual real world solution space in which solutions are represented in a way they are represented in real-world situations.
*Decoding and Encoding − Decoding is a process of transforming a solution from the genotype to the phenotype space, while encoding is a process of transforming from the phenotype to genotype space.
*Fitness Function / Evaluation Function –Fitness Function evaluates how close a given solution is to the optimum solution of the desired problem. It determines how fitting a particular solution is.
*Genetic Operators − These alter the genetic composition of the offspring. These include crossover, mutation, selection, etc.
Selection
The idea of the selection phase is to select the fittest individuals and let them pass their genes to the next generation.
Two pairs of individuals (parents) are selected based on their fitness scores. Individuals with high fitness have more chance to be selected for mating.
Crossover
Fertilization occurs by the process of exchanging the genes in chromosomes. Crossover is such gene-exchanging mechanism that has been identified so far. It is one of the most significant phases in a genetic algorithm. Crossover is the mostly occurring genetic operation among chromosomes. Here for each pair of parents to be mated, a crossover point is chosen at random from within the genes.
In the crossover, Offspring are created by exchanging the genes of parents among themselves until the crossover point is reached. The new offspring are added to the population through this process of exchanging genes among parents.
For example, consider the crossover point chosen between gene 2 and 3 of parent chromosomes as shown below in (i). Here (i) shows the parent chromosomes, (ii) crossover operation and (iii) Resulted child chromosomes /off springs respectively.
Basically, there are 4 types of crossover as follows.
Single point crossover — One crossover point is selected, binary string from beginning of chromosome to the crossover point is copied from one parent, the rest is copied from the second parent.
Example:- 1 1 0 0 1 0 1 1 + 1 1 0 1 1 1 1 1 = 1 1 0 0 1 1 1 1
Two point crossover —Two crossover point are selected, binary string from beginning of chromosome to the first crossover point is copied from one parent, the part from the first to the second crossover point is copied from the second parent and the rest is copied from the first parent.
Example:- 1 1 0 0 1 0 1 1 + 1 1 0 1 1 1 1 1 = 1 1 0 1 1 1 1 1
Uniform crossover — Bits are randomly copied from the first or from the second parent.
Example:- 1 1 0 0 1 0 1 1 + 1 1 0 1 1 1 0 1 = 1 1 0 1 1 1 1 1
Arithmetic crossover — Some arithmetic operation is performed to make a new offspring
Example:-1 1 0 0 1 0 1 1 + 1 1 0 1 1 1 1 1 = 1 1 0 0 1 0 0 1 (AND)
Note that in the crossover, parent chromosomes get directly transferred to offsprings. Thus offsprings have almost or some similar characteristics to that of their parents.
Mutation
In some situations, we see children that have almost different characteristics when compared with their parents. This occurs as a result of a mutation that happens between chromosomes. Here some of the genes in a chromosome get flipped and get a completely opposite value.
Note that crossover is a frequent phenomenon occurs within chromosomes whereas mutation occurs very rarely and so it has a low random probability. Crossover happens between 2 chromosomes whereas mutation occurs in a gene/genes within a single chromosome.
Since the off-springs hand on completely different features; Mutation occurs to maintain diversity within the population and prevent premature convergence. Thus mutation always adds a disturbance / randomness / noise to the population. So mutation is also known as a randomness added / noise added operation in genetics.
Basic Process of a Genetic Algorithm
The basic structure of a Genetic Algorithm is as follows.
The process should be started with an initial population, which may be generated at random or seeded by other heuristics. Next, using evaluation function, parents are selected from this population for mating. Then crossover and mutation operators are applied to the parents to generate new off-springs. Finally, these off-springs replace the existing individuals in the population and the process repeats. This is really how genetic algorithms actually mimic the human evolution. The whole process can be combined with a flowchart as follows.
Applications of Genetic Algorithms
Genetic Algorithms are primarily used in optimization problems, then again they are frequently used in other application areas as well.
Following are some of the areas in which Genetic Algorithms are frequently used. These are −
-Optimization − Genetic Algorithms are most commonly used in optimization problems where we have to maximize or minimize a given evaluation function value under a given set of constraints.
-Artificial Neural Networks − To train neural networks, mainly recurrent neural networks.
-Financial Sector — In the financial markets, genetic algorithms are most commonly used to find the best combination values of parameters in a trading rule and they can be built into ANN models designed to pick stocks and identify trades.
-Economics − To characterize various economic models like the cobweb model, asset pricing, game theory equilibrium resolution, etc.
-Parallelization − Genetic algorithms have very good parallel capabilities and prove to be very effective means in solving certain problems and also provide a good area for research.
-Image Processing − Genetic algorithms are used for various digital image processing applications like dense pixel matching.
-Agricultural Sector- Precision agriculture is a new trend in the agricultural sector which is primarily based on Decision Support System (DSS) for farm management with the goal of optimizing returns on inputs while preserving resources. Genetic algorithms are used in precision agriculture systems to determine the best nutrition combinations in greenhouses, determine optimal cropping patterns and in developing agriculture extension agents etc.
-Scheduling applications −Genetic algorithms are used to solve various scheduling problems, for instance, the timetabling problem.
-Robot Trajectory Generation − To plan the path which a robot arm takes by moving from one point to another.
-Parametric Design of Aircrafts − To design aircraft by varying the parameters and evolving better solutions.
-DNA Analysis −In determining the structure of DNA using spectrometric data about the sample.
· Multi-modal Optimization − Genetic algorithms are obviously very good approaches for multi-modal optimization in which we have to find multiple optimum solutions.
· Traveling Salesman Problem and its applications − Genetic algorithms have been used to solve the Traveling salesman problem, which is a well-known combinatorial problem using novel crossover and packing strategies.
Limitations of Genetic Algorithms
Like any scientific technique, Genetic Algorithms also suffer from a few limitations. These include −
i) Not suited for all problems, especially problems which are simple and for which derivative information is available.
ii) The fitness value is calculated repeatedly which might be computationally expensive for some problems.
iii) The requirement of computers with high processing power and capacity. Since a lot of space is needed to store the increasing population when a genetic algorithm runs.
iv) Take more time to produce a result if there is not adequate processing power and computer capacity.
v) Being stochastic, there are no guarantees on the optimal or the quality of the solution.
vi) If not implemented properly, the Genetic Algorithms may not converge to the optimal solution.
Implementation Of Genetic Algorithms
This section includes a Demo Application developed in Python to demonstrate how genetic algorithms work.
This example uses the decimal representation for genes, one point crossover, and uniform mutation.
The objective of the demo is to maximize an equation. Here genetic algorithm has been used to get the best possible values after a number of generations.
The solution is available at:-
I will come with more details on this implementation in my next blog post.
Hope you got a clear understanding through this initiative blog post. If you have any issues or comments on this blog post please leave a comment below.
Cheers!
References
[1] Genetic Algorithms in Search, Optimization and Machine Learning by David E. Goldberg.
[2] Artificial Intelligence by Prof. AS Karunananda
[3] https://www.linkedin.com/pulse/introduction-optimization-genetic-algorithm-ahmed-gad/
[4] https://www.kdnuggets.com/2018/03/introduction-optimization-with-genetic-algorithm.html
[5] https://www.analyticsvidhya.com/blog/2017/07/introduction-to-genetic-algorithm/
[6] http://mathgifs.blogspot.com/2014/03/the-traveling-salesman.html
[7] http://www.obitko.com/tutorials/genetic-algorithms/crossover-mutation.php
