Dynamics of Stochastic vs. Greedy Heuristics in Traveling Salesman Problem

• Autorzy: Białogłowski M. , Staniaszek M. , Laskowski W. , Grudniak M.

Identyfikatory

DOI

10.26348/znwwsi.19.7

• Języki publikacji: EN

Abstrakty

EN

We studied the relative performance of stochastic heuristics in order to establish the relations between the fundamental elements of their mechanisms. The insights on their dynamics, abstracted from the implementation details, may contribute to the development of an efficient framework for design of new probabilistic methods. For that, we applied four general optimization heuristics with varying number of hyperparameters to traveling salesman problem. A problem-specific greedy approach (Nearest Neighbor) served as a reference for the results of: Monte Carlo, Simulated Annealing, Genetic Algorithm, and Particle Swarm Optimization. The more robust heuristics – with higher configuration potential, i.e. with more hyperparameters – outperformed the smart ones, being surpassed only by the method specifically designed for the task.

Słowa kluczowe

EN

traveling salesman problem; Nearest Neighbor; Monte Carlo; Simulated Annealing; genetic algorithm; particle swarm optimization (PSO)

• Wydawca: Warszawska Wyższa Szkoła Informatyki
• Czasopismo: Zeszyty Naukowe Warszawskiej Wyższej Szkoły Informatyki
• Rocznik: 2018
• Tom: nr 19
• Strony: 7--24
• Opis fizyczny: Bibliogr. 9 poz., rys., tab., wykr.

Twórcy

autor

Białogłowski M.

• Warsaw School of Computer Science

autor

Staniaszek M.

• Warsaw School of Computer Science

autor

Laskowski W.

• Warsaw School of Computer Science

autor

Grudniak M.

• Warsaw School of Computer Science

Bibliografia

• [1] S.S. Skiena, The Algorithm Design Manual (2nd ed.), Springer, 2008.
• [2] S. Kirkpatrick, C.D. Gelatt Jr., M.P. Vecchi, Optimization by Simulated Annealing, Science, 220, 671-680, 1983.
• [3] F. Glover, Future paths for integer programming and links to artificial intelligence, Comput. Oper. Res., 13, 533-549, 1986.
• [4] D. Whitley, A genetic algorithm tutorial, Stat. Comput., 4, 65-85, 1994.
• [5] M.R. Bonyadi, Z. Michalewicz, Particle Swarm Optimization for Single Objective Continuous Space Problems: A Review, Evol. Comput., 25, 1-54, 2017.
• [6a] gr96 [Online]. http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/gr96.tsp [access 9/11/18]
• [6b] gr137 [Online]. http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/gr137.tsp [access 9/11/18]
• [6c] gr202 [Online]. http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/gr202.tsp [access 9/11/18]
• [6d] gr229 [Online]. http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/gr229.tsp [access 9/11/18]
• [6e] gr431 [Online]. http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/gr431.tsp [access 9/11/18]
• [6f] gr666 [Online]. http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/gr666.tsp [access 9/11/18]
• [7] Implementations of heuristics [Online]. https://github.com/WojtaX/TSPheuristics [access 26/11/18]
• [8] Discrete and Combinatorial Optimization Group, Heidelberg University [Online]. https://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLI B95/STSP.html [access 9/11/18]
• [9] D.J. Rosenkrantz, R.E. Stearns, P.M. Lewis, An Analysis of Several Heuristics for the Traveling Salesman Problem, SIAM J. Comput., 6, 563-581, 1977.

Uwagi

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

2. Zgodnie z numeracją , bibliografii liczy 14 poz.