Algoritam računalne inteligencije za rješavanje problema putujućeg lopova

završni rad

• Naslov (engleski): Computational Intelligence Algorithm for Traveling Thief Problem
• Autor: Božo Kvesić
• Mentor: Nikola Ivković (mentor); MBZ: 306480
• Član povjerenstva: Ivan Magdalenić (član povjerenstva); MBZ: 244501
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet organizacije i informatike; (Katedra za informatičke tehnologije i računarstvo); Varaždin
• Datum i država obrane: 2020-09-21, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: DRUŠTVENE ZNANOSTI; Informacijske i komunikacijske znanosti; Organizacija i informatika

Sažetak

U ovom radu je implementiran algoritam računalne inteligencije koji rješava problem putujućeg lopova. Algoritam je implementiran u jeziku C++, u okruženju Microsoft Visual Studio 2019. Korišten je mravlji algoritam, preciznije MMAS algoritam na kojemu su kasnije provođeni eksperimenti na primjercima problema s 51, 76, 100 i 280 gradova te od 1 do 5 predmeta u svakom pojedinom gradu osim početnom. Cilj istraživanja bio je postići napredak algoritma kroz vrijeme, odnosno njegovo učenje i konstrukciju optimalnog rješenja. Problem putujućeg lopova je noviji višekomponentni problem koji je približan stvarnim problemima s kojima se tvrtke danas susreću. Problem je kombinacija problema trgovačkog putnika (TSP) i problema naprtnjače (KP) koji su veoma poznati u svijetu optimizacije. Cilj rada je rješavanje NP-teškog problema koji standardnim matematičkim metodama nije rješiv u realnom vremenu, a korištenjem mravljeg algoritma ćemo dobiti približno optimalno rješenje koje će biti prihvatljivo. Sergey Polyakovskiy predstavlja prve primjerke problema putujućeg lopova. Algoritam na kojemu su se vršili eksperimenti je testiran s 20 mrava i 1000 iteracija. Nakon provedenih eksperimenata došao sam do zaključaka kako MMAS algoritam relativno dobro napreduje kroz iteracije te konstruira bolja rješenja kako vrijeme prolazi. Lokalna optimizacija uvelike doprinosi napretku algoritma na način da u početku pomaže algoritmu konstruirati bolja rješenja kako bi u kasnijim iteracijama algoritam bolje učio. Loša karakteristika lokalne optimizacije je usporavanje izvođenja samog algoritma, ali s obzirom na dobivena kvalitetnija rješenja onda možemo zanemariti tu činjenicu.

• Ključne riječi: optimizacija; računalna inteligencija; NP-težak problem; programiranje, algoritam
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:211:902336
• Studijski program: Naziv: Informacijski sustavi; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/prvostupnica (baccalaureus/baccalaurea) informatike (univ.bacc.inf.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2021-05-13 13:18:44