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

Parallel Genetic Algorithm for SAT Problems Based on OpenMP

作　　者：吴贯锋 徐扬[2,3] 常文静 陈树伟[2,3] 徐鹏 WU Guanfeng;XU Yang;CHANG Wenjing;CHEN Shuwei;XU Peng(School of Information Science and Technology,Southwest Jiaotong University,Chengdu 610031,China;National-Local Joint Engineering Laboratory of System Credibility Automatic Verification,Southwest Jiaotong University,Chengdu610031,China;School of Mathematics,Southwest Jiaotong University,Chengdu 610031,China)

机构地区：[1]西南交通大学信息科学与技术学院,四川成都610031 [2]西南交通大学系统可信性自动验证国家地方联合工程实验室,四川成都610031 [3]西南交通大学数学学院,四川成都610031

出　　处：《西南交通大学学报》2019年第2期428-435,共8页Journal of Southwest Jiaotong University

基　　金：国家自然科学基金资助项目(61673320);中央高校基本科研业务费专项资金资助项目(2682017ZT12)

摘　　要：为了提高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倍.To improve solving efficiency for SAT(boolean satisfiability)problems,a combination of genetic algorithm(GA)with local search algorithm(LSA)on the OpenMP(open multi-processing)framework was proposed.This combination improved the selection algorithm in the hybrid genetic algorithm(HGA)and reduced the time complexity of the original selection operation to O(N).The compiler guide statement#pragma omp parallel in OpenMP was applied to coarse-grained parallelization driven HGA,and the#pragma omp single statement block was used to implement the synchronization migration operation of the individuals in different sub-groups.Compared with the similar algorithm,HCGA(hybrid cloud genetic algorithm),both the improved algorithm(HGA)and the coarse-grained parallel hybrid genetic algorithm(CGPHGA)significantly improved solution success rate and problem solving efficiency.Solution success rate for some problems was increased by 5 times.

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

分 类 号：TP311.1[自动化与计算机技术—计算机软件与理论]