Statistikk og Simulering

Prosjekt 2

Teori: agentbasert modellering

5.2. Teori: agentbasert modellering

Agentar er eit konsept både innanfor modellering og innanfor programvarearkitektur. Agentbaserte modellar kan implementerast vha. programvareagentar, men òg på andre måtar. Programvareagentar kan likeeins brukast til meir enn berre modellering og simulering.

Teorigrunnlaget som me presiserer her er pensum. Det vil nok gje mest meining om ein ser det i samanheng med labprosjektet, men i år er det forventa at ein kan gjera presist greie for agentbasert modellering og samanlikna med alternative modelleringsformar.

Videoane er gamle. Dei kan vera nyttige, men er ikkje direkte tilpassa framstillinga i år.

5.2.1. Ulike tilnærmingar til modellering

Lat oss ta rovdyr/byttedyr-problemet som døme. I eit område lever der rev og kanin. Båe artane formerer seg og reven et kanin. Korleis kan me modellera og simulera utviklinga i populasjonen? Simuleringa kan brukast til å vurdera sannsynet for at ein eller båe artane døyr ut.

Les: Shiflet og Shiflet s. 224ff

Foilar: PDF

Alt. 1. Differentiallikningar Dersom me berre er interessert i populasjonstala, og ikkje geografien der artane lever, kan me laga ein enkel modell med differentiallikningar. Lotka-Volterra-modellen er den mest kjende.

Lat x og y vera talet på hhv. kanin og rev. Observasjonane som ligg til grunn er at

Dette gjev likningane

dx dt = x(α βy) (14)  dy dt = y(γ δx), (15) 

der α, β, γ og δ er positive konstantar.

Legg merke til at denne modellen er deterministisk. Ingenting er tilfeldig. Han modellerer berre på makronivået, med heile populasjonstal. Individet er uinteressant.

Ein kan simulera Lotka-Voltera-modellen ved iterera over tida t. For kvart tidssteg kan ein estimera ut populasjonane for neste steg ved hjelp av forrige verdi av x og y saman med x og y.

Alt. 2. Celleautomaton Ein meir detaljert modell krev at me modellerer landskapet der reven og kaninane bur. Det er vanleg å bruka eit rutenett, slik at dyra alltid flyttar seg i diskrete steg. Det er enklare enn ein kontinuerleg modell. Rutene kallar me gjerne for celler.

Ein automaton er ei tilstandsmaskin. Ein celleautomaton er eit rutenett der kvar celle har eit endeleg tal moglege tilstandar. Til dømes kan tilstandane vera rev, kanin eller tom.

Modellen må ha ein starttilstand, dvs. kvar celle er anten rev, kanin eller tom når modellen startar. Dynamikken i systemet vert avgjort av ein serie med reglar, t.d. 

1.
Rev med kanin i nabocelle
  • reven flyttar til nabocella og kaninen forsvinn
2.
Kanin med ein tom nabo
  • kaninen flyttar til den tomme cella (gjerne tilfeldig)
3.
Kanin når aldersgrensa
  • tom celle (kaninen døyr av alderdom)
4.
Tom celle med to naboar med kanin.
  • kanin (fødsel)

For å køyra modellen itererer ein over tida t. For kvart tidsteg vert kvar regel køyrd etter tur, og regelen vert brukt parallelt på alle cellene i rutenettet.

Dette er ein modell som er lett å implementera på ein parallell arkitektur (t.d. GPU) og køyra raskt med relativt store rutenett og mange dyr. Det er derimot ikkje lett å definera eit detaljert regelsett. I dømet over, t.d., kan me sjå at reven sit i ro til der kjem ein kanin forbi og to kaninar kan lett flytta inn i same celle slik at den eine kaninen forsvinn.

Alt. 3. Agent-basert simulering Agent er ein som handlar (frå latin agere). Kaninar og revar er agentar, dei handlar, dvs. dei et, jaktar, flyktar, osv.

Agentbaserte modellar fokuserer på individet, dvs. kvar einskild agent. I prinsippet kan ein modellera ein unik oppførsel for kvar agent, og det er lett å modellera mykje meir enn to ulike artar i økosystemet.

Dersom me skal modellera rev/kanin-problemet med agentar vil me gjerne bruka eit rutenett tilsvarande celleautomatonen, men i staden for å bruka eit lite regelsett uniformt over heile rutenettet, vil me tenkja på kvar agent som ei autonom skapning som bestemmer kva ho vil gjera. Me skal utdjupa dette i dei neste avsnitta.

Agentbaserte modellar gjer det enkelt å skriva detaljerte modellar for korleis kvart dyr oppfører seg, slik at ein får gode mikromodellar. Simulering kan derimot krevja meir maskinressursar dersom der er mange agentar i modellen, fordi koden for kvar agent i prinsippet er unik og gjerne komplisert.

5.2.2. Programvareagentar

Programvareagentar er ein autonom programvaremodul. Der er ein del sprik i definisjonane, men ein reknar gjerne med at agenten ikkje er bunden til ei spesifikk maskin, men kan flyttast t.d. gjennom lastbalanse. Der er låg kopling mellom agentane, men ein eller annan kommunikasjonsprotokoll. Agenten sjølv bestemmer når og korleis han skal handla.

JADE er eit bibliotek og programmeringsrammeverk for agentar i Java. Me skal ikkje gå inn i detaljane for programvareagentar utanom simuleringssamanheng.

5.2.3. Agent-basert simulering

Agent-baserte modellar fokuserer på individetet (agenten), og når me implementerer ein slik modell for simulering, må me halda dette fokuset. Agentane er autonome og handlar ut frå si eiga (lokale) oppfatting av verda. Det tilseier låg kopling mellom agentane.

pict


Figur 3: Agentbasert simulatormodel med visualisering.

Det er mogleg å bruka agent-rammeverk som JADE for å implementera agentbaserte modellar, men ein kan òg velja ein enklare programvaremodell der agentane er objekt. Grovarkitekturen er vist i Figur 3, med fire kritiske klasser.

Agent er gjerne ei abstrakt klasse og representerer alle moglege agentar i modellen. T.d. vil rev og kanin vera underklasser av agent. Agentklassa treng ein act()-metode som simulatorklassa kaller kvar gong agenten får handla, og denne metoden bestemmer oppførselen som gjerne er forskjellig for kvar underklasse.

World er modellerer verda der agentane bur. Agentane må kunna spørja verda kva dei ser rundt seg, og det vil seia at verda må halda greie på kvar agentane er, og evt. andre ting som finst i verda.

Simulator er selve kjerna i simulatoren. Normalt vil der berre vera eitt simulatorobjekt (gjerne singleton-mynster), og det har ansvar for å instantiera verda og agentane, halda greie på tida, og gje alle agentane høve til å handla (kalla act()) for kvart tidssteg.

Desse tre klassene utgjer ein fullstendig simulator, men ingen visualisering og helst ikkje annan I/O heller. Der kan vera andre hjelpeklasser, men dei bør vera knytt til éi av klassene og ikkje bidra til sterk kopling mellom dei.

SimViz er visualiseringa. Dette objektet må for all del ikkje påverka dei andre tre klassene (simulatoren), men tek informasjon frå dei for å visualisera tilstanden i simulatoren.

Me kjenner igjen grunnleggjande designprinsipp, med low coupling og high cohesion. Ei klasse for I/O og berre I/O. Simuleringa (utrekningane) er delt mellom tre klasser for henholdsvis tida, individa og landskapet. Dette er den mest grunnleggjande og grovkorna oppgåvedelinga. Komplekse modellar kan krevja rafinering og meir finkorna inndeling.

5.2.4. Vidare lesing og prøving

1.
Barnes og Kölling har eit døme med simulering av foxes and rabbits (sjå neste labøving).
2.
Greenfoot er eit pedagogisk verkty for å læra Java. Det har ein agentmodell i botn, og det er lett å arbeida med simuleringar som foxes and rabbits.
3.
JADE er eit profesjonelt bibliotek og programmeringsrammeverk for agentar i Java.

5.2.5. Innføringsvideoar

Videoane er utvikla for kurset i 2015, men er stadig relevante som ein introduksjon.

Foilar: PDF

Foilar: PDF

Les: Barnes og Kölling s. 326-342

Foilar: PDF