Algotimizace prostrihu
nesvacil@posys.eu
nesvacil@posys.eu
Neděle Březen 25 16:17:07 CEST 2007
Evolucnich algoritmu je docela dost - viz ty geneticke.
Kdyz jste pocital, zda se neco prekryje nebo ne, tak by se z toho dala
udelat funkce napr. vysledkem funkce by bylo vypocitano kolik plochy se na
tom velkem obdelniku vyzujie. Jestlize by se neco prekryvalo, tak bych tu
hodnotu prekryvu pocital zaporne tj. hodnotu o co se prekryva * -2.
Ta funkce by mela ty parametry orient_LH, ... proste vse co jste mel v tech
cyklech.
Vysledkem je, ze hledat co nejvetsi vyuziti plochy toho velkeho obdelniku a
mate tech nekolik parametru.
Te funkci co sestrojite se rika ucelova funkce nebo taky nakladova funkce.
Nyni k zakladu misto tech nekolik cyklu pouzijeme rizenou nahodu, ktera nam
umozni najit optimalni hodnoty tech orient_lh ... . Vsechny ty promenne,
ktere chceme zjistit to orient_lh ... dame do struktury, matematicky vektoru
a rika se tomu Jedinec. Nyni tedy rikame, ze hledame jedince, ktery ma pro
nas optimalni hodnoty.
V programu vytvorime pole Jedincu urcime si nejake. Tomu poli se rika
Pupulace. Na zacatku si pomoci generatoru nahodnych cisel vygenerujeme
hodnoty.
Nyni se rozdeluji evolucni algoritmu jakym zpusobem se s poulaci bude
zachazet tj. jakym zpusobem vygeneruji novou populaci, dalsi novou, az po
vyhodnoceni tech Jedincu v populaci si myslim, ze jsem dosel do konce.
Jestli budete hledat nejaka prisna pravidla jak z populace udelat chytrejsi
populaci nejakym jasne danym algoritmem, tak jste na tom stejne jako ja na
zacatku.
Aby se nemusel opakovat, tak tady mam z prednasky vytah gen.alg:
Genetické algoritmy
1) musíme nadefinovat účelovou funkci
- to mame to je ta nase max plocha
2) musíme nadefinovat specimen (vzorový jedinec), např:
{
{real, Lo1, Hi1} X1 -
{int, Lo2, Hi2} X2-
..
{real, Lon, Hin}} Xn-
}
Je to vlastně definice typu a rozsahu vstupních parametrů účelové fce
- to je nase struktura Jedince
3) vygenerování počáteční populace
RND((Hi-Lo))+Lo - z daného intervalu vygeneruji náhodné číslo, čímž
vygeneruji jednotlivé jedince
- pouzijeme nahodu
4) ohodnocení kvality:
vezmu každého jedince, dám ho do účelové fce a vypočítám její hodnotu
- vypocitame plochu u kazdeho jedince
5) výběr rodičů
- Vyberu si jednu metodu. Nejlepe ruleta:
ruletou - vezmu si pomyslnou ruletu a jednotlivým jedincům přidělím výsek na
ruletě, jehož
velikost odpovídá kvalitě jedince - čím kvalitnější jedinec, tím má na
ruletě větší výsek; pak
náhodně vybírám z ruletu; je to náhodný výběr s preferencí lepších jedinců;
je to nejpoužívanější
metoda
- Kvalita jedince mi rika jestli ma vetsi plochu DPS ci mensi tj. udelam
zebricek a tem lepsim pridelim vetsi usek na rulete.
6) křížení
Jedinci v GA mají binární charakter. Celému jedinci se říká chromozón.
0 1 1 0 0 1 . . . . 1 1 0
X1 X2 X2
Jednotlivým algoritmům X1, X2.Xn se říká geny.
Křížení spočívá v tom, že chromozóny dvou jedinců:
o rozstřihnu na poloviny a jednu polovinu jedince vyměním se stejnou
polovinou druhého jedince
o rozstřihnu na poloviny a jednu polovinu jedince vyměním s opačnou
polovinou druhého jedince
o rozstřihnu na třetiny a krajní třetiny vyměním s druhým jedincem
o spojím "do kruhu" a někde znovu rozříznu
Tím dostanu dva nové potomky (samozřejmě musím brát v potaz ošetření
překročení hranic).
7) mutace - nové potomky musím zmutovat, dělá se to nejčastěji takhle:
for i=1 to n (n - počet bitů jedince)
{
if (rnd > prahMutace) then mutuj else ponech
}
Požívá se to proto, že když křížím dva rodiče, tak může vzniknout jen
konečný počet potomků.
Mutacím zajistím, že se mi potomci dostanou i mimo tento konečný počet.
8) výběr lepších (tvorba nové populace)
ze staré populace a potomků vyberu ty nejlepší (elitizmus) a vznikne nová
populace - vlastně vezmu
rodiče, potomky a podle filtru vyberu, jestli je lepší rodič nebo potomek a
toho vezmu. Mohou se
porovnávat jen rodiče a jejich potomci, nebo se budou porovnávat všichni, je
to otázka strategie.
V okamžiku, když je nová populace zaplněna, tak stará umírá
9) test na konečné podmínky
musím otestovat, jestli už nemám skončit (např. počet plánovaných generací
je splněn) tak ukonči, jinak
skok na krok 5
Snad to takto na zacatek staci. Jestli Vam neni jasny bod Krizeni, tak to
mne taky nebyl. Nejedna se o to vytvorit neco lepsiho, ale jen neco zamenit
respektive neco jako v chromozomu, proto se to taky jmenuje geneticky
algoritmus. Napriklad u nas budou ty 1 a 0 bity tech numerickych cisel. Ano
uplne nesmyslne se to prehazi - to je taky ucelem. Pokud nejaka hodnota
vyjedem mimo hranici, tak se zase na hranici musi posunout natvrdo.
Jirka
----- Original Message -----
From: "Ales Prochaska" <prochaska@alsoft.cz>
To: <hw-list@list.hw.cz>
Sent: Sunday, March 25, 2007 11:02 AM
Subject: Re: Algotimizace prostrihu
Jasne, tohle bylo reseni metodou nejmensiho odporu neboli receno
ajtackou mluvou "prototyp aplikace". V dalsim kroku se daji u ctyr z
tech cyklu dopocitat horni meze a dva cykly se daji zrusit protoze
hodnotu ridici promenne lze vypocist z ostatnich.
Kdyz tak nahodte taky nejaky evolucni algoritmus, treba taky
primitivni ale funkcni. Osobne by me docela zajimalo porovnani
ucinnosti obou algoritmu.
Ales Prochaska
> Nejste moc daleko od nejake prakticke realizace.
> Obecne zde mate nekolik cyklu for, ktere daji casove zabrat. Evolucni
> algoritmy se zaobariaji jen tim, ze vam rychleji pomohou najit ty promenne
> orient_LH, ... . Je to pomerne jednoduche.
> Jirka
> ----- Original Message -----
> From: "Ales Prochaska" <prochaska@alsoft.cz>
> To: <hw-list@list.hw.cz>
> Sent: Saturday, March 24, 2007 7:36 PM
> Subject: Re: Algotimizace prostrihu
> Docela me zaujalo jak tu navrhujete geneticke algoritmy a podobne
> teoreticky dobre zvladnute uvahy, ale nejak mi pripada, ze by bylo
> tezke z toho neco vydolovat pro praxi. Takze jsem pustil delfi a na
> treti preklad mi vypadlo tohle. Najde to nejlepsi pokryti zalozene na
> sireni pokryti ze vsech rohu papiru soucasne. Urcite to pujde urychlit
> doplnenim dynamickych mezi cyklu a nahradou tech poli [0..1]
> promennymi a dosazovanim do nich a podobne.
> Ales Prochaska
> program rezani;
> {$APPTYPE CONSOLE}
> uses
> SysUtils;
> const
> papir_x = 210;
> papir_y = 297;
> papirek_x = 50;
> papirek_y = 100;
> var
> orient_LH : integer; // 0 = na sirku, 1 = na delku
> orient_PH : integer;
> orient_LD : integer;
> orient_PD : integer;
> pocet_LH_x : integer;
> pocet_LH_y : integer;
> pocet_PH_x : integer;
> pocet_PH_y : integer;
> pocet_LD_x : integer;
> pocet_LD_y : integer;
> pocet_PD_x : integer;
> pocet_PD_y : integer;
> rozmer_x : array [0..1] of integer; // transformace rozmeru (rotace
> papiru)
> rozmer_y : array [0..1] of integer;
> plocha : integer; // pokryta plocha v jedne iteraci
> max_plocha : integer; // maximalni dosud nalezene pokryti plochy
> begin
> rozmer_x[0]:=papirek_x;
> rozmer_x[1]:=papirek_y;
> rozmer_y[0]:=papirek_y;
> rozmer_y[1]:=papirek_x;
> max_plocha := 0;
> // vyzkouset vsechny orientace v rozich
> for orient_LH:=0 to 1 do begin
> for orient_PH:=0 to 1 do begin
> for orient_LD:=0 to 1 do begin
> for orient_PD:=0 to 1 do begin
> // plnit papir zkusmo ze vsech rohu
> for pocet_LH_x:=0 to papir_x div rozmer_x[orient_LH] do begin
> for pocet_LH_y:=0 to papir_y div rozmer_y[orient_LH] do begin
> for pocet_PH_x:=0 to papir_x div rozmer_x[orient_PH] do begin
> for pocet_PH_y:=0 to papir_y div rozmer_y[orient_PH] do begin
> for pocet_LD_x:=0 to papir_x div rozmer_x[orient_LD] do begin
> for pocet_LD_y:=0 to papir_y div rozmer_y[orient_LD] do begin
> for pocet_PD_x:=0 to papir_x div rozmer_x[orient_PD] do begin
> for pocet_PD_y:=0 to papir_y div rozmer_y[orient_PD] do begin
> // neprekryvaji se potvory?
> if (pocet_LH_x * rozmer_x[orient_LH] + pocet_PH_x *
> rozmer_x[orient_PH] <= papir_x)
> and (pocet_LD_x * rozmer_x[orient_LD] + pocet_PD_x *
> rozmer_x[orient_PD] <= papir_x)
> and (pocet_LH_y * rozmer_y[orient_LH] + pocet_LD_y *
> rozmer_y[orient_LD] <= papir_y)
> and (pocet_PH_y * rozmer_y[orient_PH] + pocet_PD_y *
> rozmer_y[orient_PD] <= papir_y)
> and ((pocet_LH_x * rozmer_x[orient_LH] + pocet_PD_x *
> rozmer_x[orient_PD] <= papir_x)
> or (pocet_LH_y * rozmer_y[orient_LH] + pocet_PD_y *
> rozmer_y[orient_PD] <= papir_y))
> and ((pocet_LD_x * rozmer_x[orient_LD] + pocet_PH_x *
> rozmer_x[orient_PH] <= papir_x)
> or (pocet_LD_y * rozmer_y[orient_LD] + pocet_PH_y *
> rozmer_y[orient_PH] <= papir_y))
> then begin
> plocha := pocet_LH_x * rozmer_x[orient_LH] * pocet_LH_y *
> rozmer_y[orient_LH]
> + pocet_PH_x * rozmer_x[orient_PH] * pocet_PH_y *
> rozmer_y[orient_PH]
> + pocet_LD_x * rozmer_x[orient_LD] * pocet_LD_y *
> rozmer_y[orient_LD]
> + pocet_PD_x * rozmer_x[orient_PD] * pocet_PD_y *
> rozmer_y[orient_PD];
> if plocha > max_plocha then begin
> max_plocha:=plocha;
> // kontrolni vypis
> writeln('Pokryta plocha:
> ',plocha/(papir_x*papir_y)*100:3:2,' %');
> // zde doprogramovat ulozeni rozlozeni papirku
> end; //if
> end; //if
> end; //for
> end; //for
> end; //for
> end; //for
> end; //for
> end; //for
> end; //for
> end; //for
> end; //for
> end; //for
> end; //for
> end; //for
> readln;
> end.
> _______________________________________________
> HW-list mailing list - sponsored by www.HW.cz
> Hw-list@list.hw.cz
> http://list.hw.cz/mailman/listinfo/hw-list
> _______________________________________________
> HW-list mailing list - sponsored by www.HW.cz
> Hw-list@list.hw.cz
> http://list.hw.cz/mailman/listinfo/hw-list
_______________________________________________
HW-list mailing list - sponsored by www.HW.cz
Hw-list@list.hw.cz
http://list.hw.cz/mailman/listinfo/hw-list
Další informace o konferenci Hw-list