Název:
Evoluční řešení problému cestujícího zloděje
Překlad názvu:
Evolutionary Approach to the Traveling Thief Problem
Autoři:
Fodor, Dávid ; Hurta, Martin (oponent) ; Sekanina, Lukáš (vedoucí práce) Typ dokumentu: Bakalářské práce
Rok:
2023
Jazyk:
slo
Nakladatel: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstrakt: [slo][eng]
Táto práca predstavuje návrh evolučného algoritmu na riešenie problému cestujúceho zlodeja (TTP), ktorý sa skladá z dvoch vzájomne prepojených podproblémov, problému cestujúceho obchodníka (TSP) a problému batohu (KP). Návrh obsahuje viacero variácií navrhovaného algoritmu. Je založený na genetickom algoritme, evolučnom algoritme (1+1) a ich kombinácii. Algoritmus je implementovaný a testovaný na oficiálnych testovacích inštanciách TTP. Najlepšia navrhnutá varianta evolučného algoritmu bola porovnaná s náhodným vyhľadávaním a najlepšími verejne nájdenými riešeniami pre testované inštancie.
This thesis presents design of an evolutionary algorithm for solving the Traveling thief problem (TTP), which is composed of two interconnected subproblems, the traveling salesperson problem (TSP) and the knapsack problem (KP). The proposed algorithm contains multiple variations of evolutionary algorithm. It is based on the genetic algorithm, the evolutionary algorithm (1+1), and their combination. The algorithm is implemented and tested on official TTP benchmark instances. The best variation of the proposed evolutionary algorithm is chosen and compared with random search and the best publicly available solutions for tested problem instances.
Klíčová slova:
evolutionary algorithms; genetic algorithm; optimization; traveling thief problem
Instituce: Vysoké učení technické v Brně
(web)
Informace o dostupnosti dokumentu:
Plný text je dostupný v Digitální knihovně VUT. Původní záznam: http://hdl.handle.net/11012/211082