A massively parallel Grammatical Evolution technique with OpenCL

Grammatical Evolution (GE) is a bio-inspired metaheuristic capable of evolving programs in an arbitrary language using a formal grammar. Among the major applications of the technique, the automatic inference of models from data can be highlighted. As with other genetic programming techniques, GE has a high computational cost. However, the algorithm has steps that can be computed independently, enabling the use of parallel computing to reduce the execution time and, consequently, making it possible its application to larger and more complex problems. Here, models of massively parallel computation for GE are studied and proposed using OpenCL, a framework for the creation of parallel algorithms in heterogeneous computing environments. Computational experiments were conducted to analyze the performance of an implementation using GPUs (Graphics Processing Units), when compared to a sequential implementation in CPUs (Central Processing Units). Finally, speedups of up to 528× were achieved, when all steps are performed in parallel in a GPU.