臺灣博碩士論文加值系統

「分群優化問題」是實務應用及作業研究中時常見到的 NP-hard 問題。本研究以「將一堆物件分群」的角度來建構數學模式並開發蟻拓求解法。本研究詳細探討各式物件分群優化問題，並依有無物件屬性、有無物件間互斥限制、群與物件間限制、群的物件數或屬性容量上限、及群數固定與否、…等做詳細的分析及進行分類，並提出一個三段式的物件分群優化問題分類命名法則，方便日後援引。據此，本研究主要在開發蟻拓尋優（Ant Colony Optimization）技術為基的物件分群優化演算法。開發方法係以物件導向技術建模並萃取設計樣型（design pattern），以確保此啟發式演算法能應用於各式物件分群優化問題。
在系統實作上，本研究延伸「台大蟻拓優化軟體礎架（National Taiwan University Ant Colony Optimization Framework, NTUACOF）」，開發蟻拓物件分群優化演算的核心軟體類別，名為「蟻拓物件分群優化礎架（Ant Colony Optimization Object Grouping Framework, ACOOGF）」。此外，本研究並利用 ACOOGF 實作節點著色問題、節點數平衡的著色問題、裝箱問題、入學考試排程問題前期分群處理的求解系統，以驗證整個 NTUACOF 的求解能力及擴充性。經四個應用系統的實作結果顯示 ACOOGF 確實可有效提供使用者繼承此礎架內的類別並自行開發以 ACO 演算法為求解核心的物件分群優化問題求解系統。

Object grouping optimization problems, known as NP-hard problems, are frequently encountered in operation research areas and industrial fields. Traditionally, these problems are modeled as set partitioning problems. In this thesis, viewpoint of group allocation for a set of objects is adopted to construct mathematical models and to classify these problems. In this thesis, a three-segment naming mechanism for grouping optimization problems is proposed. This thesis then focuses on developing an object grouping technique based ACO (Ant Colony Optimization) method to solve this kind of problems. Design patterns of using ACO approaches to solve object grouping optimization problems are discussed. General procedures are postulated for further applications of solving object grouping optimization problems.
To implement the proposed method, this thesis extends and expands NTUACOF (National Taiwan University Ant Colony Optimization Framework) to solve object grouping optimization problems by developing core software classes. These classes are dedicated to using ACO techniques to solve object grouping problems and are named as Ant Colony Optimization Object Grouping Framework (ACOOGF). Based on this framework, applications of solving graph coloring problems, node number balanced graph coloring problems, bin packing problems, and exam timetabling problems are also implemented to verify the functionalities and expandability of ACOOGF. Augmented by ACOOGF, NTUACOF is a complete decision making tool for discrete optimization problems.

目 錄........................................................i
圖目錄........................................................v
表目錄.....................................................viii
名詞彙編.....................................................ix
符號列表....................................................xii
第一章 緒論..................................................1
1.1 研究背景..................................................1
1.2 問題描述與研究動機........................................3
1.3 研究目的及內容............................................5
1.4 研究範疇與架構............................................6
1.5 章節概要..................................................8
第二章 文獻探討..............................................9
2.1 求解優化問題的選優機制及啟發式演算法......................9
2.2 旅行推銷員問題（Traveling Salesman Problems）............12
2.2.1 旅行推銷員問題之定義.................................12
2.2.2 旅行推銷員問題之數學規劃模式.........................13
2.3 一般化的指派問題（Generalized Assignment Problem）.......15
2.4 集合分割問題（Set Partitioning Problems）................16
2.5 節點著色問題（Graph Coloring Problems）..................18
2.5.1 循序式著色法則（Sequential Coloring Algorithm）......20
2.5.2 配對著色簡化法則.....................................22
2.5.3 分群著色法則（Partitioning Coloring Algorithm）......23
2.5.4 節點著色問題的啟發式解法.............................24
2.6 裝箱問題（Bin Packing Problem）..........................24
2.6.1 裝箱問題與維度.......................................26
2.6.2 線上（On-Line）與離線（Off-Line）之裝箱問題..........27
2.6.3 求解離線裝箱問題前的預先編排處理.....................28
2.6.4 裝箱問題的啟發式求解法...............................28
2.7 蟻拓尋優法介紹...........................................30
2.7.1 真實螞蟻覓食行為的探討...............................30
2.7.2 蟻拓尋優法的各種求解技術及演進過程...................35
2.7.3 螞蟻系統（Ant System）...............................36
2.7.3.1 螞蟻系統介紹.....................................36
2.7.3.2 螞蟻系統基本架構.................................37
2.7.3.3 螞蟻系統演算法...................................40
2.7.4 Ant-Q................................................42
2.7.5 AS-elite 及 AS-rank..................................45
2.7.6 螞蟻屯拓系統（Ant Colony System）....................47
2.7.6.1 ACS 轉移規則.....................................48
2.7.6.2 ACS 全域性費洛蒙強度更新規則.....................49
2.7.6.3 ACS 區域性費洛蒙強度更新規則.....................50
2.7.7 MMAS（MAX-MIN Ant System）...........................51
2.7.8 平行運算的螞蟻系統...................................52
2.7.9 蟻拓尋優巨集啟發式方法（ACO Meta-Heuristic）.........53
2.7.10 蟻拓尋優法的應用....................................55
2.8 文獻探討結語.............................................57
第三章 物件分群問題與蟻拓物件分群優化法.....................59
3.1 物件分群問題.............................................59
3.2 物件分群優化問題之數學模式...............................63
3.2.1 物件（objects）......................................63
3.2.2 物件間互斥限制（mutual exclusive constraints）.......64
3.2.3 物件屬性（attributes of object）.....................66
3.2.4 群（groups）.........................................67
3.2.5 群數（number of groups）.............................68
3.2.6 物件群落限制（object-group allocation constraints）..69
3.2.7 群容量上限（grouping capacity）......................71
3.2.8 目標函數（objective funcitons）......................75
3.2.9 物件分群優化問題的分類及一個三段式命名法.............75
3.3 蟻拓物件排序演算法及蟻拓物件分群演算法...................83
3.3.1 蟻拓物件排序優化演算法...............................84
3.3.2 蟻拓物件分群優化演算法...............................94
3.3.2.1 將限制條件隱含於初始費洛蒙資料中.................95
3.3.2.2 螞蟻的工作：選取欲分群的目標物件.................99
3.3.2.3 螞蟻的工作：將目標物件分入群中...................99
3.3.2.4 另闢新群的機制..................................100
3.3.2.5 費洛蒙的更新....................................102
3.3.2.6 螞蟻的物件分群作業演算流程......................103
3.4 物件分群優化問題之蟻拓求解模式..........................113
3.4.1 節點著色問題的蟻拓物件分群求解模式..................115
3.4.2 GCP 延伸：節點數平衡的著色問題的蟻拓物件分群求解模式119
3.4.3 裝箱問題的蟻拓物件分群求解模式......................122
3.4.4 入學考試排程問題的蟻拓物件分群求解模式..............125
3.5 小結....................................................126
第四章 蟻拓物件分群優化礎架.................................127
4.1 蟻拓物件分群優化礎架之系統開發動機......................127
4.2 NTUACOF 及 ACOOGF 系統模型、分析、及設計...............128
4.2.1 操用境況模型（Use Case Model）......................129
4.2.2 類別模型（Class Model）.............................135
4.2.3 物件行為模型（Object Behavior Model）...............149
4.3 NTUACOF 及 ACOOGF 系統實作..............................156
4.3.1 NTUACOF 系統人機界面主視窗..........................156
4.3.2 問題模式選擇視窗....................................161
4.3.3 演算策略、演算參數，執行參數設定及修改視窗..........162
4.3.4 數字依序排序優化問題求解時的相關設定................171
4.3.5 旅行推銷員問題客製化視窗及相關設定..................173
4.3.6 JSP 客製化視窗及相關設定............................177
4.3.7 物件分群優化問題客製化視窗及相關設定................182
4.3.8 有物件屬性的物件分群優化問題客製化視窗及相關設定....185
第五章 實務問題求解及結果分析...............................191
5.1 節點著色問題範例演練及討論..............................191
5.2 節點數平衡的著色問題....................................197
5.3 裝箱問題................................................201
5.4 入學考試排程問題前期分群處理............................205
第六章 結論與未來研究方向...................................211
6.1 結論與建議..............................................211
6.2 未來研究建議............................................212
參考文獻....................................................213
附件一 螞蟻系統演算法 (AS)..................................217
附件二 螞蟻族群系統演算法 (ACS).............................219

1. Bodin, L., Golden, B.L., Assad, A., and Ball, M., 1983, “Routing and Scheduling of Vehicle and Crew: The State of Art,” Special Issue of Computers and Operations Research 10(2), pp. 63-211.
2. Booch, G., Rumbaugh, J., and Jacobson, I., 1999, The Unified Modeling Language User Guide, Addison Wesley.
3. Brelaz, D., 1979, “New Methods to Color thef Vertices of a Graph,” Communications of the ACM, 22, 4, pp.251-256.
4. Bullnheimer, B., Hartl, R.F., and Strauss, C., 1997, “A new rank based version of the ant system: A computational study,” Working paper, University of Vienna, Austria.
5. Detrain, C., Deneubourg, L., and Pasteels, M., 1999, Information Processing in Social Insects, Birkhäuser.
6. Dorigo, M., Caro, G., and Sampels, M. (eds.), 2002, Ant algorithms : third international workshop, ANTS 2002, Brussels, Belgium, September 12-14, proceedings.
7. Dorigo, M. and Caro, G.., 1999, “The Ant Colony Optimization Meta-Heuristic,” New Ideas in Optimization, McGraw-Hill, pp. 11-32.
8. Dorigo, M. and Caro, G.., 1999, “Ant Colony Optimization: A New Meta-Heuristic,” Proceedings of the 1999 Congress on Evolutionary Computation, Vol. 2, pp. 1470-1477.
9. Dorigo, M. and Gambardella, L. M., 1997, “Ant Colony System: A cooperative Learning Approach to the Traveling Salesman Problem,” IEEE Transactions on Evolutionary Computation, vol.1, no.1, pp. 53-66.
10. Dorigo, M., Maniezzo, V., and Colorni, A., 1996, “Ant System: Optimization by a Colony of Cooperating Agents,” IEEE Transactions on System, Man, and Cybernetics - Part B: Cybernetic, vol.26, no.1, pp. 29-41.
11. Dorigo, M., Colorni, A., and Maniezzo, V., 1991, “Distributed Optimization by Ant Colonies,” Proceedings of ECAL-91 European Conference on Artificial Life, Paris, France.
12. Dorigo, M., Maniezzo, V., and Colorni, A., 1991, “Positive Feedback as a Search Strategy,” Technical Report 91-016, Dip. Elettronica, Politecnico di Milano.
13. Dutton, R. D. and Brigham, R. C., 1981, “A New Graph Colouring Algorithm,” The Computer Journal, 24, 1, pp.85-86.
14. Gambardella, L. M. and Dorigo, M., 1995, “Ant-Q: A Reinforcement Learning Approach to the Traveling Salesman Problem,” Proceedings of ML-95, Twelfth International Conference on Machine Learning, A. Prieditis and S. Russell (Eds.), Morgan Kaufmann, pp.252—260.
15. Garey, MR., and Johnson, DS., 1979, “Computers and Intractability: A Guide to the Theory of NP-Completeness,” W.H. Freeman and Company: New York.
16. Glover, F., 1989, Tabu Search─Part I, ORSA Journal on Computing, 1 (3), pp. 190—206.
17. Goss, S., Beckers, R., Deneubourg, J.L., Aron, S., and Pasteels, J.M., 1990, “How Trail Laying and Trail Following Can Solve Foraging Problems for Ant Colonies,” in Behavioural Mechanisms of Food Selection, R.N.Hughes ed., NATO-ASI Series, Vol. G 20, Berlin:Springer-Verlag.
18. How-Ming Shieh, and Ming-Der May, 2001, “Solving The Capacitated Clustering Problem With Genetic Algorithms,” Journal of the Chinese Institute of Industrial Engineers, Vol. 18, No. 3, pp. 1-12.
19. Holldobler, B. and Wilson, E.O., 1995, Journey to the Ants: A Story of Scientific Exploration, Belknap printing, reprint edition.
20. James, K. and Jiefeng Xu, 1998, “A Set-Partitioning-Based Heuristic for the Vehicle Routing Problem”.
21. Johri, A. and Matula, W., “Probabilistic Bounds and Heuristic Algorithms for Coloring Large Random Graphs,” Technical Report, Southern Methodist University, Dallas Texas.
22. Junger, M., Reinelt, G., and Rinaldi, G., 1995, The Traveling Salesman Problem, Chapter 4 in Ball M., Magmanti T., Monma C. and Nemhanser G. eds., Network Models, Handbooks in Operations Research and Management Science 7, pp. 225-323.
23. Maniezzo, V., Colorni, A., and Dorigo, M., 1994, “The Ant System Applied to the Quadratic Assignment Problem,” Technical Report IRIDIA/94-28, Université Libre de Bruxelles, Belgium.
24. Matula, D. W., et al., “Graph Coloring Algorithms,” Graph Theory and Computing, R. C. Read (ed.). Academic Press, New York.
25. Pearl, J., 1984, Heuristics: Intelligent Search Strategies for Computer Problem Solving, Addison Wesley.
26. Peck, J. E. L. and Williams, M. R., 1966, “Algorithm 286 Examination Scheduling,” Communications of the ACM, 9, 6, pp. 433-434.
27. Stuart, J. R. and Peter N., 1994, Artificial Intelligence: A Modern Approach, Prentice Hall, 1st edition.
28. Stutzle, T. and Hoos, H., 1997, “The MAX-MIN Ant System and Local Search for the Traveling Salesman Problem,” In Proceedings of the Fourth International Conference on Evolutionary Computation. (ICEC''97), IEEE Press, pp.308-313.
29. Welsh, D. J. A. and Powell, M. B., 1967, “An Upperbound for the Chromatic Number of a Graph and Its Application to Timetabling Problems,” Comput. J., 10, pp. 85-86.
30. West, D., 1996, Introduction to Graph Theory, Prentice Hall, 2nd edition.
31. 吳森原譯著，1988，圖形論及其應用，曉園出版社，第八、九章，pp. 156-224。
32. 韓復華，卓裕仁，2001，「網路節點服務問題 TSP 與 VRP 問題回顧」，運輸網路分析，五南圖書出版公司，林正章(編輯)，第八章，pp. 201-224。
33. OR LIBRARY 標竿問題範例參考網址 http://mscmga.ms.ic.ac.uk/info.html