1~ de®ned by:Let us consider program Pmaximizea 2 A;w ;s 
x
w x
b xs x f xja dx
subject to IR, LL and IC aa0 for all a; a 0 2 A such that a 0 < a. We considerthe function:Xf xja 0 L x; a    a0 1f xjaa 0 <a
Since  a 0   0 and a 0 < a, MLRC implies that function L x; a is increasing~ is that:~ s~ to solve Pin x for all a 2 A. A necessary condition for a~; w;~ x 6 w;if w~ x  w;if w
1 L x; a and  x  0;~ xu0 w1
 xu 0 w
 L x; a
~ x is non-decreasingThis condition and the concavity of u  implies that wwith x.s  is non-increasing with respect to x. Lemma 1 tellsLet us show now that ~~ x 6 w (~us that it is the case when ws is constantly equal to 0). When~ x  w, one has:w@Lb x f xjad x L x; a@s xd xSince b x=d x  L x; a is increasing with x, the sign of the derivative of theLagrangian with respect to s can change at most once. This is sucient toprove that ^s  is non-increasing with respect to x.~ is also aTo ®nish the proof, we have to show that a solution of program P^~^solution of program P. Since programs P and P dier only by the number^ is more constrained than P),~ it is sucient to show thatof constraints ( P^~ ~a~; w;s is admissible for P which is equivalent to show that for all a 0 > a~,~ s~ the utility function of the agent,condition IC aa~ holds. Denoting UA a 0 ; w;we have to show that8a 0 > a~;
~ ~~ ~ss > UA a 0 ; w;UA a~; w;
~ ~s and a~ ~s  UA a~; w;Let us consider a strategy a 00 < a~ such that UA a 00 ; w;parameter0 < < 1 de®ned by a~  a 00  1a 0 . Since the function
342
Advanced Trading Rules
~ x d x~uws x is increasing in x (function d x is non-increasing), thecondition (CDFC) and the convexity of function c  imply that~ s~  UA a 00 ; w;~ ~s  1UA a~; w;
~ ~sUA a 0 ; w;
which is equivalent to~ s~  UA a 0 ; w;~ ~UA a~; w;s(Recall that (CDFC) implies ®rst order stochastic dominance.) Q.E.D.
REFERENCESBensaid, B. and Boutillier, M. (1995) Le contrat notionnel: ecience et causaliteÂ,Bank of France, Notes d'Etudes et de Recherche, 44.Friedman, M. (1953) Essays in Positive Economics, Chicago University Press,1953Gennotte, G. and Leland, H. (1991) Market liquidity, hedging and crashes,American Economic Review, December, 80, 999±1021.Grossman, S. (1988) An analysis of the implications for stock and futures pricevolatility of program trading and dynamic hedging strategies, Journal ofBusiness, 61, 3, 275±98.Grossman, S. and Stiglitz, J. (1978) On the impossibility of informationallyecient markets, American Economic Review, June, 22, 477±98.Jewitt, I. (1988) Justifying the ®rst-order approach to principal-agent problems,Econometrica, 56, 1177±90.Kahneman, D. and Tversky, A. (1979) Prospect theory: an analysis of decisionunder risk, Econometrica, 47, 2, 263±91.Krugman, P. and Miller, M. (1993) Why have a target zone, Carnegie-RochesterConference Series on Public Policy, 38, 279±314.Kyle, A.S. (1985) Continuous auctions and insider trading, Econometrica,November, 53, 1, 315±35.Mirlees, J.A. and Milgrom, P. (1975) The theory of moral hazard and unobservable behaviour, Nueld College, Oxford.Schiller, R. (1981) Do stocks prices move too much to be justi®ed by subsequentchanges in dividends?, American Economic Review, June, 71, 3, 421±35.Shefrin, H and Statman, M. (1985) The disposition to sell winners too early andride losers too long: theory and evidence, The Journal of Finance, 777±92.
NOTES1. In any case, the trader cannot be responsible on his own wealth.2. It is only very recently that the ®nancial industry has overcome thisconstraint by delaying over time distribution of bonuses, then allowingnegative bonuses. For example, in 1994 Salomon Brothers Corporation
Stop-loss rules as a monitoring device
343
introduced intertemporal tie-ins to its pay system: a portion of the annualbonus is withheld in case the ®rm's subsequent performance is poor (TheEconomist, April 15, 1995).3. It may also be the cost associated with early closure of the wage contract,although it need not be the case.4. 1  s x  0 holds necessarily.5. When the investment ®rm faces a large pool of traders, such a commitment iscredible from a reputational point of view.6. A positive-feedback strategy is characterized by an increase of long holdingswhen prices rise.7. As a given ®rm may have more than one seat, there is a discrepancy betweenthe numbers of `own' and `customer' accounts.8. Although we rely in equation (11.5) on one type of discretization ofcontinuous pro®ts, the following results are not sensitive to the de®nitionof this indicator. Except for `error accounts' (de®ned in section 11.3.3 andeventually excluded from the analysis), the cumulative values of POt 1 DPtand POt DPt are very similar.P9. The open interest is de®ned as 1=2 j jPO jt j.10. It was the case, in particular, for a few large accounts.11. Tests of whiteness of the residuals in the ADF equations are provided inTable 11.9 of the Appendix.12. The standard error of this proportion is simplyspki 1 pki ;nkiwhere nki is the number of observations in class i, pooled across accounts.When comparing the proportion in class l and m, we computetklm 
pkl pkmklm
withs11klm  pklm 1 pklm nkl nkmandpklm 
pkl nkl  pkm nkm:nkl  nkm
We concentrate on the case where k  1.13. We use simple OLS regressions. Table A.11.5 in the Appendix providesinformation about the whiteness of residuals of regression equations (11.8)and (11.9). In most cases, there is no evidence of autocorrelation in the errorterm.
344
Advanced Trading Rules
ACKNOWLEDGMENTSResearch assistance from Valerie Golitin is gratefully acknowledged.The paper does not necessarily re¯ect the views of the Bank of France.
Chapter 12Evolving technical trading rules forS&P 500 futuresRISTO KARJALAINEN
12.1 INTRODUCTIONIn recent years, various machine learning techniques such as genetic algorithms and neural networks have made their debut in ®nancial markets. Withearning your living as a trader being as hard as it is, any approach where youset up a computer to learn trading rules for you instead of applying yourlimited time and resources to the same task has an obvious appeal. Machinelearning algorithms have indeed attracted attention in recent years (TheEconomist, 1993) and are likely to inspire an increasing amount of researchon the technical aspects of the new trading techniques (Deboeck, 1994).Since a machine learning paradigm is relatively new in ®nance, it isunderstandable that much of the research has so far concentrated ondeveloping the methodology and describing the results obtained in variousapplications. At some point, however, we need a theory of why these learningalgorithms work (if they do; if they don't, the theory of ecient marketsprovides us with an explanation). An apparently successful application maysimply have targeted a market or a time period where conditions favoured theresearcher's approach. If the approach had not been successful (or had beentoo successful), the results would never have been published.In this chapter, we take an initial step in trying to ®nd out why there appearto be price patterns that are captured by a genetic algorithm. In the course ofthis work, we set up the algorithm to learn trading rules for the Standard &Poor's 500 futures markets in a careful way, separating the data into training,validation, and out-of-sample test periods. It is found that the rules found bythe algorithm perform better than a simple buy-and-hold strategy in the outof-sample period adjusted for risk. We look at what kinds of price patternstrigger the trading rule signals, and then analyse trading activity in a relatedoptions market. It turns out that the rules are activated by particular price
346
Advanced Trading Rules
patterns and are essentially making pro®ts by betting against short-termoverreaction by the market. The price patterns coincide with systematicchanges in option volume and open interest, even though these data werenot used as inputs to the genetic algorithm. The patterns in the option dataare stable across the training and test periods. These ®ndings indicate that inthe S&P 500 futures market, the genetic algorithm is able to ®nd rules thatgeneralize out-of-sample because the underlying regularities in the marketbehaviour have remained relatively constant throughout the years.This chapter is organized as follows. Section 12.2 presents a brief summaryof genetic algorithms and their applications to ®nance. Section 12.3 describeshow a genetic algorithm was applied to ®nd trading rules for S&P 500 futures.The rules are tested in section 12.4, and the trading rule signals are analysedin more detail in section 12.5. Implications of the ®ndings are discussed insection 12.6.12.2 GENETIC ALGORITHMSThis section describes the basic features of genetic algorithms. Only thegeneral principles are reviewed here. For a more thorough introduction, thereare a number of accessible books and papers on genetic algorithms, includingGoldberg (1989), Beasley, Bull and Martin (1993), Colin (1994) and Davis(1994).A genetic algorithm refers to a search, adaptation and optimizationtechnique based on the principles of natural evolution. Genetic algorithmswere developed by Holland (1962, 1975) and have been developed further andapplied to many dierent problems since the late 1960s by many others (for asummary, see Goldberg, 1989). A genetic algorithm is one example of socalled evolutionary algorithms, all of which are based broadly on the sameprinciples. Other evolutionary algorithms include evolution strategies(Rechenberg, 1973; Schwefel, 1981), evolutionary programming (Fogel,Owens and Walsh, 1966), classi®er systems (Holland, 1976, 1980) and geneticprogramming (Koza, 1992).Genetic algorithms implement a stylized version of the Darwinian paradigm of the `survival of the ®ttest'. A genetic algorithm starts with apopulation of randomly generated solution candidates to the problem ofinterest. Each of the solution candidates is then evaluated according to aproblem-speci®c ®tness function, which is simply a measure of the quality of asolution. To create a new generation, relatively ®t members of the currentpopulation are recombined to create new solutions. These new individuals areused to replace the less ®t members of the population. Over successivegenerations, the average ®tness of the population typically increases in a
Evolving technical trading rules for S&P 500 futures
347
more or less steady manner. The evolution is allowed to continue until a predetermined termination criterion is satis®ed, which usually occurs either whenthe best members of the population are acceptable solutions to the problem orwhen the genetic algorithm makes no further progress.Dierent evolutionary algorithms share the basic paradigm, although therepresentation of the candidate solutions and the details of the generationcycle vary widely. In a basic genetic algorithm, the candidate solutions (whichwe will call `genomes') are represented by ®xed-length bit strings (e.g.00111001), which are mapped to the original solution space. These bit stringsare recombined through a `crossover' operator, where each of the two parentgenomes is broken apart at a randomly chosen location, and one part fromeach parent is put together to create an `ospring' (e.g. parents 00000000 and11111111 could be recombined to 00011111). In earlier days, it was popular tocreate a new generation by copying a fraction of the old generation overintact, and ®lling in the rest through a recombination operator. Currently, socalled `continuous reproduction' is often used, where a small number of therelatively poor genomes are replaced by new ospring, so that successivegenerations overlap (Syswerda, 1989; Whitley, 1989). In each case, the parentsfor recombination are chosen at random while favouring the ®t individuals.This has the eect of increasing the average ®tness of the population overtime, while still occasionally exploring dierent regions of the search space.The in-built randomness reduces the likelihood of the algorithm becomingtrapped in a local optimum.Genetic algorithms are popular because they oer a number of advantagesover traditional optimization methods. They can be applied to problemswhere the objective function is non-dierentiable or discontinuous. They arealso useful in optimization problems with several local optima, which oftenpose diculties for hill-climbing or gradient-based methods. In some situations, the search space is simply too large for other approaches. While geneticalgorithms may not ®nd the global optimum in such problems, they oftenconverge to acceptable solutions relatively quickly. However, evolutionaryalgorithms oer no panacea. In well-understood problems, they are unlikelyto perform better than special-purpose algorithms. Genetic algorithms alsosuer from the lack of a rigorous theoretical foundation. While they havebeen found to be quite useful in practice, there is no general result thatguarantees convergence to a global optimum. Hence, one should viewevolutionary algorithms as a complement rather than a replacement fortraditional optimization methods.Evolutionary algorithms have been applied to a large number of problemsin the past three decades (see Goldberg, 1989; Nissen, 1993). In economics,genetic algorithms have been applied to time-series forecasting by Packard
348
Advanced Trading Rules
(1990) and Meyer and Packard (1992) and to econometric estimation byDorsey and Mayer (1995), to give just a few examples (for more references,see Karjalainen, 1994). In ®nance, Allen and Karjalainen (1993) used agenetic algorithm to ®nd technical trading rules for the S&P 500 stockindex. Bauer (1994) applied a genetic algorithm to ®nding market-timingstrategies based on fundamental data for stock and bond markets. Colin(1994) and Davis (1994) describe other practical applications to ®nance.Arthur et al. (1996) have used classi®er systems to model traders in anarti®cial stock market at the Santa Fe Institute.12.2.1 Genetic programmingIn this research, we used a variant of the basic genetic algorithm called geneticprogramming. It was developed by Koza (1992), although Antonisse (1991)and Colin (1994) have independently come up with similar algorithms. In abasic genetic algorithm, the solution candidates are represented as bit stringsof ®xed length. While this representation is quite adequate for manyproblems, it is restrictive in situations where the size or the form of thesolution is not known beforehand. In genetic programming, solutioncandidates are represented as hierarchical compositions of functions. Inthese tree-like genomes, the successors of each node provide the argumentsfor the function identi®ed with the node. The terminal nodes (i.e. the nodeswithout successors) correspond to the input data. The structure of the treedoes not need to be speci®ed beforehand. Instead, one de®nes a problemdependent set of functions and terminal nodes, and allows the geneticalgorithm to recombine the tree structures to create new solution candidates.The genetic programming package used to implement this process wasdeveloped on a Unix workstation and written in C (for details, seeKarjalainen, 1994).In genetic programming, the evolution starts with a population ofrandomly generated tree structures. The root node of each tree is chosen atrandom among the available functions. Each argument of that function isthen selected among the available functions, taking care that only functionsof the appropriate type are considered. This process continues in a recursivemanner, extending the tree until each branch terminates at a function with noarguments.The crossover operator recombines two genomes by replacing a randomlyselected subtree in the ®rst parent by a subtree from the second parent. Tomaintain the syntactic validity of the trees, the subtree in the second parent ischosen among those whose root node is of the same type as the chosensubtree in the ®rst parent (this procedure preserves a so-called `closure'property).
Evolving technical trading rules for S&P 500 futures
349
When evolving new generations, continuous reproduction is used. Thisprocess involves choosing two parents at random, while biased towardschoosing the relatively ®t genomes. The two parents are then recombinedinto one ospring. This ospring replaces a randomly chosen member of thepopulation, this time biased towards the less ®t individuals. Each generationconsists of N repetitions of the crossover operation, where N is thepopulation size.12.3 EVOLVING TECHNICAL TRADING RULESThis section describes how a genetic algorithm was set up to ®nd technicaltrading rules for the S&P 500 futures. Because the rules make tradingdecisions based on past prices only on one of the most ecient markets inthe world, we should not expect the rules to lead to dramatic pro®ts.However, evolving and testing purely technical rules provides us with abase case and the methodology can be easily extended to handle other inputsbeyond prices. Moreover, there are some previous studies which suggest thateven purely price-based technical trading rules can be useful. These include apaper by Brock, Lakonishok and LeBaron (1992) on the Dow Jones index,Sweeney (1988) on individual stocks, and Lukac and Brorsen (1990) onseveral commodity futures markets.12.3.1 The futures dataWe used daily closing prices for 47 contracts of the S&P 500 futures, startingon 21 April, 1982, and ending on 15 September, 1993, with a total of 2885trading days (ignoring the overlap between the contracts). In a preliminarydata analysis, sample autocorrelation function of the daily log returns wasfound to be signi®cantly negative for the ®rst lag, with a coecient of 0.10.At higher-order lags, there was no evidence of signi®cant autocorrelation.There was evidence, however, of nonlinearity. If the returns are generated bya linear process (such as a random walk), the absolute and squared returnsshould show no evidence of autocorrelation, after linear dependence has beencontrolled for (Taylor, 1986). It turns out, however, that there is signi®cantserial dependence in the absolute residuals from an AR(5) model ®tted to thedaily returns (Karjalainen, 1994). This analysis does not explain where thenonlinearity comes from; it may simply be evidence of conditional heteroskedasticity in the data. Nevertheless, technical trading rules may be usefulfor S&P 500 futures if they manage to exploit the nonlinearity of thereturns.Because the trading volume was very small in the beginning, the ®rst threecontracts were dropped, so that the ®rst contract used by the genetic
350
Advanced Trading Rules
algorithm was March 1983. For each contract, daily closing prices in thedelivery month and in the preceding four months were retained, so that thedierent contracts partly overlap. The data were normalized by dividing eachclosing price by the ®rst price of the contract and multiplying the results by100.12.3.2 Evolving trading rulesThe trading rules were set up so that they returned a boolean value of either`true' or `false' at the close of each trading day, corresponding to a `buy' or a`sell' signal, respectively. The rules were represented by tree structures, asexplained earlier on the section on genetic programming. The tree structureswere hierarchical compositions of various logical and real-valued functionsand constants. The logical functions included an `if-then-else' function,operators `and', `or', and `not', as well as comparisons of two real numbers(`<' and `>'). The real-valued functions included division, addition, subtraction, multiplication of two real numbers, a `norm' function (absolutedierence of two real numbers), a moving average, a maximum and aminimum of past prices (with the time window speci®ed by a real-valuedargument), today's closing price, as well as a `lag' function which causes allthe functions in the subtree to be applied to prices lagged by a speci®ednumber of days. There were also logical constants (`true' and `false') and realvalued constants (drawn from a uniform distribution between 0 and 100, andtruncated to integer values when appropriate). Figure 12.1 shows two simpletrading rules that can be created using these functions and an ospringcreated by recombining the two parents. To interpret any of the rules in the®gure, start at the root of the tree and follow the arguments down to theleaves. Parent 1 in Figure 12.1, for instance, returns a `buy' signal if today'sprice is greater than a ®fty-day moving average and a maximum of the pastthirty days' prices is below today's price. To evaluate a trading rule, it wasapplied to each trading day. If the rule returned a `buy' signal, a long positionwas taken (or maintained, if the rule was already long) for the following day.If the rule returned a `sell' signal, a short position was taken (or maintained)for the day after. Whenever a trade extended beyond the ®rst day of thedelivery month, the position was covered at the ®rst switch to a new position,and the processing shifted over to the next contract. If the rule returned thesame signal for each day in the delivery month, the position was covered onthe expiry. Depending on the exact rollover day, the rules had access to 4±6weeks of past prices on the ®rst day in a new contract.The ®tness of a rule was de®ned as the excess cash ¯ow above a buy-andhold strategy, marking the position to market each day. For S&P 500 futures,the daily cash ¯ow is equal to 500 times the size of the position (one contract)
Evolving technical trading rules for S&P 500 futures
351
andPARENT 1:
average
price
price
maximum
30.050.00PARENT 2:
or
minimum
price
6.4
average
maximum
28.6
30.0
andOFFSPRING:
average
50.0
price
minimum
price
6.4
Figure 12.1 Illustration of two simple trading rules and the crossover operator. The crossovercreates a new trading rule by recombining the two parent rules. A randomly chosen subtree (designated by the dotted line) in the ®rst parent is discarded. The discarded subtree is replaced by asubtree of the same type, chosen from the second parent. The ospring is shown in the bottom of the®gure
times the price change from the previous day's close. To compute the ®tness,the cash ¯ow for each day in a long position was added to the cumulativebalance for the rule. The cash ¯ow for each day in the short position wassubtracted from the balance. Every time the position was changed, acommission of 100 dollars was subtracted from the cash balance (this is a
352
Advanced Trading Rules
conservative estimate; nowadays, institutional investors typically pay lessthan 15 dollars as a roundtrip commission, and the bid-ask spread is usually50 dollars or less). The buy-and-hold policy was implemented by rolling overa long position to the next contract on the same day that the particular rule inquestion switched to the next contract.To evolve trading rules, the data set was divided into three subperiods.Contracts one to sixteen (March 1983 to December 1986) were used as atraining period. The best rule from each generation of the genetic algorithmwas applied to a selection period, consisting of contracts seventeen to twentyfour (March 1987 to December 1988). If the rule improved on the previouslybest rule in the selection period, it was saved instead, overwriting thepreviously best rule. The selection period was used to avoid over®tting, i.e.stop evolution while the best rules still retained their capability to generalizebeyond the training data. Each trial was terminated after a maximum of ®ftygenerations, or until no progress had been made for twenty-®ve generations.The rule saved from the trial was then applied to an out-of-sample test period,consisting of contracts 25±43 (March 1989 to September 1993), covering 1211trading days. To build a collection of trading rules to test, a total of 100 trialswere conducted, each starting with a population of 500 randomly generatedtrading rules. The test results for the saved 100 rules are described below.
12.4 TESTING THE TRADING RULESThis section describes the out-of-sample test results for the trading rulesevolved for the S&P 500 futures. Although one might be interested in theabsolute pro®ts for the rules, the results for a simple buy-and-hold strategyare also presented for comparison. The riskiness of the trading rules is alsoanalysed.
12.4.1 Trading rule resultsThe average buy-and-hold cash ¯ow for holding a long position of onecontract during the test period in 1989±1993 was 3546 dollars per 3-monthcontract, accruing a 100 dollars commission for each rollover. The averagecash ¯ow for the 100 trading rules was 4306 dollars, using the same 100dollars roundtrip commissions. The average trading rule cash ¯ow rangesfrom 2320 dollars to 9043 dollars. The average daily cash ¯ow for longpositions was 106.94 dollars; the average for short positions was 31.27dollars.
Evolving technical trading rules for S&P 500 futures
353
d of trades
Cash flowFigure 12.2 The average cash ¯ow and the average number of trades per contract for the 100trading rules for the S&P 500 futures. The rules were evolved using price data for contracts fromMarch 1983 to December 1988, and tested on contracts from March 1989 to September 1993
Figure 12.2 shows the average cash ¯ow versus trading frequency. Acrossthe rules, there was an average of 6.53 trades per contract or one trade every10 days. The frequency ranges from less than two days per contract (a tradeevery thirty to forty days) to a high of ®fteen trades per contract (a tradeevery four days), indicating that there is a fair range of diversity in the tradingstrategies.To get a dierent view of the trading rule performance, consider Figures12.3 and 12.4. They show the distribution of the daily pro®t (ignoringcommissions) for trades of dierent duration for long (Figure 12.3) andshort (Figure 12.4) positions. The graphs are truncated at ten days, becausethere are relatively few observations for the long-term trades. It can be notedthat the average cash ¯ows are positive for long positions and negative forshort, regardless of the duration of the trade. The largest pro®ts are made onshort-term trades of one to three days.Figure 12.5 shows the cumulative cash ¯ow for a `portfolio' of tradingrules. The portfolio corresponds to a trading strategy where the daily positionis equal to the net position (between 1 and 1) across the rules. Figure 12.5indicates that the trading rules did miss the big market upswings, but made upthe gap achieving relatively small but steady gains. The cash balance for thebuy-and-hold strategy in the end of test period on 31 August, 1993 was 73 150dollars, starting from zero on 30 November, 1988. The ending cash balancefor the trading rule portfolio was 84 013 dollars.
354
Advanced Trading RulesCash flow
DaysFigure 12.3 The distribution of the average daily pro®t for trades in long positions for the S&P 500futures, using trading rules found by a genetic algorithm. The results are averaged over the 100trading rules over the test period from December 1988 to August 1993
Cash flow
DaysFigure 12.4 The distribution of the average daily pro®t for trades in short positions for the S&P500 futures, using trading rules found by a genetic algorithm. The results are averaged over the 100trading rules over the test period of December 1988 to August 1993
Evolving technical