Title Evolucijska hiperheuristika za rješavanje problema izrade krojnih slika Title (english) Evolutionary hyper-heuristic for solving the strip-packing problem Author Daniel Domović Mentor Marin Golub (mentor)Mentor Tomislav Rolich (komentor)Committee member Marin Golub (član povjerenstva)Committee member Tomislav Rolich (član povjerenstva)Granter University of Zagreb Defense date and country 2018, Croatia Scientific / art field, TECHNICAL SCIENCES Universal decimal classificationUDC ) 677 - Textile industry Abstract 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.
Abstract (english) Within this doctoral dissertation, the problem of strip-packing from the garment industry was solved. The strip-packing problem is a combinatorial optimization problem in which a set of cutting parts must be optimally fitted into the material of a rectangular shape (i.e. a marker), so that the waste of material is minimized, i.e. the utilization of material is optimal. Based on the possibilities of improvement of the existing methods for solving the strip-packing problem, the aim of the research was to create a flexible algorithm for solving the strip-packing problem with material and cutting parts of arbitrary shape and the possibility of expanding the algorithm with additional features, such as determining the low-quality areas of material. To solve the problem three heuristics have been implemented: Grid, Grid-BLP and Grid-Shaking, five memetic algorithms and evolutionary hyperheuristics. The Grid heuristic places the cutting parts on a marker by discretizing it with a mesh of points. Heuristics Grid-BLP and Grid-Shaking have the ability to compact the marker obtained with Grid heuristics and the possibility of escaping from a local optimum. The heuristics are hybridized with the evolutionary algorithm. For this purpose, a representation of an individual in evolutionary algorithm has been developed that consists of a permutation part, rotation part, dynamic mesh density parameter, and a parameter for selecting a heuristics (i.e. hyperheuristic). Since it is sometimes difficult to determine which heuristic will obtain the best results for a data set, evolutionary hyperheuristics has been developed. The choice of heuristics is performed by an evolutionary algorithm based on the information in the structure of each individual. The algorithm is consisted of features to adjust the dynamic mesh density and to determine the placement order of identical groups of cutting parts All Equal First (AEF). It has been experimentally proven that designed features such as the fitting order All Equal First and dynamic mesh density, as well as the application of evolutionary hyperheuristics, favourably influence the efficiency of a marker. Compared to the results from literature and to those obtained by commercial programs, implemented algorithms obtain competitive results. The original scientific contributions of this doctoral thesis are: evolutionary hyperheuristics that chooses between several heuristics that solve the strip-packing problem and optimizes the parameters of the chosen heuristic, a memetic algorithm for solving the strip-packing problem and a representation of an individual of evolutionary algorithm that includes permutation, rotation, hyperheuristic selection of heuristic and parameters of heuristics.
Keywords
evolucijski algoritam
hiperheuristika
izrada krojnih slika
problem pakiranja
Keywords (english)
evolutionary algorithm
hyper-heuristics
marker making
strip-packing problem
Language croatian URN:NBN urn:nbn:hr:168:873774 Study programme Title: Electrical Engineering and Computing Type of resource Text Extent 202 str. ; 30 cm. File origin Born digital Access conditions Closed access Terms of use Created on 2019-04-03 13:40:56
