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

Model motywacji nauczyciela i studentów podczas nabywania kompetencji

Artykuł prezentuje pomysł na opracowanie modelu motywacji, mający na celu wspieranie aktywności zarówno studentów, jak i nauczycieli przy wdrażaniu i wykorzystaniu systemu otwartego nauczania na odległość. Opisano strukt...

Hybrydowy system rekomendacji planów treningowych

Hybrydowe systemy rekomendacji łączą zalety metod stosowanych powszechnie w rekomendacji. Głównym celem tego artykułu jest przedstawienie zastosowania uczenia maszynowego do budowy hybrydowego silnika rekomendacji. Uczen...

Systemy ekspertowe w e-zdrowiu: studium przypadku diagnostyki grypy

Systemy ekspertowe, które stanowią jedną z dziedzin sztucznej inteligencji, wykorzystywane są w rozwiązywaniu problemów oraz wspomagają użytkownika w procesie podejmowania decyzji poprzez podpowiadanie możliwych rozwiąza...

Porównanie wydajności i produktywności algorytmu tworzenia drzew decyzyjnych zaimplementowanego w środowiskach SPARK oraz GASPI

W pracy zbadano wydajność i produktywność programistyczną wykorzystania chmur obliczeniowych oraz dwu odmiennych środowisk programistycznych, a mianowicie SPARK i GASPI, do równoległej implementacji algorytmów eksplorują...

Bezpieczeństwo zasobów informacyjnych determinantą informatycznych technologii zarządzania

W artykule przedstawiono problem bezpieczeństwa zasobów informacyjnych w kontekście wykorzystania informatycznych systemów wspomagających zarządzanie. Skoncentrowano się na metodach i technikach zapewniania ciągłości dzi...

Download PDF file
  • EP ID EP476369
  • DOI 10.26348/znwwsi.19.7
  • Views 113
  • 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