Metoda harmony search při řešení úlohy obchodního cestujícího a její porovnání s dalšími metaheuristickými metodami

Abstract

Úloha obchodního cestujícího je velmi známý a populární optimalizační problém. Protože se jedná o NP-těžkou úlohu, počet přípustných řešení je velmi vysoký – roste s faktoriálem počtu vrcholů v dopravní síti. Proto ani se soudobou výpočetní technikou není možné rozsáhlé úlohy obchodního cestujícího řešit exaktními metodami. V tomto příspěvku bude představeno pět metaheuristických metod: tabu search, simulované žíhání, genetický algoritmus, metoda mravenčí kolonie a metoda harmony search. Tyto algoritmy budou mezi sebou srovnány, když jako porovnávací měřítko bude použita odchylka mezi hodnotou účelové funkce nejlepšího vypočteného řešení a řešení optimálního.