Genetické algoritmy a jejich aplikace v praxi
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

Genetické algoritmy a jejich aplikace v praxiGenetické algoritmy a jejich aplikace v praxi

 

Genetické algoritmy a jejich aplikace v praxi

Google       Google       26. 7. 2005       37 720×

Ve svém článku bych chtěl navázat na informace v seriálu o umělé inteligenci a zabývat se méně známým oborem této teorie, genetickými algoritmy. Vedle všeobecné informace o genetických algoritmech popisuji konkrétní praktické aplikace optimalizačních úloh, které tvoří součást informačních systémů dodávaných naší firmou. Uvádím také modifikace, které přizpůsobují řešení praktickým podmínkám a zrychlují naleznení požadovaného řešení. V závěru shrnuji ekonomické přínosy a odkazuji na volně šířitelné demo a výukové programy z této oblasti.

..
Reklama
Reklama

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

Konstrukční kusovník

Prvním projektem firmy VÍTKOVICE ITS s.r.o., využívajícím 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 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 jsou z části dodávány jako součást firemních informačních systémů, zčásti jsou dokončovány nebo předány do ověřovacího provozu. Historicky první projekt, optimalizace dělení tyčového materiálu v konstrukčním kusovníku, je v současné době implementován ve 4 firmách. Úspora materiálu je 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áši 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.

Praktické ukázky aplikací genetických optimalizačních systémů jsou na internetové stránce: www.volny.cz/jaroslav.teda

Literatura

  1. Šíma, J., Neruda, R.: Teoretické otázky neuronových sítí, Praha, MATFYZPRESS,1996
  2. Teda, J., Chamrád, J.: Inteligentní systém optimalizace dělení hutního materiálu, časopis Automatizace č. 1, leden 2003, str. 33 - 36
  3. Teda, J.: Inteligentní optimalizační software, Mezinárodní konference Svět informačních systémů 2005, Zlín 2005, str. 282 - 288
  4. Vondrák, I.: Umělá inteligence a neuronové sítě, Ostrava, VŠB TU, 1994

×Odeslání článku na tvůj Kindle

Zadej svůj Kindle e-mail a my ti pošleme článek na tvůj Kindle.
Musíš mít povolený příjem obsahu do svého Kindle z naší e-mailové adresy kindle@programujte.com.

E-mailová adresa (např. novak@kindle.com):

TIP: Pokud chceš dostávat naše články každé ráno do svého Kindle, koukni do sekce Články do Kindle.

1 názor  —  1 nový  
Hlasování bylo ukončeno    
0 hlasů
Google
(fotka) Jaroslav TedaAutor se zabývá vývojem inteligentních softwarových systémů ve firmě OPTI Intelligent s.r.o. Publikoval na seminářích včetně mezinárodních i zahraničních a v časopise Automatizace.
Web    

Nové články

Obrázek ke článku NEWTON Media prohledá 200  milionů mediálních zpráv během sekund díky Cisco UCS

NEWTON Media prohledá 200 milionů mediálních zpráv během sekund díky Cisco UCS

Česká společnost NEWTON Media provozuje největší archiv mediálních zpráv ve střední a východní Evropě. Mezi její zákazníky patří například ministerstva, evropské instituce nebo komerční firmy z nejrůznějších oborů. NEWTON Media rozesílá svým zákazníkům každý den monitoring médií podle nastavených klíčových slov a nabízí online službu, kde lze vyhledat mediální výstupy v plném znění od roku 1996.

Reklama
Reklama
Obrázek ke článku Delphi 10.1.2 (Berlin Update 2) – na co se můžeme těšit

Delphi 10.1.2 (Berlin Update 2) – na co se můžeme těšit

Touto roční dobou, kdy je zem pokrytá barevným listím a prsty křehnou v mrazivých ránech, se obvykle těšíme na zbrusu novou verzi RAD Studia. Letos si však ale budeme muset počkat na Godzillu a Linux až do jara. Vezměme tedy za vděk alespoň updatem 2 a jelikož dle vyjádření pánů z Embarcadero se budou nové věci objevovat průběžně, pojďme se na to tedy podívat.

Obrázek ke článku Konference: Moderní datová centra pro byznys dneška se koná už 24. 11.

Konference: Moderní datová centra pro byznys dneška se koná už 24. 11.

Stále rostoucí zájem o cloudové služby i maximální důraz na pružnost, spolehlivost a bezpečnost IT vedou k výrazným inovacím v datových centrech. V infrastruktuře datových center hraje stále významnější roli software a stále častěji se lze setkat s hybridními přístupy k jejich budování i provozu.

Obrázek ke článku Konference: Mobilní technologie mají velký potenciál pro byznys

Konference: Mobilní technologie mají velký potenciál pro byznys

Firmy by se podle analytiků společnosti Gartner měly  rychle přizpůsobit skutečnosti, že mobilní technologie už zdaleka nejsou horkou novinkou, ale standardní součástí byznysu. I přesto - nebo možná právě proto - tu nabízejí velký potenciál. Kde tedy jsou ty největší příležitosti? I tomu se bude věnovat již čtvrtý ročník úspěšné konference Mobilní řešení pro business.

loadingtransparent (function() { var po = document.createElement('script'); po.type = 'text/javascript'; po.async = true; po.src = 'https://apis.google.com/js/plusone.js'; var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(po, s); })();
Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý