Naslov
Modeliranje, analiza i poboljšanje algoritama optimizacije kolonijom mrava
(Modeling, Analysis and Improvement of Ant Colony Optimization Algorithms)

Autori
Ivković, Nikola

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, doktorska disertacija

Fakultet
FAKULTET ELEKTROTEHNIKE I RAČUNARSTVA

Mjesto
Zagreb

Datum
03.04

Godina
2014

Stranica
251

Mentor
Golub, Marin

Ključne riječi
optimizacija kolonijom mrava; strategija ažuriranja feromonskih tragova; vjerojatnost konstrukcije rješenja; stohastički optimizacijski algoritam; funkcijska ekvivalencija algoritama; problem trgovačkog putnika; problem kvadratnog pridruživanja; optimizacija; učinkovitost algoritma; kvantil
(ant colony optimization; pheromone trails update strategy; solution construction probability; stochastic optimization algorithm; algorithmic functional equivalence; traveling salesman problem; quadratic assignment problem; optimization; algorithmic efficiency; quantile)

Sažetak
Optimizacija kolonijom mrava (ACO) je metaheuristika koja se uspješno primjenjuje za rješavanje teških optimizacijskih problema, osobito kombinatoričkih optimizacijskih problema koji pripadaju klasi NP-teških problema. Ciljevi ovoga rada su proširiti spoznaje o načinu djelovanja algoritma ACO i istražiti njegove zakonitosti, omogućiti poboljšanja uvođenjem novih strategija te razviti novi algoritam ACO za probleme kombinatoričke optimizacije. U radu su sistematizirani i analizirani načini mjerenja učinkovitosti stohastičkih optimizacijskih algoritama. Predloženo je i argumentirano korištenje kvantila umjesto uobičajene prakse korištenja aritmetičke sredine za iskazivanje dobrote algoritma. Predložene su poopćene strategije odabira rješenja za ažuriranje feromonskih tragova u algoritmima optimizacije kolonijom mrava. Na ispitnim je instancama problema, uz pomoć neparametarskih statističkih testova, eksperimentalno dokazano da predložene strategije mogu poboljšati svojstva algoritama ACO. Definirane su i analizirane pojave grupiranja i separacije feromonskih tragova na temelju čega je razvijen model za određivanje vjerojatnosti konstrukcije rješenja. Primjenom modela su izvedeni izrazi za vjerojatnost konstrukcije rješenja za problem trgovačkog putnika, nesimetričan problem trgovačkog putnika i problem kvadratnog pridruživanja za algoritme MAKS MIN sustav mrava i sustav kolonije mrava. Predložen je algoritam ACO za koji se umjesto isparavanja feromonskih tragova povremeno provodi stezanje tragova, a koji je funkcionalno ekvivalentan algoritmu MAKS MIN sustavu mrava do iteracije algoritma u kojoj feromonski trag izlazi izvan zadanih feromonskih granica. Zbog drugačijeg postupka ažuriranja feromonskih tragova predloženi algoritam ima nešto manju računsku složenost. Algoritam je uporabljen za rješavanje problema izrade oligonukleotidnih mikropostroja, za koje je pronašao bolja rješenja od do tada poznatih najboljih rješenja.

Izvorni jezik
Hrvatski

Znanstvena područja
Računarstvo

POVEZANOST RADA