论文标题
灰色盒优化设置中的GPU加速平行基因池最佳混合
GPU-Accelerated Parallel Gene-pool Optimal Mixing in a Gray-Box Optimization Setting
论文作者
论文摘要
在允许部分评估的灰色框优化（GBO）设置中，可以在修改其变量子集后有效地更新个人的适应性。由于其关键强度：基因池最佳混合（GOM），这可以通过基因池最佳混合进化算法（GOMEA）进行更有效的进化优化。对于每种解决方案，GOM对许多（小）变量集进行变化。为了进一步提高效率，可以利用并行计算。对于EAS而言，通常这包括人口平行化。但是，除非人口规模较大，否则这会提供有限的收益。对于大型GBO问题，无论总体规模如何，基于GOM的变化都具有更大的加速潜力。但是，由于变量之间的依赖关系，无法直接利用该潜力。我们展示了如何将图形着色用于分组可以在不违反依赖项的情况下并行进行变化的变量集。我们在图形处理单元（GPU）上测试了CUDA实现的性能，以解决最大切割问题，这是一个众所周知的问题，可以控制依赖关系结构。我们发现，对于连通性有限的足够大图，可以更快地找到高质量的解决方案，从而展示我们方法的巨大潜力。
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.
