基于散列函数加速的并行遗传算法

Parallel genetic algorithm acceleration method based on Hash function

针对新一代种群在并行遗传算法收敛过程中产生旧的个体可能性逐渐增大导致重复计算适应度的问题,提出一种基于散列函数加速的并行遗传算法(HPGA)。一方面利用散列函数查表时间复杂度低的优势,在散列表中存储算法运行中产生的个体以及其相应的适应度,减少个体适应度的重复计算;另一方面利用时间戳替代键,改进散列表存储方式,从而解决散列函数处理冲突的问题。通过求解集合覆盖问题对比了原始并行遗传算法和HPGA,结果表明HPGA在不影响求解精度的情况下,运行速度提升了3倍以上。

In the process of convergence of parallel genetic algorithm,the possibility of generating old individuals in new generation of population is gradually increasing,which leads to repetitive computations of fitness value. A parallel genetic algorithm acceleration method based on Hash function,namely HPGA(Hash-based Parallel Genetic Algorithm),was proposed. On the one hand,taking advantage of low time complexity,the Hash function was used to store individuals and their fitness values in the Hash table to reduce the repetitive computations;on the other hand,the timestamps were used instead of keys stored in the Hash table to solve the collision problem of the Hash function. By solving a set covering problem,original parallel genetic algorithm and HPGA were compared. Experimental proves that HPGA can increase the running speed by 4 times without affecting the accuracy of the solution.