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

Algoritam MinMaxAS

Autor: Filip Domazet
Poveznice: završni rad

Značenje tragova i računanje vjerojatnosti odabira

Korišten optimizacijski algoritam kolonije mrava bazirao se na Max-Min Ant Systems verziji. U Max Min Ant System algoritmu postoji donja i gornja granica na vrijednosti tragova, te da tragove postavlja samo najbolji mrav [3], no u ovom slučaju gornja granica tragova se neće primjenjivati.

Koriste se dva skupa tragova, jedan koji se koristi pri određivanju duljine materijala koju treba uzeti, a drugi koji pri određivanju izreska kojeg treba dodati u plan rezanja već odabranog materijala.

Što se tiče tragova među izrescima, značenje tragova i formule računanja vjerojatnosti se oslanjaju na [2]. Trag između izreska duljine i te izreska duljine j , tj. ?(i, j) se koristi kao mjera povoljnosti da se u planu rezanja materijala duljine x nalaze izresci duljina i i j (vrijedi ?(i, j) = ?(j, i)).

Prema tragovima među izrescima koji su u planu rezanja (označimo taj skup sa s) i izrescima koje još možemo dodati računa se vjerojatnost odabira pojedinog izreska koristeći sljedeću formulu:

gdje J(x, s) skup izrezaka koji još "stanu" u plan rezanja materijala. Gornja formula vrijedi ako je , u protivnom je p(i, s) = 0. ?b(i) je prosječna vrijednost tragova između izreska duljine i i svih izrezaka trenutno u planu rezanja (s), formalno:

Što se tiče tragova za duljine materijala, oni predstavljaju koliko je određena duljina materijala povoljna za koristiti. Vjerojatnost odabira materijala duljine x se računa prema formuli:

gdje L(k) predstavlja skup raspoloživih duljina u koraku k (nakon k odabira), a ?(x) predstavlja heurističku povoljnost odabira materijala duljine x. Heuristička povoljnost se zadaje kao parametar koji daje prednost duljinama materijala koje su u ograničenim zalihama (pretpostavlja se da su to ostaci prijašnjih rezova kojih se želi riješit).

Funkcija dobrote

Prema [2] funkcija dobrote rješenja S računa se po sljedećoj formuli:

gdje je N broj korištenih materijala u rješenju S, Fi zbroj izrezaka u planu rezanja i-tog materijala, a xi ukupna duljina i-tog materijala. Pomoću eksponenta k može se podešavati kakva se rješenja vrednuju više. Ako je k = 1, onda se gleda samo prosječna iskorištenost, a za k > 1, bolja se smatraju rješenja koja imaju mješavinu dobro iskorištenih materijala i manje dobro iskorištenih materijala. Prilagodba koja se koristi pri ovom algoritmu jest da se materijal smatra potpuno iskorištenim ako je ostatak manji od duljine koja se smatra prihvatljivom (označimo s d), tj. ako xi – Fi < d. onda se umjesto stavlja 1.

Značenje tragova i računanje vjerojatnosti odabira

Tragove postavlja najbolji mrav, i to naizmjence najbolji u iteraciji i globalno najbolji, pri čemu globalno najbolji tragove postavlja svakih ? iteracija. Vrijednosti tragova vezanih uz duljine materijala se povećaju za "prosječnu" iskorištenost materijala određene duljine (računa sa prema formuli funkcije dobrote, ali samo za materijale te duljine) unutar rješenja.
Tragovi među izrescima i i j u za materijal duljine x, se povećaju za , pri čemu je m broj pojavljivanja materijala duljine i zajedno sa materijalom duljine j unutar istog plana rezanja materijala duljine x. Nakon postavljanja tragova, primjenjuje se isparavanje, tako da se vrijednosti svih tragova pomnože sa parametrom isparavanja ?, .
Zbog navedene definicije tragove i ovakvog načina računanja tragova, nije postavljena gornja granica na vrijednost tragova. Donja granica vrijednosti tragova se zadaje kao parametar algoritma.