Evolucijska hiperheuristika za rješavanje problema izrade krojnih slika : doktorski rad - Domović, Daniel (D. Domović ; Fakultet elektrotehnike i računarstva, 2018)
U okviru ove doktorske disertacije rješavan je problem izrade krojnih slika iz odjevne industrije. Problem izrade krojnih slika kombinatorički je optimizacijski problem u kojem se skup krojnih dijelova mora optimalno uklopiti u materijal pravokutnog oblika tako da je međukrojni gubitak prilikom iskrojavanja najmanji, odnosno iskorištenost krojne slike najveća. S obzirom na mogućnosti unapređenja postojećih metoda, cilj ovog istraživanja bio je načiniti dovoljno općenit i prilagodljiv algoritam za rješavanje problema izrade krojnih slika koje se mogu izraditi pomoću materijala proizvoljnog oblika (npr. pravokutni oblik, nepravilni oblik kože). Pritom mora postojati podrška za uklapanje neaproksimiranih krojnih dijelova proizvoljnog oblika. Algoritam se mora lako moći proširiti kako bi zadovoljio i dodatne korisničke potrebe poput mogućnosti određivanja područja kvalitete materijala. Za rješavanje problema osmišljene su i programski ostvarene tri heuristike: Grid, Grid-BLP i Grid-Shaking. Grid heuristika uklapa krojne dijelove u krojnu sliku privremeno ju diskretizirajući mrežom točaka. Heuristike Grid-BLP i Grid-Shaking imaju mogućnost dodatnog zbijanja krojne slike dobivene Grid heuristikom i mogućnost izbacivanja krojnog dijela iz lokalnog optimuma. Heuristike su hibridizirane s evolucijskim algoritmom. U tu svrhu osmišljen je prikaz jedinke evolucijskog algoritma koji se sastoji od permutacijskog i rotacijskog dijela, parametra za određivanje dinamičke gustoće mreže i parametra za izbor heuristike. Budući da je ponekad teško utvrditi koja će heuristika dati najbolje rezultate za skup podataka, razvijena je evolucijska hiperheuristika. Izbor heuristike obavlja evolucijski algoritam uz pomoć parametra za izbor u strukturi svake jedinke u populaciji evolucijskog algoritma. U algoritme je ugrađeno svojstvo prilagođavanja dinamičke gustoće mreže i određivanja redoslijeda uklapanja identičnih skupina krojnih dijelova – AEF (engl. All Equal First). Eksperimentalni rezultati pokazali su kako hiperheuristika najčešće izabire najprimjereniju heurističku metodu za svaki skup ispitnih podataka. Dokazano je da svojstva algoritama poput redoslijeda uklapanja krojnih dijelova AEF i dinamičke gustoće mreže povoljno utječu na iskorištenost krojnih slika. U usporedbi s rezultatima iz literature, kao i s rezultatima koje daju komercijalni programi, programski ostvarenim algoritmima dobiveni su kompetitivni rezultati. Izvorni znanstveni doprinosi ovog doktorskog rada su: evolucijska hiperheuristika koja omogućuje: izbor između više heurističkih algoritama koji rješavaju problem dvodimenzionalnog pakiranja i optimiranje parametara izabranog heurističkog algoritma, memetički algoritam za rješavanje problema dvodimenzionalnog pakiranja i prikaz jedinke evolucijskog algoritma koji uključuje permutaciju, rotaciju, izbor heurističke metode i vrijednost parametra heurističke metode. Ključne riječi: evolucijski algoritam, hiperheuristika, izrada krojnih slika, problem pakiranja