Genetic Algorithm and Genetic Programming

Artificial intelligence (AI) is a very broad subject within computer science. My own specialisation centres around evolutionary computation. In particular I use genetic algorithm and genetic programming to optimise trading rule entries and exits.

Recently, I optimised a trading rule that I had been developing within a spreadsheet. Whenever I design a trading rule I always visualise data on a spreadsheet using charts. The next thing I do is create an hypothesis to see if it generates a trading edge. The hypothesis can then be tweaked until an edge is found or the hypothesis (and its variants) are refuted and I start again.

I saw that my hypothesis could make a prediction about the future state of the market but I wasn't sure on how to go about profiting from the strategy. I knew which data triggered an entry but I was unsure of when to exit the trade. Exiting too soon might lose some profit and staying too long in the trade might mean that I would be jumping on the profit taking bandwagon with all the manual traders when it was too late.

Genetic algorithm (GA) was used to optimise a suitable stop and profit taking exit strategy. In GA possible numerical solutions are encoded as numbers called chromosomes. These chromosomes are then grouped together into inhabitants and a population of random inhabitants are created. Each inhabitant is evaluated against test data to generate a fitness value. After fitness is evaluated the population is then paired off for reproduction with fitter inhabitants more likely to be selected for reproduction. 

During reproduction chromosomes are shared between parents to create children who share their parents' traits but with small differences, as in nature. In GA the parent population is replaced by the child population and the new population is evaluated for fitness. This process is continued until an inhabitant of desired fitness is found.

Example

I might encode an inhabitant with three chromosomes representing an entry, stop loss and take profit. The entry tells the rule when to back or lay, the stop loss tells the rule when to get out of a losing trade and the take profit tells the rule when to close the trade for a profit. An initial population contains inhabitants (typically thousands) with each of these chromosomes. Each chromosome has a random value as a possible solution to a problem.

An example inhabitant would be

Inhabitant = 12, 20, 40 (enter when price rises 12%, stop at 20% loss, take at 40% profit)

Each inhabitant is evaluated against a set of data and given a fitness as a function of return on trades executed. Inhabitants are then selected in pairs as parents for reproduction. The fitter an inhabitant is the more likely they are to be chosen.

Parent1 = 12, 20, 40
Parent2 = 12, 25, 35

Parents then undergo "crossover" whereby children are created from the sharing of chdromosomes from the parents. A random point is chosen where the crossover between the parents will take place. In this example we shall say that position three is chosen.

Child1 = 12, 20, 35
Child2 = 12, 25, 40

As you can see two children have been created that are different to their parents but use the same traits as their parents. These children may or may not be superior to their parents in gaining return from their trades. Such is the case in nature, evolution is directed by the ability to survive in an environment but in a random way.

The old population is replaced by the children and tested as before. As many generations are evolved as is desired by the operator. However, cares must be taken not to over-fit inhabitants to the data otherwise they will have no predictive power. A set of data is left out of the training data and used to test a chosen solution for generality. If say the best candidate solution scores a 10% yield in training but only 1% with the test data then the candicate is probably over-fitted to the training data. It would therefore be wise to run the training phase again but for fewer generations to get a lower yielding solution that might stand up to evaluation by the test data.

In my implementation, each inhabitant had two chromosomes, one representing a percentage stop loss value for closing a losing trade and the other a percentage profit take value for taking a profit. The entry was known so it did not have to be optimised. The fitness function was the return on a £2 bet after trading each of the races in my training data. The fittest inhabitant would be the one with the most return after being evaluated against all the training races.

The results were interesting in that the genetic algorithm recommended a stop when the loss was 30% or more. That is something that I would never have imagined as a manual trader but I checked the result and it was correct. Too often, when I was a manual trader I would panic when there was any kind of loss. Eventually, I educated myself to only close a trade with a 10% loss. Now, by working in tandem with a machine intelligence I can use my superior human skills for looking for patterns in data coupled with a machine intelligence that optimises a trading rule to get the most profit out of it.

When I first worked in evolutionary computation the two books that I referred to most were David Goldberg's Genetic Algorithms in Search, Optimization and Machine Learning and John Koza's Genetic Programming: On the Programming of Computers by Means of Natural Selection. Both books are available secondhand for a reasonable price.

The two books deal with slightly different aspects of evolutionary computation. You can think of GA as a tool for optimising a known formula or equation. In my stop/profit example above, I knew when to enter a trade, I just didn't know how much of a loss to accept or how much profit to take. The GA returned just two numbers, a percentage stop value (e.g. 30%, the amount I could lose before closing a losing position) and the percentage profit taking value (e.g. 80%, the profit yielded from the trade before taking the profit and closing the position).

If neither the stop nor the profit taking values are hit then the trade is left until just before the off where the position is closed out for a value between -30% and +80% of the value of the trade. The machine intelligence had optimised these values to give the best overall profit margin for all the trades in the training data. In this case the trades as a whole would have yielded 10% on average.

In the case of genetic progamming (GP) nothing is known about the solution to a problem and so a complete program tree is evolved to maximise a fitness function. The program might contain logical statements, for example "If lay_price > 30_minute_moving_average then lay". Each program element; 'If', 'lay_price', '>', '30_minute_moving_average', 'then', 'lay' is a separate chromosome. Some programs might be non-sensical (e.g. if if then if then) but that is okay as their poor fitness means they will not be selected for reproduction. The fitter programs will pass their traits on to future generations.

This is essentially the basis of a paper I wrote in 1998 called EDDIE Beats The Bookies so I won't explain GP further and just refer you to the paper. There enough detail in the paper for an experienced AI programmer to replicate a basic GP environment for evolving decision trees. The trees in the paper were evolved to select the winner of a horse race in a very rudimentary manner so I would take the results with a pinch of salt. The aim of the research was to show how intelligence could emerge from data and be guided by the payoffs from success or failure of each tree.

I have a personal preference for evolutionary computation. For me neural networks are black boxes and you can never be sure what they are upto. A GP has a program tree that can be easily read so that you can see the logic behind the solution. That is not to say that neural networks have no place in AI as can be seen by the recent victory of a machine against a human Go player.

Further Reading

Genetic Algorithms in Search, Optimization and Machine Learning. All you need to know about GA. Simple to understand, the ideas can be ported to any programming language.The book uses primarily uses Pascal to demonstrate how to code a GA but the logic will be easily ported to any language. I managed to port the code to C++ without difficulty.





Genetic Programming: On the Programming of Computers by Means of Natural Selection is a weighty tome, containing everything you need to know about Genetic Programming. Includes many example applications such as classification and strategy evolution.






For those who have some experience of evolutionary computation and would like to read a more trading specific book I would recommend Biologically Inspired Algorithms for Financial Modelling. The book details evolutionary computation, neural network and hybrid systems with examples of trading rule discovery and optimisation.
 

6 comments:

  1. Just out of curiosity could you test placing random backs and lays on random horses half an hour before the off say. Then perform that test with no stop and limit and then the same test but with the 30:80 settings.

    The untested theory of some technical financial traders is that perfect discipline in itself is a strategy that can make returns or break even at least just because of the inefficiency of the other market participants. A test was done I believe flipping a coin each morning before the DAX futures opened to determine a buy or sell and then a volatility calculated stop and limit. It made money for a period of time which sadly in no way constituted a sufficient sample size but the concept interests me all the same.

    Regards,

    Matthew.

    ReplyDelete
    Replies
    1. I am currently adding extra functionality to a manual analysis engine for testing basic hypotheses and from which training matrices can be generated for my GA optimisation program.

      "Time To Off" is one of the variables that I added this week. I can void chromosomes or constrict their value so I will be able to test your hypothesis in the near future.

      Although, intuition tells me that for a random back/lay with no stop or limit the results will be normally distributed around 0% return minus commission.

      However, I am finding some skewed return distributions when adding a few technicals.

      I am looking for general volatility rules that I can add to my portfolio. They will have low capacity but the idea is to have many of them.

      Delete
  2. In this circumstance where there are limited number of values for the chromosomes, is it ever worth just performing a brute force attack on the numbers trying all combinations? Does the GA always come up with the correct fit given sufficient generations?

    ReplyDelete
    Replies
    1. Good comment.

      As I mention in other posts on this site the preference is for a brute force approach. My GA Optimiser calculates the possible number of combinations and gives the user the opportunity of optimisation or brute force.

      GA does not always give the best fit for a solution. A population of solutions can discover a local maxima which is easier to hill climb than happening upon the traits of the optimal solution.

      I am researching a variety of classifiers and optimisers for publication. My own preference is for brute force given any time constraint. For that purpose I am also looking at parallel processing.

      Even VB.NET can do parallel For Next loops to make the most of multi-core processors. F# is a concurrent language within Microsoft's Visual Studio that can also be used for this purpose.

      Another methodology I mention above is Genetic Programming where not even the formula to be optimised is known. This greatly increases the search space so the genetic approach may work here. But, as with GA, the optimal solution is not always discovered.

      Something that is worthy of another article is that with a brute force approach you can see what values either side of a best fit can do to a trade. If the hill climbed is very steep then either side of the solution will be much lower returns. Not so with a fat hill where formula value give less return but not drastically so.

      This means that you can choose a not so good fit but which is more robust when your bot does not exactly hit its stops and limits. I shall write that up when I get a chance.

      Delete
  3. I guess one of the dangers with a brute force attack is that you will come across an overly back fitted solution, where the stars align to give you a fantastic result on your dataset, but provide no predictive effect due to some spurious correlation.

    So the presence of a `fat hill` rather than a spike would provide extra confidence that an optimal solution has been found.

    I've also wondered whether it is important to come up with rational explanation for the numbers you are seeing, as you mentioned in your post the -30% stop loss was a surprise and unintuitive. Is it possible to come up with a hypothesis about the market sentiment around these magic numbers?

    I guess ultimately, an explanation doesn't matter, as the numbers don't lie. Unintuitive solutions may provide an edge because the crowd are less likely to follow them.

    ReplyDelete
    Replies
    1. Your assumptions about fat and narrow hills are correct. I will verify them in my next article on the subject.

      There is an easy explanation for the case of the 30/80 rule that I developed. It was a rule specifically for indentifying short-priced drifters.

      A few of these drifters can go from favourite or second favourite to a fourth or fifth favourite with double figure odds. They are few but they account for some very big wins, hence the the 80% limit on profit taking.

      It is because these big drifters skew the limit that the 30% stop is possible. The big drifters can soak up a lot of losers and still yield a profit.

      I can add other chromosomes to the rule, which can filter out more losers and reduce the 30% stop but then I would lose a lot of generalisation in the rule. It's a case of Occam's Razor.

      Delete