aiQUANT

This paper argues that the Genetic Algorithm and Genetic Programming are pretty much the same - at least in as far as the differentiating features are considered:

GA or GP? That is not the question
Woodward, J.R.
Evolutionary Computation, 2003. CEC apos;03. The 2003 Congress on
Volume 2, Issue , 8-12 Dec. 2003 Page(s): 1056 - 1063 Vol.2

Key points emerging from the paper:

• The greatest distinction between GAs and GP is that of fixed or variable length. In some cases, the size of the required solution sought may be known beforehand, but in other cases, such as evolution of trading rules, imposing a fixed size could reduce the search space hence neglecting optimal solutions.

• GAs do not necessarily represent the evolution of algorithms, but rather a subset of all possible algorithms. GP typically does not evolve computer programs as we would expect, but typically logical or mathematical expressions are evolved, or if then type rules of a classifier system.

• In GAs, the mutation of bit strings takes the form of flipping a single bit. Two main crossover operators have been used; uniform crossover uniformly selects a bit from each position from one of the two parents, one point crossover selects a point at random along the genome of two parents
  and takes the left part of parent one and combines this with the right part parent two. In GP, mutation takes the form of replacing a randomly selected sub tree in a program with a randomly generated sub tree. Crossover swaps randomly selected sub trees of two programs.

Essentially the paper states that the differences are unimportant because whether we are considering GAs or GP, whatever the high level representation is, it will ultimately be stored in the computer’s memory as a bit string. I think it’s a fair enough argument but really does not really our day to day understanding and application of the of the two algorithm variants. Because even more “artificial” forms of the algorithm such as Grammatical Evolution (GE) use bit string at lower levels, but this is irrelevant to the problem solver.

Trees in GP

It might be worth hinting at tree representation in GP here.  I have shown two examples of tree representations with their equivalent expression:

You might want to try drawing trees for the following two expressions. Note that there is a comma at the end of the first line of each expression:

1.
times(times(times(X1,plus(cos(cos(X1)),X1)), sin(plus(cos(X1),sin(plus(cos(X1),X1))))),plus(cos(minus(X1,X1)),X1))

2.
nor(nor(nor(or(X2,X2),or(X2,X3)),and(nand(X2,X3),X1)), and(nand(and(X1,X1),X3),and(nand(X2,X1),or(X3,X1))))

You can find the tree representations for 1 here and for 2 here. 

I shall be using such representations in future posts so this post serves as a reference for any unfamiliarities with tree representations/expressions that may emerge.

Bookmark & Share

Part 6: Simulation Results and wrap-up

A fitness landscape is a 3-D (or sometimes 4-D) plot which shows how the fitness value varies with respect to other variables that it depends on. To obtain the fitness landscape for our problem I altered the population size from 2 to 20 for mutation probabilities within the range 0 to 1. I then ran the GA for 25 generations and recorded the average fitness of the entire population so as to ascertain optimum mutation rate and population size to use. Alternatively we could have recorded the fitness of the fittest organism within the population, but this would not have given us an indication of the overall quality of solutions evolved by the algorithm. Hence the reason for taking the overall population fitness into account. The plot below shows how the average fitness changes for different population size and mutation rate.

We can also view the 3-D plot in the form of a contour plot:

We are interested in the dark regions because the value of the fitness function in these locations is closest to zero. It is important to point out that ideally the fittest organism in our problem should have a fitness of 0 as this represents that there in no difference between the predicted value and the actual value. We see that a mutation rate of alteast 0.5 and population size greater than 9 will yield fittest solutions within the first 25 generations.

Using the minimum mutation rate and population size (0.5 and 10 respectively) we run the GA for mating rates varying from 0.1 to 1 for 25 generations. This time we are interested in seeing how the fitness value depends on the mating rate The graph shows that for mating rates upto about 0.7, the algorithm produces fit organisms. For rates above 0.8 we see poor solutions as the overall fitness rapidly increases. The explanation for this is that organisms that high mating rates almost always results in child genes being dominated by that of the parents which gives little room for population diversity. Hence the population remains generally unfit for many generations into the future.

Hence for our experiment we use the following parameters:-

Population size: 10
Mutation rate: 0.5
Mating rate: 0.5

We let the GA run for 500 generations and get the fittest genome which we use in our prediction function. Recall that our prediction function is:

The paremeters of the fittest genome evolved by the GA after 500 generations are:

We can now apply our evolved prediction function to the 3 data sets of the FTSE 100 time series. However, to give more meaning to our results we can compare with the Random Walk model of an asset price, which takes the form:

where is a normally distributed random variable and is drift.

Comparative results are summarised below:

Data set 2 is the true out-of sample range with we intended to forecast via our prediction function. Clearly it under-performs relative to the random walk model suggesting that our prediction function provides a poor approximation of the FTSE 100 index. Note that it is not the GA which is at fault here, but the prediction function.

Key Points:

• We have shown that the GA can evolve optimum parameters for a pre-defined prediction function
• The performance of the GA is totally independent to the forecasting ability of the prediction function. The GA will almost always find the best solutions for the prediction function, which might be a poor approximator of the asset price as in our case.
• GAs are very powerful tools for global search and optimisation. However, there is a trade-off between search coverage and simulation time. Analysing fitness landscapes based on a small number of evolved generations can help estimate suitable population size as well as mutation rate and mating rate hence reducing simulation time for larger generations.

Possible improvements:

• Let the algorithm search for its own prediction function. This leads to Genetic Programming which helps generate very sophisticated prediction functions.
• Use a range of other fundamental and technical indicators as inputs to the prediction function.
• Apply filtering so as to reduce noise over-fitting.

Bookmark & Share

Part 5: Programming Issues

I wrote code for the Genetic Algorithm in MATLAB and it is terribly slow.  A run for 50 Generations averages to about 1 second per generation.  Here are some performance measures obtained using Matlab Profiler:

The FitnessFunction function is the biggest culprit and takes almost 100% of the total simulation time.  Evaluation of the fitness function is the most time consuming part in the Genetic Algorithm.  This is generally the case even with simpler fitness functions because on a relative scale, operators such as crossover and mutation require very little algebraic manipulation.  Looking at the function itself we get more detail:

We find that evaluations for alpha and beta take the most time.  I shall attempt to speed up the algorithm by writing a MEX function.  In doing so we expect the simulation time to drop by many orders of magnitude as compiled MEX code would not need to run under Matlab’s interpreted mode.

Bookmark & Share

Part 4: Roulette Selection

So we have initialised our population of chromosomes each of which is made up of 13 genes.  We can represent our population in the from of a matrix where individual chromosomes are represented vertically and it’s genes horizontally.  We have something like:

Each member of the population is assigned a fitness value based on the fitness function, which in our case is defined as

Why Roulette Selection?

Roulette wheel sampling was first suggested by Goldberg and provides a method of global selection when applied to members of a population.  In order for genes of fit chromosomes to be passed on to future generations, there must be some form of selection method to decide which members of the population will be selected to breed and which ones will be replaced.  It seems sensible to breed from genes belonging to the fittest chromosomes and replace the least fit ones, but this has a draw back: the GA can converge to local minimum as the search space is restricted to the genes covered by the fittest chromosomes only.  One of the mechanisms that enable genes of weaker organism to be passed on while at the same time favouring fitter chromosomes is Roulette Selection.  To understand this consider the following example:

Assume we have a population of 4 chromosomes each of which has their fitness value evaluated. To construct a Roulette wheel for this population we calculate the Roulette probability of each chromosome as a ratio of its fitness to the fitness of the entire population. That is

The illustration below shows the Roulette wheel for our hypothetical 4-chromosome population:

Extending the method to the problem at hand, we have:

 Note that our Roulette wheel represents a population size of 10.  Chromosome 2 for instance has a higher probability of being picked compared to to Chromosome 6.  This off-course doesn’t mean that Chromosome 2 will always be picked.  It all depends on where the Roulette wheel “stops”.  Also note that different population size would have a different representation to its Roulette wheel because every chromosome is allocated a section corresponding to its fitness value.

Main Points:

• Roulette Selection is an efficient way of allowing excellent genes embedded in a poor performing chromosome to be passed on to future generations.
• Roulette Selection enables convergence to global minimum.
• Think of this method as chromosomes represented on a Roulette wheel which is “spun” whenever a parent needs to be selected for crossover/breeding.

Bookmark & Share

Part 3: Constraining the Search Space

 We noted previously that  are integer values which will be evolved by the algorithm.  If we are to assuming that the range of possible values for each one of these parameters range from -infinity to +infinity then our algorithm will take an eternity to evaluate each and every permutation.  In order to improve convergence to an optimum solution it is useful to specify a range of values that encompasses optimum parameter values.  For instance can only have a minimum value of 2 and a maximum value less than or equal to 800.  But clearly numbers closer to 800 seem way off because it is very unlikely that patterns will persist that far back in time given the nature of our prediction function.  Parameters  will be decimal numbers with a resolution of one decimal place and will fall over a wider range.

•   fall in the integer range 2 to 65  (We will refer to these as Integer Genes)
• fall in the decimal range -1000 to 1000  (We will refer to these as Decimal Genes)

Other constants shall be set to

• Population Size = 20
• Mutation Probability = 0.7
• Mate Probability = 0.8

We don’t need to limit the algorithm to a fixed set of constants.  In-fact we will see later on the effect of altering each of these constants with respect to other parameters and constants.

 1.  Initialising the Population

We know that there are 13 genes in total that form a chromosome and we also know the boundary values individual genes may take.  What is the best way to create the required population of 20 chromosomes in-order to get our algorithm started?  We shall do so by selecting random numbers and scaling them to the permitted range

Note that  is a decimal number between 0 and one.   means that the number is rounded to the nearest integer value since the corresponding parameters are Integer Genes.

Essentially what we are saying is that Integer genes will be random numbers from the range 2 to 65 and Decimal genes will be random numbers from the range -1000 to 1000.

Bookmark & Share

Part 2:  Algorithm Overview

 The Genetic Algorithm is a subset of Evolutionary Algorithms that model biological processes to optimise highly non-linear cost functions.  They require multiple initialisation points on the cost surface hence giving the algorithm a global outlook towards the minimisation or maximisation task.  A few other advantages of these algorithms over traditional local search algorithms include

• Don’t need to compute the derivative of the function
• They can escape local minima
• They can provide a list of suitable solutions and not just one
• Simultaneous searching due to wide sampling of the cost surface
• etc etc

  The figure below shows the main steps in the Genetic Algorithm.

1.  Set Constants

Constants are the parameters that drive the rate and quality of evolution in the Genetic Algorithm.  In out example we have three constants namely

1. Population Size
2. Mutation Probability
3. Mating Probability

There is no fixed rule on how to choose the best values for these constants since they can differ from problem to problem.  The Population Size is the number of organisms or sampling points on the cost surface.  The fittest organisms of this population, which is calculated via a fitness function are allowed to breed via crossover with the premise that they will produce fitter organisms.  Mutation adds random diversity to future generations of the population.  Mating Probability ensures certain genes during crossover are unchanged hence adding more diversity.

2.  Initialise Population

In our example the population is composed of different samplings of the parameters we want to evolve.  A single member organism or chromosome is shown below: 

A gene refers to an individual entity or parameter belonging to the the prediction function.  Recall that our prediction function is:

 Note that the words organism and chromosome are used interchangeably.

3.  Evaluate Fitness

The fitness function determines how fit individual members of the population are with regards to the prediction function.  In our case we shall use a fitness function that compares the predicted price movement with the actial price movement, averaging the absolute value of the difference over a time period of  days.   

I shall explain later the variable .

4.  Sort by Fitness

Each member of the poplation is assigned a fitness value.  If the fitness is above a pre-defined threshold the algorithm is terminates.  Otherwise the algorithm proceeds to inter-breed the population so as to produce fitter organisms.

5.  Select Parents

There are many ways of selecting parents, which for instance can be based on their fitness ranking within the population.  However the actual selection mechanism may be random such as Roulette Selection.  We will use Roulette Selection in our example and I shall talk more about this later on.

6.  Breed

The genes of the selected parents are crossed over with the aim of producing a fitter organism/chromosome.  The Mating Probability ensures that certain genes are unaltered, hence adding diversification to the resulting generation.

7.  Mutate

The downside of cross over during breeding is that values are exchanged between parents but no new ones are introduced.  Mutation allows new genes to show up, hence adding even more diversification to the population.   We are emphasising on diversification because this prevents the algorithm from getting stuck at a local minimum as different members of the population represent a wider range of sampling points on the cost surface.

8.  Remove Twins

The existance of two organisms with identical genomes has limited utility in a Genetic Algorithm.  In our case, we search for two similar organisms and replace the genes of one of the organism with random values.

Bookmark & Share

So far we have looked at a case study where the MLP Neural Network was applied to forecast a Financial Index.  A derived trading model showed that Neural Networks generate higher returns than that of the buy and hold strategy for an Index traded Fund.  Predictive Edge?… Probably not given the simplicity of the model we have been dealing with.  But we have learnt and discovered a few things about MLPs which will be usefull when we shall build more complicated models.

We have seen that

• A committee of MLP NNs outperforms a single MLP structure.
• Dimensionally reduced inputs improve the quality of your NN outputs.  Garbage in garbage out.
• Smoothing your inputs via minimum lag filters enables your outputs to appear in a timely fashion.

Some challenges to overcome with MLPs:

• The learning algorithms explored thus far only perform local searches.  We dont know if the weights of our trained NN is occupying a local minimum.  A committee NN structure tries to deal with this problem by having different initialisations for each network, but this does not provide a thorough global search mechanism.
• We limit ourselves to a fixed MLP structure - how do we know our chosen structure is the best given the infinite set of possible structures we haven’t tested?
• Our forecasts are relatively good for out-of-sample sets closer to the training set.  How do we know what length of walk forward window to use for re-training without compromising the quality of forecasts?
• etc, etc.

We now move on to look at another Biologically Inspired Algorithm, the Genetic Algorithm.  We would like to apply the Genetic Algorithm to search for suitable parameters for our stock price prediction function.  To start with we will look at a simple prediction function whose structure is fixed, which will form the basis for developing self-evolving prediction functions later on.  We will then move on to look at a form of Genetic Programming known as Grammatical Evolution which allows us to evolve trading rules.  Hopefully by then we would have enough material to develop a Genetically inspired trading model incorporating all the ideas we would have covered by then. 

Part 1: The case of a fixed prediction function

Our prediction function aims to predict the difference between the closing value and the opening value of the FTSE100 index based on historical values.  Because we are limiting ourselves to using historical values for the FTSE100 time-series, our prediction function needs to incorporate the generalised forms of various technical trading strategies that use historical data to forecast and hence trade the index.  A function with terms relating to filters, closing prices, opening prices etc seems appropriate for this task.  The prediction function shall take the form:

Where:

•  is the difference between the closing price and the opening price of the FTSE100 index on day T
•  is the closing price on day T-1 minus the average of of the closing prices of T-2 up to and including day T-x

•  is the closing price on day T-1 minus the the lowest price between days T-2 and T-x
•  is the closing price on day T-1 minus the the highest price between days T-2 and T-x
•  are all integer values which will be evolved by our genetic algorithm.  So we have 13 integer parameters to evolve.

The time-series of interest is taken from the range 10/07/2000 to 28/12/2006.  We make a slight modification such that our training set occupies the middle of the time-series.  This would allow us to examine how well our model copes with a range it was trained with as well as a range it needs to forecast. 

• Test Set 1: 800 trading days.  To check how well our model generalises its forecasts and aviods overfitting.
• Test Set 2: 36 trading days.  This will be the “true” out-of-sample range to forecast.
• Training Set: 800 trading days.  This range will be used by the Genetic Algorithm to evolve the 13 parameters of our Prediction Function.

Bookmark & Share