论文部分内容阅读
为了提高SAT问题求解效率,本文提出在OPENMP编程框架下,将遗传算法与局部搜索算法结合,改进了混合遗传算法中的选择算法,将原有选择操作的时间复杂度降低到O(N)级别。该算法采用OPENMP中的编译制导语句#pragmaomp parallel粗粒度并行化驱动混合遗传算法,采用#pragma omp single语句块实现了个体的同步迁移操作。文中详细介绍了整个算法的原理和实现过程。与同类算法比较分析表明:改进算法以及并行后的混合遗传算法在求解成功率和求解效率上都有显著提高,部分问题求解成功率提高达5倍,求解效率提高达1000倍。