Towards the Automatic Construction of Machine Vision Systems using Genetic Programming

Olly Oechsle

A thesis submitted for the degree of

Doctor of Philosophy at the

School of Computer Science and Electronic Engineering

University of Essex August 2009

A Brief Glossary

Abbreviation Description  Page
DRS Dynamic Range Selection. A means of representing classifiers.  1176

DRS2 Refers to the author’s extension of DRS, which render it free of parameters.

1288

DRS2C Refers to the author’s extension of DRS2, which renders it capable of returning confidence estimates.

1288

ECJ A popular Java-based toolkit for evolutionary computation.  ??
ES Evolution Strategies. An early genetic learning technique.  153

FULL A tree builder, used for generating programs in Genetic Programming.

229

GA Genetic Algorithm(s).  171

Genotype The encoding of a solution, which may differ from its eventual behaviour (phenotype).

179

GLCM Grey-Level Co-occurence Matrix. Summarises spatial relationships between different pixels, used to calculate texture descriptors.

860

GP Genetic Programming.  179

GROW A tree builder, used for generating programs in Genetic Programming.

221

ICS Intelligent Classification System. The author’s classification framework.

1450

JASMINE An end-user component of the author’s software. Permits users to generate vision systems.

??

LDA Linear Discriminant Analysis. A long-established statistical technique that may be used for binary classification.

??

Phenotype The behaviour of a program or individual, which is not always entirely determined by its genotype.

179

PS Partial Solutions. Another of the author’s classification frameworks.

1410

SXGP The author’s own Genetic Programming toolkit.  ??

Abstract

Computer vision is a topic that has interested researchers and commercial organisations alike for some time: it provides both a considerable intellectual challenge, and a wide variety of useful applications, some of which are now becoming ubiquitous. In this thesis the author has studied means by which vision software may be constructed automatically using Genetic Programming (GP) – a technique that learns how to write programs during a simulation of Darwinian evolution. This research addresses the question of how one might create more “complete” vision systems using GP, beyond simply proving the applicability of evolutionary learning to particular image processing tasks. Research into making Genetic Programming more suitable for deployment as a generic learning tool is presented, evaluated and assessed, and novel means by which multi-stage vision systems can be constructed from evolved components is described. The author does not claim to have invented significant new paradigms in either GP or mainstream computer vision – rather the focus is on bridging the gap between task-specific applications and a generic learning framework. An architecture for creating such applications is presented, along with software that permits non-expert users to create vision systems rapidly of a complexity first equal to, then beyond that so-far published by GP researchers.

Acknowledgements

I would like to express my gratitude to a number of people before commencing this document. I am particularly grateful to my fiancée (now wife!) Rong Gao for her patient support and kindness, especially in the last stressful months of preparing a thesis document. It appears that most doctoral study inevitably deteriorates into mathematics to some degree; I also thank her for her assistance in those areas.

I am grateful for the support of my supervisor, Dr Adrian Clark, throughout the course of my study. I trust his assistance to have steered me along the right track, while allowing me to take the research my own direction and to indulge ideas that have interested me since childhood. I also gratefully acknowledge the assistance from the EPSRC for making the last three years financially tolerable!

I dedicate this thesis to my parents, Maggie and Gunther, who invested so much into my education – a sacrifice that, until now, I’ve never properly thanked them for.

Contents

iii

List of Figures

iv

List of Tables

v

Datasets

Although the author’s software develops and uses bespoke datasets for a number of vision problems, the following benchmark datasets, mainly from the UCI machine learning repository, are used throughout this thesis for the purposes of comparison and validation. These are summarised here for the reader’s convenience. Unless otherwise stated, results on these datasets are averages following the execution of 50 evolutionary learning runs.

Dataset  Samples  Purpose

BUPA 345 To predict whether or not a patient will suffer liver disorders based on the results of 5 blood tests and the number of alcohol units drunk per day. Validated using 10-fold cross validation.

Glass 214 To identify 6 different types of glass, using 10 attributes discovered following chemical analysis. Validated using 10-fold cross validation.

Heart 270 To determine the presence or absence of heart disease using 13 different attributes, including the patient’s age/sex and the results of various diagnostic tests. Validated using 10-fold cross validation.

Dataset  Samples  Purpose

Ionosphere 351 To identify radar patterns indicating the presence or absence of “some type of structure” in the ionosphere. Uses 34 attributes collected from an array of 16 high-frequency antennas. Validated using 10-fold cross validation.

Iris 150 R.A. Fisher’s classic dataset concerning the recognition of three species of Iris using 4 attributes: measurements of the width and length of flowers’ petals and sepals. Validated using 10-fold cross validation.

PenDigits 7494 + 3498 To recognise ten different characters [0–9], hand-written by 44 authors, based on a feature vector of 16 attributes corresponding to different arc lengths. Validation using a separate test set.

Pima 768 To identify whether a female patient shows signs of diabetes or not, based on 8 different attributes. Validated using 10fold cross validation.

SatImage 4435 + 2000 36 features from a multi-spectral imager are used to identify 6 different types of terrain on the ground below. Validated using a separate test set.

Thyroid 3772 + 3428 To determine whether or not a patient has an overactive thyroid, using 21 attributes, 16 of which are binary. Validated using a separate test set.

Vehicle 846 To classify a given silhouette as one of four types of vehicle, using a set of 18 image features extracted from the silhouette. Validated using 9 fold cross validation, for which the sets are pre-defined.

WDBC 569 To diagnose the presence of breast cancer using 30 features derived from a fine needle aspirate (FNA) of a breast mass describing cell nucleii. Validated using 10-fold cross validation.

Overview

The following is a high-level overview of the research described in this thesis.

Chapter 1

Introduction

Some 540 million years before you started reading this thesis, something interesting happened. Although living organisms have existed on Earth for over 3.5 billion years of our planet’s 4.5 billion year history, the most dramatic evolution of new species occurred during a period of “just” 60–70 million years – an event we now refer to as the Cambrian Explosion. Although the fossil record isn’t fully complete, the data suggest that life on Earth transformed during this short period from mainly single-celled species to a world filled with the major groups of complex, multicellular life still in evidence today.

The Cambrian Explosion was so rapid and pronounced that even Charles Darwin expressed concern that it undermined his theory of evolution by natural selection. However, later research [?] suggested that evolution is not, in fact, a process of gradual improvement, rather it consists of large periods of stasis punctuated by rapid bursts of change. To this day, and in the absence of other hypotheses, evolution is human-kind’s best explanation for how we all came to be here – and how you come to be reading this thesis.

As it happens, it is from this period that the earliest fossil remains of animal eyes have been found. While basic photo receptors are sufficient for an individual to distinguish light from dark or day from night, an eye is something rather special. Our vision systems permit us to explore and navigate through the world with a remarkable degree of understanding.

Although nobody knows for certain what triggered the Cambrian Explosion, some zoologists [?] believe it was the advent of sight that sustained it. One can only imagine the advantage of a predator with some form of sight would have in a world filled with blind prey. The survival of a species would hinge on its ability to adopt better defences or to develop such new senses in turn; an evolutionary arms race commenced. As it happens, the Burgess Shale, a substantial deposit of fossils dating from the Cambrian Explosion, shows evidence of the adaptations evolved by predators and prey alike. Nowadays 96% of the world’s species employ some form of vision system in order to perceive the world as illuminated by visible light^{1}.

Most species have what one might describe as a vision system, including both eye sensors and a degree of processing in the brain^{2}. Indeed some species, notably birds of prey, have significantly better sensors than humans. However, humans are distinguished by the significant portion or our already generously proportioned brains dedicated to vision processing. In addition to being able to perceive our surroundings instantly in astonishing clarity, we can recognise almost anything, including things we haven’t seen before. We can understand how some tools and machines work simply by looking at them, all seemingly without effort.

Because these “tasks” can be performed without much noticeable exertion, it is quite easy to be complacent about the quality and scope of our vision system. It is perhaps only when we try to implement vision systems in silicon that we come to realise just what an astonishing feat of engineering is to be found inside our heads. From our implementations of imperfect sensor technology, incomplete vision algorithms and underpowered hardware, one gains an appreciation of how much has been accomplished within and behind our eyes. Nonetheless, while the tasks that computer vision researchers have set themselves are sometimes ambitious, some great leaps forward have been made in recent years.

1.1 The Rise of Machine Vision

During the last decade or so, some applications of computer vision, such as the automatic recognition of car number-plates or in-camera face detection, have become ubiquitous. This is thanks both to the significant increases in computing power available in increasingly small devices and the quality of work undertaken by academic researchers and commercial organisations in labs around the world. Whether one likes or dislikes applications such as the congestion charge cameras in London, they only exist because machines can now do the bulk of the vision processing automatically and accurately.

Now that machines can demonstrably perform a limited subset of useful vision tasks, human ambition demands ever more applications for them to work on. Some are completely new, such as the interactive window displays now showing on the streets of Tokyo or the foyers of Harrods department store. As machine vision breaks out from military and research circles into the mainstream, new topics of research arise, along with a desire to produce these systems more easily.

1Of course, visible light is only a small band in the electromagnetic spectrum. Interestingly, the wavelengths within the “visible” spectrum are one of only two bands of light that can travel through water. Our continuing exclusive perception of just this small band is a throwback to the environment in which vision systems first appeared – in creatures who lived underwater.

2Although some species of jellyfish do not – their eyes are connected directly to motor receptors.

How might one go about creating vision systems more easily? Certainly many of the established, excellent techniques for extracting information from images are not easy to understand, being rooted firmly within the confines of mathematics, statistics and pattern analysis. They are often built around certain assumptions about how the world appears, which may not hold true, and they generally require the effort of an expert to select, implement and tune them. In short, it is time-consuming and difficult to produce vision software.

1.2 Machine Learning

As a concept, it would be nice to be able to develop strategies in a way that required less effort. Ideally we would have the computer do this on its own – a process broadly defined as machine learning. After all, computers can work on certain problems much more quickly than we can and, unlike humans, computers don’t have a concept of impatience nor do they demand hourly wages! Modern computing power is certainly making heavy tasks such as image processing increasingly practical and so the automatic learning of computer vision is becoming more and more feasible. Indeed, some high quality vision software has already been developed using machine learning techniques, for instance the work by Viola and Jones on face detection [?].

One family of machine learning techniques takes inspiration from Charles Darwin’s theory of evolution directly. The aim is that by simulating the process of natural selection, computers may be able to replicate the explosion of progress and adaptation that occurred on Earth 540 million years previously. So-called evolutionary computation was largely confined to parameter optimisation tasks until computing power permitted the invention of Genetic Programming (GP) [?], an adaption of the classic genetic algorithm [?] which evolves programs instead of sets of numerical coefficients. Over the last twenty or so years, researchers have been exploring the ways that programs themselves can be evolved to solve all manner of problems. As we’ll see later, some equal or outperform human invention.

The value of machine learning is well understood, and accordingly many learning algorithms have been proposed, most from outside the realm of evolutionary computation.

Some, such as neural networks, can already claim a variety of established applications within computer vision, notably character recognition. Most learning techniques, however, are constrained either by assumptions or applicability. Support Vector Machines for instance, are an excellent classification technique but can’t develop algorithms, per se. Neural networks are somewhat limited in their ability to develop truly non-parametric solutions to problems. Decision trees can make decisions based on features but cannot develop the features themselves. Genetic Programming is distinct from each: as an abstract learning system with no particular underlying assumptions about input data, it is uniquely placed to develop a whole range of different software, including all the examples above. As such, it seems appropriate that GP should be used for the automatic construction of vision systems.

1.3 Evolved Vision Software

As we’ll see later, Genetic Programming has already been put to work on a wide variety of problems in computer vision. Although a number of excellent solutions have been evolved by GP researchers, they are generally developed to prove that GP can solve problems within a particular domain. However, if one is to devise and implement a separate GP learning system for every situation, then one of the main advantages of machine learning – reducing the human effort – is lost.

In contrast, this thesis explores the viability of the GP as a domain-independent generator of visual routines; more specifically, the development of more complete, working vision systems – something that isn’t generally tackled by GP researchers. The author would define a working vision system as one that takes images as input and returns highlevel output without requiring human intervention in the intermediate stages. The idea is to develop a framework that can learn to develop vision systems applicable to a range of different situations, with the proviso that all the task-specific information can be encapsulated within training data. The key is that the framework should not require manual tuning, adaptation or modification for individual tasks.

It is the aim of this thesis to explore the extent to which certain vision tasks can be learned automatically (or with minimal human input) by this generic architecture, and to see whether the GP-learned vision software is any good from a practical point of view. The feasibility, accuracy and capabilities of vision components developed using Genetic Programming will be described and analysed.

1.4 Challenges

Some would argue that the use of Genetic Programming is a self-imposed challenge in its own right. As we shall later see, Genetic Programming does have some significant drawbacks not least its reputation, which is not entirely undeserved, for being slow and inefficient.

A theme that runs through the entire course of this thesis concerns means by which Genetic Programming can be made more efficient at solving problems involving vision. We shall also see how many of the parameters usually required to define a GP run can be dispensed with, turning the GP system into a more flexible learning tool.

Despite the drawbacks, one cannot deny the power of evolution as evidenced by nature. The potential of Genetic Programming to discover novel solutions by means we hadn’t previously considered motivates this author to produce vision systems whose taskspecific components are all evolved by GP, something that has not been done before.

1.5 Contributions

The author has made a number of novel contributions during the course of undertaking this research. These are outlined briefly below:

• The author has developed a complete Genetic Programming toolkit specifically for the purpose of solving vision problems, which compares favourably to a current, widely-used toolkit, ECJ [?]. ................................................. p.??

• The author has developed a classification scheme using Genetic Programming termed “Intelligent Classification System”, which produces demonstrably better results on public datasets than the majority of other GP classification systems. The classification system makes pseudo-intelligent decisions, can run in parallel, and can solve problems with many classes. .............................................. p.1450

• The author has proposed an extension to an existing GP classification representation to include confidence estimation. This makes it more suitable to certain problems and can improve classification accuracy when used by multiple classifier systems. p.1325 • The author has described how many of the parameters in GP systems can be opti-

mised or discarded such as to render GP into a suitably generic learning engine for vision problems ..............................................................p.??

• The author has developed a generic feature-detection approach which is capable of evolving components for a variety of domains, to a similar standard to those previously published by GP researchers. ...........................................p.??

• The author has developed a multi-stage vision framework which permits the creation of vision systems applicable to a variety of different tasks. The architecture is controlled by graphical user interface which permits end-users to define tasks and create training data visually. After the training data has been created, the interface initiates an intelligent learning process to evolve complete vision systems automatically. ........................................................................ p.??

• The author has demonstrated the vision systems on a number of different vision tasks of a complexity not previously attempted by GP researchers. ............ p.??

• The author’s work on generating vision systems using Genetic Programming has been published in [?]. By the time you come to read this thesis, two further papers will have been submitted. The first is a more thorough description to the author’s vision system generator. The second concerns the author’s approaches to classification by GP. ...................................................................p.??

1.6 Thesis Structure

This thesis concerns two areas of study: computer vision and evolutionary computation. Accordingly it begins with two literature surveys. In the following chapter the author introduces evolutionary computation in general and Genetic Programming in particular, and covers a number of techniques and algorithms employed by researchers in the GP community. In Chapter 3 the wider field of computer vision and pattern recognition is introduced. A number of techniques commonly employed in computer vision are described and assessed; solutions developed by human intuition and machine learning are compared and contrasted.

The learning component of the author’s system is based largely around the classification or labelling of feature vectors. Before discussing what features may be appropriate to describe the content of an image, Chapter 4 considers how to use Genetic Programming in order to generate classifiers in a general sense.

The field of information theory and pattern recognition is well established. There has already been mention of various machine learning techniques. In Chapter ?? the results of the author’s GP classifiers are compared to other GP toolkits and other machine learning systems, in order to justify more fully the decision to use GP on a generic system. The chapter also describes in more detail the implementation of the author’s GP toolkit.

Later chapters are concerned with the development of vision systems by Genetic Programming. We do not believe it possible to evolve a complete vision system during the course of a single evolutionary run; early it on it was decided to create a vision system comprising several stages. The first is concerned with low-level vision tasks, or the detection of features, and is discussed in Chapter ??. The further stages of the author’s vision system framework are presented in Chapter ??, which covers how GP can be used to produce more complete, standalone vision systems. It also describes how the process of creating them can be automated to the extent that non-expert users can produce vision software. Finally, in Chapter ?? both the capabilities and limitations of the author’s system are explored.

The reader is left with a question as this introduction draws to a close. How might one create a vision system, that can learn to analyse medical images, read car number-plates, recognise gestures in real-time or read sheet music, without any form of parameter tuning or expert knowledge? In this thesis we’ll discover whether Genetic Programming can find an answer.

Chapter 2

An Overview of Genetic

Programming

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.

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.

2.1 The Inspiration Behind Evolutionary Algorithms

The theory of evolution by means of natural selection (“survival of the fittest”^{1}) 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^{2}, 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^{3}. 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.446) or the abnormal event where errors occur during the transcription process (mutation, see p.519). 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.

1First coined by Herbert Spencer in 1864, later integrated into Darwin’s 5th Edition of On the Origin of Species.

2Exceptions do exist: evolution of species of fruit fly introduced into North America have been observed over periods of less than 20 years [?].

3This is a safety mechanism that helps impede the rapid replication of mutated or otherwise damaged cells.

2.2 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 2.1. The concept is to produce a 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.

Figure 2.1: The general process of artificial evolution

2.2.1 Evolution Strategies (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 [?]. In Evolution Strategies, the population is composed of a number of 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 2.2). Selection techniques, which usually aim to select better individuals while maintaining diversity, are discussed in more detail in Section 2.3.4.

Figure 2.2: 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.

2.2.2 Genetic Algorithms (GA)

Following Evolution Strategies were the Genetic Algorithms (GA), popularised by the work of John Holland [?]. 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.446), a more realistic mutation operator (p.519), and inversion^{4}, 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.

2.2.3 Genetic Programming (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^{5}). 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 nonlinear logic in the form of computer programs. Therefore, Genetic Programming is not a parameter optimisation technique but a method for automatic programming.

4Inversion 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.

5XCS [?] is a classification system which uses a GA as its learning component.

Although several researchers investigated the automatic evolution of 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 [?].

The primary difference between Genetic Programming and Genetic Algorithms is the differentiation between phenotype and 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.

2.3 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:

• The Representation and Creation of Individuals

• The Evaluation of an Individual’s Fitness

• The Selection of Individuals

• The Choice of Genetic Operators

For a more thorough, beginner-level introduction to Genetic Programming, the author recommends the “Field Guide to Genetic Programming” by Poli, Langdon and McPhee [?].

2.3.1 The Representation of Individuals

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 [?]. 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 240).

The more common approach in Genetic Programming is to express programming code using a tree structure (see Figure 2.3). The tree consists of a series of nodes which represent programming functions and inputs. The leaves of the tree are referred to as 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 function nodes. Execution starts at the top 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 [?]) such as to represent more complex dynamics, such as loops (see Teller and Veloso [?] or Shirakawa et al. [?]). 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 240), 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”.

Figure 2.3: An example tree whose function is equivalent to x = R/(G + B).

2.3.2 The Creation of Individuals

As was shown in Figure 2.1, 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 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.

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 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.

FULL Builder

Koza’s second tree builder [?] 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 2.4). This is implemented by selecting function nodes on 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.

Figure 2.4: 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.

The Ramped Half-and-Half Population Builder

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}, ⋯, 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.

Strong Typing

Koza’s early function sets tended to use nodes of the same “type”. A set composed of, for instance, the mathematical operators +, −, ×, ÷ and a series of numeric terminals x_{1}, x_{2}, …, 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 (⋯) function (see Figure 2.5), for instance, then it may still return a number dependent on the branch it chose to execute, but its condition would have to be boolean.

Figure 2.5: 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.

Although Koza proposed a clunky solution to the problem, an early deviation from his original implementation was the addition of strong typing by Montana [?] 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 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 ??.

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 [?] developed a tree builder named 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 size of trees created. However, although depth 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 [?] 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}}{∑_{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 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 nonterminals 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.

2.3.3 The Evaluation of an Individual’s 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 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.

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 ∈ X, the correct class y ∈ C, and a corresponding weight w . The fitness of function f : X → C may be calculated as:

error_{1} = ∑_{i=1}^{N} w_{i}[f(x_{i}) ≠ 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 367), 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.

Different Errors, Different Costs 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 false positive, where a sample from another class is incorrectly identified as the class in question, or a false negative, where a genuine sample from the class in question is not identified as such^{6}. 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.

6Although the false negative in one class may be a false positive for another.

The relative importance of different mistakes can be encoded by introducing extra coefficients α and β into the fitness function. An example, used by Roberts & Howard [?], is:

error_{2} = \frac{αT P}{αN + βF P}

where T P is the number of correctly classified samples (true positives), F P 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 α and β. 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%.

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 [?]). 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 4 we’ll see some of the other approaches to multi-class classification by GP.

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^{7}. 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 ??). 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 introns^{8}. Introns are undesirable as they can reduce the efficiency of the learning process.

7The modern interpretation is slightly different to the original principle: “entia non sunt multiplicanda praeter necessitatem”. which roughly translates to “entities must not be multiplied beyond necessity”.

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 [?] 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 ??.

Multi-Objective Optimisation 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 goldplate 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 Pareto Front.

It is necessary, therefore, to consider the optimal solution instead as a 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.

8The term is borrowed from genetics, relating to DNA portions in genes which apparently do not perform any function during the production of proteins.

The main approach to multi-objective optimisation are the 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 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 [?] 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 [?]) 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 [?]. The consequence of this technique is that it selects individuals that can excel with regard to one criterion, but not necessarily both.

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.

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^{9}.

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 worst performance is then used as its overall fitness (see Ebner [?]). This removes some of pressure towards over-fitting the training data, which usually degrades the program’s ability to generalise and is an issue with non-parametric learning methods.

2.3.4 The Selection of Individuals

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 deterministic selection (also referred to as 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:

9k-Nearest-Neighbour may also be slow to run on large data sets, although a Best-Bin-First (BBF) (see Beis and Lowe [?]) algorithm can be employed to speed up the distance matching.

“The rate of increase in fitness of any species is equal to its genetic variance in fitness.” R. A. Fisher, 1958 [?]

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.

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 [?]. In SUS, the individuals are shuffled before being placed on the roulette line with each marker a fixed distance from the last (see Figure 2.6). 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.

Figure 2.6: 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.

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 selective pressure.

Rank-Based Selection This algorithm is similar to fitness proportional selection, except that the raw fitness is discarded in favour of the 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 [?]:

j = ⌊\frac{N}{2(c − 1)} (c − \sqrt{c^{2} − 4(c − 1)r})⌋

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.

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 [?]) 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 i