An ant colony optimisation algorithm for the triple matching problem

• Autorzy: Schiff K.

Identyfikatory

DOI

10.4467/2353737XCT.18.028.8001

Warianty tytułu

PL

Algorytm mrówkowy dla potrójnego zagadnienia dopasowania

• Języki publikacji: EN

Abstrakty

EN

In this article, ant colony optimisation algorithms for the triple matching problem are described. This is the first elaborated ant algorithm for this problem. The problem is modeled by means of a 3-dimensional array. The ant algorithm was compared with the Apx3Dmatchnig-F algorithm and tested for different values of ant algorithm parameters. The results of these tests were presented and discussed.

PL

W artykule został przedstawiony po raz pierwszy algorytm mrówkowy dla problemu potrójnego zagadnienia dopasowania. Problem potrójnego dopasowania zaprezentowano przy pomocy tablicy trój-wymiarowej. Algorytm mrówkowy został porównany z algorytmem Apx3Dmatching-F i przetestowany przy różnych wartościach parametrów algorytmu mrówkowego, a wyniki tych testów zostały zaprezentowane i omówione.

Słowa kluczowe

EN

triple maximum matching problem; ant colony optimization algorithm; non weighted version

PL

potrójne maksymalne dopasowanie; algorytm mrówkowy; wersja bez wag

• Wydawca: Wydawnictwo Politechniki Krakowskiej im. Tadeusza Kościuszki
• Czasopismo: Technical Transactions
• Rocznik: 2018
• Tom: Vol. 115, iss. 2
• Strony: 179--186
• Opis fizyczny: Bibliogr. 8 poz., wz., tab., wykr., il.

Twórcy

autor

Schiff K.

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

Bibliografia

• [1] Karp R.M., Reducibility among combinatorial problems, [in:] R. Miller, J. Thatcher, Complexity of Computer Computations, Plenum, 1972, 85–103.
• [2] Knuth, D., Stable marriage and its relation to other combinatorial problems, An introduction to the mathematical analysis of algorithms, Amer. Math. Soc., Providence, RI, 1997.
• [3] Biro P., McDermid, E., Three-sided stable matching with cyclic preferences, Algorithmica 58(1), 2010, 5–18.
• [4] Eriksson, K., Sjostrand, J., Strimling, P., Three-dimensional stable matching with cyclic preferences, Math. Soc. Sci. 52(1), 2006, 77–87.
• [5] Dorigo M., Stützle T., Ant colony optimization, Cambridge MIT Press. Proceedings of EvoWorkshops 2002, Berlin, Heidelberg, Springer-Verlag, 2002, 61–71.
• [6] Chen J., Iterative Expansion and Color Coding, an Improved Algorithm for 3D-Matching, ACM Transactions on Algorithms, 2012, 6.1–6.22.
• [7] Cao J., Chang W-L, Guo M., Using sticker to solve the 3-dimensional matching problem in molecular supercomputers, Int. J. High Performance Computing and Networking, Vol. 1, 2004, Nos. 1/2/3.
• [8] Epifiano F.S., Ogasawara E., Soares J., Amorim M., Souza U., O Problema de Alocacao deTutores em Aplicacoes de Provas, XLVI Simposio Brasileiro de Pesquisa Operacional, Salvador, 16–19.09.2014 Brasil, 2014, 3007–3018.

Uwagi

EN

Section "Electrical Engineering"

PL

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).