Algoritam GGA
Autor: Ante Modrić
Poveznice: završni rad
Genetski algoritmi
Genetski algoritmi (GA) su skupina optimizacijskih metoda gdje se do rješenja dolazi pomoću imitiranja prirodne evolucije nad populacijom kodiranih rješenja (kromosomi). Evolucija se imitira postupcima selekcije, križanja (reprodukcije) i mutacije. Selekcijom, u kojoj se prednost daje boljim jedinkama (kodiranim rješenjima), se biraju jedinke od kojih će se križanjem i mutacijom kromosoma generirati nove jedinke.
Problem rezanja se može interpretirati kao problem grupiranja elemenata skupa (zahtjevi za rezanjem) u podskupove (komade raspoloživog materijala od kojih će se rezati). Zbog toga za rješavanje zadanog problema rezanja korišten je grupirajući genetski algoritam.
Grupirajući genetski algoritam (GGA) se razlikuje od tradicionalnih GA, u kojima svaki gen kromosoma predstavlja jedan element i njegova pozicija ili poredak u odnosu na ostale gene u kromosomu je bitan, po tome što u GGA gen predstavlja grupu elemenata, te njegova pozicija ili poredak u odnosu na druge gene u kromosomu nije bitan. Također, za razliku od tradicionalnih GA, gdje se nove jedinke generiraju kombinacijom križanja i mutacije, kod GGA se jedinke generiraju ili križanjem ili mutacijom.
Grupiranje
Problem prilagođavanja Falkenauerovog GGA (konstruiranog za rješavanje problema pakiranja) za rješavanje problema rezanja gdje se očekuje više različitih duljina raspoloživog materijala se svodi na problem pridruživanja duljine komada materijala od kojeg se grupa elemenata rezati svakoj grupi materijala [3]. Taj problem je riješen proširivanjem zapisa grupe duljinom prikladnog komada materijala.
Generiranje početne populacije
Generiranje početne populacije je izvedeno slučajnim odabirom komada raspoloživog materijala, te zatim pridruživanjem u pripadnu grupu neostvarene zahtjeve za rezanjem korištenjem First-Fit algoritma (FF)[8]. Takav način generiranja daje rješenja koja su relativno dobra (tj. nisu jako loša) a i dalje su međusobno vrlo različita.
Selekcija
Za selekciju se koristi proporcionalna selekcija, što znači da je vjerojatnost da neka jedinka bude odabrana za reprodukciju jednaka njenoj relativnoj dobroti u odnosu na cijelu populaciju. Selekcijom se odabiru dvije jedinke roditelja od kojih će se generirati dvije jedinke nove generacije.
Križanje
Za križanje se koristi GGA operator križanja [7] koji je modifikacija standardnog križanja sa 2 točke prekida za GGA kromosome. Nova jedinka se generira iz odabranih roditelja na način da se iz prvog roditelja kopira dio grupa, zatim se iz drugog roditelja kopiraju sve grupe kojima se ne prelazi broj zahtjeva za rezanjem ni broj raspoloživih materijala, te se na kraju od preostalih nesvrstanih zahtjeva za rezanjem generiraju nove grupe koristeći algoritam FF.
Mutacija
Za mutaciju se koristi GGA operator mutacije [7] koji funkcionira na način da se određeni broj grupa obriše te se zatim iz oslobođenih elemenata generiraju nove grupe koristeći algoritam FF.
Funkcija dobrote
Za funkciju cijene se koristi sljedeća formula [3]:
gdje je:
C = funkcija "cijene"
wi = otpad nakon rezanja i-tog komada materijala
li = duljina i-tog komada materijala
ws = ukupan broj neiskorištenih komada materijala (komadi materijala kojima je ostatak veći od maksimalnog dopuštenog)
n = ukupan broj korištenih komada materijala
