ZAVRŠNI RAD br.
1225
Rješavanje problema krojenja
uz pomoć
genetskog algoritma
Domagoj Kusalić
JMBAG: 0036440699
SADRŽAJ
1.
Uvod
2.
Problem krojenja
2.1. Jednodimenzijski problem
krojenja
2.2. Višedimenzijski problem
krojenja
3.
Genetski algoritam
4.
Problem krojenja
4.1. Problem krojenja u dvije
dimenzije
4.1.1. Zapis jedinke
4.1.2. Dobrota
4.1.3. Mutacija
4.1.4. Križanje
5.
Ostvareno programsko rješenje
5.1. Opis programskog sustava
5.2. Upute za korištenje
5.3. Analiza
6. Zaključak
Literatura
1. Uvod
Cilj rada je definirati jednodimenzijski i višedimenzijski problem krojenja, te rješiti dvodimenzijski problem krojenja genetskim algoritmom. Potrebno je osmisliti genetski algoritam koji rješava dvodimenzijski problem krojenja, opisati ostvareni programski sustav, te analizirati rezultate koje daje ostvareni programski sustav.
Nakon uvoda slijedi opis problema krojenja. Opisuje se jednodimenzijski problem krojenja, te se navode primjeri problema i razni načini definiranja problema. Zatim se opisuje višedimenzijski problem krojenja sa naglaskom na dvodimenzijski problem. U trećem poglavlju se ukratko opisuje genetski algoritam. U četvrtom poglavlju nalazi se opis genetskog algoritam, slijedi definiranje zapisa jedinke, funkcije dobrote, te genetskih operatora koji se koriste za rješavanje dvodimenzijskog problema krojenja. U petom poglavlju razmatra se ostvareno programsko rješenje dvodimenzijskog problema krojenja. Prvo se opisuje dizajn programskog sustava, korišteni genetski algoritam i dodatne funkcionalnosti programskog sustava. Slijede upute za korištenje koje opisuje grafičko korisničko sučelje i način zapisa problema krojenja kojeg se želi riješiti. Na kraju petog poglavlja nalazi se analiza izvođenja programa. U analizi izvođenja razmatraju se rješenja koje genetski algoritam stvara, način podešavanja i smisao pojedinog parametra genetskog algoritma, te brzina izvođenja algoritma. Šesto poglavlja je zaključak rada.
2. Problem krojenja
2.1. Jednodimenzijski problem krojenja
Jednodimenzijski problem krojenja (raspoređivanja), poznat i kao problem rezanja, spada u kategoriju NP-potpunih problema [6]. NP-potpuni problemi se mogu rješiti u vremenskoj složenosti koja polinomijalno ovisi o veličini unosa, što je za veće unose procesorski vrlo zahtjevno.
Jednodimenzijski problem raspoređivanja (engl. cutting-stock problem) je optimizacijski problem, točnije, problem linearnog programiranja [7]. Problem pronalazi mnoge primjene u industriji.
- Jedna od primjena javlja se u industriji papira. Papir se stvara u velikim rolama određene širine. Svaki naručitelj papira naručuje papir neke specifične širine, pa je potrebno postojeće role papira izrezati na određenu širinu. Na koji način rezati role papira tako da bude što manje otpadaka?
- Sličan problem susreću i proizvođači roletni za prozore. Naručitelji roletni žele roletne određene širine (roletne se sastoje od mnoštva jednako širokih drvenih letvica). Na koji način treba rezati letvice za roletne, tako da nastane što manje otpadnog materijala?
- Sa sličnim problemom susreću se proizvođači električnih kablova ili željeznih cijevi.
Problem se može detaljnije definirati na mnoge načine:
- Proizvođač ima mnoštvo rola papira različite širine, te treba izrezati što više rola zadanih širina.
- Proizvođač ima mnoštvo rola papira različite širine, te treba izrezati fiksan broj rola pojedine širine.
- Proizvođač ima mnoštvo rola papira različite širine, te treba izrezati što više paketa rola papira, pri tome se pojedini paket sastoji od određenog broj rola zadanih širina.
- Proizvođač ima neograničen broj rola papira iste širine, te treba izrezati određen broj rola papira zadane širine.
Zadnja navedena formulacija problema je vrlo česta. Slijedi primjer za navedenu formulaciju:
Na raspolaganju je neograničena količina velikih rola papira širine 5600mm. Potrebno je izrezati 13 narudžbi prikazanih u tablici 2.1. Za navedeni primjer postoji ukupno 308 načina rezanja. Optimalan način rezanja (rješenje) prikazan je na slici 2.1. Optimalno rješenje koristi 73 velike role širine 5600mm, te stvara 0.401% otpadnog materijala.[7]
2.2. Višedimenzijski problem krojenja
Višedimenzijski problemi krojenja (raspoređivanja) su, kao i jednodimenzijski, NP-potpuni problemi [5]. Od višedimenzijskih problema krojenja najčešće se u industrijskoj proizvodnji pojavljuje dvodimenzijski problem raspoređivanja. U dvodimenzijskom problemu raspoređivanja potrebno je iz dane površine "izrezati" zadane 2D oblike, tako da se površina što bolje iskoristi, tj. ostane što manje otpadnog materijala.
- Problem se često susreće u tekstilnoj industriji. Cilj je što bolje iskoristiti platno kako bi se iz njega izrezalo što više željenih oblika, te kako bi ostalo što manje neiskorištenog materijala.
- Sličan problem se javlja pri proizvodnji namještaja i obradi stakla.
Problem se može detaljnije definirati na mnoge načine:
- Potrebno je minimizirati otpad. Otpad(višak) je razlika zauzete kvadratne površine i ukupne površine izrezanih oblika.
- Potrebno je izrezat što više oblika iz dane površine.
- Potrebno je izrezati svaki zadani oblik jednom, te pritom zauzeti što manji dio površine.
U okviru ovog rada ostvareno je programsko rješenje koje uspješno rješava dvodimenzijski problem krojenja pri kojemu je potrebno svaki oblik izrezati samo jedno.
Od višedimenzijskih problema raspoređivanja u industriji se pojavljuje još i trodimenzijski problem raspoređivanja u obliku problema pakiranja. Problem pakiranja se može definirati na sljedeće načine:
- Rasporedi objekte u kontejner tako da zauzmu što manje mjesta.
- Rasporedi zadane objekte u što manje kontejnera.
- Rasporedi što više istih objekata u dani kontejner.
3. Genetski algoritam
Kroz milijune godina različite vrste se razvijaju kako bi što bolje preživjele u okolišu koji ih okružuje. Razvijene prilagodbe se prenose unutar vrste kroz generacije, te se proces prilagodbe nastavlja. Prilagodbe su većinom takve da omogućuju jedinki bolje šanse za preživljavanje u svom okolišu. Promjene koje su štetne postepeno iščezavaju, dok promjene koje su korisne imaju veće šanse za očuvanjem jer osiguravaju preživljavanje jedinke koja ih posjeduje. Na taj način priroda uspijeva razviti sve naprednije organizme koji su sve sposobniji preživljavanju u okolišu koji ih okružuje.
Inspirirana procesom evolucije, znanost je razvili računalnu paradigmu zvanu evolucijsko računarstvo (engl. evolutionary computation) koja oponašanjem prirodnih evolucijskih procesa pokušava riješiti razne procesorski zahtjevne računalne probleme. U području umjetne inteligencije, evolucijski algoritmi predstavljaju podskup evolucijskog računarstva [9]. Evolucijski algoritmi koriste neke mehanizme inspirirane biološkom evolucijom: selekcija, reprodukcija, mutacija i rekombinacija, kako bi pronašli što bolje rješenje određenog problema. Potencijalna rješenja optimizacijskog problema kojeg evolucijski algoritam pokušava riješiti igraju ulogu "jedinke" u "populaciji". Pritom se potencijalna rješenje (jedinke) međusobno kombiniraju i razvijaju na sličan način kao što to u prirodi čine biološke jedinke neke vrste.
Evolucijski algoritmi često dobro aproksimiraju rješenja bilo kojeg problema jer nemaju ugrađene pretpostavke o izgledu domene pretrage nad kojim se provode. To opće svojstvo čini evolucijske algoritme korisnim u raznovrsnim područjima poput: umjetnosti, ekonomije, marketinga, robotike, sociologije, fizike, politike i kemije.[8] Bitne komponente evolucijskih algoritama čine: genetski algoritmi, genetsko programiranje i evolucijske strategije.[3]
Najpoznatiji primjer evolucijskih algoritama predstavlja genetski algoritam.
Genetski algoritmi[1] su klasa računalnih metoda koje oponašaju principe prirodne evolucije za potrebe pretrage i optimizacije. Genetski algoritmi koriste dvije bitne karakteristike prirodne evolucije:
- prenošenje informacija iz jedne generacije u drugu (nasljeđivanje) i
- nadmetanje za preživljavanje (preživljavanje najsposobnijih).
Glavne prednosti genetskih algoritama, koje ih čine podobnima za rješavanje problema iz stvarnog života su:
- Prilagodljivi su.
- Učinkoviti su u rješavanju kompleksnih problema u kojima je glavni cilj brzo naći dobro, no ne nužno i optimalno rješenje.
Posebno su podobni za aplikacije koje zahtijevaju pretragu i optimizaciju kada je prostor pretrage izrazito velik i kompleksan, te nema potrebe naći baš najbolje rješenje. Najviše se primjenjuju za razlikovanje uzoraka, procesiranje slika, prepoznavanje scena, dizajniranje neuronskih mreža, problem rasporeda, planiranje puta, optimizaciju problema trgovačkog putnika, bojanje grafova, numeričku optimizaciju, te mnoge druge probleme.
Genetski algoritmi (kraće GA) modeliraju principe prirodnog genetskog sustava, pritom genetski materijal pojedine jedinke (potencijalnog rješenja) biva zapisan u strukturu zvanu "kromosom". GA koriste određeno znanje o prirodi problema kako bi oblikovali funkciju dobrote, pomoću koje se pretraga usmjeruje u više obećavajuća područja. Svaka jedinka (jedinku čini kromosom) ima pridruženu vrijednost funkcije dobrote koja ocjenjuje koliko je jedinka dobra u odnosu na rješenje koje predstavlja. Grupa jedinki se naziva "populacija". Različiti biološki inspirirani operatori poput selekcije, križanja i mutacije bivaju primijenjeni na kromosome iz populacije, kako bi stvorili potencijalno bolje rješenje danog problema.
GA se provodi sljedećim koracima:[3]
- Inicijalizira se populacija tako što se stvori određen broj jedinki sa slučajno popunjenim kromosomima (jedinke predstavljaju slučajno rješenje danog problema).
- Procjenjuje se dobrota pojedine jedinke (kvaliteta pojedinog rješenja koje jedinka predstavlja) pomoću funkcije dobrote.
- Selektiraju se jedinke koje se ne eliminiraju (provodi se selekcija).
- Nad selektiranim jedinkama se provode genetski operatori (križanje i mutacija).
- Novonastale i/ili promijenjene jedinke tvore novu populaciju.
- Prekida se algoritam ili nastavlja od 2. koraka.
U 2. koraku se svaka jedinka procjenjuje funkcijom dobrote koja brojčanom vrijednošću pokušava opisati sposobnost pojedine jedinke (potencijalnog rješenja) da riješi dani problem.
U 3. koraku se s većom vjerojatnošću odabiru bolje jedinke (preživljavanje najsposobnijih), kako bi sljedeća populacija imala bolju prosječnu dobrotu jedinki (napredak algoritma).
U 4. koraku se selektirane (preživjele) jedinke međusobno križaju i mutiraju kako bi stvorile nove jedinke.
Operatori križanja i mutacije se u genetskom algoritmu provode na način sličan kao u prirodi. Mutacija se provodi tako što se napravi manja promjena u strukturi koja zapisuje potencijalno rješenje problema (kromosom), kao što se u prirodi napravi manja mutacija nad genima jedinke. Pri križanju se pomoću dvije (ili više) jedinke (zvane "roditelji") stvara nova jedinka (zvana "dijete") čija struktura podatka (koja opisuje potencijalno rješenje danog problema) nastaje kombiniranjem "roditeljskih" struktura podataka. Na sličan način se u prirodi geni potomaka stvaraju kombiniranjem gena roditelja.
4. Problem krojenja
4.1. Problem krojenja u dvije dimenzije
U okviru rada je ostvareno programsko rješenje koje genetskim algoritmom rješava dvodimenzijski problem krojenja. Površina iz koje se oblici "izrezuju" je pravokutna, dok je svaki oblik predstavljen poligonom.
4.1.1. Zapis jedinke
Problem krojenja koji genetski algoritam rješava zapisan je kao niz poligona.
Svaka pojedina jedinka zapisuje potencijalno rješenje tako što za svaki poligon zapiše x i y koordinatu početne točke poligona, te kut za koji se poligon rotira u smjeru suprotnom od kazaljke na satu. Dakle, jedinka pamti tri podatka za svaki poligon.
Na slici 4.1 prikazan je način zapisivanja jedinke. Zaokruženi vrh predstavlja početni vrh poligona, te se pomicanjem njega pomiče cijeli poligon.
4.1.2. Dobrota
Dobrote jedinke je sposobnost jedinke pri rješavanju problema krojenja. Prilikom procjene dobrote jedinke koristi se funkcija koja za pojedinu jedinku daje brojčanu vrijednost koja opisuje sposobnost jedinke prilikom rješavanja problema.
Dobrota jedinke se izračunava kao površina najmanjeg pravokutnika čije su stranice paralelne sa x i y osima ravnine u kojoj se nalazi.Paralelnost sa osima ne predstavlja ograničenje pri traženju rješenja budući da se poligoni mogu rotirati, te na taj način prilagoditi orijentaciji x i y osi. Na slici 4.2 površina zatamnjenog pravokutnika predstavlja dobrotu jedinke.
4.1.3. Mutacija
Operator mutacije sa zadanom vjerojatnošću vrši manje promjene nad jedinkom kako bi unio nov genetski materijal u populaciju, te time povećao genetsku raznolikost. Mutacijom se jedinka može pomaknuti u neistraženo područje prostora pretrage, te time omogućiti algoritmu pronalazak potencijalno boljeg rješenja.
Mutacija se provodi na jedan od dva moguća načina. (Slika 4.3.)
- Sa vjerojatnošću 50% se slučajno odabire poligon, te se rotira za slučajno odabran kut.
- Sa vjerojatnošću 50% se slučajno odabire poligon, te se pomakne na slučajno odabrano mjesto unutar minimalnog pravokutnika koji obuhvaća sve poligone. Budući da se poligon pomiče na mjesto koje je unutar pravokutnika u kojem su svi poligoni, jedinka se uspješno prilagođava veličini poligona i uređenosti rješenja kojeg predstavlja.
Nakon
mutacije, rješenje koje jedinka predstavlja može biti neispravno, ukoliko se
poligoni sijeku. Zato se poziva funkcija koja popravlja rješenje kako bi
postalo valjano (poligoni se "razmiču" kako se ne bi sjekli, te se
zatim približavaju).
4.1.4. Križanje
Križanjem dvije postojeće jedinke (roditelji) stvara se nova jedinka (dijete) koja sadrži genetski materijal roditelja.
Križanje se vrši uniformno[1] tako da se s jednakom vjerojatnošću bira hoće li se pozicija i kut pojedinog poligona preuzeti iz jednog ili drugog roditelja. Primjer križanja dan je na slici 4.4.
Budući da
nakon križanja rješenje koje dijete predstavlja može biti neispravno (poligoni
se sijeku) rješenje se uređuje funkcijom koja popravlja rješenja kako bi bilo
valjano. Funkcija popravlja rješenje tako da poligone međusobno udalji (kako se
ne bi sjekli), te ih zatim što više približi bez da se sijeku.
5. Ostvareno programsko rješenje
5.1. Opis programskog sustava
Programski sustav je ostvaren u jeziku Java (verzija 6). Sustav je stvoren u programskom okružju Eclipse (verzija 3.5.2). Eclipse je integrirana razvojna okolina (IDE) koja je besplatna za korištenje, te je otvorenog koda.
Sve klase korištene u ostvarenom sustavu nalaze se u paketu com.kusalic.zavrsni.
Od ostvarenih klase treba istaknuti nekoliko bitnijih:
- GUI - Ostvaruje grafičko sučelje kroz koje se pokreće algoritam, podešavaju parametri algoritma, te upravlja izvođenjem. Grafičko sučelje prikazuje najbolje pronađeno rješenje, te dodatne informacije o provedbi algoritma.
- Prikaz - Klasa Prikaz ostvaruje komponentu koja grafički prikazuje rješenje opisano pojedinom jedinkom algoritma.
- GA - GA ostvaruje sam genetski algoritma, te pamti populaciju jedinki i njihove dobrote. Klasa GA barata sa interfaceom IJedinka, te ostvaruje oblikovni obrazac Metoda tvornice.
- IJedinka - IJedinka je interface koji nasljeđuje jedinka koja ostvaruje genetske operatore za pojedini problem. Ovaj interface omogućuje inverziju ovisnosti između samog genetskog algoritma opisanog klasom GA i implementacije genetskih operatora za pojedini problem koji GA rješava (u ovom slučaju klasu Krojenje).
- Krojenje - Klasa Krojenje implementira interface IJedinka, te ostvaruje genetske operatore za potrebu rješavanje dvodimenzijskog problema krojenja. Objekti klase Krojenje predstavljaju pojedine jedinke genetskog algoritma.
- ZapisProblema - Klasa ostvaruje oblikovni obrazac Jedinstveni objekt kako bi se uštedjeli računalni resursi, te kako bi se osigurala jedinstvena odgovornosti pri definiranju problema. Klasa zapisuje problem koji se rješava, tj. popis poligona koje treba "izrezati" iz što manje površine. ZapisProblema se inicijalizira datotekom s opisom poligona.
Na slici 5.1 je prikazan UML dijagram bitnijih klasa.
Detaljniji opis pojedine metoda u svakoj klasi može se pronaći u obliku javadoc dokumentacija koja je ugrađena u sam kod klasa.
Prilikom ostvarivanja genetskog algoritma implementirana je eliminacijska selekcija. Ostvareni genetski algoritam ima sljedeći oblik[1]:
Eliminacijski
genetski algoritam{
generiraj početnu populaciju;
sve dok nije zadovoljen uvjet završetka
evolucijskog procesa{
izračunaj vjerojatnost eliminacije za svaku
jedinku;
M puta jednostavnom selekcijom odaberi i
izbriši jedinku;
križanjem preživjelih jedinki nadopuni
populaciju;
}
}
Selekcija je provedena ruletskim kolom, te je kazna pojedine jedinke ki određena izrazom
ki = (di-dmax) / (dmin-dmax)
U izrazu je dmax dobrota najbolje jedinke u populaciji, dmin dobrota najgore jedinke u populaciji, a di dobrota i-te jedinke u populaciji. Navedeni način izračuna kazne osigurava "elitizam" najbolje jedinke.[1]
Za određivanje broja jedinki koje treba eliminirati u populaciji (M), korištena je preporuku iz [1], prema kojoj u populaciji od 30 jedinki treba eliminirati 30/2 jedinki, dok u populacija od 100 jedinki treba eliminirati 100/4 jedinki. Zato je za određivanje broja jedinki koje treba eliminirati u populaciji veličine n korištena formula:
M = n / (2+(n-30)/35)
Nakon primjene operatora križanja ili mutacije jedinka može sadržavati zapis rješenja problema koji nije ispravan, jer se neki poligoni međusobno sijeku. Kako bi se takve nepravilnosti ispravile ostvarena je metoda "private void slijepi()".
Navedena metoda "popravlja" rješenje koje pojedina jedinka predstavlja. Prvo se poligoni međusobno udalje kako se nikoja dva ne bi međusobno sjekli. Nakon toga se poligoni približavaju koliko god je moguće, bez da se sijeku ili da jedan poligon obuhvati neki drugi. Prije pomicanja pojedinih poligona izračuna se točka koja predstavlja "težište", kao prosjek svih točaka od kojih se sastoje pojedini poligoni. Zatim se poligoni jedan po jedan približavaju težištu počevši od onih poligona koji su najbliži težištu. Provjera sijeku li se poligoni vrši se na sljedeći način:
- Provjeri se sječe li se neki brid pomaknutog poligona sa nekim bridom ostalih poligona.
- Iz jedna točke pomaknutog poligona povuče se polupravac u proizvoljnom smjeru, te se izračuna koliko bridova siječe povučeni polupravac (ne računaju se bridovi pomaknutog poligona). Ukoliko polupravac siječe paran broj bridova, tada se točka iz koje je povučen polupravac nalazi van ostalih poligona.
- Za svaki poligon se provjeri nalazi li se unutar pomaknutog poligona.
Pri pomicanju poligona prema točki težišta koristi se binarna pretraga[2][4]. Primjer dužine po kojoj se radi binarna pretraga prikazan je na slici 5.2 iscrtkanom linijom. Poligon sa lijeve strane slike se pomiče što više prema poligonima na desnoj strani slike. Pritom iscrtkana linija prikazuje putanju po kojoj se lijevi poligon može pomicati bez da se siječe sa poligonima s desne strane. Iscrtkani poligona predstavlja poligon s lijeve strane nakon što većeg pomaka, koji pronađe binarna pretraga.
5.2. Upute za korištenje
Programsko rješenje ostvaruje grafičko korisničko sučelje kroz koje se može upravljati izvođenjem algoritma. Grafičko korisničko sučelje je prikazano na slici 5.3.
Na desnoj strani korisničkog sučelja nalazi se područje u kojem se vizualno prikazuje najbolje do sada pronađeno rješenje. Pronađeno rješenje je prikazano plavim poligonima. Oko plavih poligona nalazi se crveni pravokutnik koji prikazuje površinu iz koje se "kroje" poligoni. Veličina crvenog pravokutnika vizualno prikazuje dobrotu trenutno najboljeg pronađenog rješenja. Područje za prikaz rješenja prilagođava se tako da uvijek prikaže sve poligone od ruba do ruba, te zato uvećava pronađeno rješenje kako bi se prikazalo što većim.
Na lijevoj strani korisničkog sučelja nalaze se polja za unos i tipke pomoću kojih se upravlja izvođenjem programa, dok se pri dnu korisničkog sučelja nalazi progresna traka u kojoj se prikazuje napredak izvršavanja algoritma.
U gornjem lijevom dijelu korisničkog sučelja prikazuju se upute i poruka o trenutnom stanju programa. To su poruke: "Odaberite datoteku...", "Niste učitali datoteku!", "Učitali ste datoteku.", "Inicijalizacija nije uspjela", "Algoritam je inicijaliziran.", "Broj je krivo upisan.", "Algoritam se izvršava", "Algoritam je završio" i sl.
Odmah ispod uputa i poruka o trenutnom stanju programa, nalazi se tipka "Učitavanje datoteke" koja otvara prozor unutar kojeg se odabire datoteka sa opisom problema.
Ispod tipke za učitavanje datoteke, nalaze se dva polja za unos u koja se upisuje parametri s kojima se inicijalizira genetski algoritam. Parametri su veličina populacije i vjerojatnost mutacije jedinke nakon križanja.
Ispod polja za unos parametara nalazi se tipka "Inicijalizacija". Stiskanjem tipke genetski se algoritma inicijalizira upisanim parametrima (ukoliko su parametri krivo upisani dobiva se obavijest) i poligonima opisanim unutar odabrane datoteke, te se u desnoj strani korisničkog sučelja prikazuje najbolja jedinka iz slučajno generirane populacije rješenja. Želimo li inicijalizirati program novim problemom dovoljno je učitati novu datoteku i ponovno inicijalizirati populaciju. Nakon inicijalizacije, tipka se mijenja u tipku "Restart" kojom se može ponovno izgenerirati slučajna početna populacija rješenja. Nakon inicijalizacije se omogućava stiskanje tipke "Izvrši".
Ispod tipke za inicijalizaciju nalazi se polje za unos u koje se upisuje željeni broj koraka algoritma. Ispod se nalazi tipka "Izvrši" koja izvrši željeni broj koraka algoritma (ukoliko je broj krivo upisan dobiva se odgovarajuća obavijest). Prilikom izvršavanja algoritma nije moguće koristiti tipke "Restart" i "Izvrši" sve dok se algoritam ne završi. Napredak izvršavanja algoritma prikazuje se u progresnoj traci pri dnu grafičkog korisničkog sučelja, dok se u području za prikaz rješenja izmjenjuje prikaz trenutno najbolje jedinke u populaciji. Nakon što algoritam završi može se upisati novi broj koraka u polje za unos, te stiskanjem tipke "Izvrši" nastaviti koristiti postojeću populaciju rješenja (ne stvara se nova slučajna populacija rješenja).
Datoteka koja opisuje poligone oblikovana ja na način koji se često koristi u računalnoj grafici. Poligoni su zapisani kao tablice vrhova i bridova:
- Vrhovi su dijeljeni, zajednički za različite poligone, nisu replicirani.
- U tablici poligona su zapisani indeksi vrhova.
- Pomicanje jednog vrha izobličit će sve poligone koji ga dijele
- Razdvojena je informacija o geometriji (vrhovi) i topologiji (povezanost - poligoni)
Svaka linija datoteke može biti prazna, ili počinjati sa znakom '#', 'v' ili 'f'. '#' predstavlja komentar, te se linije koje počinju znakom '#' zanemaruju. Linija koja počinju znakom 'v' opisuju pojedinu točku pomoću dva broja koji su x i y koordinata točke. Linija koja počinje znakom 'f' opisuje pojedini poligon pomoću niza 1-indeksiranih točaka (prethodno navedenih linijama koje počinju znakom 'v').
Sljedeći primjer datoteke opisuje poligone sa slike 5.4:
# tocke
pocinju sa 'v', a poligoni sa 'f'
v 0.0 0.0
v 1.0 0.0
v 0.0 1.0
f 1 2 3
v 2.0 1.0
v 1.0 2.0
f 1 2 4 5
5.3. Analiza
Na slici 5.5 su dana razna rješenje koje je genetski algoritam generirao za isti skup poligona (istu ulaznu datoteku). Algoritam je svaki put pokrenut sa veličinom populacije 30, vjerojatnošću mutacije 0.3, te je provedeno 50 koraka algoritma.
Kao što se sa slike 5.5 može uočiti, rješenja koja daje genetski algoritam se međusobno razlikuju, ali sva prilično dobro popunjavaju pravokutnik (crvene boje) u koji su smješteni.
Čovjek u svakom ponuđenom rješenju lako može primijetiti manje promjene koje bi se mogle napravit kako bi rješenje bilo još malo bolje. Ipak, klasični genetski algoritam teško može provoditi takva "fina" podešavanja budući da ne radi pretpostavke o izgledu područja pretrage. Kad bi htjeli da nam program stvori rješenje u kojemu nećemo odmah uočiti moguće poboljšanje, trebali bi napraviti dodatna geometrijska ispitivanja i preoblikovanja rješenja u okviru novih funkcionalnosti programa, nevezanih za sam genetski algoritam. Ne bi imalo previše smisla duže vrijeme izvoditi genetski algoritam samo zato da bi postigli "fina" podešavanja rješenja, jer genetski algoritam ne bi bio previše uspješan u tome.
Na slici 5.6 su dana tri tipična rezultata koje je generirao genetski algoritam za problem krojenja sedam "kuglica". Algoritam je pokretan sa populacijom od 30 jedinki, vjerojatnošću mutacije 0.3, te je provedeno 50 koraka algoritam.
Navedeni problem (slika 5.6) je vrlo tipičan, te čovjek lako pronalazi optimalno rješenje. Ipak, genetski algoritam ne koristi informacije koje koristi čovjek (npr. da su poligoni isti, te da je pojedini poligon simetričan), nego osmerokutima pristupa na jednak način kao i svakim drugim poligonima. Treba primijetiti da genetski algoritam ipak uspijeva pronaći optimalnu organizaciju poligona (ne i "fino" podešavanje), što ukazuje na dobru sposobnost genetskog algoritma pri rješavanju problema krojenja.
Na slici 5.7 naveden je najekstremniji primjer problema u kojem čovjek izrazito lagano pronalazi optimalno rješenje. Kao što se sa slike može vidjeti, program je pokrenut za veću populaciju (80 jedinki), te je zato uzeta manje vjerojatnost mutacije (0.2), te znatno veći broj koraka algoritma (500 koraka).
U problemu sa slike 5.7 teškoće stvara i položaj poligona i njihova rotacija. Čovjek pri rješavanju problema raspolaže informacijama da su svi kutovi okomiti, uviđa da su poligoni jednaki i simetrični, te da je broj poligona 9=32. Genetski algoritam ne čini pretpostavke o izgledu domene pretrage te ne raspolaže navedenim informacijama. Ipak, genetski algoritam uspijeva rasporediti poligone u tri retka sa tri stupca, te uspijeva približno dobro rotirati poligone (u prosjeku 15-ak stupnjeva pogrešno u odnosu na optimalno rješenje), kako bi zauzeo manje prostora.
Ostvareni algoritam pronalazi toliko dobro rješenje kao ono na slici 5.7 kada se radi o problemu gdje postoji jedinstveno optimalno rješenje. Zato se sa sigurnošću može tvrditi da program dobro rješava i sve one probleme u kojima ljudi ne bi bili previše uspješni, što ga čini izrazito dobrim i primjenjivim rješenjem problema krojenja.
Parametri genetskog algoritma:
- Veličina populacije - Veličina populacije utječe na brzinu konvergacije algoritma prema lokalnom optimumu. Što je populacija veća to više genetskog materijala sadrži, te je potrebno više iteracija algoritma kako bi se populacija ujednačila. Zato velika populacija sporije konvergira od male populacija. S druge strane, velika populacija sadrži veću genetsku raznolikost od manje populacije, te zato bolje pretražuje prostor pretrage i sa većom vjerojatnošću pronalazi globalni optimum. Više jedinki bolje pretraže prostor pretrage, te je populacija "otpornija" na konvergiranje prema lokalnom optimum. Nad većom populacijom se sporije provodi pojedini korak algoritma budući da više jedinki treba eliminirati i nadomjestiti križanjem.
- Vjerojatnost mutacije - Vjerojatnost mutacije utječe na unos novog genetskog materijala u populaciju. Mutacija unosi novi genetski materijal u populaciju, te omogućava jedinkama da izađu iz lokalnog optimuma i pronađu potencijalno bolja područja pretrage. Ukoliko se vjerojatnost mutacije postavi na previše malu vrijednost, algoritam biva skloniji zapasti u lokalne optimume. Ukoliko se pak vjerojatnost mutacije postavi na previše veliku vrijednost, algoritam teško otkriva globalni maksimum jer gubi sposobnost konvergacije, te zapravo vrši slučajnu pretragu prostora potencijalnih rješenja. Preporučena vjerojatnost mutacije je u intervalu [0.05,0.5].
- Broj koraka algoritma - Broj koraka algoritam je u direktnoj vezi za vremenom izvođenja. Nakon što algoritam zapadne u neki optimum, nema previše smisla nastaviti provedbu algoritma jer je mala vjerojatnost pronalaska boljeg rješenja. Broj koraka potreban da bi algoritam konvergirao vezan je za veličinu populacija i vjerojatnost mutacije. Što je populacija veća to treba više vremena da konvergira. Što je mutacija vjerojatnija, to populacija teže konvergira. Za veliku populaciju često se postavi manja vjerojatnost mutacije (jer veća populacija može sadržavati više različitog genetskog materijala, pa je mutacija manje potrebna), te velik broj koraka algoritam jer se očekuje sporija konvergacija.
Brzina izvođenja algoritma ovisi o broju poligona koje treba posložiti, te o broju stranica od kojih se pojedini poligon sastoji. Što više poligona treba posložiti, to je više vremena potrebno kako bi se provjerilo sijeku li se svaka dva poligona. Brzina izvođenja se usporava kvadratno o broju poligona i stranica poligona. Brzinu izvođenja je sporija ukoliko se radi o većoj populaciji jedinki, proporcionalno veličini populacije. Brzinu izvođenja usporava i veća vjerojatnost mutacije, proporcionalno vjerojatnosti.
Prosječno vrijeme potrebno da se stvori neko od rješenja sa slika 5.5 i 5.6 iznosi 5 sekundi.
Algoritam pokazuje lošije rezultate pri krojenju velikog broja poligona. Nakon 8 sati izvođenja sa populacijom od 100 jedinki, algoritam je pri slaganju 40 jednakih trokuta stigao napraviti 2000 koraka. Rezultat je prikazani na slici 5.8. Kako bi se postigli bolji rezultati potrebno je ostvariti adaptivni genetski algoritam koji će prilagođavati parametre algoritma ovisno o stanju u populaciji.
5.4. Daljnji razvoj programskog sustava
Ostvareni programski sustav se može nastaviti razvijati kako bi dao bolje rezultate, te bio lakši za koristiti.
Smjernice za daljnji razvoj:
- Drukčija definicija poligona. Unos oblih oblika (kružnica).
- Adaptivni genetski algoritam.
- Drukčija implementacija genetskih operatora ili funkcije sljepljivanja.
- Proširenje grafičkog sučelja.
- Paralelna izvedba genetskog algoritma.
6. Zaključak
U radu je definiran jednodimenzijski i višedimenzijski problem krojenja, pri čemu su u obzir uzete razne vrste ograničenja. Osmišljen je genetski algoritam za rješavanje dvodimenzijskog problema krojenja. Ostvaren je programski sustav koji genetskim algoritmom rješava dvodimenzijski problem krojenja te su analizirani dobiveni rezultati. Programski sustav uspješno rješava problem krojenja, te u vrlo kratkom vremenu daje kvalitetne rezultate. Programski sustav koristi odgovarajuće oblikovne obrasce i algoritme kako bi bio što brži i što stabilniji. Kroz ostvareno grafičko sučelje upravlja se izvođenjem programa, te se vizualiziraju rješenja problema. Programski sustav je primjenjiv na stvarne industrijske probleme.
LITERATURA
[1] Marin Golub. Genetski algoritam, skripta – 1. dio,
1997. URL http://www.
zemris.fer.hr/~golub/ga/ga_skripta1.pdf.
[2] Robert Sedgewick. Algorithms in C.
Addison-Wesley, 1990.
[3] Sanghamitra Bandyopadhyay & Sankar K. Pal. Classification
and Learning Using Genetic Algorithms. Springer, 2007.
[4] Thomas H. Cormen, Charles E. Leiserson, Ronald L.
Rivest, Clifford Stein. Introduction to Algorithms, Second Edition. MIT
Press, McGraw-Hill, 2001.
[5] U.S. National Institute of Standards and Technology. Cutting
stock problem, 2010. URL http://www.itl.nist.gov/div897/sqg/dads/HTML/
cuttingStock.html.
[6] Wikipedia. NP-complete, 2010. URL http://en.wikipedia.org/wiki/
NP-complete.
[7] Wikipedia. Cutting stock problem, 2010. URL http://en.wikipedia.
org/wiki/Cutting_stock_problem.
[8] Wikipedia. Evolutionary algorithm, 2010. URL http://en.wikipedia.
org/wiki/Evolutionary_algorithm.
[9] Wikipedia. Evolutionary computation, 2010. URL
http://en.wikipedia. org/wiki/Evolutionary_computation.
Rješavanje problema
krojenja uz pomoć genetskog algoritma
Sažetak
Problem krojenja pripada kategoriji NP-potpunih problema, te pronalazi mnoge primjene u industriji. Cilj problema krojenja je smanjiti industrijske viškove koji nastaju pri obradi materijala, kako bi se smanjili troškovi proizvodnje. U ovom radu se genetskim algoritmom pristupa rješavanju dvodimenzijskog problema krojenja. Programski je ostvaren genetski algoritam koji rješava problem krojenja. Ostvareni programski sustav uspješno rješava dvodimenzijski problem krojenja. U radu je programski sustav detaljno opisan, analizirane su performanse sustave, kvaliteta rješenja koje sustav stvara, te opisani utjecaji parametara genetskog algoritma na performanse sustava.
Ključne riječi: genetski algoritam, problem krojenja, ostvareni
programski sustav
Solving Tailoring Problem
with Genetic algorithm
Abstract
The Tailoring problem belongs to the category of NP-complete problems, and finds many applications in industry. The aim of tailoring problem is to reduce industrial surpluses generated by the processing of materials in order to reduce production costs. This paper offers the approach to solving two-dimensional cutting problem using genetic algorithm. The genetic algorithm that solves the problem of tailoring has been implemented. The software system successfully solves the problem of two-dimensional cutting. The software system is described in detail. System performance and quality of solutions are analyzed. Influence of genetic algorithm parameters on the performance of the system are described.
Keywords: genetic algorithm, tailoring problem, software solution