PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

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

Autorzy
Treść / Zawartość
Identyfikatory
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.
Wydawca
Rocznik
Strony
115--119
Opis fizyczny
Bibliogr. 6 poz., rys., tab.
Twórcy
autor
  • 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
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-AGH2-0010-0025
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.