Abstract
We present an implementation of genetic algorithm (GA) training of feedforward artificial neural networks (ANNs) targeting commodity graphics cards (GPUs). By carefully mapping the problem onto the unique GPU architecture, we achieve order-of-magnitude speedup over a conventional CPU implementation. Furthermore, we show that the speedup is consistent across a wide range of data set sizes, making this implementation ideal for large data sets. This performance boost enables the genetic algorithm to search a larger subset of the solution space, which results in more accurate pattern classification. Finally, we demonstrate this method in the context of the 2009 UC San Diego Data Mining Contest, achieving a world-class lift on a data set of 94682 e-commerce transactions.
Introduction
Traditional training of Artificial Neural Networks (ANNs) typically relies on backpropagation, a gradient-descent method prone to converging on local extrema rather than global optima. Genetic Algorithms (GAs) offer a robust alternative by simulating evolution through populations of candidate solutions that undergo mutation and crossover. However, the computational cost of evaluating dozens of ANNs over thousands of generations has historically limited the practicality of GAs in data mining. This research addresses this bottleneck by leveraging NVIDIA’s CUDA platform to parallelize the evaluation phase on commodity GPUs.
Methodology and Implementation
The core of the implementation involves mapping the ANN architecture and the GA operators to the GPU's massively parallel environment. Each candidate network is represented as a "chromosome" containing real-valued arrays for edge weights, Radial Basis Function (RBF) center values, and widths.
To maximize throughput, several CUDA-specific optimizations were employed:
- Coalesced Memory Access: Feature data was stored in "feature-major order," ensuring that simultaneous thread reads access sequential memory addresses, significantly reducing latency.
- Multi-pass Thresholding: To calculate "lift"—a metric requiring the identification of the top 20% of scores—the authors developed a multi-pass algorithm using small binary heaps. This bypassed the 16 KB on-chip memory limits of the hardware by avoiding a full dataset sort.
- Robust Preprocessing: A Bayesian-inspired method converted nominal categories into numeric values, while Interquartile Range (IQR) standardization was used to prevent output saturation in floating-point calculations.
Performance Analysis and Results
The system was benchmarked using the 2009 UC San Diego Data Mining Contest dataset, which consists of 94,682 e-commerce transactions. The task involved identifying anomalies within a highly imbalanced dataset (1:50 class ratio).
As shown in the performance plots, the GPU implementation (GTX260 and GTX275) achieved a consistent 10x speedup over a modern x86 CPU. This advantage scales linearly with both the population size (number of ANNs) and the training set size. Notably, the GPU's performance advantage only manifests with sufficient parallel work; for very small populations (fewer than 10 ANNs), the overhead of data transfer to the GPU makes the CPU implementation more efficient.
In the UCSD contest, the model achieved a lift of 4.51 out of a maximum 5.0, demonstrating exceptional accuracy in identifying anomalies within the top 20% of ranked results. Furthermore, the GA's ability to evolve the network topology—by setting unnecessary weights or RBF widths to zero—effectively optimized the model architecture alongside its parameters.
Conclusion
By offloading the compute-intensive evaluation of ANN populations to the GPU, we have demonstrated that Genetic Algorithms can be a viable and highly performant tool for large-scale data mining. Future work will explore hybrid approaches combining GAs with local "hill-climbing" refinement and the migration of genetic operators (mating and mutation) entirely to the GPU to further minimize CPU-GPU communication overhead.
Summary updated