臺灣博碩士論文加值系統

次經驗演算法為解決最佳化問題的重要方法之一，且已有許多相關的研究，而其中的混合式演算法結合多個單一演算法的特性與優點，對於複雜問題的求解效果更是顯著。外掛群體智慧演算法即是一種有效的混合式演算法，且已被證實為有效的連續型最佳化演算法，效能優於數個目前最具代表性的最佳化演算法，例如PSO、SS、GRASP等。本研究提出一個離散型的外掛群體智慧演算法(簡稱DCSA)，並考慮其距離定義、多重啟始、鑽勘性與多樣性等策略。實驗結果顯示本研究提出的DCSA對於著名的二次指派問題有不錯的求解效果，且結果也顯示DCSA也比近年來數個最好的單列設備布局演算法，有更佳的求解效能。

Metaheuristic technique is one of the important methods for solving optimization problems. Many related researches were proposed. Among them, hybrid algorithms combining advantageous features of multiple algorithms appear to be more significant for solving complex problems. Cyber Swarm Algorithm (CSA) is a hybrid algorithm and has been shown to be more effective than several state-of-the-art algorithms for the continuous optimization problem, such as PSO, SS, and GRASP. This paper proposes a discrete version of CSA (to be referred to as DCSA) by considering the distance definition, multistart, intensification and diversity strategies. The experimental results show that DCSA has good performance in solving the well-known quadratic assignment problem. The experimental results also showed that DCSA outperforms several existing methods for important benchmark single row facility layout problem instances.

目錄
致謝 I
摘要 II
Abstract III
圖目錄 VI
表目錄 VIII
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 論文架構 2
第二章 文獻探討 3
2.1 粒子群優化 3
2.1.1 原始版本(Kennedy & Eberhart 1995) 3
2.1.2 慣性權重版本(Shi & Eberhart 1998) 4
2.1.3 壓縮因子版本(Clerc 1999) 4
2.1.4 多點引導版本(Mendes et al. 2004) 5
2.2 探索式搜尋法 5
2.3 路徑重劃 6
2.4 外掛群體智慧演算法 8
第三章 研究方法 10
3.1 問題編碼 10
3.2 離散型外掛群體智慧演算法 11
3.2.1 動態社交網路 11
3.2.2 差異性控制 14
3.2.3 區域搜尋 15
3.2.4 多重啟始策略 15
3.2.5 演算法流程 16
第四章 實驗結果 18
4.1 二次指派問題 20
4.1.1 問題定義 21
4.1.2 資料集 21
4.1.3 效能分析 22
4.1.4 最差例分析 26
4.1.5 收斂分析 31
4.2 單列設備布局問題 33
4.2.1 問題定義 34
4.2.2 資料集 35
4.2.3 效能分析 35
4.2.4 最差例分析 39
4.2.5 收斂分析 42
第五章 結論與未來展望 44
參考文獻 45

圖目錄
圖1 常見的路徑重劃方式(單點引導)：(a)前向式PR、(b)反向式PR與(c)雙向式PR 7
圖2 連續型CSA虛擬碼 9
圖3 排列編碼 10
圖4 截短式PR示意圖 13
圖5 多樣性程序虛擬碼 16
圖6 DCSA虛擬碼 17
圖7 類型一實體lipa90b：(a)直方圖與(b)點線圖 27
圖8 類型二實體tho150：(a)直方圖與(b)點線圖 27
圖9 類型三實體chr15c：(a)直方圖與(b)點線圖 28
圖10 類型四實體tai80b：(a)直方圖與(b)點線圖 28
圖11 類型一實體tai40a：(a)直方圖與(b)點線圖 29
圖12 類型二實體sko42：(a)直方圖與(b)點線圖 30
圖13 類型三實體esc32d：(a)直方圖與(b)點線圖 30
圖14 類型四實體tai40b：(a)直方圖與(b)點線圖 31
圖15 類型一實體tai40a與lipa90b之收斂分析 32
圖16 類型二實體sko42與tho150之收斂分析 32
圖17 類型三實體chr15c與esc32d之收斂分析 33
圖18 類型四實體tai40b與tai80b之收斂分析 33
圖19 AKV2005實體akv60e：(a)直方圖與(b)點線圖 39
圖20 AY2009實體ste36a：(a)直方圖與(b)點線圖 40
圖21 HA2012實體yusa30：(a)直方圖與(b)點線圖 40
圖22 AKV2005實體akv70c：(a)直方圖與(b)點線圖 41
圖23 AY2009實體sko64b：(a)直方圖與(b)點線圖 41
圖24 HA2012實體nug24：(a)直方圖與(b)點線圖 42
圖25 DCSA與S&E TS 2010的收斂分析 43

表目錄
表1 不同距離參數的比較 18
表2 DCSA參數設定 20
表3 DCSA與DivTS在類型一實體的比較 23
表4 DCSA與DivTS在類型二實體的比較 24
表5 DCSA與DivTS在類型三實體的比較 25
表6 DCSA與DivTS在類型四實體的比較 26
表7 DCSA與其它演算法在AKV2005的比較 36
表8 DCSA與其它演算法在AY2009的比較 37
表9 DCSA與其它演算法在HA2012的比較 38

1.Clerc, M., "The Swarm and the Queen: Towards a Deterministic and Adaptive Particle Swarm Optimization," Proceedings of the 1999 Congress on Evolutionary Computation, 1999, Vol. 3, 1951-1957.
2.Cohoon, J. P. and Paris, W. D., "Genetic Placement," IEEE Transactions on Computer-Aided Design, 1987, Vol. CAD-6, No. 6.
3.Connolly, D. T., "An improved annealing scheme for the QAP," European Journal of Operational Research, 1990, Vol. 46, No. 1, 93-100.
4.Datta, D., Amaral, A. R.S., Figueira, J. R., "Single row facility layout problem using a permutation-based genetic algorithm," European Journal of Operational Research, 2011, Vol. 213, 388-394.
5.Gamboa, D., Rego, C., and Glover, F., "Implementation analysis of efficient heuristic algorithms for the traveling salesman problem," Computers & Operations Research, 2006, Vol. 33, 1154-1172.
6.Glover, F. and Laguna, M., "Tabu Search" Kluwer Academic Publishers, 1997.
7.Glover, F., "A Template For Scatter Search And Path Relinking," Lecture Notes on Computer Science, 1998, Vol. 1363, 3-54.
8.Glover, F., "Tabu Search and adaptive memory programming - advances, applications and challenges" Interfaces in Computer Science and Operations Research, Kluwer Academic Publishers, 1996.
9.Hungerländer, P. and Rendl, F., "A computational study and survey of methods for the single-row facility layout problem," Computational Optimization and Applications, September 2012.
10.James, T., Rego, C., and Glover, F., "Multistart Tabu Search and Diversification Strategies for the Quadratic Assignment Problem," IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans, 2009, Vol. 39, No. 3, 579-596.
11.Kennedy, J. and Eberhart, R., "Particle Swarm Optimization," IEEE International Conference on Neural Networks, 1995, Vol. 4, 1942-1948.
12.Koopmans, T. C. and Beckmann, M., "Assignment Problems and the Location of Economic Activities," Econometrica, 1957, Vol. 25, No. 1, 53-76.
13.Kothari, R. and Ghosh, D., "Insertion based Lin–Kernighan heuristic for single row facility layout," Computers & Operations Research, 2013, Vol. 40, 129-136.
14.Kothari, R. and Ghosh, D., "Scatter search algorithms for the single row facility layout problem," Indian Institute of Management Ahmedabad, 2012, W.P. No. 2012-04-01.
15.Kothari, R. and Ghosh, D., "Tabu search for the single row facility layout problem using exhaustive 2-opt and insertion neighborhoods," European Journal of Operational Research, 2013, Vol. 224, 93-100.
16.Kothari, R. and Ghosh, D., "The Single Row Facility Layout Problem: State of the Art," Indian Institute of Management Ahmedabad, 2011, W.P. No. 2011-12-02.
17.Laguna, M. and Marti, R., "Scatter Search: Methodology and Implementation in C," Kluwer Academic Publishers, 2003.
18.Maniezzo, V. and Colorni, A., "The Ant System Applied to the Quadratic Assignment Problem," IEEE Transactions on Knowledge and Data Engineering, 1999, Vol. 11, No. 5, 769-778.
19.Mendes, R., Kennedy, J., and Neves, J., "The Fully Informed Particle Swarm: Simpler, Maybe Better," IEEE Transaction on Evolutionary Computation, 2004, Vol. 8, No. 3, 204-210.
20.Misevicius, A., "A Tabu Search Algorithm for the Quadratic Assignment Problem," Computational Optimization and Applications, 2005, Vol. 30, No. 1, 95-111.
21.Rego, C., "Relaxed tours and path ejections for the traveling salesman problem," European Journal of Operational Research, 1998, Vol. 106, 522-538.
22.Samarghandi, H. and Eshghi, K., "An efficient tabu algorithm for the single row facility layout problem," European Journal of Operational Research, 2010, Vol. 205, 98-105.
23.Samarghandi, H., Taabayan, P., Jahantigh, F. F., "A particle swarm optimization for the single row facility layout problem," Computers & Industrial Engineering, 2010, Vol. 58, 529-534.
24.Sarker, B. R., Wilhelm, W. E., and Hogg, G. L., "Locating sets of identical machines in a linear layout," Annals of Operations Research, 1998, Vol. 77, No. 0, 183-207.
25.Satheesh Kumar R.M., Asokan P., Kumanan S., Varma B., "Scatter search algorithm for single row layout problem in FMS," Advances in Production Engineering & Management, 2008, Vol. 3, 4, 193-204.
26.Sevaux, M. and Sörensen, K., "Permutation distance measures for memetic algorithms with population management," Proceedings of 6th Metaheuristics International Conference, 2005.
27.Shi, Y. and Eberhart, R. C., "Parameter Selection in Particle Swarm Optimization," Lecture Notes in Computer Science, 1998, Vol. 1447, 591-600.
28.Skorin-Kapov, J., "Tabu Search Applied to the Quadratic Assignment Problem," ORSA Journal on Computing, 1990, Vol. 2, No. 1, 33-45.
29.Solimanpur, M., Vrat, P., Shankar, R., "An ant algorithm for the single row layout problem in flexible manufacturing systems," Computers & Operations Research, 2005, Vol. 32, 583-598.
30.Stützle, T. and Dorigo, M., "ACO algorithms for the quadratic assignment problem," New Ideas for Optimization, 1999, 33-50.
31.Taillard, E., "Robust taboo search for the quadratic assignment problem," Parallel Computing, 1991, Vol. 17, 443-455.
32.Tate, D. M. and Smith, A. E., "A Genetic Approach to the Quadratic Assignment Problem," Computers & Operations Research, 1995, Vol. 22, No. 1, 73-83.
33.Teo, Y.T. and Ponnambalam, S.G., "A Hybrid ACO/PSO Heuristic to solve Single Row Layout Problem," 4th IEEE Conference on Automation Science and Engineering, August 23-26, 2008.
34.Wilhelm, M. R. and Ward, T. L., "Solving Quadratic Assignment Problems by 'Simulated Annealing'," IIE Transactions, 1987, Vol. 19, No. 1, 107-119.
35.Yin, P., Glover, F., Laguna, M., and Zhu, J., "Cyber Swarm Algorithms － Improving particle swarm optimization using adaptive memory strategies," European Journal of Operational Research, 2010, Vol. 201, No. 2, 377-389.