\chapter{An Overview of Genetic Programming}
\label{ch:gpsurvey}

%http://zhurnaly.com/cgi-bin/wiki/TuringComplete

At certain points in the 20th century, people were especially interested in measuring the ``redundancy'' within languages -- which letters are most repeated, and which words could actually be done without. While the reader may have guessed such information is particularly useful for practitioners of modern cryptography, it also reveals some interesting characteristics about the languages we speak. It turns out that most human languages are about 50\% redundant.

% I can't find a REF for that last quote, although it seems widely known. It seems to be from O'Sullivan, 1994, but I can't find more information than that. 

Although computer software is rather more restricted in its basic vocabulary, the range of solutions to a particular problem that can be expressed in most programmingt languages can be quite diverse. If one were to instruct a hundred programmers to solve a task, one would probably amass a whole range of different approaches to the problem. Some approaches may be better than others. 

Genetic Programming (GP) is a machine learning technique that aims to develop computer software through a similar process of producing redundant software solutions. GP also has the potential, at least, to devise solutions that none of the hundred programmers would have thought of. Fortunately, a squadron of human developers is not required for a process of evolutionary computation -- GP is intended to find solutions in a reasonably automatic manner. In this chapter, the author will cover some of the key aspects of Genetic Programming in detail, starting with the general rationale underlying evolutionary learning algorithms.

\section{The Inspiration Behind Evolutionary Algorithms}
The theory of evolution by means of natural selection (``survival of the fittest''\footnote{First coined by Herbert Spencer in 1864, later integrated into Darwin's 5th Edition of \emph{On the Origin of Species.}}) is the established scientific explanation for how intelligent life came to be on Earth. It is the process by which heritable traits that benefit individuals become more and more common within a species, and heritable traits that disadvantage individuals are rapidly discarded; those individuals with beneficial traits are more likely to pass them on to subsequent generations.

Key to the process of evolution is the variation between members of a species. Although life is filled with instances of good and bad luck, mainly outside of an individual's control, features present in certain individuals but absent in others may cause the former to have a slightly better chance of surviving until breeding, at which point those factors may be passed on, perhaps to spread throughout the species. Although natural evolution is generally not observable during a human life span\footnote{Exceptions do exist: evolution of species of fruit fly introduced into North America have been observed over periods of less than 20 years \cite{fruit-fly-evolution}.}, the cumulative result of this selective process over thousands or millions of generations is a species that has become highly adapted for survival in its chosen environment.

The second key to evolution is the ability of members of a species to store these adaptations reliably. If alternations cannot be recorded, then they cannot easily be accumulated. This is made possible by each individual's genetic material, or DNA, which encodes everything needed to make a perfect replica. A copy of the individual's entire genetic sequence is present in every cell: the genetic material of any multi-cellular organism is massively redundant\footnote{This is a safety mechanism that helps impede the rapid replication of mutated or otherwise damaged cells.}. At the point of reproduction, however, just one set of genes from each parent is required for the creation of a new, genetically distinct, offspring. It is at this point where new variations may be introduced, either following the normal process of combining two sets of parent genes together (recombination, see p.\pageref{crossover}) or the abnormal event where errors occur during the transcription process (mutation, see p.\pageref{mutation}). In either case, the offspring may be more, less or equally capable of survival than its parents, which in turn affects its overall likelihood of breeding. And so the process of natural selection proceeds.

\section{A Very Brief History of Evolutionary Computation}
Almost as soon as the computer age dawned during the middle of the 20th Century, researchers became interested in using machines to simulate the evolutionary process. It soon became apparent that as well as providing insights into the nature of evolution itself, these evolutionary techniques had potential to solve contemporary engineering problems. 

The author will shortly introduce three different evolutionary learning techniques, covered in chronological order, to give the reader some idea of  evolutionary computation's own evolution. Although the techniques exhibit some significant differences, they each share a common evolutionary process, which is shown in Figure \ref{fig:evolution}. The concept is to produce a \emph{population}  comprising a reasonably diverse pool of solutions. Each solution is evaluated against certain metrics, the better ones are selected for ``breeding'' in order to produce new solutions that may become part of a subsequent generation. The process continues iteratively until termination criteria are met.

%\begin{enumerate}
%   \item Produce a population of solutions (p. \pageref{treebuilders})
%	\item Evaluate each one (p. \pageref{fitness})
%	\item Select the best solutions as parents (p. \pageref{selection})
%	\item Produce a new population of offspring (p. \pageref{operators}
%	\item Goto 2
%\end{enumerate}

\begin{figure}[ht]
\begin{centering}
\includegraphics[width=0.8\textwidth]{images/evolution-diagram}
\par\end{centering}
\caption[The Process of Artificial Evolution]{The general process of artificial evolution}
\label{fig:evolution}
\end{figure}

\subsection{Evolution Strategies (ES)}
\label{es}
Once of the first attempts at artificial evolution was the development of an optimisation technique named Evolution Strategies by Ingo Rechenberg in the 1960s and 70s \cite{rechenberg:thesis}. In Evolution Strategies, the population is composed of a number of \emph{individuals}, each typically represented as a vector of real-valued numbers (genes). The values are used to make decisions depending upon the task. The chore of finding optimal values is left to the evolutionary process whose search is driven by a mutation operator. The operator perturbs the values of each gene by adding a normally distributed random value to each, simulating the genetic mutations which cause much of the diversity found in the natural world. The parents then compete with the children for a place in the next generation. In contemporary versions, the learning environment comprises a population of ``parent'' individuals. Following the selection of a number of good parents (the definition of ``good'' or ``bad'' in this sense will be discussed later), a population of offspring is generated using mutation and recombination operators; the mutation operator is the dominant means of producing variance. 

Evolution Strategies has been demonstrated as a useful parameter optimisation technique for certain real-world problems, but is somewhat limited by the simple numeric representation of its individuals. It does not make use of a particularly accurate simulation of natural selection or genetic recombination. ``Classic'' ES uses deterministic (greedy) selection, which always selects the top $n$ individuals to become parents. Although this approach initially appears the best way to arrive at a solution quickly, it also significantly reduces the diversity within the population, since the remaining individuals have a zero chance of reproduction. The mutation operator is used to put diversity back into subsequent generations. In general, reductions in diversity may decrease the rate of learning in later generations, leaving the ES learning system potentially prone to becoming stuck in local optima (Figure \ref{fig:local-minima}). Selection techniques, which usually aim to select better individuals while maintaining diversity, are discussed in more detail in Section \ref{selection}.

\begin{figure}[ht]
\begin{centering}
\includegraphics[width=0.8\textwidth]{images/local-minima}
\par\end{centering}
\caption[Local Minima]{Sometimes solutions are only locally optimal. If the population concentrates its search in these areas too much, it may become unable to progress further towards the global maximum.}
\label{fig:local-minima}
\end{figure}

\subsection{Genetic Algorithms (GA)}
\label{ga}
Following Evolution Strategies were the Genetic Algorithms (GA), popularised by the work of John Holland \cite{Holland:GA}. Holland's work was focused on symbolic as opposed to real-valued representation of individuals. This more abstract approach makes GAs applicable to a wider veriety of different domains. Indeed, Genetic Algorithms are used in a whole variety of different circumstances. Although GA and ES are broadly similar, there are a number of key differences. The most important is that Genetic Algorithms use operators more closely related to our knowledge of genetics, namely crossover (p.\pageref{crossover}), a more realistic mutation operator (p.\pageref{mutation}), and inversion\footnote{Inversion aims to address the need for the function of genes to be independent from their position. It worked by flipping the positions of genes in a section of the individual's chromosome. It is less commonly used in modern GA systems thanks to more sophisticated crossover implementations.}, together with a less greedy selection implementation. 

In essence Holland was more interested in the study of natural adaptation; indeed his technique was a closer simulation of biological evolution than Evolution Strategies. 

\subsection{Genetic Programming (GP)}
\label{gp}
Although Genetic Algorithms are reasonably abstract, their inherently linear nature remains a limitation (which is apparent in other systems based on GAs, such as XCS\footnote{XCS \cite{wilson95classifier} is a classification system which uses a GA as its learning component.}). Genetic Programming is an extension of the GA algorithm such that individuals are represented not as vectors of values, but as syntax trees (programs) which can express non-linear logic in the form of computer programs. Therefore, Genetic Programming is not a parameter optimisation technique but a method for automatic programming.

Although several researchers investigated the automatic evolution of \emph{programs} during the 1980s, the modern concept of Genetic Programming is based the work of John R. Koza who published a tome of research on the topic in the early 1990s \cite{EvoVision:Koza:1992}.

The primary difference between Genetic Programming and Genetic Algorithms is the differentiation between \emph{phenotype} and \emph{genotype}. The genotype refers to the encoding of the solution (in nature this is the genetic material, the DNA) with the phenotype relating to the realisation of that solution; the eventual organism and its behaviour. In nature -- and Genetic Algorithms -- these are distinct: the GA's symbolic genes must be interpreted in some way when applied to domain-specific problems. In Genetic Programming they are often the same, so the programs being evolved may be used directly (although this need not necessarily be the case). Genetic Algorithms, therefore, are somewhat restricted to discovering parameters required by certain models to solve a problem; Genetic Programming can be used both for optimisation and the discovery of the model. We shall come back to this distinction later in this thesis -- sometimes a separate phenotype is beneficial.

%In common with genetic algorithms, the genetic programming process is an iterative one in which successive populations are generated following some kind of artificial selection which ensures the search is not purely random. 

%The GP procedure is as follows:

%\begin{enumerate}
%\item An initial population of individuals is created in some way.
%\item Each individual is evaluated against some kind of criteria and has a fitness value assigned to it.
%\item ``Parent'' individuals are selected from the population with probability proportional to their fitness. Two parents create offspring using either the crossover or mutation operators. The offspring are inserted into a new population.
%\item When the new population is the same size as the old one, the old one is replaced and the process of evaluation starts again.
%\end{enumerate}

\section{Components}
Evolutionary learning systems usually comprise a number of core components necessary to simulate the process of artificial evolution. In this section, we shall cover in detail four of the most important components with respect to Genetic Programming. This section is intended to give the reader an appreciation of the current areas of research in Genetic Programming and some of its strengths and weaknesses with regard to:

\begin{itemize}
\item The Representation and Creation of Individuals
\item The Evaluation of an Individual's Fitness
\item The Selection of Individuals
\item The Choice of Genetic Operators
\end{itemize}

For a more thorough, beginner-level introduction to Genetic Programming, the author recommends the ``Field Guide to Genetic Programming'' by Poli, Langdon and McPhee \cite{gpfieldguide}.

\subsection {The Representation of Individuals}
\label{tree-representation}

The purpose of each GP individual is to represent program code, so that the evolutionary process can search for the program code that best solves a particular problem. GP researchers generally adopt one of three main approaches to represent code. One of which is a linear representation, in which each individual is composed of a  list of commands, see Nordin \cite{linear-gp}. These commands are usually low-level in nature, and may be used to develop machine-code programs. Linear representations are simpler to implement, as they rely on a more straightforward data structure, but also suffer some drawbacks: it may be more difficult to ensure the program performs meaningful computations (see page \pageref{strong-typing}).

The more common approach in Genetic Programming is to express programming code using a tree structure (see Figure \ref{fig:example-tree}). The tree consists of a series of nodes which represent programming functions and inputs. The leaves of the tree are referred to as \emph{terminals}, through which input values are provided to the program, either in the form of data acquired from some process or as constants. The remaining non-leaf nodes in the tree take any child nodes as input parameters and perform some processing action on them, and are referred to as \emph{function} nodes. Execution starts at the top \emph{root} node whose children are then traversed recursively. In many cases, the output from the root node is taken as the output of the program. The ``size'' of a program is usually defined as the number of nodes in its tree. The tree may be extended into a graph (also known as graph-based GP \cite{poli:1997:PDGP}) such as to represent more complex dynamics, such as loops (see Teller and Veloso \cite{teller:1995:PADO} or Shirakawa \emph{et al.} \cite{graph-gp}). However, graph-based GP is less able to support strong-typing and it is more difficult to ensure that programs are efficient.

The advantage of tree-structures is that they permit the dependencies and types of each node to be taken into account more carefully (see page \pageref{strong-typing}), and that they are better able to handle functions which may require different numbers or types of arguments. In this thesis, the reader may assume ``genetic programming'' refers to ``tree-based genetic programming''.

\begin{figure}[h]
\begin{centering}
\includegraphics[width=0.25\textwidth]{images/tree-diagram}
\par\end{centering}
\caption[An Example Genetic Program Tree]{An example tree whose function is equivalent to $x = R / (G + B)$.}
\label{fig:example-tree}
\end{figure}

% *** TODO: Mention the tree builders - is there any best one - research papers.
\subsection {The Creation of Individuals}
\label{tree builders}

As was shown in Figure \ref{fig:evolution}, the first stage in an evolutionary computation run is to produce an initial population of programs. Since the system has no means of guessing the solution to a problem, the process is largely random. The expectation is that within the randomly generated population there will be some ``good ideas'' which can be built upon in subsequent generations. In Genetic Algorithms, the production of random, fixed-length sets of constants or symbols is straightforward, but the nature of GP's tree representation makes the process rather more complex.

Koza proposed three methods for creating random program trees, given a set of function and terminal nodes, and a \emph{maximum-depth} parameter which sets an upper bound on the size of the tree. The process in each case is similar: add children to the root node until its constraints are satisfied (for instance: ``I require two children as arguments''), then apply the same process to each child of the root node and so forth. 

\subsubsection{GROW Builder}
\label{grow-builder}
Given a set of function nodes and terminals, the GROW builder selects one at random to produce the root node. If the root node requires children then these are added in a similar fashion, until terminal nodes have ``completed'' every branch. The GROW builder is simple to implement and can run in linear time, and is commonly used in Genetic Programming toolkits. Since the tree generation process is largely unconstrained, the builder can generate a variety of regular and irregular tree structures, that is to say tree structures whose branches \emph{all} extend to the maximum depth, or those trees whose branches do not. However, the size of trees generated by the GROW builder is dependent upon the ratio of function nodes to terminal nodes. If the function nodes have arity $n$, then if the proportion of function nodes to terminal nodes equals or exceeds $1/n$, then the GROW builder becomes likely to produce trees of infinite size! For this reason a maximum depth constraint $D$ is usually imposed -- if the depth is about to exceed $D$ then the GROW builder selects a terminal to complete the branch.

\subsubsection{FULL Builder}
\label{full-builder}
Koza's second tree builder \cite{EvoVision:Koza:1992} works similarly to GROW, with a small addition which causes it to build ``full'' trees in which every branch extends to the maximum permitted depth $D$ (see Figure \ref{fig:fulltree}). This is implemented by selecting function nodes on \emph{all} occasions except where their addition would bring the branch beyond the depth $D$. There are some comments that one could make about such a builder. Insisting upon a particular depth for trees appears slightly restrictive, especially considering that there are fewer full-trees than there are irregular trees. The full-ness constraint may reduce the thoroughness with which the search space is explored.

\begin{figure}[ht]
\begin{centering}
\includegraphics[width=0.66\textwidth]{images/full-tree-diagram}
\par\end{centering}
\caption[ ``Full'' Trees]{The distinction between a ``full'' tree (left), where all the branches extend to the maximum depth, and a tree developed by the GROW builder, in which some or all the branches may terminate before reaching the maximum depth (right). There are more ``unfull'' trees than there are ``FULL'' trees.}
\label{fig:fulltree}
\end{figure}

\subsubsection{The Ramped Half-and-Half Population Builder}
\label{ramped-half-and-half}
Although the GROW builder is able to produce both full and under-full trees, it suffers from one drawback, namely that the probability of reaching a particular tree size/depth is linked to the proportion of terminals and non-terminals. Similarly, the FULL builder is perhaps overly restrictive for particular depths. To mitigate the disadvantages of each technique, Koza proposed a strategy to use both while generating populations. Given a minimum depth $D_{min}$, a maximum depth $D_{max}$ and a required population size $N$, roughly $N/(D_{max} - D_{min})$ trees at each depth $D_{min}, \cdots, D_{max}$ are generated, half using the GROW builder and half using the FULL builder. However, as the author will assert later in this thesis, the ramped-half-and-half builder still suffers the drawbacks of each builder. The GROW builder's behaviour is affected by different terminal sets, which clearly will have implications for any generic system. Later in this thesis we will examine how to mitigate some of these problems.

\subsubsection{Strong Typing}
\label{strong-typing}
Koza's early function sets tended to use nodes of the same ``type''. A set composed of, for instance, the mathematical operators ${+,-,\times,\div}$ and a series of numeric terminals ${x_1, x_2, \dots , x_n}$ are all compatible with each other, since every node returns a numeric value and every function requires numeric inputs. However, more complex programs demand extra types. If one wanted to introduce an $IF(\cdots)$ function (see Figure \ref{fig:if-node}), for instance, then it may still return a number dependent on the branch it chose to execute, but its condition would have to be \emph{boolean}. 

\begin{figure}[h]
\begin{centering}
\includegraphics[width=0.33\textwidth]{images/if-diagram}
\par\end{centering}
\caption[$IF()$ Statements in GP]{An $IF()$ Statement in GP. The first branch is the condition, which decides which of the other two branches will be returned as the node's output. Nodes in this tree use two different types: boolean and numeric. The code statement here is used to implement a $max(A,B)$ function, a useful non-linear transformation.}
\label{fig:if-node}
\end{figure}

Although Koza proposed a clunky solution to the problem, an early deviation from his original implementation was the addition of \emph{strong typing} by Montana  \cite{EvoVision:Montana:1993} which permitted the use of different data types within the same tree. Strong typing is a common feature in many programming languages: it prevents the compilation of code that may be semantically incorrect. As the search space will consist of a number of potential useful solutions but a much larger number of useless ones, the technique is also useful in preventing GP from needlessly evaluating senseless trees and sub-trees.

Strong typing is implemented in the tree building and search operators of the GP system, each of which must ensure that nodes which expect certain types are satisfied. For instance it may be specified that an \emph{add()} node should only take numeric inputs; the GP system will then honour this requirement. The author's toolkit has extended this concept further, which will be explained in Chapter \ref{ch:gpcomparison}.

\subsubsection{Other Tree Builders}
The generation of trees is important -- the algorithm employed inherently defines the extent to which the search space can be explored. Nonetheless, tree builders are a somewhat neglected aspect of GP research. Since Koza's initial work, only a few authors have proposed alternatives.

Iba \cite{iba96} developed a tree builder named \emph{RAND_tree}, which built uniform trees from the bottom up, joining nodes then sub-trees together such as to build a single tree. This type of approach permits the user some control over the \emph{size} of trees created. However, although depth \emph{limits} size, the average size at a given depth remains dependent on the function and terminal sets. Iba's approach is less easy to implement with strong typing, and takes longer to produce trees than does the simpler GROW method, which can execute in linear time.

Luke \cite{luke-tree-creation} made a study of tree builders and developed two algorithms (named PCT1 and PCT2) which could run in linear time but still offer greater control over the average tree size to the user. Luke's PCT1 algorithm starts by calculating the probability $p(t)$ of selecting a terminal (rather than a node) such that the average tree size would be $s$. Given $F$ functions, each with arity $a_i$, that have equal probability of being selected, $p(t)$ is:

\[
p(t) = \frac{1-\frac{1}{s}}{\displaystyle \sum_{i=1}^F \frac{1}{F}a_i}
\]

Luke's PCT algorithm is otherwise identical to the GROW algorithm, except that the functions and terminals are divided into two sets. The probability that a given node is selected from the terminal set is $p(t)$, otherwise it is chosen from the set of functions. Of course, this algorithm does not guarantee that trees will \emph{always} be of the user's preferred size, they will only be of size $s$ on average; indeed there may be significant variance between different trees generated by PCT1 and the likelihood remains that there will be significantly more small trees than large trees, which may account for redundancy in the population.

In order to enforce a more fixed size constraint Luke suggested another algorithm, PCT2, which could generate trees with to fit both a given average size and a given size distribution. PCT2 starts by choosing a random tree size $s_r$ from the user's preferred probability distribution, then builds a tree to match. The tree is built by adding non-terminals at random to open branches of the tree until the tree size + the required number of terminals to ``complete'' the tree equals or exceeds $s_r$. At this point, terminals are added to the end of each branch to finish the tree.

Both PCT1 and PCT2 can be extended to support strong typing, although this may sometimes conflict with $p(t)$. As we have seen so far, there is no such thing as a perfect tree-creation algorithm, although Luke's builders would appear to solve some of the problems of GROW and FULL. Still, each can produce redundant trees -- trees that are identical to others in the population, because certain tree depths have a limited number of possible tree combinations which is less than the proportion of the population assigned to a particular depth. The author will make additional contributions later in this thesis with regard to ensuring that random populations do not exhibit as much redundancy.

\subsection {The Evaluation of an Individual's Fitness}
\label{fitness}

Nature implements rather a blunt evaluation of an individual's fitness: the organism will either die before breeding (perhaps following a confrontation or another of life's unpleasantries), in which case its genes will disappear from the population, or it will survive sufficiently long as to reproduce, at which point its genetic heritage is secured for one more generation.

Essential to any \emph{artificial} system which learns through a process of simulated natural selection is some kind of ``fitness'' function that describes mathematically the performance of a program. This permits direct comparisons to be made between individuals such that some may be selected for breeding. GP generally discovers solutions using a supervised learning paradigm, using a human-generated set of training data that has been marked with appropriate classes. Individuals are then measured by their ability to emulate the human decision making process.

If one is to develop a GP program for the purposes of pattern recognition, then the fitness of an individual should be proportional to the number of patterns that it can classify correctly, or rather the proportion of times with which its output agrees with the human decision. Although humans usually associate higher performance with a higher ``score'', in Genetic Programming the reverse is the case: fitness is usually measured by counting the number of mistakes. This means that a fitness value of zero signals that the ``perfect'' individual has been found. In this case the term ``fitness function'' is something of a misnomer: ``error'' or ``cost'' function is more accurate.

\label{error1}
The most straightforward fitness function is defined as follows. Given a set of classes $C = \{c_1,...,c_n\}$ and a set of samples \{$(x_1,y_1,w_1),...,(x_n, y_n, w_n)\}$, with each sample comprising a feature vector $x \in X$, the correct class $y \in C$, and a corresponding weight $w$ . The fitness of function $f : X \rightarrow C$ may be calculated as:

\[
error_1 = \displaystyle\sum_{i=1}^N w_i [f(x_i) \neq y_i)]
\]

In other words, $error_1$ sums the weights of samples mistakenly classified. In the author's experience this kind of fitness function performs well, in spite of its apparent simplicity. Since the function is calculated using only one measure, it is possible that a number of classifiers may be assigned identical fitness; in which case the selector (see page \pageref{selection}), when faced with two or more equally fit individuals, will choose the smallest. The training data error is thus the overriding factor in determining an individual's fitness; other desirable features are secondary. We shall see alternate means by which competing criteria may be accommodated later in this section.

\paragraph{Different Errors, Different Costs}
\label{fitness-bias-ratio}
Some problems demand slightly more complex fitness functions which permit certain adjustments to be made, usually relating to the relative cost of making different kinds of mistake. A classifier can generally make two types of mistake: either a \emph{false positive}, where a sample from another class is incorrectly identified as the class in question, or a \emph{false negative}, where a genuine sample from the class in question is not identified as such\footnote{Although the false negative in one class may be a false positive for another.}. In some cases, notably medical diagnosis or credit management, the cost associated of each kind of mistake is different. When diagnosing disease the false positive may be alarming to the patient but is substantially less costly than the false negative, which can leave a person unaware of a potentially serious health problem which, upon its eventual discovery, would no doubt leave the indivudal much worse off and the medical establishment facing a substantial claim. 

The relative importance of different mistakes can be encoded by introducing extra coefficients $\alpha$ and $\beta$ into the fitness function. An example, used by Roberts \& Howard \cite{roberts:1999:evdIRLI}, is:

\[
error_2=\frac{\alpha TP}{\alpha N+\beta FP}
\]

\noindent where $TP$ is the number of correctly classified samples (true positives), $FP$ is the number of incorrectly classified samples (false positives), and $N$ is the size of the training set. This fitness function produces a one-dimensional bias in favour of either sensitivity (maximising the true positives), or specificity (minimising the false positives) depending on the ratio of $\alpha$ and $\beta$. This provides an additional level of control that may be useful in tuning the system for problems in which outcomes have different costs. For example False Positives are acceptable for a cancer screening application, provided that the sensitivity is at or around 100\%. 

\paragraph{Extra Embellishments}
Penalties or rewards may be added to the fitness function to provide incentives for certain behaviours. For multi-class problems, the fitness function may include a penalty if at least one sample from each class is not classified (see Teredesai \cite{teredesai:2004}). Although the principle of ``guiding'' the classifier in this way may yield desirable outcomes, such a penalty also creates a large fitness-step which may be disproportionate to the improvement in ability. In Chapter \ref{ch:gp-classification} we'll see some of the other approaches to multi-class classification by GP.

\paragraph{Parsimony Pressure}
Interestingly, the author's experiments have shown that the most effective fitness function is often $error_1$, which, as we have seen, simply sums to the number of mistakes out of the total training samples. It might well have been the preferred technique of William of Ockam, the 14th century logician, had he been born six hundred years later and with an interest in evolutionary computation. Ockam's benchmark principle, now known as Occam's Razor, states that the simplest solution is usually the best one\footnote{The modern interpretation is slightly different to the original principle: ``\foreign{entia non sunt multiplicanda praeter necessitatem}''. which roughly translates to ``entities must not be multiplied beyond necessity''.}. Simple fitness functions, however, do not necessarily yield simple, parsimonious solutions. In fact Genetic Programming is rather prone to producing over-complicated solutions to problems, described as ``bloat'' (covered in more detail in Chapter \ref{ch:gpcomparison}). Unlike GA individuals, which generally use fixed-length chromosomes, there is no arbitrary limitation on the size of GP trees, so they can grow considerably. Parts of trees which do not contribute to fitness are described as \emph{introns}\footnote{The term is borrowed from genetics, relating to DNA portions in genes which apparently do not perform any function during the production of proteins.}. Introns are undesirable as they can reduce the efficiency of the learning process.

For this reason, a parsimony component is sometimes added to the fitness function, the size of the penalty depending on the individual's tree size. This creates a fitness pressure towards smaller, simpler individuals. The extent to which parsimony is pressurised is determined by a parsimony coefficient $c$, the choice of which requires deliberation of its own. Parsimonious fitness functions are composed of a regular fitness metric $f$ plus an additional penalty associated with the individual's size $s$:

\[
error_{parsimony}=f+cs
\]

Of course, particularly large values of $c$ will cause the program to treat size as its main objective and ignore $f$ altogether! Poli and McPhee \cite{Poli:2008:geccop} suggested a means by which $c$ could be calculated automatically in order to maintain a given average population size.

A further discussion of fitness with more specific regard to machine vision problems awaits the reader in Chapter \ref{ch:gpcomparison}.

%Competitive selection, doesnt use fitness (Tettamanzi, 1994)
%Tournament selection, attributed to Wetzel (never published), first mentioned in Brindle (1981)
%Fitness on a per-class basis?

\paragraph{Multi-Objective Optimisation}
\label{moo}
We have now seen a couple of examples where two objectives are incorporated into a unidimensional fitness function. In the case of classification $error_1$ is quite often sufficient. However, research into multi-objective optimisation (MO-O) deserves a mention here, not least because of the desire in some cases to gold-plate the definition of a useful solution with other beneficial characteristics. The crucial problem with MO-O is that it isn't possible to define ``optimum'' in a scalar way given two or more objectives, since different criteria will usually conflict with each other. In most cases it is only possible for individuals to represent good compromises rather than globally optimal solutions. These individuals, which represent the best possible trade-off between two or more criteria, are said to lie on a \emph{Pareto Front}. 

It is necessary, therefore, to consider the optimal solution instead as a \emph{set} of solutions.
Evolutionary algorithms are particularly suitable in this regard because they deal simultaneously with populations of possible solutions. Two issues immediately arise: how to define the local optimality of solutions, and how to ensure that the population does not become dominated by a single solution. Various approaches have been proposed which fall into two broad categories. 

%NSGA = Non Dominated Sorting Genetic Algorithm

The main approach to multi-objective optimisation are the \emph{Pareto-based} approaches which do not attempt to define a fitness term which can never be optimal. Rather they evaluate individuals according to their proximity to the Pareto front, which is based on the concept of \emph{dominance}. An individual is said not to be dominated if there exists no other individual in the population that can improve a given objective without causing a simultaneous reduction in another objective. An individual is Pareto optimum if there exists no feasible individual that can do this. There many be many or an infinite number of Pareto optimal solutions; these are distributed along the Pareto Front. There are rather more solutions than necessary: popular GA toolkits such as NSGA-II try to ensure that individuals in the population are distributed over the Pareto front. The problem, as ever, is that assessing non-dominance is computationally expensive, especially for large populations or large numbers of criteria. 

It has been established that Pareto optimal solutions may be discovered using a scalar, rather than multi-objective measurement of fitness, in which the objectives are all aggregated into a single criterion. There are various approaches to doing this. Syswerda \cite{syswerda} used an approach where the fitness with respect to each criterion is measured, then combined together in a weighted sum. The question then becomes how best to define the weights for each criterion -- another optimisation problem!. So-called lexicographic ordering (Fourman \cite{fourman85}) is more readily definable -- the objectives are placed in order of importance. In a competition between two individuals, the first objective is compared first; in the event of a tie the individuals are evaluated  against the second criterion and so forth. This approach works well provided there are few objectives -- objectives too far down the pecking order are unlikely to be taken into account at all. Schaffer suggested evaluating different sub-populations with different fitness functions, an idea later implemented by Fonesca \cite{fonesca93}. The consequence of this technique is that it selects individuals that can excel with regard to one criterion, but not necessarily both. 

%Zhang proposed a multi-objective algorithm entitled MOEA/D, which works by decomposing the multi-objective problem into scalar sub-problems which are then solved simultaneously.
%http://dces.essex.ac.uk/staff/qzhang/papers/moead.pdf

This completes a very brief survey of multi-objective optimisation. Later in this thesis the author will touch upon a couple of multi-objective fitness functions: however in general the addition of extra criteria inevitably harms the accuracy of the solution in classification. Other criteria, such as efficiency, are desirable extra characteristics, but we will see that there are other means to address bloat without compromising the fitness function.

\paragraph{Generality and Validation Sets}
While the fitness function exists to measure the accuracy of a GP solution on a set of training samples, it does not necessarily indicate how robust or general the solution may be on data that it hasn't seen before. 1-Nearest Neighbour algorithms, for instance, are immediately capable of 100\% accuracy on training data, but may fail to achieve decent results on test data\footnote{k-Nearest-Neighbour may also be slow to run on large data sets, although a Best-Bin-First (BBF) (see Beis and Lowe \cite{beislowe97}) algorithm can be employed to speed up the distance matching.}.

Initial experiments using Genetic Programming reported the performance of the evolved programs on the same data sets that had been used to train them, a practice which gives little indication of the actual robustness or usefulness of the evolved algorithms. Later research split data sets partitioned into training and validation partitions, with the latter used to provide a better indication of the performance on unseen data. We shall take a closer look at validation data later in this thesis.

Another means of encouraging ``generalists'' is to evaluate the individual on a series of different datasets (or in the case of machine vision, images), and calculate the fitness individually for each. The individual's \emph{worst performance} is then used as its overall fitness (see Ebner \cite{ebner:2001:colour-constancy}). This removes some of pressure towards \emph{over-fitting} the training data, which usually degrades the program's ability to generalise and is an issue with non-parametric learning methods.

% Three set training data
% ``Genetic Programming, Validation Sets and Parsimony Pressure'', Desktop

\subsection {The Selection of Individuals}
\label{selection}

One of the primary concepts of Darwin's theory of evolution by natural selection is that species become better adapted to their environment by ``survival of the fittest''. Artificial evolutionary learning systems, therefore, are motivated to select ``better'' individuals while discarding ``worse'' individuals. After the fitness of each member of the population has been computed, certain individuals are then selected to be ``parents'' of the next generation. The characteristics of good individuals are thus more likely to re-appear in subsequent populations, at which point the genetic operators will attempt to refine them further.

In this chapter we have already encountered so-called \emph{deterministic} selection (also referred to as \emph{truncation} selection), used by Evolution Strategies, in which the top $n$ individuals in the population are guaranteed to be selected as parents. Indeed, given the extremely limited computational resources available in the 1960s, this was probably the only efficient means of getting a solution. However, selection methods are guided by a well-known principle which states:

\begin{quotation}
\noindent ``The rate of increase in fitness of any species is equal to its genetic variance in fitness.''
\em R. A. Fisher, 1958 \cite{EvoVision:Fisher:1958}
\end{quotation}

\noindent So if deterministic selection chooses the best $n$ individuals in the population, all other individuals have a zero probability of being involved in breeding. This means that the variation in subsequent populations is derived from only a small, fixed subset of individuals in the current population, and over time the diversity may be severely curtailed, although the genetic operators will continue to reintroduce diversity. Diversity in the population may be better maintained if each individual in the population is permitted at least some chance of reproduction. 

At the heart of the selection process, therefore, is a dilemma concerning the desire both to utilise the most successful individuals immediately and to preserve the diversity of the population as a whole -- which may come in useful at a later stage. Good selection algorithms should incorporate both a bias in favour of better individuals and sufficient randomness as to maintain a broad range of different solutions within the population.

Three main selection algorithms are in common usage in the GP community: Fitness Proportional Selection, Rank Based Selection and Tournament Selection, which shall be discussed in turn.

\paragraph{Fitness Proportional Selection}

As its name suggests, this technique selects individuals from the population with a probability proportional to its fitness. This may be implemented in practice using stochastic sampling (``roulette wheel'' selection), in which a number of ``markers'' are assigned to each individual, the number proportional to its fitness. To select an individual from the population, a marker is randomly chosen and the individual associated with that marker is selected. Sampling is repeated $n$ times until a sufficient number of parents have been selected. Dependent on the resolution of the stochastic sampling, some individuals may have such low fitness that they are not assigned a marker at all, so the technique is biased. Unless sampling is made without replacement, there is the potential for a single, very fit individual to dominate the breeding population -- at the expense of diversity.

For these reasons, Stochastic Universal Sampling (SUS) was introduced by Baker \cite{baker87}. In SUS, the individuals are shuffled before being placed on the roulette line with each marker a fixed distance from the last (see Figure \ref{fig:sus}). The markers are then chosen all at once. Each individual has a non-zero chance of selection, and the selection of individuals is fast. SUS has zero bias, and reduces the potential for a single individual to remove all the diversity.

\begin{figure}[ht]
\begin{centering}
\includegraphics[width=0.8\textwidth]{images/sus}
\par\end{centering}
\caption[Stochastic Uniform Sampling]{Stochastic Uniform Sampling. Each individual is allocated a given width on the line, according to its fitness. Individuals are shuffled then placed on the line. A set number of markers is placed along the line, equally distributed. The number of markers associated with each individual determines the number of times it may be involved in breeding.}
\label{fig:sus}
\end{figure}

Still, even the enhanced forms of fitness proportional selection suffer from two further drawbacks: an individual with an unusually high fitness remains likely to dominate the intermediate parent population at the expense of diversity; and fitness proportional selection does not provide a means of adjusting the \emph{selective pressure}.

\paragraph{Rank-Based Selection}

This algorithm is similar to fitness proportional selection, except that the raw fitness is discarded in favour of the \emph{rank} of an individual, following the sorting of the population by fitness. The individuals are ranked in descending order. The index $j$ of the selected individual may be chosen according to the following formula by Whitley \cite{whitley89genitor}:

\[
j=\left\lfloor
\frac{N}{2(c-1)}\left(c-\sqrt{c^{2}-4(c-1)r}\right)\right\rfloor \]

\noindent The variable $c$ determines the selective pressure, or the slope of the linear distribution. $N$ refers to the size of the population. The function converts the output of $r$, a uniform random number, into a linear distribution which is more likely to select lower-indexed, fitter individuals in the population. 

Rank-Based selection has, therefore, two advantages over Fitness Proportional Selection: the selective pressure can be adjusted, and the selection technique is less prone to outlying fitness values. However, the sorting of the entire population introduces an additional computational overhead.

\paragraph{Tournament Selection}
\label{tournament-selection}

Arguably the most commonly used algorithm used for selection in evolutionary learning systems is Tournament Selection, on account of its simplicity to understand, model and implement, both on a single machine and on parallel systems. 

Tournament selection consists of two stages: sampling and selection. $t$ individuals are sampled from the population, the most fit among which is selected as the winner. The selective pressure may be increased by using higher values of $t$. The choice of tournament size $t$ determines the probability that an individual will be sampled at all (discussed by Poli \cite{poli:2005:foga}) and also affects the diversity and quality of the next generation. $t=1$ tournament selection is akin to random search -- diversity will be maintained but there is no selection pressure at all. When $t$ approaches $N$ (the number of individuals in the population) the best individual in the population will come to dominate the parental population, but any diversity in the subsequent generation will be severely curtailed. It is therefore necessary to choose a reasonable value of $t$, which (in combination with $N$) defines the selective pressure.

Tournament selection does produce a sampling bias. There is a chance, due to the random nature of tournament selection sampling, that an individual may never be selected. This probability can be calculated as:

% This is Xie, Zhang and Andreae \cite{xie:zhang:andreae}'s formula, but mine is neater.
%\[
%p_{selected}=1-\left(\left(\frac{N-1}{N}\right)^{N}\right)^{t}\]
%

\[
p_{notselected}=\left(1-\frac{t}{N}\right)^N\]

The formula assumes that the number of tournaments is equal to $N$, which is true in standard evolutionary breeding process where one parent produces one child via mutation and two parents produce two children via crossover. In a population of 500 individuals with a tournament size of 2, the probability of an individual not being selected is 13.5\% (which is relatively constant for different values of $N$). Therefore 13.5\% of individuals are evaluated even though the result of the evaluation, their fitness, is never used: they never compete in a tournament.

One solution, first suggested by Poli \cite{poli:2005:foga}, is that individuals which are not included in any tournament should not be evaluated. To do this, Poli pre-calculated the memberships of a series of tournaments across a given number of generations (in the form of a graph), so that individuals not participating need not be evaluated, or indeed created. Although this is a tidy scheme which does avoid unnecessary fitness evaluations, it is perhaps slightly overkill in the case of evolved vision: the \emph{creation} of individuals will generally take only a fraction of the time it takes to evaluate individuals on image data.

%Firstly, the computational savings are apparent only in the ultimate generations as the probability that all individuals in earlier generations must be evaluated tends toward certainty. Secondly, 

A simpler scheme was suggested by Xie, Zhang and Andreae \cite{xie:zhang:andreae}, named ``evaluated-just-in-time'' where individuals are evaluated only once they enter a tournament. While certain individuals are still created but never evaluated, the authors pointed out that the bulk of computational expense comes from the evaluation rather than the creation of the individual. %In the field of image processing, covered by this project, this holds particularly true.

Perhaps the ideal solution is to ensure that the problem of sampling effects leading to selection bias does not arise in the first place, this should be better able to maintain diversity and makes use of the entire population. Sokolov and Whitley \cite{sokolov:whitley2005} suggested a different form of tournament selection termed uniform tournament selection. If each individual is located according to its index $i$ in a population of size $N$, where $i \in I$ and $I = \{ 0,1,2,\ldots,N-1\}$. Each individual is allocated a tournament partner whose index $p_i$ is selected such that $p_i \in I$ and $p_i \neq i$. The individual at index $i$ then competes with the individual at $p_i$. This guarantees each individual at least two tournaments. The best individual in the population will be selected exactly twice, and the worst individual will not be selected at all.
This is the same idea as suggested by Goldberg \cite{goldberg:89g}. However, the value of $t$ is then fixed at 2; it can be extended to higher values of $t$, but ensuring that tournaments are unique becomes messy.

%Hmm, reconsider the whole of the following:

%In this author's opinion, there exists a simpler solution. Each of these techniques assumes a tournament size of 2 is ideal, which is true in terms of maximising variance which should have an effect on the potential learning rate. It is the standard tournament size in Genetic Algorithms, However, the tournament size is appropriate only in terms of the population size in total. If the population size is very large and the tournament size is small, then the selective pressure will be low which will cause the learning rate to be slow. Through experiments, we discovered that a 500 individual population with $t=7$ (the standard size in Genetic Programming) slightly outperformed one with $t=2$. An increased tournament size increases the chances of an individual being chosen: with a population size of 500, the chance of any individual not being chosen is 0.08\%, (0.43 individuals per generation would not be sampled), causing the sampling problem to become insignificant.

\paragraph{Island Models}
\label{island-selection}

Although more applicable to the evaluation of fitness than to selection, it is certainly the case that evolutionary algorithms require more computational resources than other learning systems owing to the wasteful nature of the search process itself. Fortunately, evolutionary algorithms may also be executed in parallel with relative ease as the time-consuming evaluation of individuals can be delegated to other machines. The relatively fast process of selection and recombination can be left to a single machine.

A different form of parallelism, implemented using a so-called island model (see Pettey \emph{et al.}\cite{island-model}), may also be implemented in software, this time to increase diversity and decrease premature divergence. Again inspired by observations from nature\footnote{It is a common observation that distinct species arise following geographic separation, for instance the Galap{\'a}gos Islands Iguana or, closer to home, the four-horned Loghton sheep, which is unique to the Isle of Man.}, the island model presumes that if the population is split into sub-populations then each may tread a different path through the search space. Allowing the sub-populations to inter-breed occasionally may help share the expertise of each sub-region while maintaining more diversity that might otherwise be the case in a single population.

\subsection {The Genetic Operators}
\label{operators}
Following the evaluation and selection of individuals, new programs are generated by adjusting or combining the parents in order to find new and better solutions. In Genetic Programming, these adjustments are usually performed by two key operators: crossover and mutation.

\subsubsection{Crossover}
\label{crossover}

The main genetic search operator employed in Genetic Algorithms, and subsequently Genetic Programming, is crossover, a process inspired by genetic recombination in the natural world. In essence, two parent genomes are combined in such a way as to create a new individual that is similar to but genetically distinct from both parents (see Figure \ref{fig:crossover}).

\begin{figure}[ht]
\begin{centering}
\includegraphics[width=0.66\textwidth]{images/crossover-diagram}
\par\end{centering}
\caption[Crossover in Action]{The crossover operation. Given two parents, a point on each is selected as the crossover location. The sub-trees are then swapped between parents to yield two distinct offspring.}
\label{fig:crossover}
\end{figure}

``Standard'' crossover is a simulation (and gross simplification) of the operation that happens during sexual reproduction. It works by selecting one sub-tree from each of two ``parent'' trees  at random\footnote{If the trees are strongly typed, constraints may be applied to ensure that both trees are compatible.}. The sub-trees are then exchanged between the parents to produce either one or two new individuals. These ``children'' are subsequently inserted into the new population. 

The reasoning behind crossover stems from the idea that fit individuals are composed of useful ``building blocks''. By exchanging building blocks \emph{between} individuals, the system may find new and improved building block combinations which yield fitter individuals. In most Genetic Programming systems, crossover is the dominant search operator, the main driver behind the search process. The advantages of crossover were analysed by MacKay \cite{EvoVision:MacKay:2003}, who showed that it permits useful sub-trees to spread rapidly through the population while rapidly removing unhelpful ones.

%TODO: Can the GA genes be dependent to?

Common Genetic Programming wisdom, inherited from Genetic Algorithms, suggests that crossover is the best operator for genetic search. However, Genetic Programming and GAs differ in various significant ways, chief among them being that the nodes in a GP tree are not independent: the output of a parent node is dependent on the output of its children\footnote{The author acknowledges that genes in Genetic Algorithms can also be dependent in certain circumstances.}. Therefore, a single change lower down the tree can ``break''  the entire individual. Crossover, therefore, is rather a blunt instrument, since it exhibits no intelligent strategy for selecting \emph{suitable} crossover points. The random means by which sub-trees are selected may result in  otherwise fit programs being severely disrupted. Experiments by Nordin \emph{et al.}  \cite{nordin:1996:aigp2} showed that the average fitness of child programs is less than half the fitness of the parents following about 75\% of crossover events for certain tasks: standard crossover often has decidedly injurious effects! Furthermore, if the mean population fitness is reduced, then the few remaining fit individuals will be selected more and more often, leading to a reduction in population diversity.

A second consequence of this harmful behaviour is that individuals with higher proportions of useless code (that is to say code that does not contribute towards the individual's fitness), are more likely survive crossover intact. This is one explanation of code \emph{bloat} in Genetic Programming.

The main explanation of bloat in GP is the so-called crossover bias theory. Although crossover should not change the average size of a population, it is observed the distribution of trees produced by crossover is characterised by substantial numbers of very small programs, due to the bias of the operator to choose nodes from near the leaves of the tree. For most non-trivial problems it is unlikely that very small individuals will be able to solve the task satisfactorily: the larger individuals will be fitter, on average. The theory states, therefore, that there arises a selective pressure in favour of larger programs.

Crossover also provides the \emph{mechanism} by which bloat may be introduced: in GAs the two alleles swapped are always the same size; but in GP they may be between sub-trees of different sizes, which provides a means for programs to grow and grow. Approaches to controlling code bloat will be described in further detail in Chapter \ref{ch:gpcomparison}.

Poli and Langdon \cite{poli:1998:crossover} demonstrated through modelling and empirical investigations that standard crossover was also local and biased. Local search generally yields offspring which are not very different from their parents, and may not provide a thorough exploration of the search space. Standard crossover is biased towards smaller sub-trees, since it is more likely to make adjustments near to the leaves of the tree (there are more of them). In Genetic Algorithms, by contrast, each individual is usually of the same length and each position has the same probability of being selected, so recombination is inherently less biased. For various reasons, therefore, it can be concluded that GA crossover and GP crossover are not quite equivalent. Poli and Langdon suggested versions of GP crossover that are generalisations of corresponding GA operators, including ``one-point crossover'' and ``uniform crossover'', which are intended to reduce the bias and local nature of standard crossover.

\label{non-destructive-crossover}
A substantial amount of research has been devoted to addressing the shortcomings of crossover in the GP environment; the proposed refinements take many forms. One  approach aims to ``undo'' any destructive crossover events by only permitting recombined individuals into the next generation if they are at least as fit as their parents. If crossover does produce poor quality offspring, then they are discarded. This is generally referred to as ``non-destructive crossover''. The crossover operation may have to be repeated several times until a successful outcome is reached. Usually it is tried only a fixed number of times to prevent the evolutionary process from stalling.

%Check my salmon statistics, heard from BBC's "Nature's Great Events"

Following a similar train of thought, Tackett \cite{tackett:1995:brood} noted that animals often produce large broods owing to the likelihood that a number of their offspring would not survive\footnote{This is especially the case with fish. Wild salmon, for instance, usually produce broods of thousands of offspring -- following their epic journey through river and ocean, on average fewer than ten make it back to spawn the following year.}. He proposed that crossover between parents should be repeated $n$ times to produce a {}``brood'' of $2n$ individuals (instead of the usual two), from which the best pair would be chosen. This would increase the probability that some offspring would survive crossover\footnote{Tackett's analogy is not strictly accurate, of course: offspring in nature are likely to die as a result of factors relating to their environment, not because of their individual genetic predispositions.}. Although this helps to ensure that the crossover operator is less destructive while still permitting an exploration of the search space, it does impose a significant amount of additional processing.

% What is the difference though - an experiment to find out here would be quite good.

The author proposes that another way to make crossover less destructive is to use a classification procedure that is not dependent on a fixed output range or threshold, which reduces to some extent the dependencies that make GP individuals fragile. We shall cover one technique, so-called dynamic range selection, in Chapter \ref{ch:gp-classification}.

Iba \emph{et al.} \cite{ito98} attempted to adjust non-destructive crossover to remove its local bias and make it concentrate on larger, more influential sub-trees. They did this by choosing first a depth $d$ at which to cross over, then selecting a node at depth $d$ to create the crossover point. Curiously they assigned weights to each depth $i$ such that the weight associated with each depth is $1/2^i$. This would appear to generate a bias in the other direction.

Lang \cite{lang:1995:headlesschicken} proposed another crossover strategy, dubbed {}``headless chicken'' crossover, where only one parent was selected from the population and then crossed over with a randomly generated individual. Crossover was repeated until the offspring was better than the parent -- a form of hill climbing. While Lang showed that his method could outperform standard crossover on a multiplexer problem, Zhang \emph{et al.} \cite{zhang:2007:newcrossover} showed that while it could still get better results than standard crossover, it was also  significantly slower. Crossover with a random individual is analogous with point mutation, with the exception that it is more wasteful.

% Context aware crossover...
If humans were in charge of the crossover operator, we might make more effort to reach an intelligent decision as to how to swap sub-trees. In programming, we might like to change a piece of code, but we usually need to ensure the replacement is still compatible with the rest of the program. D'haeseleer \cite{context-preserving-crossover} invented so-called \emph{context-aware} crossover, which aims to do something similar. The context of each node is encoded as an $n$ coordinate array $A = {p_1, p_2, ... , p_n}$, where $n$ is the depth of the node in the tree and $p_i$ is the position in the tree at depth $i$. D'haeseleer suggested operators where sub-trees could only be exchanged if they had identical contexts. The problem with this approach is that it does not readily permit new, possibly better contexts to be discovered by crossover. The author would further submit that the \emph{position} of a node in a tree is not necessarily an ideal measure of its context.

% Selective crossover (Hengraprohm and Chongstitvatna)
Another approach is to evaluate the usefulness of each sub-tree, so that they may be protected. Hengraprohm and Chonstitvatna \cite{selective-crossover} proposed that the ``value'' of a particular sub-trees could be identified my measuring the difference in an individual's fitness if the sub-tree were removed and replaced with a function-less node. This procedure is used to identify the ``best'' and ``worst'' nodes in the tree. A single offspring is created by replacing the worst node in one parent with the best node from the other, a process termed \emph{selective crossover}. Hengraprohm and Chonstitvatna demonstrated that their operator could converge on solutions with around 20\% less computational effort. The reader should note that computational effort is a measure of how many individuals are evaluated before the population converges on a solution. Although the ``computational effort'' was lower, the amount of processing per-individual would have been significantly higher, so Hengraprohm 's and Chonstitvatna's algorithm would not have yielded individuals more quickly.

In summary, one can see that there is a number of strategies for dealing with the side-effects of crossover. It is perhaps possible to guide the crossover operator to more intelligent decisions, but doing so requires a lot of additional computation. Unfortunately there appears to be no analytical means of estimating the fitness or usefulness of a particular sub-tree: in all cases, the addition or subtraction of a sub-tree from a program can only be measured empirically, which is computationally expensive. If GP is used to construct vision algorithms, which are already computationally intensive, the addition of certain hungry crossover operators is likely to make the process excessively slow. %The author's preferred approach in this regard is the basic non-destructive crossover operator, which integrates the crossover process with a hill-climbing component that ensures damaged offspring are discarded, without imposing any additional computation.

% Uniform crossover (Poli and Langdon)

% Computational effort: 

\subsubsection{Mutation}
\label{mutation}
% The purpose of mutation.
The second genetic operator in common use in Genetic Programming is mutation. In nature, mutation is the name given to the rare event during which parental DNA is incorrectly transcribed or copied. Although mutations occur in our bodies with surprising frequency, their effect is usually confined to just one cell in the 50--75 \emph{trillion} cells in an average human being. Still, we all start off from a single cell, so any transcription error during the production of that cell will become part of every subsequent cell in the offspring's body. Despite our perceptions to the contrary, mutation is usually benign in the natural world, thanks to the redundancy within DNA; other times it is harmful and occasionally it is beneficial. It is mutation more than crossover which is believed to bring about the ``unusual'' changes that can trigger leaps forward in the evolution of a species.

Mutation is commonly used in artificial evolutionary systems. In Evolution Strategies, mutation was simulated by perturbing the numeric values of genes. In Genetic Programming, mutation works by manipulating the tree. The GP mutation operator works by taking a single parent, discarding a sub-tree at random and replacing it with a new one, commonly generated using the GROW tree builder. The adjusted parent is then inserted into the new population.

As we've seen, the consequence of fitness-based selection techniques and crossover is to make certain sub-trees more abundant in the population, while discarding others. This leads to a reduction in diversity in the population, which may cause the search rate to decrease. The rationale is that mutation can help maintain the diversity in the population by occasionally adding new sub-trees or re-introducing previously discarded ones that may yet be useful. 

The mutation rate in GP populations is usually set much lower than crossover: between 10--20\% of the population are generated by the mutation operator, in recognition of the fact that mutation makes completely new additions to an individual, rather than swapping sub-trees known to make up reasonably successful individuals. 

In common with crossover, mutation may have lethal effects on individuals. Indeed, many of the issues associated with crossover also apply to mutation. Accordingly, issues like local bias and destructiveness may be dealt with in a similar fashion as discussed earlier.

\subsubsection{Elitism}
\label{elitism}

The final means by which individuals may pass into subsequent generations is though \emph{reproduction}. Reproduction refers to the insertion of an individual directly into the next generation without subjecting it to either crossover or mutation. Since reproduction doesn't involve any further exploration of the search space, it is usually left at a low level (around 5\%), or reserved for so-called \emph{elite} individuals.

Elitism is a protective mechanism for situations where the selection mechanism fails to select the best individuals in a population, or where crossover produces offspring that are worse than their parents. Elitism guarantees  that the $n$ best individuals will be copied into the next generation. These individuals are not affected by crossover or mutation and therefore will continue to exist until better individuals take over the elite set. This is distinct from deterministic selection since each elite is only copied to the next generation \emph{once}.

As we have seen, the genetic operators are designed to discover further refinements given a number of selected parents, but can also produce offspring with significantly worse fitness. We have also discussed code bloat, manifested in GP programs as useless code fragments or \emph{introns}. Introns provide a form of protection against the effects of the genetic operators: introns are expendable. The \emph{Baldwin effect} is an observable phenomenon, in which the genes (and introns) of successful individuals become more and more common in the population through their increased breeding potential. Introns bloom in GP populations because, although they don't make an individual any better, they might help it to survive. 

In addition to preventing the population's maximum fitness from regressing and helping to ensure a higher end-of-run fitness, elitism also appears to reduce code bloat \cite{Piszcz:2006, Poli:2008:geccoe}, as it reduces some of the advantage that introns offer to the survivability of individuals.

One of the problems of GP, exemplified by issues with crossover and mutation, is that crossover lacks a  mechanism for preserving the useful information it has discovered so far, beyond the hope that natural selection will cause useful sub-trees to become more abundant within the population. Andre \cite{EvoVision:Andre:1994} suggested the use of Automatically Defined Functions (ADFs) in which the tree builder could take advantage of whole sub-trees as well as using the basic nodes. It is intended that this technique would allow the GP process to generate and keep those building blocks in order produce complex programs more easily. However, as we've seen in the case of crossover and mutation, it is difficult to assess the usefulness of sub-trees in a computationally efficient manner, so the identification of ADFs is not straightforward. We shall consider another approach by which useful code fragments can be preserved in Chapter~\ref{ch:gp-classification}.

%Coevolution is a technique similar to ADFs where two or more populations would evolve together and work on a symbiotic basis. 

\subsection{Generation Gap Methods}
\label{generation-gap}

Having covered selection as a means for selecting good parents for breeding, it is also worthwhile considering the natural consequence of such an action -- the removal of another individual in order to maintain the population at the same size. We saw that in the classic version of Evolution  Strategies, the parents compete with their offspring for a place in subsequent generations, a scheme referred to as \emph{plus} selection, often represented as $\left(\mu+\lambda\right)$, where $\mu$ is the size of the parent population and $\lambda$ the size of the new offspring population. Plus selection bears much in common with a different paradigm, referred to as steady-state evolution, in which the concept of separate ``generations'' is discarded in favour of producing a much smaller number of offspring following each process of evaluation. In plus reproduction and steady state reproduction a \emph{deletion schemes} is necessary in order to remove the \emph{worst} individuals from the combined population (see GENITOR \cite{whitley89genitor}).

A more common approach, alluded to throughout this chapter, is referred to as \emph{comma} reproduction, denoted by $\left(\mu,\lambda\right)$, in which the offspring population completely replaces the parent population -- there is no overlap or competition between the two, so all individual ``lifetimes'' are of a fixed length. The deletion scheme in comma reproduction is therefore trivial -- simply discard all the parents. 

At first glance, it appears that plus reproduction is the more effective means of going about evolution. It bears something in common with non-destructive-crossover, which helps ensure that the genetic operators do not cause population fitness to regress and it does not discard parents in an arbitrary fashion. Plus selection is an elitist strategy: parents will remain in the population until such a point as offspring can outperform them. However, if elitism is applied to half the population instead of just a few individuals, it can cause the population to become stuck in local minima; it isn't possible for individuals to regress and explore different avenues of exploration. Substantial amounts of elitism will cause the same parents to reproduce repeatedly, which compromises population diversity.

Wakunda and Zell \cite{Wakunda00anew} proposed a different selection scheme intended to help maintain diversity within plus and steady state populations. They also showed that comma schemes required more computational effort -- more evaluations -- in order to achieve a desired degree of fitness on certain problems. Holland and Reitman \cite{holland78} found that generational reproduction was not suitable for \emph{classifier systems} where each classifier is to some extent dependent on the others as decisions are made by the population as a whole (see Wilson \cite{Wilson1995a} for a more definitive version). They found that replacing only a small part of the population at a time was more beneficial than replacing the whole population in one go. Eggermont \emph{et al.} \cite{Eggermont99} performed a comparative study that appeared to show that generational GP yields slightly better results, on average, than does steady state GP on certain classification problems. This may be because the steady state approach does not encourage learning to the same degree. De Jong \cite{dejong1975} stated that the advantages of overlapping populations were offset by the effects of genetic drift (loss of diversity). Like many areas of research in Genetic Programming, generation gap methods exemplify the different approaches taken to solving problems; each is applicable to certain situations.

\section{Conclusion}

In this chapter, the author has covered in detail the main components of evolutionary systems in general and Genetic Programming in particular. An issue throughout, highlighted in the section on multi-objective optimisation, is that there are often conflicting demands for each component. Indeed, it is quite difficult to describe any of these components as being optimal in all circumstances; we've seen that most have particular advantages and particular disadvantages. Consequently it is difficult to write down \emph{the} definitive set of parameters, although this is desirable if GP is to be rendered into a ``black-box'' learning system for evolving vision systems in general. Later in this thesis the author will go about describing suitable choices that make GP suitable for learning vision components in particular. We shall now turn our attention to those vision system components -- the major challenges and areas of study in computer vision, and the quality and extent of vision software evolved by GP researchers thus far.
