臺灣博碩士論文加值系統

二次分配問題是一個NP-hard的問題，它屬於組合最佳化的問題。現實生活中有很多問題可以化成二次分配問題。例如：打字機鍵盤設計問題、學校及醫院配線設計問題及排班問題等。

　　本研究中提出一新的架構並結合基因演算法及區域搜尋演算法來解二次分配問題。針對目前為止所發展的演算法的弱點，我們提出下列方法加以克服：1. 利用新的架構對解空間做更廣泛且有效率的搜尋；2. 提出解空間縮放機制加強對搜尋之引導；3. 搭配多種區域搜尋演算法以達到更細部的搜尋。

　　我們應用本論文所提出之演算法和Tseng與Liang在2006年及James、Rego與Glover在2009年所匯整的四個題組中，和其他演算法進行比較，並獲得了不錯的成果。

The quadratic assignment problem (QAP) is one of the NP-hard problems. It is a well-known combinatorial optimization problem. There are many practical problems that can be formulated as the QAP, for example, problems dealing with typewriter keyboard design, school and hospital layout design and scheduling.

In this thesis, we propose a new method called the multiple trajectory search(MTS) algorithm to solve the quadratic assignment problem. Observing the weak points of some algorithms published in the literature, we developed our algorithm with following three characteristics: 1.We used a new architecture to search more thoroughly and efficiently the solution space; 2.We proposed medium-scale region search to improve the search; 3.We used a variety of local search methods to achieve a more detailed search.

We compared the proposed algorithm with other algorithms published in the literature on the benchmarks offered by Tseng and Liang in 2006, and James, Rego and Glover in 2009.

摘要 i
Abstract ii
目錄 iii
圖表目錄 iv
表格目錄 v
第一章 緒論 1
1.1 研究背景 1
1.2 問題定義 2
1.3 解的表示法 2
1.4 論文架構 3
第二章 文獻探討 4
2.1 超探索式演算法 4
2.2 多重超探索式演算法 7
2.3 小結 9
第三章 研究方法 10
3.1 多重軌跡搜尋演算法 10
3.1.1 MTS主要架構 10
3.1.2 MTS之概念、特性 12
3.2 中範圍區域搜尋演算法 13
3.2.1 中範圍區域搜尋主要架構 13
3.2.2 灑點 16
3.2.3 基因演算法(Genetic algorithm) 16
3.2.4 區域搜尋演算法(Local Search) 17
第四章 研究結果與資料分析 22
4.1 實驗題組介紹 22
4.2 MTS實驗結果 23
4.3 實驗結果分析 36
第五章 結論與未來研究方向 37
參考文獻 38

1.Angel, E. and V. Zissimopoulos, On the landscape ruggedness of the quadratic assignment problem. Theoretical Computer Science, 2001. 263(1-2): p. 159-172.
2.Bousonocalzon, C. and M.R.W. Manning, The Hopfield Neural-Network Applied to the Quadratic Assignment Problem. Neural Computing & Applications, 1995. 3(2): p. 64-72.
3.Connolly, D.T., An Improved Annealing Scheme for the Qap. European Journal of Operational Research, 1990. 46(1): p. 93-100.
4.Wilhelm, M.R. and T.L. Ward, Solving Quadratic Assignment Problems by Simulated Annealing. Iie Transactions, 1987. 19(1): p. 107-119.
5.Tate, D.M. and A.E. Smith, A Genetic Approach to the Quadratic Assignment Problem. Computers & Operations Research, 1995. 22(1): p. 73-83.
6.Misevicius, A., Genetic algorithm hybridized with ruin and recreate procedure: application to the quadratic assignment problem. Knowledge-Based Systems, 2003. 16(5-6): p. 261-268.
7.Taillard, E., Robust Taboo Search for the Quadratic Assignment Problem. Parallel Computing, 1991. 17(4-5): p. 443-455.
8.Misevicius, A., A tabu search algorithm for the quadratic assignment problem. Computational Optimization and Applications, 2005. 30(1): p. 95-111.
9.James, T., C. Rego, and F. Glover, A cooperative parallel tabu search algorithm for the quadratic assignment problem. European Journal of Operational Research, 2009. 195(3): p. 810-826.
10.Nissen, V. and H. Paul, A Modification of Threshold Accepting and Its Application to the Quadratic Assignment Problem. Or Spektrum, 1995. 17(2-3): p. 205-210.
11.Gambardella, L.M., E.D. Taillard, and M. Dorigo, Ant colonies for the quadratic assignment problem. Journal of the Operational Research Society, 1999. 50(2): p. 167-176.
12.Maniezzo, V. and A. Colorni, The ant system applied to the quadratic assignment problem. Ieee Transactions on Knowledge and Data Engineering, 1999. 11(5): p. 769-778.
13.Tseng, L.Y. and S.C. Liang, A hybrid metaheuristic for the quadratic assignment problem. Computational Optimization and Applications, 2006. 34(1): p. 85-113.
14.Demirel, N.C. and M.D. Toksari, Optimization of the quadratic assignment problem using an ant colony algorithm. Applied Mathematics and Computation, 2006. 183(1): p. 427-435.
15.Drezner, Z., Compounded genetic algorithms for the quadratic assignment problem. Operations Research Letters, 2004. 33(5): p. 475-480.
16.Drezner, Z., Extensive experiments with hybrid genetic algorithms for the solution of the quadratic assignment problem. Computers & Operations Research, 2008. 35(3): p. 717-736.
17.Drezner, Z., A new genetic algorithm for the quadratic assignment problem. Informs Journal on Computing, 2003. 15(3): p. 320-330.
18.Sahni, S. and T. Gonzalez, P-Complete Approximation Problems. Journal of the Acm, 1976. 23(3): p. 555-565.
19.Fleurent, C. and F. Glover, Improved constructive multistart strategies for the quadratic assignment problem using adaptive memory. Informs Journal on Computing, 1999. 11(2): p. 198-204.
20.Stutzle, T., Iterated local search for the quadratic assignment problem. European Journal of Operational Research, 2006. 174(3): p. 1519-1539.
21.James, T., C. Rego, and F. Glover, Multistart Tabu Search and Diversification Strategies for the Quadratic Assignment Problem. Ieee Transactions on Systems Man and Cybernetics Part a-Systems and Humans, 2009. 39(3): p. 579-596.
22.Burkard, R.E., S.E. Karisch, and F. Rendl, QAPLIB - A quadratic assignment problem library. Journal of Global Optimization, 1997. 10(4): p. 391-403.