Genetic algorithms, inspired by natural selection, are a commonly used approach to approximating solutions to optimization and search problems. Their necessity lies in the fact that there exist problems which are too computationally complex to solve in any acceptable (or determinant) amount of time.
Take the well-known travelling salesman problem, for example. As the number of cities involved in the problem grow, the time required for determining a solution quickly becomes unmanageable. Solving the problem for 5 cities, for example, is a trivial task; solving it for 50, on the other hand, would take an amount of time so unreasonable as to never complete.
It turns out that approximating such optimization problems with genetic algorithms is a sensible approach, resulting in reasonable approximations. Genetic algorithms have had a place in the machine learning repertoire for decades, but their recent revival as tools for optimizing machine learning hyperparameters (and traversing neural network architecture search spaces) has brought them to the attention of a new generation of machine learning researchers and practitioners.
This article presents simple definitions for 12 genetic algorithm key terms, in order to help better introduce the concepts to newcomers.
1. Genetic Algorithm
A genetic algorithm (GA) characterizes potential problem hypotheses using a binary string representation, and iterates a search space of potential hypotheses in an attempt to identify the "best hypothesis," which is that which optimizes a predefined numerical measure, or fitness. GAs are, collectively, a subset of evolutionary algorithms.
2. Evolutionary Algorithm
An evolutionary algorithm (EA) is any type of learning method motivated by their obvious and intentional parallels to biological evolution, including, but not limited to, genetic algorithms, evolutionary strategies, and genetic programming.
3. Genetic Programming
Genetic programming is a specific type of EA which leverages evolutionary learning strategies to optimize the crafting of computer code, resulting in programs which perform optimally in a predefined task or set of tasks.
In a GA, each iteration, or generation, results in a series of possible hypotheses for best approximating a function, and the population refers to the complete set or pool of these generated hypotheses after a given iteration.
In an obvious nod to biology, a chromosome is a single hypothesis of which many make up a population.
In a GA, potential hypotheses are made up of chromosomes, which are, in turn, made up of genes. Practically, in a GA, chromosomes are generally represented as binary strings, a series of 1s and 0s, which denote inclusion or exclusion of particular items represented by position in the string. A gene is a single bit within such a chromosome.
For example, the Hello World of genetic algorithms is often considered to be the knapsack problem. In this problem, there would be a set of N items which may or may not be included in a thief's knapsack, and these N items would be represented as a binary string (the chromosome) N characters long, with each position in the string representing a particular item and the positional bit (1 or 0; the gene) denoting whether the item is included in the particular hypothesis or not.
Population → all of the proposed solutions to the knapsack problem of the current generation (iteration of the algorithm)
Chromosome → a particular proposed solution to the knapsack problem
Gene → positional representation of a particular item (and its inclusion or exclusion) in the knapsack of a particular solution to the knapsack problem
In GAs, new sets of hypotheses are formed from previous sets of hypotheses, either by selecting some full chromosome (generally of high fitness) to move forward to a new generation unscathed (selection), by flipping a bit of an existing full chromosome and moving it forward to a new generation (mutation), or, most commonly, by breeding child chromosomes for the new generation by using an existing set's genes as parents.
A generation, then, is simply the full set of the results of a GA iteration.
Breeding refers to what is generally the most common method of creating new chromosomes from an existing generation's set of hypotheses, which is using a pair of said chromosomes as parents and creating from them new child chromosomes, using the crossover method.
In a nod to natural selection, the concept of selection is ensuring that the best performing (highest fitness) chromosomes are ensured a higher probability of being used for breeding the next generation. Often highest performing chromosomes may be selected and pushed forward into the new generation without being used for breeding, ensuring that subsequent generations of hypotheses will minimally perform at the same level of the current generation.
How are selected chromosomes used to breed subsequent generations? The crossover method, shown below, is the general choice. A pair of selected strings of N bits in length would be chosen, and a random integer c generated as point of crossover of some size (say, 0 < c < N). The 2 strings are then independently split at this crossover point c and reassembled using the head of one string and the tail of the other, forming a pair of new chromosomes. The fitness of these new hypotheses would then be assessed in the following generation.
Just like in biological terms, mutation is used in GAs in order to push hypotheses toward optimal. Generally used sparingly, mutation would simply flip the bit of a random gene and push the entire chromosome forward to the subsequent generation, a strategy for escaping potential local minima.
We need some metric to measure the best fit of a hypothesis. Some fitness function is used to evaluate each chromosome, and best fits can be identified and more heavily relied upon in order to create new generational chromosomes. The fitness function is heavily task-dependent.
Update: My continued confusion of referring to genes as chromosomes and vice versa (which has an unfortunate and lengthy history) was pointed out by both Ahmed Gad and Ana Faraon. This current version has been edited to reflect reality. Thanks to both for catching this, and apologies for misleading readers of the earlier version.
- Descriptive Statistics Key Terms, Explained
- Natural Language Processing Key Terms, Explained
- Deep Learning Key Terms, Explained