Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/19767
標題: 在實數空間上解可滿足性問題之多軌跡搜索法
Multiple Trajectory Search for the Satisfiability Problem in Real Domain
作者: 林政翰
Lin, Cheng-Han
關鍵字: 可滿足性問題;多軌跡搜索法
出版社: 資訊科學與工程學系所
引用: 參考文獻 [1] 林祐安(2009),解可滿足性問題之混合式基因演算法,國立中興大學資訊工程研究所碩士論文。 [2] T. Back, A. Eiben and M. Vink, "A Superior Evolutionary Algorithm for 3-SAT," Proceedings of the 7th Annual Conference on Evolutionary Programming, vol. 1477 of LNCS, pp. 125-136, 1998. [3] A. Beringer, G. Aschemann, H.H. Hoos, M. Metzger and A.Weiss, "GSAT versus Simulated Annealing," Proceedings of the European Conference on Artificial Intelligence, pp. 130-134, 1994. [4] M. Davis and H. Putnam, "A Computing Procedure for Quantification Theory," J. ACM, vol. 7, no. 3, pp. 201-215, July 1960. [5] M. de Jong and W. Kosters, "Solving 3-SAT using adaptive sampling," Proceedings of 10th Dutch/Belgian Artificial Intelligence Conference, pp. 221-228, 1998. [6] K.A. De Jong and W.M. Spears, “Using Genetic Algorithms to Solve NP-Complete Problems,” Proceedings of the third international conference on Genetic algorithms, pp. 124-132, 1989. [7] A. Eiben and J. van der Hauw, "Solving 3-SAT with Adaptive Genetic Algorithms," Proceedings of the 4th IEEE Conference on Evolutionary Computation, pp. 81-86, 1997. [8] I.P. Gent and T. Walsh, “Towards an Understanding of Hill-climbing Procedures for SAT,” Proceedings of AAAI-93, pp.28-33, 1993. [9] I.P. Gent and T. Walsh, “Unsatisfied Variables in Local Search,” in Hybrid Problems, Hybrid Solutions (AISB-95), pp.73-85, 1995. [10] J. Gottlieb and N. Voss, "Representations, Fitness Functions and Genetic Operators for the Satisfiability Problem," Proceedings of the 5th International Comference on Parallel Problem Solving from Nature. Lecture Notes in Computer Science, vol. 1498, pp. 755-764, 1998. [11] J. Gottlieb and N. Voss, "Adaptive Fitness Functions for the Satisfiability Problem," Proceedings of the 6th International Comference on Parallel Problem Solving form Nature. Lecture Notes in Computer Science, vol. 1917, pp. 621-630, 2000. [12] J. Gottlieb, E. Marchiori and C. Rossi, "Evolutionary Algorithms for the Satisfiability Problem," Evolutionary Computation, vol. 10, no. 1, pp. 35-50, 2002. [13] J. Gu, “Efficient Local Search for Very Large-Scale Satisfiability Problems,” ACM SIGART Bulletin, vol. 3, no. 1, pp. 8-12, Jan. 1992. [14] J.K. Hao, F. Lardeux and F. Saubion, "Evolutionary Computing for the Satisfiability Problem," Applications of Evolutionary Computing, vol. 2611 of LNCS, pp. 258-267, April 2003. [15] J.K. Hao, F. Lardeux and F. Saubion, "GASAT: a genetic local search algorithm for the Satisfiability Problem," Evolutionary Computation, vol. 14, no. 2, pp 223-253, June 2006. [16] E. Marchiori and C. Rossi, "A Flipping Genetic Algorithm for Hard 3-SAT Problems," Proceedings of Genetic and Evolutionary Computation Conference, pp. 393-400, 1999. [17] B. Mazure, L. Sais and E. Gregoire, "Tabu Search for SAT," Proceedings of the 14th National Conference on Artificial Intelligence, pp. 281-285, 1997. [18] C. Rossi, E. Marchiori and J. Kok, "An Adaptive Evolutionary Algorithm for the Satisfiability Problem," Proceedings of ACM Symposium on Applied Computing, pp.463-469, 2000. [19] B. Selman, H.J. Levesque, and D. Mitchell, “A New Method for Solving Hard Satisfiability Problems,” Proceedings of the Tenth National Conference on Artificial Intelligence, pp. 440-446, 1992. [20] B. Selman and H.A. Kautz, "Domain-Independent Extensions to GSAT: Solving Large Structured Satisfiability Problems," Proceedings of the 13th International Joint Conference on Artificial Intelligence, pp. 290-295, 1993. [21] B. Selman and H. A. Kautz and B. Cohen, “Noise Strategies for Improving Local Search,” Proceedings of the twelfth national conference on Artificial intelligence, vol. 1, pp. 337-343, 1994. [22] W.M. Spears, "Simulated Annealing for Hard Satisfiability Problems," Technical report, Naval Research Laboratory, 1993. [23] L. Y. Tseng and C. Chen, “Multiple trajectory search for large scale global optimization,” Proceeding 2008 IEEE Congress on Evolutionary Computation, pp. 3052-3059, 2008.
摘要: 
本篇論文提出一種新的方法,並且以多軌跡搜索法(Multiple Trajectory Search)來解決可滿足性問題(Satisfiability Problem, SAT),可滿足性問題為計算機科學領域中著名的問題,其計算複雜度為NP-Hard,在人工智慧、機器學習、超大型積體電路設計與測試等領域有諸多應用

本研究中所使用的方法:1.將可滿足性問題的搜尋方式從Discrete Domain轉換為Real Domain。2.使用多軌跡搜索法來加強搜尋的效率,試圖突破過去演算法所遇到的搜尋瓶頸及弱點。

本篇論文使用所提出的方式及搜尋法來解Gottlieb、Marchiori與Rossi於2002年所匯整的題組,和其他演算法進行比較,在論文當中將會列出實驗的結果,我們使用的方式表現出不錯的成果。

The satisfiability problem is one of famous NP-complete problem in computer science field, with applications in artificial intelligence, machine learning and VLSI design and test。

The satisfiability problem is a problem in discrete domain. In this thesis, we proposed a method to convert this problem into real domain (continuous domain), and applied the multiple trajectory search to solve this problem.

We compared the performance of the proposed algorithm with that of other algorithms published in the literature on the benchmarks presented by Gottlieb, Marchiori and Rossi in 2002.
URI: http://hdl.handle.net/11455/19767
Appears in Collections:資訊科學與工程學系所

Show full item record
 

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.