臺灣博碩士論文加值系統

在資訊科技快速發展的今日，仍有許多複雜的組合最佳化問題(combinatorial optimization problems)無論對演算法的設計或計算機的速度都是重大的挑戰，例如：編碼問題(coding problems)、電路測試(circuit testing)、附加條件搜尋(additive search problem),資料庫的線上查詢(on-line models with equivalent queries)，與密碼系統破解(differential cryptanalysis)。而這些問題的都與演繹競局最佳化相關聯。亦即：在演繹競局最佳化問題中得到的任何結論或成果，皆可能應用到上述重要科技領域的發展，可說是現今電腦科學領域中的ㄧ門重要的課題。
一般而言，競局問題的計算複雜度相當高，通常皆為Pspace、Exptime或者是Expspace的問題，因為其計算複雜度會隨著問題大小(problem size)的增大而呈指數成長，對於較大的問題而言，幾乎是不可能在多項式時間(polynomial time)內找到確定性deterministic的最佳策略。在本研究中，我們首先針對著名的電腦科學家Knuth提出的演繹競局最佳化問題：Mastermind和AB game (在歐洲叫做 "bulls and cows")及其變化做深入的研究。其次，對於更一般化的最佳化問題，我們不但深入的分析與探討機率演算法(probabilistic algorithm)、近似演算法(approximate algorithm)及平行演算法(parallel algorithm)等技術的特性與效能，更利用這些演算法的優點與特性，提出了一系列嶄新且有系統的最佳化演算法，應用這些演算法來有效的解決更複雜的演繹競局及相關組合最佳化問題，此研究中提出的演算法有：(1)圖形分割演算法(graph-partition, GP)，(2) k分支逼近演算法(k-way-branching, KWB)，(3)應用鴿籠定理的回溯搜尋法(pigeonhole-principle-based backtracking, PPBB)，(4)菁英演化式演算法(elitism-based evolutionary algorithm, EBEA)，以及其平行分散式的演算法(5) DEBEA。
首先，我們利用競局樹(Game tree)的一些特性：例如樹的外部路徑長度(external path length)與高度(height)來具體描述整個問題的架構；除此之外，以競局圖(Game graph)來表示競局過程中的每ㄧ個狀態。圖形分割演算法(GP)就是建立在這個架構上，藉由此架構，我們發現競局圖中一些對稱(symmetric)、全等(equivalent)和遞迴(recursive)的特性，利用這些特性，不但減少了整個問題的搜尋空間，更幫助我們有效率的尋找最佳策略。也因此發展出在平均狀況(expected case)和最差狀況(the worst case)下解決這類型問題的最佳策略，我們得到了以下的最佳化結果：
(1) 2×n AB game在最差狀況下，最多必須要猜n/2+1 次。
(2) 2×n AB game在平均狀況下，當n是偶數時平均猜測次數為(4n3+21n2 -76n+72)/ 12n(n-1)次；而當n是奇數時為(4n3+21n2 -82n+105)/12n(n-1)次。
(3) 2×n Mastermind在最差情況下，最多必須要猜 n/2+2 次。
(4) 2×n Mastermind在平均狀況下，當n是偶數時需要猜(8n3+51n2-74n+48)/24n2次；當n是奇數時要猜(8n3+51n2-80n+69) / 24n2次。
其次，我們提出k分支近似演算法(KWB)，KWB已成功的應用於找尋4×10 AB game的最佳策略。此演算法可以獲得在最差狀況下的最佳策略，以及在平均情況下接近最佳(near-optimal)的策略；而且如果在執行時間和空間允許的情況下，我們可以增加參數k的值而使得所得的策略更接近最佳解。另外，我們提出了擴展鴿籠定理(extended pigeonhole principle)，並利用其發展一套電腦輔助驗證的演算法PPBB來證明在4×10 AB game在最差情況下所需猜測次數的下限(lower bound)，藉此可證明在最差狀況下，我們所獲得的策略為最佳化策略。利用這KWB與PPBB演算法，我們得到以下新的結果：
(1) 在4×6 Mastermind競局的期望情況下，當k=1時，近似演算法的結果是97.385 接近最佳解；當k=40時，結果是99.487 接近最佳解，此結果較先前所有文獻中最好的heuristic策略為佳。
(2) 在4×10 AB Game最差情況下，我們得到了最佳策略，其中至多只需要猜7次；在平均狀況下也得到了一個平均猜測次數為5.268次的策略。
(3) 為了將成果提供各界參考運用，本研究在演繹競局上所提出的最佳化演算法已在網頁上完成系統實作。網址如下：http://alg.csie.ntnu.edu.tw/deductive_game/
在此研究的最後部分，我們探討演化式演算法來處理較複雜的演繹競局及相關的組合最佳化問題；其中，我們提出了菁英演化式演算法(EBEA)，EBEA很成功的應用於一個NP-complete問題：二元決策圖(BDD)最佳化問題。我們也在叢集電腦(PC cluster)上發展了一套有效率的分散式演算法(DEBEA)，並比較與分析其平行化的效能。應用EBEA與DEBEA於BDD最佳化問題，可獲致以下新的結果：
(1)在EBEA中，我們提出了ㄧ個演化式演算法的終止機制：stable function，並推導出該機制一些很好的特性，這些特性能幫助我們選擇終止條件，而有效的減少程式的執行時間。
(2)在BDD基準測試電路LGSynth91中，EBEA能夠很有效率的將所有最佳解已知(exact-size-known)的測試電路(benchmarks)求出最佳解。
(3)藉由多處理器的合作，對LGSynth91中較大的測試電路而言，DEBEA都能有效的求得甚而超越目前文獻已知的最佳解。

With the rapid development of information technologies, many state-of-the-art combinatorial optimization problems─ such as coding, circuit testing, additive search, online models with equivalent queries and differential cryptanalysis─ are related to solutions for deductive games. In other words, any conclusion drawn from this kind of game may be applied, although probably not directly, to any of these problems as well as to any other combinatorial optimization problem.
The optimization problems mainly considered in this study are two kinds of well-known deductive games: Mastermind and AB games (or "bulls and cows"), the optimization problems of which were proposed by the renowned scientist Donald E. Knuth. To analyze and solve the games, we propose a series of novel and systematic optimization algorithms and approaches, including graph-partition (GP), pigeonhole-principle-based backtracking (PPBB), and k-way-branching (KWB) approaches. Moreover, evolutionary algorithms are investigated for solving the games with larger sizes and related hard-combinatorial problems.
The graph-partition approach, which takes advantage of properties of game trees and a graphic model for representing the game-guessing process, has been successfully applied to completely solve 2×n AB games and 2×n Mastermind games. With this novel approach, we find some symmetric, isomorphic, and recursive structures in the game-guessing process. This not only reduces the size of the search space, but also helps us to derive the optimum strategies more efficiently. By using this technique, we develop optimal strategies for the games in both the expected and the worst cases. We summarize the optimal results for the games as follows:
(1) n/2+1 guesses are necessary and sufficient for 2×n AB games in the worst case.
(2) The minimum number of guesses required for 2×n AB games in the expected case is (4n3+21n2 -76n+72)/12n(n-1) if n is even, and (4n3+21n2 -82n+105)/12n(n-1) if n is odd.
(3) n/2+2 guesses are necessary and sufficient for 2×n Mastermind games in the worst case.
(4) The minimum number of guesses required for 2×n Mastermind games in the expected case is (8n3+51n2 -74n+48)/24n2 if n is even, and (8n3+51n2 -80n+69)/24n2 if n is odd.
The k-way-branching (KWB) approach is proposed for the 4×10 AB game. By using the novel algorithm, we achieve an optimal strategy for the game in the worst case. In the expected case, a near-optimal solution is obtained. Furthermore, we can get closer to the optimal solution by increasing the value of a parameter k, depending on the execution time and space allowed. In addition, a computer-aided verification algorithm, called pigeonhole-principle-based backtracking, is used to verify the optimal strategy for the 4×10 AB game in the worst case. We obtain the following new results:
(1) For the 4×6 Mastermind game in the expected case, the results obtained by the KWB algorithm are within 97.385  of optimum if k=1, and within 99.487  of optimum if k=40, which outperforms the best results of previous heuristic strategies.
(2) For the 4×10 AB game, 7 guesses are necessary and sufficient in the worst case; 5.268 guesses are sufficient in the expected case.
Since the complexity of these games grows at an exponential rate, it is very difficult to obtain optimal strategy for them when they have higher dimensions, as well as for NP-hard problems with lager sizes. Therefore, in the last part of this research, evolutionary algorithms are investigated for these complicated problems. A new elitism-based evolutionary algorithm (EBEA) has been developed and successfully applied to the popular NP-complete problem: minimization of Binary Decision Diagrams (BDD). We also develop a distributed model of EBEA, called DEBEA, on a dedicated PC-cluster. We summarize the results as follows:
(1) EBEA provides an effective termination mechanism, called the stable function, for evolutionary algorithms. Some excellent properties are derived from the mechanism. This not only helps to efficiently choose an appropriate termination criterion for a system, but also reduces the run time for redundant generations in the evolutionary process.
(2) EBEA is able to efficiently find all the optimal variable orders for all exact-size-known benchmark circuits in the LGSynth91.
(3) DEBEA obtains the best-ever variable orders for almost all benchmark circuits in the LGSynth91 within a reasonable run time.

Contents
List of Figures
List of Tables
Chapter 1 Introduction
1.1 Deductive Games 1-1
1.1.1 The Game of Mastermind 1-1
1.1.2 The AB Game 1-2
1.1.3 Variants and Applications of Deductive Games 1-3
1.2 Properties of Deductive Games 1-4
1.2.1 Game Trees 1-4
1.2.2 Optimization Problems for Deductive Games 1-5
1.2.3 Search Space for Deductive Games 1-8
1.3 Combinatorial Optimization (CO) Problems 1-9
1.4 Categories of the Algorithms Introduced in This Study 1-10
1.5 Organization of This Dissertation 1-12
Chapter 2 Graph-Partition Approach
2.1 Graphic Model 2-1
2.1.1 Graphic Representation 2-1
2.1.2 Principles of Partition 2-3
2.1.3 Strategies for the 2×5 AB Game 2-4
2.2 Optimal Strategies for 2×n AB Games 2-7
2.2.1 Graphic Representation 2-7
2.2.2 Optimal Strategy in the Expected Case 2-8
2.2.3 Optimal Strategy in the Worst Case 2-13
2.3 Optimal Strategies for 2×n Mastermind Games 2-15
2.3.1 Graphic Representation 2-15
2.3.2 Optimal Strategy in the Expected Case 2-16
2.3.3 Optimal Strategy in the Worst Case 2-22
2.4 Recursive State Transition Diagrams (RSTD) 2-24
2.5 Conclusions of This Chapter 2-26
Chapter 3 Optimization Algorithms for the 4×10 AB Game
3.1 Analysis of the AB Game 3-1
3.2 k-Way-Branching (KWB) 3-2
3.2.1 The Algorithm 3-2
3.2.2 Experimental Results 3-4
3.3 Pigeonhole-Principle-Based Backtracking (PPBB) 3-6
3.4 Conclusions of This Chapter 3-12
Chapter 4 Evolutionary Algorithms for Hard Combinatorial
Optimization Problems
4.1 Evolutionary Algorithms (EAs) 4-2
4.2 Solving Deductive Games Using EAs 4-3
4.3 Binary Decision Diagrams (BDD) 4-5
4.3.1 BDD representation 4-5
4.3.2. Reduction Rules 4-6
4.3.3 Minimization of BDD 4-7
4.3.4 Heuristic Algorithms for BDD Minimization 4-9
4.4 Elitism-Based Evolutionary Algorithm (EBEA) 4-9
4.4.1 Representation, Initialization and Evaluation 4-11
4.4.2 Operators 4-11
4.4.3 Termination Criteria 4-13
4.5 Distributed Model of EBEA (DEBEA) 4-18
4.5.1 Migrations 4-19
4.5.2 Termination 4-21
4.6 Experimental Results 4-21
4.6.1 Performance of EBEA 4-21
4.6.2 Performance of DEBEA 4-24
4.7 Conclusions of This Chapter 4-27
Chapter 5 Summaries and Directions for Future Research
5.1 Summaries 5-1
5.2 Future Research 5-2
Bibliography
Appendix A: The Proofs of Theorems in Chapter 2
Appendix B: Publication List

[Alb02a] Alba, E. (2002). “Parallel evolutionary algorithms can achieve super-linear performance,” Information Processing Letters, 82, pp. 7-13.
[Alb02b] Alba, E. and Tomassini, M. (2002). “Parallelism and Evolutionary Algorithms,” IEEE Trans. on Evolutionary Computation, Vol. 6, No. 5, pp. 443-462.
[App77] Appel, K. and Jaken, W. (1977). “Every Planar Map is Four Colorable: Part I; Discharging,” Illinois J. Math., 21, 429-490.
[Ben99] Bento, L. Pereira, L. Rosa, A. (1999). “Mastermind by evolutionary algorithms,” in Proceedings of the International Symposium on Applied Computing, pp. 307-311.
[Ber96] Bernier, J. L. Herraiz, C. I., Merelo, J. J., Olmeda, S., and Prieto, A. (1996). “Solving Mastermind using Gas and simulated annealing: a case of dynamic constraint optimization,” in Proceedings PPSN, Parallel Problem Solving from Nature IV, in Computer Science, 1141, pp. 554-563.
[Blu03] Blum, C. and Roli, A. 2003. Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison. ACM Computing Surveys, Vol. 35, No. 3, pp. 268-308.
[Bol96a] Bolling, B. and I. Wegener. (1996). “Improving the variable ordering of OBDDs is NP-complete,” IEEE Trans. Computer., vol. 45, pp 993-1002.
[Bol96b] Bolling, B. M. Löbbing, and I. Wegener. (1996). “On the effect of local changes in the variable ordering of ordered decision diagrams,” Inform. Processing Lett., vol. 59, pp. 233-239.
[Box57] Box, G. (1957). “Evolutionary operation: A method for increasing industrial productivity,” Journal of the Royal Statistic Society, 6(2), 81-101.
[Bra84] Brayton, R. K., G. D. Hachtel, C. T. McMullen, and A. L. Sangiovanni- Vincentelli, (1984). Logic Minimization Algorithms for VLSI Synthesis. Boston: Kluwer Academic Publishers.
[Bra96] Brassard, G. and Bratley, P. (1996). Fundamentals of Algorithmics. Prentice-Hall, Inc.
[Bry86] Bryant, R. E. (1986). “Graph-based algorithms for Boolean function manipulation,” IEEE Trans. Comput., vol. 35, pp. 677-691.
[Bry92] Bryant, R. E. (1992). “Symbolic Boolean Manipulation with Ordered Binary-Decision Diagrams,” ACM, Comp. Surveys, vol. 24, 293-318.
[Che96] Chen, Zhixiang and Cunha, Carlos (1996). “Finding a hidden code by asking questions,” COCOON’96, Computing and Combinatorics, pp. 50-55.
[Cul93] Culberson J. (1993). Crossover versus mutation: fueling the debate: TGA versus GIGA. In Proceedings of the 5th International Conference on Genetic Algorithms ICGA-93, 632.
[Dav85] Davis, L. (1985). ”Applying Adaptive Algorithms To Epistatic Domains,” in Proceedings of the International Joint Conference on Artificial Intelligence, 162-164.
[Dre97] Drechsler, R. and N. Gockel. (1997). ”Minimization of BDDs by Evolutionary Algorithms,” International Workshop on Logic Synthesis (IWLS''97).
[Dre00] Drechsler, R. Drechsler, N., and Günther, W. (2000). “Fast exact minimization of BDDs,” IEEE Trans. Computer-Aided Designs, vol. 19, pp. 384-389.
[Dre01a] Drechsler, R., W. Günther, and F. Somenzi. (2001). “Using lower bounds during dynamic BDD minimization,” IEEE Trans. Computer-Aided Designs, vol. 20, pp. 51-57.
[Dre01b] Drechsler, R. and W. Günther. (2001). “History-based dynamic BDD minimization,” the VLSI journal, vol. 31, pp. 51-63.
[Esh91] Eshelman, L. J. (1991). “The CHC adaptive search algorithm: how to have safe search when engaging in nontraditional genetic recombination.” Foundations of Genetic Algorithms, FOGA-I, pp. 265-283.
[Fer99] Ferber, Jacques. (1999). Multi-Agent Systems - An Introduction to Distributed Artificial Intelligence, Addison-Wesley.
[Flo88] Flood, M. M. (1988). “Sequential search strategies with Mastermind variants ─ Part 1,” Journal of Recreational Mathematics, 20:2, pp. 105-126.
[Fog88] Fogel, D. B. (1988). “An Evolutionary Approach to the Traveling Salesman Problem.” Biological Cybernetics 60, 139—144.
[Fog90] Fogel, D. B. (1990). “A Parallel Processing Approach to a Multiple Traveling Salesman Problem Using Evolutionary Programming.” In Canter, L. (ed.) Proceedings on the Fourth Annual Parallel Processing Symposium, 318—326.
[Fog93] Fogel, D. B. (1993). “Applying Evolutionary Programming to Selected Traveling Salesman Problems.” Cybernetics and Systems 24, 27—36.
[Fri90] Friedman, S. J. and K. J. Supowit. (1990). “Finding the optimal variable ordering for binary decision diagrams,” IEEE Trans. Comput., pp. 710-713, May.
[Fuj91] Fujita, M., Y. Matsunaga, and T. Kakuda. (1991). ”On variable ordering of binary decision diagrams for the application of multi-level synthesis,” in European Conf. Design Automat., 50-54.
[Gol85] Goldberg, D.E. and Lingle, R. Jr. (1985). “Alleles, loci, and the traveling salesman problem.” In Proceedings of the 1st International Conference on Genetic Algorithms ICGA-85, pp. 154-159.
[Gun99] Günther, W. and R. Drechsler. (1999). “Minimization of Free BDDs,” Design Automation Conference, Proceedings of the ASP-DAC ''99. Asia and South Pacific vol.1, pp. 323 -326.
[Hol75] Holland, J. H. (1975). Adaptation in Natural and Artificial Systems, University of Michigan Press.
[Hun02] Hung, N. N. William, Xiaoyu Song, El Mostapha Aboulhamid, and Michael A. Driscoll. (2002). “BDD Minimization by Scatter Search,” IEEE Trans. CAD, vol. 21, No. 8, pp. 974-979.
[Irv78] Irving, R. W. (1978-79). “Towards an optimum Mastermind strategy,” Journal of Recreational Mathematics, 11:2, pp. 81-87.
[Ish91] Ishiura, N., H. Sawada, and S. Yajima. (1991). “Minimization of binary decision diagrams based on exchange of variables,” in Proc. Int. Conf. Computer-Aided Design, pp. 472-475.
[Jeo93] Jeong, S.-W., T.-S. Kim, and F. Somenzi. (1993). “An efficient method for optimal BDD ordering computation,” in Proc. Int. Conf. VLSI and CAD.
[Kab00] Kabatianski, G. and Lebedev, V. (2000). “The Mastermind game and the rigidity of the Hamming space,” in Proceedings of the International Symposium on Information Theory IEEE, pp. 375-375.
[Kal03] Tom Kalisker and Doug Camens (2003). “Solving Mastermind Using Genetic Algorithms,” GECCO 2003, LNCS 2724, pp. 1590-1591, 2003.
[Kan02] Kantard, M. (2002). Data Mining: Concepts, Models, Methods and Algorithms, Wiley-IEEE Press.
[Keb92] Kebschull, U., E. Schubert, and W. Rosenstiel. (1992). “Multilevel logic synthesis based on functional decision diagrams,” in Proc. European Design Automation Conf. pp 43-47.
[Knu76] Knuth, D. E. (1976). “The computer as Mastermind,” Journal of Recreational Mathematics, 9:1, pp. 1-6.
[Knu98] Knuth, D. E. (1998). The art of computer programming- sorting and searching, volume 3, second edition.
[Ko86] Ko, K.-I. Teng, S.-C.. (1986). “On the number of queries necessary to identify a permutation,” Journal of Algorithms, 7, pp. 449-462.
[Koy93] Koyama, K. Lai, T. W. (1993). “An optimal Mastermind strategy,” Journal of Recreational Mathematics, 25, pp. 251-256.
[Kum94] Kumar V., A. Grama, A. Gupta, and G. Karypis. (1994). Introduction to Parallel Computing: Design and Analysis of Algorithms. Redwood City, California: Benjamin/Cummings Publishing Co.
[Lin01] Lin, S. S. and C. J. Wei. (2001). “Improved Algorithm for Binary Decision Diagram Minimization Problem,” National Computer Symposium, pp. A068-A079.
[Lin04] Lin, S. S. (2004). Web site: http://csie.ntnu.edu.tw/~linss/.
[Lyn96] Lynch, N. A. (1996). Distributed algorithms, Morgan Kaufmann Publishers, Inc.
[Mer99] Merelo, J. J. Carpio, J. Castillo, P. Rivas, V. M. Romero, G. GeNeura Team. (1999). “Finding a needle in a haystack using hints and evolutionary computation: the case of Genetic Mastermind,” Genetic and Evolutionary Computation Conference late breaking papers books, pp. 184-192.
[Mic99] Michalewicz, Z., Genetic algorithms + Data structures = Evolution Programs, Springer, Berlin: Germany, 1999.
[Mit97] Mitchell, T. M. (1997). Machine Learning. McGraw-Hill.
[Mol94] Möller, D. and R. Drechsler. (1994). “Symmetry based variable ordering for ROBDD’s,” in Proc. IFIP Workshop on Logic and Architecture Synthesis, pp. 47-53.
[Neu82] Neuwirth, E. (1982) “Some strategies for Mastermind,” Zeitschrift fur Operations Research, 26, pp. 257-278.
[Oli87] Oliver, I. M., Smith, D. J., and Holland, J. R. C. (1987). “A study of permutation crossover operators on the traveling salesman problem.” In Proceedings of the 2nd International Conference on Genetic Algorithms, ICGA-87, pp. 224—230.
[Pan95] Panda, S. and F. Somenzi. (1995). “Who are the variables in your neighborhood,” in Int. Conf. Computer-Aided Design, pp. 74-77.
[Pap82] Papadimitriou, C. H. and Steiglitz, K. (1982). Combinatorial Optimization Algorithms and complexity. Dover Publications, Inc., New York.
[Pel02] Pelc, A. (2002). “Searching games with errors fifty years of coping with liars,” Theoretical Computer Science, 270, pp. 71-109.
[Roc97] Roche, J. R. (1997). “The value of adaptive questions in generalized Mastermind,” in Proceedings of the International Symposium on Information Theory IEEE, pp. 135-135.
[Rud93] Rudell, R. (1993). “Dynamic variable ordering for ordered binary decision diagrams,” Int. Conf. Computer-Aided Design, pp. 42-47.
[Rus03] Russell, S. and Norvig, P. (2003). Artificial Intelligence: A Modern Approach, Prentice-Hall.
[Sch99] Scholl, C., D. Möller, and P. Molitor. (1999). “BDD minimization Using Symmetries,” IEEE Trans. Computer-Aided Designs of Integrated Circuits and Systems, vol. 18, no 2. pp. 81-99.
[Sed88] Sedgewick, R. (1988). Algorithms, second edition, Addison-Wesley.
[Som01a] Somenzi, F. (2001). CUDD: CU Decision Diagram Package — Release 2.3.1 Technical report, Dept. of Electrical and Computer Engineering, University of Colorado, Boulder, Colorado.
[Som01b] Somenzi, F. (2001). Web site: http://vlsi.colorado.edu/~fabio.
[Thi94] Thierens, D., and Goldberg, D. E. (1994). “Elitist recombination: an integrated selection recombination GA.” In Proceedings of the 1st IEEE World Congress on Computational Intelligence, 508—512.
[Ula76] Ulam, S. M. (1976). Adventures of a Mathematician, Scribner, New York, p. 281.
[Whi89] Whitley, D., Starkweather, T., and Fuquay, D’A. (1989). “Scheduling problems and traveling salesman: the genetic edge recombination operator.” In Proceedings of the 3rd International Conference on Genetic Algorithms ICGA-89, pp. 133—140.
[Wil99] Wilkinson, B. and Allen, M. (1999). Parallel Programming: Techniques and Applications Using Networked Workstations, Prentice Hall.
[Yan00] Yang, J. M. and Kao, C. Y. (2000). “Integrating adaptive mutation and family competition into genetic algorithms as function optimizer,” Soft Computing, vol. 4, pp. 89-102.