Název:
Problém obchodního cestujícího
Překlad názvu:
Traveling Salesman Problem
Autoři:
Šůstek, Martin ; Snášelová, Petra (oponent) ; Zbořil, František (vedoucí práce) Typ dokumentu: Bakalářské práce
Rok:
2015
Jazyk:
cze
Nakladatel: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstrakt: [cze][eng]
Práce se zaměřuje na úpravu známých postupů ACO a GA s ohledem na zvyšování efektivity nalézaných řešení. Jsou zde prezentovány dva nové přístupy pro řešení TSP. Pomocí jednoho z nich lze také vytvořit počáteční populaci pro GA. Je uveden konkrétní návrh programu a v příloze pak i jeho implementace v jazyce Java. Aby se zlepšila efektivita řešení, jsou navržené a implementované lokální optimalizace. Po uplynutí předem stanoveného strojového času jsou mezi sebou porovnány minimální vzdálenosti dosažené zvolenými metodami. Experimenty jsou provedeny na sadách s různými počty míst, konkrétně od 101 až po 3891.
This thesis is focused on modification of known principles ACO and GA to increase their performance. Thesis includes two new principles to solve TSP. One of them can be used as an initial population generator. The appendix contains the implementation of the application in Java. The description of this application is also part of the thesis. One part is devoted to optimization in order to make methods more efficient and produce shorter paths. In the end of the thesis are described experiments and their results with different number of places from 101 up to 3891.
Klíčová slova:
ACO; Deterministické řešení pro TSP; GA; Genetický algoritmus; Optimalizace GA; Optimalizace mravenčí kolonií; Počáteční populace pro GA; Problém obchodního cestujícího; TSP; ACO; Ant Colony Optimization; Deterministic solution for TSP; GA; GA Optimization; Genetic Algorithm; Initial Population for GA; Travelling Salesman Problem; TSP
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/52479