I received some interesting comments after publishing a recent article on evolutionary computation. One commenter asked if evolutionary computation always finds the best solution and when is it best to use a brute force approach instead.

Answering the second question first is easiest so I will do so. If you can do a brute force search then do so. If the creators of the Deep Blue chess computer that beat Garry Kasparov and the AlphaGo program that beat Lee Sedol at go could have used brute force techniques then they would have. They had to use artificial intelligence (AI) techniques to optimise the best move because the search space for chess and go moves is so large.

Today's desktop PCs are very powerful with their multi-core CPUs, parallel processing GPUs and programming languages that can make use of parallel processing techniques. It is better to perform an exhaustive search first and then to make sense of your findings rather than immediately turning to AI. There is no magic in AI. Both brute force and AI search will find the same solutions to a problem. It is only when time is a constraint or nothing is known about a search space does AI come into its own.

To answer the first question, 'Does evolutionary computation (or any AI technique) always find the best solution?' the answer is no. The only way to be sure that you have found the ideal solution is to search the entire problem space. If that is not possible then you are reliant on 'satisficing' (being satisfied with a sufficient solution).

Your AI technique might find a local maximum

You might find a trading rule that has a 50% yield but only finds a trade three times a month. The trading rule will probably be over-fitted to the training data with no predictive value with unseen future data. It would be better to choose a less optimal trading rule that trades 100 times a month with a yield of 10% and an out-of-sample yield of 5%. At least then you know the rule has a degree of robustness.

Answering the second question first is easiest so I will do so. If you can do a brute force search then do so. If the creators of the Deep Blue chess computer that beat Garry Kasparov and the AlphaGo program that beat Lee Sedol at go could have used brute force techniques then they would have. They had to use artificial intelligence (AI) techniques to optimise the best move because the search space for chess and go moves is so large.

Today's desktop PCs are very powerful with their multi-core CPUs, parallel processing GPUs and programming languages that can make use of parallel processing techniques. It is better to perform an exhaustive search first and then to make sense of your findings rather than immediately turning to AI. There is no magic in AI. Both brute force and AI search will find the same solutions to a problem. It is only when time is a constraint or nothing is known about a search space does AI come into its own.

To answer the first question, 'Does evolutionary computation (or any AI technique) always find the best solution?' the answer is no. The only way to be sure that you have found the ideal solution is to search the entire problem space. If that is not possible then you are reliant on 'satisficing' (being satisfied with a sufficient solution).

Your AI technique might find a local maximum

*i.e.*the technique gets trapped in a certain part of the search space and provides the best solution for that part of the search space even though a better solution lies elsewhere. Finding the best answer in a search space is not always the best solution to a problem.You might find a trading rule that has a 50% yield but only finds a trade three times a month. The trading rule will probably be over-fitted to the training data with no predictive value with unseen future data. It would be better to choose a less optimal trading rule that trades 100 times a month with a yield of 10% and an out-of-sample yield of 5%. At least then you know the rule has a degree of robustness.

We can think of optimisation as a hill-climbing exercise. The idea is to find the peak of a hill representing a high rate of return from an investment. In the first picture we see a chart that is quite fat in comparison to the hill in the second picture. Each bar in the chart can be regarded as a slightly different entry for a trading rule and the height of each bar in the chart can be regarded as the return for the rule.

In the second picture the hill is not so fat. The optimal solution is superior to the optimal solution in the first picture but the neighbourhood consists of many more sub-optimal solutions than the neighbourhood in the first picture.

Due to slippage we may not get the exact prices we want for entries and exits and so we will be trading with either side of the optimal entry point. If you have been monitoring your slippage then you will have an idea how far either side of the optimal price you have been getting matched. You will want to make sure that even with slippage you are hitting profitable trades.

Now imagine if these hills in the above pictures were next to each other in a search space. The peak on the hill to the right has a very attractive return compared to the hill on the left. However, if you look at the solution just three bars to the left and right of peak on the right hand hill you will see that the return is less than the return for the solution three bars to the left of the peak solution in the leftmost hill. Not only that but you soon get a zero return if you go further. Whereas you are guaranteed a little return by missing the ideal entry on the leftmost hill.

Another problem you will run into is over-fitting a trading rule to its training data. Leave a genetic algorithm (GA) to run long enough and you will get a rule that gives an astounding return on investment but will only trade a few times given many hundreds of training examples. You can be sure in this case that the GA is over-fitted and may not work on test data or actual trading.

You might want to select one of your earlier solutions that gives a much lower rate of return but has enough leeway to soak up slippage and other trading errors. This will give you more trades and more certainty that the GA has learnt something.

In conclusion I would suggest using AI sparingly and be fully understanding of the underlying maths. As I have said there is no magic. You will find the same solutions to a problem with a brute force approach, given enough time. The most important thing is determining what problem you are trying to solve and understanding the results of your work. That requires mathematical skills that cannot be avoided.

You might want to select one of your earlier solutions that gives a much lower rate of return but has enough leeway to soak up slippage and other trading errors. This will give you more trades and more certainty that the GA has learnt something.

In conclusion I would suggest using AI sparingly and be fully understanding of the underlying maths. As I have said there is no magic. You will find the same solutions to a problem with a brute force approach, given enough time. The most important thing is determining what problem you are trying to solve and understanding the results of your work. That requires mathematical skills that cannot be avoided.

Would something like Excel's "Solver" tool be considered as a form of brute force optimisation?

ReplyDeleteMore or less. I believe it is directed towards a solution. Something akin to Newton's Method.

DeleteCompared with a standard brute force, which tries every combination in a set order and Monte Carlo, which tries every combination in random order.