Evolutionary algorithms are often categorised into four main branches that are mainly distinguishable by their commonly used representation and operators: genetic algorithms use a bit-string and two-parent crossover, evolutionary strategies use a real-valued vector and Gaussian mutation, evolutionary programming employs a finite-state machine and mutation operators, and genetic programming uses a computer program or executable structure and two-parent crossover. These classifications represent common or initial implementations. Many implementations use components from different branches and make the classifications less accurate.
The genetic algorithm was originally represented by bit-strings in a fixed length genome. The term genome refers to the bit-string. Early work by Fraser (1957), reprinted in [Fogel, 1998], and Bremermann (1962) provided the foundations of genetic algorithms, which were later popularised by Holland (1975) and DeJong (1975). A bit-string requires a mapping to a representation that can be evaluated and assigned a fitness by the heuristic evaluation function. The genetic algorithm traditionally relied on various forms of crossover as the main operator. For instance, in one-point crossover with bit-strings and with bit positions indexed from , a point is chosen such that . Next, the bit-strings exchange the portions of the string delineated by point so that
Evolutionary strategies traditionally uses a direct encoding of the candidate solution, typically as a vector of real numbers [Rechenberg, 1965,Bäck et al., 2000a]. The method began using a population consisting of a single individual. Offspring are produced by a Gaussian mutation operator and became the new population if they were better than the parent. Population-based evolutionary strategies uses two main selection schemes, the comma or plus strategy. In the (,) version, offspring replace the parents. In the () version, parents and offspring compete to become the new set of parents. Evolutionary programming was originally based on the iterative adaptation of finite-state machines [Fogel et al., 1966]. Finite-state machines are evaluated and assigned a fitness. A mutation operator is usually the only means of variation. In this sense, the population in evolutionary programming is like an ecosystem of species, where each individual is a different species.
Within the evolutionary algorithm framework, specialised methods such as multipopulation models [Cohoon et al., 1987], coevolutionary models [Potter and De Jong, 1994] and memetic models [Moscato, 1989,Krasnogor, 2002] exist to further blend evolutionary algorithms with other local search and heuristic methods. These hybrid algorithms typically combine global search strategies with local strategies, representing the state-of-the-art in optimisation [Davis, 1991,Pardalos and Resende, 2002,Glover and Kochenberger, 2003]. Hybrids allow a general metaheuristic search strategy to be specialised for specific applications. Davis (1991) points out that the two objectives of generalisation and specialisation are conflicting in that increasing the performance of a method for a specific domain is likely to make the same method perform worse on other domains. The ``No Free Lunch Theorems'' by Wolpert and Macready (1997) emphasised this performance trade-off by explicitly stating that the average performance of all methods over all problems will be equal. However, this does not prevent some algorithms from being better than others on particular classes of problems.
Genetic programming is an evolutionary algorithm that represents solutions as programs. The remainder of this thesis will focus specifically on the canonical form of this method and representation.