基于图形处理器的并行遗传过程挖掘

Parallel Genetic Process Mining Based on Graphics Processing Unit

  • 摘要: 为提高遗传过程挖掘算法对大规模事件日志处理的性能,该文提出一种基于GPU的并行遗传过程挖掘算法。由于传统基于二进制的染色体编码不能表示因果矩阵中的AND-Split/AND-Join和OR-Split/OR-Join结构,提出一种新的染色体编码方案。该方案通过内容、标识、位置3个数组,有效地解决了GPU上因果矩阵的遗传表示问题。同时,设计并实现了高效的遗传交叉/变异算子和适应度并行计算方法。仿真实验表明,与当前CPU上的遗传过程挖掘算法相比,本文算法在求解精度和收敛速度方面都具有明显优势,并且在两个数据集上分别取得36.4倍和47.2倍的执行时间加速比。

     

    Abstract: To improve the performance of genetic process mining algorithm for handling large scale event log, a GPU-based parallel genetic process mining algorithm is proposed. Since traditional binary chromosome coding method can not represent the AND-Split/AND-Join and the OR-Split/OR-Join structures in causal matrix, a new coding method of chromosome is proposed. The proposed method can effectively solve the problem of genetic representation of causal matrix on graphics processing units (GPU) by three arrays, which are content, labels and position. Meanwhile, the efficient genetic crossover/mutation operators and a parallel method of fitness value computation are designed and implemented. Simulation experiments show that the proposed algorithm, compared with the CPU-based genetic process mining algorithm, has obvious advantages in precision and convergence rate, and moreover it obtains speedup of 36.4 and 47.2 on two data sets respectively.

     

/

返回文章
返回