Optimalizace a adaptace parametrů simulace komplexních samoorganizujících systémů

Rok / Year: 2011

Svazek / Volume: 13

Číslo / Number: 5

Optimalizace a adaptace parametrů simulace komplexních samoorganizujících systémů Optimization and adaptation of simulation parameters of complex self-organizing systems Michal Janošek [email protected] Ostravská univerzita v Ostravě, Přírodovědecká fakulta, Katedra informatiky a počítačů

Abstrakt: Tento článek si klade za cíl seznámit čtenáře s problematikou návrhu komplexních systémů, zejména s fází simulace. Důraz je zde kladen na studium technologií uplatnitelných při modelování komplexních systémů a metodik vhodných pro návrh modelů těchto systémů. Na systém zde bude nahlíženo jako na samoorganizující se multiagentový systém s důrazem na adaptivní kontrolní mechanismus. Rovněž jsou uvedeny výsledky provedených experimentů.

Abstract: This article aims to familiarize the reader with problems of design of complex systems, especially with the phase of the simulation. Emphasis is placed on studying technologies applicable in modeling complex systems and methodologies for the design of suitable models for these systems. The system here will be regarded as self-organizing multiagent system with emphasis on adaptive control mechanism. It also shows the results of the experiments.

2011/55 – 25. 10. 2011

VOL.13, NO.5, OCTOBER 2011

Optimalizace a adaptace parametrů simulace komplexních samoorganizujících systémů Michal Janošek1 1

Ostravská univerzita v Ostravě, Přírodovědecká fakulta, Katedra informatiky a počítačů Email: [email protected]

Abstrakt – Tento článek si klade za cíl seznámit čtenáře s problematikou návrhu komplexních systémů, zejména s fází simulace. Důraz je zde kladen na studium technologií uplatnitelných při modelování komplexních systémů a metodik vhodných pro návrh modelů těchto systémů. Na systém zde bude nahlíženo jako na samoorganizující se multiagentový systém s důrazem na adaptivní kontrolní mechanismus. Rovněž jsou uvedeny výsledky provedených experimentů.

[1]. To znamená, že se na systém díváme z širšího úhlu pohledu (opak specializace). Složitost systému 𝐶𝑠𝑦𝑠 [2] se zvyšuje s množstvím jeho komponent #𝐸� , interakcí #𝐼 ̅ mezi komponenty, složitostí samotných elementů 𝐶𝑒 a složitostí interakcí 𝐶𝑖 (1).

1 Úvod Mezi jednu z časově nejnáročnějších fází návrhu komplexního systému patří simulace, kdy je třeba otestovat model systému s množstvím parametrů vlastní simulace, kontrolního mechanismu a jednotlivých komponent modelu našeho systému. Klíčové pro tuto fázi je testování různých scénářů a strategií kontrolních mechanismů (mediátorů). Prozkoumáme-li problematiku testování parametrů simulace našeho modelu z hlediska aktuálních metodik pro návrh samoorganizujících systémů, zjistíme, že jen málo těchto metodik se věnuje podrobně této oblasti. Tento článek je součástí dlouhodobého výzkumu prováděného na Ostravské univerzitě v Ostravě Chyba! Nenalezen zdroj odkazů.[27][28][29], který se zabývá vývojem metody vycházejících z algoritmů umělé inteligence, jež napomůže adaptaci parametrů simulace za účelem urychlení a zefektivní simulace vybraného komplexního (samoorganizujícího) systému.

2 Komplexní systémy Na každý reálný systém je možno nahlížet jako na komplexní fenomén. Je složen z množství částí, které spolu reagují takovým způsobem, že je nesnadné je separovat. Navíc, chování systému je obtížné odvodit od chování jeho částí a toto odvození je tím obtížnější, čím více částí, nebo čím více interakcí se v systému nachází [2]. Vlastnosti systému mohou být rovněž výsledkem interakcí mezi komponentami systému, které tyto vlastnosti nemají. Tento jev nazýváme emergencí [17]. Příkladem může být např. diamant; má vlastnosti jako tvar, lesk, tvrdost, barvu a další. Tyto vlastnosti, základní komponenty diamantu – atomy uhlíku, nemají. Čím složitější je systém z hlediska komponent a interakcí, tím složitější je jej dekomponovat na jednotlivé části. Navíc, v případě, že chování a vlastnosti systému emergují z interakcí jeho částí, jeví se jako vhodnější použít integrativní přístup namísto redukčního

#𝐸� #𝐼 ̅ 𝐶𝑠𝑦𝑠 ~ ∑#𝐸� 𝐶 ⎨ 𝑗=0 𝑒𝑗 ⎪∑#𝐼 ̅ 𝐶 ⎩ 𝑘=0 𝑖𝑘 ⎧ ⎪

(1)

Nelze jednoduše a bez kontextu rozhodnout, kdy je systém ještě jednoduchý a kdy již komplexní. Například celulární automaty jsou poměrně komplexní systémy svou strukturou, ale s celkem jednoduchými interakcemi. Na druhou stranu systém pohybu kyvadla je strukturou poměrně jednoduchý systém, ale s poměrně složitými interakcemi. V případě statického systému je jednou z vhodných možností využít optimalizace parametrů simulace. Optimalizace nám dává ty nejlepší výsledky pro danou konfiguraci. Např. při návrhu křídla letadla nabízí optimalizace dobré výsledky, jelikož aerodynamické nároky letadla jsou konstantní (pro danou rychlost, hmotnost, atd.). Nicméně, optimalizační techniky mají tendenci dávat zastaralá řešení v případě, že problém se změní dřív, než stačíme provést samotnou optimalizaci [4]. Naproti tomu dynamické komplexní systémy se typicky sestávají z množství propojených pozitivních a negativních zpětnovazebních smyček, kde změna jakékoliv jeho části vyvolává kaskádovou změnu v množství propojených komponent, což se v konečném důsledku projeví negativní nebo pozitivní vazbou v původní komponentě. V případě proměnného času mezi těmito efekty je nemožné provádět jakoukoliv optimalizaci takového systému. Jelikož nevíme, co bude ovlivněno jako první, tím pádem ani nevíme, zda efekt bude potlačen či zesílen. Jako příklad můžeme uvést prostředí burzy. Na burze jsou akcie prodávány či nakupovány v závislosti na jejich ceně. Cena se odvíjí od toho, jak hodně se nakupuje nebo prodává. Tato vnitřní zpětnovazební smyčka má jak pozitivní, tak negativní aspekt. Zákon nabídky a poptávky implikuje negativní zpětnou vazbu, jelikož zvýšení ceny běžně redukuje poptávku, která po určité době, opět sníží cenu. Paralelní mechanismus spekulací přesto způsobuje pozitivní zpětnou vazbu, jelikož rostoucí cena vytváří u nakupujících předpoklad, že v růstu bude pokračovat, čímž je motivuje k dalšímu nakupování.

55 – 1

2011/55 – 25. 10. 2011

VOL.13, NO.5, OCTOBER 2011

Interakce mezi těmito dvěma nelineárními efekty jsou běžné na trzích a produkují chaotické chování ve vývoji ceny [1]. Nikdy tedy nebudeme schopni plně kontrolovat nebo předvídat chování takovýchto komplexních chaotických systémů. Vždy se vyskytnou chyby, překvapení a nečekané problémy. Jaké je tedy jedno z možných řešení? Můžeme se vyrovnat s nečekanými událostmi adaptováním našich akcí vzhledem ke vzniklé situaci [8]. Abychom se adaptovali na změnu (očekávanou nebo neočekávanou), je dostatečné kompenzovat vzniklou odchylku aktuální situací od požadovaného směru. V případě, že reakce na změnu přijde dostatečně rychle (předtím než problém bude mít možnost narůst), tato regulace (feedback-based) může být velmi efektivní. V případě, že máme prostředky k potlačení vzniklé odchylky chování systému od požadovaného směru, tak již nezáleží, jak moc je samotný systém komplikovaný (z pohledu faktorů a interakcí) [6]. Např. nezáleží, jaké kombinace komplikovaných sociálních, politických nebo technologických změn způsobí změnu chování ekonomiky. Centrální banka může regulovat tempo růstu zvyšováním nebo snižováním úrokových sazeb. Abychom byli schopni reagovat rychle a pružně, je dobré mít alespoň nějaká očekávání toho, co se může stát a jaké reakce v řízení systému budou odpovídající. Očekávání zde reprezentují subjektivní pravděpodobnosti, které se učíme ze zkušeností. Potřebujeme tedy mít znalost o systému. Čím častěji se okolnost B objeví po okolnosti A (anebo čím účinnější je akce B při řešení problému A), tím silnější bude asociace A→B. Střetneme-li se v budoucnu s A (nebo něčemu podobnému), budeme připraveni a pravděpodobně budeme i adekvátně reagovat. Jednoduchým uspořádáním možností dle pravděpodobností, se kterou mohou nastat, tak nesmírně snižujeme složitost při rozhodování [7].

3 Multiagentové systémy Multiagentový systém (MAS) je tvořen minimálně dvěma agenty, nacházejícími se v daném prostředí. Agenty jsou v multiagentovém systému koordinovány a mohou spolu komunikovat, případně kooperovat na různých úrovních. V zásadě rozlišujeme čtyři typy agentů, a to reaktivní, deliberativní, sociální a hybridní [3]. Reaktivní agent má nejjednodušší vnitřní architekturu [13]. Akce agenta jsou pouze reakcí na podněty z prostředí. Deliberativní agent si uchovává reprezentaci prostředí a vnitřních stavů a je schopen vytvářet plány pro dosahování svých cílů. Sociální agent dokáže s ostatními sociálními agenty komunikovat ve vyšším komunikačním jazyce (jako například v jazyce KQML 1) [18]. Hybridní agent je potom kombinací agentů předchozích typů. Anglickému výrazu agents přísluší dva české výrazy, a to agenty, případně agenti. Výraz agenty je používán pro neživotné entity, výraz agenti pro entity životné. Obojí je správně a záleží na kontextu. Agenty se dají využít pro množství různých úloh. Zajímavou prací je rozpoznávání otisků prstů pomocí reaktivních agentů a neuronových sítí [9]. Zde se autoři snaží řešit problém rozpoznávání otisků prstů jako navigaci reaktivních agentů v komplexním prostředí. Agent se pohybuje 1

Knowledge Query and Manipulation Language – [Finin, Labrou, 1998]

v prostředí, které je tvořeno samotným otiskem a snaží se dosáhnout svého předem daného cíle vyhodnocením lokálních informací. Modeluje se zde jistá variace plánování trasy. Dalším výzkumem je využití multiagentových systémů v průmyslu. V. Mařík [15] navrhl multiagentový systém pro nasazení v průmyslových aplikacích. Multiagentový systém se nachází v kooperativním módu, kdy neexistuje žádný centrální řídící prvek. Tento přístup činí systém robustnější a je možné pracovat v reálném čase. Multiagentový systém je nasazen na všech úrovních průmyslové sféry a to od nejnižší fyzické úrovně až po podnikové plánování. Na všech úrovních výrobního systému pracuje komunita autonomních inteligentních agentů se svými cíli, kteří mezi sebou spolupracují a koordinují svá rozhodování k plnění globálního cíle. Mezi další využití MAS je jejich použití jako součást multiagentového obchodní systému obchodujícího na burze [11]. Cíl je kladen na jejich autonomnost a schopnost adaptace v souvislosti s interakcí s prostředím. V článku [16] bylo analyzováno, jak se agenty hodí pro tuto operaci. Byla implementována množina autonomních obchodních agentů s využitím architektury, která integruje klasifikační moduly a také moduly fungující na základě pravidel expertních systémů. Výsledky simulace však nesplnily očekávání. Agenty prováděly velké množství obchodů a tím se staly neefektivní z hlediska vynaložených prostředků představující komise za jednotlivý obchod.

4 Samoorganizace Je vcelku obtížné definovat termín samoorganizace systému. Vše záleží na typu systému a také na úhlu pohledu pozorovatele. Požadovaný stav systému můžeme nazvat jako organizovaný, bude-li se dynamika systému vyvíjet směrem k organizovanému stavu systému. Stejně jako pojem inteligence či život [19], nelze proto ani pojem samoorganizace jednoduše definovat. Systém tedy můžeme popsat jako samoorganizující v případě, že jeho komponenty spolu interagují tak, aby dosáhly globální požadované funkce či chování [5]. Základní otázka by tedy neměla být, zda je systém samoorganizující, ale kdy je vhodné jej popsat jako samoorganizující? Samoorganizující systém je takový, jehož komponenty jsou navrženy tak, aby dynamicky a autonomně řešily problém nebo vykonávaly žádanou funkci na systémové úrovni [1]. Např. výrobní linka s roboty může být popsána jako samoogranizující systém, jelikož každá komponenta tohoto systému může měnit své chování na základě aktuálního stavu. Teorie regulace a řízení je zaměřena především na metody automatického řízení, ale zahrnuje i metody adaptivního a fuzzy řízení a nemusí se jednat jen o technické, ale i ekonomické aplikace. Obecně lze prostřednictvím řízení nebo regulace usměrnit chování systému požadovaným směrem. Základní otázkou je, na základě čeho budeme systém řídit. Abychom dokázali systém řídit, potřebujeme konkrétní systémová data, podle kterých bychom se mohli rozhodnout. Samozřejmě nemusí jít pouze o data reprezentující chování systému, ale mohou obsahovat také údaje o prostředí, ve kterém se systém nachází a které jej ovlivňují. Rozdílné přístupy v řízení systému závisí na způsobu, jak tato systémová data zpracujeme a dále využijeme[2]. K řízení systému můžeme přistupovat několika způsoby. Jednou z možností je přímé

55 – 2

2011/55 – 25. 10. 2011

VOL.13, NO.5, OCTOBER 2011

řízení, další je řízení systému na základě predikce, případně adaptování odchylky systému od požadovaného směru a mnohé další. Přímým řízením je myšlena situace, kdy systémová data použijeme k přímé regulaci bez toho, abychom prováděli nějakou analýzu naměřených hodnot. Pokud se jedná o model jednoduchého lineárního systému, kdy výstupy systému jsou úměrné jeho vstupům a platí-li princip superpozice, je možno na základě analýzy průběhu vstupních dat provádět průběžnou predikci, jež obvykle bývá velmi přesná. Gershenson [1] navrhnul několik samoorganizujících systémů (samoorganizované dopravní semafory, samoorganizovaný úřad, samoorganizované přístroje), kde je každá část systému modelována jako agent plnící své cíle na nejnižší úrovni a poté na systémové úrovni nastavující takový způsob kooperace a komunikace agentů, aby jako celek systém směřoval ke svému cíli, pokud možno s co nejmenším „třením“ mezi jeho jednotlivými složkami. Další prací je využití samoorganizačních map jako nástroje k rozpoznání známých formací v tzv. svíčkových grafech na burze. Tyto mapy byly použity k vizualizaci vzorů a také jako vstupy pro komplexní rozhodovací obchodní systém. Rovněž byla představena profitabilní verze tohoto systému [14].

5 Model a vzory Systém charakterizujeme nejčastěji tak, že si vytvoříme jeho model. Tento model odráží náš vlastní pohled, naše znalosti o systému a také účel, pro který model vytváříme. Gershenson [1] zavádí dva typy modelů, absolutní a relativní. Absolutní model jevu či věci reprezentuje takový objekt, který je nezávislý na pozorovateli. Na druhou stranu relativní model odkazuje na vlastnosti jevu nebo věci tak, jak jsou vnímány pozorovatelem v určitém kontextu. Jelikož pozorovatel nemůže mít kompletní informace, může o své realitě hovořit jen pomocí relativních modelů. Relativní model je omezený, zatímco absolutní model může mít nekonečně vlastností. Neexistuje tedy nejlepší model, pouze různé modely jsou vhodné pro různé kontexty nebo cíle. Jakýkoliv systém pak může být modelován jako skupina agentů, kteří se snaží uspokojit své cíle. Pokud máme vytvořen relativní model systému, můžeme v něm pozorovat jeho určité charakteristiky, a to jak v jeho popisu, tak i v jeho chování s ohledem na prostředí, ve kterém se systém nachází. Některé z těchto důležitých charakteristik můžeme označit za vzory. Vzory tedy reprezentují charakteristické formy chování relativního modelu systému. [12]

6 Metodiky pro návrh komplexních systémů Zmiňme několik metodik věnujících se návrhu komplexních systémů. Při konstrukci systémů s adaptivním řízením lze s úspěchem použít výše zmiňované multiagentové systémy. Jednotlivé agenty v systému definují polohu jednotlivých komponent. Definují tedy konkrétní komponentu systému, kterou můžeme monitorovat a případně ji řídit. V případě, že agenty vybavíme neuronovou sítí pro rozpoznávání vzorů, dostaneme velmi silný nástroj. Samozřejmě zde můžeme uvažovat několik vrstev multiagentového systému.

Gershenson [1] navrhnul tzv. obecnou metodiku, The General Methodology (GM) (Obr. 1), pro návrh a správu komplexních systémů. Autor sám ovšem zmiňuje, že se nejedná o „ready-make“ řešení. Poskytuje spíše konceptuální framework, pomocí něhož může nabídnout postupy řešení. Metodika počítá s měnícími se požadavky tak, aby se systém dokázal adaptivně přizpůsobovat.

Obrázek 1. Fáze obecné metodiky [5] Agent je zde entita, která provádí akce ve svém prostředí. Na každou komponentu systému i na každý systém můžeme nahlížet jako na agenty se svými cíli a chováním směřujícím k plnění systémových cílů. Chování agenta může ovlivnit (pozitivně, negativně, neutrálně) plnění cílů ostatních agentů. Plnění cílů agenta můžeme označit jako jeho satisfakci 𝜎 ∈ [0, 1]. Vztáhneme-li satisfakci k vyšší úrovni, tak satisfakce systému 𝜎𝑠𝑦𝑠 (2) může být reprezentována funkcí 𝑓 ∶ ℝ ⟶ [0, 1], jež je satisfakcí jednotlivých komponent. 𝜎𝑠𝑦𝑠 = 𝑓 (𝜎1 , 𝜎2 , … , 𝜎𝑛 , 𝑤0 , 𝑤1 , 𝑤2 , … , 𝑤𝑛 ) (2)

𝑤0 zde označuje bias, další váhy 𝑤𝑖 určují důležitost danou každému 𝜎𝑖 . Komponenty, které snižují 𝜎𝑠𝑦𝑠 a zároveň zvyšují své 𝜎𝑖 , bychom neměli považovat za část systému. Samozřejmě nelze obecně stanovit, zda ke zvýšení satisfakce systému stačí zvýšit satisfakci jeho komponent. Některé komponenty totiž mohou využívat ostatních komponent při plnění cílů. Pro maximalizaci 𝜎𝑠𝑦𝑠 bychom měli snížit tření mezi jednotlivými komponentami na minimum a tím zvýšit jejich synergii. Je tedy potřeba usměrnit chování jednotlivých komponent. Tuto funkci zastává tzv. mediátor. Mediátor usměrňuje chování komponent systému, minimalizuje jejich konflikty, interference a tření a maximalizuje kooperaci a synergii na úrovni systému. Metodika se skládá z několika kroků (reprezentace, modelování, simulace, aplikace, evaluace). Reprezentací je myšlen návrh specifikací komponent systému, které budou reprezentovat stěžejní komponenty, spolu se vzájemnými interakcemi. Zadáváme základní specifikace systému, omezení a požadavky. Dále je nutné ustanovit slovník a úroveň abstrakce, jimiž budeme systém popisovat. Např. v biologii může být v určitých situacích vhodné popsat buňku jako základní element – agenta, v jiných situacích můžeme buňku popsat jako systém s agenty reprezentující jednotlivé komponenty buňky. Modelování vychází z reprezentace a mělo by specifikovat kontrolní mechanismy, které zajistí, že systém funguje tak, jak je od něj požadováno. Používá se zde tzv. adaptivní kontrolní

55 – 3

2011/55 – 25. 10. 2011

VOL.13, NO.5, OCTOBER 2011

mechanismus. Využívají se jednak agenty, které tvoří běžné komponenty systému a pracují na svých cílech a také tzv. agenty mediátory, které usměrňují chování ostatních agentů tak, aby mezi nimi minimalizovaly vzájemná tření a zvyšovaly jejich kooperaci a celkovou synergii systému. V této fázi je nutné vzít v úvahu také některé kompromisy jako složitost komponent vs. složitost interakcí, kvalitu vs. kvantitu, úspornost vs. redundanci, homogenitu vs. heterogenitu. Ve fázi simulace je stěžejní implementovat navržený model a otestovat různé scénáře a strategie mediátorů a další parametry systému. Postupuje se od testování základních konceptů, tj. „hrubého“ modelu a v případě očekávaného fungování na základní úrovni se postupně implementují další detaily. Neoddělitelnou částí je také porovnávání navrhovaného řešení s tradičními přístupy. Záleží na uživateli, aby rozhodl, které parametry bude optimalizovat a které adaptovat. Fáze aplikace slouží k vybudování reálného systému na základě simulací. Zde je důležité vzít v potaz také proveditelnost aplikace z hlediska konstrukčního i ekonomického. Závěrečnou fází je evaluace, kdy je nutné porovnat výkon systému s výkonem případných předchozích verzí systému a také je důležitá zpětná vazba s provozovatelem reálného systému. Existují i další metodiky postavené na samoorganizaci. Zmiňme alespoň některé z nich. Adelfe [20] (viz. Obr. 2) je metodika zaměřená na multiagentové samoorganizující systémy s decentralizovaným řízením využívajícím emergenci. Pracuje s upravenou verzí jazyka UML (Agent-UML) a je založená na teorii AMAS 2, ve které hraje hlavní roli kooperace. V kooperačním módu se agenty snaží předpokládat problémy, které mohou nastat, vyhledávat případná selhání ve vzájemné spolupráci a tyto skutečnosti napravovat. Kooperativní agent postavený na AMAS teorii je autonomní a není si vědom globální funkce nebo cíle systému. Metodika je rozdělena do šesti základních fází: předběžné požadavky, finální požadavky, analýza, návrh, implementace a test. Každá fáze se potom skládá z množství aktivit.

Obrázek 3. Metodika CUP [21] Během fáze analýzy požadavků je problém rozdělen na funkční a ne-funkční požadavky. Je využito případových studií, seznamu vlastností a doménového modelu. Rovněž jsou identifikovány požadavky na globální úrovni. Fáze návrhu se skládá z návrhu architektury systému a detailního návrhu komponent. Během fáze implementace je realizován konkrétní návrh s použitím specifického jazyka. Ve fázích testování a ověření je získaná agentově založená simulace verifikována. Metodika MetaSelf [22] (viz. Obr. 4) nahlíží na samoorganizující systém jako na kolekci volně vázaných komponent. Pomocí metadat popisuje funkční i ne-funkční charakteristiky a metadata vztahující se k prostředí. Chování systému je předepsáno tzv. politikou, která popisuje odezvu komponent systému na zjištěný stav a změny v metadatech. Při běhu systému využívají jak komponenty tak „run-time“ infrastruktura tato metadata k podpoře rozhodování a své adaptaci v souladu s politikou. Metaself popisuje jak samotnou systémovou architekturu, tak i proces vývoje. Politiky definují systémové cíle, omezení prostředí a chování komponent. Metodika se skládá ze tří fází. Fáze požadavků a analýzy identifikuje funkcionalitu systému spolu s tzv. self-požadavky specifikujícími kde a kdy je samoorganizace potřebná. Fáze návrhu popisuje výběr vzorů, rozhodovacích mechanismů a návrhu aplikačního systému. Výsledkem implementační fáze je „run-time“ infrastruktura.

Obrázek 4. Metodika MetaSelf [22]

Obrázek 2. Metodika Adelfe [20] The Customized Unified Process (CUP) [21] (viz. Obr. 3) je další metodikou a tvoří ji iterativní proces, který opět využívá jak samoorganizaci, tak emergenci v kontextu samoorganizovaného chování v průmyslových systémech. Je založena na UP 3. Skládá se ze čtyř hlavních kroků: analýzy požadavků, návrhu, implementace a testování.

A Simulation Driven Approach (SDA) [23] (viz. Obr. 5) není kompletní metodikou, ale spíše způsobem jak integrovat své metody do stávajících metodik. K popisu prostředí používá agenty a artefakty. Agenty jsou autonomní proaktivní entity se svými vnitřními cíli. Artefakty jsou pasivní reaktivní entity poskytující služby a funkcionality agentům. Existují ještě speciální agenty prostředí, jež jsou zodpovědné za správu artefaktů. SDA je zařazeno mezi fáze analýzy a návrhu, tzv. „Early design“ fáze. Předpokládá, že už známe požadavky systému a byla provedena jeho analýza. SDA se skládá ze tří fází. Fáze modelování slouží k formulaci strategií. Poskytuje charakteristiku uživatelských agentů, artefaktů a agentů prostředí. Ve fázi simulace jsou odzkoušeny vytvořené specifikace, a zkoumá se, zda vyhovují navrhovanému řešení. Ve fázi ladění potom dochází k ladění modelu a jeho parametrů.

2 Adaptive Multi-Agent System theory [Capera, Georg, Gleizes, Glize, 2003] 3 Unified Process [Jacobson, Booch, Rumbaugh, 1999]

55 – 4

2011/55 – 25. 10. 2011

VOL.13, NO.5, OCTOBER 2011

Analysis phase

Design phase

Early design phase

1-Modelling

2-Simulation

3-Tuning

Obrázek 5. SDA [23]

7 Experimenty s parametry simulace V předchozí kapitole jsme si představili pět metodik pro návrh komplexních systémů. Žádná z těchto metodik ovšem nedisponuje návodem pro nastavení parametrů simulace. Pro ověření, jak hodně může jen malá změna jednoho či dvou parametrů simulace ovlivnit celkové výsledky simulace byl proveden následující experiment. Pro experimenty s parametry simulace byla zvolena simulace Self-Organizing Traffic Lights [25] od Carlose Gershensona. Simulace je naprogramována v prostředí NetLogo [10] a je dostupná na výše uvedené adrese. Simulace umožňuje zkoumat, za jak dlouho (v počtu kroků) systém přejde do samoorganizovaného stavu. Stanovme tedy, že systém bude v samoorganizovém stavu, bude-li rychlost vozidel (Average Speed of Cars) maximální možná. Byly vybrány dva parametry keep-platoon a cut-platoon. Parametr keep-platoon označuje vzdálenost, na kterou jsou vozidla vnímána semaforem. Parametr cut-platoon označuje minimální velikost skupiny vozidel schopných projet křižovatkou. Na Obr. 6. můžeme vidět průběh simulace s nastavením parametrů tak, jak je určil sám autor. Systém přejde do samoorganizovaného stavu přibližně po 1500 krocích. Byly provedeny 4 simulace se stejným nastavením parametrů a vybrán byl nejlepší (nejkratší) výsledek.

Obrázek 7. Keep-platoon=4, Cut-platoon=2 Na Obr. 8. vidíme výsledky simulace, v níž byla hodnota parametru keep-platoon zvýšena o hodnotu 2, tzn. keepplatoon = 7. Systém přejde do samoorganizovaného stavu přibližně po 4000 krocích. Byly provedeny 4 simulace se stejným nastavením parametrů a vybrán byl nejlepší (nejpříznivější) výsledek.

Obrázek 8. Keep-platoon=7

8 Závěr

Obrázek 6. Výchozí simulace Na Obr. 7. vidíme výsledky simulace, v níž byla hodnota parametrů keep-platoon a cut-platoon snížena o hodnotu 1, tzn. keep-platoon = 4 a cut-platoon = 2. Systém přejde do samoorganizovaného stavu přibližně po 9600 krocích. Byly provedeny 4 simulace se stejným nastavením parametrů a vybrán byl nejlepší (nejpříznivější) výsledek.

Modelování systémů jako samoorganizujících je výhodné v případě dynamických komplexních systémů. Hlavní výhoda samoorganizujících systémů spočívá v možnosti adaptace. Samoorganizující systém je schopen hledat neustále nová řešení a má dostatečně velkou robustnost. Pro modelování těchto systémů je vhodné použít architekturu MAS. V rámci článku bylo stručně představeno několik metodik pro modelování komplexních systémů. Existují také publikace zabývající se jejich srovnáním [24] (viz. Tab. 1.). Adelfe je jedinou metodikou soustřeďující se na specifické samoorganizační charakteristiky. Navíc vynucuje užití kooperace mezi agenty, což může být výhodou pro jisté systémy, ale určitě ne pro všechny. Zajímavou inovací CUP metodiky je „information flow“ diagram (viz. Obr. 3.), jež usnadňuje pochopení způsobu, jak systém pracuje a jak jsou informace vyměňovány mezi agenty. Funkčnost metodiky MetaSelf spočívá ve volně vázaných komponentách systému, metadatech a politice. Není ale nijak zpracována situace konfliktních politik. The General Methodology nabízí vcelku volnou metodiku pro stavbu komplexních systémů, avšak nerozebírá detailně fázi simulace. Navíc nejsou zmíněna žádná doporučení pro tvorbu slovníku ve fázi reprezentace systému. Nakonec metodika SDA, která

55 – 5

2011/55 – 25. 10. 2011

VOL.13, NO.5, OCTOBER 2011

není ani metodikou, jako spíše části metodiky, je navržena za účelem integrace do ostatních metodik.

[7]

Heylighen, F.: Fitness as default: the evolutionary basis for cognitive complexity reduction. In Cybernetics and Systems ’94, R. Trappl, (Ed.), p. 1595–1602. Singapore: World Science, 1994. ISBN: 9789810217617.

[8]

Heylighen, F.: The science of self-organization and adaptivity. In The Encyclopedia of Life Support Systems, L. D. Kiel, (Ed.). EOLSS Publishers, Oxford. [cit. 2011-05-01], URL http://pcp.vub.ac.be/Papers/EOLSSSelf-Organiz.pdf, 2003.

[9]

Montesanto, Anna and collective. Analysis of fingerprints through reactive agent, Systemics of Emergence, 2006, s. 93-104. ISBN: 978-0-387-28899-4.

Tabulka 1. Srovnání metodik pro návrh samoorganizujících systémů Metodika Adelfe

Požadavky

Návrh

Model

x

x

x

CUP x

GM x

Vyhodnocení x

x

MetaSelf

SDA

Simulace

x

x

x

x

x

x

x

x

Ačkoliv studované metodiky pro návrh komplexních systémů pokrývají většinu těchto fází počínaje požadavky na systém a konče jeho evaluací, většina z nich však dostatečně nepokrývá fáze simulace a vyhodnocení. Zejména fáze simulace je v režii uživatele, kdy uživatel ručně testuje různé scénáře a nastavení jednotlivých parametrů simulace tak, aby co nejlépe odpovídaly modelované realitě a požadované funkci systému. Na provedených experimentech můžeme vidět, že stačí jen malá změna parametrů simulace od původního nastavení k výraznému ovlivnění délky simulace a to až několikanásobně. Zde je prostor pro návrh metody umožňující detailněji popsat a urychlit simulační fázi a doporučit nastavení parametrů systému, což by mělo být jádrem naší další práce.

9 Literatura [1]

[2]

[3]

Gershenson, C.: Design and Control of Self-organizing Systems. Mexico: CopIt ArXives, 2007. ISBN: 978-09831172-3-0. Gershenson, C.: Complex philosophy. In Proceedings of the 1st Biennial Seminar on Philosophical, Methodological & Epistemological Implications of Complexity Theory. La Habana, Cuba. [cit. 2011-05-01], URL http://uk.arxiv.org/abs/nlin/0109001v3, 2002. Kubík, Aleš, Inteligentní agenty. 1. vyd. Brno: Computer Press, 2004. 280 s. ISBN: 80-251-0323-4.

[4]

Gershenson, C.: Self-organizing urban transportation systems. [cit. 2011-05-01], URL http://arxiv.org/abs/0912.1588, 2009.

[5]

Gershenson, C.: A general methodology for designing self-organizing systems. Tech. Rep. 2005-05, ECCO. [cit. 2011-05-01], URL http://uk.arxiv.org/abs/nlin/0505009v3, 2006.

[6]

Kelly, K.: Out of Control. New York: Basic Books, 1995. ISBN: 978-0201483406.

[10] NetLogo [online]. Wilensky, U. NetLogo Home Page, [cit. 2011-02-12]. Dostupný z WWW: http://ccl.northwestern.edu/netlogo/. [11] Barbosa, R.P. and Belo O.: Autonomous trading agents. Lecture Notes in Computer Science, Volume 5077/2008, 389-403. Berlin: Springer, 2008. DOI: 10.1007/978-3540-70720-2_30. [12] Pattern Recognition Ability of a Multi-Agent Model of the Immune System. Canada: ICSC Academic Press, 2001. ISBN: 3-906454-25-8. [13] Nolfi, S.: Power and the Limits of Reactive Agents. Neurocomputing, Vol: 42, 2002, Pages: 119-145, ISSN: 09252312. [14] Ciskowski, P. and Zaton, M.: Neural Pattern Recognition with Self-organizing Maps for Efficient Processing of Forex Market Data Streams. Berlin: Springer, 2010. ISBN: 978-3-642-13207-0. [15] Mařík, V. and McFarlane, D.: Industrial Adoption of Agent-Based Technologies. Intelligent Systems, IEEE, 2005, p. 27-35. ISSN: 1541-1672. [16] Barbosa, R.P. and Belo O.: Multi-Agent Forex Trading System. Studies in Computational Intelligence, Springer 2010, Volume 289/2010, 91-118, DOI: 10.1007/978-3642-13526-2_5. [17] Chung JR, Choe YS: Emergence of Memory-like Behavior in Reactive Agents Using External Markers. IEEE International Conference on, pp. 404-408, 2009 21st IEEE International Conference on Tools with Artificial Intelligence, 2009. ISBN: 978-0-7695-3920-1. [18] Mirolli, M. and Nolfi, S.: Evolving Communication in Embodied Agents: Theory, Methods, and Evaluation. In Evolution of Communication and Language in Embodied Agents, pages 105--121. Springer Verlag, 2010.

55 – 6

2011/55 – 25. 10. 2011

VOL.13, NO.5, OCTOBER 2011

[19] Krakauer, D. C. And Zanotto, P. M. A. (2006). Viral individuality and limitations of the life concept. In Protocells: Bridging Nonliving and Living Matter, S. Rasmussen., M. A. Bedau, L. Chen, D. Deamer, D. C. Krakauer, N. Packard, and D. P. Stadler, (Eds.). MIT Press.

[29] Janošek, M.: Systémy Simatic a jejich využití ve výzkumu. Studentská vědecká konference 2010. Ostrava: Ostravská univerzita, 2010, s. 177-180. ISBN 978-80-7368719-9

[20] C. Bernon, V. Camps, M.-P. Gleizes, and G. Picard. Engineering adaptive multi-agent systems: The adelfe methodology. In B. Henderson-Sellers and P. Giorgini, editors, Agent-oriented Methodologies,, pages 172–202. Idea Group Pub., Hershey, PA, USA, 2005. [21] T. De Wolf. Analysing and engineering self-organising emergent applications. PhD thesis, Department of Computer Science, Katholieke Universiteit Leuven, Belgium, 2007. [22] G. Di Marzo Serugendo, J. Fitzgerald, A. Romanovsky, and N. Guelfi. MetaSelf - A framework for designing and controlling self-adaptive and self-organising systems. Technical report, School of Computer Science and Information Systems, Birkbeck College, London, UK, 2008. [23] L. Gardelli, M. Viroli, M. Casadei, and A. Omicini. Designing self-organising environments with agents and artifacts: A simulation-driven approach. Int. Journal of Agent-Oriented Software Engineering, 2(2):171–195, 2008. [24] Puviani, M., Di Marzo Serugendo, G., Frei, R. and Cabri, G.: Methodologies for self-organising systems: a SPEM approach. TR BBKCS-09-05, School of Computer Science and Information Systems, Birbeck College, London, UK, 2009. [25] Self-Organizing Traffic Lights [online]. Gershenson, C. SOTL, [cit. 2011-08-17]. Dostupný z WWW: http://turing.iimas.unam.mx/~cgg/sos/SOTL/SOTL.html. [26] Janošek, M., Kocian, V., Kotyrba, M., Volná E.: Pattern recognition and system adaptation. 10th International conference Aplimat 2011. Bratislava: Slovak Univerzity of Technology Bratislava, 2011, s. 1217-1226. ISBN 978-80-89313-51-8 [27] Janošek, M., Volná E.: Adaptace systému na základě charakteristických vzorů. Ve Kelemen, J., Kvasnička, V. (eds.): Kognice a umělý život XI. Opava: Slezská univerzita v Opavě, 2011. s. 87-92. ISBN 978-80-7248-6441 [28] Janošek, M. Simulace umělého života. Elektrorevue. 2010, roč. 2010, č. 116, s. 1-5. ISSN 1213-1539.

55 – 7