What is a Genetic Algorithm?
Evolutionary Computation
In order to understand how a Genetic Algorithm works, one must first understand how a generic Evolutionary Algorithm works. Evolutionary Computation (EC) is a wide-ranging field of computing techniques based on the evolutionary principle of natural selection, wherein candidate solutions are continually improved within their environment based on the theory of survival of the fittest, taking strong cues from biological terminology. With evolutionary algorithms, a problem is addressed using populations of individuals, each representing a potential solution to the problem. These populations are then slowly evolved over a number of generations by interbreeding and varying the components of individual solutions to produce new child solutions that form the basis of each subsequent generation. An objective function (known as the fitness function) determines the ability of each individual to solve the problem at hand, and assigns it a value by which it can be judged against its peers (usually known as a fitness) to determine the best solutions in the population. The fittest solutions in a population then have a higher probability of passing on information to subsequent generations. After a certain number of generations, or after some stopping criterion is met, the evolutionary process is terminated and the best overall individual is presented as the evolved solution.
Different methods of representing or encoding a solution (representation), creating the initial population (initialization), choosing individuals for reproduction (selection), exchanging information between individuals (crossover), varying individuals (mutation), evaluating individuals’ fitness (evaluation), and choosing individuals for the next generation (replacement) are employed by these algorithms. The canonical overall evolutionary algorithm process cycle is illustrated in Fig. 1.
Figure 1: The evolutionary cycle of a typical evolutionary algorithm. Each block represents an operation on a population of candidate solutions.
Genetic Algorithms
Examples of Evolutionary Algorithms include Genetic Programming, NeuroEvolution, Grammatical Evolution, and Genetic Algorithms. The main difference between EAs such as these typically lies in differences in the representation of the problem.
- Genetic Programming uses tree structures to describe computer programs, with leaf nodes typically being function arguments and branch nodes being functions themselves.
- NeuroEvolution is a popular and powerful method of optimising the architecture of Neural Networks, wherein each individual describes a different neural architecture.
- Grammatical Evolution uses a formal grammar to define a set of rules and choices that is used to map a string of genetic information to a solution.
- Genetic Algorithms (GAs) are a form of evolutionary search and optimisation algorithm that use a binary integer string as a way to encode information for an individual solution (known as a genome/chromosome). A GA genome/chromosome is then directly mapped to an observable set of characteristics of the solution, known as the phenotype.
GAs traditionally represent their chromosomes as a fixed-length binary string, and map directly from genotype to phenotype without the use of an intermediate interpreter (unlike e.g. Grammatical Evolution, which uses a formal grammar in the mapping process). As such, a GA representation is very effective at parameter tuning and in situations where direct variance of values is required, such as the Knapsack problem.