• ISSN 0258-2724
  • CN 51-1277/U
  • EI Compendex
  • Scopus
  • Indexed by Core Journals of China, Chinese S&T Journal Citation Reports
  • Chinese S&T Journal Citation Reports
  • Chinese Science Citation Database
Volume 54 Issue 2
Jun.  2019
Turn off MathJax
Article Contents
Journal of Southwest Jiaotong University  > 2019  >  54(2): 428-435.
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
shu

Parallel Genetic Algorithm for SAT Problems Based on OpenMP

doi: 10.3969/j.issn.0258-2724.20170700
  • Received Date: 20 Sep 2017
  • Rev Recd Date: 04 Apr 2018
    • Available Online: 30 May 2018
  • Publish Date: 01 Apr 2019
    Abstract
  • 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.

     

    • FullText(HTML)
  • loading
    • References(24)
  • 黄拙,张健. 由一阶逻辑公式得到命题逻辑可满足性问题实例[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
    • Relative Articles
    • Supplements(0)
    • Cited By
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Figures(5)  / Tables(4)

    Get Citation
    PDF
    XML
    Article views(501) PDF downloads(15) Cited by()
    Proportional views
    Related

    Copyright © 2009 Journal of Southwest Jiaotong University

    Address: RM449 & 451, Administrative Building, Xipu Campus, Southwest Jiaotong University Western Hi-tech Zone, Chengdu, Sichuan 611756, P. R. China

    Tel: 028-66367562Fax: 028-66366552Email: xbz@home.swjtu.edu.cn

    Supported by: Beijing Renhe Information Technology Co. Ltd  support: info@rhhz.net

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return