  In a Gray-Box Optimization (GBO) setting that allows for partial evaluations,
the fitness of an individual can be updated efficiently after a subset of its
variables has been modified. This enables more efficient evolutionary
optimization with the Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA)
due to its key strength: Gene-pool Optimal Mixing (GOM). For each solution, GOM
performs variation for many (small) sets of variables. To improve efficiency
even further, parallel computing can be leveraged. For EAs, typically, this
comprises population-wise parallelization. However, unless population sizes are
large, this offers limited gains. For large GBO problems, parallelizing
GOM-based variation holds greater speed-up potential, regardless of population
size. However, this potential cannot be directly exploited because of
dependencies between variables. We show how graph coloring can be used to group
sets of variables that can undergo variation in parallel without violating
dependencies. We test the performance of a CUDA implementation of parallel GOM
on a Graphics Processing Unit (GPU) for the Max-Cut problem, a well-known
problem for which the dependency structure can be controlled. We find that, for
sufficiently large graphs with limited connectivity, finding high-quality
solutions can be achieved up to 100 times faster, showcasing the great
potential of our approach.
