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

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

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

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.