為了提高SAT （boolean satisfiability）問題求解效率,在OpenMP （open multi-processing）編程框架下,將遺傳算法與局部搜索算法結(jié)合,改進了混合遺傳算法中的選擇算法,將原有選擇操作的時間復雜度降低到O（N）級別.算法采用OpenMP中的編譯制導語句#pragma omp parallel粗粒度并行化驅(qū)動混合遺傳算法,采用#pragma omp single語句塊實現(xiàn)了子種群間個體的同步遷移操作.與同類算法HCGA （hybrid cloud genetic algorithm）比較分析表明:改進算法HGA （hybrid genetic algorithm）以及并行后的混合遺傳算法CGPHGA（coarse-grained parallel hybrid genetic algorithm）在求解成功率和求解效率上都有顯著提高,部分問題求解成功率提高達5倍. 

【文章來源】：西南交通大學學報. 2019,54(02)北大核心EICSCD

【文章頁數(shù)】：8 頁

【參考文獻】：
期刊論文
[1]求解SAT問題的算法的研究進展[J]. 郭瑩,張長勝,張斌.  計算機科學. 2016(03)
[2]求解SAT問題的多智能體社會進化算法[J]. 潘曉英,焦李成,劉芳.  計算機學報. 2014(09)
[3]遺傳算法選擇策略比較[J]. 張琛,詹志輝.  計算機工程與設計. 2009(23)
[4]并行遺傳算法研究綜述[J]. 高家全,何桂霞.  浙江工業(yè)大學學報. 2007(01)
[5]由一階邏輯公式得到命題邏輯可滿足性問題實例(英文)[J]. 黃拙,張健.  軟件學報. 2005(03)

博士論文
[1]粗粒度并行遺傳算法的計算性能及其應用研究[D]. 岳嵚.華中科技大學 2008



本文編號：3440426