|The main task of any trader is the selection of pro table strategies for trading a nancial instrument. One of the simplest ways to represent trading rules is binary decision trees based on the comparison of current values of technical indicators with some absolute values. This approach simpli es the creation of trading systems but their validity is limited to short-term intervals of trade. This paper represents an approach for generating more universal trade rules in the form of binary decision trees based on the comparison of the current values of technical indicators with relative levels. The ranges of these levels are recalculated on a daily basis which allows the trading rule to remain relevant within a long term. The proposed system analyzes the historical price data for a long period and using the genetic algorithm causes trading strategies optimized relatively to the Sharpe ratio.
A strategy of a trader concluded in the formalization of
rules for opening and closing a position. Quite often these
rules are based on methods of the technical analysis and
processing of such data as the current price of the
instrument, the volume of trading, the maximum / minimum
price for a certain period, the price at the time of opening
/ closing of the trading session. Based on the series of
these data, so-called technical indicators are generated.
In accordance with postulates of the technical analysis
technical indicators allow to predict the probable trend
direction in a given security. Thus, the combination of the
indicator and its value can serve as a basis for the trading
strategy [
The discovery of pro table patterns is a non-trivial task.
Typically a trader manually programmes his trading
system and then optimizes its key parameters by exhaustive
search or by heuristic algorithms [
One of the simplest representations of trade strategy
is binary decision trees [
In our work, a similar approach is used, which was rst
presented in [
It should be noted that similar systems use BUY/SELL signals allowing opening short positions and working with them symmetrically to the long ones. In practice, however, there are limitations: the adequate estimation of the e ectiveness of short positions is di cult because of the necessity to pay for the borrowed securities; the period of their retention should be as short as possible; there are temporary or permanent prohibitions on their opening.
There are systems based on the markup of historical data with instructions to take a trade action. This stage is necessary for training some classi ers the essence of which is to nd the relationship between a particular class and the values of technical indicators. However, at the moment there is no optimal way of such a markup.
So, for example, in paper [
Thus, the abundance of all possible variants of the markups of historical data per trading actions led to the decision to use the genetic algorithm as a classi er. This approach requires only the existence of the objective function from the data for the decision tree, thus eliminating the need to subjectively mark out historical data.
The contribution of this paper is as follows: 1) In trade rules only long positions are allowed. 2) A new optimization algorithm for the decision tree is presented which is obtained after the application of crossover and mutation operators.
3) The principle of calculating the levels of indicators is described.
A more detailed description of the tree structure is given in Section II. Section III contains a description of the genetic algorithm including the initialization process and the classical evolutionary steps. Principles of testing the best systems and the analysis of their e ectiveness are presented in Section IV.
A decision tree is a connected acyclic graph with the leaves represented by decisions, in our case these can be signals for opening a long position (LONG) and exit from it (CLOSE LONG). The process of determining decisions starts from the root, then, depending on the node value, the transition into either the right or the left node takes place. As a result, the leaf at the end is taken, i.e. an order to buy a stock and open a long position (LONG) or sell out the purchased volume (CLOSE LONG). The system starts with the CLOSE LONG state allowing the rst purchase with the LONG signal. The position size is determined by the maximum possible number of shares that can be purchased at the current balance. Thus, all the received income is reinvested.
A tree node is a predicate de ning a transition to one of the two children. In every non-terminal node, the value of the technical indicator is compared to a certain level to see whether they match.
Most often indicators have real values, but their current
state can be associated with a certain level, this approach
proved itself in [
To calculate this value, the system uses n previous values of the indicator. In this system, n equals to the duration of the training period. After that the calculation of the ranges for each level takes place: 1) The maximum (M ax) and minimum (M in) values of the indicator for the previous n days are computed. 2) On the basis of these indicators, an interval [M in,
M ax] is generated and divided into 5 equal segments. 3) The current level is determined by the segment into which the real value of the indicator falls.
If the value exceeds M ax, the indicator level is assigned V eryHigh. Similarly, if the value is less than M in the indicator level will be V eryLow.
It should also be noted that the current level of indicator is determined after closing the trading session and it is valid for the whole next trading day.
In the simplest form, the decision tree is shown in Fig. 1.
To identify the best tree the genetic algorithm is used. All steps of the classic evolution are involved.
The initial population is initialized with a preset number of random generated trees, with each node created by selecting a random indicator and associating it with a random level. The height of the tree is determined by the number of indicators available to the system (in our case 3). After this height has been reached, the generation of non-terminal nodes ceases and random LONG/CLOSE LONG leaves are created.
For the further tree modi cation with the genetic operators the individuals that t most are selected and thus the next generation is formed. The selection is done by the roulette wheel method. For each tree the probability of being chosen is: pi =
fi Pn j=1 fj (1) where fi is the tness function of tree Ti
For the evaluation of the tree the Sharpe ratio (Sharpe
Ratio), an indicator of the e ectiveness of the strategy,
introduced by W.F. Sharpe [
Rf (x) ; (2) where rp is the average income, Rf is the income with a zero risk, (x) is the standard deviation of income. As a risk-free rate, the value of 2.5% was taken as an analogue of the 10-year US Treasuries.
Genetic operators are constructed by analogy with
paper [
Due to these two operations, the principles of inheritance and self-adaptivity can be achieved. Taking into account the speci cs of the tree-shape data structure, the basis for the modi cation consists of manipulations with the terminal and non-terminal nodes.
In the process of crossover, two individuals (in the form of decision trees) are selected for crossing. The probability of selection of each one is consistent with the roulette method and it is computed using formula (1). After that copies of the both trees exchange their randomly selected subtrees and get included into the population (together with the original trees). An example of the operator's action is shown in Fig. 2.
The mutation operator is a unary operator, whose purpose is to prevent from premature convergence of the generation to each other. It is based on the same principle as the crossover - two nodes are randomly selected and swapped in the tree.
After these operators are applied, an important step is needed to remove inconsistent nodes. In Fig. 3 a typical case of this kind of errors is presented. As it can be seen, when visiting node IND1 is LOW it is already known that this predicate is false, since on the way from it to the root there is node IND1 is HIGH. The process of removing excess nodes goes by raising their respective child. In this example, if IND1 is HIGH is true, there will be a transition to IND3 is MEDIUM (i.e. to the subtree, to which would be a transition in case of falsity of node IND1 is LOW ).
After creating a new generation, an excess node removal algorithm (Algorithm 1) is run for each tree that had been modi ed by crossover or mutation. As a result, a tree either retains its structure, or, if an unnecessary predicate is found in a node, the nodes are replaced according to the algorithm suggested below. The output is an optimized tree (optimizedT ree) that works exactly the same way as the original one.
As the input the algorithm accepts two nodes which are swapped. In this case the nodes can belong to both di erent trees and to one tree. So, it can be used both in case of a crossover and a mutation. In this algorithm replacedN ode1, replacedN ode2 are the nodes that are swapped around; RightT ree is the subtree node in the case of truth of the predicate, Lef tT ree is the subtree in case of falsity; N ame - the name of the indicator in the predicate, V alue is its amount; parent is the parent of the node.
The estimation of computational complexity is O(n log n), where n is the number of nodes in the tree. This complexity allows, in principle, to use a large number of indicators to build a trading system.
The general algorithm consists of the steps of the classical genetic algorithm. Iteratively (in 25 steps) new generations (200 individuals) are created, after which their tness function is calculated and the selection is carried out by means of the roulette method. To a certain number of winners the operators of crossover (35%) and mutation (5%) are applied. The trees that underwent these permutations are optimized by Algorithm 1. The result will be the best tree (by the tness function value) in the latest generation.
All parameters are chosen empirically to ensure a
balance of quality and running time. The algorithm scheme,
its parameters and time characteristics are described more
in detail in our work [
Output: optimizedTree // Traversal of the children of the changed nodes TraversalOptimize(replacedN ode1); TraversalOptimize(replacedN ode2);
if tree:Lef t 6= N ull then
Traversal(tree:Lef t); end if tree:Right 6= N ull then
Traversal(tree:Right); end
FixRepetitions (tree); /* /* Procedure for checking and removing excess nodes */ Procedure FixRepetitions (node) /* Remember the true and false branch of the veri ed node */ trueW ay node:RightT ree; f alseW ay node:Lef tT ree; currentN ode node:parent; /* Going up to the root and checking
currentN ode with each node on the path */ while currentN ode 6= N ull do if currentN ode:N ame = node:N ame then if currentN ode:V alue = node:V alue then // An identical predicate is found if node in currentN ode:Lef tT ree then /* If the node is in the left descendants subtree of the current node, replace it with the false branch. */ node f alseW ay; else /* Otherwise, for the true one node trueW ay end else /* If only the names of the indicators coincide, it is su cient to check whether the node is in the right descendants subtree of the current one. In this case, the node is obviously false, since the values di er. if node in currentN ode:RightT ree then
node f alseW ay; end end end end /* Going one level up currentN ode currentN ode:parent
In addition to the objective function { the Sharpe ratio, for the analysis of the results, additional metrics were used. 1) Return is a pro t rate in percent and it is calculated by trade simulations using historical data. The higher it is, the better.
F inalBalance Return = ( 1) 100; (3)
StartBalance where F inalBalance is the amount of money after the simulation and StartBalance is the amount of money at the beginning. 2) Max drawdown is the maximum reduction of the account balance value from its local high in percent. It allows to estimate the maximum loss of capital when using this strategy. The lower it is, the better. 3) Trades count is the number of open positions for the period under review. The index is proportional to the possible value of the commission costs. 4) Buy and Hold represents the stock return, which is provided by the market. The essence of this strategy is in the purchase of the instrument at the very beginning and its retention until the end of the given trading period. For a comparison, the pro t indices and the Sharpe ratio (B&H Returns, B&H Sharpe) were taken.
Below there are indicators [
A greater number of indicators increases the sensitivity of the trading system, which increases the number of transactions.
As a testing object, ve large IT companies were selected: Citrix Systems (CTXS), Electronic Arts (EA), eBay Inc (EBAY), Intel (INTC), Oracle (ORCL). Consistently for each year a selection of the best trading decision tree and its veri cation in the next one is carried out. One year has 251 trading signals, each of which corresponds to a certain stock market day.
It should be noted that the time characteristics of our
algorithm allow to apply it to the analysis of 5-minute
timeframes and higher. However, for liquid shares the
greater the timeframe is, the lower the in uence of the
"noise" component of the market is. This component is
caused by unpredictable actions of large players, as well
as by a random combination of actions of many trading
robots and traders. Vulnerability of the trading system
to such a random component leads to premature signals.
Therefore, similarly to works [
The results are shown in Tables I - V. The lines with the better system performance than the B&H strategy are highlighted in grey.
Obviously, the e ciency of the constructed trading strategies substantially depends on the set of technical indicators and their parameters. In this regard, it is necessary to investigate the applicability of other technical indicators and to automate the selection of optimal parameters of the indicators. Also in the future it is planned to expand the set of nodal predicates. At the moment indicator values are only able to belong to the level but later it is planned to add the relationships between several indicators within a predicate. An important area is the study of applicability of the approach for BUY/SELL/HOLD signals. Year
As it can be seen from the presented examples, on average in 6 out of 9 cases the integral Sharpe ratio was better with our system than with the market. At the same time, the maximum loss of capital was 48% against 65% for a simple investment. This means that there are stocks and periods for which this approach can be e ective. The number of entries into the long position varies from 58 to 7, which indicates a low sensitivity of the rules received. This may be due to the fact that a period of 1 year was taken as a sliding interval to determine the level ranges. Reducing this interval leads to an increase in the speed of the system reaction, but more false signals emerge.
It should be noted that during the training this trade system is adjusted to a certain ratio of trend and consolidation movements of the share price. If in the next period this ratio changes, then the trader can expect whether pro t or loss. This fact is inherent in most algorithmic trading strategies based on methods of the technical analysis.