TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
V tomto starším článku o umělé inteligenci se zabývám jejím méně známým oborem, genetickými algoritmy. Vedle všeobecných informací popisuji konkrétní praktické aplikace optimalizačních úloh, které jsem na počátku své činnosti v tomto oboru realizoval. Uvádím také modifikace, které přizpůsobovaly řešení praktickým podmínkám a urychlovaly naleznení požadovaného řešení. Aktuální aplikace a nové poznatky popisuji v dalších článcích na tomto serveru.
Pojem genetický algoritmus
Genetické algoritmy patří do třídy evolučních algoritmů, které mimo ně zahrnují také evoluční programování, evoluční strategii a genetické programování. Jsou to vyhledávací algoritmy založené na mechanismu přirozeného výběru a principech genetiky. Jejich velkou výhodou je poměrná jednoduchost. Ideovým vzorem pro genetické algoritmy byly principy vývoje, které se uplatňují v přírodě. Zde existují populace jednotlivých živočišných druhů, složených z jedinců různých vlastností. Tyto vlastnosti jsou prvotně zakódovány v jejich genech, které tvoří větší celky, chromozómy. Při křížení vznikají noví jedinci, kteří mají zpravidla náhodně část genů od jednoho rodiče a část genů od rodiče druhého. Přitom ve zvlášť vyjímečném případě může dojít k náhodné změně některého genu v chromozómu, tzv. mutaci, která může být pro další vývoj druhu příznivá nebo ne. Podle svých vlastností má každý z potomků větší nebo menší schopnost obstát v přirozeném výběru a vytvořit další generaci. Proces výběru se stále opakuje a v jeho průběhu se zlepšují genetické vlastnosti daného druhu. Tak probíhala celá evoluce v přírodě.
V teorii umělé inteligence je genetický algoritmus proces postupného vylepšování populace jedinců opakovanou aplikací genetických operátorů, který vede k evoluci takových jedinců, kteří lépe vyhovují stanoveným podmínkám než jedinci, ze kterých vznikli. Proces konverguje k situaci, kdy je populace tvořena jen těmi nejlepšími jedinci. Hlavním principem je kopírování a vyměňování řetězců - chromozómů. Chromozóm má pevnou délku, jednotlivé pozice tvoří geny. Geny reprezentuje často binární 0 nebo 1, ale obecně mohou mít libovolnou hodnotu. Množina chromozómů tvoří populaci. Každý chromozóm v populaci má definovánu hodnotící funkci, nazývanou fitness funkce, která charakterizuje vhodnost chromozómu.
Genetický algoritmus definuje operátory křížení, mutaci a reprodukci. Operátor křížení znamená vytváření nových jedinců podle následujícího pravidla: Z populace vybereme náhodné páry a náhodně zvolíme pozici k. Do prvního potomka zkopírujeme geny 1 až k prvního rodiče a geny k + 1 až n druhého rodiče, kde n je počet genů, a do druhého potomka kopírujeme geny opačně.
Při aplikaci operátoru mutace vybereme s malou pravděpodobností náhodný gen v náhodném chromozómu a změníme jeho hodnotu z 0 na 1 nebo naopak. Operátor reprodukce kopíruje chromozómy do nové populace. Chromozómy s vyšší fitness hodnotou jsou do nové populace kopírovány s vyšší pravděpodobností. Pravděpodobnost kopírování je dána vzorcem pi = fi / Suma(f), kde
- pi = pravděpodobnost reprodukce i-tého chromozómu
- fi = hodnota fitness funkce i-tého chromozómu
- Suma(f) = součet všech hodnot fitness funkce v populaci
Někdy se používá tzv. elitářský mechanismus: Určité procento nejlepších jedinců je do nové generace reprodukováno vždy.
V praxi se pomocí genetických algoritmů řeší úlohy optimalizace, využívají se k vyhledávání nejlepší topologie, v technologii a výrobě a v průmyslové automatizaci a jako alternativní metody učení neuronových sítí. Na rozdíl od gradientních metod, které reprezentují hledání lokálního minima nebo maxima pomocí jednoho zpřesňujícího se řešení, představují genetické algoritmy jiný přístup, který používá populaci prozatímních řešení, jež paralelně procházejí parametrický prostor a navzájem se ovlivňují a modifikují pomocí genetických operátorů. Tím se dosahuje toho, že populace jedinců najde správné řešení rychleji, než kdyby se prohledával prostor izolovaně.
Praktické využití evoluční optimalizace
V dále popsaných projektech jsem realizoval genetickou optimalizaci na počátku své činnosti v tomto oboru. Od roku 2015 již nejsou tyto systémy dodávány. Aktuální informace obsahují mé další články na tomto serveru www.programujte.com v sekci Ostatní, Umělá inteligence a robotika, například Umělá inteligence ve výrobním podniku, Analýza a optimalizace software 1 až Analýza a optimalizace software 3, Zobrazení grafu s použitim evoluční metody a další. Praktické ukázky současných aplikací systémů s umělou inteligencí, demo a výukové programy najdete na internetové stránce: www.optiintelligent.cz.
Konstrukční kusovník
Prvním projektem, kde jsem realizoval genetickou optimalizaci, byl konstrukční kusovník, vytvořený pro podporu práce konstruktéra. Umožňuje mu vytvářet detailní rozpis 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. Kusovník vzniká principiálně v konstrukci a pak je využíván například technologickými útvary, které do něj doplňují další specifické údaje.
Navrhovaná konstrukční řešení u jistých typů výrobků 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íly je nutno z původních profilů nařezat.
Optimalizační část Konstrukčního kusovníku plánuje způsob 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í). Definování genů, chromozomů i celé populace je znázorněno na obr. 1.
Obr. 1: Prvky genetického algoritmu v úloze optimalizace dělení materiálu
Dělení válcovaných profilů
Zatímco při dělení materiálu v kusovníku je nutno nařezat stanovené množství položek různých délek tak, aby docházelo k co nejmenší ztrátě a k dispozici jsou jednak polotovary na skladě, jednak je možno objednat profily ve stanovených délkách, při optimalizaci dělení válcovaných profilů máme právě opačný úkol. Ze zásobníku zakázek se mají vybírat postupně takové položky, které lze nařezat z profilů daných délek, které jsou právě vyválcovány. V předchozím případě se k položkám vybíraly profily, nyní se k profilům vybírají položky. Dosavadní aplikace navíc sloužily pro útvary konstrukce a přípravy výroby a proto odezva systému sice musela být přiměřená, ale přesto nebyla kritická, avšak při řízení v reálném čase, které řešíme v popisovaném systému, se nároky na rychlost výpočtu podstatně zvyšují.
Plošná optimalizace
Součást informačního systému realizuje dělení plošného materiálu tak, aby se ušetřilo co nejvíce výchozího polotovaru a snížily náklady na výrobu. Jako vstupní hodnoty získá rozměry zdrojových tabulí, souřadnice již vyřezaných částí a rozměry součástí, které se mají vyřezat. Výsledkem je optimální umístění jednotlivých součástí na zadané plechy. Tento systém se již používá v předvýrobních etapách, připravuje se návrh plánu řezání konkrétních plechů.
V předvýrobní etapě slouží ke stanovení počtu plechů potřebných vlastností s využitím zbytků, které jsou na skladě. Při vlastním dělení navrhne umístění jednotlivých dílů na plechy. Přitom vždy zohledňuje řadu provozních podmínek, jako je velikost řezných spár, vlastnosti podložky a pod.
Plán tavení
Systém realizuje rozhodovací proces při plánování taveb v pecích různých typů ve slévárnách nebo ocelárnách, v integraci s firemním informačním systémem. Jedná se o proces volby nejlepší z velkého množství alternativ, kterou dosud prováděli intuitivně pracovníci přípravy výroby na základě svých dlouholetých zkušeností, přičemž neměli jistotu, že se jim podaří nalézt skutečně tu nejlepší možnost. Výstupem je stanovení optimálního plánu taveb s ohledem na snižování výrobních nákladů. Musí se přitom zohledňovat řada dalších faktorů: zaměnitelnost materiálů, dostatek formovacích rámů, pracovní doba zaměstnanců, provozní podmínky pecí a také dohodnuté odběrové diagramy. Nejedná se proto pouze o optimalizaci z hlediska energetické náročnosti, ale celého předvýrobního a vlastního technologického procesu.
Optimalizace kování
Součást informačního systému plánuje postup tváření a ohřívání v kovárně a pohyb ingotů a výkovků na lisech. Do kovárny přicházejí ingoty, ze kterých se mají kovat výkovky. Ukládají se do ohřívacích pecí a ve vhodnou dobu se zpracují na lisu. Ke každé zakázce definuje technolog pořadí operací, které se mají provést. Jedná se jednak o tváření na listu, jednak o další ohřívání mezi tvářením. Přitom je nutno respektovat požadavky uvedené na technologickém předpisu, rozměry výkovků a rozměry a teplotní charakteristiky pecí i charakteristiky a dobu výměny nástrojů na lisu.
Dopravní dispečerský systém
Připravovaný dopravní dispečerský systém řeší optimalizaci pohybu lokomotiv a železničních vozů tak, aby se ušetřily provozní náklady. Optimalizace je plánována ve dvou úrovních - optimalizace pohybu vlaků mezi jednotlivými uzly tak, aby s co nejmenšími náklady byly realizovány požadované výkony a optimalizace posunu s co nejmenším počtem úkonů a dalším snížením nákladů.
Modifikace algoritmů
Uvedené praktické úlohy nás vedly k určitým modifikacím genetických algoritmů.
Definice genů a chromozómů
V genetických algoritmech se definuje chromozóm jako řetězec genů pevné délky, přičemž gen zpravidla má binární hodnotu 0 a 1, případně je to reálné číslo. Tuto zásadu nebylo možné v uvedených případech téměř nikdy dodržet. Definice genů se případ od případu lišila, ale vždy to byl seznam určitých vlastností vztahující se k nejmenší jednotce optimalizace.
V případě tyčové optimalizace to byl popis dělení každé tyče, t.j. seznam pořadových čísel položek, které měly být z dané tyče nařezány. U plošné optimalizace byla zvolena transformační matice položky spolu s identifikací plechu, představující geometrické umístění dané položky.
Obdobně při plánování tavících procesu byl genem předpis pro jednu tavbu a v kovárně jedna operace při kování.
Z uvedeného rovněž vyplývá, že nebylo možné dodržet pravidlo chromozómů stejné délky. Při náhodném výběru se spotřebuje více nebo méně tyčí nebo tabulí, provede různé množství taveb nebo použije odlišný počet přesunů a ohřívání výkovků, což se sice projeví ve výběru plánu do další generace, ale při vytváření chromozómů bylo nutné s tím počítat. Naše knihovna umělé inteligence samozřejmě obsahuje také algoritmy pro chromozómy stejné délky, které jsou podstatně jednodušší.
První vytvoření populace, mutace
V obou případech je nutné přihlížet ke specifickým podmínkám výrobního procesu:
- při výběru, třebaže v podstatě náhodném, je nutné respektovat pravidla vyplývající z charakteru výrobního procesu
- i při respektování všech omezení není každý prvek v daném okamžiku stejně vhodný k tomu, aby byl do chromozómu vybrán
Řešením byla kombinace náhodného výběru s pravidlovým systémem. V dosavadních projektech stačilo realizovat jej procedurálně, ale v obecném případě to nemusí platit. Výsledkem byl v čase proměnný seznam, který pro každý prvek nebo skupinu prvků určoval pravděpodobnost, s jakou má být vybrán do chromozómu. Seznamy byly buď binární - může - nemůže být v daném okamžiku vybrán, nebo množiny reálných čísel, určujících pravděpodobnost výběru.
Například u tyčové optimalizace taková pravděpodobnost byla průběžně definována vždy pro položky stejné délky, a položky, které měly délku větší než byl zbytek na tyči nebo položky, jejichž zásoba již byla vyčerpána, měly pravděpodobnost výběru 0.
Křížení
Pro urychlení optimalizačního procesu se výběr rodičovských chromozómů opět neprovádí zcela náhodně, ale pomocí heuristického hodnocení chromozómů v populaci. Navíc pokud bychom v průběhu křížení převzali část plánu z jednoho chromozómu a část z druhého, některé položky by se objevily ve výsledném plánu vícekrát a některé by chyběly.
Proto je definována funkce fitgen, která zhodnotí, zda se při křížení určitý gen ještě může do chromozómu použít nebo ne. Postup výběru genů odpovídá heuristickému hodnocení jejich kvality. Po vyčerpání všech genů z obou chromozómů je potomek doplněn podle pravděpodobnostní funkce tak jako při mutaci.
Reprodukce
Při výběru nejvhodnějších variant do další populace se často muselo přihlížet k více kritériím. Byly zvoleny dvě cesty:
- V některých projektech bylo definováno více hodnotících funkcí a uživatel si pomocí přepínače zvolil, které hodnocení preferuje. Tak například při optimalizaci tavení má uživatel možnost požadovat maximální zaplnění pecí nebo minimální cenu na kilogram odlitku
- V jiných projektech se vypočítaly hodnoty více kritérií a každému se po dohodě s uživatelem přisoudila určitá váha. Například v optimalizačním systému válcovny byl kromě celkového zbytku materiálu preferován zbytek právě řezaného vývalku koeficientem, který představoval důvěru, že v průběhu kampaně přijdou takové předvalky, které celkový výsledek procesu zlepší
Příklad
Na obrázku 2 je znázorněn jednoduchý příklad, kdy by mechanické použití genetického operátoru křížení vedlo k chybnému výsledku. Z profilů na skladě se mají nařezat po dvou položkách delších, jejichž součet délek odpovídá přesně profilu, a dvou kratších, kdy zůstane po řezání určitý zbytek. Pokud bychom oddělili části rodičovských chromozómů tak, jak znázorňuje červená čára, můžeme dostat doporučení, abychom nařezali pouze 4 položky delší. Toto doporučení bude dokonce v hodnotící funkci preferováno, protože nezůstává žádný zbytek. Dvě delší položky by nám pak zůstaly na skladě a dvě kratší by nám v dodávce chyběly.
Obr. 2: Příklad, kdy nelze použít standardní genetické křížení
Závěr
Popsané produkty byly dodávány do roku 2014 jako součást informačních systémů. Historicky první projekt, optimalizace dělení tyčového materiálu v konstrukčním kusovníku, byl implementován ve 4 firmách. Úspora materiálu byla dosažena efektivním rozdělením tyčí potřebné délky a minimalizací odpadu, kombinací různých délek polotovaru a využitím zbytků materiálu po dělení nebo určením nejvhodnější délky objednávaných tyčí. Popsaný systém přinášel také úsporu lidské práce. Při simultánním zpracování byl výsledek pomocí počítače k dispozici téměř ihned, pracovník počítal tuto úlohu na kalkulačce několik minut a to ještě věděl předem, z kolika tyčí se bude řezat. Při ověřování modelu optimalizace dělení profilů pro válcovnu byla úspora materiálu 1 - 2 bloky na kampaň, při simultánním návrhu tavících plánu vycházela úspora 1 - 2 tavby za sledovaný úsek 1 týden.
Od roku 2015 již žádný z těchto systémů není dodáván a jsou nahrazeny novější systémy. Jejich popis naleznete v dalších článcích na tomto serveru.
Demo programy a software zdarma
Další materiály k tématu Umělá inteligence, demo programy k výuce a jednoduché verze inteligentních systémů zdarma naleznete na webové stránce naší firmy www.optiintelligent.cz. Stránku průběžně doplňuji o další výukové materiály.
Literatura
- Šíma, J., Neruda, R.: Teoretické otázky neuronových sítí, Praha, MATFYZPRESS,1996
- Teda, J., Chamrád, J.: Inteligentní systém optimalizace dělení hutního materiálu, časopis Automatizace č. 1, leden 2003, str. 33 - 36
- Teda, J.: Inteligentní optimalizační software, Mezinárodní konference Svět informačních systémů 2005, Zlín 2005, str. 282 - 288
- Vondrák, I.: Umělá inteligence a neuronové sítě, Ostrava, VŠB TU, 1994
