• ISSN 0258-2724
  • CN 51-1277/U
  • EI Compendex
  • Scopus 收录
  • 全国中文核心期刊
  • 中国科技论文统计源期刊
  • 中国科学引文数据库来源期刊

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

吴贯锋 徐扬 常文静 陈树伟 徐鹏

吴贯锋, 徐扬, 常文静, 陈树伟, 徐鹏. 基于OpenMP的并行遗传算法求解SAT问题[J]. 西南交通大学学报, 2019, 54(2): 428-435. doi: 10.3969/j.issn.0258-2724.20170700
引用本文: 吴贯锋, 徐扬, 常文静, 陈树伟, 徐鹏. 基于OpenMP的并行遗传算法求解SAT问题[J]. 西南交通大学学报, 2019, 54(2): 428-435. doi: 10.3969/j.issn.0258-2724.20170700
WU Guanfeng, XU Yang, CHANG Wenjing, CHEN Shuwei, XU Peng. Parallel Genetic Algorithm for SAT Problems Based on OpenMP[J]. Journal of Southwest Jiaotong University, 2019, 54(2): 428-435. doi: 10.3969/j.issn.0258-2724.20170700
Citation: WU Guanfeng, XU Yang, CHANG Wenjing, CHEN Shuwei, XU Peng. Parallel Genetic Algorithm for SAT Problems Based on OpenMP[J]. Journal of Southwest Jiaotong University, 2019, 54(2): 428-435. doi: 10.3969/j.issn.0258-2724.20170700

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

doi: 10.3969/j.issn.0258-2724.20170700
基金项目: 国家自然科学基金资助项目(61673320);中央高校基本科研业务费专项资金资助项目(2682017ZT12)
详细信息
    作者简介:

    吴贯锋(1986—),男,博士研究生,研究方向为智能信息处理、自动推理与并行计算,E-mail:wl520gx@gmail.com

  • 中图分类号: TP311.1

Parallel Genetic Algorithm for SAT Problems Based on OpenMP

  • 摘要: 为了提高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倍.

     

  • 图 1  迁移拓扑

    Figure 1.  Topology of the migration

    图 2  CGPHGA算法执行流程

    Figure 2.  Flow of CGPHGA

    图 3  HCGA、HGA和CGPHGA求解成功率比较

    Figure 3.  Success rates of HCGA,HGA and CGPHGA

    图 4  HGA和CGPHGA进化代数分布

    Figure 4.  Distribution graph of evolution of HGA and CGPHGA

    图 5  迁移规模对求解成功率的影响

    Figure 5.  Effect of volume of migration on the success rate

    表  1  实验环境对比

    Table  1.   Experimental conditions

    环境操作系统CPU内存/GB限时
    本文Win10 x64i3-32404200 s
    对比Win7 x64i5-3470423 h
    下载: 导出CSV

    表  2  改进混合遗传算法和并行遗传算法运行参数信息

    Table  2.   Parameters of HGA and CGPHGA

    变元子句算法种群大小LSA步长并行数迁移间隔迁移率
    50218HGA10010
    CGPHGA2510480.10
    75325HGA10010
    CGPHGA25104100.08
    100430HGA10010
    CGPHGA5010480.10
    125538HGA15015
    CGPHGA40154100.10
    下载: 导出CSV

    表  3  HCGA、HGA和CGPHGA平均时间对比

    Table  3.   Average time required by HCGA,HGA and CGPHGA

    变元子句HCGAHGA平均
    时间/s
    CGPHGA
    平均时间/s
    5021838.08923.45122.779
    75325128.75465.06461.132
    10043085 714.20093.93093.492
    1255380158.960 122.740
    下载: 导出CSV

    表  4  CGPHGA与其他并行算法对比情况

    Table  4.   Comparison of CGPHGA with the other parallel algorithms

    变元子句PGSATPDPLLCGPHGA
    S平均时间/sS平均时间/sS平均时间/s
    1255380.10186.4000.41101.2060.21122.541
    1506450.14152.9570.10173.612
    1757530.02199.2980.05196.793
    2259600.01198.570
    下载: 导出CSV
  • 黄拙,张健. 由一阶逻辑公式得到命题逻辑可满足性问题实例[J]. 软件学报,2005,16(3): 329-325.

    HUANG Zhuo, ZHANG Jian. Generating SAT instances from first-order formulas[J]. Journal of Software, 2005, 16(3): 329-325.
    LI Bingfen, ZHANG Y A. A hybrid genetic algorithm to solve 3-SAT problem.[C]//2016 12th International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery. Changsha: IEEE Press, 2016: 476-480
    潘晓英,焦李成,刘芳. 求解SAT问题的多智能体社会进化算法[J]. 计算机学报,2014,37(9): 2011-2020.

    PAN Xiaoying, JIAO Licheng, LIU Fang. A multi-agent social evolutionary algorithm for SAT problem[J]. Chinese Journal of Computers, 2014, 37(9): 2011-2020.
    LUO Chuan, CAI Shaowei, WU Wei, et al. Double configuration checking in stochastic local search for satisfiability[C]//Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence. Québec City: AAAI, 2014: 2703-2709
    郭莹,张长胜,张斌. 求解SAT问题的算法的研究进展[J]. 计算机科学,2016,43(3): 8-17.

    GUO Ying, ZHANG Changsheng, ZHANG Bin. Research advance of SAT solving algorithm[J]. Computer Science, 2016, 43(3): 8-17.
    HOLLAND J H. Adaptation in natural and artificial systems[M]. Cambridge: MIT press, 1992: 159-171
    DE JONG K A. The analysis of the behavior of a class of genetic adaptive systems[D]. Ann Arbor: University of Michigan, 1975
    GOLDBERG D E. Genetic algorithms in search optimization and machine learning[J]. Machine Learning, 1988, 3(2): 95-99.
    张琛,詹志辉. 遗传算法选择策略比较[J]. 计算机工程与设计,2009,30(23): 5471-5474,5478.

    ZHANG Chen, ZHAN Zhihui. Comparisons of selection strategy in genetic algorithm[J]. Computer Engineering and Design, 2009, 30(23): 5471-5474,5478.
    高家全,何桂霞. 并行遗传算法研究综述[J]. 浙江工业大学学报,2007(1): 56-59,72. doi: 10.3969/j.issn.1006-4303.2007.01.013

    GAO Jiaquan, HE Guixia. A review of parallel genetic algorithms[J]. Journal of Zhejiang University of Technology, 2007(1): 56-59,72. doi: 10.3969/j.issn.1006-4303.2007.01.013
    ROBERGE V, TARBOUCHI M, LABONTE G. Comparison of parallel genetic algorithm and particle swarm optimization for real-time UAV path planning[J]. IEEE Trans. Industrial Informatics, 2013, 9(1): 132-141. doi: 10.1109/TII.2012.2198665
    CALEGARI P, GUIDEC F, KUONEN P, et al. Parallel island-based genetic algorithm for radio network design[J]. J. Parallel Distrib. Comput, 1997, 47(1): 86-90. doi: 10.1006/jpdc.1997.1397
    YANG Hongtai, YANG Paichuan, HUANG Chinglien. A parallel genetic algorithm approach to solving the unit commitment problem:Implementation on the transputer networks[J]. IEEE Transactions on Power Systems, 1997, 12(2): 661-668. doi: 10.1109/59.589638
    TIMOTHY G. MATTSON B S, BERNA M. Patterns for parallel programming[M]. [S.l.]: Pearson Education, 2004: 76-78
    ASGHAR S, AUBANEL E, BREMNER D. A dynamic moldable job scheduling based parallel SAT solver[C]//2013 42nd International Conference on Parallel Processing (ICPP). [S.l.]: IEEE, 2013: 110-119
    HAMADI Y, JABBOUR S, SAIS L. ManySAT:a parallel SAT solver[J]. Journal on Satisfiability,Boolean Modeling and Computation, 2008, 1(6): 245-262.
    WU Guanfeng, XU Yang, CHANG Wenjing, et al. Parallel genetic algorithm for SAT problems based on the coarse-grained model[C]//Uncertainty Modelling in Knowledge Engineering and Decision Making: Proceedings of the 12th International FLINS Conference. Roubaix: Springer, 2016: 489-495
    MASTSUMURA T, NAKAMURA M, OKENCH J, et al. A parallel and distributed genetic algorithm on loosely-coupled multiprocessor systems[J]. IEICE Transactions on Fundamentals of Electronics,Communications and Computer Sciences, 1998, 81(4): 540-546.
    BECKERSM L M, DERKS EPPA, MELSSEN W J, et al. Using genetic algorithms for conformational analysis of biomacromolecules[J]. Computers & Chemistry, 1996, 20(4): 449-457.
    岳嵚. 粗粒度并行遗传算法的计算性能及其应用研究[D]. 武汉: 华中科技大学, 2008
    MENOUER T, BAARIR S. Parallel satisfiability solver based on hybrid partitioning method[C]//2017 25th Euromicro International Conference on Parallel, Distributed and Network-based Processing. [S.l.]: IEEE, 2017: 54-60
    LAYEB A, SAIDOUNI D E. A hybrid quantum genetic algorithm and local search based DPLL for max 3-SAT problems[J]. Applied Mathematics & Information Sciences, 2014, 8(1): 77-87.
    ROLI, A. Criticality and parallelism in structured SAT instances[C]//International Conference on Principles and Practice of Constraint Programming. Berlin: Springer, 2002, 714-719
    ZHANG Wenhui, HUANG Zhuo, ZHANG Jian. Parallel execution of stochastic search procedures on reduced SAT instances[C]//Pacific Rim International Conference on Artificial Intelligence. Berlin: Springer, 2002: 108-117
  • 加载中
图(5) / 表(4)
计量
  • 文章访问数:  489
  • HTML全文浏览量:  303
  • PDF下载量:  13
  • 被引次数: 0
出版历程
  • 收稿日期:  2017-09-20
  • 修回日期:  2018-04-04
  • 网络出版日期:  2018-05-30
  • 刊出日期:  2019-04-01

目录

    /

    返回文章
    返回