Pregled hevristik za problem trgovskega potnikaGABERC ARTENJAK, JAKOB (Avtor) Robič, Borut (Mentor) hevristikaProblem trgovskega potnikasimetrični Problem trgovskega potnikaLokalno iskanjek-optLin-KerninghanSimulirano ohlajanjeKolonija mraveljOptimizacija z roji delcevOponašanje volkovProblem trgovskega potnika je iskanje najkrajše poti med vsemi mesti, kjer obiščemo vsako mesto natanko enkrat in se vrnemo nazaj na začetno mesto. Na problem lahko gledamo kot na iskanje najcenejšega cikla v grafu, ki obišče vse točke natanko enkrat. Pridobivanje optimalne rešitve problema trgovskega potnika je praktično neuporabno zaradi časovne zahtevnosti problema. Hevristični algoritmi so dobra alternativa optimalnemu reševanju problema, saj pridobijo rešitev v praktično izvedljivem času, a izgubijo jamstvo optimalne rešitve. Uvod diplomske naloge vsebuje osnovni opis problema trgovskega potnika. Temu sledijo primeri praktične uporabe problema, natančnejši opis problema, opredelitev hevristik in opis testnega okolja. Glavni del naloge vsebuje šest hevrističnih algoritmov, ki smo jih implementirali in jih testirali. Izbrali smo algoritem Lokalnega iskanja z operacijo k-opt, Lin-Kernighanov algoritem, algoritem Simuliranega ohlajanja, algoritem Kolonije mravelj, algoritem Optimizacije z roji delcev in algoritem Oponašanja volkov. Končni del naloge vsebuje primerjavo eksperimentalnih rezultatov in komentar nad uporabljeno metodologijo za primerjavo algoritmov.20202020-09-10 15:05:13Diplomsko delo/naloga119680VisID: 26661COBISS_ID: 30748419sl