臺灣博碩士論文加值系統

This thesis applies two algorithms to the maximum and minimum weighted bipartite matching problems. In such matching problems, the maximization and minimization problems are essentially same in that one can be transformed
into the other by replacing the weight on each edge with an inverse of the weight. Depending on the algorithms we used, we will choose the maximization or minimization problems for illustrations. We apply the ant colony optimization (ACO) algorithm on a minimum weighted bipartite matching
problem by transforming the problem to a traveling salesman problem (TSP). It may seem that makes the problem more complicated, but in reality it does not. We call this algorithm “ant-matching,” which can solve any weighted
bipartite matching problems with or without a perfect matching. Besides, we also apply the Metropolis algorithm to solve the maximum weighted bipartite matching problem. To analyze the performance on these two algorithms, we
compare the algorithms with the exact Hungarian algorithm, a well-known combinatorial optimization method for solving the weighted bipartite matching problem.

1 Introduction 5

2 Preliminaries 6
2.1 Maximum/Minimum Weighted Bipartite Matching . . . . . 6
2.1.1 Weighted Bipartite Graph . . . . . . . . . . . . . 6
2.1.2 Maximum/Minimum Weighted Bipartite Matching . . . . 6
2.2 Ant Colony Optimization . . . . . . . . . . . . . . . 7
2.3 Metropolis Algorithm . . . . . . . . . . . . . . . . 8

3 Maximum/Minimum Weighted Bipartite Matching Problems 10
3.1 ACO Algorithm for Minimum-Weighted Bipartite Matching 10
3.1.1 Transforming Minimum-Weighted Bipartite Matching
to Traveling Salesman Problem . . . . . . . . . . . . . . 11
3.1.2 Using ACO Algorithm to Solve Minimum-Weighted Bipartite Matching . . . . . . . . . . . . . . . . . . . 13
3.1.3 The Complexity of Ant-Matching Algorithm . . . . . 14
3.2 Metropolis Algorithm for Maximum-Weighted Bipartite
Matching . . . . . . . . . . . . . . . . . . . . . . . . 14
3.2.1 The Complexity of Metropolis Algorithm . . . . . . 16

4 Experimental Results 17
4.1 Comparison of Complexity . . . . . . . . . . . . . . 17
4.2 Graph Sampling Algorithm . . . . . . . . . . . . . . 18
4.3 Results . . . . . . . . . . . . . . . . . . . . . . . 18
4.3.1 Results on Complete Bipartite Graphs . . . . . . . 19
4.3.2 Results on Sparse Bipartite Graphs . . . . . . . . 20
4.3.3 Results on Ant-Matching Algorithm . . . . . . . . . 23
4.3.4 Results on Metropolis Algorithm . . . . . . . . . . 25
5 Conclusions 35

Bibliography 36

[1] S. Chib and E. Greenberg. (1995) Understanding the Metropolis-Hasting Algorithm. The American Statistician, Vol. 49, No. 4 (November 1995), pp. 327–335.

[2] J. Munkres. (1957) Algorithms for the Assignment and Transportation Problems. Journal of the Society of Industrial and Applied Mathematics, Vol. 5, No. 1 (March 1957), pp. 32–38.

[3] Y. Nakamichi and T. Arita. (2001) Diversity Control in Ant Colony Optimization. Proceedings of the Inaugural Workshop on Artificial Life (AL’01), pp. 70–78, Adelaide, Australia, December 2001.

[4] T. St¨utzle, M. Dorigo. (1999) ACO Algorithms for the Traveling Salesman Problem. In K. Miettinen, M. Makela, P. Neittaanmaki, and J. Periaux, editors, Evolutionary Algorithms in Engineering and Computer Science. Wiley, 1999.

[5] I, Wegener. (2005) Simulated Annealing Beats Metropolis in Combinatorial Optimization. ICALP 2005. LNCS 3580, pp. 589–601.