GPU加速的并行遗传算法在金融模式挖掘中的应用

需积分: 10 114 浏览量更新于2024-07-18 收藏 4.54MB PDF 举报

"本书《Parallel Genetic Algorithms for Financial Pattern Discovery Using GPUs》探讨了如何利用GPU的并行计算能力来实现金融模式的发现，主要关注基因算法在金融数据分析中的应用。作者包括João Baúto、Rui Neves和Nuno Horta，他们通过 Springer Briefs in Applied Sciences and Technology 的 Computational Intelligence 系列出版了这本书。该系列由Janusz Kacprzyk主编，旨在快速发布和分享计算智能领域的最新进展和研究成果，涵盖神经网络、遗传算法、进化计算、人工智能等多个领域。" 正文: 基因算法（Genetic Algorithm，简称GA）是一种基于生物进化理论的优化方法，模仿了自然选择和遗传过程。在金融模式识别中，基因算法能够处理复杂的非线性问题，寻找最优解。由于金融市场的动态性和复杂性，传统的方法往往难以捕捉到有效的交易模式。而基因算法则可以通过模拟种群的进化，不断优化解决方案，从而在海量数据中发现潜在的规律。 GPU（Graphics Processing Unit）是专门设计用于图形处理的硬件，但近年来因其高度并行的计算能力，也被广泛应用在科学计算和大数据处理中。在金融模式发现中，利用GPU的并行计算能力可以极大地提高数据处理速度，减少计算时间，使得对大规模金融数据的分析成为可能。通过并行化基因算法，可以同时处理大量数据，加速模式识别的过程，提高算法的效率。本书详细介绍了如何将基因算法与GPU技术结合，以解决金融数据中的模式识别问题。章节结构清晰，便于读者逐步理解和掌握。书中可能涵盖了以下内容： 1. 基因算法的基础理论：包括种群初始化、选择、交叉和变异等操作，以及适应度函数的设计。 2. GPU编程基础：如CUDA编程模型，数据并行性和任务并行性的实现，以及如何利用GPU的计算资源。 3. 金融数据预处理：清洗、标准化和特征工程等步骤，为基因算法提供合适的输入。 4. 模型构建与优化：介绍如何构建适用于金融模式识别的基因算法模型，并进行参数调优。 5. 结果评估与验证：如何评价找到的模式的有效性，以及如何避免过拟合等问题。 6. 应用案例分析：展示实际金融数据上的应用示例，以及所发现的模式如何解释和应用。此外，书中还可能涉及其他计算智能技术，如模糊系统、神经网络和进化计算等，它们与基因算法的融合可能进一步提升模式发现的性能。这本书对于金融领域的研究人员和数据科学家来说，提供了宝贵的工具和理论指导，帮助他们在GPU的帮助下，更高效地挖掘金融市场的潜在规律。

1.2 Goals 3

The ﬁrst step is analysing the performance of SAX/GA and understand where are

the causes of prolonged execution time. Once the bottlenecks are identiﬁed, different

GPU strategies of optimization will be presented and compared to the original CPU

algorithm based on accuracy of the solution and speedup (Eq. 1.1).

Speedu p =

CPU Exec. Timeof SAX/GA

CPU + GPU Exec. Timeof Solution x

(1.1)

1.3 Book Outline

This Book is organized as follows:

• Chapter 2 discusses fundamental concepts, key to understand the proposed work,

such as pattern recognition or matching, GAs and GPUs.

• Chapter 3 presents a review of the state-of-the-art pattern recognition techniques

with practical application examples.

• Chapter 4 addresses the CPU implementation of the SAX/GA algorithm along

with a detailed explanation of the genetic operators involved. A benchmark anal-

ysis discusses the performance of SAX/GA and introduces possible locations to

accelerate the algorithm.

• Chapter 5 presents the developed solutions along with previous attempts to accel-

erate the SAX/GA algorithm. Each solution started as a prototype that evolved

based on the advantages and disadvantages identiﬁed.

• Chapter 6 discusses the experimental results obtained for each solution and com-

pares them to the original implementation. Solutions are evaluated based in two

metrics, the speedup and the ROI indicator.

• Chapter 7 concludes the developed work and indicates aspects of the SAX/GA

algorithm that can be improve in the near future.

References

1. E.F. Fama, The behavior of stock-market prices. J. Bus. 38(1), 34–105 (1965)

2. A. Canelas, R. Neves, N. Horta, A SAX-GA approach to evolve investment strategies on

ﬁnancial markets based on pattern discovery techniques. Expert Syst. Appl. 40(5), 1579–1590

(2013), http://www.sciencedirect.com/science/article/pii/S0957417412010561. https://doi.org/

10.1016/j.eswa.2012.09.002

3. A. Canelas, R. Neves, N. Horta, Multi-dimensional pattern discovery in ﬁnancial time series

using sax-ga with extended robustness, in GECCO (2013). https:// doi.org/10.1145/2464576.

2464664

6 2 Background

ED( p, q) =



− p

)

+ (q

− p

)

(2.1)

At ﬁrst sight it is possible to observe some important issues. What if both time

series have a different magnitude, and different alignments? With a different magni-

tude, applying the ED method would be pointless as the main feature lies in direct

spatial comparison. The same result is observed with different alignments as both

series may be equal or the very least partially similar, but since they shifted or

unaligned, a direct match will not be found.

2.1.2 Dynamic Time Warping

An alignment technique, Dynamic Time Warping (DTW) [1], can be used to solve the

previous problem. This approach aligns two times series, P = ( p

, p

, ..., p

)

and Q = (q

, q

, ..., q

), using a matrix D of n × m. First, to each pair (i, j)

in D, the distance ( p

− q

)

is calculated. The warping or alignment path (W )is

obtained by minimizing the cumulative distance deﬁned by,

γ(i, j) = D(i, j) + mi n[γ(i − 1, j), γ (i − 1, j − 1), γ (i, j − 1)] (2.2)

Iterating through all entries of D is a costly problem with exponential complexity.

To reduce the search space and therefore the number of possible paths, some limi-

tations are introduced to the initial problem. Points in the warping path are mono-

tonically ordered so that i

k−1

 i

and j

k−1

 j

preventing that a sub-sequence is

associated a priori and a posteriori. The resulting path must be a continuous path,

starting in (i = 1, j = 1) and ending in (i = n, j = m), so that the algorithm does

not ignore sub-sequences, locking into partial solutions. A warping path that follows

the diagonal of D indicates that the input query Q is completely aligned with the

time series P and therefore they are similar.

2.1.3 Piecewise Linear Approximation

DTW was capable of solving the alignment problem however it was through an

increase in the computational time. Some optimizations could be done to DTW

algorithm but the main issue would remain untouched, the dataset. Financial time

series tend to present small variance in value during a time period and, taking this

into consideration, some points of the dataset can be eliminated.

With a sliding-window Piecewise Linear Approximation (PLA) approach, the time

series is condensed into a representation using N breakpoints where each breakpoint

is the last point that satisﬁed a threshold condition. The series can then be approxi-

mated by two methods, a linear interpolation, connecting each breakpoint into linear

8 2 Background

¯p

·i



·(i−1)+1



¯p

: element ith of approximated time series



: element jth of original time series

n : size of original time series

w : size of PAA time series

(2.4)

In order to discover similarities in time series, PAA uses a ED-based formula

where, instead of the point-to-point calculation, it uses the mean value of the reduced

series (Eq. 2.5).

Dis tance(P, Q) =















i=1

( ¯p

−¯q

)

(2.5)

2.1.5 Symbolic Aggregate approXimation

SAX [4] can be viewed as an improvement to PAA as it still uses this method to

obtain a dimensional reduced time series but adds a new type of data transformation,

numeric to symbolic representation.

This transformation relies in a Normal distribution, N ∼ (0, 1), with α

intervals

where the probability between the z-score of α

i+1

(β

i+1

) minus α

z-score (β

)must

be equal to

, where each interval is to considered as a symbol. For example, with

= 3, there are 3 intervals, all of them with equal probability of 33.3% and with

symbolic representation,

α = ’A’ ii f −∞< c

<β

α = ’B’ ii f β

< c

<β

α = ’C’ ii f β

< c

< +∞

(2.6)

In Fig. 2.2, frame 3 (c

) has an average value of 1.5 and considering an alphabet

with 3 letters (α = 3), from Table 2.1 and Eq. 2.6 it is possible to assess that c

is between β

and ∞ and, therefore, the corresponding letter is ’C’. This method

ensures that, in an alphabet containing all possible symbols in the SAX representation,

each symbol has equal probability allowing a direct comparison. The z-score values

(Table 2.1) were obtained from [4, 5].

Now that PAA series is normalized and the z-scores of α are known, the SAX

representation can be easily obtained. To each segment of PAA (c

) a corresponding

α interval will be assigned so that α must satisfy to conditions similar to those in

Eq. 2.6. The transformation in Fig. 2.2 compressed a window with size equal to 500

into a SAX sequence with si ze = 10 and an alphabet of 3 letters.

Until this point, there is not must of an improvement since there is not a way to

compare two time series, the input and search pattern. The authors of SAX faced

a struggle, how to compared two series if they are represented in a string format?

剩余102页未读，继续阅读

zzzzasleep

粉丝: 2
资源: 6

GPU加速的并行遗传算法在金融模式挖掘中的应用

Computational Intelligence for Pattern Recognition

Parallel Genetic Algorithms Theory and Real World Applications

parallel_cgal_Parallel Geometric Algorithms for Multi-Core Computers

parallel 和parallel for

parallel_for｛parallel_for｛｝｝

intel parallel studio xe for linux 下载

Parallel Guidance Network for image inpainting

Parallel.For 和Parallel.ForEach 例子

pragma omp parallel for

Parallel.For怎么用

最新资源