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

Parallel Genetic Process Mining Based on Graphics Processing Unit

作　　者：李龚亮 敬思远[3] 郭兵[1] 沈艳[4] LI Gong-liang;JING Si-yuan;GUO Bin;SHEN Yan(School of Computer,Sichuan University Chengdu 610065;Institute of Computing Applications,China Academy of Engineering Physics Mianyang Sichuan 621000;School of Computer Science,Leshan Normal University Leshan Sichuan 614000;School of Control Engineering,Chengdu University of Information Technology Chengdu 610225)

机构地区：[1]四川大学计算机学院,成都610065 [2]中国工程物理研究院计算机应用研究所,四川绵阳621000 [3]乐山师范学院计算机科学学院,四川乐山614000 [4]成都信息工程大学控制工程学院,成都610225

出　　处：《电子科技大学学报》2019年第6期918-924,共7页Journal of University of Electronic Science and Technology of China

基　　金：国家自然科学基金重点项目(61332001);国家自然科学基金(61772352,61472050);四川省科技计划(2018ZDZX0010,2017GZDZX0003,2018JY0182)

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

关 键 词：遗传算法 图形处理器 PETRI网 过程挖掘 工作流 

分 类 号：TP311.1[自动化与计算机技术—计算机软件与理论]