Publikace detail

Solving Travelling salesman problem using Harmony search algorithm and other metaheuristics

Autoři: Míča Ondřej

Rok: 2016

Druh publikace: článek ve sborníku

Název zdroje: Recenzovaný sborník příspěvků vědecké interdisciplinární mezinárodní vědecké konference doktorandů a odborných asistentů QUAERE 2016

Název nakladatele: MAGNANIMITAS

Místo vydání: Hradec Králové

Strana od-do: 640-648

Tituly:

Jazyk	Název	Abstrakt	Klíčová slova
cze	Možnosti řešení úlohy obchodního cestujícího metodou Harmony search	Úloha obchodního cestujícího náleží mezi základní úlohy operačního výzkumu. Jedná se o NP-těžký problém. Počet možných řešení úlohy je velmi vysoký - roste s faktoriálem počtu uzlů v grafu. Proto, i s dnešními výkonnými počítači, zabere řešení úlohy obchodního cestujícího exaktními metodami velké množství času. Z tohoto důvodu se úloha obchodního cestujícího zpravidla řeší heuristickými (či metaheuristickými) metodami, které jsou schopné získat dostatečně kvalitní řešení v reálném čase. Tento článek je zaměřen na jednu z nejnovějších metaheuristických metod - na metodu Harmony search, která je inspirovaná improvizací hudebníků. článek se zabývá několika různými instancemi úlohy obchodního cestujícího, jejichž řešení metodou Harmony search porovnává s řešeními získanými jinými metaheuristickými metodami a s nejlepším dosud nalezeným řešením.	Úloha obchodního cestujícího; Metaheuristiky; Harmony search; optimalizace
eng	Solving Travelling salesman problem using Harmony search algorithm and other metaheuristics	Travelling salesman problem belongs in basic problems of operations research. It is a NP-hard problem. The number of possible solutions of this problem is very high – it increases with the factorial of the number of the nodes at the graph. So even with nowadays computers it takes very large amount of time to solve TSP with exact methods. Therefore TSP is now usually solved with a heuristic (or metaheuristic) techniques, which provides a satisfactory solution in real-time. This paper is focused on one novel metaheuristic method – Harmony Search, which is inspired by the improvisation process of musicians. Several instances of travelling salesman problem are solved in this paper with this method and gained results are compared with the optimal solution of each instance and with results computed by other metaheuristic methods.	Travelling salesman problem; Metaheuristics; Harmony search; Optimization

Vyhledávání

Přihlášení pro studenty

Přihlášení pro zaměstnance

Publikace detail

Katedry

Pracoviště

Jak nás najdete?

Služby

Často hledáte