Baúto / Neves / Horta Parallel Genetic Algorithms for Financial Pattern Discovery Using GPUs

1. Auflage 2018
ISBN: 978-3-319-73329-6
Verlag: Springer Nature Switzerland
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 103 Seiten

Reihe: SpringerBriefs in Applied Sciences and Technology

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. 

João Baúto works at Fundacao Champalimaud in Lisbon, Portugal. He implements high performance computing tools applied to neuroscience and cancer research.
Rui Ferreira Neves is a professor at Instituto Superior Técnico, Portugal. His research activity comprises evolutionary computation and pattern matching applied to the financial markets, sensor networks, embedded systems and mixed signal integrated circuits.
Nuno Horta is the Head of the Integrated Circuits Group, Instituto de Telecomunicacoes, Portugal. His reseach interests are mainly in analog and mixed-sgnal IC design, analog IC design automation, soft computing and data science.

Autoren/Hrsg.

Baúto, João

Neves, Rui

Horta, Nuno

Inhaltsverzeichnis

1;Preface;7
2;Contents;9
3;Acronyms;12
4;1 Introduction;14
4.1;1.1 Motivation;15
4.2;1.2 Goals;15
4.3;1.3 Book Outline;16
4.4;References;16
5;2 Background;17
5.1;2.1 Time Series Analysis;17
5.1.1;2.1.1 Euclidean Distance;17
5.1.2;2.1.2 Dynamic Time Warping;18
5.1.3;2.1.3 Piecewise Linear Approximation;18
5.1.4;2.1.4 Piecewise Aggregate Approximation;19
5.1.5;2.1.5 Symbolic Aggregate approXimation;20
5.2;2.2 Genetic Algorithm;22
5.2.1;2.2.1 Selection Operator;23
5.2.2;2.2.2 Crossover Operator;24
5.2.3;2.2.3 Mutation Operator;24
5.3;2.3 Graphics Processing Units;25
5.3.1;2.3.1 NVIDIA's GPU Architecture Overview;25
5.3.2;2.3.2 NVIDIA's GPU Architectures;27
5.3.3;2.3.3 CUDA Architecture;29
5.4;2.4 Conclusions;31
5.5;References;31
6;3 State-of-the-Art in Pattern Recognition Techniques;33
6.1;3.1 Middle Curve Piecewise Linear Approximation;33
6.2;3.2 Perceptually Important Points;34
6.3;3.3 Turning Points;38
6.4;3.4 Symbolic Aggregate approXimation;40
6.5;3.5 Shapelets;40
6.6;3.6 Conclusions;42
6.7;References;43
7;4 SAX/GA CPU Approach;1
7.1;4.1 SAX/GA CPU Approach;45
7.1.1;4.1.1 Population Generation;46
7.1.2;4.1.2 Fitness Evaluation;46
7.1.3;4.1.3 Population Selection;50
7.1.4;4.1.4 Chromosome Crossover;50
7.1.5;4.1.5 Individual Mutation;51
7.2;4.2 SAX/GA Performance Analysis;52
7.3;4.3 Conclusions;55
7.4;References;56
8;5 GPU-Accelerated SAX/GA;57
8.1;5.1 Parallel SAX Representation;57
8.1.1;5.1.1 Prototype 1: SAX Transformation On-Demand;57
8.1.2;5.1.2 Prototype 2: Speculative FSM;59
8.1.3;5.1.3 Solution A: SAX/GA with Speculative GPU SAX Transformation;62
8.2;5.2 Parallel Dataset Training;67
8.2.1;5.2.1 Prototype 3: Parallel SAX/GA Training;67
8.2.2;5.2.2 Solution B: Parallel SAX/GA Training with GPU Fitness Evaluation;69
8.3;5.3 Fully GPU-Accelerated SAX/GA;72
8.3.1;5.3.1 Population Generation Kernel;73
8.3.2;5.3.2 Population Selection;74
8.3.3;5.3.3 Gene Crossover Kernel;75
8.3.4;5.3.4 Gene Mutation Kernel;75
8.3.5;5.3.5 Execution Flow;77
8.4;5.4 Conclusions;77
8.5;Reference;78
9;6 Results;79
9.1;6.1 SAX/GA Initial Constraints;79
9.2;6.2 Study Case A: Execution Time;80
9.2.1;6.2.1 Solution A: SAX/GA with Speculative FSM;80
9.2.2;6.2.2 Solution B: Parallel Dataset Training;86
9.2.3;6.2.3 Solution C: Fully GPU-Accelerated SAX/GA;89
9.3;6.3 Study Case B: FSM Prediction Rate;93
9.4;6.4 Study Case C: Quality of Solutions;96
9.5;6.5 Conclusions;100
10;7 Conclusions and Future Work;101
10.1;7.1 Future Work;103