Identyfikatory
Warianty tytułu
Multi-type Ant colony algorithm for optimal matching problem in weighted bipartite graph
Języki publikacji
Abstrakty
Praca prezentuje algorytm wykorzystujący metodę optymalizacji różnymi typami kolonii mrówek dla problemu maksymalnego i minimalnego dopasowania w ważonych grafach dwudzielnych. Algorytm ten wyznacza optymalne dopasowanie, bazując na wyznaczaniu rozdzielnych ścieżek w grafie między wierzchołkami s-t, które stanowią rozwiązanie dla problemu optymalnego dopasowania w ważonych grafach dwudzielnych. Opracowany algorytm został porównany z algorytmem węgierskim i algorytmem mrówkowym o jednym typie kolonii mrówek i omówione zostały wyniki tego porównania.
In this paper algorithm for optimal matching problem in weighted bipartite graph is presented, which is based on multi-type ant colony optimization. Matching problem is modeled as disjoint-paths problem between s-t vertices. Multi-type ants was used in order to find these disjoint paths between s-t vertices which are the solution for optimal matching problem in weighted bipartite graph. The algorithm was compared with Hungarian algorithm and ACO algorithm for optimal matching problem in weighted bipartite graph and results of this comparison was discussed.
Wydawca
Czasopismo
Rocznik
Tom
Strony
115--119
Opis fizyczny
Bibliogr. 6 poz., rys., tab.
Twórcy
Bibliografia
- [1] Dorigo M., Di Caro G.: The Ant Colony Optimization meta-heuristics. [w:] Corne D., Dorigo M., Glover F. (eds.), New Ideas in Optimization, McGraw Hill, UK, 1999, 11-32
- [2] Munkers J.: Algorithms for the Assignment and Transportation Problems. Journal of the Society of Industrial and Applied Mathematics, vol. 5, no. 1, 1957, 32-38
- [3] Shih H.: Two Algorithms for the maximum and minimum weighted bipartite matching. Raport, Department of Computer Science and Information engineering, National Taiwan University 2006
- [4] Nowe A., Verbeeck K., Vrancx P.: Multi-type Ant colony: The Edge Disjoint Paths Problem [w:] M. Doringo i in.: Ant colony Optimization and Swarm Intelligence, 4 International Worskshops, Belgium, September 2004, Proceedings, Springer 2004
- [5] Blesa M. J., Blum Ch.: On Solving the Maximum Disjoint Paths Problem with Ant Colony Optimization. Raport, Department de Llengu-atges i Sistemes Informatics, Universitat Politecnica de Catalunya, Barcelona, Spain 2006
- [6] Stutzle T., Doringo M.: AC O Algorithms for the Traveling Salesman Problem, [w:] K. Miettinen, M. Makela, P. Neittananmaki i J. Periaux (Eds), Evolutionary Algorithms in Engineering and Computer Science, Wiley 1999
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-AGH2-0010-0025