Parallel Genetic Algorithms for Financial Pattern Discovery Using GPUs | springerprofessional.de

Springer Professional

Top

2018 | Book

Read chapter Read first chapter

Parallel Genetic Algorithms for Financial Pattern Discovery Using GPUs

Authors: Dr. João Baúto, Prof. Rui Neves, Prof. Nuno Horta

Publisher: Springer International Publishing

Book Series : SpringerBriefs in Applied Sciences and Technology

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access

About this book

This Brief presents a study of SAX/GA, an algorithm to optimize market trading strategies, to understand how the sequential implementation of SAX/GA and genetic operators work to optimize possible solutions. This study is later used as the baseline for the development of parallel techniques capable of exploring the identified points of parallelism that simply focus on accelerating the heavy duty fitness function to a full GPU accelerated GA.

Advertisement

Table of Contents

Frontmatter

Chapter 1. Introduction

Abstract

This chapter presents a brief description on the scope of the problem addressed in the book which is the performance and optimization of algorithms based on pattern discovery. Additionally, the main goals to be achieved by this work are discussed along with a breakdown of the document’s structure.

João Baúto, Rui Neves, Nuno Horta

Chapter 2. Background

Abstract

This Chapter presents some fundamental concepts required to fully understand the topics discussed. First, a brief introduction to some concepts related to pattern matching and time series dimensional reduction followed, lastly, by an historical and architectural review of GPUs. Time series analysis is one of the pillar of technical analysis in financial markets. Analysts use variations in a stock’s price and volume of trade in combination with several well known technical indicators and chart patterns to forecast what will be the future price of a stock or speculate at least whether the price will increase or decrease. However, the widespread use of this indicators and patterns may indirectly influence the direction of the market causing it to converge into chart patterns that investors recognize.

João Baúto, Rui Neves, Nuno Horta

Chapter 3. State-of-the-Art in Pattern Recognition Techniques

Abstract

Pattern recognition, matching or discovery are terms associated with the comparison of an input query, a pattern, with a time series sequence. These input queries can be patterns similar to those presented in Chen (Essentials of Technical Analysis for Financial Markets, 2010 [1]) or user-defined ones. Although focus will be in pattern matching techniques applied to financial time series, these techniques proved to be very versatile and expandable to different areas, going from the medical sector with applications in Electrocardiogram (ECG) Chen et al. (Comput Methods Programs Biomed 74:11–27, 2004 [2]) to the energy sector with forecasting and modelling of buildings energetic profile Iglesias and Kastner (Energies 6:579, 2013 [3]).

João Baúto, Rui Neves, Nuno Horta

Chapter 4. SAX/GA CPU Approach

Abstract

This chapter discusses the sequential implementation of the SAX/GA algorithm which is an algorithm designed for the optimization of market trading solutions. SAX/GA uses the SAX representation to validate the similarity between a possible solution and the training dataset, while the GA optimizes the pool of trading strategies based on a function that defines the quality of each solution. Later on, a benchmark analysis is presented in order to understand the performance of SAX/GA and locate possible regions that can take advantage of a parallel implementation.

João Baúto, Rui Neves, Nuno Horta

Chapter 5. GPU-Accelerated SAX/GA

Abstract

This chapter presents several solutions to accelerate the SAX/GA algorithm using a GPU with each solution aiming at maximizing the parallel potential of SAX/GA. The first implementation, Solution A, focuses in the bottleneck identified previously, the SAX transformation, while Solution B and C try to explore a new method to optimize the populations of individuals and take further advantage of the GPU architecture to the benefit of SAX/GA.

João Baúto, Rui Neves, Nuno Horta

Chapter 6. Results

Abstract

In this chapter the results from the three developed solutions described in the previous chapter are presented. First, the SAX/GA constraints for both the CPU and GPU solutions are presented and finally the experimental results of the three solutions. The two metrics used to evaluate the proposed solutions are the speedup (Eq. 1.1) or ratio between the execution time of each implementation comparatively to the original CPU algorithm and the quality of the trading strategy that the algorithm converged into. The execution time takes in consideration the time of the serial execution performed by the CPU and the parallel computation by the GPU. As for the quality of trading strategies, the performance is evaluated using the ROI indicator (Eq. 6.1) and what would be the ideal strategy. An additional test is also applied to the implemented solution in order to understand whether the proposed predictive FSM has a significant impact in the performance of the GPU solutions.

João Baúto, Rui Neves, Nuno Horta

Chapter 7. Conclusions and Future Work

Abstract

This work presents a detailed study of the parallelization of a Genetic Algorithm (GA) for pattern discovery using the Symbolic Aggregate approXimation (SAX). The main purpose was to understand the structure of the SAX/GA and if it could benefit from the highly parallel computation that the GPU provides. Each step of the genetic algorithm was analysed thoroughly and, based on a benchmark analysis applied to the sequential SAX/GA, three distinct solutions are proposed, each with its own benefits.

João Baúto, Rui Neves, Nuno Horta

Title: Parallel Genetic Algorithms for Financial Pattern Discovery Using GPUs
Authors: Dr. João Baúto
Prof. Rui Neves
Prof. Nuno Horta
Copyright Year: 2018
Publisher: Springer International Publishing
Electronic ISBN: 978-3-319-73329-6
Print ISBN: 978-3-319-73328-9
DOI: https://doi.org/10.1007/978-3-319-73329-6

Premium Partner