臺灣博碩士論文加值系統

螞蟻族群最佳化 (Ant Colony Optimization) 是一種新的多用途經驗法則 (meta-heuristic) 演算法；由Dorigo等人於90年代初期所提出。螞蟻族群最佳化是一種藉由觀察自然界螞蟻的行為所產生的演算法；已成它a解決釵h不同種類的組合最佳化問題。正因螞蟻族群之天性結構蘊涵了實作於電腦時的平行處理，本論文即在探索螞蟻族群最佳化的各種平行可能性。我們提出螞蟻族群最佳化在單一處理器內或多處理器間之運算與訊息傳遞的各式平行組合；並以最小權重點覆趕暋D (minimum weight vertex cover) 為測試的對象；對在個人電腦叢集上實作平行計算後的實驗數據，進行整理和討論。

The Ant Colony Optimization (ACO) is a new meta-heuristic that is proposed by Dorigo et al. (1991) to solve hard combinatorial optimization problems. It is a population-base, nature-inspired approach and has been applied successfully to variety combinatorial optimization problems. As the structure of the ACO highly suggests a parallel implementation of the algorithm, we would like to explore the parallelism of ACO in this paper. The various alternatives of the parallelism of the computations and communications of ACO within a processor as well as among processors are generally proposed. We test our parallel ideas on the minimum weight vertex cover (MWVC) problem. The computational results of the implementation of our parallel ACO algorithms for MWVC on a PC cluster are reported and analyzed.

Chapter 1. Introduction
Chapter 2. Ant Colony Optimization
2.1 Outline of ACO 3
2.2 Minimum weight vertex cover problem
2.3 ACO for the Minimum Weight Vertex Cover Problem
Chapter 3. Parallelism of ACO
3.1 Literature Review
3.2 Parallelism of ACO
3.3 Communications of Shared Information
Chapter 4. Experimental Results
Experiment 1
Experiment 2
Experiment 3
Experiment 4
Experiment 5
Chapter 5. Conclusion
Reference 38
Appendix A. Comparison for results of different strategies in pheromone updating rule
Appendix B. Parameter Setting of the fraction of pheromone adjusted in master-slave model

[1]A. Bauer, B. Bullnheimer, R. F. Hartl and C. Strauß, An Ant Colony Optimization Approach for the Single Machine Total Tardiness Problem, Proceedings of the Congress on Evolutionary Computation, 1999
[2]C. Blum and M. Dorigo, The Hyper-Cube Framework for Ant Colony Optimization, IEEE Transactions on Systems, Man and Cybernetics B, 34(2), 1161 - 1172, 2004
[3]R. Bar-Yehuda, S. Even, A local-ratio theorem for approximating the Weighted Vertex Cover problem, Ann. Discrete Math. 25 (1985) 27-46
[4]B. Bullnheimer, G. Kotsis and C. Strauß, Parallelization Strategies for the Ant System, Adaptive Information Systems and Modelling in Economics and Management Science, Nr. 8, October 1997
[5]B. Bullnheimer, R. F. Hartl and C. Strauss, An Improved Ant System Algorithm for the Vehicle Routing Problem, Sixth Viennese workshop on Optimal Control, Dynamic Games, Nonlinear Dynamics and Adaptive Systems, Vienna (Austria), May 21-23, 1997
[6]E. Bonabeau, M. Dorigo and G. Theraulaz, Inspiration for optimization from social insect behavior, Nature, Vol. 406, 6 July, 2000, pp.39-42.
[7]M. den Besten, T. Stützle, M. Dorigo, Ant Colony Optimization for the Total Weighted Tardiness Problem, Parallel Problem Solving from Nature - PPSN VI 6th International Conference, 2000
[8]V. Chvatal, A greedy-heuristic for the set cover problem, Mathematics of Operations Research, Vol. 4, 1979, pp. 233-235.
[9]K. L. Clarkson, A Modification of the Greedy Algorithm for Vertex Cover, Information Processing Letters, Vol. 16, pp. 23--25, January 1983
[10]D. Corne, M. Dorigo, and F. Glover (eds.), New Ideas in Optimization. New York: McGraw-Hill, pp. 11–32
[11]A. Colorni, M. Dorigo and V. Maniezzo, Distributed optimization by ant colonies. In: Varela F, Bourgine P, eds. Proc. of the ECAL''91 European Conf. of Artificial Life. Paris: Elsevier, 1991. 134~144.
[12]A. Colorni, M. Dorigo, F. Maffioli, V. Maniezzo, G. Righini, M. Trubian, HEURISTICS FROM NATURE FOR HARD COMBINATIORIAL OPTIMIZATION PROBLEM, International Transactions in Operational Research, 3, 1, pag. 1-21
[13]C. K. Chau, A Non-Convergence to the Optimal Path in Parallel Ant Colony Optimization, Working Paper, 2002
[14]M. Dorigo, Optimization, learning and natural algorithms. Ph.D.Thesis, Politecnico di Milano, Italy, 1992
[15]M. Dorigo, E. Bonabeau and G. Theraulaz, Ant algorithms and stigmergy. Future Generation Computer Systems 16, pp.851– 871.
[16]M. Dorigo, G. D. Caro and L. M. Gambardella, Ant Algorithm for Discrete Optimization, Artificial Life 5: 137-172, 1999
[17]M. Dorigo and G. D. Caro, Ant Colony Optimization: A New Meta-Heuristic, Proc. 1999 Congress on Evolutionary Computation, July 6-9, 1999, pp. 1470-1477.
[18]M. Dorigo and G. D. Caro, The Ant Colony Optimization Meta-Heuristic, Chapter 2 : New Ideas in Optimization, McGraw Hill, 1999
[19]M. Dorigo and L. M. Gambardella, Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem, IEEE Transactions on Evolutionary Computation, Vol. 1, No. 1, 1997
[20]M. Dorigo and L. M. Gambardella, Ant colonies for the traveling salesman problem, BioSystems, Vol. 43, 1997b, pp. 73-81.
[21]P. Delisle, M. Krajecki, M. Gravel and C. Gagné, PARALLEL IMPLEMENTATION OF AN ANT COLONY OPTIMIZATION METAHEURISTIC WITH OPENMP, International Conference on Parallel Architectures and Compilation Techniques, 2001.
[22]M. Dorigo, V. Maniezzo, & A. Colorni, Positive feedback as a search strategy. (Tech. Rep. 91-016). Milan, Italy: Politecnico di Milano, Dipartimento di Elettronica, 1991
[23]M. Dorigo, V. Maniezzo and A. Coloni, The Ant System: Optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybermetics-Part B, Vol. 26, No. 1, 1996, pp. 1-13
[24]I. Dinur and S. Safra, On the importance of Being Biased (1.36 hardness of approximating Vertex-Cover), Annals of Mathematics, to appear. Proc. of 34th STOC, 2002
[25]M. Dorigo and T. Stützle, The Ant Colony Optimization Metaheuristic: Algorithms, Applications, and Advances, Metaheuristic Network Publication International Summer School on Metaheuristics, March 3-7, 2003
[26]L. M. Gambardella and M. Dorigo, Ant-Q: A Reinforcement Learning approach to the traveling salesman problem, International Conference on Machine Learning, 1995
[27]L. M. Gambardella and M. Dorigo, Solving Symmetric and Asymmetric TSPs by Ant Colonies, IEEE Conference on Evolutionary Computation (ICEC’ 96), May 20-22. 1996, Nagoya, Japan
[28]M. R. Garey and D. S. Johnson, Computers and Intractability. A Guide to the Theory of NP-Completeness, W. H Freeman and Company, 1979
[29]M. Guntsch and M. Middendorf: A Population Based Approach for ACO, EvoWorkshops 2002: 72-81
[30]J. Håstad, Some optimal inapproximability results, Journal of ACM, Vol.~48, 2001, pp 798--859.
[31]M. T. Islam, P. Thulasiraman and R. K. Thulasiram, A Parallel Ant Colony Optimization Algorithm for All-Pair Routing in MANETs, IEEE Proceedings of the International Parallel and Distributed Processing Symposium, 2003
[32]R. Karp, Reducibility among Combinatorial Problems, Complexity of Computer Computations, Plenum Press, 1972
[33]Asistidis Likas, Anderas Stafylopatis, A Parallel Algorithm for the Minimum Weight Vertex Cover Problem, Information Processing Letter, 1995
[34]G. Leguizamon and Z. Michalewicz, A New Version of Ant System for Subset Problems, Proceedings of the Congress on Evolutionary Computation, July 6-9, 1999, pp.1459-1464.
[35]R. Motwani, Lecture Notes on Approximation Algorithms Volume I (1992)
[36]V. Maniezzo and A. Carbonaro, Ant Colony Optimization: An Overview, CiteSeer, 1999
[37]V. Maniezzo, A. Colorni,, & M. Dorigo, The Ant System applied to the quadratic assignment problem. (Tech. Rep. IRIDIA/94-28). Belgium: Universit´e Libre de Bruxelles, 1994
[38]R. Michels and M. Middendorf, An Ant System for the Shortest Common Supersequence Problem, Technical Report 378, Institute AIFB, University of Karlsruhe, Germany, June 1998
[39]M. Middendorf, F. Reischle and H. Schmeck, Information Exchange in Multi Colony Ant Algorithm, Parallel and Distributed Computing, Proceedings of the 15 IPDPS 2000 Workshops, 2000
[40]M. Middendorf, F. Reischle and H. Schmeck, Multi Colony Ant Algorithms, Journal of Heuristics, 8: 305-320, 2002
[41]L. Pitt, A Simple Probabilistic Approximation Algorithm for Vertex Cover, Technical Report YaleU/DCS/TR-404, Department of Computer Science, Yale University, 1985
[42]V. T. Paschos. A survey of approximately optimal solutions to some covering and packing problems. ACM Computing Surveys, 29(2):171--209, June 1997.
[43]D.A.L. Piriyakumar and P. Levi, A new approach to exploiting parallelism in ant colony optimization, Proceedings of 2002 International Symposium on Micromechatronics and Human Science, pp. 237-243, 2002
[44]M.J. Quinn. Parallel computing: Theory and practice, McGraw-Hill, 1994
[45]M. Randall, A Parallel Implementation of Ant Colony Optimization, Journal of Parallel and Distributed Computing, 2002.
[46]M. Randall, A. Lewis, A Parallel Implementation of Ant Colony Optimization, Journal of Parallel and Distributed Computing, Volume 62, Number 9, 1421-1432, September 2002
[47]O. Roux, C. Fonlupt, E. Talbi and D. Robilliard, ANTabu - enhanced version LIL-99-1, http://fmatbhpl.tu-graz.ac.at/%7Ekarisch/qaplib/
[48]T. Stützle, MAX-MIN Ant System for Quadratic Assignemnt Problems, Intellectics Group: Technical Report, 1997
[49]T. Stützle, Parallelization Strategies for Ant Colony Optimization, Lecture Notes in Computer Science, 1998.
[50]T. Stützle and M. Dorigo, ACO Algorithm for Traveling Salesman Problem, Evolutionary Algorithms in Engineering and Computer Science, Wiley, 1999
[51]T. Stützle, H. Hoos, MAX-MIN Ant System, Future Generation Computer Systems Journal. 16(8):889-914, 2000
[52]S. J. Shyu, B. M. T. Lin and T. S. Hsiao, Ant Colony Optimization for the Cell Assignment Problem in PCS Network, IEEE Transactions on Systems, Man and Cybernetics: Part B , May 2003
[53]S.J. Shyu, B.M.T. Lin and P.Y. Yin, An application of ant colony systems to no-wait flowshop scheduling, presented at The INFORMS Meeting , Maui , Hawaii , June, 2001.
[54]S.J. Shyu, P.Y. Yin and B.M.T Lin, An Ant Colony Optimization Algorithm for the Minimum Weight Vertex Cover Problem, to appear in Annals of Operations Research, 2004
[55]E-G. Talbi, O. Roux, C. Fonlupt and D. Robillard, Parallel Ant Colonies for Combinatorial Optimization Problems, IEEE Int. Parallel Processing Symposium / Symposium on Parallel and Distributed Processing, 1999
[56]E-G. Talbi, O. Roux, C. Fonlupt, D. Robillard, Parallel Ant Colony for the Quadratic Assignment Problem, Future Generation Computer System, Vol. 17 (4) pp. 441-449 2001.