facebook LinkedIN LinkedIN - follow
IT SYSTEM 3/2001

Genetické algoritmy a jejich využití v řízení výroby - II. část

Jiří Vejvoda





V podnikové praxi se velmi často objevuje problém vícekriteriálního rozhodování za omezené dostupnosti potřebných informací. Právě tento typ problémů je však základním zdrojem dalšího růstu produktivity práce. Příkladem může být problematika operativního řízení výroby.

Efektivní využití podnikových zdrojů je silně závislé na souladu mezi logistikou a kapacitním plánováním výroby. Systémů ERP, které se snaží tuto problematiku řešit, je celá řada. Praxe ale ukazuje, že prokazatelně úspěšné jsou jen ve výrobě velkosériové a hromadné. Problém je v tom, že klasické systémy MRP II plánují výrobu za předpokladu neomezených výrobních kapacit a skutečné kapacity jsou zahrnuty až následně některým z modulů CRP (Capacity Requirements Planning) a o konečných úpravách plánu rozhoduje plánovač. Tento řetězec přípravy operativních plánů přestává být efektivní s klesající velikostí dávky, snižováním velikosti skladů a zaváděním štíhlé výroby. Jako naprosto nevhodný se ukazuje při zavádění systémů JIT a Kanban. 

Řešení tohoto problému bylo hledáno v použití klasických matematických metod. Bylo sice dosaženo pozoruhodných výsledků, ale podstata problému vyřešena nebyla. Klasické matematické metody, jako jsou např. lineární programování, statistika nebo regresní a korelační analýza, jsou omezené různými požadavky (linearita, počet vzájemných vztahů, rozsah hodnot apod.). Navíc existují problémy, kde vůbec není možné tyto metody použít, protože je nelze popsat tradičními způsoby. Existence zpětných vazeb, skokové závislosti, náhodné rozhodování, poruchy , změna požadavků - to vše jsou aspekty, které jsou stále častěji součástí praktických problémů, a které způsobují selhání klasických metod. 

Takže problém není jen v tom, že co víme neumíme řešit, ale také v tom, že nevíme co nevíme.

Proto stále vzniká mnoho nových metod a postupů, které se snaží tento problém uspokojivě řešit. Jednou z těchto staronových metod je využití genetických algoritmů. Starých proto, že příroda je úspěšně užívá pro řešení podobných problémů již několik miliard let a nových proto, že si jejich sílu uvědomujeme teprve v poslední stovce let. 

Je velmi důležité si uvědomit, že v praxi nás nezajímají všechna řešení lepší než zadané podmínky, ale alespoň jedno řešení, které zadaným podmínkám vyhovuje. Proto je pro nás důležitější schopnost vyhledat řešení s možnost sledovat a řídit průběh tohoto hledání podle aktuálních podmínek, než získat řešení plné příčinných vztahů a podmínek existence z nepřesných nebo neaktuálních dat. 

Čím genetické algoritmy zaujaly
Pro přiblížení problému si představme výrobu a celou logistiku zajišťující tuto výrobu jako gigantickou n-rozměrnou šachovnici, kde všechny prvky, které se účastní výroby jsou obdobou figurek a úspěšně sehraná partie je vlastně nějaký produkt realizovaný na trhu. Ti co znají problém tak vědí, že současná výpočetní technika má problémy s klasickou dvourozměrnou šachovnicí o 64 polích a to ještě nemusí řešit problém, že většina figurek musí být včas na správném místě. 

Zde se projevuje jedna velmi zajímavá vlastnost genetických algoritmů. Jedinci v rámci jedné generace jsou volně rozptýleni po celém n-rozměrném prostoru omezeném pouze okrajovými podmínkami. Díky stavbě genetického algoritmu máme jistotu, že pokud některý jedinec nalezne vzhledem k zadaným podmínkám zajímavé řešení, tak ho příští generace bude zdokonalovat. Vzniká tedy jakýsi proces učení, který již v zárodku eliminuje velké množství variant neúspěšných a zároveň dochází k paralelnímu vyhledávání přípustných řešení. 

Klasické algoritmy jsou závislé na reálnosti matematického modelu systematicky prohledávající prostor dobrých i špatných řešení a tak nutně od jistého stupně složitosti problému překračují meze dané potřebou údajů v reálném čase za přijatelné náklady. Mnoho praktiků se snaží obejít tento problém a dopouští se neoprávněné linearizace a zjednodušení vstupních podmínek. Důsledkem jsou přesné výpočty s nepřesnými čísly, dochází ke ztrátě informace, chybám a náročný výpočet zpravidla slouží pouze jako alibi. 

Další velmi výhodnou vlastností řešení založených na genetických algoritmech je možnost v průběhu výpočtu sledovat, který z parametrů nebo která z podmínek se stává omezující, případně naopak kterého parametru není dosahováno a řešení začíná konvergovat mimo pásmo přípustnosti. Lze pak operativně a velmi jednoduše zasáhnout formou změny priorit, termínů nebo změnou podmínek a ve vyhledávání přípustného řešení pokračovat bez jakékoliv ztráty informací z dosavadního průběhu výpočtu. U klasických metod je při jakékoli změně výchozích podmínek potřeba celý výpočet opakovat od začátku.

Datová náročnost, doba řešení problému a snadnost ovládání realizovaných programů je na takové úrovni, že je bez problémů možno zařadit tyto systémy do dílenského plánování. Na druhé straně výkonnost a dosahované výsledky předurčují systémy využívající tyto genetické algoritmy k přehodnocení mnoha přístupů vrcholového managementu a k nahrazení dosavadních velmi drahých a náročných systémů v kvalitě i v čase.

Vhodné úlohy pro genetické algoritmy
Převaha genetických algoritmů se projevuje u složitých úkolů. Obecně je možno o říci, že se jedná o rozsáhlé nelineární problémy rozhodování za velké neurčitosti s mnoha faktory ovlivňujícími výsledek řešení. Tedy takové problémy, kde klasické metody neznají algoritmus řešení nebo jsou pro datovou náročnost nepoužitelné. 

Jeden z důvodů síly genetických algoritmů je v samotné podstatě algoritmu hledání řešení, které spočívá v tom, že nehledáme nějaké určité řešení, ale skupinu přípustných řešení, z nichž vybíráme to nejlepší. Od klasických metod (například Monte Carlo) se genetické algoritmy odlišují způsobem, kterým se přibližujeme k řešení. Převaha genetických algoritmů se projevuje ve složitých problémech s mnoha parametry.

Současný stav využití genetických algoritmů 
Pokud je nám známo je ve světě již řada praktických využití genetických algoritmů ve všech oblastech lidského podnikání. 

Za všechny alespoň jeden zajímavý příklad z oblasti výroby zemědělských strojů ve střední Americe. Firma vyrábí různé zemědělské stroje na zakázku podle přání jednotlivých zákazníků. Dá se tedy říci, že každý dodaný stroj je unikátní a tedy velikost výrobní dávky je velmi blízká 1. Při rozsahu sortimentu a krátkých termínech dodávek všechny klasické metody řízení výroby selhávaly, docházelo k neustálým posuvům termínů a hromadění zásob a výroba se potýkala s neúměrně velkou rozpracovaností. V zhledem ke stále se měnícím podmínkám a novým objednávkám se objevila potřeba každý den upravovat operativní plán výroby. 

Genetické algoritmy zde našly uplatnění v nástroji pro sestavení a doplnění operativního plánu výroby. 

Centrální počítač po skončení každého pracovního dne předá potřebné údaje do výroby, kde přímo na hale běžně dostupné PC přes noc projde tisíce přípustných operativních plánů a připraví je pro zahájení příští směny. Tak je nalezeno přijatelné řešení z hlediska současného stavu výroby a nových podmínek a požadavků. 

Nízká náročnost na výpočetní techniku
Aplikace výše popsaných metod nevyžaduje nejen radikální změnu struktury firmy, ale dokonce ani změnu technického vybavení. Čím je to umožněno:

1) Velmi složité exaktní výpočty u klasických metod vyžadující velké množství parametrů a požadavky na data, která prakticky není možné jednorázově dodat. Toto nahrazují genetické algoritmy efektivním způsobem vyhledávání mnohanásobným opakováním jednoduchých operací - náhodný výběr (selekce), křížení a mutace v prostředí, které zajišťuje učení.

2) Datová náročnost je vzhledem k použité technologii značně nižší. Dochází k značné úspoře při pořizován dat.

3) Problematicky algoritmizovatelné řešení je nahrazeno výběrem nejlepšího řešení z velkého množství přijatelných řešení. 

4) Při přerušení úlohy není nutno zahájit výpočet od začátku, jak je tomu u klasických metod, ale je možno pokračovat ve výpočtu.

5) Při změně počtu nebo rozsahu parametrů je nutno u klasických metod zpravidla měnit algoritmus výpočtu, což není v požadovaném reálném čase prakticky možné a omezení, která vyplývají z nutných zjednodušení prakticky vylučují jejich použitelnost. Genetické algoritmy umožňují měnit parametry i během výpočtu. Změny mají vliv pouze na délku výpočtu a umožňují tak uživateli sestavit operativní plán , který je možno kdykoli přizpůsobit měnícím se podmínkám a tak pomáhá nalézat průchodná řešení za respektování mnoha podmínek, parametrů, priorit a termínů. Algoritmus nás též upozorňuje na parametry, které umožní plán zprůchodnit nebo vylepšit.

Závěr
Přes veškerou jednoduchost pro uživatele systémů na bázi genetických algoritmů představuje nasazení takovýchto produktů jednu změnu. Změnu v interpretaci určitých jevů a trénink způsobu jak na tyto jevy reagovat.

Pozn.: Autor pracuje jako konzultant ve firmě Janouch a.s., která je výrobcem SW pro řízení výroby na bázi genetických algoritmů)

Chcete získat časopis IT Systems s tímto a mnoha dalšími články z oblasti informačních systémů a řízení podnikové informatiky? Objednejte si předplatné nebo konkrétní vydání časopisu IT Systems z našeho archivu.


Inzerce

Konec papírování, digitalizujte a usnadněte si práci!

IT Systems 3/2024V aktuálním vydání IT Systems jsme se zaměřili na vývoj digitalizace ve světě peněz, tedy v oblasti finančnictví a pojišťovnictví. Dozvíte se například, proč je aktuální směrnice PSD2 v inovaci online bankovnictví krokem vedle a jak by její nedostatky měla napravit připravovaná PSD3. Hodně prostoru věnujeme také digitalizaci státní správy a veřejného sektoru, která nabírá obrátky.