“The answer to any question you could wish to know can be found in nature.
All you need to know is how to ask the question and how to recognise the answer.”

‘The Power of One’, by Bryce Courtenay.

 
 

I.Introduction
 

1.1Can Machines Think?

In 1950 Alan Turing put forward the question “Can machines think?”. He stated that by the turn of the century a computer should be able to pass a standard test of intelligence (now known as the ‘Turing Test’) in no less than 30 per cent of trials [6]. In 1995, few researchers share Turing’s confidence that a machine will prove its intelligence this way by the year 2000. Many researchers are, however, dedicated to the development of such a machine. This pursuit is the goal of researchers in the field of adaptive systems.

Adaptive systems, in computing, comprise numerous techniques that, when applied to a problem, autonomously adjust the relative importance of input parameters to solve that problem. In other words, the goal of all adaptive systems is machine learning through identifying the patterns and relationships between the input parameters and the desired outputs. Although these systems can be ‘tuned’ to apply to specific problem domains, they do not have any one specific goal in their conclusion. Rather, they adopt a ‘best fit’ strategy to problem solving. This ‘best fit’ strategy results in systems that are well suited to non-linear and NP complete problems. While the field of adaptive systems research is often referred to as artificial intelligence, there are two very distinct approaches to the problem of machine learning, of which artificial intelligence is one. The two main streams of adaptive systems are artificial intelligence and evolutionary systems.
 
 

1.1.1 Artificial Intelligence

The term artificial intelligence (AI) was first coined in the 1950s [30]. The field of AI is concerned with the ‘hows’ and the ‘whys’ of human intelligence. This focus is not surprising, as the originators of AI came from the fields of psychology and mathematics (McCarthy, Minsky, McCulloch, Pitts).

The use of techniques like propositional calculus (Simon and Newell, 1956), propositional logic and predicate logic is intended to simulate the way we deduce a solution: the ‘hows’ of intelligence. These methods have been effective in the fields of Expert and Decision Support systems.

Other researchers in the AI field attempt to imitate the mechanics of thought: the ‘whys’ of intelligence. These ‘mechanical’ systems include Semantic Networks (Quillian in 1968), Neural Networks (McCulloch and Pitts, Hebb) and Frames (Minsky 1976). Of these systems, the neural network has proven the most popular in real world applications.

1.1.2 Evolutionary Systems

Evolutionary systems are the other main stream of adaptive systems. These systems are sometimes referred to as artificial life. The term evolutionary system is derived from a metaphor of computer-based systems taking a Darwinian approach to problem solving: survival of the fittest.

Put simply, computer-based evolutionary systems are an orchestrated competition for resources among potential solutions to a problem environment. The fitness of individuals within that environment is based on their relative contribution toward a solution. In this way, the distribution of resources (namely, the likelihood of survival and mating) is, to some extent, proportionate to the utility of that individual.

The attraction of the evolutionary system as a problem solving strategy is apparent in nature’s ability to find diverse solutions to difficult and dynamic problems. So, if evolution is considered a problem solving algorithm, that algorithm is well suited to problems with many possible solutions and no known optimal solution. This suitability is suggested because there is no evidence that evolution, in nature or otherwise, is a singly directed process, i.e., that the goal of evolution is to produce any one particular species, or that there is an optimal solution to evolution. However, evolution does, in time, produce species that are robust within their domain.

The most common of these systems are Genetic Algorithms [13], Classifier Systems, Evolution Systems by Rechenburg in 1965, Evolutionary Programming by Fogel, Owens, and Walsh, in 1966 [10], and Genetic Programming in 1990 [16]. The most recent development in the field of evolutionary systems is genetic programming, and is the focus of this research. The key elements of all the computer-based evolutionary techniques have been modelled on the basic natural (Darwinian) evolutionary processes. i.e., Selection, Reproduction and Mutation. As the name adaptive implies, the purpose of any adaptive system is to perform machine learning.

1.2 Introduction to the Genetic Programming Paradigm

The genetic programming paradigm suggests a method of problem solving that is directly related to the genetic algorithm. In fact, it is the genetic algorithm that serves as the fundamental ‘engine’ of this strategy.

To the genetic program, each potential solution to a problem is considered a chromosome. The number of chromosomes tested in each iteration of the genetic algorithm constitutes the genetic program’s population. The result of this testing is the system’s ability to identify which chromosomes are better (more fit) than others, i.e., a ranking of relative performance. The likelihood of longevity and mating of these chromosomes then, can be based on survival of the fittest.

From the description above, the genetic programming paradigm sounds remarkably like the genetic algorithm. The difference lies in the structures that represent the chromosomes, i.e., the genome. The genetic algorithm’s representation of chromosomes is modelled on the base-4 make up of the DNA. The genome of the chromosomes in the genetic program, on the other hand, are less analogous to nature. However this departure from the genetic algorithm representation has added an element of versatility to genetic systems not previously available.

In particular, the versatility of genetic programming stems from the almost limitless values (or functions) that can be represented in the genes of the genetic program’s chromosome. In this way, to many, much of the value of the genetic programming paradigm lies in its potential as a “Turing complete programming language” [27].

A more detailed account of genetic programming follows in the literature review.
 

1.3 Machine Learning

Machine learning is the ability of a computer program to adapt to its environment to achieve some desired outcome. All forms of adaptive system use some method of machine learning. This learning falls into two main categories: supervised learning, and unsupervised learning.
 

1.3.1 Supervised Learning

Supervised learning involves running the system over a series of trials with known outcomes. The parameters for each trial are known as the training data. The training data used for the course of the machine learning is the training set. Training data is input to the system and the trainer gives the system feedback as to the accuracy of the system’s result. The system then makes the necessary adjustments to improve the quality of its responses [30].

This type of learning method is commonly used for situations where the problem area is well understood and clearly defined. Supervised learning requires that a trainer knows the desired responses for each of the inputs in the training set. Thus, supervised learning is not suitable to many applications.
 

1.3.2 Unsupervised Learning

Unsupervised learning is the learning scheme used by systems that do not require a ‘trainer’. This type of learning requires the system to solve the credit assignment problem [9]. Credit assignment is the testing of each individual control strategy against the resulting control action. Each control strategy can then be rated against another by its performance over a sequence of actions. The rating of each strategy is designed to reflect the goal (or desired outcome) of the system [9]. Kohonen’s self organising neural network was the first system to use unsupervised learning [30].

In the genetic algorithm, credit assignment is conducted by fitness proportionate selection, particularly when failure criteria are not explicitly included in the fitness function. The system must then deduce, implicitly, the relationship between the outputs and failure [22]. Systems that are capable of employing this type of learning have wider application than those that require supervised learning: the outcome for each set of inputs need not be known, and the system designer requires less domain knowledge.
 

1.4 Demonstrating Machine Learning

Machine learning is demonstrated by a computer-based system’s ability to autonomously adapt its responses to improve its performance in a task. In the field of adaptive systems, the most common method used to demonstrate machine learning is to apply the adaptive system to a simulation of a problem. The advantages of computer simulation are the control the analyst has over experimental variables. In particular, the computer-based simulation can guarantee that the conditions of the experiment will be identical, regardless of the location or the number of times the experiment is run. In this way, if adequate information is supplied, the learning environment can be accurately replicated, so the results can be easily reproduced.

There are numerous simulations used in adaptive systems research to test, or demonstrate, a system’s ability to perform in a variety of environments. Examples of these environments include sorting, games theory and control theory. Sorting problems involve the discovery of some optimum order of objects (e.g., the knapsack problem and sequence induction). Problems based on game theory test a system’s ability to develop a strategy to ‘win’ the game and so view a problem holistically (e.g., the prisoner’s dilemma, checkers etc.) [5]. Problems based on control theory test the systems ability to control some dynamic, usually unstable, object (e.g., the cart-pole problem and the truck backer-upper). Each of these categories includes problems that are generally considered to be of adequate difficulty to act as problem domains in testing machine learning. The basis of this statement is the popularity of these problems in this area of research.

In order to take full advantage of the benefits of computer-based simulation, the simulation must follow some accepted guidelines. If those guidelines have been shown to provide a suitably difficult learning environment and task, the benefits are twofold: first, the simulation is easy to reproduce and therefore, the results can be verified; secondly, the problem is sufficiently difficult so that a solution to the problem is considered non-trivial and non-random. The cart-pole problem, as described by Geva and Sitte [9], is such a problem and is discussed in detail in section 2.5.

1.5 A Statement of the Problem

In nature, evolution is directed by numerous selection techniques, conducted simultaneously and in varying degrees depending on the local ecosystem. In computer-based genetic systems, a single selection method is chosen to direct the evolution of the entire population. Not surprising, then, is the observation that different selection techniques will result in varying performances of the system in a variety of problem domains [10].

After reviewing the current literature in the area of genetic programming, two gaps in the state of current research seemed evident. First, there was no evidence to suggest that the genetic programming paradigm could perform this complex control task within the constraints set out by Geva and Sitte [9]. To qualify this statement, the genetic programming paradigm appeared to have only been applied to simplified versions of the cart-pole problem ([16], [17], [20], [21]). Secondly, while there have been numerous comparisons of genetic operators on difficult sorting problems and games theory problems ([1], [7], [15], [28]), the effect of selection techniques on performance in solving difficult control problems, in particular a ‘benchmark’ version of the cart-pole problem, seems to have been overlooked.

The research described in this dissertation applies the suggested methods designed to test the performance of genetic programming on a ‘benchmark’ version of the cart-pole problem as described by Geva and Sitte. In so doing, the suitability of the application of the genetic programming paradigm to this problem could be gauged according to Geva and Sitte’s performance criteria [9]. In addition, the results of the research described in this dissertation will allow the future comparison of genetic programming to the numerous other adaptive systems already applied to the cart-pole problem.
 


[T.O.C][Chapter 2]
[Beer]