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

摘要

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