No description available.

With the increasing speeds of modern processors the possibility of using genetic programming for problems with a huge amount of data has become feasible. One area where people over the course of time have been interested in looking for pattern is in the financial markets. Due to the nature of financial markets it is very hard to find patterns with traditional techniques. It is hoped that genetic programming can find these patterns that can’t be found in other ways, if they exist. This report studies genetic programming and a system called TSL that creates trading models with the help of genetic programming. TSL is built on a genetic programming software called Discipulus which is a very fast machine code based regression and classification tool. The first step before a run can take place is to collect the financial data that the models will be built from. During this work the data has been taken from TradeStation which is a system used for analyzing and trading the financial markets. After this is done TSL must be set up for the run. It has a lot of different parameters for the user to configure. When the run is over some of the models are saved and these can be tested in TradeStation to see their performance on another time period. If it gives a satisfactory result the models can be used for live trading. During the work I have focused on two futures contracts, Standard & Poor’s 500 E-mini contract and the British Pound contract. On these instruments extensive testing has been made but I have not been able to find any models that return risk adjusted excess returns during my work. There is a possibility thou that such systems actually has been produced during the evolution but due to flaws in the saving mechanism in TSL some of the most promising looking models have not been saved.

Det finns idag ett stort behov av att kunna klassificera stora mängder data på ett effektivt sätt. Prediktiv modellering är ett område inom data mining där prediktioner kan utföras baserat på tidigare erfarenheter. Dessa prediktioner presenteras sedan i en modell. Avvägningen mellan tolkningsbarhet och träffsäkerhet är ett begrepp som beskriver hur träffsäkra modeller ofta är ogenomskinliga, medan genomskinliga modeller ofta har lägre träffsäkerhet. Detta är ett problem eftersom det finns ett behov av modeller som är både träffsäkra och tolkningsbara.I denna studie visas hur man kan gå till väga för att skapa en modell som har en träffsäkerhet i klass med en ogenomskinlig modell, men samtidigt har en högre tolkningsbarhet. Två algoritmer presenteras för att ta fram en hybridmodell som bygger på beslutsträd där en implementering av Random Forest hanteras som alternativa lövnoder. Kontrollerade experiment och statistiska tester genomfördes för att mäta hybridmodellens träffsäkerhet mot träffsäkerheten hos J48 och Random Forest. Träffsäkerheten mättes även mot beslutsträd som genererats av den genetiska programmeringen som finns implementerad i ramverket G-REX.Resultatet visar att hybridmodellen kan uppnå en träffsäkerhet som är jämförbar med Random Forest men samtidigt hanterar de vanliga prediktionslöven i genomsnitt 39,21% av instanserna. Alltså är den hybridmodell som presenteras i studien mer tolkningsbar än Random Forest utan att ha någon signifikant skillnad i träffsäkerhet. / Program: Systemarkitekturutbildningen

When classifying high-dimensional data, a lot can be gained, in terms of both computational time and precision, by only considering the most important features. Many feature selection methods are based on the assumption that important features are highly correlated with their corresponding classes, but mainly uncorrelated with each other. Often, this assumption can help eliminate redundancies and produce good predictors using only a small subset of features. However, when the predictability depends on interactions between the features, such methods will fail to produce satisfactory results. Also, since the suitability of the selected features depends on the learning algorithm in which they will be used, correlation-based filter methods might not be optimal when using genetic programs as the final classifiers, as they fail to capture the possibly complex relationships that are expressible by the genetic programming rules. In this thesis a method that can find important features, both independently and dependently discriminative, is introduced. This method works by performing two different types of permutation tests that classifies each of the features as either irrelevant, independently predictive or dependently predictive. The proposed method directly evaluates the suitability of the features with respect to the learning algorithm in question. Also, in contrast to computationally expensive wrapper methods that require several subsets of features to be evaluated, a feature classification can be obtained after only one single pass, even though the time required does equal the training time of the classifier. The evaluation shows that the attributes chosen by the permutation tests always yield a classifier at least as good as the one obtained when all attributes are used during training - and often better. The proposed method also fares well when compared to other attribute selection methods such as RELIEFF and CFS. / Då man handskas med data av hög dimensionalitet kan man uppnå både bättre precision och förkortad exekveringstid genom att enbart fokusera på de viktigaste attributen. Många metoder för att hitta viktiga attribut är baserade på ett grundantagande om en stark korrelation mellan de viktiga attributen och dess tillhörande klass, men ofta även på ett oberoende mellan de individuella attributen. Detta kan å ena sidan leda till att överflödiga attribut lätt kan elimineras och därmed underlätta processen att hitta en bra klassifierare, men å andra sidan också ge missvisande resultat ifall förmågan att separera klasser i hög grad beror på interaktioner mellan olika attribut. Då lämpligheten av de valda attributen också beror på inlärningsalgoritmen i fråga är det troligtvis inte optimalt att använda sig av metoder som är baserade på korrelationer mellan individuella attribut och dess tillhörande klass, ifall målet är att skapa klassifierare i form av genetiska program, då sådana metoder troligtvis inte har förmågan att fånga de komplexa interaktioner som genetiska program faktiskt möjliggör. Det här arbetet introducerar en metod för att hitta viktiga attribut - både de som kan klassifiera data relativt oberoende och de som får sina krafter endast genom att utnyttja beroenden av andra attribut. Den föreslagna metoden baserar sig på två olika typer av permutationstester, där attribut permuteras mellan de olika dataexemplaren för att sedan klassifieras som antingen oberende, beroende eller irrelevanta. Lämpligheten av ett attribut utvärderas direkt med hänsyn till den valda inlärningsalgoritmen till skillnad från så kallade wrappers, som är tidskrävande då de kräver att flera delmängder av attribut utvärderas. Resultaten visar att de attribut som ansetts viktiga efter permutationstesten genererar klassifierare som är åtminstone lika bra som när alla attribut används, men ofta bättre. Metoden står sig också bra när den jämförs med andra metoder som till exempel RELIEFF och CFS.

<p>I detta arbete undersöks hur bestraffningsmetoder för att bestraffa storleken på GP-program påverkar generaliseringsförmågan. Arbetet grundar sig på ett arbete som Cavaretta och Chellapilla gjort, där de undersöker skillnaden i generaliseringsförmåga mellan bestraffningsmetoden ”Complexity Penalty functions” och ingen bestraffningsmetod.</p><p>I detta arbete har nya experiment gjorts med ”Complexity Penalty functions” och ”Adaptive parsimony pressure”, som är en annan bestraffningsmetod. Dessa bestraffningsmetoder har undersökts i samma domän som Cavaretta och Chellapilla och ytterligare i en domän för att ge en bättre bild av hur de generaliserar.</p><p>I arbetet visar det sig att användningen av någon av bestraffningsmetoderna ”Complexity Penalty functions” och ”Adaptive parsimony pressure” oftast ger bättre generaliseringsförmåga hos GP-program. Detta motsäger det Cavaretta och Chellapilla kommer fram till i sitt arbete. ”Adaptive parsimony pressure” verkar också vara bättre på att generalisera än ”Complexity Penalty functions”.</p>

I detta arbete undersöks hur bestraffningsmetoder för att bestraffa storleken på GP-program påverkar generaliseringsförmågan. Arbetet grundar sig på ett arbete som Cavaretta och Chellapilla gjort, där de undersöker skillnaden i generaliseringsförmåga mellan bestraffningsmetoden ”Complexity Penalty functions” och ingen bestraffningsmetod. I detta arbete har nya experiment gjorts med ”Complexity Penalty functions” och ”Adaptive parsimony pressure”, som är en annan bestraffningsmetod. Dessa bestraffningsmetoder har undersökts i samma domän som Cavaretta och Chellapilla och ytterligare i en domän för att ge en bättre bild av hur de generaliserar. I arbetet visar det sig att användningen av någon av bestraffningsmetoderna ”Complexity Penalty functions” och ”Adaptive parsimony pressure” oftast ger bättre generaliseringsförmåga hos GP-program. Detta motsäger det Cavaretta och Chellapilla kommer fram till i sitt arbete. ”Adaptive parsimony pressure” verkar också vara bättre på att generalisera än ”Complexity Penalty functions”.

One of the main purposes of the fields of Robotics and Artificial Intelligence is to develop solutions that can autonomously solve problems. An important part of this is synthesising behaviours of robots. Behaviour Trees are a tree structure that enables combining existing lower level behaviours into a high level behaviour through task switching. However, designing appropriate Behaviour Trees can be prohibitive due to time and knowledge requirements. One way of automating the creation of Behaviour Trees is through Genetic Programming, which evolves solutions through mutations and combinations akin to biological evolution. This Masters thesis explores how Genetic Programming can be used to generate Behaviour Trees in an automatic fashion. More specifically, whether so-called Quality Diversity can be used to improve the search. Quality Diversity describes a field of algorithms that combine both performance and novelty of behaviour to evaluate solutions. By including a novelty aspect the search space is more thoroughly explored, and deceptive local optima may be more easily avoided. In this thesis three Quality Diversity algorithms are implemented and evaluated in different settings: Novelty Search, Novelty Search with Local Competition, and Multi-dimensional Archive of Phenotypic Elites. The results show that Quality Diversity has potential to both increase the speed at which solutions are found and decrease the likelihood of premature convergence due to local optima. However, we also find that care must be taken in how behaviours are defined, and how some common techniques of Genetic Programming need to be adapted for Quality Diversity algorithms. / Ett av huvudsyftena med robotik och artificiell intelligens är att skapa system som självständigt kan lösa problem. En viktig del av detta är att skapa robotars beteenden. Beteendeträd är en trädstruktur som gör det möjligt att kombinera befintliga beteenden på lägre nivå till ett beteende på hög nivå. Att utforma lämpliga beteendeträd kan dock kräva både mycket tid och kunskap. Ett sätt att automatisera skapandet av beteendeträd är genom genetisk programmering, som utvecklar lösningar genom mutationer och kombinationer i likhet med biologisk evolution. Detta examensarbete undersöker hur genetisk programmering kan användas för att automatiskt generera beteendeträd. Mer specifikt undersöks om kvalitetsmångfald (Quality Diversity) kan användas för att förbättra sökningen. Kvalitetsmångfald beskriver en familj av algoritmer som kombinerar både prestanda och innovation i en lösnings beteende för att utvärdera lösningar. Genom att inkludera en innovationsaspekt blir sökområdet mer noggrant utforskat och vilseledande lokala optima kan lättare undvikas. I detta examensarbete implementeras och utvärderas tre kvalitetsmångfaldsalgoritmer i olika miljöer: Novelty Search, Novelty Search with Local Competition, och Multi-dimensional Archive of Phenotypic Elites. Resultaten visar att kvalitetsmångfald har potential att både öka hastigheten med vilken lösningar hittas och minska sannolikheten för tidig konvergens på grund av lokala optima. Vi konstaterar dock också att man måste vara försiktig med hur beteenden definieras och hur vissa vanliga tekniker för genetisk programmering måste anpassas för algoritmer med kvalitetsmångfald. / Eén van de belangrijkste doelstellingen van het vakgebied Robotica en Kunstmatige Intelligentie is het ontwikkelen van oplossingen die autonoom problemen kunnen oplossen. Een belangrijk onderdeel hiervan is het synthetiseren van gedragingen van robots. Gedragsbomen zijn een boomstructuur waarmee bestaande gedragingen van een lager niveau kunnen worden gecombineerd tot een gedrag van een hoger niveau door middel van taakwisseling. Het ontwerpen van geschikte gedragsbomen is echter soms niet haalbaar haalbaar vanwege de benodigde tijd en kennis. Een manier om het maken van gedragsbomen te automatiseren is door middel van genetisch programmeren, dat oplossingen ontwikkelt door mutaties en combinaties, vergelijkbaar met biologische evolutie. Deze masterproef onderzoekt hoe genetische programmering kan worden gebruikt om automatisch gedragsbomen te genereren. Meer specifiek of kwaliteitsdiversiteit (Quality Diversity) kan worden gebruikt om het zoeken te verbeteren. Kwaliteitsdiversiteit beschrijft een gebied van algoritmen die zowel prestaties als nieuwheid van een oplossingsgedrag combineren om oplossingen te evalueren. Door een nieuwheidsaspect te introduceren wordt de zoekruimte grondiger verkend en kunnen bedrieglijke lokale optima gemakkelijker worden vermeden. In deze masterproef worden drie algoritmen voor kwaliteitsdiversiteit toegepast en geëvalueerd in verschillende omgevingen: Novelty Search, Novelty Search with Local Competition en Multi-dimensional Archive of Phenotypic Elites. De resultaten tonen aan dat kwaliteitsdiversiteit het potentieel heeft om zowel de snelheid waarmee oplossingen worden gevonden te verhogen als de kans op voortijdige convergentie als gevolg van lokale optima te verminderen. Wij stellen echter ook vast dat zorgvuldigheid geboden is bij de definitie van gedragingen en dat sommige gebruikelijke technieken van genetisch programmeren moeten worden aangepast voor algoritmen met kwaliteitsdiversiteit.