最小延时问题GPU并行加速变邻域搜索方法

A Variable Neighborhood Search Method Based on GPU Parallel Acceleration for Minimum Latency Problem

为了能够在尽可能短的时间内获得最小延时问题的优质解,提出一种运行在CPU-GPU混合环境中的变邻域搜索方法。在遗传算法的顺序交叉生成子代基因过程中,改变邻域结构以避免解方案陷入局部最优。该方法在避免局部最优问题的同时,又可以利用GPU的并行加速能力缩短算法运行时间。实验结果表明,对于大规模最小延时问题,可以在短时间内获得足够好的解。

In order to obtain the best solution of the minimum latency problem within the shortest time as possible,a variable neighborhood search method running in a mixed CPU-GPU environment was proposed.During the process of sequence constructive crossover method in genetic algorithm,the method changed the neighborhood structure to avoid the solution falling into a local optimum.This method can reduce the running time of the algorithm by using the GPU parallel acceleration capability while avoiding the local optimal problem.The experimental results illustrate that for large-scale minimum latency problem,the search method can obtain a good enough solution in a short time.