An improved ant algorithm for the triple matching problem

• Autorzy: Schiff Krzysztof

Identyfikatory

DOI

10.37705/TechTrans/e2020005

Warianty tytułu

PL

Udoskonalony algorytm mrówkowy dla potrójnego zagadnienia dopasowania

• Języki publikacji: EN

Abstrakty

EN

In this article a new version of the ant colony optimisation algorithm with a desirability function for the triple matching problem is described. The problem is modelled by means of two 2-dimensional arrays. The new version of the ant algorithm was compared with the previous version of the ant algorithm and tested for different values of ant algorithm parameters; the results of these tests are presented and discussed.

PL

W artykule został przedstawiony w nowszej wersji algorytm mrówkowy wraz z funkcją pożądania dla problemu potrójnego zagadnienia dopasowania. Problem potrójnego dopasowania zaprezentowano przy pomocy tablic dwuwymiarowych. Algorytm mrówkowy został porównany ze starszą wersją algorytmu mrówkowego i przetestowany przy różnych wartościach parametrów algorytmu mrówkowego, a wyniki tych testów pokazano i omówiono.

Słowa kluczowe

EN

triple maximum matching problem; ant colony optimisation

PL

zagadnienie potrójnego maksymalnego dopasowania; algorytm mrówkowy

• Wydawca: Wydawnictwo Politechniki Krakowskiej im. Tadeusza Kościuszki
• Czasopismo: Technical Transactions
• Rocznik: 2020
• Tom: Vol. 117, iss. 1
• Strony: art. no. e2020005
• Opis fizyczny: Bibliogr. 7 poz., tab., wz.

Twórcy

autor

Schiff Krzysztof

• Department of Automatic Control and Technology Information, Faculty of Electrical and Computer Engineering, Cracow University of Technology

Bibliografia

• Biro, P., McDermid, E. (2010). Three-sided stable matching with cyclic preferences. Algorithmica, 58(1), 5–18.
• Chen, J. (2012). Iterative Expansion and Color Coding: an Improved Algorithm for 3D-Matching. ACM Transactions on Algorithms, 6.1–6.22.
• Dorigo, M., Stützle, T. (2002). Ant colony optimization. In Proceedings of EvoWorkshops 2002 (pp. 61–71). Berlin: Heidelberg: Springer-Verlag.
• Eriksson, K., Sjostrand, J., Strimling, P. (2006). Three-dimensional stable matching with cyclic preferences. Math. Soc. Sci., 52(1), 77–87.
• Karp, R. M. (1972). Reducibility among combinatorial problems. In R. Miller, J. Thatcher (Eds.), Complexity of Computer Computations (pp. 85–103). New York: Plenum.
• Knuth, D. (1997). Stable marriage and its relation to other combinatorial problems: An introduction to the mathematical analysis of algorithms. Rhode Island: American Mathematical Society.
• Schiff, K. (2018). An ant algorithm for the triple matching problem. Technical Transaction, 2(115), 179–186.

Uwagi

Section "Electrical Engineering"

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).