簡易檢索 / 詳目顯示

研究生: 黃聖龍
Huang, Sheng-Lung
論文名稱: 利用監督式機器學習方法對SAT 問題進行分類
SAT Problem Classification by Supervised Machine Learning Method
指導教授: 陳盈如
Chen, Yean-Ru
學位類別: 碩士
Master
系所名稱: 電機資訊學院 - 電機工程學系
Department of Electrical Engineering
論文出版年: 2021
畢業學年度: 109
語文別: 中文
論文頁數: 77
中文關鍵詞: 布林可滿足性問題NP 完全問題分類問題神經網路
外文關鍵詞: Boolean satisfiability problem, NP complete, Classification, Neural Network
相關次數: 點閱:73下載:0
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • 摘要i Abstract ii 英文延伸摘要iii 誌謝viii 目錄ix 表格xi 圖片xii 第一章緒論1 1.1 SAT 問題 1 1.1.1 名詞介紹 2 1.2 SAT 演算法 3 1.2.1 完整演算法 4 1.2.2 不完整演算法 6 1.3 SAT 演算法配置 7 1.4 機器學習方法 8 1.5 研究動機與論文貢獻 10 1.6 論文組織 11 第二章文獻探討12 2.1 SATzilla 12 2.2 Simple algorithm portfolio for SAT 15 2.3 與Related work 進行比較 16 第三章研究方法17 3.1 研究動機 17 3.2 背景知識與專有名詞介紹 18 3.2.1 候選求解器 18 3.2.2 神經網路 24 3.3 流程圖 30 3.4 CNF 實例以及提取的特徵 31 3.4.1 初版選擇的CNF 及其特徵 32 3.4.2 標籤的原則 47 3.4.3 特徵分析 50 3.4.4 最終選擇的CNF 及其特徵 55 第四章實驗結果61 4.1 環境設置 61 4.2 分類器的準確率 61 4.3 數據比較 65 4.3.1 比較執行時間 65 4.3.2 比較準確率 67 4.4 利用Random Forest 分析特徵的重要性 69 4.5 與單一個SAT solver 比較執行時間 70 第五章結論75 References 76

    [1] Yean-Ru Chen Chin-Wei Lien. A hardware sat solver with efficient bcp. Masters thesis, National Cheng Kung University, 2019.
    [2] Stephen A Cook. The complexity of theorem-proving procedures. In Proceedings of the third annual ACM symposium on Theory of computing, pages 151–158, 1971.
    [3] Martin Davis, George Logemann, and Donald Loveland. A machine program for
    theorem-proving. Communications of the ACM, 5(7):394–397, 1962.
    [4] Richard Evans, David Saxton, David Amos, Pushmeet Kohli, and Edward Grefenstette. Can neural networks understand logical entailment? arXiv preprint arXiv:1802.08535, 2018.
    [5] Carla P Gomes and Bart Selman. Algorithm portfolios. Artificial Intelligence, 126(1-2):43–62, 2001.
    [6] Holger H Hoos and Thomas Stützle. Stochastic local search: Foundations and applications. Elsevier, 2004.
    [7] Samuel H Huang. Supervised feature selection: A tutorial. Artif. Intell. Res., 4(2):22–37, 2015.
    [8] Frank Hutter, Holger H Hoos, Kevin Leyton-Brown, and Thomas Stützle. Paramils: an automatic algorithm configuration framework. Journal of Artificial Intelligence Research,36:267–306, 2009.
    [9] Michail G Lagoudakis and Michael L Littman. Learning to select branching rules in the dpll procedure for satisfiability. Electronic Notes in Discrete Mathematics, 9:344–359, 2001.
    [10] D Mitchell, B Selman, and H Leveque. A new method for solving hard satisfiability problems. In Proceedings of the tenth national conference on artificial intelligence (AAAI-92), pages 440–446, 1992.
    [11] Mladen Nikolić, Filip Marić, and Predrag Janičić. Instance-based selection of policies for sat solvers. In International Conference on Theory and Applications of Satisfiability Testing, pages 326–340. Springer, 2009.
    [12] Mladen Nikolić, Filip Marić, and Predrag Janičić. Simple algorithm portfolio for sat. Artificial Intelligence Review, 40(4):457–465, 2013.
    [13] Eugene Nudelman, Kevin Leyton-Brown, Holger H Hoos, Alex Devkar, and Yoav Shoham. Understanding random sat: Beyond the clauses-to-variables ratio. In International Conference on Principles and Practice of Constraint Programming, pages 438–452. Springer, 2004.
    [14] Paul Walton Purdom, Jr and Cynthia A Brown. The pure literal rule and polynomial average time. SIAM Journal on Computing, 14(4):943–953, 1985.
    [15] Philip Sedgwick. Pearson's correlation coefficient. Bmj, 345, 2012.
    [16] Bart Selman, Henry A Kautz, and Bram Cohen. Noise strategies for improving local search. In AAAI, volume 94, pages 337–343, 1994.
    [17] Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo de Moura, and David L Dill. Learning a sat solver from single-bit supervision. arXiv preprint arXiv:1802.03685, 2018.
    [18] Yean-Ru Chen Shi-Wei Wu. A non-exhaustive hardware sat solver with deeper state exploration capability. Master’s thesis, National Cheng Kung University, 2019.
    [19] Dave AD Tompkins and Holger H Hoos. Ubcsat: An implementation and experimentation environment for sls algorithms for sat and max-sat. In International conference on theory and applications of satisfiability testing, pages 306–320. Springer, 2004.
    [20] Dave AD Tompkins, Frank Hutter, and Holger H Hoos. Scaling and probabilistic
    smoothing (saps). SAT, 2004.
    [21] Lin Xu, Frank Hutter, Holger H Hoos, and Kevin Leyton-Brown. Satzilla: portfoliobased algorithm selection for sat. Journal of artificial intelligence research, 32:565–606, 2008.
    [22] Lin Xu, Frank Hutter, Holger H Hoos, and Kevin Leyton-Brown. Satzilla2009: an
    automatic algorithm portfolio for sat. SAT, 4:53–55, 2009.

    無法下載圖示 校內:2026-09-24公開
    校外:2026-09-24公開
    電子論文尚未授權公開,紙本請查館藏目錄
    QR CODE