× Aktuálně z oboru

Programátoři po celém světě dnes slaví Den programátorů [ clanek/2018091300-programatori-po-celem-svete-dnes-slavi-den-programatoru/ ]
Celá zprávička [ clanek/2018091300-programatori-po-celem-svete-dnes-slavi-den-programatoru/ ]

Evoluční optimalizační systémy III

[ http://programujte.com/profil/164-jaroslav-teda/ ]Google [ ?rel=author ]       [ http://programujte.com/profil/118-zdenek-lehocky/ ]Google [ ?rel=author ]       20. 2. 2007       21 240×

V minulé kapitole jsme si předvedli jednoduchý genetický algoritmus a jeho základní funkce. V této kapitole již popíšeme skutečný systém přinášející značné úspory materiálu ve výrobě.

Optimalizace dělení tyčového materiálu

Základní principy optimalizace dělení tyčového materiálu byly již popsány v článku Genetické algoritmy a jejich aplikace v praxi. Nyní si problém probereme podrobněji včetně ukázek na demo verzi.

Konstrukční kusovník a úloha optimalizace

Program Konstrukční kusovník byl vytvořen pro podporu práce konstruktéra. Umožňuje mu vypsat seznam materiálu potřebného k výrobě vyvíjeného výrobku a zároveň ho uložit do podnikového informačního systému, tj. založit všechny položky a uložit strukturu. Kusovník vzniká principiálně v konstrukci a pak je využíván například technologickými útvary, které do kusovníku doplňují další specifické údaje.

Konstrukce zpravidla obsahují tyče, trubky a válcované profily různých délek. Délky těchto dílů jsou přizpůsobené dané konstrukci a neodpovídají délkám, ve kterých se daný profil dodává na trh. Konkrétní délky dílů je nutno z původních délek nařezat. Konstrukční kusovník dokáže vygenerovat seznam materiálů za celou konstrukci a toto lze použít jako podklad k objednání materiálu. Výstupní seznam materiálu by však byl neuspořádaný a kdyby se měly tyče řezat dle tohoto seznamu, vznikal by velký odpad. Protože se tyče dodávají od výrobců jako polotovar v několika délkách, je složité určit, z jaké tyče se mají položky nařezat.

Proto obsahuje kusovník také optimalizaci posloupnosti řezání materiálů. Tento subsystém tvoří integrovanou část Konstrukčního kusovníku. Provádí optimalizaci dělení tyčového materiálu tak, aby se ušetřilo co nejvíce výchozího polotovaru a snížily náklady na výrobu. Cílem optimalizace je minimalizovat počet použitých tyčí a dále maximalizovat zbytek z poslední tyče. Protože tyče ze skladu nemají zpravidla stejnou cenu jako tyče objednané, přepočítává se jejich hodnota zadaným koeficientem (skladovým faktorem), který určí uživatel. Použití stanovených (zpravidla krátkých) tyčí můžeme dokonce zvýhodnit, pokud zadáme skladový faktor záporný (to vlastně znamená odečtení nákladů na další skladování).

Následující systém je zastaralý a od roku 2015 se již nedodává. Jeho popis ponechávám z historických důvodů jako ukázku úspěšného řešení. Pro dělení materiálu je nyní k dispozici nová verze DelProTab, jehož popis naleznete na www.programujte.cz [ http://www.programujte.cz ] v sekci Ostatní, Umělá inteligence a robotika v článku Analýza a optimalizace - Software 1 [ http://programujte.com/clanek/2015090700-Analýza a optimalizace - Software 1 ]. 

Demo verze konstrukčního kusovníku

Stáhněte si ze sekce Download soubor CutOpt.zip a rozbalte do odpovídajícího adresáře na disku. Po odstartování CutOpt.exe se zobrazí úvodní obrazovka s hlavní nabídkou funkcí. Ovládání programu je popsáno ve funkci Nápověda → Obsah html nebo Nápověda → Obsah text, zde si předvedeme postupně základní funkce.

Jednoduchý test funkce algoritmu

V základní nabídce zvolte funkci Zpracování → Zadání. V horní části obrazovky stiskněte tlačítko Školní příklad. Okénka v levé části obrazovky představují vstupní hodnoty programu – nahoře seznam dodávaných tyčí, v dolní části seznam požadovaných položek, které se mají z dodávaných tyčí nařezat. Příklad je testovací, velikosti položek jsou vybrány tak, aby je bylo možno nařezat z dodávaných tyčí beze zbytku. V praxi takový případ asi málokdy nastane, praktickou úlohu si proto předvedeme později.

Stiskneme tlačítko Optimalizuj. V okénku pod tímto tlačítkem se začnou postupně objevovat údaje o jednotlivých krocích optimalizace – délka objednaných tyčí, délka tyčí ze skladu a zbytek po řezání. V tomto případě je délka zbytku pro kritérium podstatná. Skutečně po přibližně 100 iteracích nalezne systém nejlepší řešení, tj. plán řezání, při kterém nezbude žádný materiál. V tomto okamžiku stiskneme tlačítko Zastav a v oblasti vpravo dole se objeví výsledný nejlepší plán řezání: V levém seznamu počty a délky použitých tyčí a po označení některé tyče myší se vpravo objeví způsob řezání zvolené tyče.

Srovnání s teoretickým modelem

V plánu vpravo dole je znázorněn nejlepší chromozóm a jeho geny. Chromozóm je celý seznam použitých tyčí, geny představují rozpisy řezání jednotlivých tyčí. Populace je v průběhu výpočtu skrytá, představuje všechny současně uvažované alternativy. Její velikost se zadává v dialogu parametrů. Naopak vývoj kritéria vidíme v okénku optimalizace vpravo nahoře.

Praktický příklad

V praxi se zpravidla nepodaří nařezat tyče beze zbytku. Spokojíme se s tím, že odpad je po rozumné době výpočtu minimální. Ukázku vidíme, když klikneme myší na tlačítko Příklad z praxe a poté Optimalizuj. Vidíme, že po nějaké době se i při skutečném zadání z praxe najde plán s co možná nejmenším zbytkem. Pro ověření se dají číst také data exportovaná z tabulky z Excelu, výsledky se dají zapisovat do textového souboru nebo importovat do Excel tabulky.

Parametry algoritmu

Obrazovka pro zobrazení a úpravu parametrů ovlivňujících činnost algoritmu nebo realizujících požadavky uživatele se objeví, jestliže v základní nabídce zvolíme funkci Zpracování → Parametry. Obrazovka je rozdělena do několika polí týkajících se jednotlivých problémových oblastí. Zde uvedeme základní přehled, přesný popis parametrů je v nápovědě.

V poli PARAMETRY ALGORITMU se definují základní vlastnosti evolučního systému – velikost populace, četnost mutací a křížení v jedné populaci a počet elitních jedinců při aplikaci elitářského algoritmu. Nastavení těchto parametrů je vyhrazeno pokročilým uživatelům, nevhodné hodnoty mohou nepříznivě ovlivnit činnost algoritmu nebo dokonce výpočet znemožnit.

Vpravo v poli PREFERENCE zadáváme podmínky, které musí výsledný plán splňovat, a další okolnosti zadané uživatelem.

  • Neuvažovat poslední tyč – Jestliže vybíráme z tyčí různých délek, záleží na požadavcích provozu, zda je vhodnější, aby zbytek po dělení byl na co nejkratší tyči kvůli úspoře materiálu, nebo na co nejdelší tyči, aby ji ještě mohl použít při dalším dělení.
  • Preference algoritmu – V případě, že máme dlouhé tyče, je přesnější minimalizovat zbytky na každé tyče místo toho, abychom maximalizovali použité položky. Kompaktní rozpis sdružuje stejné rozpisy dělení a parametry Urychlení definují způsob, jak se vyloučí nevhodné chromozomy.
  • Vlastnosti materiálu a zařízení – Definuje dodatečné požadavky na optimalizační proces. Prořez představuje šířku nože, která se musí přičíst k délce položky kromě poslední. Počet položek na tyči usnadňuje práci zaměstnancům provozu při ukládání materiálu nebo nastavení vzdáleností, přitom alternativně je možné definovat určité procento položek, které nemusí uvedené pravidlo respektovat. Někdy je možné objednat jednu délku profilu v určitém rozmezí.
  • Všechny tyto údaje znamenají podmínky, které musí optimalizační proces splňovat. To je důležitá vlastnost evolučních systémů: V rámci určitých základních pravidel řeší problém poměrně obecně a při změně podmínek navrhnou okamžitě jiné řešení.
  • Významnou informací, kterou musíme dodat systému, je podmínka, při které optimalizační proces skončí. Buď máme seznam položek a objednáváme k nim profily, jak je tomu v konstrukčním kusovníku, nebo máme naopak profily a k nim vybíráme zakázky, jak je to v případě dělení válcovaných profilů.

Závěr

Optimalizace tyčového materiálu je první subsystém evoluční optimalizace, který jsem řešil. Tvořil integrovanou součást komplexního systému Konstrukční kusovník.Nejdůležitější výhodu tohoto evolučního modelu byla poměrně vysoká rychlost výpočtu. To by se pravděpodobně nepodařilo dosáhnout samotným genetickým algoritmem. Popsaný model byl spíše hybridní systém na bázi genetického algoritmu, uvedená rychlost je výsledkem zhruba půlročního hledání vhodných heuristických metod, které výpočet zrychlily proti původnímu řešení přibližně stokrát, při zachování flexibilní reakce na změněnou situaci na provozu a především vysokých úspor materiálu minimalizací odpadu.

Literatura

Teda, J., Chamrád, J.: Inteligentní systém optimalizace dělení hutního materiálu, časopis Automatizace č. 1, leden 2003, str.33-36


Článek stažen z webu Programujte.com [ http://programujte.com/clanek/2006122504-evolucni-optimalizacni-systemy-iii/ ].