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
- EP ID EP476369
- DOI 10.26348/znwwsi.19.7
- Views 109
- Downloads 0
Porównanie wydajności algorytmu k-means zaimplementowanego w języku X10 i środowisku C++/MPI
W pracy opisano algorytm k-średnich oraz sposób jego implementacji w języku X10. Dokonano porównania tego rozwiązania z implementacją w języku C++11 z wykorzystaniem standardu MPI. Stwierdzono, że implementacja w języku...
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...
Analiza metod e-learningowych stosowanych w kształceniu osób dorosłych
W opracowaniu scharakteryzowano współcześnie stosowane metody, techniki i narzędzia e-learningu, które mogą zostać wykorzystane do celów projektu „Efektywni 50+” realizowanego przez WWSI. Zaprezentowano zarys historii zd...
Jak sprawnie zrealizować badanie efektów szkolenia zdalnego?
W artykule opisano realizację oceny efektów szkolenia w pięciu krokach. Tekst traktuje przede wszystkim o korzyściach płynących z badania efektów szkolenia zdalnego. Nie zaniedbuje przy tym zasad andragogiki i nauczania...
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...