Introduction to Genetic Algorithms
Background
When Charles Darwin developed his theory of evolution in the 19th century little did he know that this theory would have a profound impact on computational algorithms.
The ideas of natural selection, survival of the fittest, mutation, and cross-over **** all lead to the ‘best' variants surviving and carrying the ‘best' traits forward. John Henry Holland took these concepts and pioneered the _meta-heuristic genetic algorithm in 1975 to solve mathematical optimization problems. This is not the first time biological processes have influenced Machine Learning. Perhaps the most notable is Frank Rosenblatt developing the neural network perceptron in 1958_ inspired by the real neurons in the brain.
Most genetic algorithms are used to solve _combinatorial optimization problems where the brute-force search is intractable due to the sheer magnitude of permutations and combinations. Example include the knapsack and traveling salesman_ problems.
If you are a Data Scientist, chances are you will come across problems like these in your career, therefore it is worth understanding how to approach them and this post will cover one of the best and most common methods. We will dive into the theory, methodology, and general uses of genetic algorithms to show how you can implement them to solve almost any Optimization problem.
Notation & Terminology
Much of the terminology for genetic algorithms derive from its corresponding biological process:
- Encoding & Decoding: Mapping the problem to a conveniently numerical format for the algorithm to utilize. Common techniques include binary and permutation encoding.
- Population: A set of possible solutions.
- Chromosome: A single possible solution.
- Gene: A positional representation of one element in the chromosome.
- Allele: The value of a Gene.
- Fitness Function: A score is given to each solution to determine its ‘fitness' to the optimization problem.
These different terms can be visually demonstrated below:
Algorithm
Initialisation
The algorithm begins by generating an initial population for the problem. This needs to be adequately diverse with a range of solutions from the possible search space with a total number in the 100s or 1000s ideally.
Selection
After we have our population, we need to select solutions (parents) to take forward to produce offspring for the next generation. The parents are selected based on their fitness to ensure the ‘best' genes are passed on.
Some techniques for selection are:
- Elitism: Choose a certain number of solutions in the current population with the best fitness function.
- Roulette Wheel: _Sample from a probability distribution of the solutions (chromosomes) in the current population where each solution's probability, p_s, is proportional to its fitness score, f_s:_
- Tournament: This involves selecting solutions at random and running tournaments with these subset solutions where the winner is the one with the best fitness score.
There are many other methods for the selection process and different variants of the techniques listed above. You can also combine selection procedures to generate hybrid methods as well. There is no ‘one size fits all' and it's best to experiment with various types.
Crossover
Now that we have our parents, we need to combine their genetic material to produce offspring to generate a new fitter population. Similarly to the selection stage, there exists sundry **[operators](https://en.wikipedia.org/wiki/Operator%28computerprogramming%29)** to carry out crossover, and it is very dependent on the type of encoding for the problem.
Let's go through some of the most common:
- One-point crossover: Swap the genes from a selected point on the parents' chromosomes:
- Two-point crossover: Swap the genes from two selected points on the parents' chromosomes:
- Uniform crossover: Each gene is randomly selected from the corresponding genes from the two parents:
These techniques are valid for binary-encoded chromosomes and for other different encodings other operators will probably be required. There is a great article linked here that gives a comprehensive list of some more complex crossover operators.
Mutation
The final step in the algorithm is **[mutation](https://en.wikipedia.org/wiki/Mutation%28geneticalgorithm%29)**. This is analogous to biological mutation where offspring can have a random alteration to its DNA. A mutation is a slight modification to the genes in a solution with a small probability. If the probability is high, then the genetic algorithm becomes a _random search. The main motivation behind the mutation operator is to diversify the population and reduce the chance of local optima_.
Lets run through some simple and easy to apply mutations:
Bit flip: Iterate through the genes in a chromosome and with each pass randomly flip a bit with a small probability:
- Swap: Select two genes, with low probability, in the chromosome and swap them:
Linked here is a further list of mutation operators.
Similarly to crossover, the above mutation operators are valid for binary-encoded problems, therefore may not be appropriate for other types of problems and encodings.
Termination
The algorithm can end due to several reasons which are up to the users' discretion:
- A certain number of generations reached
- A desired fitness is achieved
- Computational resource exhausted
- Fitness score has plateaued
Applications
Genetic algorithms are used in an assorted range of fields, including but not limited to:
- Scheduling in production planning
- Vehicle routing problems
- Financial markets and portfolio optimization
- Training neural networks
- Image processing
Weaknesses
Some vulnerabilities of the genetic algorithm are:
- Scalability is not as good as other optimization algorithms, hence can have a long computing time
- Difficulty to adequately fine-tune hyperparameters such as mutation and selection can lead to non-convergence or useless results
- Doesn't guarantee finding the global optimum, however, this is the trade-off of all meta-heuristic methods
- An expensive and complex fitness function can also lead to long computation durations
Summary & Thoughts
The genetic algorithm derives its name from the analogous process in evolutionary biology. It is a meta-heuristic optimization algorithm that starts from an initial population and iteratively uses the best solutions from the population to create new and better solutions (offspring) through the operators of selection, crossover, and mutation. It can be used in many areas such as medicine and supply chain but can suffer from long compute times depending on the evaluation metric and the hyperparameters are chosen.
Another Thing!
I have a free newsletter, Dishing the Data, where I share weekly tips for becoming a better Data Scientist. There is no "fluff" or "clickbait," just pure actionable insights from a practicing Data Scientist.
Connect With Me!
References & Further Reading
- Algorithms for Optimization. Mykel J. Kochenderfer and Tim A. Wheeler. 2019.
- Combinatorial Optimization: Theory and Algorithms. Bernhard Korte and Jens Vygen. 2018.
- Holland, J.H. (1975) Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor. (2nd Edition, MIT Press, 1992.)
- Rosenblatt, F. (1958). The perceptron: A probabilistic model for information storage and organization in the brain. Psychological Review, 65(6), 386–408. https://doi.org/10.1037/h0042519
