Evoluční algoritmy pro vytváření optimálních nářezových plánů

Univerzita Karlova v Praze Matematicko-fyzikální fakulta

BAKALÁŘSKÁ PRÁCE

Štěpán Balcar Evoluční algoritmy pro vytváření optimálních nářezových plánů Katedra teoretické informatiky a matematické logiky

Vedoucí bakalářské práce: Mgr. Martin Pilát Studijní program: Informatika Studijní obor: Programování

Praha 2012

Chtěl bych poděkovat všem lidem, co se mi za dobu mého studia na MFF UK věnovali a inspirovali mě svými znalostmi a zkušenostmi v oboru. Největší poděkování patří mému vedoucímu bakalářské práce panu Mgr. Martinovi Pilátovi za odborné vedení této práce, nekonečnou trpělivost a mnoho skvělých rad, které přispěly k napsání této práce. Také bych chtěl poděkovat mým rodičům za pomoc v průběhu tvorby této práce. Zvláštní poděkování patří mojí babičce Anežce a tetě Libuši za maximální možnou morální podporu.

Prohlašuji, že jsem tuto bakalářskou práci vypracoval samostatně a výhradně s použitím citovaných pramenů, literatury a dalších odborných zdrojů. Beru na vědomí, že se na moji práci vztahují práva a povinnosti vyplývající ze zákona č. 121/2000 Sb., autorského zákona v platném znění, zejména skutečnost, že Univerzita Karlova v Praze má právo na uzavření licenční smlouvy o užití této práce jako školního díla podle §60 odst. 1 autorského zákona. V . . . . . . . . dne . . . . . . . . . . . .

Podpis autora

Název práce: Evoluční algoritmy pro vytváření optimálních nářezových plánů Autor: Štěpán Balcar Katedra: Katedra teoretické informatiky a matematické logiky Vedoucí bakalářské práce: Mgr. Martin Pilát, Katedra teoretické informatiky a matematické logiky Abstrakt: Tvorba nářezových plánů velkoplošného materiálu pro kotoučovou pilu je praktický problém z mnoha oblastí průmyslu. Pro tento problém byl navržen speciální a specifický algoritmus. Všechny objekty, jak materiál, tak vzniklé podobjekty, jsou pravoúhlé a mají obdélníkový půdorys. Vzniklý algoritmus vytváří, kromě kotoučovou pilou rozřezatelného nářezového plánu, optimalizovaný seznam řezů a nářezů. Tato data mohou sloužit jako vstup pro bezobslužnou, plně automatickou kotoučovou pilu. Nový algoritmus přináší úsporu v množství potřebného materiálu k vyřezání požadovaných objektů, ale i další úspory v množství potřebné pracovní síly. Klíčová slova: evoluční algoritmy, nářezový plán, semigilotinovatelnost, velkoplošný materiál

Title: Evolutionary Algorithms for 2D Cutting Problem Author: Štěpán Balcar Department: Department of Theoretical Computer Science and Mathematical Logic Supervisor: Mgr. Martin Pilát, Department of Theoretical Computer Science and Mathematical Logic Abstract: Creation of optimal cutting plans is an important task in many types of industry. In this work we present a novel evolutionary algorithm designed to deal with this problem. The algorithm assumes rectangular shapes of the objects and creates a cutting plan which is can be cut out using a circular saw. The output is presented in a form usable by automatic saws as well as graphically. The algorithm reduces the amount of the material used and, moreover, also reduces the number of needed employees. Keywords: evolutionary algorithms, cutting plan, semiguilotinable, chipboard material

Obsah 1 Úvod 1.1 Příklad problému . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Příbuzné problémy a jejich řešení . . . . . . . . . . . . . . . . . .

3 4 5

2 Základní pojmy

7

3 λ-semi-gilotinovalnelnost 3.1 Specifikace problému . . . . . . . . . . . . . . . . . . . . . . . . .

8 13

4 Evoluční algoritmy 4.1 Evoluční algoritmus . . . . . . . . . . . . . . . . . . . . . . . . . .

14 14

5 Algoritmy - packing problém 5.1 Negilotinovatelné nářezové plány . . . . . . . . . . . . 5.1.1 Smithův algoritmus (1985) . . . . . . . . . . . . 5.1.2 Jakobův algoritmus (1996) . . . . . . . . . . . . 5.1.3 Liu a Teng algoritmus (1999) . . . . . . . . . . 5.1.4 Leung et al. algoritmus (1999) . . . . . . . . . . 5.1.5 Dagli a Poshyanonda algoritmus (1997) . . . . . 5.1.6 Lai a Chan algoritmus (1997) . . . . . . . . . . 5.2 Gilotinovatelné . . . . . . . . . . . . . . . . . . . . . . 5.2.1 Hwang et al. algoritmus - binární strom (1994) . 5.2.2 Rahmani a Ono algoritmus (1995) . . . . . . . . 5.2.3 András et al. algoritmus (1996) . . . . . . . . . 5.2.4 Hwang et al. algoritmus - permutace (1994) . . 5.2.5 Corno et al. algoritmus (1997) . . . . . . . . . . 5.2.6 Min-Lin algoritmus (2008) . . . . . . . . . . . . 5.3 Algoritmy s pozicováním . . . . . . . . . . . . . . . . . 5.4 Algoritmy s nepravidelnými objekty . . . . . . . . . . . 5.4.1 Bottom-Left-Fill Algorithm BLF (2005) . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

18 18 18 19 20 21 24 24 25 25 25 26 26 27 27 28 29 29

6 Vytváření nářezového plánu pro kotoučovou pilu 6.1 Zvolený evoluční algoritmus . . . . . . . . . . . . . 6.2 Testování rozřezatelnosti . . . . . . . . . . . . . . . 6.3 Převod nářezového plánu na graf . . . . . . . . . . 6.4 Řezání grafu . . . . . . . . . . . . . . . . . . . . . . 6.5 Algoritmus dekódování jedince . . . . . . . . . . . . 6.6 Algoritmus vkládání . . . . . . . . . . . . . . . . . 6.7 Odhad složitosti vytvořeného algoritmu . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

31 31 33 35 36 39 39 41

7 Experimenty 7.1 Příklady výstupů . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 Vylepšení algoritmu . . . . . . . . . . . . . . . . . . . . . . . . . .

42 49 51

Závěr

52

1

. . . . . . .

. . . . . . .

Přílohy

56

A Slovní popis algoritmů A.1 Převod nářezového plánu na graf A.2 Řezání grafu . . . . . . . . . . . . A.3 Algoritmus dekódování jedince . . A.4 Algoritmus vkládání . . . . . . .

57 57 57 61 61

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

1. Úvod Žijeme v době, kdy značná část řemeslné práce a průmyslové výroby se z důvodu větší efektivity a ekonomické výhodnosti přeměňuje na snahu, o co nejjednodušší a nejlevnější nakoupení a následné smontování podčástí výsledného výrobku. Jedná se o ekonomický trend, který z naší země vytváří kompletárnu jinde levněji vyrobených součástek a materiálů. Tato skutečnost se projevuje ve výrobních továrnách, ve stavebnictví, ale také v dodávkách spotřebního zboží. Jedná se o jasný důsledek rozdílnosti světových ekonomik a přívětivosti podnikatelského prostředí, vytvořeného jednotlivými státy. Následkem časté nekonkurenceschopnosti našeho výrobního sektoru je i značné zjednodušování práce v sektoru služeb. Příkladem tohoto vývoje ekonomiky na našem území je třeba transformace výrobních firem na pouhé obchodníky s univerzálními jednoduše smontovatelnými komponentami. Konkrétně se může jednat o společnost obchodující s libovolným velkoplošným materiálem, která prodává materiál na jednotlivé zakázky řadovým truhlářům, krejčím nebo klempířům. Z fungování tohoto typu firem můžeme jednoduše vyčíst snahu, o co nejúspornější vytvoření výsledného výrobku a co nejefektivnější spolupráci s jejich odběrateli. Díky stávajícímu ekonomickému vývoji je tento model přenositelný do velkého množství oblastí působnosti dnešních firem. Podnikatelské plány mohou pocházet z prostředí dřevoobchodu a následné kompletace nábytku, nebo prodeje atypických plechových dílů pro tvorbu nebo opravu karoserií automobilů. Případně se může jednat i o prodej kusů textilní látky pro šití oděvů na míru. Cílem mé bakalářské práce je vytvořit algoritmus, který by našel uplatnění při tvorbě softwaru určeného konkrétně pro dřevoobchod a jeho zákazníky. Výsledný program by měl sloužit k vytváření optimálních nářezových plánů pro kotoučovou pilu na velkoplošný materiál. Jde o hledání posloupnosti řezů, jejíž aplikací se ze vstupního materiálu získají požadované produkty. Následně si uvedeme modelový obchod dřevoobchodu. Truhlář přijde do dřevoobchodu nakoupit materiál na konkrétní zakázku. Zná rozměry a počty dílů, které bude potřebovat na vytvoření výsledného kusu nábytku. Mezi nezbytné specifikace každého dílu patří směr zbarvení dekorem, materiál, ze kterého se bude díl vyřezávat, počet kopií, šířka a výška v milimetrech. Prodejce dostane tímto jednoznačně zadané díly, které si chce truhlář koupit pro svoji zakázku. Dřevoobchod má tedy na skladě desky velkoplošného materiálu a jejich zbytky, zná požadavky odběratele a musí nalézt, co možná nejlepší nářezový plán, pro co nejlevnější uspokojení požadavků truhláře. Desky velkoplošného materiálu jsou na skladě v tovární velkosti, ale jsou k dispozici i levnější zbytky z předchozích řezání a cílem je vytvoření nářezového plánu, který bude co možná ekonomicky nejvýhodnější. Odpadem z řezání nazveme nevyužité oblasti materiálu s výjimkou části poslední desky. V případě, že poslední velkoplošná deska byla využitá pouze z části, je snahou maximalizovat vzniklý zbytek. Tento a další nevyužité kusy se opětovně přednostně použijí při další zakázce, která vyžaduje stejný typ materiálu velkoplošné desky. Velkoplošným materiálem nejčastěji myslíme takzvané lamino nebo slabší sololit. 3

Struktura těchto desek je tvořena tvrzenou dřevotřískou potaženou slaboučkou vrstvičkou dekoru. Největší předností lamina bývá cenová dostupnost a věrohodná imitace dřeva. Desky se vyrábějí v různých tloušťkách, tedy síle pevnosti. Materiál je absolutně nehomogenní a tudíž jediný možný způsob, jak lamino rozřezat, je pomocí kotoučové pily. Využitím jiných druhů pil se nevyhneme roztřepenosti dekoru a viditelnému okousání oblasti okolo řezu. Nevýhodou tohoto způsobu řezání je neschopnost udělat rovný řez ve směru tloušťky lamina a nutnost testování rozřezatelnosti výsledného nářezového plánu. Kotoučová pila totiž není schopná rozřezat všechny případně vytvořené nářezové plány, protože každé naříznutí lamina nám na konci řezu zanechá stopu po oblouku kotouče pily. Tento oblouček může způsobit buď nedoříznutí aktuálního dílu, nebo případně poničení sousedního dílu. Co možná nejlepší vytváření nářezového plánu může tedy paradoxně obsahovat také strategické rozmisťování prořezů mezi jednotlivými díly lamina. Rozmisťováním prořezů myslíme záměrné vytváření mezer mezi díly lamina. Vhodně umístěný prořez může zajistit nutnou rozřezatelnost, neboť nářezový plán, podle kterého nejsme schopni řezat kotoučovou pilou, je i třeba přes nízké procento prořezů pro naše účely bezcenný.

1.1

Příklad problému

Uvedeme si příklad toho, jaký problém by výsledný algoritmus měl řešit. Na vstupu dostane rozměry produktů, rozměry zbytků desek materiálu z minulé zakázky a tovární rozměry desek materiálu. Z tloušťky desky materiálu a z rozměru kotouče pily, používající se pro řezání aktuálního typu materiálu, můžeme dopočíst velikost obloučku, který bude vznikat. Produkty: počet, šířka, výška 1 krát 500 x 500 5 krát 1000 x 800 4 krát 800 x 600 . .

Materiál: počet, šířka, výška, tloušťka 1 krát 2500 x 1500 1 krát 5000 x 3000 1 krát 5000 x 3000 . .

Tabulka 1.1: Příklad vstupu

Obrázek 1.1: Příklad nářezového plánu (zbytek + 2x tovární velikost) Výstupem softwaru bude kotoučovou pilou rozřezatelný a co možná na množství odpadů a množství použitých desek materiálu nejúspornější nářezový plán. Vý4

stupem by měla být posloupnost řezů potřebných k rozřezání nářezového vzoru. Posloupnost by měla být optimalizovaná tak, aby truhlářovi ulehčila co nejvíce práce s manipulací s velkoplošným materiálem.

1.2

Příbuzné problémy a jejich řešení

Problém hledání rozřezatelného nářezového plánu, s co nejmenším počtem prořezů, jde částečně přeformulovat na známý packing problém. Tento můžeme dělit podle více kritérií. Dělení se nejčastěji uvažuje podle materiálu, ze kterého se vyřezává nebo podle způsobu vyřezávání produktů.

Dělení podle požadavku na materiál Každý materiál se vyznačuje specifickými vlastnostmi. Tyto vlastnosti pak předurčují možné způsoby výroby a dopravy meziproduktů. Pro přepravu a manipulaci bývá nejdůležitější flexibilita a tvarovatelnost materiálu. Kvůli těmto vlastnostem vzniklo následující dělení. ● Problém minimálního počtu kontejnerů - Bin packing problém ● Problém naplňování zásobníku - Strip packing problém Problém minimálního počtu kontejnerů Tento problém spočívá v co nejefektivnějším umístění malých desek do desek větších. Cílem je maximální využití velkých desek a získání co nejmenšího počtu prořezů. Příkladem problému může být získávání komponent pro tvorbu nábytku. Materiál na vytvoření výrobků tohoto typu bývá z konstrukčních důvodů dodáván ve formě desek. Problém naplňování zásobníku Opět se jedná o umisťování malých desek do co nejmenšího prostoru. Tento prostor je ale nekonečný pás daného materiálu o určité šířce. V tomto případě jsme tedy omezeni jen šířkou pásu daného materiálu. Snahou je naskládat malé produkty tak, abychom minimalizovali délku využitého pásu. Jako příklad využití uvedeme textilní výrobu. Textilní materiál bývá kvůli své flexibilitě dodáván ve formě role.

Dělení podle požadavku na způsob řezání Řezací technika se často dělí podle funkcí, které poskytuje. Specifikací se může docílit zjednodušení práce obsluze pily. ● Gilotinovatelné rozložení ● Negilotinovatelné rozložení

5

Rozdíl mezi gilotinovatelelností a negilotinovatelností spočívá v rozdílných možnostech, ve způsobu řezání. Přesné definice řezů, pomocí kterých se provádí oddělování v těchto případech, budeme definovat v následující kapitole.

6

2. Základní pojmy V této kapitole jsou vysvětleny základní pojmy, které budou používány v dalších částech práce. Tyto pojmy jsou inspirovány oblastí dřevovýroby, přestože popisují daleko širší a obecnější problém, který se neméně týká například textilního průmyslu nebo zpracovatelství plechů. Materiál a produkt Materiálem označujeme desku lamina, sololitu, dřevotřísky nebo jiného velkoplošného materiálu, který slouží jako základní surovina k výrobě levného nábytku. Z desky materiálu se vyřezávají produkty, ze kterých je nábytek jednoduše, jen s použitím vrutů a klížících kolíků, sestaven. Jako produkt označujme jednu z částí nábytku, který se v aktuální zakázce vyrábí. Je to podčást velké desky materiálu, kterou budeme podle vzniklého nářezového plánu vyřezávat. Zbytkem nazveme dolní nevyužitou oblast poslední desky materiálu. Tuto oblast můžeme použít při výrobě další zakázky. Odpadem nazveme všechny nevyužité části desek materiálu kromě zbytku. Řez, nářez a přířez Řez je dvojice souřadnic (x1 , y1) » (x2 , y2 ). Tyto souřadnice značí začátek řezu a konec řezu. Obě souřadnice musí být na hranici aktuálně nerozřezané desky materiálu. Dále musí platit, že x1 = x2 nebo y1 = y2 . Nebo-li řez kotoučovou pilou musí být rovnoběžný s okrajem materiálu. Nářezem, nebo-li naříznutím, nazýváme nedokončený řez kotoučovou pilou. To znamená, že souřadnice řezu na jedné straně hraničí s okrajem aktuálně nerozřezané desky materiálu. Druhá strana řezu se nachází uvnitř desky. Přířez je úzký proužek lamina, který se vkládá mezi produkty z důvodu rozřezatelnosti kotoučovou pilou. Vkládání přířezu se provádí jak na vertikální, tak na horizontální straně. Přířezy považujeme za nutný odpad zdrojového materiálu.

Materiály Dřevoobchody obchodují s různými typy velkoplošného materiálu. Pomineme-li zbarvení dekoru, desky materiálu se liší rozměry, pevností a konstrukcí. Obecně platí, že tenčí desky bývají méně pevné. Pevnost materiálu je způsobena vnitřními kovovými armaturami, tvořící oporu rozdrcené výplně. Lamino je 1,6 cm nebo 1,8 cm tlustá dřevotříska se slaboučkou povrchovou úpravou v barvě dřeva. Sololit je 3,0 mm tlustá pružná dřevotříska se slaboučkou povrchovou úpravou ve stejné barvě jako lamino. Používá se jako zadní strana skříní a na místech, kde není nutný materiál s větší pevností. Sololit bývá třikrát až čtyřikrát levnější než lamino. Tento materiál jen zřídka obsahuje vnitřní kovové armatury, proto bývá velmi pružný.

7

3. λ-semi-gilotinovalnelnost Pila, kterou je řezán velkoplošný materiál v dřevoobchodě, musí být kotoučová. Jen taková pila je schopna provést rovný čistý řez. Použitím jiné pily bychom se nevyhnuli roztřepeným a okousaným okrajům vrchní vrstvičky lamina nebo sololitu. Kotoučová pila je schopná rozřezat neomezeně velkou desku materiálu s přesností řezu na setiny milimetru. Šířka kotouče není v tomto měřítku zanedbatelná, ale výsledný software nezohledňuje žádnou šířku kotouče. V případě potřeby, jde ke každému produktu připočítat šířku jednoho řezu z každé strany. Tento způsob připočtení sice teoreticky rozbíjí přesnost rozměrů krajních produktů. Ve skutečnosti se nerovné okraje velké desky také běžně ještě před začátkem řezání o velmi malý kousek zařezávají z důvodu odstranění poruch materiálu vzniklých v průběhu přepravy z výrobní továrny. Proto zanedbání šířky pily neomezuje výsledný software a neovlivňuje přesnost výsledků programu.

Obrázek 3.1: Kotoučová pila

Vzdálenost, kterou naopak nezanedbáme, máme vyznačenou na obrázku nad písmenem delta. Delta udává délku obloučku po kotouči, který pila zanechává ve velkoplošném materiálu při naříznutí nějakého řezu. Při řezech přes celou délku zatím λ-nerozřezané desky materiálu žádný oblouček po kotouči nevzniká, ten vzniká jen při nedokončených řezech, takzvaných nářezech. Velikost vzniklého obloučku po kotouči se mění v závislosti na velikosti kotouče a na tloušťce řezaného materiálu. Obvykle délka vzniklého obloučku je přibližně stejně veliká, jako tloušťka řezaného materiálu. Co máme k dispozici K řezání je určena pouze popisovaná kotoučová pila a není možné použít žádný jiný stroj pracující na jiném principu. Z tohoto důvodu nemůže být v truhlárně vyhotoven svislý nářez. Svislým nářezem myslíme nářez, který nekončí obloučkem po kotouči pily, ale na horní straně desky je nářez stejně dlouhý jako na spodní 8

straně desky. Průměr kotouče pily a křehkost kotouče vylučuje možnost natáčet pilu nebo i materiál v průběhu řezání, tudíž pila umí uříznout pouze rovné řezy a to s přesností na desetiny milimetru. Jedna z nutných podmínek na nářezový plán je rozřezatelnost. Tato vlastnost se dále nejčastěji dělí podle typu použitých řezů. Proto jako první zadefinujeme typy řezů. Pro rozdělení rozřezatelnosti budeme využívat této terminologie a podle výskytu řezů budeme dělit nářezové plány. Definice Gilotinovatelný řez je řez začínající na jedné straně materiálu a končící na druhé straně. Gilotinovatelné řezy jsou základním kamenem gilotinovalných nářezových plánů. Platí u nich, že jak začátek, tak konec řezu, se nachází na konci desky materiálu. Po provedení každého takového řezu dojde k rozdělení desky na dva samostatné kusy. Definice Nářez je řez začínající na jedné straně desky materiálu a končící uvnitř desky. Řez, který nerozděluje desku materiálu na dva samostatné kusy a končící uvnitř materiálu. Jedná se o další specifikaci řezů, které se vyskytují v nářezových plánech. Definice Oblouček po kotouči je část řezu nacházející se pod povrchem horní hrany desky materiálu na nedokončeném konci nářezu. Z vlastností kotoučové pily, které budou popsány později, vyplývá termín oblouček. Jedná se o stopu po kotouči pily, která zůstane v desce po nářezu materiálu. S tímto vedlejším efektem musí být počítáno při vytváření nářezových plánů, aby se zabránilo poničení sousedních produktů. Definice Rohový řez je dvojice dvou vzájemně kolmých nářezů, které se protnou v jednom bodě. Překřížením dvou nářezů může dojít také k oddělení rohového kusu desky materiálu. Musí zde být dodržen dostatečný vzájemný přesah nářezů, který je vynucen aktuální délkou obloučku. Definice Nářezový plán je gilotinovatelný, jde-li rozřezat pouze gilotinovatelnými řezy. Gilotinovatelnost nářezového plánu je zadefinována podle schopnosti rozřezat plán pouze pomocí gilotinovatelných řezů.

9

Dělíme-li nářezové plány podle typu řezů, pak se nejčastěji objevuje dělení na gilotinovatelné a negilotinovatelné nářezové plány. U gilotinovatelných plánů existuje posloupnost řezů vedoucí vždy přes celou v aktuálním kroku nerozřezanou desku materiálu. Toto kritérium zajišťuje velmi rychlý a méně pracný postup při řezání. Negilotinovatelným nářezovým plánům k rozřezání naopak nepostačí využít pouze gilotinovatelných řezů. Tuto třídu nářezových plánů představuje podle definice nadmnožina všech nářezových plánů s rozložením produktů, kde nedochází ke vzájemnému překrývání. Často se množinou negilotinovatelných nářezových plánů myslí právě doplněk ke gilotinovatelným. Negilotinovatelným nářezovým plánem se pak tedy nazývá každý plán, který nesplňuje žádná kritéria na způsob řezání. Produkty musí v této třídě nářezových plánů splňovat pouze podmínku korektního vložení bez vzájemného překrývání nebo přesahů ven z desky materiálu. Toto obvyklé dělení ale nepokrývá problém rozřezatelnosti kotoučovou pilou. Pro problém dřevoobchodu zadefinováváme novou třídu rozřezatelnosti, a to takzvanou λ-semi-gilotinovatelnost. Na rozdíl od gilotinovatelných nářezových plánů, u kterých se může využívat pouze gilotinovatelných řezů, u λ-semi-gilotinovatelnosti můžeme pro řezání využít jak gilotinovatelných řezů, tak nářezů. Schopnost rozřezat nářezový plán za použití těchto řezů, budeme používat jako definici λ-semigilotinovatelnosti, protože právě tyto řezy je schopná uříznout kotoučová pila. Obecně platí, že každý gilotinovatelný nářezový plán je λ-semi-gilotinovatelný. A také, že každý semi-gilotinovatelný nářezový plán je negilotinovatelný. V trojici těchto typů plánů nejsou žádné dvě třídy vzájemně ekvivalentní. Tudíž vlastnost λ-semi-gilotinovatelnost se nachází právě mezi gilotinovalnelností a negilotinovatelností. Podle λ-semi-gilotinovatelnosti se tedy dále dělí třída negilotinovatelných nářezových plánů.

Obrázek 3.2: Množinové uspořádání tříd problémů

Pro nářezy v λ-semi-gilotinovatelných nářezových plánech platí jistá omezení vycházející z konstrukce a z vlastností kotoučové pily. Popis pily se nachází v následující kapitole. Z technologie řezání kotoučovou pilou vyplývá, že chceme-li naříznout desku materiálu do nějaké vzdálenosti v celé tloušťce řezaného materiálu, budeme muset tento řez prodloužit minimálně o délku obloučku po kotouči pily. Prodloužení řezu můžeme použít, ale jen někdy, a to v těchto situacích:

10

• Nekončí-li řez podle nářezového plánu na konci aktuálního produktu, ale pokračuje-li dále v délce minimálně odpovídající délce obloučku po kotouči. • Nachází-li se za aktuálním produktem dostatečně široký odpad, kde by oblouček po kotouči pily nezpůsobil žádný problém. Tento odpad musí být dostatečně dlouhý, aby se tam oblouček po kotouči vešel. • Řez pokračuje, ale ne v dostatečné délce, ale můžeme využít odpadu nacházející se za koncem následujícího produktu. Prodloužení řezu nemůžeme provést v situaci, když se blíže než je délka obloučku pily nachází jiný produkt, který bychom tím pádem porušili. Ještě může nastat situace, kdy produkt je krajní a to z obou protilehlých stran, nebo-li nemá žádného souseda na těchto stranách. To ale znamená, že existuje řez přes celou aktuálně nerozřezanou desku materiálu. Nebo-li existuje gilotinovatelný řez.

Obrázek 3.3: Příklad nářezového plánu, který není ani gilotinovatelný ani λ-semigilotinovatelný pro λ > 0

Obrázek 3.4: Příklad nářezového plánu, který není gilotinovatelný, ale je λ-semigilotinovatelný pro λ < šířka mezery

11

Definice Pro dané X > 0 je nářezový plán λ-semi-gilotinovatelný v případě, že je nářezový plán rozřezatelný sekvenci gilotinovatelný řezů a nářezů s velikostí obloučku menší nebo rovné X bez poškození sousedních produktů. λ-semi-gilotinovatelnost nářezového plánu je zadefinována podle schopnosti rozřezat plán pouze pomocí gilotinovatelných řezů a nářezů. Pozorování Vlastnost λ-semi-gilotinovatelnost nářezového plánu je pro λ = 0 ekvivalentní tradiční definici negilotinovatelnosti. V případě, že se λ = ∞ je naopak λ-semigilotinovatelnost ekvivalentní s gilotinovatelností. Věta 1 Nechť Gr je optimální gilotinovatelné řešení a Sr je optimální λ-semi-gilotinovatelné řešení. Pak je Sr přinejhorším stejně dobré jako Gr . Důkaz Důkaz plyne z následující věty popisující závislost existence optimálnějšího, nebo stejně dobrého λ1 -semi-gilotinovatelného nářezového plánu, k již existujícímu λ2 -semi-gilotinovatelnému nářezovému plánu na rozdílné velikosti λ1 a λ2 . Problém hledání optimálního gilotinovatelného nářezového plánu můžeme jednoznačně převést na problém nalezení λg -semi-gilotinovatelného nářezového plánu, kde λg může nabývat libovolné velikosti. A problém porovnání optimality λ-semigilotinovatelného a gilotinovatelného nářezového plánu může být převeden na problém porovnání λ-semi-gilotinovatelného a λg -semi-gilotinovatelného nářezového plánu, kde λg = 2λ. Tato věta tedy popisuje specifický příklad následující věty. Tím pádem je věta dokázaná. Tato věta říká, že optimální semi-gilotinovatelné řešení je při nejhorším stejně dobré, jako optimální gilotinovatelné řešení. Tím, že řešení bude hledáno ve třídě λg -semi-gilotinovatelných nářezových plánů určitě nepřijdeme o možnost najít optimální řešení. Věta 2 Nechť S1 je optimální λ1 -semi-gilotinovatelné řešení a S2 je optimální λ2 -semigilotinovatelné řešení. Platí-li λ1 < λ2 pak S1 zabere přinejhorším tak stejně materiálu jako S2 . Důkaz Máme-li z jedněch vstupních dat vytvořené dva pro dané λi optimální nářezové plány S1 λ1 -semi-gilotinovatelný a S2 λ2 -semi-gilotinovatelný, kde λ1 < λ2 . Z definice nářezů a obloučku vyplývá, že nářezový plán S2 je λ1 -semi-gilotinovatelný. Tudíž výsledek hledání optimálního λ1 -semi-gilotinovatelného nářezového bude stejný nebo lepší než S2 .

12

3.1

Specifikace problému

Nyní můžeme formálně specifikovat cíl této práce. Je jím vytváření co nejekonomičtějších λ-semi-gilotinovatelných nářezových plánů pro velkoplošný materiál. Na vstupu dostaneme seznam rozměrů produktů, které chceme vyřezat z desek materiálu. Rozměr produktu získáme jako dvojici (výška, šířka). Specifikovány jsou také rozměry desky materiálu tovární velikosti (výška, šířka) a rozměry zbytků materiálu z předchozího řezání (výška, šířka). Dále je uvedena informace o tloušťce desek materiálu, ze které je odvozena velikost λ. Úkolem je umístit produkty do desek materiálu tak, aby vzniklý nářezový plán byl rozřezatelný a minimalizoval se počet prořezů. Produkty jsou prioritně umísťovány do zbytků desek materiálu. V okamžiku, kdy je vyčerpán seznam zbytků desek materiálu, v nářezovém plánu jsou použity desky tovární velikosti. Produkty nesmí být při umisťování do nářezového plánu otáčeny ani nakláněny. Výstupem programu by měl být nářezový plán ve formě optimalizovaného seznamu řezů o souřadnicích (x1 , y1, x2 , y2 ) - začátek řezu, konec řezu.

13

4. Evoluční algoritmy Jako způsob řešení daného problému, jsme zvolili evoluční algoritmy. Jedná se o obecné a nedeterministické algoritmy, které pro získání řešení problému hledají inspiraci v přírodě. Autoři těchto algoritmů se snažili využít Darwinovy teorie k vytvoření algoritmu, který by postupným nedeterministickým vylepšováním nějakého řešení vyvinul řešení, které je dostatečně dobré.

4.1

Evoluční algoritmus

Obecná podoba algoritmu vypadá jako cyklus ukončený právě tehdy, když nejlepší vytvořené řešení je už dostatečně dobré. Populace » Selekce » Křížení » Mutace » Elitismus » Populace

Obrázek 4.1: Vývojový diagram evolučního algoritmu

Každý průchod tohoto cyklu představuje vývoj jedné generace evoluce. První generace jedinců je náhodně vygenerována. V každé generaci se provádí výběr jedinců podle ohodnocovací funkce, křížení a mutace. Vzniklí jedinci jsou vloženi do další generace. Nejlepší prvky z předchozí generace jsou vkládány podle míry elitismu. Výsledkem algoritmu je na základě ohodnocovací funkce nejlepší získaný dekódovaný jedinec z poslední generace.

14

Gen: Alela: Generace: Populace Jedinec:

Část jedince, vyjadřuje určitou vlastnost Konkrétní hodnota genu Značí číslo průchodu přes hlavní cyklus, v každé generaci se obmění aktuální populace Množina jedinců v nějaké generaci Jedno řešení problému

Tabulka 4.1: Pojmy z oblasti evolučních algoritmů

Ohodnocovací funkce Jedinec představuje v evolučních algoritmech jedno zakódované řešení. Pro získání řešení se musí jedinec dekódovat a vzniklé řešení může být ohodnoceno pomocí ohodnocovací funkce(fitness funkce). Evoluční algoritmy vycházejí z Darwinovy teorie, kdy s největší pravděpodobností přežívá právě nejlepší jedinec. Ohodnocovací funkce má tedy za úkol přiřadit každému jedinci odpovídající hodnotu, která bude popisovat jeho kvalitu. Kvalita jedince je určována podle úspěšnosti řešení, které v sobě jedinec skrývá. Podle hodnoty fitness funkce můžeme jedince v aktuální populaci setřídit a následně podle jejich kvality vybírat do následující generace. Nultá generace jedinců může být vytvořena pouhým náhodným nagenerováním hodnot jednotlivých alel, průchodem přes určitý počet generací jsou řešení vylepšována, třeba až na nejlepší možné řešení problému.

Dekódování Dekódování je proces převedení jedince na řešení aktuálního problému. Tento proces se provádí nejen pro získání konečného řešení celé evoluce, ale dochází k němu u každého jedince v každé generaci. Získání řešení z jedince vyžaduje ohodnocovací funkce, která následně zkoumá kvalitu výsledku. Fitness funkce nehodnotí jedince, ale až dekódované řešení. Tudíž proces převodu jedince na řešení se bude provádět při každém ohodnocování jedinců. Složitost této operace bude tedy značně ovlivňovat běh celého evolučního algoritmu. Mluvíme-li o zakódování, jde o inverzní operaci. Přímé zakódování Přímé zakódování je jeden ze způsobů reprezentace řešení aktuálního problému. Jedinec představuje datovou strukturu, která skrývá přesně popsané řešení. Toto řešení je v chromozomu zaneseno a dekódování spočítá jen ve správném přečtení informací. Není proto nutná žádná dekódovací heuristika nebo jiný složitý algoritmus. Absenci heuristiky, která z jakýchkoli hodnot alel v jedinci vytvoří smysluplné řešení je právě znak přímé reprezentace. Dekódování v přímé reprezentaci vyžaduje data v chromozomu v přesném formátu. Datové struktury v rámci chromozomu bývají mnohem složitější a dekódování částečně znamená znovupostavení datové struktury a interpretaci dat uložených v jedinci. Jako příklad přímého zakódování může být uvedeno třeba pozicování souřadnic jednoho rohu každého produktu. Operátory u přímé reprezentace bývají mnohem složitější než 15

u jiných reprezentací. Důležité je, aby byla zachována konzistence a smysluplnost dat a aby z těchto dat později šla vytvořit potřebná datová struktura. Jako příklad bychom mohli uvést výměnu souřadnic u části produktů. Operátory křížení bývají v těchto situacích velmi těžko zkonstruovatelné, protože musí zajistit, aby se produkty, které se vzájemně překrývají, posunuly do nekolidujících pozic. Nepřímé zakódování Zakódování označujeme za nepřímé, když jedinec neobsahuje přesný popis jak vytvořit řešení, ale obsahuje jen nutné informace, ze kterých jde konkrétní řešení odvodit. Nepřímé zakódování ukrývá pouze vstupní data pro nějakou dekódovací heuristiku, která spočítá, jak by v jedinci ukryté řešení mohlo vypadat. To, že informace, které je program při dekódování schopný dopočítat se do jedince vůbec neukládají, má spoustu výhod. Dekódovací heuristika pak dokáže z jakýchkoli dat požadované délky vytvořit smysluplné řešení daného problému. Je-li řešení takto zakódováno, není problém navrhnout jednoduché operátory, které někde nějaký gen trochu pozmění nebo nějaké části chromozomu přehodí. Ať udělá operátor s chromozomem vlastně cokoli, heuristika vždycky dokáže řešení smysluplně dekódovat. Příkladem reprezentace je chromozom ve formátu permutace určující pořadí objektů. Na základě pravidel a informací o objektech, které nejsou uvedeny v žádném jedinci, jsou pak objekty dále zpracovávány.

Selekce Selekce představuje algoritmus výběru jedinců z aktuální generace. Výběr se provádí za účelem získat jedince do další generace nebo pro potřebu nějakého genetického operátoru. Výběr je řízen na základě hodnot přidělených jedincům ohodnocovací funkcí. Pomocí ohodnocovací funkce dokážeme jednoznačně určit kvalitu jedince, vybíráním pouze podle kvality jedince dochází k velmi rychlému profilování výsledku celé evoluce. Pak dochází k předčasné konvergenci k nejbližšímu lokálnímu extrému. Snahou je zapojit do procesu výběru více faktorů, aby docházelo k efektivnímu prohledávání celé množiny řešení.

Křížení Křížení je genetický operátor vytvářející ze dvou jedinců dva nové jedince. Tato metoda vychází z idey pohlavního rozmnožování v přírodě, kdy se genetický materiál rodičů přesune do jejich potomků. Potomci našich jedinců, tak zdědí určité vlastnosti od svých rodičů, záleží vždy pouze na tom, jaké vlastnosti potomek získá od jednoho rodiče a jaké od druhého. Potomek pak může být výrazně horší než je každý z jeho rodičů, nebo může získat od obou dobré vlastnosti a může vzniknout lepší řešení aktuálního problému. Tento genetický operátor se snaží ze dvou řešení vytvořit dvě odlišná a lepší řešení. Dochází k novému kombinování předešlého genetického materiálu, nebo-li ke vzniku jiných řešení zadaného problému, což se může pozitivně projevit v dalších generacích evoluce.

16

Mutace Mutace je genetický operátor, který mění náhodně vybraného jedince. Změnou vzniká jiný jedinec, nebo-li nové řešení, které by mohlo být prospěšné v dalších generacích. Operátor závisí na způsobu dekódování. Z nově vzniklého jedince musí po dekódování vzniknout řešení. Na tuto skutečnost se primárně nesmí zapomínat u přímé reprezentace řešení. Kde jedinec, pro to aby mohl být úspěšně dekódován, musí splňovat některé vlastnosti.

Elitismus Elitismus je způsob, jak zachovat nejlepší řešení z aktuální generace do následující generace jedinců. Nejlepších N jedinců je automaticky přeneseno do další generace. Velikost N udává míru elitismu, což je parametr operátoru. Na jedince se neaplikuje křížení ani mutace, což zajišťuje, že tyto jedinci zůstanou zachování v původní podobě. Automatická přítomnost těchto nejlepších řešení z předcházející generace v následující generaci zaručuje, že se řešení v průběhu evoluce nemůže zhoršit. Získává se tím jistota, že i když křížením a mutací získaní jedinci budou horší než jejich rodiče, o již získaná lepší řešení se nepřijde. Elitismus je vlastně obrana proti nevhodné mutaci a neúspěšnému křížení.

Explorace a exploatace Explorace je název pro důsledek způsobu chování genetických operátorů evolučního algoritmu. Explorací nazýváme hledání nových možných cest, které by vedly k lepším výsledku v následujících generacích. Při exploraci se příliš nevyužívá současný genetický materiál, ale zkouší se najít jedinec, který by přinesl nový potenciál pro další evoluci. Příliš častou snahou nalézat nové oblasti řešení se může stát, že evoluce nedostane šanci stávajícího jedince vylepšit ve velmi úspěšné řešení. Exploatace je vlastně protipříklad k exploraci ve smyslu hledání nových jedinců v průběhu evoluce. Exploatace se liší v tom, že maximálně využívá aktuální genetický materiál a snaží se ho co nejvíce využít k vylepšení stávajícího řešení. Exploatace se vůbec nezaměřuje na hledání úplně jiného způsobu řešení daného problému, ale snaží se jen smysluplně přeformulovat předchozí řešení. Přehnaným používáním exploatace nemusí evoluce najít ani přibližně nejlepší možné řešení, ale může skončit neúspěšnou snahou vylepšovat neuspokojivé řešení.

17

5. Algoritmy - packing problém Uvedeme si nejznámější evoluční algoritmy pro packing problém. A to z obou, pro naši truhlárnu, zajímavých oblastí. Ze začátku se budeme zabývat algoritmy pracujícími pouze s obdélníkovými a čtvercovými deskami a produkty. Seznámíme se ale i s algoritmy, které dokáží vytvořit nářezový plán pro nepravidelné produkty.

5.1

Negilotinovatelné nářezové plány

V této části uvedeme algoritmy, které vytvářejí nářezový plán, který nemusí být gilotinovatelný. Nepovinná gilotinovatelnost se jako charakteristika vyskytuje u algoritmů, pracující s materiály a řezací technikou, u kterých jsme schopni bez jakýchkoli omezení vyříznout libovolný krajní produkt. Zakódování Nářezový plán je zakódován do jedince nejčastěji následujícími způsoby. Jedinec bývá reprezentován jako permutace identifikátorů produktů nebo strom uzlů, kde každý uzel reprezentuje produkt. Rozdílnost zakódování přináší různé operátory s různými efekty na straně explorace a exploatace. U stromové reprezentace se využívají přehozy podstromů u mutace. Operátory křížení obsahující rozdílné postupy kombinování podstromů, jejichž implementací dochází ke vzniku nových generací jedinců. Permutace nám udává jedno z možných pořadí produktů. V tomto pořadí jsou produkty vkládány příslušným algoritmem do desky materiálu. Permutace je tedy pole o délce počtu produktů. Jedinec v tomto případě obsahuje pouze permutaci identifikátorů produktů a je závislý na dalších dodatečných informacích. Pro dekódování musí mít jedinec přístup k seznamu převádějící identifikátory produktů na informaci o šířce, výšce a otočení produktu. Strom je druhé nejčastěji používané zakódování jedince. Toto zakódování umožňuje zakódovat mnohem více informací. Jako uzly jsou kódovány produkty a hrany grafu reprezentující sousedské vztahy. Jedno z možných kódování je binární strom, kde jeden syn je první vodorovný sousední produkt a druhý syn je první svislý sousední produkt. Do každého uzlu jde zakódovat informaci o rozměrech aktuálního produktu. Strom může být v jedinci reprezentován jako samotný strom nebo jako řetězec vrcholů v polské notaci.

5.1.1

Smithův algoritmus (1985)

Smithův algoritmus [9] je jedním z nejobecnějších algoritmů řešící bin packing problém implementující dva nejzákladnější způsoby dekódování jedince. Tento algoritmus implementuje rotace produktů jako jeden ze způsobů mutování. Pro uchování informací o stávajícím natočení je potřeba rozšířit datový model jedince. Algoritmus využívá jednoho z heuristických algoritmů Slide-Pack nebo Skyline(viz níže), který v pořadí určené permutací určí pořadí produktů v desce 18

materiálu. Algoritmus tedy nezapisuje konkrétní cílové řešení do jedince, ale zapisuje do jedince jen vstupní data pro jeden z heuristických algoritmů vytvářející výsledný nářezový plán. Operace křížení a mutace se tedy provádí bez znalosti aktuálního kontextu a smysluplnosti dané operace. Autor tohoto algoritmu uvádí, že algoritmus je časově efektivnější než jiné heuristické metody řešící packing problém. Slide-pack algoritmus Do jednoho horního rohu desky materiálu je umístěn produkt. Tento produkt pak „padá„ směrem ke vzdálenějšímu dolnímu rohu desky. Padáním myslíme kličkování směrem do stabilní polohy. Horizont (Skyline) algoritmus Algoritmus vyzkouší všechny stabilní pozice produktu v desce materiálu. Jedna z pozic je následně vybrána. Způsob výběru jedné pozice závisí na detailech úlohy. Problém Reprezentace Dekódování Fitness Křížení Mutace

Packing of single closed bin, 90◦ rotace Permutace Slide-Pack algoritmus, Skyline algoritmus Procento odpadů Jednobododvé křížení Náhodné přehození, rotace

Tabulka 5.1: Popis - Smithův algoritmus

5.1.2

Jakobův algoritmus (1996)

Jakobův algoritmus [3] řeší problém strip packing s možností rotace produktů pomocí mutace. Zakódování řešení v jedinci je řešeno opět pomocí permutace produktů a následné heuristiky. Algoritmus využívá k dekódování Bottom-left heuristiku. Před vytvořením nulté generace jsou produkty setříděny podle své šířky od největšího po nejmenší. Podle tohoto pořadí jsou vytvoření počáteční jedinci, kteří jsou přidáni do počáteční nulté generace. Toto setřídění zajistí, že produkty, které budou s největší pravděpodobností spolu sousedit, budou mít stejný jeden rozměr a zamezí se tvorbě prázdných míst uvnitř rozložení. Bottom-left algoritmus (BL) Do pravého horního rohu desky materiálu je umístěn produkt. Produkt je pak „posunut„ směrem co nejvíce dolů a co nejvíce doleva. Toto posunutí dolů a doleva může být provedeno vícekrát za sebou, ale může být také provedeno pouze jednou. Nakonec se zkontroluje, jestli je produkt ve stabilizované poloze. Algoritmus ne vždycky umístí produkt do nejnižší možné pozice. V průběhu vodorovného přesunu produktu se již netestuje možnost sestupu. Posunutí doleva je vždy dokončeno a teprve pak se uvažuje posun směrem dolů. Použitím menšího počtu opakování posunů směrem dolů se zmenšuje počet operací v heuristice, a tudíž 19

se sníží časová složitost dekódování jedince. Příklad vkládání produktu můžeme vidět na následujícím obrázku 5.1.

Obrázek 5.1: Příklad vytváření nářezového plánu Bottom-left algoritmu (BL)

Problém Reprezentace Dekódování Fitness Křížení Mutace

Strip packing, 90◦ rotace Permutace BL algoritmus Délka spotřebovaného materiálu Jednobododvé křížení Náhodné přehození dvou elementů, rotace

Tabulka 5.2: Popis - Jakobův algoritmus

5.1.3

Liu a Teng algoritmus (1999)

Liu a Teng algoritmus [10] je velmi podobný Jakobovému algoritmu. Jako heuristika se využívá vylepšený Bottom-left algoritmus (BLLT) a křížení je dvoubodové. Bottom-left Liu a Teng algoritmus (BLLT) Vylepšená heuristika vycházející z BL algoritmu, přidána je pouze priorita posunutí směrem dolů. Tento algoritmus se snaží umístit aktuální produkt co nejníže a tím ušetřit materiál. Nalezení nejlepší možné pozice, ať je měřítkem jakákoli vlastnost, není ovšem zaručena. Jde jen o změnu priorit posunu pro nalezení první stabilní pozice, ze které již nemůže být produkt posunut ani směrem dolů ani doleva. Dekódování využívající tuto heuristiku dosahuje lepších výsledků, ale přibývá počet operací a tím pádem jsou zde větší nároky na čas. Příklad vytváření nářezového plánu můžeme vidět na následujícím obrázku 5.2.

20

Obrázek 5.2: Příklad vytváření nářezového plánu Bottom-left Liu a Teng algoritmu (BLLT) Problém Reprezentace Dekódování Fitness Křížení Mutace

Strip packing, 90◦ rotace Permutace Vylepšený BL algoritmus Délka spotřebovaného materiálu Dvoubododvé křížení Náhodné přehození dvou elementů, rotace

Tabulka 5.3: Popis - Liu a Teng algoritmus

5.1.4

Leung et al. algoritmus (1999)

Leung et al. algoritmus [11] řeší problém strip packing bez možnosti rotace produktů. Využívá více křížících operátorů, které se specifikují až podle přesného zadání problému. Order crossover (OX) Jedná se o operátor křížení, který na vstupu dostane dva jedince zakódované jako permutace. Výsledkem křížení jsou dva noví jedinci. Náhodně se vygenerují dva indexy. Tyto indexy určí část chromozomu, která se beze změn přesune z chromozomu předků do výsledných jedinců. Oblast mezi indexy v prvním chromozomu se přesune do prvního výsledného chromozomu a oblast z druhého rodičovského bude přesunuta do druhého výsledného. Zbylé geny 5.3 ve výsledných chromozomech se zaplní hodnotami, které se v něm nevyskytují. Zaplňuje se v pořadí, ve kterém se geny nacházejí v předcích. U prvního jedince se začne zaplňovat od druhého indexu a u druhého jedince od indexu nula.

21

Obrázek 5.3: Příklad Order crossover (OX)

Cyclic crossover (CX) Tento operátor vytváří ze dvou jedinců nové dva jedince. Chromozomy jsou napsány pod sebe a jsou převedeny na posloupnost cyklů. Každý druhý cyklus je převrácen a opět vrácen do posloupnosti. Ze vzniklých 5.4 cyklů se vytvoří opět dvě permutace.

Obrázek 5.4: Příklad Cyclic crossover (CX)

Problém Reprezentace Dekódování Fitness Křížení Mutace

Strip packing, bez rotace Permutace Různé Minimalizace ztráty materiálu na prořezech PMX, CX, OBX, OX (jednobodové, dvoubododvé) Náhodné přehození dvou elementů

Tabulka 5.4: Popis - Leung et algoritmus

22

Partially-mapped crossover (PMX) Operátor partially-mapped implementuje křížení, kde se ze dvou rodičovských chromozomů vytváří dva noví jedinci. Prvním krokem je rozdělení vstupních chromozomů. Z délky chromozomu jsou spočítány dva indexy, které dělí chromozom na tři přibližně stejné části. Podle těchto indexů rozdělíme oba dva vstupní chromozomy a prostřední část obou chromozomů vložíme do výsledných chromozomů. Prostředek prvního výsledného chromozomu 5.5 bude tvořen z prostředku druhého vstupního chromozomu a prostředek druhého výsledného chromozomu bude tvořen z prostředku prvního vstupního chromozomu. Jde vlastně o prohození třetiny genů. Geny z prvního rodičovského chromozomu se přesouvají na stejné indexy do prvního vzniklého jedince za předpokladu, že vzniklý chromozom danou hodnotu genu nezískal prohozením prostřední části chromozomu. Pokud se gen již v chromozomu nachází, použije se opakovaně funkce částečného mapování. Jedná se o zobrazení prostřední třetiny genů prvního jedince na prostřední třetinu druhého jedince. Tato funkce se aplikuje opakovaně, vždy na předcházející výsledek funkce, dokud není nalezena hodnota genu, která se v jedinci ještě nevyskytuje.

Obrázek 5.5: Příklad Partially-mapped crossover (PMX)

Order-based crossover (OBX) Operátor křížení, který ze dvou rodičovských chromozomů vytváří jeden nový chromozom. Na začátku je náhodně vygenerováno přibližně N/2 pozic nacházející se v chromozomu. Z vygenerovaných pozic jsou v prvním rodičovském chromozomu vybrány hodnoty genů a tyto hodnoty genů jsou vloženy do nového jedince na stejné indexové pozice, na kterých se geny nacházely v prvním rodičovském chromozomu. Vznikne tak nový jedinec 5.6 s dírami na zbylých indexech. Do vzniklých děr doplní geny, které nový jedinec ještě neobsahuje podle pořadí, ve kterém se tyto chybějící geny nacházejí v druhém rodičovském chromozomu.

23

Obrázek 5.6: Příklad Order-based crossover (OBX)

5.1.5

Dagli a Poshyanonda algoritmus (1997)

Dagli a Poshyanonda algoritmus [12] hledá řešení pro problém strip packing s možností rotace jednotlivých produktů. Řešení je opět zakódováno do permutace a jako křížení se používá operátor Order crossover. Snahou algoritmu je přenést bloky informací z předchozí generace do další generace. Tyto bloky jsou vybírány sice náhodně, ale špatně vybrané bloky budou díky selekci jedinců do další generace odstraněny. Problém Reprezentace Dekódování Fitness Křížení Mutace

Strip packing, 90◦ rotace Permutace Posouvaní, Hledání nejlepšího místa pomocí neuronové sítě Minimalizace výšky OX Inverze

Tabulka 5.5: Popis - Dagli a Poshyanonda algoritmus

5.1.6

Lai a Chan algoritmus (1997)

Algoritmus [13] řeší problém bin packing, využitím heuristiky pro dekódování. Nevyužívá se zde žádné křížení a operátor pro mutaci bývá navrhován na konkrétní zadání problému. Operátory mutace tedy musí provádět jak exploraci, tak exploataci. Dekódování probíhá jako vkládání produktů v pořadí podle permutace do pozic, co nejblíže k dolnímu levému rohu desky materiálu. Problém Reprezentace Dekódování Fitness Křížení Mutace

Packing of single closed bin, bez rotace Permutace Umísťuje nejblíže k levému dolnímu rohu Minimalizace ztráty materiálu na prořezech Žádné Prohození dvou elementů, operátor podle problému

Tabulka 5.6: Popis - Lai a Chan algoritmus

24

5.2

Gilotinovatelné

Následující algoritmy vytvářejí nářezové plány, které jsou vždy gilotinovatelné. Zakódování Zakódování jedinců gilotinovatelných algoritmů se od negilotinovatelných příliš neliší. Využívá se opět binárních stromů nebo permutací. Rozdíl nejčastěji spočívá v přítomnosti heuristického dekódovacího algoritmu, který se postará o to, aby nářezový plán byl gilotinovatelný.

5.2.1

Hwang et al. algoritmus - binární strom (1994)

Algoritmus [14] řešící problém strip packing pro pravoúhlé objekty. Existují dvě možné implementace zakódování jedince a to přímý binární strom a sekvence úrovní jednotlivých produktů. Binární strom je tvořen z uzlů reprezentující jednotlivé produkty a synové každého uzlu jsou vždy horizontální a vertikální sousedé. Dekódování probíhá tak, že se prochází binární strom a produkty jsou umísťovány přímo za sebe podle horizontálních a vertikálních vztahů. Binární strom vlastně uvádí informaci pro každý produkt o dvou sousedech na vůči sobě kolmých stranách. Dekódování probíhá od kořene postupně přes všechny vrcholy až do listů, implementace se liší podle volby rohu desky materiálu pro umístění kořene stromu. Problém Reprezentace Dekódování Fitness Křížení Mutace

Strip packing pro pravoúhlé objekty, 90◦ rotace Řetězec reprezentující stromovou strukturu Procházení binárního stromu Délka spotřebovaného materiálu Výměna podstromů za určitých podmínek Prohození podstromů nebo obdélníků, změna orientace odbélníků

Tabulka 5.7: Popis - Hwang et al. algoritmus - binární strom

5.2.2

Rahmani a Ono algoritmus (1995)

Tento algoritmus [15] řešící problém bin packing na jednoduchých uzavřených objektech bez možnosti použít rotaci. Jedinec je zakódován jako strom, kde jednotlivé listy reprezentují produkty. Vnitřní listy určují vztahy mezi horizontálními a vertikálními pozicemi jednotlivých listů. Pro křížení byl vymyšlen operátor, který hledá k vybranému jedinci druhého jedince do páru. Tento algoritmus se od běžného evolučního algoritmu liší v tom, že jedinci se do další generace nevybírají, ale využívají se všichni jedinci, ke kterým se hledá druhý vhodný jedinec. Po nalezení vhodného páru jsou tito jedinci zkříženi. Křížení probíhá jako výměna podstromů. Vnitřní uzly obsahují informace o horizontálním a vertikálním uspořádání každé dvojice uzlů. Toto uspořádání nesmí operátory porušit.

25

Problém Reprezentace Dekódování Fitness Křížení Mutace

Packing of a bin (jednoduchých uzavřených), bez rotace Strom Procházení stromu Velikost využité oblasti Výměna podstromů za určitých podmínek inversion of cut-line; shifting of a cutting position

Tabulka 5.8: Popis - Rahmani and Ono algoritmus

5.2.3

András et al. algoritmus (1996)

András et al. algoritmus [16] je určený pro problém bin packing neumožňující rotaci objektů. Pro zakódování jedince se používá přímý strom, kde každý uzel reprezentující produkt, obsahuje informaci o poloze, rozměrech a orientaci. Fitness je odvozena od využitelnosti oblasti. Jedná se tedy o přímou reprezentaci a není nutné žádné dekódování. Problém Reprezentace Dekódování Fitness Křížení Mutace

Packing of a bin (jednoduchých uzavřených), bez rotace Strom Procházení stromu Velikost využité oblasti Výměna podstromů Používá se jako oprava nevhodně zvoleného křížení Tabulka 5.9: Popis - András et al. algoritmus

5.2.4

Hwang et al. algoritmus - permutace (1994)

Tento algoritmus [14] je druhou implementací Hwang et al. algoritmu řešící problém strip packing, využívající rozdílné zakódování jednice a to pomocí permutace. Sekvence úrovní produktů je vlastně jedna z forem zápisu permutace. Jedná se o pořadí v jakém se produkty pomocí dalších algoritmů skládají do levého dolního rohu. Pro skládání se využívá algoritmus First fit nebo Best fit. Vkládání se realizuje do posloupnosti obdélníkových úrovní, které jsou tvořeny vkládáním předešlých produktů. First fit (FF) je heuristika, která vkládá produkty do první možné úrovně v desce materiálu. Tento algoritmus je možné aplikovat i na problém bin packing. První možná úroveň se nachází v první velké desce, když se nepodaří vložení zrealizovat, začnou se zkoušet úrovně v následující desce materiálu. Vkládání produktu do úrovně se nezdaří buď z nedostatku místa, nebo případně z negilotinovatelnosti rozložení. Best fit (BF) je heuristika, která vkládá produkty do nejlépe vyhovující úrovně ve velké desce. Ohodnocování nejlepší úrovně může být realizováno více způsoby. Nejčastěji volíme způsob, kdy nejlepším umístěním nazveme pozici, která nejpřesněji odpovídá rozměrům produktu. Algoritmus je také možné aplikovat i na 26

problém bin packing. První možná úroveň se nachází v první velké desce, když se nepodaří vložení zrealizovat, začnou se zkoušet úrovně v následující desce materiálu. Vkládání produktu do úrovně se nezdaří buď z nedostatku místa, nebo případně z negilotinovatelnosti rozložení. Problém Reprezentace Dekódování Fitness Křížení Mutace

Strip packing, 90◦ rotace Permutace Úrovňově orientované FF, BF Šířka využité oblasti PMX Prohození dvou elementů, změna orientace

Tabulka 5.10: Popis - Hwang et al. algoritmus - permutace

5.2.5

Corno et al. algoritmus (1997)

Algoritmus [17] řeší problém bin packing s možností rotace a dalšími omezujícími podmínkami. Byl vymyšlen pro továrnu zpracovávající sklo a implementuje všechny technické detaily, které se při výrobě musí dodržovat. Problém se týká řady omezení jako gilotinovatelnost, minimální vzdálenost mezi řezy a možnost defektu skla v dané oblasti. Jedinec je zakódován jako permutace malých dílů skla, ale v jedinci jsou ke každému dílu skla uvedeny další informace týkající se otočení a umístění. Heuristický dekodér využívá těchto všech informací z chromozomu a pro tento problém upraveným BF algoritmem vyhledává nejlepší pozici pro umístění. Zároveň musí umístění splňovat omezující podmínky. Problém Reprezentace Dekódování Fitness Křížení Mutace

Packing of bin, řešící vady, rotace 90◦ , vzdálenosti Permutace + informace o otoční, umístění Heuristika zohledňující technologické překážky daného problému Velikost využité oblasti OBX Prohození dvou elementů, změna orientace, změna umístění Tabulka 5.11: Popis - Corno et algoritmus

5.2.6

Min-Lin algoritmus (2008)

Jedná se o adaptivní [5] algoritmus, který se využívá ve spojení s dalším evolučním algoritmem. Idea Min-Lin algoritmu vychází ze simulovaného žíhání. Tímto se zabraňuje uváznutí evoluce v lokálním minimu. Tato metoda se tomu snaží zabránit proměnlivou mírou křížení a mutace. Operátor křížení K náhodně vybranému jedinci je vybrán druhý jedinec, nikoli náhodně, ale vybere se nejvíce odlišný jedinec z celé populace. Použitý operátor pracuje s jedincem reprezentovaným permutací a tudíž hledá rozdíly na pozicích chromozomu. 27

Operátor mutace Z populace je náhodně vybrán jeden jedinec. Tento jedinec je ohodnocen a z celé populace je spočítána průměrná hodnota všech jedinců. V případě, že fitness náhodně vybraného jedince je větší než průměrná hodnota fitness, pak se zvýší pravděpodobnost mutace o příslušnou konstantu závislou na rozdílnosti fitness jedince a průměru fitness. Problém Reprezentace Dekódování Fitness Křížení Mutace

Packing of bin, řešící vady, rotace 90◦ , vzdálenosti Permutace, jiné typy reprezentací Heuristika Využitá oblast Křížení vždy dvou nejvíce odlišných jedinců různými operátory Pravděpodobnost mutace se mění na základě fitness jedince, různé operátory Tabulka 5.12: Popis - Min-Lin algoritmus

De Armas et al. (2011) De Armas et al. [6] je skupina evolučních algoritmů využívající hyper-heuristické zakódování. Jedná se o obecné využití kombinace zatím popisovaných evolučních algoritmů a jejich heuristik. Tyto algoritmy jsou použitelné jak bin packing, tak strip packing problémech většinou pro tvorbu gilotinovatelných nářezových plánů. Přichází s novým způsobem zakódování, specifickým tím, že jedinec je tvořen permutací objektů s dodatečnou informací, jakou heuristikou se bude daný objekt dekódován. Každý objekt pak obsahuje informaci o použité heuristice a úhlu otočení. Mezi použité heuristiky patří First Fit, Best Fit pro výšku nebo šířku, Next Fit. Jako operátory evoluce se využívá například upravené dvoubodové křížení. Fitnes se snažší minimalizovat počet prořezů. Next Fit Objekty jsou zarovnávány doleva až do doby, když se další objekt nepodaří vložit. Pak se objekt umístí o úroveň výše.

5.3

Algoritmy s pozicováním

Pozicování je alternativní způsob reprezentace vůči stromové nebo permutační reprezentaci. Jedná se o daleko přímější reprezentaci s úplně jinými operátory. Křížení ani mutace nemohou jen jednoduše změnit datovou strukturu, která bude vždy dekódována na řešení splňující všechny podmínky. Algoritmy s reprezentací založenou na přesné pozici produktu nepoužívají žádný náročný dekodér, který by z jakýchkoli pozic utvořil nářezový plán splňující dané rozměry. Tvorbě příslušnou pilou nerozřezatelných, rozměrově neproveditelných nebo nějakým jiným způsobem nevyhovujícím nářezovým plánům musí být v evolučním algoritmu zamezeno. Rozměrovou neproveditelností myslíme vzájemné překrývání produktů nebo vyčnívání části produktů z desky materiálu. Jedním způsobem 28

je použití složitějších operátorů, které nevytvoří žádného jedince neodpovídající podmínkám na výstupního jedince. Druhý způsob spočívá v penalizaci jedinců nevyhovujících podmínkám.

5.4

Algoritmy s nepravidelnými objekty

Problém vytváření nářezových plánů pro nepravidelné desky materiálu i produkty je v praxi daleko častější, než problém zabývající se objekty s obdélníkovým půdorysem. Nepravidelné objekty bývají často aproximovány pravidelnými, nejlépe obdélníkovými, objekty. Aproximují se jak desky materiálu z vnitřní strany, tak i produkty z vnějšku. Algoritmy se dělí podle pravidelnosti desek materiálů a podle reprezentace jedince. Evoluční algoritmus řešící problém s nepravidelnými objekty se od problémů s objekty obdélníkového půdorysu příliš neliší. Operátory křížení jsou velmi často jednobodové nebo vícebodové křížení případně upravené pro reprezentaci permutací. V případě použití stromové reprezentace se používá výměna podstromů. Jako operátor mutace se používá náhodné prohození dvou genů permutace nebo dvou podstromů binárního stromu. Jako dekódovací algoritmus se používají algoritmy podobné Bottom-left algoritmu pro permutaci nebo umisťování podle vztahů mezi produkty v binárním stromě. Algoritmy se liší ve složitosti heuristik dekódování, tyto heuristiky musí řešit daleko složitější prolínání sousedících objektů. Obtížnější bývá určit, jestli se dva produkty umístěné na konkrétních souřadnicích vzájemně překrývají. Na kotoučové pile je prakticky nemožné uříznout jiný než rovný řez nebo nářez. Tato skutečnost je dána délkou řezné úseče kotouče, která nemůže být v průběhu řezání ohýbána. Z tvaru pily je také nemožné vyříznout žádný uzavřený výřez uprostřed produktu. Všechny otvory musí být pracně odvrtávány a musí zde být počítáno s poničením dekoru lamina, které se schovává pod přechodové lišty. Pro problém s kotoučovou pilou přichází v úvahu pouze aproximace produktů núhelníky s tupými vnitřními úhly. N-úhelníky s tupými nebo pravými úhly jsou, pokud pile nepřekáží žádný sousední produkt, kotoučovou pilou vyřezatelné. V oblasti jako je prodej velkoplošného truhlářského materiálu bývají požadavky na nepravidelné produkty velmi ojedinělé. A v nejčastějších případech se jedná pouze o zkosení ostrých rohů obdélníkových desek. Proto bývá naprosto dostatečná pouze aproximace těchto nepravidelných produktů produkty obdélníkového půdorysu. V případě požadavku na n-úhelníkové produkty s půdorysem, který je tvořen z ostrých vnějších úhlů, musí být stejně vyříznut první objekt, kterým daný půdorys aproximujeme. Poté jsou teprve dořezány tupé rohy. Vyřezávání se provádí nejčastěji ručně použitím mechanické pily. Výsledky nejsou vždy stoprocentní, proto se truhláři snaží těmto konstrukčním prvkům v prvé řadě vyhýbat.

5.4.1

Bottom-Left-Fill Algorithm BLF (2005)

Jako příklad algoritmu [19] pracující s nepravidelnými objekty uvedeme BottomLeft-Fill algoritmus. Jedná se o heuristiku, která se zabývá dekódováním v bin packing problémech s nepravidelnými objekty s možností rotace. Produkty jsou 29

aproximovány pomocí kružnic a úseček. Pro takto aproximované objekty umí pak algoritmus BLF hledat optimální nářezový plán. Algoritmus Bottom-Left-Fill vychází z Bottom-Left algoritmu. Rotace nepravidelných objektů přináší spoustu problémů s nepredikovatelností vkládaných objektů. Algoritmus může využít základní idey jednoduchého posouvání produktů až do konečné stabilní polohy. Finální poloha je vybrána s vědomím, že dojde k překrytí vkládaného produktu s produkty, které se již v nářezovém plánu nacházejí. Bottom-Left-Fill heuristika si umí poradit využitím posunů se všemi typy překrývání objektů aproximovanými kružnicemi a úsečkami. Algoritmus poopraví aktuální rozložení a najde vhodné umístění pro produkt. V rámci vkládání heuristika vyzkouší všechny možné způsoby otočení produktu a vybere otočení nejvíce se přizpůsobující okolním objektům. Bottom-Left-Fill není přímo evoluční algoritmus, jedná se pouze o dekódovací heuristiku. Jako operátor se používá třeba náhodné vybrání dvou objektů a jejich prohození nebo vybrání náhodného tvaru a vložení na náhodně vybrané místo pomocí BLF algoritmu.

30

6. Vytváření nářezového plánu pro kotoučovou pilu Všechny výše popsané algoritmy řešily problém založený na vkládání produktů do materiálu. Tyto algoritmy se lišily ve vlastnostech rozřezatelnosti nářezového plánu, který byl vyprodukován. Problém vyřezání dílů kotoučovou pilou pro výrobu nábytku není jednoznačně převoditelný na žádný z předcházejících problémů. Algoritmy vytvářející negilotinovatelný nářezový plán nesplňují všechny nutné podmínky semi-gilotinovatelnosti. A algoritmy jejichž výstupem je gilotinovatelný nářezový plán naopak splňují více podmínek než je nutné. Protože gilotinovatelné ani negilotinovatelné nářezové plány neodpovídají nářezovým plánům určeným pro kotoučovou pilu, zobecnili jsme je na semi-gilotinovatelné nářezové plány. Vytvořili jsme tedy novou třídu problému. Problém vytváření semi-gilotinovatelných nářezových plánů se nachází mezi těmito problémy. Tato třída λ-semi-gilotinovatelných nářezových plánů dává prostor, pro vytváření nových algoritmů, které využívají užší specifikace problému. Pro vytváření semi-gilotinovatelných nářezových plánů byl vytvořen v rámci mé bakalářské práce nový algoritmus, který řeší konkrétně danou třídu problému. Tento algoritmus vytváří efektivnější nářezové plány, optimální pro řešený problém.

6.1

Zvolený evoluční algoritmus

V této části uvedeme specifické vlastnosti použitého evolučního algoritmu. Popíšeme použité operátory a parametry evoluce. Ohodnocovací funkce Fitness funkce vrací hodnotu, která vyjadřuje počet zcela využitých desek materiálu. Pro jednoduchost se zanedbává, zda se jedná o desku materiálu tovární velikosti, nebo jestli jde o zbytek z předchozího řezání. Za zcela využité se považují všechny desky materiálu až na poslední. U poslední desky materiálu se počítá velikost zbytku. Dopočítá se výška materiálu, která je potřebná k umístění všech produktů z poslední desky. Ze získané výšky využité oblasti funkce dopočte poměr využité a nevyužité části poslední desky. Fitness funkce vrací hodnotu počtu desek materiálu zmenšenou o poměr nevyužité části poslední desky. Tato fitness funkce automaticky počítá s tím, že největší nevyužitá část materiálu se nachází v poslední desce. Tato skutečnost je ale zaručena způsobem dekódování. Algoritmus dekódování také zajišťuje, že všechny vložené produkty se nacházejí v horní části materiálu a v dolní části každé desky se pak nachází odpad. Poslední, a díky dekodéru největší, odpad uvažovaný v tovární šíři může být proto považován za zbytek. Použitá fitness funkce tedy vrací počet využitých desek s tím, že poměr využitelnosti desky materiálu se počítá a následně započítává pouze u poslední desky. Tuto funkci se snažíme v průběhu evoluce minimalizovat. 31

Jako alternativu předcházejícího výpočtu fitness, bychom mohli někdy uvažovat pouze hodnotu výšky zbytku v poslední desce materiálu. Evoluce by pak ale neřešila potřebný problém. Naším cílem je minimalizovat počet desek materiálu a maximalizovat velikost zbytku v poslední desce. Takto zvolená funkce by pouze maximalizovala poslední zbytek a záměrně by zvětšovala počet desek použitého materiálu tak, aby na poslední desce zbyl jen jeden produkt s nejnižší výškou. Aby bylo zabráněno tomuto nežádoucímu chování funkce, tak se spočítá povrch nevyužitého prostoru v aktuálním nářezovém plánu. Hodnota nevyužité plochy bude v každé generaci stejná, jen s rozdílem počtu použitých desek materiálu. Přesahuje-li hodnota nevyužitelnosti velikost plochy jedné celé velké desky, pak dochází k penalizaci celé fitness funkce. Tato fitness nakonec nebyla v Přířezy algoritmu využita. Selekce V evolučním algoritmu používáme Turnajovou selekci (viz níže). Tento způsob selekce s vysokou pravděpodobností zaručí evoluci co možná nejširší výběr genetického materiálu. Selekce se postará o vybírání nových řešení a zajistí jim šanci na vylepšení a zdokonalení. Zároveň vybere ze souboje s určitou pravděpodobností lepší řešení. U Turnajové selekce se z populace vybírá náhodně N jedinců. Tito jedinci se spolu utkají v turnaji, ze kterého vyjde jako vítěz nejlepší jedinec. Jedinci se utkávají v souboji jeden proti jednomu a vítězem souboje se stává ten s lepší fitness s pravděpodobností P . Vítěz souboje dvou jedinců se utká v dalších soubojích a vítěz všech soubojů je vítěz celého turnaje. Turnaje se opakují dokud není vybrán potřebný počet jedinců. Pro výběr každého jedince je vybrána nová skupina N jedinců a uspořádán nový turnaj. Dekódování Jedinec je reprezentován jako permutace identifikátorů produktů. Každý produkt je identifikován číslem určeným podle pořadí, ve kterém byly jeho rozměry zadány na vstupu. Jedná se tedy o nepřímé zakódování. Dekódování je složené z hledání vhodného místa pro vložení produktu a ze samotného vložení. Tyto problémy řeší algoritmy popsané v sekci „vkládání produktů do desky materiálu„ a „vkládání produktu do interní podčásti desky materiálu„. Tato permutace může po dekódování reprezentovat následující nářezový plán 6.1. p = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 } Produkty se umisťují do co nejvíce vlevo a zároveň nejvíce nahoře položených volných míst jednotlivých desek materiálu. Tyto desky materiálu mají pevně dané pořadí. Jako první se vkládá do volných míst ve zbytcích z minulých řezání. Pozice pro případné vložení jsou reprezentovány jako utříděný seznam obdélníků, kde postupně do každého obdélníku zkusíme umístit vkládaný produkt. Algoritmus řeší i problémy se spojováním sousedních obdélníků. Po vložení každého obdélníku dojde k preventivnímu rozříznutí části obdélníků, aby se zjednodušil 32

převod interní reprezentace nářezového plánu na graf. Příklad vnitřní reprezentace nářezového plánu je vidět na následujícím obrázku 6.1.

Obrázek 6.1: Interní reprezentace nářezového plánu dvou desek materiálu

Pořadí desek materiálu do kterých se realizuje postupné vkládání je pevně dáno v implementaci softwaru. Nářezový plán je tvořen přednostně ze zbytků a až pak z desek materiálu tovární velikosti. Pořadí zbytků je dáno podle uspořádání na vstupu. Desky materiálu tovární velikosti jsou v pořadí, ve kterém do nich byly vkládány produkty. Elitismus Jako elitu vybíráme z každé generace jednoho jedince. Což v přepočtu dává vyšší míru elitismu, než je obvyklé u jiných problémů. Tento vyšší poměr je dán malou velikostí populace. Elitismu využíváme, protože při použité selekci nemáme jistotu, že nám přežije nejlepší jedinec. Použitím nepřímé reprezentace a málo konkrétních operátorů bychom jinak mohli o nejlepšího jedince přijít. Křížení Jako operátor křížení se používá vlastní implementace Partially-mapped crossover. Tento operátor prohazuje vnitřní třetiny chromozomů, zbytky chromozomu předka se postupně prochází a v případě, že se aktuální gen ještě nevyskytuje v potomkovi, pak je gen přenesen do potomka na stejnou pozici. V okamžiku, kdy se gen v chromozomu už nachází je použit první ještě nepoužitý gen z prostřední třetiny rodičovského chromozomu. Mutace Jako mutaci používáme operátor, který náhodně prohodí hodnotu dvou genů chromozomu. Nebo-li dochází k prohození dvou náhodně vybraných čísel v chromozomu. Díky nepřímému kódování může být použit tento jednoduchý operátor. Dekódovací heuristika dokáže totiž zpracovat jakoukoli vstupní permutaci.

6.2

Testování rozřezatelnosti

Pro samotné testování rozřezatelnosti nářezového plánu používáme vlastní algoritmus. Tento algoritmus nepracuje s nářezovým plánem, který máme reprezentovaný jako seznam odpadů a seznam produktů, ale pracuje s nářezovým plánem 33

převedeným do formy grafu. Právě proto se nejprve budeme zabývat převodem nářezového plánu na graf. Převod na graf Převod nářezového plánu na graf budeme provádět z důvodu jednoduššího a efektivnějšího zpracování dat algoritmem, který by měl rozhodnout o tom, jestli je nářezový plán rozřezatelný nebo není. Z rohů desek, které reprezentují odpady nebo produkty vytvoříme vrcholy grafu a z hran těchto desek vytvoříme hrany grafu.

Obrázek 6.2: Nářezový plán, Vrcholy grafu, Přidávání hran do grafu, Výsledný graf

Jednoznačnost grafu Z popsané grafové reprezentace nářezového plánu vyplývá, že jsou jednoznačně popsána pouze řezná místa. Řezná místa jsou v grafu reprezentována jako hrany grafu. Odpady a produkty tím pádem představují místa mezi každou čtveřicí vrcholů spojenou po obvodu. Tudíž z grafu není jasné jestli čtveřice vrcholů určuje odpad nebo produkt. Pro vyřezání všech produktů a odpadů tuto informaci vlastně znát ani nemusíme. Absence informace nám nebrání v použití zvoleného algoritmu na vkládání produktů do desky materiálu. Po vložení každého produktu musí být pak všechny odpady, který by mohly někdy bránit v rozřezatelnosti nářezového plánu kotoučovou pilou preventivně rozřezány. Specifikaci dílu materiálu udávající, zda je aktuální kus odpad nebo produkt, nutně potřebujeme v situaci, kdy chceme dělat optimalizace, které by vynechaly nepotřebné řezy, nebo sestavily posloupnost řezů podle nějakého kritéria. Proto jsou v každém vrcholu grafu vedeny informace o tom, jestli je soused na příslušné straně tohoto vrcholu odpad nebo produkt. Vzniklý graf je pak plně izomorfní s nářezovým plánem, který reprezentuje. Řezání grafu Pro dokázání rozřezatelnosti nářezového vzoru převedeme nářezový vzor na graf a ten se následně pokusíme rozřezat. Řezání grafu je vlastně procházení grafu rovnými gilotinovatelnými řezy nebo nářezy. Pro rozříznutí musíme najít buď dva vhodně protínající se nářezy, nebo jeden gilotinovatelný řez. Po vyhledání řezu použijeme implementovaný algoritmus, který graf vhodně rozdělí na dva 34

podgrafy. Při oddělování musí být zdvojeny vrcholy i hrany grafu v místech řezu. Řezání probíhá rekurzivně na obou podgrafech.

Obrázek 6.3: Celý graf(vlevo), Rozdělený graf s duplikátními vrcholy(uprostřed), Rozdělený graf bez duplikátních vrcholů(vpravo) Zdvojování vrcholů nemůže být prováděno úplně bez rozmyslu, protože některé vrcholy po rozříznutí grafu už nejsou potřebné a pro jednoznačnou reprezentaci nářezového plánu musí být odstraněny. Optimalizace řezání grafu Tvorba posloupnosti řezů a nářezů je optimalizována tak, aby se nejdříve do posloupnosti zařazovaly rovné gilotinovatelné řezy. V okamžiku, kdy v aktuálně nerozřezané velké desce nemůže být nalezen gilotinovatelný řez, začne být hledána dvojice nářezů, která rozdělí velkou desku na dva kusy. Tímto zajišťujeme jednodušší manipulaci s velkou deskou pro truhláře obsluhující pilu. Částečně docílíme i toho, že nevyužitý zbytek poslední desky materiálu zůstane vcelku a nebude rozřezán na více částí. Při dekódování jedince na nářezový vzor jsou produkty vkládány s preventivním rozřezáváním zbytků v úrovni hran vkládaného produktu. Interní reprezentace tedy obsahuje více míst k řezání, než je potřeba řezů k vyřezání všech produktů. Nebo-li místa k řezání oddělují vzájemně i dva odpady. Cílem je co největší ulehčení práce truhláři obsluhující pilu v ohledu počtu nařezaných řezů. Tudíž není nutné rozřezávat od sebe pouze odpady. Jako první se tedy upřednostňují řezy, které hraničí aspoň s jedním produktem. Skupina pospojovaných odpadů, neobsahující žádný produkt, se díky dodatečným informacím v grafu nebude rozřezávat a tato množina odpadů zůstane jako jeden celý odpad. Ve zbytku této kapitoly si detailně popíšeme algoritmy, ze kterých se skládá celý nový evoluční algoritmus. Algoritmus jsem pojmenoval Přířezy algoritmus, protože pro zajištění λ-semi-gilotinovatelnosti využívá v případě, že je to potřeba, vložení dvou přířezů. Algoritmy jsou popsány slovně, přesný přepis algoritmů v pseudokodu se nachází v příloze.

6.3

Převod nářezového plánu na graf

Vytvořený nářezový plán musí být otestován na rozřezatelnost kotoučovou pilou. Pro rozhodnutí, je-li nářezový plán rozřezatelný, je hledán seznam řezů a nářezů takový, že použitím této sekvence řezů dojde k získání požadovaných produktů. 35

Existence této sekvence jednoznačně dokazuje rozřezatelnost nářezového plánu. Jednodušší hledání řezů a nářezů umožní grafová reprezentace daného nářezového plánu.

Přidání vrcholů Přidávání vrcholů do grafu se provádí jako první krok pro převod na graf. Rohy produktů a rohy preventivně rozřezatelných odpadů jsou v grafové reprezentaci nářezového plánu reprezentovány jako vrcholy. Algoritmus sloučí všechny produkty a preventivně rozřezané odpady, postupně je všechny projde a z rohů každého objektu vytvoří vrcholy grafu. Duplikátní vrcholy jsou odstraněny. Výsledný seznam vrcholů tvoří základ grafu.

Přidání hran Přidání hran k již přidaným vrcholům do grafu je druhým krokem převodu. Tento algoritmus sloučí produkty a preventivně rozřezané odpady do jednoho pole. Pole postupně procházíme a pro aktuálně zpracovávaný prvek najdeme v grafu odpovídající čtyři vrcholy. Tyto vrcholy graf obsahuje, protože byly do grafu přidány. Postupně se na všech stranách aktuálního prvku zjistí sousední produkty nebo odpady. Má-li aktuální prvek na aktuální straně jednoho nebo žádného souseda, přidáme do grafu celou hranu. Má-li prvek pole více sousedů, pak jsou do grafu přidány pouze dvě hrany vedoucí z aktuálního vrcholu směrem k nejbližšímu sousednímu vrcholu na každé straně. Stejným zpracováním celého pole vznikne celý graf.

6.4

Řezání grafu

Existence posloupnosti řezů a nářezů, které vedou k získání požadovaných produktů, určuje rozřezatelnost grafu. Posloupnost řezů se tvoří podle optimalizačního algoritmu, který upřednostňuje řezy hraničící s aspoň jedním produktem. Díky reprezentaci preventivního rozřezávání odpadů, by bez použití této optimalizace seznam výsledných řezů obsahoval i řezy, rozřezávající pouze dva odpady od sebe. Algoritmus vyhledá gilotinovatelný horizontální, případně vertikální řez přes aktuální graf, který v některé oblasti hraničí s nějakým produktem. Není-li nalezen gilotinovatelný řez, algoritmus zkusí najít dva nářezy hraničící aspoň s jedním produktem na oddělení prvního možného pravého dolního podgrafu. Pokud žádný takový řez ani nářez neexistuje, je hledán gilotinovatelný řez horizontální a posléze vertikální bez ohledu na sousedy řezu. Není-li nalezen ani takovýto řez, pokusí se algoritmus najít dva jakékoli nářezy oddělující pravý dolní podgraf. Neexistuje-li žádný z těchto řezů ani nářezů je graf prohlášen za nerozřezatelný. Tento algoritmus není kompletní, rozšířením se budeme zabývat později. Bude se jednat o optimalizace, které povedou k úspoře materiálu a práce obsluhy pily. Najde-li algoritmus nějaký řez nebo dva nářezy, graf je rozříznut na dvě části, přičemž každá část je rekurzivně zpracovávána dokud v grafu existuje nějaký produkt k vyřezání. 36

Horizontální přeříznutí Přeříznutí grafu v horizontálním směru se volá z algoritmu řezání grafu v případě, je-li nalezen horizontální řez, nebo-li možnost graf v určitém místě rozdělit na dva kusy. Problémem ale zůstává rozdělení grafové reprezentace a změna informací o sousedech vrcholů grafu. Máme-li na vstupu řez grafem, nebo-li vrchol, ze kterého můžeme provést gilotinovatelné horizontální přeříznutí, vytvoříme prázdný horní a prázdný dolní podgraf. Do horního podgrafu přidáme všechny vrcholy s Y-ovou souřadnicí větší než je souřadnice řezu a dolního podgrafu všechny vrcholy se souřadnicí nižší než je souřadnice řezu. Vrcholy grafu s Y-ovou souřadnicí rovné souřadnici řezu musí být duplikovány a musí být změněny informace o sousedech těchto vrcholů. Z každého hraničícího vrcholu s řezem, který bude přidán do horního podgrafu musí být vymazány informace o všech dolních sousedech a vrchol musí být prohlášen za vertikálně okrajový. V případě, že vrchol byl označený jako tupý pravý dolní, nebo-li byl středem výřezu pravého dolního podgrafu, dochází provedením tohoto řezu k zarovnání grafu. Tudíž zaniká výřez pravého dolního rohu a informace o již neexistujícím výřezu v této části grafu musí být odstraněna. To také znamená odstranit identifikátor vertikálně okrajový vrchol. Podobně musí být přidány kopie s řezem hraničících vrcholů do dolního podgrafu. Musí být upraveny informace o sousedech, případně smazány informace o bývalém výřezu pravého dolního podgrafu. Výstupem jsou dva podgrafy, na které může být opět volán algoritmus řezání, v případě, že algoritmus řezání najde pro oba podgrafy seznam řezů, je vrácena kladná informace o rozřezatelnosti grafu. Vrchol značím jako tupý, když se právě v tomto vrcholu potkalo vertikální a horizontální naříznutí grafu. Vrchol je tím pádem okrajový ve vodorovném i svislém směru.

Vertikální přeříznutí Tento algoritmus řeší opět problém řezání grafu na vstupu, podle daného řezu. Výsledkem je také informace o tom, jestli je daný graf rozřezatelný. Na vzniklé podgrafy je stejně jako u horizontálního řezání použit algoritmus řezání. Algoritmus opět vytváří dva podrafy, tentokrát levý a pravý a řeší stejné implementační problémy s vrcholy hraničící s řezem grafu.

Vyříznutí pravého dolního rohu Algoritmus opět rozděluje graf na vstupu tentokrát podle daných nářezů na dvě části. Jako první jsou opět vytvořeny dva prázdné podgrafy, první „podgraf zbytek„ a „podgraf odřezek„. Vrcholy, které jsou zároveň napravo od horizontálního a dolů od vertikálního nářezu, vložíme do podgrafu odřezek. Vrcholy vlevo od vertikálního nářezu a vrcholy nahoru od horizontálního nářezu přidáme do podgrafu zbytek. Problémem zůstávají vrcholy ležící na hranici řezu. V tomto případě musí být počítáno se situací, kdy nářezy mohou protínat tupé vrcholy. Je to situace, kdy 37

výřez se dále rozšiřuje dalším výřezem. Proto pro každý vrchol hraničící s vertikálním nářezem testujeme, má-li vrchol horního nebo dolního souseda a pro každý vrchol, hraničící s horizontálním nářezem testujeme, má-li vrchol pravého nebo levého souseda. V případě existence levého souseda je vrchol duplikován, upraven a přidán do podgrafu nalevo, v případě existence pravého souseda je duplikovaný a upravený vrchol přidán do podgrafu napravo. V případě existence horního souseda je vrchol duplikován, upraven a přidán do podgrafu nahoře, v případě existence dolního souseda je duplikovaný a upravený vrchol přidán do podgrafu dole. Úprava vrcholů hraničících s nářezy přidávaných do podgrafů je prováděna stejně jako u vertikálních a horizontálních řezů. Rozdíl je jen u vrcholu ležícího na průniku nářezů, tento vrchol musí být v jednom podgrafu nastaven jako tupý.

Rozřezatelnost grafu na dva kusy Přeříznutí doprava Algoritmus odpovídá na otázku jestli je graf na vstupu rozříznutelný gilotinovatelným řezem vedoucím ze zadaného vrcholu. Vrchol na vstupu musí hraničit z leva s osou Y nebo může být tupý s vyříznutím nahoře vlevo nebo dole vlevo. Graf je pak z tohoto vrcholu procházen do hloubky. Skončí-li procházení ve vrcholu, který hraniční s osou Y, pak je graf rozřezatelný. V opačném případě není graf v tomto místě rozříznutelný. Přeříznutí dolů Podobně se prochází graf i vertikálně. Na vstupu je opět graf a vrchol, ze kterého bude začínat procházení. V případě, že procházení skončí okrajovým vrcholem hraničící s osou X, pak je graf v tomto místě rozřezatelný. Vyříznutí pravého dolního rohu Jednoduchou kombinací dvou předchozích algoritmů je algoritmus vyřezávající pravý dolní podgraf grafu. Na vstupu je opět graf a dva vrcholy, horizontální a vertikální vrchol. Pro vrcholy musí platit, že horizontální vrchol musí být výše než vertikální vrchol. Vertikální vrchol musí být nalevo od horizontálního vrcholu. Toto rozestavení vrcholů musí platit, aby nářezy oddělily právě pravý dolní podgraf. Procházení směrem doleva z horizontálního vrcholu a nahoru směrem z vertikálního vrcholu je realizováno úplně stejně jako v přeříznutí grafu dolů nebo doprava. Nutnou podmínkou pro vyříznutí podgrafu je dostatečná délka nářezů, které se musí protnout a ještě zajistit místo pro profil kotouče pily. Za předpokladu, že se nářezy protnou s dostatečným přesahem, je graf v tomto místě rozříznutelný.

38

6.5

Algoritmus dekódování jedince

Algoritmus dostane na vstupu permutaci identifikátorů a seznam rozměrů produktů. Na vstupu je také seznam zbytků desek materiálu a rozměry desky materiálu tovární velikosti. Výsledkem je nářezový plán, nebo-li seznam odpadů a desek materiálu obsahující produkty.

6.6

Algoritmus vkládání

Algoritmus vkládání postupně umisťuje seznam produktů na vstupu v pořadí určující permutace do desek materiálu a zbytků z předešlých řezání. Seznam zbytků a velikost desky tovární velikosti je také na vstupu. Vkládání produktů je prováděno rekurzivně následujícím algoritmem.

Vkládání produktů do desek a zbytků materiálu Na vstupu je seznam produktů a seznam zbytků desek materiálu. Produkty jsou setříděny v pořadí udávající permutace. Také je na vstupu informace o velikosti desky materiálu tovární velikosti. Algoritmus postupně prochází všechny zbytky desek z předchozích řezání v pořadí daném na vstupu a snaží se pomocí následujícího algoritmu vložit aktuální produkt do aktuální desky materiálu. Nepovede-li se algoritmu vložení produktu do aktuální desky, zkusí se vložení do další desky. Nepodaří-li se vložit produkt do žádné desky, je na konec seznamu zbytků přidána nová deska materiálu tovární velikosti, do které se produkt s jistotou vejde. Rozměry produktů jsou totiž omezeny velikostí desky tovární velikosti. Po vložení všech produktů na vstupu, algoritmus vrátí seznam vstupních zbytků a přidaných desek materiálu obsahující vložené produkty, nevyužité odpady a nový zbytek.

Vkládání produktu do desky materiálu Na vstupu je produkt a deska materiálu nebo odpad z předchozího řezání, cílem je umístit produkt do nějakého místa desky materiálu na vstupu. Každá deska materiálu je v interní reprezentaci tvořena seznamem obdélníkových odpadů, které představují místa, kam je možné vložit nějaký produkt. Seznam odpadů je setříděn podle vzdálenosti odpadů od horní hrany desky a následně podle vzdálenosti od levé hrany desky. Tento seznam postupně procházíme a produkt se pokoušíme vložit pomocí následujícího algoritmu do aktuálního odpadu. Povede-li se vložení do odpadu otestuje se λ-semi-gilotinovatelnost nářezového plánu. Je-li nářezový plán rozřezatelný i po vložení, tento algoritmus vrátí informaci o úspěšném vložení produktu. Není-li nářezový plán po vložení rozřezatelný, právě přidaný produkt je vyjmut a algoritmus se pokusí vložit před produkt horní a levý přířez. Pokud se přidání přířezů a opakované vložení produktu povede, je opět testována rozřezatelnost nářezového plánu. Je-li po přidání přířezů nářezový plán rozřezatelný, je vrácena informace o úspěšném vložení produktu.

39

Ve všech ostatních případech se vrací informace o nemožnosti vložit produkt a nářezový plán zůstává nezměněný od vstupního.

Obrázek 6.4: Příklad negilotinovatelného a λ-semi-gilotinovatelného nářezového plánu Tento příklad ilustruje, proč je algoritmus vkládání tak složitý. Algoritmus zajišťuje, aby nikdy nenastala situace, kterou můžeme vidět na prvním obrázku. Výstupem je deska materálu obsahující seznam produktů a odpadů.

Vkládání produktu do vybraného místa materiálu Algoritmus vkládá produkt do vybraného odpadu desky materiálu. Odpadem myslíme konkrétní nevyužité místo v desce materiálu, do kterého nezasahuje žádný produkt. Je-li produkt menší než odpad, pak je produkt jednoduše vložen. V případě, že je větší než odpad jsou rekurzivně hledány odpady na potřebných stranách. Pokud potřebné odpady existují, rekurzivně se do nich vkládá. Pokud se podaří vložit celý produkt, pak jsou využité odpady vymazány a do seznamu odpadů jsou naopak přidány zbytky po vkládání z krajních odpadů. Pokud se vložení povede, jsou všechny odpady v celé desce materiálu zasahující do X-ové souřadnice pravé hrany produktu, nebo Y-ové souřadnice dolní hrany produktu rozříznuty na dva samostatné odpady.

Obrázek 6.5: Interní reprezentace - první vložení, šesté vložení Při použití tohoto algoritmu může být zaručeno, aby nářezový plán vždy bylo možné převést na graf požadovaného typu. Vzniklý graf může být procházen a díky vnitřní reprezentaci je zajištěno, že při průchodu grafu nebude překážet žádný odpad. 40

6.7

Odhad složitosti vytvořeného algoritmu

Vzniklý algoritmus používá nepřímou reprezentaci, součástí odhadu složitosti bude i odhad dekódovacího algoritmu, který bude nezanedbatelně ovlivňovat výslednou celkovou složitost. Celý problém je metaheuristika. Složitost dekódování je tedy určena složitostí dílčích heuristik, hledající řešení v souladu s jednotlivými podmínkami, které musí splňovat dekódovaný jedinec. Schopnosti evoluce, která využije exploataci a exploraci k efektivnímu hledání globálního extrému v množině řešení, nyní úplně zanedbáme. Do hodnoty určující asymptotickou složitost započteme celou velikost této množiny řešení a budeme počítat s tím, že evoluce musí poctivě projít všechna možná řešení. Reprezentace jedince určuje maximální počet řešení, které jsme schopni vytvořit. O umisťování produktů v materiálu se sice stará deterministická heuristika, ale počet řešení, které jsme schopni v chromozomu popsat se rovná počtu permutací čísel 1 až N, kde každé číslo představuje jeden produkt. Reprezentovat jsme tedy schopni maximálně N! řešení. Toto číslo použijeme jako horní asymptotický odhad velikosti množiny řešení, kterou algoritmus musí projít. Složitost heuristiky dekódování se skládá ze složitosti nalezení vhodného místa pro produkt a z umístění jedince. Problém nalezení místa spočívá v lineárním vyzkoušení všech možných pozic pro umístění. Počet těchto pozic vyplývá z vnitřní reprezentace nářezového plánu. Jelikož heuristika provádí postupné vkládání, bude se počet míst určených pro vkládání v průběhu vkládání produktů měnit. Nejvíce možných pozic pro vložení bude mít na výběr poslední vkládaný produkt. Přibývání pozic nejsme schopni jednoduše asymptoticky odhadnout. Proto bereme nejhorší možný odhad pro vložení posledního produktu jako odhad vkládání každého i-tého produktu. Počet pozic pro umisťování v každé desce materiálu jde proto shora odhadnout druhou mocninou počtu produktů nacházejících se v aktuální desce. Přesně n-krát se bude preventivně rozřezávat vnitřní reprezentace každé desky materiálu. P ocetpozic = n21 + n22 + .... + n2k ≤ (n1 + n2 + .... + nk )2 = N 2 Problém umístění jedince nemůžeme jednoduše popsat, můžeme jej pouze odhadnout. Vkládání mění interní reprezentaci nářezového plánu aktuální desky materiálu. Dochází tam k preventivnímu rozdělování interní reprezentace částí materiálu. Toto rozdělování jde odhadnout součtem dvojnásobku počtu produktů nezarovnaných na horizontální a vertikální straně. Rozložení produktů v materiálu může být jakékoli a proto jediný způsob jak počet operací odhadnout, je hodnotou dvojnásobku počtu produktů v aktuální desce materiálu. Dvojnásobek se jedná z důvodu preventivního oddělování na obou stranách produktu. Tato konstanta je ale pro odhad asymptotické složitosti zanedbatelná. P ocetvklad.operaci = 2P ocetvert.prod. + 2P ocethoriz.prod. ≤ 2P ocetprod = 2N Složitost dekódování jednoho jedince je O(N 3 ) Složitosti jednotlivých podproblémů jsou násobeny, asymptotická složitost vzniklého algoritmu tedy je O(N! ∗ N 2 ∗ N) = O(N! ∗ N 3 ) 41

7. Experimenty V této kapitole srovnáváme dva nové algoritmy s již existujícími. V tabulce 7.1 jsou uvedené dva vytvořené algoritmy, které byly navrženy přímo pro problém dřevoobchodu. Jedná se o Přířezy algoritmus a o Přeskoky algoritmus. Druhý algoritmus se liší pouze v heuristice dekódování. Algoritmus se chová rozdílně v okamžiku, kdy dojde k situaci, že po přidání posledního produktu přestal být nářezový plán gilotinovatelný. Místo přidávání přířezů a opětovného testování λsemi-gilotinovatelnisti algoritmus rovnou prohlásí, že na tuto pozici není možné tento produkt vložit a pokusí se vložit do další pozice. Název Evoluce

Vkládání Rozřezatelnost

Přířezy Alg. Prohození dvou produktů, PMX, Permutace First Fit, přířezy existence řezů a nářezů

Přeskoky Alg. Prohození dvou produktů, PMX, Permutace First Fit, přeskok na další existence řezů a nářezů

Tabulka 7.1: Navržené algoritmy Pro srovnání jsme zvolili algoritmy uvedené v tabulce 7.2. Je zde popsán jeden negilotinovatelný a jeden gilotinovatelný algoritmus ve dvou modifikacích. Algoritmy jsou používány ve spojení s adaptivním evolučním algoritmem Min Lin (2008). Název Evoluce

Vkládání Rozřezatelnost

Lian Chan Alg. (1997) Obyčejné prohození dvou produktů, PMX Permutace First Fit, preventivní přířezy netestuje se

Corno Alg. (1997) Obyčejné prohození dvou produktů, PMX Permutace First Fit existence gilotin. řezů

Min Lin(2008), Lian Chan Adaptivní oper., Prohození dvou produktů, PMX Permutace First Fit, preventivní přířezy netestuje se

Min Lin(2008), Corno Adaptivní oper., Prohození dvou produktů, PMX Permutace First Fit existence rovných řezů

Tabulka 7.2: Existující algoritmy, vhodné pro srovnání Corno algoritmus na výstupu produkuje přímo gilotinovatelné nářezové plány. Heuristika First Fit vloží produkt do materiálu pouze pokud nářezový plán zůstane gilotinovatelný. Můžeme tedy říct, že existuje posloupnost řezů vedoucí k získání všech produktů. Tudíž algoritmus splňuje požadavky na vytváření semigilotinovatelných nářezových plánů. U Lian Chan algoritmu není rozřezatelnost nikterak testována. Všechny vkládané produkty mají proto o délku obloučku zvětšené rozměry. Zvětšíme-li každý pro42

dukt o šířku přířezu na horizontální i vertikální straně produktu, pak z jakéhokoli nářezového plánu můžeme vyřezat požadované produkty. Zdůvodnění toho, že všechny desky materiálu jsou pak rozřezatelné je jednoduché, protože všechny produkty jsou obdélníkového nebo čtvercového tvaru. Pak jeden obdélník musí být vždycky rohový, tento rohový obdélník můžeme jednoduše vyříznout dvěma na sebe kolmými řezy, protože jeho sousedé jsou od něj na všech místech vzdálení nejméně o šířku kotouče pily. Induktivně najdeme další rohový prvek. Parametry evoluce Testy všech algoritmů byly spuštěny s parametry evoluce uvedenými v následující tabulce 7.3. Také jsou zde uvedeny parametry týkající se rozměrů vstupních desek. Jedná se ale jen o parametry určující tovární rozměry velkých desek. Zbylá vstupní data jako velikosti zbytků z minulého řezání a velikosti požadovaných produktů jsou umístěny ve zvláštních vstupních souborech. Parametr board-factory-high board-factory-wigth push-truck population-size max-generations elite-size repeats

Hodnota 3000 5000 30 6 50 0,1 100

Vysvětlení výška celé desky, ze které se bude vyřezávat šířka celé desky, ze které se bude vyřezávat velikost kolečka, nebo-li λ velikost populace maximální počet generací velikost elity kolikrát se má experiment opakovat

Tabulka 7.3: Parametry evoluce

Použitá implementace adaptivity V implementaci algoritmu Min Lin Corno není využita přesná podoba algoritmu Min-Lin. Správná míra a způsob použití adaptivity je pro každý problém specifická. Možností zesložitit adaptivitu je nepřeberné množství. V implementaci jsou použity jen základní myšlenky a výpočet vedoucí k rozhodnutí o adaptivitě je částečně zjednodušen. Testy Popsané testy byly spuštěny s parametry v předchozí tabulce 7.3. Tudíž tovární velikost materiálu je 3x5 metrů a tloušťka je standardních 1,8 cm. Při této tloušťce nebude délka vzniklého obloučku od kotouče pily delší než 3 cm. Velikost obloučku je tedy nastavena na 30 mm. Algoritmy byly testovány na sadě problémů převzaté z Beasley benchmark dat. Převzaté testy - Beasley benchmark data [21]. • Test1 - Beasley benchmark data U1 • Test2 - Beasley benchmark data U2 43

• Test3 - Beasley benchmark data U2 • Test4 - Beasley benchmark data U3 • Test4 - Beasley benchmark data U3 Test 1 Obsahuje pouze deset vstupních produktů a žádné zbytky z předešlých řezání. Rozměry produktů jsou všechny zarovnány na desítky, nebo-li rozměry jsou zaokrouhleny na centimetry. Produkty nabývají obvyklých rozměrů, které se při tvorbě nábytku používají. Test 2 Tento test obsahuje celkem dvacet produktů s rozměry zarovnanými na desítky. Rozměry mohou být tedy vyjádřeny v centimetrech. Na vstupu nejsou žádné odpady z minulého řezání, tudíž vkládat se začíná do desek tovární velikosti. Test 3 Test 3 je velmi podobný Testu 2 s tím rozdílem, že na vstupu je jeden zbytek z předešlého řezání o rozměrech 1,5x1,5 metru. Produkty stejné jako u Testu 2. Test 4 Tento test neobsahuje žádný zbytek z minulého řezání. Produktů je přesně 30 a jsou zaokrouhleny na desítky milimetrů. Test 5 Test 5 je velmi podobný Testu 4 s tím rozdílem, že na vstupu je jeden zbytek z předešlého řezání o rozměrech 1,5x1,5 metru. Produkty stejné jako u Testu 4. Můj test 1 Tento test jsem vytvořil z 63 produktů, jejichž rozměry jsou velmi často zarovnány na stovky milimetrů. Test navíc obsahuje opakující se produkty stejných rozměrů. Testuje, jestli je Přířezy algoritmus na podobných datech doopravdy schopný dosáhnout stejně dobrých výsledků jako algoritmy vytvářející gilotinovatelné nářezové plány. Můj test 2 Test obsahuje jeden velký zbytek z předešlého řezání o velikosti 2x2 metry. Produkty jsou částečně zarovnány na desítky a částečně na stovky. Produktů je celkem 52. Test by měl reprezentovat nejčastější typ úlohy, kdy některé produkty budou zarovnány až na desítky centimetrů a jiné budou vyřezány s přesností na milimetry. Můj test 3 Tento test obsahuje 50 produktů a jeden zbytek z předchozího řezání o velikosti 1,5x1,5 metru. Rozměry produktů jsou absolutně nezarovnané ani na desítky milimetrů a požadavky na produkty se neopakují. Tento test představuje úlohu, kde se produkty stejných rozměrů vyskytují v minimální míře. Reálný test 1 Jedná se o test na reálných datech, určený pro tvorbu kuchyňské linky. Rozměr 44

linky je standardních 240 cm. Výška dolních skříněk včetně podstavce a pracovní desky je 85 cm. Výška horních skříněk je jednotná standardních 72 cm. Tento typ kuchyně je nejčastější v panelákových bytech a starých typizovaných bytových jednotkách. Test ovšem neobsahuje přední okrasná dvířka, která se vyrábí přímo na míru v továrně a neobsahuje zadní stranu skříněk, která je konstruována ze sololitu. Test obsahuje 46 produktů a žádný zbytek materiálu z předchozího řezání. Velikosti produktů se velice často opakují. Shodují se buď v obou dvou rozměrech nebo mají často stejnou délku jedné strany. To je dáno stejnou šířkou všech horních a dolních skříněk. Reálný test 2 Druhý reálný test obsahuje 54 produktů a žádný zbytek z předchozího řezání. Kuchyňská linka měří 290 cm a skříňky nejsou stejně vysoké. Součástí je také zásuvková skříň. Výsledky testů Pro porovnání algoritmů poslouží implementace algoritmů ve výsledném softwaru obsahující i uživatelské rozhraní pro vizuální zobrazení výsledného nářezového plánu. Pro porovnání výsledků jednotlivých algoritmů bylo použito pět nalezených, pro tento typ problému upravených, testů. Dále byly vymyšleny další tři vlastní testy. Parametry, se kterými byla spuštěna evoluce v předchozí tabulce 7.3. Výsledky testů jsou uvedeny v následující tabulce 7.5 udávající množství spotřebovaných desek jednotlivými algoritmy. Název Příř. alg. Můj test 1 0,70780 Můj test 2 2,17159 Můj test 3 1,62372 Test 1 1,48147 Test 2 2,37933 Test 3 3,31400 Test 4 3,48100 Test 5 4,42640

Přes. alg. 0,73067 2,31397 1,68059 1,51907 2,49360 3,44647 3,83253 4,72333

Lian-Gan 0,81673 2,31574 1,71925 1,49747 2,44233 3,41047 3,66747 4,58613

Corno M-L, L-G M-L, Cor. 0,70233 0,83607 0,70693 2,18259 2,32773 2,18529 1,62514 1,76979 1,65012 1,49907 1,49627 1,48467 2,41027 2,49940 2,44833 3,37640 3,46480 3,38653 3,54707 3,77627 3,63127 4,46887 4,69740 4,53027

Tabulka 7.4: Počty spotřebovaných desek u jednotlivých algoritmů Pro porovnání algoritmů byly použity také dva testy vycházející z reálných dat. Jako parametry evoluce se využívají stejné hodnoty jako u předcházejících testů 7.3. Název Příř. alg. Real test 1 0,85279 Real test 2 0,82244

Přes. alg. 0,88091 0,85820

Lian-Gan 0,94229 0,94409

Corno M-L, L-G M-L, Cor. 0,84885 1,17607 0,85575 0,81636 1,19233 0,82507

Tabulka 7.5: Počty spotřebovaných desek u jednotlivých algoritmů na reál datech

45

Obrázek 7.1: Výsledky testů Zlepšení Přířez algoritmu vůči ostatním algoritmům Zlepšení navrženého Přířez algoritmu ukazuje následující graf 7.2. Graf ukazuje procentuální rozdíl průměrů všech běhů evolučního algoritmu pro jednotlivé testy. V jednom případě je patrný horší výsledek Přířez algoritmu vůči Min-Lin Corno algoritmu, ale ve zbývajících případech je to opačně.

Obrázek 7.2: Zlepšení Přířez algoritmu vůči Min-Lin Corno algoritmu

46

Výsledky t-testů Z výsledků, které jednotlivé algoritmy spočítaly, byly spočítány t-testy. Hodnotou t-testu zjistíme pravděpodobnost s jakou pocházejí výsledky dvou algoritmů, ze stejných pravděpodobnostních rozdělení. Měli bychom tedy získat informace o tom, jak významné jsou odchylky výsledků dvou algoritmů. Výsledky základních algoritmů bez případných rozšíření byly testovány ve všech dvojicích, jako by v kartérském součinu. V následujících tabulkách můžeme nalézt přesné informace o tom, jak významné jsou odchylky výsledků každého páru základních algoritmů. V ideálním případě, by nově vzniklý Přířezy algoritmus měl ukázat, že testy, ve kterých byl Přířezy algoritmus lepší, jsou statisticky významné a testy, ve kterých dosáhl lepších výsledků jiný algoritmus, jsou t-testy statisticky nevýznamné. Pak by bylo experimentálně dokázáno, že je Přířezy algoritmus lepší než všechny předcházející algoritmy. Název Př. alg. Ods. alg. Lian-Gan Corno M-L, L-G M-L, Cor.

Příř. alg. 1,0000 0,0000 0,0000 0,0007 0,0000 0,8289

Přes. alg. 0,0000 1,0000 0,0000 0,0000 0,0000 0,0000

Lian-Gan 0,0000 0,0000 1,0000 0,0000 0,0640 0,0000

Corno 0,0007 0,0000 0,0000 1,0000 0,0000 0,2330

M-L, L-G 0,0000 0,0000 0,0640 0,0000 1,0000 0,0000

M-L, Cor. 0,8289 0,0000 0,0000 0,2330 0,0000 1,0000

Tabulka 7.6: Výsledky T-testu Můj Test 1 Název Př. alg. Ods. alg. Lian-Gan Corno M-L, L-G M-L, Cor.

Příř. alg. 1,00000 0,00000 0,00000 0,69025 0,00000 0,62320

Přes. alg. 0,00000 1,00000 0,80748 0,00000 0,07818 0,00000

Lian-Gan 0,00000 0,80748 1,00000 0,00000 0,08487 0,00000

Corno 0,69025 0,00000 0,00000 1,00000 0,00000 0,92234

M-L, L-G 0,00000 0,07818 0,08487 0,00000 1,00000 0,00000

M-L, Cor. 0,62320 0,00000 0,00000 0,92234 0,00000 1,00000

Tabulka 7.7: Výsledky T-testu Můj Test 2 Název Př. alg. Ods. alg. Lian-Gan Corno M-L, L-G M-L, Cor.

Příř. alg. 1,0000 0,0000 0,0000 0,6787 0,0000 0,0003

Přes. alg. 0,0000 1,0000 0,0000 0,0000 0,0000 0,0001

Lian-Gan 0,0000 0,0000 1,0000 0,0000 0,0102 0,0000

Corno 0,6787 0,0000 0,0000 1,0000 0,0000 0,0006

M-L, L-G 0,0000 0,0000 0,0102 0,0000 1,0000 0,0000

Tabulka 7.8: Výsledky T-testu Můj Test 3

47

M-L, Cor. 0,0003 0,0001 0,0000 0,0006 0,0000 1,0000

Název Př. alg. Ods. alg. Lian-Gan Corno M-L, L-G M-L, Cor.

Příř. alg. 1,0000 0,0000 0,0010 0,0033 0,0018 0,4661

Přes. alg. 0,0000 1,0000 0,0014 0,0079 0,0007 0,0000

Lian-Gan 0,0010 0,0014 1,0000 0,8040 0,8222 0,0146

Corno 0,0033 0,0079 0,8040 1,0000 0,6595 0,0220

M-L, L-G 0,0018 0,0007 0,8222 0,6595 1,0000 0,0239

M-L, Cor. 0,4661 0,0000 0,0146 0,0220 0,0239 1,0000

M-L, L-G 0,0001 0,8349 0,0437 0,0028 1,0000 0,1002

M-L, Cor. 0,0005 0,0104 0,7275 0,0452 0,1002 1,0000

Tabulka 7.9: Výsledky T-testu Test 1 Název Př. alg. Ods. alg. Lian-Gan Corno M-L, L-G M-L, Cor.

Příř. alg. 1,0000 0,0000 0,0000 0,0505 0,0001 0,0005

Přes. alg. 0,0000 1,0000 0,0000 0,0000 0,8349 0,0104

Lian-Gan 0,0000 0,0000 1,0000 0,0171 0,0437 0,7275

Corno 0,0505 0,0000 0,0171 1,0000 0,0028 0,0452

Tabulka 7.10: Výsledky T-testu Test 2 Název Př. alg. Ods. alg. Lian-Gan Corno M-L, L-G M-L, Cor.

Příř. alg. 1,0000 0,0000 0,0001 0,0114 0,0000 0,0027

Přes. alg. 0,0000 1,0000 0,0071 0,0000 0,2210 0,0000

Lian-Gan 0,0001 0,0071 1,0000 0,0377 0,0020 0,1151

Corno 0,0114 0,0000 0,0377 1,0000 0,0000 0,5202

M-L, L-G 0,0000 0,2210 0,0020 0,0000 1,0000 0,0000

M-L, Cor. 0,0027 0,0000 0,1151 0,5202 0,0000 1,0000

Tabulka 7.11: Výsledky T-testu Test 3 Název Př. alg. Ods. alg. Lian-Gan Corno M-L, L-G M-L, Cor.

Příř. alg. 1,0000 0,0000 0,0000 0,0000 0,0000 0,0002

Přes. alg. 0,0000 1,0000 0,0000 0,0000 0,1494 0,0000

Lian-Gan 0,0000 0,0000 1,0000 0,0000 0,0024 0,3464

Corno 0,0000 0,0000 0,0000 1,0000 0,0000 0,0267

M-L, L-G 0,0000 0,1494 0,0024 0,0000 1,0000 0,0032

M-L, Cor. 0,0002 0,0000 0,3464 0,0267 0,0032 1,0000

Tabulka 7.12: Výsledky T-testu Test 4 Název Př. alg. Ods. alg. Lian-Gan Corno M-L, L-G M-L, Cor.

Příř. alg. 1,0000 0,0000 0,0000 0,0446 0,0000 0,0002

Přes. alg. 0,0000 1,0000 0,0000 0,0000 0,4725 0,0000

Lian-Gan 0,0000 0,0000 1,0000 0,0000 0,0022 0,0334

Corno 0,0446 0,0000 0,0000 1,0000 0,0000 0,0166

M-L, L-G 0,0000 0,4725 0,0022 0,0000 1,0000 0,0000

Tabulka 7.13: Výsledky T-testu Test 5 48

M-L, Cor. 0,0002 0,0000 0,0334 0,0166 0,0000 1,0000

Zhodnocení výsledků testů Výsledky testů ukazují, že v devíti z deseti testů Přířezy algoritmus překonal všechny ostatní algoritmy, jako druhý nejlepší algoritmus v testech vyšel MinLin Corno algoritmus. Přířezy algoritmus byl nejlepší v obou dvou reálných testech, ve všech převzatých testech pro bin packing problém a ve dvou ze tří nově navržených testů. Můj Test 1 jako jediný dopadl v neprospěch Přířezy algoritmu, algoritmus MinLin Corno byl v tomto případě o 0,12 procenta lepší. Výsledek t-testu hodnot Přířez algoritmu a MinLin Corno u tohoto testu ukazuje, že výsledky běhů evoluce nejsou statisticky významné. V Testu 1 sice Přířezy algoritmus překonal všechny ostatní algoritmy, zlepšení vůči Přířezy algoritmu ale dosáhlo pouze 0,22 procenta. V tomto případě opět t-test Přířezy algoritmu a MinLin Corno algoritmu ukazuje, že pravděpodobnostní rozdělení jsou si částečně podobné. T-test výsledných hodnot těchto dvou algoritmů ukazuje, že rozdělení jsou si velmi podobná. Největší zlepšení Přířezy algoritmu vůči algoritmu MinLin Corno vyšlo u Můj Test 3, kde rozdíl výsledků činí až 4,14 procent. Zlepšení je statisticky významné, p-hodnota t-testu vyšla 0,0003. Ostatní testy vykazují zlepšení do pěti procent. Toto zlepšení je určitě nezanedbatelné, jak z hlediska smysluplnosti definice nové třídy problému, tak z praktického využití ve dřevoobchodě, kde úspora pěti procent znamená například ušetření až 250 Kč na nákladech materiálu při tvorbě jednoduché kuchyňské linky. T-testy ukázaly, že hodnoty běhů testů, které ukázaly zlepšení Přířezy algoritmu, jsou statisticky významné a výsledky testů, které nedokazují zlepšení nového algoritmu jsou statisticky bezvýznamné.

7.1

Příklady výstupů

Na následujících obrázcích je vidět příklad výstupu Přířez algoritmu, Odsazení algoritmu a Min-Lin Corno algoritmu zpracovávající Můj test 1.

49

Obrázek 7.3: Výstup - Přířezy algoritmu

Obrázek 7.4: Výstup - Odsazení algoritmu

Obrázek 7.5: Výstup - Min-Lin, Corno algoritmu 50

7.2

Vylepšení algoritmu

Použitý algoritmus dekódování jedince reprezentující řešení aktuálního problému obsahuje otestování λ-semi-gilotinovatelnosti. Tato rozřezatelnost byla splněna pokud šel celý nářezový plán rozřezat svislými a vodorovnými gilotinovatelnými řezy nebo nářezy oddělující dolní pravý roh desky materiálu. Jedná se o oddělení jednoho rohu přířezy. Rozřezávání bylo doplněno o schopnost oddělit více než jeden roh desky materiálu. Vylepšený algoritmus dokáže odříznout až dva různé rohy desky materiálu. Název Můj test 1 Můj test 2 Můj test 3 Reálný test 1 Reálný test 2 Test 1 Test 2 Test 3 Test 4 Test 5

Dva rohy 0,7115333333 2,1842466667 1,6262333333 0,8250266667 0,8509066667 1,4814666667 2,3754666667 3,3298666667 3,5038666667 4,4222666667

Jeden roh 0,7078 2,1715866667 1,6237228 0,8527866667 0,82244 1,4798666667 2,3793333333 3,314 3,481 4,4264

T-test 0,09248 0,64931 0,44780 0,00000 0,00000 0,65037 0,80005 0,58892 0,15322 0,83793

Tabulka 7.14: Porovnání spotřeby Přířezy alg. s algoritmem vyřezávající dva rohy Vylepšený algoritmus byl úspěšnější ve třech případech z celkových deseti testovaných případů. Ve dvou případech bylo toto zlepšení statisticky bezvýznamné. Bylo ovšem na úkor vyšší časové náročnosti dekódování jedinců. Přířezy algoritmus implementující pouze odřezávání jednoho rohu je schopný rozřezat menší počet nářezových plánů než algoritmus, který umí odříznout více rohů. Z porovnání výsledků algoritmu odřezávajícího jen jeden roh a algoritmu odřezávající dva rohy je vidět, že obohacováním algoritmů o schopnost řezat další rohy nedochází na daných vstupních datech k významným zlepšením. Výsledky ukazují, že nářezové plány, u kterých by se projevilo zlepšení, se vyskytují velmi zřídka. V problému dřevoobchodu nebude tedy docházet z příčiny doplnění schopnosti odřezat zbylé rohy k získávání lepších výsledků. Vylepšováním algoritmu tímto směrem, pro toto využití se tedy nebudeme zabývat.

51

Závěr Výsledkem práce je nový Přířezy algoritmus, který se skládá ze známých operátorů, ale nového způsobu dekódování jedince. Implementace ukazuje, že se vzniklým Přířezy algoritmem lze dosáhnout úspory nákladů na materiálu při výrobě. Míra úspory se pohybuje do 5 procent spotřebované plochy velkých desek. Nový algoritmus byl úspěšně srovnán s algoritmy řešícími podobný problém. Testované algoritmy mají stejnou časovou složitost všech použitých heuristik a bylo experimentálně zjištěno, že žádný heuristiku využívající algoritmus není výrazně pomalejší. O navrženém Přířezy algoritmu byl napsán článek obsahující i zavedení nového dělení problematiky tvorby nářezových plánů. Objevuje se zde definice λ-semigilotinovatelnosti. Článek [20] byl publikován na konferenci IEEE World Congress on Computational Intelligence. Dále vznikl nový software určený pro firmu obchodující s velkoplošným materiálem. Software se specializuje na pravidelný materiál rozřezatelný pouze kotoučovou pilou. Naprogramovaný software s kompletními zdrojovými kódy se nachází na přiloženém CD. Software je ve více variantách, pro každý testovaný algoritmus je zvláštní balíček. Součástí softwaru je uživatelská a programátorská dokumentace, pomáhající uživatelům a administrátorům s obsluhou a správou programu. Na CD je přiložena také prezentace vysvětlující jednotlivé části použitých algoritmů. CD dále obsahuje kompletní výsledky všech spočítaných testů, ze kterých bylo zjištěno zlepšení v oblasti materiálové úspory a pomocí t-testů potvrzena statisticky významná odlišnost pravděpodobnostních rozdělení výstupů jednotlivých algoritmů. Přířezy algoritmus je možné obohatit o mnoho vylepšení a drobných pozměnění. Navržený algoritmus musí v každém kroku evolučního algoritmu otestovávat rozřezatelnost nářezového plánu. Tudíž jen samo ohodnocení jedince je výpočetně poměrně složitý úkol. Při přidání dalších vylepšení musí být počítáno se zvýšením časové složitosti vzniklého algoritmu. Jedno z nejjednodušších možných vylepšení algoritmu spočívá v testování, jeli nutné při nemožnosti rozřezat nářezový plán, přidávat vždy přířezy, jak na vertikální, tak i na horizontální straně. Je možné, že by v aktuální situaci postačilo přidat pouze jeden z přířezů. Další vylepšení stávajícího algoritmu je možné vytvořit obohacením o další možnosti řezání. Mohl by takto vzniknout algoritmus, který k otestování rozřezatelnosti používá hledání výřezů všech čtyřech rohů. Tím by se zamezilo situacím, kdy vzniklý algoritmus označí nářezový plán za nerozřezatelný přestože ve skutečnosti rozřezatelný je. Toto vylepšení by ovšem bylo cenné pouze na určitých druzích truhlářských pil.

52

Výstup vzniklého softwaru může sloužit jako vstup pro bezobslužnou kotoučovou pilu. Úspora nákladů firmy by tedy nemusela být jen na straně využití materiálu, ale také v redukci pracovních míst v důsledku automatizace výroby.

53

Seznam použité literatury [1] E. K. Burke, R. S. R. Hellier, G. Kendall, and G. Whitwell, 2010, Irregular Packing Using the Line and Arc No-Fit Polygon. Oper. Res. 58, 4-Part-1 (July 2010), 948-970. [2] E. Hopper and B. Turton, 1997, Application of Genetic Algorithms to Packing Problems - A Review. Proceedings of the Second On-line World Conference of Soft Computing in Engineering Design and Manufacturing, SpringerVerlag, 279-288. [3] E. Hopper, 2000, Two-dimensional Packing utilising Evolutionary Algorithms and other Meta-Heuristic Methods. TU Dresden. PhD. thesis. [4] Wascher, Gerhard & Haussner, Heike & Schumann, Holger, 2007, An improved typology of cutting and packing problems. European Journal of Operational Research, Elsevier, vol. 183(3), pages 1109-1130, December. [5] Baochun Wang, 2010, An Adaptive Genetic Algorithm for 2D Packing Problem, School of Mechanical Engineering, Tianjin University of Technology and Education, Tianjin 300222, China. [6] de Armas, J., Miranda, G., Len, C., 2011, Hyperheuristic Encoding Scheme for Multi-Objective Guillotine Cutting Problems, GECCO 11, July 12 16, 2011, Dublin, Ireland [7] Beasley, J.E., 1985, Algorithms for unconstrained two-dimensional guillotine cutting. The Journal Research Socienty 36(4), 297-306. [8] Goldberg, D., Lingle, R., 1985, alleles, loci and the travelling salesman problem. In: Proceedings of the the 1st International Conference on Genetic Algorithms and Their Applications. L. Erlbaum Associates Inc., Hillsdale, NJ, USA. [9] Smith D., 1985, Bin-packing with adaptive search. In: Grefenstette (Ed.), Proceedings of an International Conference on Genetic Algorithms and their Applications, Lawrence Erlbaum, pp. 202-206. [10] Liu D. and Teng H., 1999, An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles. European Journal of Operational Research 112, 413-419. [11] Leung T. W., Yung C. H. and Chan C .K., 1999, Applications of genetic algorithm and simulated annealing to the 2-dimensional non-guillotine cutting stock problem. Presented at IFORS 99, Beijing China, August 16-20. [12] Dagli C. H. and Poshyanonda P., 1997, New approaches to nesting rectangular patterns. Journal of Intelligent Manufacturing 8, 177-190. [13] Lai K. K. and Chan W. M., 1997, An evolutionary algorithm for the rectangular cutting stock problem. International Journal of Industrial Engineering 4, 130-139. 54

[14] Hwang S. M., Cheng Y. K. and Horng J. T., 1994, On solving rectangle bin packing problems using genetic algorithms. In: Proceedings of the 1994 IEEE International Conference on Systems, Man and Cybernetics. Part 2 (of 3), San Antonio, TX, USA, 1583-1590. [15] Rahmani A. T. and Ono N., 1995, An evolutionary approach to twodimensional guillotine cutting problem. In: Proceedings of the IEEE Conference on Evolutionary Computation, pp. 148-151. [16] András P., András, A. and Zsuzsa, S., 1996, A genetic solution for the cutting stock problem. In: Proceedings of the First On-line Workshop on Soft Computing, Aug. 1996, Nagoya University, pp. 87-92. [17] Corno F., Prinetto P., Rebaudengo M. and Sonza Reorda M., 1997, Optimising area loss in flat glass cutting. In: Proceedings of Second International Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications, GALESIA ’97, University of Strathclyde, Glasgow, UK, pp. 450-455. [18] Cui, Y., Yang, Y., 2010, A heuristic for the one-dimensional cutting stock problem with usable leftover. European Journal of Operational Research 204(2), 245 - 250. [19] E. Burke, R. Hellier, G. Kendall, G. Whitwell, 2005, A New Bottom-LeftFill Heuristic Algorithm for the Two-Dimensional Irregular Packing Problem, School of Computer Science and Information Technology, University of Nottingham, Jubilee Campus, Nottingham NG8 1BB, United Kingdom [20] Štěpán Balcar, Martin Pilát, Roman Neruda, 2012, IEEE Congress on Evolutionary Computation, An evolutionary algorithm for 2D semi-guillotinable circular saw cutting, Charles University in Prague. [21] Beasley, 1985, Algorithms for Unconstrained Two-Dimensional Guillotine Cutting, Journal of the Operational Research Society, http://dip.sun.ac.za/∼vuuren/repositories/levelpaper/spp%5B1%5D.htm

55

Přílohy A) Použité algoritmy v „Přířezy Algoritmu„ B) Přiložené CDčko se softwarem, zdrojovými kódy a kompletními výsledky

56

A. Slovní popis algoritmů Popsané algoritmy jsou podčásti nového algoritmu Přířezy algoritmu.

A.1

Převod nářezového plánu na graf

Přidání vrcholů Slovní popis: - sloučíme všechny produkty a odpady do jednoho pole - pole postupně procházíme a pro každý prvek : - najdeme v grafu všechny čtyři vrcholy a přidáme je do grafu - vymažeme duplikátní vrcholy

Přidání hran Slovní popis: - sloučíme všechny produkty a odpady do jednoho pole pole postupně procházíme a pro každý prvek : - najdeme v grafu všechny čtyři vrcholy (vrcholy tam jsou, protože jsme je tam sami přidali) - zjistíme sousední produkty a odpady aktuálního produktu nebo odpadu ve všech směrech (horní, dolní, levé a pravé sousedy) - pro každý směr provedeme: - nemá-li aktuální produkt nebo odpad žádného souseda v aktuálním směru nebo má-li pouze jednoho souseda v aktuálním směru provedeme : - levý vrchol(pravý, dolní, horní) roh spoj s vrcholem pravým (levým, horním, dolním) a pravý () s levým () - má-li aktuální produkt nebo odpad více než jednoho souseda: - setřiď sousedy - pro oba vrcholy(rohy) v aktuálním směru proveď: - spoj roh aktuální strany aktuálního produktu nebo odpadu s prvním(posledním) prvkem z aktuálního seznamu sousedů a obráceně

A.2

Řezání grafu

Funkce vrací informaci o tom jestli je graf rozřezatelný. Slovní popis: - zjistit, jestli existuje řez přes celou desku směrem zleva doprava takový, že řez sousedí s nějakým produktem (sousedit s produktem : řez aspoň v jednom místě vede po hraně nějakého produktu = nerozřezává pouze odpady) - pokud řez existuje : - proveď return ,,Horizontální přeříznutí,, - zjistit, jestli existuje řez přes celou desku směrem shora dolu takový, že řez sousedí s nějakým produktem - pokud řez existuje : - proveď return ,,Vertikální přeříznutí,,

57

- zjistit, jestli existuje pravo-dolní vyříznutí poddesky velké desky takové, že aspoň jeden řez sousedí s nějakým produktem - pokud řez existuje : - proveď return ,,Vyříznutí pravého dolního rohu,, - zjistit, jestli existuje řez přes celou desku směrem zleva doprava - pokud řez existuje : - proveď return ,,Horizontální přeříznutí,, - zjistit, jestli existuje řez přes celou desku směrem shora dolu - pokud řez existuje : - proveď return ,,Vertikální přeříznutí,, - zjistit, jestli existuje pravo-dolní vyříznutí poddesky velké desky - pokud řez existuje : - proveď return ,,Vyříznutí pravého dolního rohu,, return false;

Horizontální přeříznutí Na vstupu dostaneme Y souřadnici řezu, funkce vrací informaci o tom, jestli je graf rozřezatelný. - vytvoříme prázdný horní podgraf a prázdný dolní podgraf - vrcholy, které mají Y-ovou souřadnici menší než Y na vstupu, tak přidáme do dolního podgrafu - vrcholy, které mají Y-ovou souřadnici větší než Y na vstupu, tak přidáme do horního podgrafu - projdeme všechny vrcholy s Y-onovou souřadnicí rovné vstupnímu Y - pokud má aktuální vrchol horního souseda (deska pokračuje nahoru) - vytvoř kopii vrcholu - kopii vrcholu označ jako vrchol horizontálně okrajový (poslední vrchol grafu v horizontálním směru) - vymaž dolního souseda z kopie vrcholu - otestuj jestli aktuální vrchol je ,,tupý,, a výřez je ,,dole vlevo,, nebo ,,dole vpravo,, - zruš označení ,,tupý,, vrchol z kopie vrcholu (už nebude tupý) - zruš označení ,,vertikálně okrajový vrchol,, z kopie vrcholu -

pokud má aktuální vrchol dolního souseda (deska pokračuje dolu) - vytvoř kopii vrcholu - kopii vrcholu označ jako vrchol horizontálně okrajový (poslední vrchol grafu v horizontálním směru) - vymaž horního souseda z kopie vrcholu - otestuj jestli aktuální vrchol je ,,tupý,, a výřez je ,,nahoře vlevo,, nebo ,,nahoře vpravo,, - zruš označení ,,tupý,, vrchol z kopie vrcholu (už nebude tupý) - zruš označení ,,vertikálně okrajový vrchol,, z kopie vrcholu

- zavolej ,,Řezání,, na horní podgraf - zavolej ,,Řezání,, na dolní podgraf - jdou-li oba dva podgrafy rozřezat tak funkce vrací ,,true,, v opačném případě ,,false,,

58

Vrchol značím jako tupý, když se právě v tomto vrcholu potkalo vertikální a horizontální naříznutí grafu. Vrchol je tím pádem okrajový ve vodorovném i svislém směru.

Vertikální přeříznutí Na vstupu dostaneme X souřadnici řezu, funkce vrací informaci o tom, jestli je graf rozřezatelný. - vytvoříme prázdný levý podgraf a prázdný pravý podgraf - vrcholy, které mají X-ovou souřadnici menší než X na vstupu, tak přidáme do levého podgrafu - vrcholy, které mají X-ovou souřadnici větší než X na vstupu, tak přidáme do pravého podgrafu - projdeme všechny vrcholy s X-onovou souřadnicí rovné vstupnímu X - pokud má aktuální vrchol levého souseda (deska pokračuje doleva) - vytvoř kopii vrcholu - kopii vrcholu označ jako vrchol vertikálně okrajový (poslední vrchol grafu ve vertikálním směru) - vymaž pravého souseda z kopie vrcholu - otestuj jestli aktuální vrchol je ,,tupý,, a výřez je ,,nahoře vlevo,, nebo ,,dole vlevo,, - zruš označení ,,tupý,, vrchol z kopie vrcholu (už nebude tupý) - zruš označení ,,horizontálně okrajový vrchol,, z kopie vrcholu - pokud má aktuální vrchol pravého souseda (deska pokračuje doprava) - vytvoř kopii vrcholu - kopii vrcholu označ jako vrchol vertikálně okrajový (poslední vrchol grafu ve vertikálním směru) - vymaž levého souseda z kopie vrcholu - otestuj jestli aktuální vrchol je ,,tupý,, a výřez je ,,nahoře vpravo,, nebo ,,dole vpravo,, - zruš označení ,,tupý,, vrchol z kopie vrcholu (už nebude tupý) - zruš označení ,,horizontálně okrajový vrchol,, z kopie vrcholu - zavolej ,,Řezání,, na levý podgraf - zavolej ,,Řezání,, na pravý podgraf - jdou-li oba dva podgrafy rozřezat tak, funkce vrací ,,true,, v opačném případě ,,false,,

Vyříznutí pravého dolního rohu Vyříznutí pravého dolního rohu: Na vstupu dostaneme dvoje souřadnice x1v , y1v , x2v , y2v a x1h , y1h , x2h , y2h souřadnice vertikálního a horizontálního řezu, funkce vrací, jestli je graf rozřezatelný. - vytvoříme prázdný podgraf, podgraf_odřezek a prázdný pravý podgraf_zbytek - vrcholy napravo_dolu od svislého a vodorovného naříznutí přidáme do podgrafu podgraf_odřezek - vrcholy ve směru nahoru nebo doleva od svislého a vodorovného naříznutí přidáme do podgrafu podgraf_zbytek

59

- projdeme všechny vrcholy mezi souřadnicemi x1v, y1v, x2v, y2v nebo x1h, y1h, x2h, y2h včetně těchto vrcholů - pokud vrchol leží mezi vrcholy (x1v, y1v, x2v, y1h) (poslední je H = řezy jsou delší, my potřebujeme jen z obdélníka) - pokud má aktuální vrchol levého souseda (deska pokračuje doleva) .................... (stejné jako u vertikálního řezání) - pokud má aktuální vrchol pravého souseda (deska pokračuje doprava) .................... (stejné jako u vertikálního řezání) - pokud vrchol leží mezi vrcholy (x1h, y1h, x2v, y1h) (předpos. je V _ řezy jsou delší, my potřebujeme jen z obdélníka) - pokud má aktuální vrchol horního souseda (deska pokračuje nahoru) .................... (stejné jako u horizontálního řezání) - pokud má aktuální vrchol dolního souseda (deska pokračuje dolu) .................... (stejné jako u horizontálního řezání) - pokud vrchol leží na souřadnicích x1v, y1h (jde o ,,tupý,, úhel) - vytvoř kopii aktuálního vrcholu tupý_vrchol_1 - nastav tupý_vrchol_1 jako vrchol vertikálně a horizontálně okrajový - vymaž levé a horní sousedy vrcholu tupý_vrchol_1 - přidej tupý_vrchol_1 do podgrafu-odřezek - vytvoř kopii aktuálního vrcholu tupý_vrchol_2 - nastav tupý_vrchol_2 jako vrchol vertikálně a horizontálně okrajový - označ tupý_vrchol_2 jako tupý_vrchol_s_výřezem_dole_vpravo - přidej tupý_vrchol_2 do podgrafu-zbytek - zavolej ,,Řezání,, na podgraf podgraf-odřezek - zavolej ,,Řezání,, na podgraf podgraf-zbytek - jdou-li oba dva podgrafy rozřezat, tak funkce vrací ,,true,, v opačném případě ,,false,,

Rozřezatelnost grafu na dva kusy Přeříznutí doprava: Na vstupu dostaneme vrchol a graf, funkce vrací informaci o tom, jestli je graf rozřezatelný na dva. - platí-li pro vrchol na je-li vrchol ,,tupý,, - procházej graf - je-li

vstupu: nehraničí s X a hraničí zleva s Y nebo s vyříznutím nahoře vlevo nebo dole vlevo do hloubky, dokud existuje další pravý vrchol poslední vrchol procházení okrajový a hraničí s osou Y - return true;

return false;

Přeříznutí dolu: Na vstupu dostaneme vrchol a graf, funkce vrací informaci o tom, jestli je graf rozřezatelný na dva. - platí-li pro vrchol na je-li vrchol ,,tupý,, - procházej graf - je-li

vstupu: hraničí ze shora s X a nehraničí s Y nebo s vyříznutím nahoře vlevo nebo nahoře vpravo do hloubky, dokud existuje další pravý vrchol poslední vrchol procházení okrajový a hraničí s osou X - return true;

return false;

Vyříznutí pravého dolního rohu: Na vstupu dostaneme horizontální a vertikální vrchol, šířka kotouče a graf.

60

- platí-li, že vertikální vrchol má levého a pravého souseda a horizontální vrchol má horního a dolního souseda - platí-li, že vertikální X_pozice < horizontální X_pozice a vertikální Y_pozice < horizontální Y_pozice - platí-li pro horizontální vrchol na vstupu: nehraničí s X a hraničí zleva s Y nebo je-li vrchol ,,tupý,, s vyříznutím nahoře vlevo nebo dole vlevo - procházej graf do hloubky, dokud existuje další pravý vrchol - je-li poslední_horizontální vrchol procházení okrajový a hraničí s osou Y - platí-li pro vrchol na vstupu: hraničí ze shora s X a nehraničí s Y nebo je-li vrchol ,,tupý,, s vyříznutím nahoře vlevo nebo nahoře vpravo - procházej graf do hloubky, dokud existuje další pravý vrchol - je-li poslední vrchol procházení okrajový a hraničí s osou X - jsou-li se řezy dostatečně dlouhé a přesahují-li oba řezy přes sebe o vzdálenost větší než šířka kotouče na vstupu - return true; - return false;

A.3

Algoritmus dekódování jedince

Vstupu:

- permutace ID_produktu - seznam rozměrů zbytků materiálu v pořadí na vstupu programu - šířka a výška desek materiálu tovární velikosti (zbytky zkusíme využít jako první, zbytek doplníme celými deskami) - seznam rozměrů produktů v pořadí na vstupu programu

- vytvoř prázdný seznam desek materiálu. - do seznamu desek materiálů vlož seznam zbytků materiálu - projdi seznam zbytků materiálu - do aktuálního zbytku materiálu vlož co nejvíce produktů (vkládá se stejně jako do desky materiálu) - dokud -

nejsou všechny produkty vloženy v nějaké desce materiálu vytvoř novou desku materiálu o továrních rozměrech (šířka, výška) na vstupu do aktuální nové desky materiálu vlož co nejvíce produktů novou desku materiálu vlož do seznamu materiálů

Výstup:

- seznam obsahující nářezové plány pro jednotlivé desky - seznam velkých desek

A.4

Algoritmus vkládání

Vkládání produktů do desek a zbytků materiálu Vstupu:

- rozměry desky materiálu: - šířka a výška (tohoto materiálu) - seznam zbytků - seznam produktů

61

- vytvoř prázdný seznam desek a zbytků - nářezový_plán - do nářezového plánu přidej všechny zbytky z předcházejících řezání - projdi seznam produktů na vstupu - projdi seznam nářezový_plán - do aktuální desky zbytku nebo materiálu se pokus vložit aktuální produkt - pokud se vložení povede - ukonči procházení seznamu zbytků - pokud se aktuální produkt nepodařilo vložit do žádného zbytku - přidej do nářezového plánu desku materiálu tovární velikosti

Výstup:

- seznam desek materiálu: - šířka a výška (tohoto materiálu) - seznam odpadů (ubyly ty, do kterých se vložily produkty) - seznam produktů (vložených)

Vkládání produktu do desky materiálu Vstupu:

- deska materiálu: - šířka a výška (této desky materiálu) - seznam odpadů - seznam produktů (již vložených = na začátku prázdné) - produkt určený k vložení do desky materiálu

- projdi seznam odpadů desky materiálu setříděný podle vzdálenosti od horní hrany desky a následně podle vzdálenosti od levé hrany desky - vlož produkt do odpadu - pokud s vložení nepovede - break; - pokud s vložení povede - otestuj rozřezatelnost daného nářezáku (deska materiálu = převod na graf) - pokud je graf rozřezatelný - return true; - pokud je graf nerozřezatelný - obnov : = vložený produkt zase odeber (vrátit všechny změny v desce materiálu na vstupu) - pokus se vložit produkt s přířezy - pokud se vložení nepovedlo - break; - pokud se vložení povedlo - otestuj rozřezatelnost daného nářezáku (desky materiálu = převod na graf) - pokud je graf rozřezatelný - return true; - pokud je graf nerozřezatelný - obnov : = vložený produkt zase odeber (vrátit všechny změny v desce materiálu na vstupu) - break; Výstup:

- deska materiálu: - šířka a výška (tohoto materiálu) - seznam odpadů (ubyly ty, do kterých se vložily produkty) - seznam produktů (vložených) - informace, jestli se vložení povedlo a zároveň, jestli je nářezák rozřezatelný

Vkládání produktu do vybraného místa materiálu - pro vložení produktu do odpadu, většího než je vkládaný produkt, vznikne jeden nebo tři odpady - tyto odpady (odpad) je přidán do seznamu odpadů (do těchto odpadů se bude vkládací algoritmus snažit vložit jiné produkty) - pro vložení produktu do menšího odpadu, než je sám produkt, se algoritmus musí podívat, jestli soused odpadu na příslušné straně je také odpad a jestli se dají odpady pospojovat, tak aby pospojovaný odpad byl dostatečně velký pro

62

vložení ve všech směrech - zbytky jsou opět přidány do odpadů - všechny odpady, jejichž horní hrana odpadu leží výše než spodní hrana produktu a dolní hrana odpadu leží níže než spodní hrana produktu, přeřízni v úrovni spodní hrany produktu na dva - všechny odpady, jejichž levá hrana odpadu leží nalevo od pravé hrany produktu a pravá hrana odpadu leží napravo od pravé hrany produktu, přeřízni v úrovni pravé hrany produktu na dva

63