Algorytm wielu kolonii mrówek dla optymalnego dopasowania w ważonych grafach dwudzielnych

• Autorzy: Schiff K.

Warianty tytułu

EN

Multi-type Ant colony algorithm for optimal matching problem in weighted bipartite graph

• Języki publikacji: PL

Abstrakty

PL

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.

EN

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.

Słowa kluczowe

PL

optymalizacja koloniami mrówek wielu typów; minimalny problem dopasowania w grafach dwudzielnych; maksymalny problem dopasowania w grafach dwudzielnych

EN

Multi-type Ant Colony Optimization; minimum weighted bipartite matching; maximum weighted bipartite matching

• Wydawca: Wydawnictwa AGH
• Czasopismo: Elektrotechnika i Elektronika
• Rocznik: 2008
• Tom: T. 27, z. 2
• Strony: 115--119
• Opis fizyczny: Bibliogr. 6 poz., rys., tab.

Twórcy

autor

Schiff K.

• Politechnika Krakowska, Katedra Automatyki

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