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

undergraduate thesis

• Title (english): Computational Intelligence Algorithm for Traveling Thief Problem
• Author: Božo Kvesić
• Mentor: Nikola Ivković (mentor); MBZ: 306480
• Committee member: Ivan Magdalenić (član povjerenstva); MBZ: 244501
• Granter: University of Zagreb; Faculty of Organization and Informatics; (Department of Computing and Technology); Varaždin
• Defense date and country: 2020-09-21, Croatia
• Scientific / art field, discipline and subdiscipline: SOCIAL SCIENCES; Information and Communication Sciences; Organization and Informatics

Abstract

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.

• Keywords: optimizacija; računalna inteligencija; NP-težak problem; programiranje, algoritam
• Language: croatian
• URN:NBN: urn:nbn:hr:211:902336
• Study programme: Title: Information Systems; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/prvostupnica (baccalaureus/baccalaurea) informatike (sveučilišni/a prvostupnik/prvostupnica (baccalaureus/baccalaurea) informatike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2021-05-13 13:18:44