Dynamics of Stochastic vs. Greedy Heuristics in Traveling Salesman Problem

Journal Title: Zeszyty Naukowe Warszawskiej Wyższej Szkoły Informatyki - Year 2018, Vol 12, Issue 19

Abstract

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.

Authors and Affiliations

Maciej Białogłowski, Mateusz Staniaszek, Wojciech Laskowski, Marcin Grudniak

Keywords

Related Articles

Algorytmy konstrukcyjne dla problemu harmonogramowania projektu z ograniczonymi zasobami

W artykule opisany jest problem harmonogramowania projektu z ograniczoną dostępnością zasobami z kryterium minimalizacji czasu trwania projektu. Do rozwiązania zagadnienia opracowane są algorytmy konstrukcyjne, które mog...

Ontologia cyberprzestrzeni

W artykule przedstawiono podstawy ontologii cyberprzestrzeni oraz propozycje ujęcia jej istoty jako megasieci i systemu złożonego oraz koncepcję ewolucji cyberprzestrzeni.

Symulowane wyżarzanie dla problemu harmonogramowania projektu z ograniczonymi zasobami

W artykule przedstawiony jest problem harmonogramowania projektu z ograniczonymi zasobami z kryterium minimalizacji czasu trwania przedsięwzięcia. Do rozwiązania zagadnienia stosowany jest algorytm symulowanego wyżarzani...

A Knowledge Representation Framework Based on Epistemic Logic

We introduce a uniform non-monotonic framework for knowledge representation based on epistemic logic which is sufficiently general to encompass several nonmonotonic formalisms, including circumscription, autoepistemic lo...

On EDF scheduler with the exponential deadlines

This work deals with the performance evaluation of EDF (Earliest Deadline First) packet scheduler with two classes. The primary metric of interest is the mean sojourn time for each class. The system is composed of two cl...

Download PDF file
  • EP ID EP476369
  • DOI 10.26348/znwwsi.19.7
  • Views 114
  • Downloads 0

How To Cite

Maciej Białogłowski, Mateusz Staniaszek, Wojciech Laskowski, Marcin Grudniak (2018). Dynamics of Stochastic vs. Greedy Heuristics in Traveling Salesman Problem. Zeszyty Naukowe Warszawskiej Wyższej Szkoły Informatyki, 12(19), 7-24. https://europub.co.uk/articles/-A-476369