基于OpenMP的并行遗传算法求解SAT问题

摘要：

为了提高SAT(boolean satisfiability)问题求解效率,在OpenMP(open multi-processing)编程框架下,将遗传算法与局部搜索算法结合,改进了混合遗传算法中的选择算法,将原有选择操作的时间复杂度降低到O(N)级别.算法采用OpenMP中的编译制导语句#pragma omp parallel粗粒度并行化驱动混合遗传算法,采用#pragma omp single语句块实现了子种群间个体的同步迁移操作.与同类算法HCGA(hybrid cloud genetic algorithm)比较分析表明:改进算法HGA(hybrid genetic algorithm)以及并行后的混合遗传算法CGPHGA(coarse-grained parallel hybrid genetic algorithm)在求解成功率和求解效率上都有显著提高,部分问题求解成功率提高达5倍.

关键词：SAT问题、OpenMP、并行混合遗传算法、粗粒度模型

所属期刊栏目：54

分类号：TP311.1(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目61673320;中央高校基本科研业务费专项资金资助项目2682017ZT12;感谢中国无线电协会对项目的资助T/RAC015-2016

在线出版日期：2019-05-24（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：428-435