Optimizacija kolonijom mrava za kombinatorne probleme

završni rad

• Naslov (engleski): Ant Colony Optimization for Combinatorial Problems
• Autor: Stjepan Janković
• Mentor: Nikola Ivković (mentor); MBZ: 306480
• Član povjerenstva: Luka Milić (član povjerenstva); MBZ: 343380
• 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: 2021-09-28, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: DRUŠTVENE ZNANOSTI; Informacijske i komunikacijske znanosti; Organizacija i informatika

Sažetak

Tema ovog rada je optimizacija kolonijom mrava (eng. Ant Colony Optimization – ACO) i njezina primjena na kombinatorne probleme. Na temelju općih smjernica napravljen je algoritam ACO za rješavanje problema paralelne dostave dronovima i trgovačkog putnika (eng. Parallel Drone Scheduling Traveling Salesman Problem – PDSTSP)
Cilj rada je saznati kakav efekt imaju različite instance, broj iteracija i mrava na ponašanje algoritma optimizacije kolonijom mrava. Rad algoritma testiran je na primjercima PDSTSP-a veličine od 20 do 100 lokacija koje su generirane za potrebe ovog istraživanja. Algoritam je implementiran u jeziku C#, a za razvoj je korišten Visual Studio 2019. Rezultati eksperimenata prikazani su tablično i grafički. Razvijen algoritam pokazao se primjerenim za rješavanje PDSTP-a. Programsko rješenje unutar kojeg je zapisan algoritam će biti objašnjeno u odjeljku 4.
Unutar eksperimenata možemo vidjeti razliku između povećanja broja mrava i povećavanja broja iteracija, njihov efekt na dobiveno rješenje i rad algoritma. Možemo vidjeti da se povećava trajanje algoritma unutar programskog rješenja, no uz to se poboljšava i rezultat. Uz sve veće povećavanje mrava i iteracija trajanje algoritma postaje sve veće, ali se dobitak u poboljšanom rezultatu sve više smanjuje.

• Ključne riječi: optimizacija; algoritam; inteligencija rojeva; računalna inteligencija
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:211:420382
• 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-10-04 04:08:37