Primjena evolucijskih algoritama u problemima raspoređivanja: Optimiranje problema krojenja 1D korištenjem evolucijskih algoritma

Algoritam YAEAuzLS

Autor: Marin Maržić

Evolucijske strategije

Evolucijske strategije su optimizacijske tehnike iz područja evolucijskih algoritama bazirane na prilagođavanju i evoluciji. Njihova središnja ideja je stvaranje jednog ili λ potomaka operacijom mutacije iz jednog ili μ roditelja. Roditelji i potomci predstavljaju potencijalno rješenje optimizacijskog problema. [4]

YAEA primjenjuje evolucijsku strategiju varijante (μ + λ)-ES gdje je μ broj roditelja koji mutacijom stvaraju λ potomaka. Selekcijom se iz skupa roditelja i potomaka odabire μ najboljih jedinki koji prelaze u sljedeću generaciju kao novi budući roditelji. U ovoj implementaciji je μ proizvoljan broj jedinki početne populacije roditelja. λ je cjelobrojni višekratnik od μ (λ = n * μ, n = 1, 2, ...). Npr. μ = 4 pa λ može poprimiti vrijednosti 4, 8, 12, ...

Programsko rješenje

Program koristi evolucijske strategije kao tehniku optimizacije pri rješavanju problema krojenja 1D (engl. cutting-stock problem ili CSP) s različitim veličinama zaliha i rezova (uključujući beskonačne zalihe). Također periodično primjenjuje varijantu lokalnog pretraživanja nad jedinkama populacije u nastojanju poboljšanja rješenja.

Zapis jedinke rješenja je baziran na redoslijedu nizova zalihe i rezova [5]. Redom rezovi "ulaze" u zalihu tj. bivaju izrezani iz nje dok ju ne "popune" tj. potroše (sljedeći rez u nizu ne može biti izrezan iz preostale zalihe). Kad je zaliha potrošena sljedeći rezovi u nizu ulaze u sljedeću zalihu u nizu. Ukoliko je rez veći od zalihe ta se zaliha preskače kao da je nije bilo. Npr. neka je niz zaliha [10, 5, 8, 9], a niz rezova [4, 4, 4, 9]. Tada će se iz zalihe 10 rezati dva reza 4, iz zalihe 5 jedan rez 4, a zaliha 9 će biti rez 9.

Mutacija i selekcija

Mutacija proizvoljan broj puta radi zamjenu elemenata nizova zaliha i rezova u nasumične tri točke (3 elementa niza zamjene pozicije). Ta zamjena je izvedena nasumičnim odabiranjem elemenata niza indeksa i, j, k i njihovim preuređenjem u niz k, i, j. Npr. ukoliko mutacija radi jednu zamjenu i imamo niz rezova [1, 2, 3, 4, 5], a nasumično su odabrani indeksi 2, 4, 5, onda će niz nakon mutacije biti [1, 5, 3, 2, 4].

Selekcija rangira skup roditelja i potomaka po funkciji dobrote što postavlja μ bolje rangiranih jedinki kao roditelje iduće generacije.

Funkcija dobrote

Funkcija dobrote jedinku rješenja vrednuje bolje po kriterijima [6]:
   - manje gubitaka pri rezanju
   - više savršenih rezova tj. unutar granice dovoljno dobrog
   - manje korištenja beskonačnih zaliha
   - ekstremniji raspored rezova tj. gubitaka (jako veliki i jako mali gubitci)

gdje je:
    J = broj zaliha korišten u rješenju
    K = broj beskonačnih zaliha korišten u rješenju
    Tj = gubitak pri rezanju j-te zalihe
    Lj = veličina j-te zalihe
    tj = 1 ukoliko je j-ta zaliha dovoljno dobro iskorištena, inače 0
    uj = 1 ukoliko je j-ta zaliha beskonačna, inače 0

Lokalno pretraživanje

YAEAuzLS radi slično kao YAEA. Razlika je u periodičnom provođenju varijante lokalnog pretraživanja (LS) između mutacije i selekcije. Frekvencija provođenja LS je proizvoljna. LS se provodi nad skupom roditelja i potomaka.

LS radi na način da "oslobodi" neke zalihe i pripadajuće rezove tako da zalihe stavi na kraj redoslijeda, a rezove izbaci te ih pokuša efikasnije ubaciti u rješenje.

Oslobođeni rezovi se pokušavaju ubaciti natrag u rješenje počevši od najvećih. Prvo se za rez pokuša naći potpuno slobodno mjesto. Ukoliko to ne uspije pokuša se zamijeniti s nekim manjim rezom tako da još uvijek "stane" u zalihu (ne zahtjeva korištenje nove zalihe), dok se manji rez oslobađa. Ukoliko ni to ne uspije rez se stavlja na kraj redoslijeda na svoje staro mjesto tj. u staru zalihu.