臺灣博碩士論文加值系統

螞蟻族群最佳化（Ant Colony Optimization）為一嶄新的近似求解演算法，由Dorigo、Maniezzo等學者於九０年代初期所提出，對於解決一些困難的組合問題(combinatorial optimization problems)，已被證明有相當好的成效。螞蟻族群演算法的設計構想源自於螞蟻覓食的合作行為，與諸多師法自然界現象的演算法如：模擬退火、基因演算法、禁忌搜尋法、等等一般，己成為一成功的自然演算法，吸引了相當多學者的注意與關切。自1991年Dorigo等學者，發表以螞蟻系統成功解決旅行銷售員問題後，許多學者也紛紛投入相關之研究，並將螞蟻族群最佳化的精神，應用於其他組合問題上。然而我們相信此一優秀的解題策略之適用範圍絕不僅止於此，應該還有許多類型的問題，能夠套用螞蟻族群最佳化的精神而獲得解決的。
本研究主要之目的在於：對螞蟻族群最佳化進行深入之研究。除了詳實探討螞蟻族群演算法的特性外，也針對新的組合問題提出了螞蟻族群演算法，以擴大螞蟻族群最佳化的應用範圍；這包括了：最小節點覆蓋問題、基地台分配問題、遠端擴張樹問題與演化樹建構問題。在最小節點覆蓋問題中，我們以子集合模式，取代既有的路徑或樹狀模式尋求解答；在基地台分配問題中則引用雙向連接圖形，及不同族群間的分工與合作來解題；在遠端擴張樹問題中，則結合了子集合與樹狀模式，完成解答之搜尋；而在演化樹建構問題中，本研究提出了一圖形表示方法，以解決該問題動態解答空間之特性。此外本研究並針對一些以螞蟻族群演算法成功解題的問題，進行初步分析與歸類，試圖提供往後學習者一解題設計的分類指引。

The Ant Colony Optimization (ACO), proposed by Dorigo et al. in the early ‘90s, is a new meta-heuristic approach to solve hard combinatorial optimization problems. Just like simulated annealing, genetic algorithms, tabu search, … , etc., Ant Colony Optimization has become a very successful natural meta-heuristic and has attracted many researchers’ attention. Since the TSP was solved by Dorigo et al. 1991, many refined models have been proposed to solve hard combinatorial optimization problems. However, we believe that the ACO approaches can be further generalized and apply to more combinatorial problems.
This research shall take a thorough study on ACO. We survey the characteristics of the ACO algorithms and propose our design of ACO algorithms for four combinatorial optimization problems in this paper, including minimum weighted vertex cover problem (MWVC), cell assignment problem (CA), remote spanning tree problem (RMST) and evolutionary tree construction problem (ETCP). In MWVC, we found a subset instead of a path or tree in a graph to construct the solution. In CA, we introduced the concepts of the bipartite graph for problem transformation and the division of labors to coodirate the power of colonies with different ability. In RMST, we combined the ideas of subset and tree to find solutions. In ETCP, we developed a pheromone representation for this problem, which has a dynamic problem space. Futher, we gave our attemption to classify the problems which are solved by ACO approaches.

第一章 緒 論 1
1.1 研究背景及動機 1
1.2 研究問題 2
1.3 研究目的 3
第二章 文獻探討 4
2.1 螞蟻族群最佳化 4
2.1.1 螞蟻族群 4
2.1.2 人工螞蟻 5
2.1.3 搜尋精神 8
2.1.4 螞蟻族群演算法 8
2.2 螞蟻族群最佳化的應用 11
2.2.1 旅行銷售員問題 12
2.2.2 二次分派問題 14
2.2.3 工作排程問題 15
2.2.4 運輸繞路問題 15
2.2.5 網路路由問題 16
2.2.6 連續性順序問題 17
2.2.7 著色問題與頻道分配問題 17
2.2.8 最短母字串問題 18
2.2.9 一般分配問題 19
2.2.10 複合背包問題 20
2.2.11漢米敦圖形辨識與圖形走覽問題 20
2.2.12 其他應用 22
第三章 研究方法 23
3.1 研究架構 23
3.2 研究步驟 24
第四章 螞蟻族群演算法之設計 25
4.1 基地台分配問題 25
4.1.1 基地台分配問題簡介 25
4.1.2基地台分配問題之近似解法 26
4.1.3 應用螞蟻族群演算法於基地台分配問題 27
4.2 節點覆蓋問題 31
4.2.1 節點覆蓋問題簡介 31
4.2.2 螞蟻族群演算法與MWVC 32
4.3 遠端擴張樹問題 36
4.3.1 遠端擴張樹問題簡介 37
4.3.2 應用螞蟻族群演算法於遠端擴張樹問題 38
4.4 演化樹建構問題 41
4.4.1 演化樹建構問題簡介 41
4.4.2 應用螞蟻族群演算法於演化樹建構問題 43
第五章 演算法實驗與分析 51
5.1 基地台分配問題實驗與分析 51
5.1.1 參數設定實驗 51
5.1.2 與其他近似解法比較 64
5.2 MWVC實驗與分析 67
5.3 遠端擴張樹問題實驗與分析 77
5.4 演化樹建構問題實驗與分析 81
第六章 結論 88
6.1 研究分析 88
6.2 研究結果 90
6.3 未來研究方向 91
參考文獻 92

[1] Bauer, A., Bullnheimer, B., Hartl, R.F. and Strauss C., Minimizing total tardiness on a single machine using ant colony optimization, Proceedings of the 1999 Congress on Evolutionary Computation, IEEE Press, Piscataway, NJ, pp.1445—1450, 1999.
[2] Beckers, R., Deneubourg, J. L. and Goss, S., Trails and u-turns in the selection of the shortest path by the ant lasius niger, Journal of Theoretical Biology, Vol.159, pp.397-415, 1992.
[3] Bhattacharjee P.S., Saha D. and Mukherjee A., Heuristics for assignment of cells to switches in a PCSN: a comparative study, 1999 IEEE International Conference on Personal Wireless Communication, pp. 331—334, 1999.
[4] Booker L., Goldberg D.E. and Holland J.H., Classifier systems and genetic algorithms, Artificial Intelligence, Vol. 40, pp. 235-282, 1989.
[5] Borndorfer R., Eisenblatter A., Grotschel M. and Martin A., The orientation model for frequency assignment problems, Technical Report TR 98—01, Konrad—Zuse—Zentrum für Informationstechnik, Berlin, Germany, 1998.
[6] Brelaz D., New methods to color vertices of a graph. Communications of the ACM, Vol. 22 pp.251—256, 1979.
[7] Bullnheimer, B.; Dorigo, M., An examination scheduling model to maximize students'' study time and an ant approach to solve it. Presentation at the 2 nd international conference on the Practice And Theory of Automated Timetabling (PATAT''97), Toronto, Canada, 1997.
[8] Bullnheimer B., Hartl R.F. and Strauss C., Applying the ant system to the vehicle routing problem, Presented at the 2nd Metaheuristic International Conference, Sophia-Antipolis, France, 1997.
[9] Bullnheimer, B., Kotsis, G. and Strauss, C., Parallelization strategies for the ant system. In: R. De Leone, A. Murli, P. Pardalos, G. Toraldo (Eds.), High Performance Algorithms and Software in Nonlinear Optimization; series: Applied Optimization, Vol. 24, Kluwer:Dordrecht, pp. 87-100, 1998.
[10] Cavalli-Sforza, L. L. and Edwards, A. W. F., Phyloge-netic analysis: Models and estimation procedures, Evolution, pp.32, 1967.
[11] Chen, J., Kanj, I., and Jia. W., Vertex cover: Further observations and further improvements. at 25th International Workshop on Graph-Theoretic Concepts in Computer Science (WG''99), Ascona, Switzerland, June 1999.
[12] Chvatal, V., A greedy heuristic for the set covering problem, Mathematics of Operations Research, Vol. 4, pp.233-235, 1979.
[13] Clarkson, K.L., A modification of the greedy algorithm for vertex cover, Information Processing Letters, Vol. 16, pp. 23-25, 1983.
[14] Colorni, A., Dorigo, M. and Maniezzo, V., Distributed Optimization by Ant Colonies. Proceedings of the First European Conference on Artificial Life, Paris, France, F.Varela and P.Bourgine (Eds.), Elsevier Publishing, pp. 134-142, 1992.
[15] Colorni, A., Dorigo, M. and Maniezzo, V., An investigation of some properties of an ant algorithm. Proceedings of the Parallel Problem Solving from Nature Conference (PPSN 92), Brussels, Belgium, R.Manner and B.Manderick (Eds.), Elsevier Publishing, pp. 509-520, 1992.
[16] Colorni A., Dorigo M., Maniezzo V., and Trubian M., Ant system for job-shop scheduling. Belgian Journal of Operations Research, Statistics and Computer Science (JORBEL), Vol. 34 pp.39—53, 1994.
[17] Costa D. and Hertz A., Ants can colour graphs. Journal of the Operational Research Society, Vol. 48 pp.295—305, 1997.
[18] Day, William H. E., Inferring phylogenies from dissim-ilarity matrices, Bull. of Math. Biol., 49(4), 1987.
[19] Di Caro G. and Dorigo M., AntNet: A mobile agents approach to adaptive routing. Technical Report 97-12, IRIDIA, Universit´e Libre de Bruxelles, 1997.
[20] Di Caro G. and Dorigo M., Extending AntNet for best-effort quality-of-service routing. Unpublished presentation at ANTS’98 - From Ant Colonies to Articial Ants: First International Workshop on Ant Colony Optimization http://iridia.ulb.ac.be/ants98/ants98.html, October 15-16 1998.
[21] Di Caro G. and Dorigo M., Two ant colony algorithms for best-effort routing in datagram networks. In Proceedings of the Tenth IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS’98), pp. 541—546. IASTED/ACTA Press, 1998.
[22] Dorigo, M. and Gambardella, L.M., Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1), pp.53-66, 1997. (Also Tecnical Report TR/IRIDIA/1996-5, IRIDIA, Universite Libre de Bruxelles.)
[23] Dorigo, M. and Gambardella, L.M., Ant colonies for the traveling salesman problem. BioSystems, Vol. 43, pp.73-81, 1997. (Also Tecnical Report TR/IRIDIA/1996-3, IRIDIA, Universite Libre de Bruxelles)
[24] Dorigo M. and Gambardella, L.M., A study of some properties of Ant-Q. Proceedings of PPSN IV-Fourth International Conference on Parallel Problem Solving From Nature, September, pp. 22-27, 1996, Berlin, Germany, Berlin: Springer-Verlag, pp. 656-665, 1996. (Also Tecnical Report TR/IRIDIA/1996-4, IRIDIA, Universite Libre de Bruxelles.)
[25] Dorigo M., Maniezzo, V. and Colorni, A., The ant system: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26(1), pp. 29-41, 1996.
[26] Dorigo M., Di Caro, G. and Gambardella, L. M., Ant algorithms for discrete optimization. Artificial Life, 5(2), pp.137-172, 1999.
[27] Dorigo, M., Maniezzo, V. and Colorni, A., Positive feedback as a search strategy. Technical Report No. 91-016, Politecnico di Milano, Italy, 1991.
[28] Dorigo, M., Bonabeau, Eric and Theraulaz, Guy, Ant algorithms and stigmergy, Future Generation Computer Systems Vol.16, pp.851— 871, 2000.
[29] Escudero L. F., An inexact algorithm for the sequential ordering problem. European Journal of Operations Research, Vol.37 pp.232—253, 1988.
[30] Farach, M., Kannan, S. and Warnow, T., A robust model for finding optimal evolutionary trees, Algorithmica, Vol.13 , pp. 155-179, 1995.
[31] Farris, J. S., Estimating phylogenetic trees from distance matrices, Amer. Naturalist, Vol.106, pp. 645-668, 1972.
[32] Felsenstein, J., Phylogenies from molecular sequences: Inference and reliability, Annual Rev. Genetics, Vol.22, pp. 521-565, 1988.
[33] Gambardella L.M., Taillard È.D. and Dorigo M., Ant colonies for the QAP, Technical Report IDSIA-4-97, IDSIA, Lugano, Switzerland, 1997.
[34] Gambardella L. M., Taillard E., and Agazzi G.., Macs-vrptw: A multiple ant colonysystem for vehicle routing problems with time windows. In D. Corne, M. Dorigo, and F. Glover, editors, New Methods in Optimisation. McGraw-Hill, 1999.
[35] Gambardella L. M. and Dorigo M., HAS-SOP: An hybrid ant system for the sequential ordering problem. Technical Report 11-97, IDSIA, Lugano, CH, 1997.
[36] Garey M.R. and Johnson, Computers and Intractability: A Guide to the Theory of NP-Compless, W.H. Freeman and Company, 1979.
[37] Glover F., Future paths for integer programming and links to artificial intelligence, Computers and Ops. Res. Vol.13, pp. 533-549, 1986.
[38] Glover F. and Laguna M., Tabu search. Boston: Kluwer Academic Publishers, 1997.
[39] Goldberg D. E., Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, Reading, MA, 1989.
[40] Guoying Lu and Zemin Liu., Multicast routing based on ant-algorithm with delay and delay variation constraints. IEEE APCCAS 2000. The 2000 IEEE Asia-Pacific Conference on Circuits and Systems, pp. 243 —246, 2000.
[41] Halldorsson M. M., Iwano K., Katoh N., and Tokuyama T., Finding subsets maximizing minimum structures. In Proceedings of the Sixth ACM-SIAM Symposium on Discrete Algorithms, Jan. 1995.
[42] Hoshyar, R., Jamali, S.H. and Locus, C., Ant colony algorithm for finding good interleaving pattern in turbo codes, Communications, IEE Proceedings, Vol: 147 Issue: 5 , Oct. pp. 257 —262, 2000.
[43] Hwang, F. K. and Richards, D. S., Steiner tree problems, Networks, 22, pp. 55-89, 1992.
[44] Jan, A.; Yamamoto, M.; Ohuchi, A., Evolutionary algorithms for nurse scheduling problem Evolutionary Computation, 2000. Proceedings of the 2000 Congress on , Vol. 1 pp.196-203 , 2000
[45] Karp, R.M., Reducibility among combinatorial problems, Complexity of Computer Computations, R.E Miller and J.W. Theater (Eds.), Plenum Press, New York, 1972.
[46] Kirkpatrick S., Gelatt C. D. JR, and Vecchi M. P., Optimization by Simulated Annealing, Science 220 (13 May 1983),pp. 671-680, 1983.
[47] Kuntz, P., Layzell, P. and Snyers, D., A colony of ant-like agents for partitioning in VLSI technology. In: Proc. of 4th European Conference on Artificial Life (Husbands, P. & Harvey, I., Eds.), pp. 417-424, MIT Press, Cambridge, MA. 1997.
[48] Lee, R.C.T., Computational Biology Lecture Notes, 2002.
[49] Leguizamón G. and Michalewicz Z., A new version of Ant System for subset problems, in: Proceedings of the 1999 Congress on Evolutionary Computation, IEEE Press, Piscataway, NJ, pp. 1459—1464 , 1999
[50] Leighton F., A graph coloring algorithm for large scheduling problems. Journal of Research of the National Bureau of Standards, Vol.84 pp. 489—505, 1979.
[51] Liang, Y.C. and Smith, A.E., An ant system approach to redundancy allocation, Proceedings of the 1999 Congress on Evolutionary Computation, IEEE Press, Piscataway, NJ, pp. 1478— 1484, 1999.
[52] Maniezzo V. and Carbonaro A., An ANTS heuristic for the frequency assignment problem, Future Generation Computer Systems, Vol.16, pp. 927-935, 2000.
[53] Michel R. and Middendorf M., An island model based ant system with lookahead for the shortest supersequence problem, in: A.E. Eiben, T. Back, M. Schoenauer, H.-P. Schwefel (Eds.), Proceedings of PPSN-V, Fifth International Conference on Parallel Problem Solving from Nature, Springer, Berlin, Germany, pp. 692—701 , 1998.
[54] Maniezzo V., Colorni A., Dorigo M., The Ant System applied to the quadratic assignment problem, Technical Report IRIDIA/94-28, IRIDIA, Université Libre de Bruxelles, Belgium, 1994.
[55] Maniezzo, V., Exact and approximate nondeterministic tree-search procedures for the quadratic assignment problem, Research Report CSR 98-1, Scienze dell''Informazione, University Di Bologna, Sede Di Cesena, Italy, 1998.
[56] Maniezzo, V. and Colorni, A., The ant system applied to the quadratic assignment problem. IEEE Transactions on Knowledge and Data Engineering, 1999.
[57] Merchant A. and Sengupta B., Assignment of cells to switches in PCS networks, IEEE/ACM Transactions on Networking, Vol.3 Issue: 5 , Oct. pp. 521—526, 1995.
[58] Motwani, R., Lecture Notes on Approximation Algorithms, Technical Report, STAN-CS-92-1435, Department of Computer Science, Stanford University, 1992.
[59] Pitt, L., A simple probabilistic approximation algorithm for vertex cover, Technical Report, YaleU/DCS/TR-404, Department of Computer Science, Yale University, 1985.
[60] Ramalhinho Lourenço H. and Serra D., Adaptive approach heuristics for the generalized assignment problem, Technical Report EWP Series No. 304, Department of Economics and Management, Universitat Pompeu Fabra, Barcelona. pp. 832—838 , 1998
[61] Saitou, N. and Nei, M., The neighbor-joining method: A new method for reconstructing phylogentic trees, Molecular Biol. Vol.4 , pp. 406-424, 1987.
[62] Schoofs L. and Naudts B., Ant colonies are good at solving constraint satisfaction problems, Evolutionary Computation, 2000. Proceedings of the 2000 Congress on , Vol 2, pp.1190—1195, 2000.
[63] Schoonderwoerd R., Holland O., Bruten J., and Rothkrantz L., Ant-based load balancing in telecommunications networks. Adaptive Behavior, 5(2) pp.169—207, 1996.
[64] Shyu, S. J., Yin, P. Y., Lin, B. M. T. and Haouari, M., An ant colony system for the generalized minimum spanning tree problem. Manuscript submitted for publication (NSC-90-2213-E-130-001), 2001.
[65] Shyu, S. J., Yin, P. Y. and Lin, B. M. T., An ant colony optimization algorithm for the minimum weight vertex cover problem. Manuscript submitted for publication. (NSC-90-2213-E-130-001), 2002.
[66] Shyu, S. J., Lin, B. M. T. and Haiao, T. S., Ant colony optimization for the cell assignment problem, Manuscript submitted for publication (NSC-90-2213-E-130-001), 2002.
[67] Song Y.H., Chou C.S. and Stonham T.J., Combined heat and power economic dispatch by improved ant colony search algorithm, Electric Power Systems Research 52, pp. 115-121, 1999.
[68] Stender, J., Hillebrand, E. and Kingdon, J., Genetic algorithms in optimisation, simulation and modeling. AmsterdamWashington , D.C. : IOS PressTokyo : Ohmsha , 1994.
[69] Stützle, T. and Dorigo, M., ACO algorithms for the quadratic assignment problem. In D. Corne, M. Dorigo and F. Glover, editors, New Ideas in Optimization, McGraw-Hill, 1999.
[70] Stützle T., Parallelization strategies for ant colony optimization. In A. E. Eiben, T. Back, M. Schoenauer, and H.-P. Schwefel, editors, Proceedings of PPSN-V, Fifth International Conference on Parallel Problem Solving from Nature, pages 722-731. Springer-Verlag, 1998.
[71] Stützle T. and Hoos. H., The MAX-MIN ant system and local search for the traveling salesman problem. In IEEE Conf. on Evol. Comp. (ICEC''97), pages 309-314, 1997.
[72] Stützle T., Hoos H., MAX-MIN ant system for the quadratic assignment problem, Technical Report AIDA-97-4, FG Intellektik, TH Darmstadt, July 1997.
[73] Stützle, T. and Dorigo, M., ACO algorithms for the quadratic assignment problem. In D. Corne, M. Dorigo and F. Glover, editors, New Ideas in Optimization, McGraw-Hill, 1999.
[74] Stützle T., An ant approach to the flow shop problem. In Proceedings of the 6th European Congress on Intelligent Techniques & Soft Computing (EUFIT''98), Vol.3, pp. 1560-1564. Verlag Mainz, Aachen, 1997.
[75] Taillard E.D. and Gambardella L.M., Adaptive memories for the quadratic assignment problem. Technical Report IDSIA-87-97, IDSIA, Lugano, Switzerland, 1997.
[76] Van Laarhoven, P.M.J., Aarts, E.H.L., Simulated Annealing: Theory and Applications. Reidel Publishing Company, 1987.
[77] Wagner, I.A., Lindenbaum, M. and Bruckstein, A.M., Cooperative covering by ant-robots using evaporating traces, Technical report CIS-9610, Center for Intelligent Systems, Technion, Haifa, April; IEEE Trans. Rob. Aut., 1996.
[78] Wagner I.A. and Bruckstein A.M., Hamiltonian(t)-an ant-inspired heuristic for recognizing Hamiltonian graphs. Evolutionary Computation, CEC 99. Proceedings of the 1999 Congress on , Vol. 2, 1999.
[79] Wagner, Israel A. , Lindenbaum, Michael and Bruckstein, Alfred M., ANTS: agents on networks, trees, and subgraphs, Future Generation Computer Systems Vol.16, pp. 915— 926, 2000.
[80] Wareham, H. T., On the computational complexity of inferring evolutionary trees, Master''s thesis, Technical report 9301, Department of Computer Science, Memorial University of Newfoundland, St. John''s, NF, Canada, 1993.
[81] Watkins C. J. C. H., “Learning with delayed rewards,” Ph.D. dissertation, Psychology Dept., Univ. of Cambridge, UK, 1989.
[82] Watkins C.J.C.H., Learning with delayed rewards. Ph.D. dissertation, Psychology Department, University of Cambridge, England, 1989.
[83] Yu, In-Keun, Chou, C.S. and Song, Y.H., Application of the ant colony search algorithm to short-term generation scheduling problem of thermal units, Power System Technology, 1998. Proceedings. POWERCON ''98. 1998 International Conference on , Vol. 1 pp. 552 -556 , 1998.
[84] Zhangsu-Bing and Liu Ze-Min, Neural network training using ant algorithm in ATM traffic control. Circuits and Systems, 2001. ISCAS 2001. The 2001 IEEE International Symposium on , Vol. 2 pp. 157 -160, 2001.