Modeliranje, analiza i poboljšanje algoritama optimizacije kolonijom mrava : : doktorski rad - Ivković, Nikola 1979 (N. Ivković ; Fakultet elektrotehnike i računarstva, 2014)
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. -