Uplatnění agentových kolon při ovládání a optimalizaci průmyslových procesů (2) Pavel Burian Ústav počítačové a řídicí techniky Vysoká škola chemicko-technologická v Praze, Technická 5, 166 28 Praha 6, tel: 220 443 773, e-mail:
[email protected]
Abstrakt: Hmyzí roj, včelí kolona, mravenčí kolona, mraveniště pracuje bez potřeby nějakého dohlížení, jejich společná práce je samoorganizující se a koordinace činnosti jednotlivců-agentů vzniká na základě různých interakcí mezi jednotlivci-agenty v koloně a mezi prostředím. I když tyto interakce mohou být poměrně jednoduché jejich výsledné působení může vést k řešení poměrně obtížných problémů. Např. problému obchodního cestujícího (Traveling Salesperson Problem), problému rozvrhování úloh na dílně, provozu (Job Shop Scheduling Problem), problematiky tzv. celulární výroby (Cellular Manufacturin), problémů řízení výroby, problémů z oblasti umělé inteligence. Takovéto chování může být nazváno „inteligencí roje, hejna, kolony“. Změny a poruchy výrobního provozu vyžadují rychlou reakci a snadno zaveditelné a modifikovatelné systémy řízení, což může být pro systémy, jejichž vzorem chování jsou uvedené kolony, poměrně jednoduché. Klíčová slova: včelí a mravenčí kolona, feromony, tanec včel, samoorganizovatelnost, problém obchodního cestujícího, rozvrhování úloh na dílně, provozu, celulární výroba (Cellular Manufacturing), řízení a ovládání výroby. Pokračování z minulého čísla.
5. Systém shánění potravinových zdrojů včelí kolonou s pomocí kývavého, kmitavého tance (waggle dance) a prozkoumáváním květinových polí Jak se chová hmyzí, včelí kolona při shánění potravy ? Model chování sebeorganizující se kolony včel (Honey Bees) je uveden v [Lemmens N., 2007]. V tomto modelu včely shánějící potravu navštěvují květinová pole (Flower Patches), vrací se do úlu s nektarem s výkonností respektující vlastnosti květového, nektarového pole. Sběr nektaru poskytuje zpětnou vazbu týkající se okamžitého stavu toku nektaru do úlu. Výkonnost je funkcí kvality nektaru, jeho prémiových vlastností a vzdálenosti květinového pole od úlu. Nastavení zpětné vazby odpovídá limitnímu prahu, tj. práhu u vchodu „verbovacího“, získávajícího signálu známého jako kývavý, kmitavý tanec (Waggle Dance). Délka závisí na odpovídající prahové, limitní hodnotě a ukazateli rentability. Kývavý, kmitavý tanec je prováděn na „tanečním patře“, které pozorují jedinci shánějící potravu. Jedinci shánějící potravu si mohou náhodně vybrat tanečníka, pozorovat jej, následovat jej a naučit se od něj polohu a umístění květového pole a opět se z pole vrátit do úlu. Tento zpětnovazební model umožňuje dobré využití zdroje potravin. Tento tanec SYSTÉMOVÁ INTEGRACE 4/2007
31
Zpravodajství
resp. včelí komunikační jazyk se skládá z řady měnících se levo a pravo stranných smyček, roztroušených do segmentů, v kterých zadeček tancující včely, kmitá ze strany na stranu. Nábor (Recruitment) jedinců, příslušníků kolonie na získání potravy uskutečňují včely informováním o směru a vzdálenosti potravinových zdrojů prostředky kývavého, kmitavého tance (Waggle Dance) prováděném ve vertikálním směru u vchodu – česna (Combs) včelího úlu. Trváním taneční fáze se měří vzdálenost k potravinovému řetězci. A úhel mezi sluncem a osou segmentu tance ve vertikálním směru u vchodu – česna (Combs) reprezentuje azimut úhlu mezi sluncem a směrem, v kterém jedinec získaný na základě náboru, by mohl najít cíl (zdroj potravy) [Michelsen A., 1992], [Dyer F., 2002]. Pro navigaci v neznámém světě, prostoru hmyz (včely, pouštní mravenci) používá strategii zvanou cestovní integrace (Path Integration - PI). Včely jsou schopny vypočítat svou okamžitou polohu z minulé trajektorie průběžně a jako následek se mohou vrátit ke svému startovnímu bodu výběrem přímé trasy raději než po své původní trajektorii. Tato navigace se skládá hlavně z tzv. cestovní integrace (Path Integration - PI), která je spojitě aktualizována vektorem integrujícím všechny řízené úhly a všechny pokryté vzdálenosti [Lambrinos D., 2000]. Při konstrukci cestovní integrace – konstrukci Path Integration – PI vektoru, hmyz nepoužívá sumarizující matematický vektor tak, jak to dělá člověk. PI vektor reprezentuje znalosti hmyzu o směru a vzdálenosti vůči svému cíli cesty. Když na cestě existují překážky, hmyz se vrací ke zdroji potravy na základě navigace pomocí zemních značek (Landmarks) např. značka může být jezero, les, aj. [Collett P., 2003], [Collett T., 2004]. Zemní značky dělí celou cestu do segmentů a každá značka má svůj PI vektor.
6. Příklad postupu řešení úloh založených na chování včelích kolon s využitím kývavého, kmitavého tance (waggle dance) a shánění (foraging) potravy, prozkoumáváním květinových polí Existují [Chong C. S. C., 2006] dvě nejdůležitější charakteristiky včelí kolony při vyhledávání zdrojů potravy: kývavý, kmitavý tanec (Waggle Dance) a shánění (Foraging), prozkoumávání (Exploration) nektaru květinových polí. Jedinec shánějící potravu (Forager) fi při vrácení se do úlu z prozkoumávání (exploration) květinových, nektarových polí bude zkoušet s pravděpodobností p provádět kývavý, kmitavý tanec v trvání D = diA, na tanečním patře, kde di je úměrné výnosnosti, rentabilitě a A je váhový (Scaling) faktor. Dále bude zkoušet jiný jedinec s pravděpodobností ri pozorovat a následovat náhodně vybraného tanečníka. Pravděpodobnost ri se též dynamicky mění s rentabilitou, výnosností. Jestliže si jedinec shánějící potravu vybere následovat vybraného tanečníka, použije cestu prováděnou, realizovanou tanečníkem ve směru květového, nektarového pole. Cesta jedince shánějícího potravu je řada hraničních bodů od zdroje (úlu) k místu určení (nektaru v květovém poli). Nektar je sladká vonná šťáva
32
SYSTÉMOVÁ INTEGRACE 4/2007
Michael Hallén: "Musíme naslouchat zákazníkům, jinak nebudeme úspěšní"
vyměšovaná květními žlázami k lákání opylujícího hmyzu. Opylování je přenesení pylu z prašníku na bliznu za účelem oplození a vytvoření semene. Pro rozvrh úloh na dílně by mohla být výnosnost, rentabilita (Profitability Rating) účelovou funkcí, která v našem případě je Pracovní rozpětí (Makespan). znamená výnosnost, rentabilitu jedince shánějícího potravu, Nechť Pfi definovanou vztahem dle [Chong C. S. C., 2006]:
Pf
i
=
1
C
(6.1)
i max
i
kde C max je Pracovní rozpětí (Makespan) rozvrhu generovaného nějakým jedincem shánějícím potravu fi . Průměrná výnosnost, rentabilita včelí kolony Pfcolony je definovaná vztahem dle [Chong C. S. C., 2006]:
Pf
colony
1 n 1 ∑ j j =1 n C
=
(6.2)
max
kde n je počet tanečníků (Waggle Dancers) v čase t, j C max je Pracovní rozpětí (Makespan) rozvrhu generovaného nějakým jedincem shánějícím potravu fj, který provádí kývavý, kmitavý tanec. Trvání tance di je dáno vztahem:
d
i
=
Pf Pf
i
(6.3)
colony
Pravděpodobnost ri následovníka cesty je přiřazena podle výnosnosti, rentability (Profitability Ratings) nějakého jedince shánějícího potravu a kolonie, a přiřazení je založeno na Tab 6.1. dle [Nakrani, S., 2004]. Výnosnost, rentabilita (Profitability Ratings) Pfi < 0,9Pfcolony 0,9 Pfcolony< Pfi <0,95 Pfcolony 0,95 Pfcolony< Pfi <1,15 Pfcolony 1,15Pfi < Pfcolon Tab 6.1. Vyhledávací tabulka přiřazující kývavého tance dle [Nakrani, S., 2004].
pravděpodobnost
ri 0,6 0,2 0,02 0,00 následovníkům
Jedinci shánějící potravu cyklicky konstruují řešení rozvrhu úloh na dílně, provozu. Jedinec shánějící potravu se pohybuje podél hran od jednoho uzlu grafu k jinému uzlu disjunktního grafu (Viz např. graf na obr. 2.1 v odst. 2.2 v první části tohoto článku, uveřejněném v předchozím čísle a graf na obr. 7.1.) a konstruuje cesty SYSTÉMOVÁ INTEGRACE 4/2007
33
Zpravodajství
reprezentující řešení. Jedinec shánějící potravu musí navštívit uzel jednou a pouze jednou, začíná v počátečním (např. zdrojovém) uzlu a končí v koncovém (Sink) uzlu. A tak konstruuje kompletní řešení. Když je jedinec shánějící potravu ve specifickém uzlu, může se pouze přesunout do následujícího uzlu, který je definován ve výpisu momentálně povolených uzlů, vložený nadřazenými omezeními operací a kdy si jedinec shánějící potravu vybírá následující uzel, na základě následujícího vztahu, pravidla:
ρ(t)ij (1/ d ij) ∑ ρ(t)ij (1/ d ij) α
P (t) =
β
α
ij
β
(6.4)
j∈_ povolenй_ uzly
ρij je poměr hrany mezi uzlem i a uzlem j. dij je heuristická vzdálenost mezi uzlem i a uzlem j. P ij je pravděpodobnost vybrání od uzlu i a uzlu j. β je volitelný parametr. Poměr ρij hrany mezi uzlem i a uzlem j je definován vztahem:
α ρ ij = 1 − mα k − α
(6.5)
kde α je hodnota přiřazená preferenční cestě, α < 1.0, k je počet povolených uzlů, m je počet preferenčních cest, m = 1 nebo 0. Na základě tohoto výrazu si lze všimnout, že při první expedici zkoumání nektaru jedincem shánějícím potravu bude poměru ρij přiřazena stejná hodnota pro všechny uzly. Algoritmický základ: Kombinace algoritmu týkajícího se chování jedince shánějícího potravu a algoritmu kývavého, kmitavého tanečníka se skládá z jednoho cyklu, iterace v rámci evolučního výpočetního přístupu. Tento evoluční přístup běží pro specifický počet iterací Nmax. Když je jednou použitelné řešení nalezeno, každá včela se vrací do úlu, aby provedla kývavý, kmitavý tanec. Nejlepší řešení během iteračního procesu bude prezentováno jako konečný rozvrh na konci výpočtu. Algoritmický základ pro vytvoření rozvrhu úloh na dílně, provozu dle [Chong C. S. C., 2006]: for i = 1 to Nmax for j = 1 to l Shánění potravy – Forage. Ulož nejlepší řešení. Kývavý, kmitavý tanec - Waggle dance. end for end for 34
SYSTÉMOVÁ INTEGRACE 4/2007
Michael Hallén: "Musíme naslouchat zákazníkům, jinak nebudeme úspěšní"
Algoritmus chování včelí kolonie využitelný pro vytvoření rozvrhu úloh na dílně, provozu dle [Chong C. S. C., 2006] byl vyvinut v jazyce Java nad systémem Windows XP. Seznam, katalog vybraných, prioritních řešení je použit pro označení jedinců shánějících potravu, kteří provádějí kývavý, kmitavý tanec na tanečním patře. Trvání tance je spojeno s počtem iterací, které seznam vybraných řešení povoluje, aby v seznamu vybraných řešení zůstaly. Každé vybrané, prioritní řešení obsahuje cestu jedince shánějícího potravu, jeho Pracovní rozpětí (Makeplan), maximální počet povolených iterací, a počet iterací (i = 1 to Nmax) do okamžiku přidání řešení do prioritního seznamu, katalogu. Po každém cyklu jedinců shánějících potravu, seznam je aktualizován a jsou odstraněny vybraná, prioritní řešení, která přesahují maximální počet iterací. Postup dle [Chong C. S. C., 2006] byl též srovnáván s mravenčím algoritmem ACO a metodou Tabu Search. Výsledky dle algoritmu ACO jsou srovnatelné, metoda Tabu Search je mírně rychlejší.
7. Závěrečné úvahy a příklady použití týkající se algoritmů hmyzích kolon Příklady řešení úloh a ovládání průmyslových procesů založených na chování kolon využívajících feromonového principu jsou uvedeny v odst. 4. v první části tohoto článku, uveřejněném v předchozím čísle tohoto časopisu. Jaké jsou příklady a úvahy o použití algoritmu včelích kolon ? Použitelné řešení při optimálním rozvrhování úloh na dílně, provozu jako kompletní rozvrh operací pokrývajících řešený problém můžeme uvažovat jako cestu z úlu k potravinovému zdroji dle [Bee colony, 2007], což ilustruje obr. 7.1. Zvýšené pozornosti se v současných i dřívějších letech též těší a těšila tzv. celulární výroba (Cellular Manufacturing) jako součást tzv. „štíhlého“ výrobního systému („Lean Manufacturing“). Klíčovým problémem celulárního výrobního systému (Cellular Manufacturing System) [Duc Truong Pham, 2007] je formování výrobní buňky (cell), do buňek (cells) strojů, které se týká seskupení částí s podobnými procesními požadavky do podobných a sdružených buňek strojů. V [Duc Truong Pham, 2007] je tento problém řešen pomocí výše uvedeného (v odst. 6.) algoritmu, postupu včelích kolon. Tato optimalizační technika se ukázala vhodná při použití celulárního výrobního systému, zejména jako efektivní při řešení rozsáhlých (large-scale) problémů. V celulární výrobě pracovní stanice a vybavení jsou sdruženy, uspořádány do sekvencí, pořadí, které podporuje hladký tok materiálu a komponent skrz výrobní proces s ohledem na minimální náklady na dopravu (transport) a zpoždění (delay). Implementace tohoto “štíhlého” (Lean) systému, metody často reprezentuje první větší posun ve výrobních aktivitách a je to klíč umožňující zvýšit rychlost a produktivitu výroby, stejně tak jako redukovat kapitálové nároky. Celulární výroba vyžaduje základní paradigmatický posun od dávkové, vsádkové a kontinuelní výroby založené na velkých skladových zásobách (pro výrobní systémy) k výrobě, která “tahne” (pull) jeden kus celou výrobou, přičemž stroje, zařízení, sekvence operací jsou podél celé výroby seřazeny tak, aby výroba probíhala hladce. Dávkové, vsádkové a kontinuelní systémy zahrnují masovou výrobu využívající s výhodou rozsáhlé skladové zásoby, kde každé funkční oddělení (functional department) je navrženo tak, aby minimalizovalo cenu práce SYSTÉMOVÁ INTEGRACE 4/2007
35
Zpravodajství
okrajových jednotek přes rozsáhlé výrobní cykly výroby podobných produktů, s minimalizací potřeby změny výrobních nástrojů. Dávková, vsádková a kontinuelní výroba činí nezbytným používat rozsáhlá výrobní zařízení, rozsáhlé výrobní svazky a používat dlouhé výrobní cykly (production runs).
Nektar ( Sink )
Nektar (Sink )
O22
Nektar ( Sink )
O12
O11 O22
O12
O11
O21 O11
O11
O11 O21
O11 Úl ( Source ) O11
O21 O21
O22
O21 O11
O11
O12 O22
O12
Nektar ( Sink )
O12
Nektar ( Sink )
O22
Nektar ( Sink )
Obr. 7.1. Řešení rozvrhu operací Oij na dílně, provozu jako cesta z Úlu (Source) k potravinovému zdroji - Nektaru (Sink), dle [Bee colony, 2007]. Celulární výroba (CV) odpovídá výrobním systémům, kde zařízení a pracovní stanice jsou sdruženy pro vykonávání efektivních sekvencí, které dovolují spojitý a hladký pohyb zásob a materiálu pro výrobu produktů od startu na konec v rámci jednoho procesního toku a zároveň dochází k minimalizaci dopravního času a prostojů resp. zpoždění. CV je důležitou složkou tzv. štíhlé, hladké (Lean) výroby. V systému nastavení jednoho procesního toku (nebo jednoho výrobního toku) celulární výroby je nezbytné, aby umístění veškerého odlišného vybavení, výrobního zařízení nutilo vyrábět výrobek společně v rámci shodné výrobní oblasti. 36
SYSTÉMOVÁ INTEGRACE 4/2007
Michael Hallén: "Musíme naslouchat zákazníkům, jinak nebudeme úspěšní"
To je v kontrastu s tradičním dávkovým, vsádkovým a kontinuálním systémem nastavení výroby, kde pouze podobná zařízení jsou umístěna ve shodné oblasti. Pod dávkovým, vsádkovým a kontinuálním systémem nastavení výroby, výrobky, které se potřebují podrobit procesnímu zpracování na jistém vybavení, potřebují být transportovány do oblasti, kde vybavení, pracovní stroje, zařízení jsou umístěny. Zde výrobky (products) čekají na zpracování v dávkách. Výsledky takového systému jsou často zpoždění v transportu, dopravě a v dávkách, vsádkách (batch). V systému nastavení jednoho procesního toku (nebo jednoho výrobního toku) celulární výroby se výrobky (products) jednoduše pohybují od jednoho výrobního vybavení, zařízení k dalšímu vybavení v rámci jedné výrobní linie, jednoho výrobního toku volným způsobem (in a free-flowing manner) tak, aby se vyhnuly dopravním, transportním a dávkovým, vsádkovým (batch) zpožděním. Optimalizační algoritmus včelí kolony může být použit též k řešení problémů spojité optimalizace, trénování neuronových sítí, kombinatorické optimalizaci, optimalizaci zatížení internetových serverů, řešení problému obchodního cestujícího, optimálnímu návrhu mechanických a elektronických komponent, aj. [Bee colony, 2007]. Pracovní rozpětí (Makespan) řešení je analogií rentability, výnosnosti zdroje potravy v termínech vzdálenosti a sladkosti, lahodnosti nektaru. Odtud plyne nejkratší Pracovní rozpětí a nejvyšší rentabilita, výnosnost řešené cesty. Tato práce byla vypracována za podpory programu č. MSM 6046137306 MŠMT ČR.
Literatura [Ant colony, 2007] Ant colony optimization Wikipedia: http://en.wikipedia.org/wiki/Ant_colony_optimization, (2007). [Bee colony, 2007] Bee colony optimization Wikipedia: http://en.wikipedia.org/wiki/Bee_colony_optimization (2007). [Chong C. S. C., 2006] Chong C. S. C., Low M. Y. H., Sivakumar A. I., Gay K. L.: A BEE COLONY OPTIMIZATION ALGORITHM TO JOB SHOP SCHEDULING. Proceedings of the 2006 Winter Simulation Konference, L. F. Perrone, F. P. Wieland, J. Liu, B. G. Lawson, D. M. Nicol, and R. M. Fujimoto, eds., 2006, http://www.informs-sim.org/wsc06papers/251.pdf, (2007). [Collett P., 2003] Collett P., Graham T.S., Durier V.: Route learning by insects. Current Opinion in Neurobiology, 13(6), 718–725, 2003. [Collett T., 2004] Collett T., Collett M.: How do insects represent familiar terrain. Journal of Physiology, 98, 259–264, 2004. [Dorigo M., 2004] M. Dorigo and T. Stützle, Ant Colony Optimization. MIT Press, Cambridge, MA, 2004. [Dorigo M., 2006] Dorigo M., Birattari M., Stützle T.: The Ant Colony Optimization (Artificial Ants as a Computational Inteligence Technique). Université Libre de Bruxelles, BELGIUM, IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE, NOVEMBER 2006, pp. 29-39, http://code.ulb.ac.be/dbfiles/DorBirStu2006cim.pdf (2007).
SYSTÉMOVÁ INTEGRACE 4/2007
37
Zpravodajství
[Duc Truong Pham, 2007] Duc Truong Pham, Ashraf Afify, Ebubekir Koc: "Manufacturing cell formation using the Bees Algorithm". IPROMS 2007 Innovative Production Machines and Systems Virtual Conference, Cardiff, UK. (2007). [Dyer F., 2002] Dyer F.: When it pays to waggle. Nature, 419, 885–886, 2002. [Eyckelhof C. J., 2002] Eyckelhof C.J., Snopek M.: Ant systems for a dynamic TSP: Ants caught in a traffic jam, in Proc. ANTS 2002, ser. LNCS, M. Dorigo et al., Eds., Springer Verlag, vol. 2463, pp. 88–99, 2002. [Goldratt E. M., 1992] Goldratt E. M.: The Goal. The North River Press, Crotonon-Hudson, NY, 1992. [Lambrinos D., 2000] Lambrinos D., Möller R.,. Labhart T, Pfeifer R., Wehner R.: A mobile robot employing insect strategies for navigation. Robotics and Autonomous Systéme. 30(1-2), 39–64, 2000. [Lemmens N., 2007] Lemmens N.1, de Jong S.2, Tuyls K. 2, Nowé A.1: Bee behaviour in multi-agent systems: A bee foraging algorithm.1 CoMo, Vrije Universiteit Brussel, Belgiím, 2 MICC-IKAT, Universiteit Maastricht, Netherlands, http://www.cs.unimaas.nl/steven.dejong/publications/alamas07_lemmens.pdf, (2007). [MASCADA - WP1,WP4, 1999] MASCADA - WP1,WP4 (Espirit LTR 22 728): MASCADA - Manufacturing Systems Capable of Handling Production Changes and Disturbances, 1999, http://www.mech.kuleuven.ac.be/pma/project/mascada.html, (2007). [Michelsen A., 1992 ] Michelsen A., Andersen B., Storm J., Kirchner W., Lindauer M.: How honeybees perceive communication dances, studied by means of a mechanical model. Behavioral Ecology and Sociobiology, 30(34):143–150, 1992. [Nakrani, S., 2004] Nakrani, S. and C. Tovey: On honey bees and dynamic allocation in an internet server colony. Adaptive Behavior, 12(3-4), p. 223-240, 2004. [NP-hard, 2007] NP-hard Wikipedia: http://en.wikipedia.org/wiki/NP-hard (2007). [SWARM-BOTS, 2001] SWARM-BOTS Project, IRIDIA, Belgiím: http://iridia.ulb.ac.be/~mdoringo/swarmbotsvacamńcies.html, 2001. [Travelling salesman, 2007] Travelling salesman problem Wikipedia: http://en.wikipedia.org/wiki/Travelling_salesman_problem, (2007).
38
SYSTÉMOVÁ INTEGRACE 4/2007
