Abstract
Evolutionary Algorithms (EAs) are powerful optimization tools but often suffer from high computational costs. This paper presents a novel approach to accelerate the Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA) by offloading its core variation operator, Gene-pool Optimal Mixing (GOM), to the GPU. By leveraging Gray-Box Optimization (GBO) principles and graph coloring, the proposed method identifies independent variable sets that can be processed in parallel. Experimental results on Max-Cut problems demonstrate speedups of up to 100x on large sparse instances, though performance degrades on dense graphs due to synchronization overhead.
Introduction
Evolutionary Algorithms are widely used for complex optimization, yet their serial nature often limits scalability. Traditional parallelization typically focuses on evaluating multiple individuals simultaneously, which is effective only for massive populations. This research addresses the bottleneck of the Gene-pool Optimal Mixing (GOM) operator within GOMEA. GOM is highly effective because it performs immediate fitness evaluations after small modifications, but this "greedy" approach is inherently serial. By transitioning to a Gray-Box Optimization (GBO) setting—where variable interactions are known—the authors propose a fine-grained parallelization strategy suitable for modern GPU architectures.
Methodology: Parallelizing GOM
The core innovation lies in identifying "conditionally independent" linkage sets that can be modified and evaluated simultaneously without interference. This is achieved through a three-stage process:
- Variable Interaction Graph (VIG): Mapping dependencies between problem variables.
- Linkage Model Interaction Graph (LMIG): Constructing a higher-level graph where nodes represent groups of variables (linkage sets) and edges represent dependencies derived from the VIG.
- Graph Coloring: Applying the Welsh-Powell algorithm to the LMIG. Nodes with the same color are independent and can be processed in parallel on the GPU.
The implementation utilizes CUDA and the Thrust library for efficient parallel reductions. To optimize for the GPU, certain serial components like "Forced Improvement" were disabled, and a static Linkage Tree model was employed.
Experimental Evaluation
The approach was tested on the Weighted Maximum Cut (Max-Cut) problem using three datasets: Set A (fully connected/dense), Set B (3D torus/sparse), and Set C (large-scale real-world benchmarks).
Key Results
The GPU-accelerated GOMEA achieved a 100x speedup on large, sparse graphs from the BIQMAC library compared to the serial CPU implementation. For sparse 3D torus graphs, the parallel version exhibited significantly better scaling with problem dimensionality.
However, a "sparsity sweet spot" exists. On the dense graphs of Set A, the GPU version was actually slower than the CPU. This highlights that the overhead of managing GPU threads and memory only pays off when the problem structure allows for significant parallel work.
Conclusion and Future Work
This work demonstrates that fine-grained parallelization of GOM can yield massive performance gains in GBO settings, particularly for sparse problems. Future research will focus on developing a parallel-friendly "Forced Improvement" procedure and parallelizing the construction of the Linkage Tree to further enhance the algorithm's efficiency. Extending this framework to other GBO domains, such as medical image registration, remains a promising direction.
Summary updated