(3.236.100.86) 您好!臺灣時間:2021/05/07 09:34
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:林祐安
研究生(外文):Yo-An Lin
論文名稱:解可滿足性問題之混合式基因演算法
論文名稱(外文):A Hybrid Genetic Algorithm for the Satisfiability Problem
指導教授:曾怜玉曾怜玉引用關係
指導教授(外文):Lin-Yu Tseng
學位類別:碩士
校院名稱:國立中興大學
系所名稱:資訊科學與工程學系所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2009
畢業學年度:97
語文別:中文
論文頁數:44
中文關鍵詞:基因演算法區域搜尋演算法基因區域搜尋演算法可滿足性問題
外文關鍵詞:genetic algorithmlocal searchgenetic local searchsatisfiability problems
相關次數:
  • 被引用被引用:1
  • 點閱點閱:125
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
可滿足性問題為計算複雜度NP是否等於P問題的核心問題,並在人工智慧、硬體設計、VLSI測試與驗證、最佳化問題等領域有諸多應用。

本研究中使用一混合式基因演算法來解可滿足性問題。針對目前為止所發展的演算法的弱點,以下列方法加以克服:1. 利用兩層式基因區域搜尋對解空間各區域做更有效率的搜尋;2. 提出新的適應度函數以加強對搜尋之引導;3. 並於區域搜尋演算法中加入重設條件,捨棄陷於區域最佳解附近的解以達到系統化的搜尋。

我們應用本論文所提出之演算法於Gottlieb、Marchiori與Rossi於2002年及Hao、Lardeux與Saubion於2006年所匯整的兩個題組中,和其他演算法進行比較,並獲得了不錯的成果。
The satisfiability problem is one of the core NP-complete problems with many applications in many fields, for example, artificial intelligence, circuits design, VLSI testing, verification, and optimization.

In this thesis, we propose a hybrid genetic algorithm to solve the satisfiability problem. Observing the weak points of some algorithms published in the literature, we developed our algorithm with following three characteristics: 1. We use a two-layer genetic algorithm to search more thoroughly the solution space; 2. We design a new fitness function to improve search; 3. We make search more effective by adding restart conditions to the local search scheme to abandon the solutions near by an already searched local optimum.

We compared the proposed algorithm with other algorithms published in the literature on the benchmarks offered by Gottlieb, Marchiori and Rossi in 2002, and Hao Lardeux and Saubion in 2006.
致謝 i
摘要 ii
Abstract iii
目錄 iv
圖表目錄 v
第一章 緒論 1
1.1 研究背景 1
1.2 問題定義 3
1.3 論文架構 4
第二章 文獻探討 5
2.1 以區域搜尋為基礎的演算法 5
2.2 以基因演算法為基礎的演算法 10
2.3 小結 14
第三章 研究方法 15
3.1 混合式基因演算法 15
3.1.1 主要架構 15
3.1.2 染色體表示法 17
3.1.3 適應度函數 17
3.1.4 終止條件 18
3.1.5 基因演算法 19
3.2 區域搜尋演算法 19
3.2.1 Minimizing breaks與輔助性之適應度函數flit 20
3.2.2 重設條件 21
3.2.3 區域搜尋演算法整體架構 23
3.3 中範圍基因區域搜尋演算法 26
3.3.1定義鄰域 26
3.3.2 中範圍基因區域搜尋演算法架構 27
第四章 研究結果與資料分析 30
4.1 實驗題組介紹 30
4.2 區域搜尋演算法 32
4.3 混合式基因搜尋演算法 33
4.4 實驗結果分析 35
第五章 結論與未來研究方向 39
參考文獻 41
[1] H.M. Adorf and M.D. Johnston, “A Discrete Stochastic Neural Network Algorithm for Constraint Satisfaction Problems,” Proceedings of the International Joint Conference on Neural Networks, vol. 3, pp. 917-924, June 1990.

[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] J. Frank, "A Study of Genetic Algorithms to Find Approximate Solution to Hard 3CNF Problems," Proceedings of Golden West International Conference on Artificial Intelligence, 1994.

[9] C. Fleurent and J. Ferland, "Object-Oriented Implementation of Heuristic Search Methods for Graph Coloring, Maximum Clique and Satisfiability," DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 26, pp. 619-652, 1996.

[10] P. Galinier and J.K. Hao, "Hybrid Evolutionary Algorithms for Graph Coloring," Journal of Combinatorial Optimization, vol. 3, no. 4, pp. 379-397, 1999.

[11] I.P. Gent and T. Walsh, “Towards an Understanding of Hill-climbing Procedures for SAT,” Proceedings of AAAI-93, pp.28-33, 1993.

[12] I.P. Gent and T. Walsh, “Unsatisfied Variables in Local Search,” in Hybrid Problems, Hybrid Solutions (AISB-95), pp.73-85, 1995.

[13] 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.

[14] 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.

[15] J. Gottlieb, E. Marchiori and C. Rossi, "Evolutionary Algorithms for the Satisfiability Problem," Evolutionary Computation, vol. 10, no. 1, pp. 35-50, 2002.

[16] J. Gu, “Efficient Local Search for Very Large-Scale Satisfiability Problems,” ACM SIGART Bulletin, vol. 3, no. 1, pp. 8-12, Jan. 1992.

[17] P. Hansen and N. Mladenovic, "An Introduction to variable neighborhood search," in Advances and Trends in Local Search Paradigms for Optimization, pp. 433-458, 1999.

[18] 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.

[19] 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.

[20] J.K. Hao, "A Clausal Genetic Representation and its Evolutionary Procedures for Satisfiability Problems," Proceedings of the International Conference on Artificial Neural Nets and Genetic Algorithms, pp. 289-292, 1995.

[21] 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.

[22] B. Mazure, L. Sais and E. Gregoire, "Tabu Search for SAT," Proceedings of the 14th National Conference on Artificial Intelligence, pp. 281-285, 1997.

[23] P. Merz and B. Freisleben, "Genetic Local Search for the TSP: New results," Proceedings of the IEEE Conference on Evolutionary Computation, IEEE World Congress on Computational Intelligence, pp.159-164, 1997.

[24] A.B. Philips, S. Minton, Johnston, P. Laired, “Solving Large-Scale Constraint Satisfaction and Scheduling Problems Using a Heuristic Repair Method,” Proceedings of AAAI-90, pp. 17-24, 1990.

[25] K. Park, "A Comparative Study of Genetic Search," Proceedings of the 6th International Conference on Genetic Algorithms, pp. 512-519, 1995.

[26] 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.

[27] 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.

[28] 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.

[29]  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.

[30] D. McAllester, B. Selman and H. Kautz, "Evidence for Invariants in Local Search," Proceedings of the National Conference on Artificial Intelligence, pp.321-326, 1997.

[31] W.M. Spears, "Simulated Annealing for Hard Satisfiability Problems," Technical report, Naval Research Laboratory, 1993.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊
 
系統版面圖檔 系統版面圖檔