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

发布时间：2021-10-16 20:10

　　为了提高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倍. 

【文章来源】：西南交通大学学报. 2019,54(02)北大核心EICSCD

【文章页数】：8 页

【参考文献】：
期刊论文
[1]求解SAT问题的算法的研究进展[J]. 郭莹,张长胜,张斌.  计算机科学. 2016(03)
[2]求解SAT问题的多智能体社会进化算法[J]. 潘晓英,焦李成,刘芳.  计算机学报. 2014(09)
[3]遗传算法选择策略比较[J]. 张琛,詹志辉.  计算机工程与设计. 2009(23)
[4]并行遗传算法研究综述[J]. 高家全,何桂霞.  浙江工业大学学报. 2007(01)
[5]由一阶逻辑公式得到命题逻辑可满足性问题实例(英文)[J]. 黄拙,张健.  软件学报. 2005(03)

博士论文
[1]粗粒度并行遗传算法的计算性能及其应用研究[D]. 岳嵚.华中科技大学 2008



本文编号：3440426