EMERGENCE OF SELF ORGANIZATION AND SEARCH FOR OPTIMAL ENTERPRISE STRUCTURE:
AI EVOLUTIONARY METHODS APPLIED TO AGENT BASED PROCESS SIMULATION
Marco Remondino
remond@di.unito.it
Department of Computer Science
Struttura del Seminario
• Introduzione: modelli informatici per la simulazione di sistemi sociali complessi.
Come e perchè.
• Tre esempi molto diversi tra loro di modellazione di sistemi complessi:
HeatBugs, SUM e jES
• Modellazione di impresa: due paradigmi
• Metodologia ibrida (ABPS): una proposta
Parte 1: INTRODUZIONE
Perchè simulare sistemi sociali?
• L’idea non è creare un modello
matematico con le conclusioni implicite nelle premesse
• Simulazione intesa come esperimento: ciò che interessa non sono (solo) i risultati
finali, ma soprattutto il modo in cui il sistema funziona
• Un modello di un sistema sociale
complesso si ottiene stabilendono regole generali per l’ambiente e regole di
comportamento per gli “agenti” coinvolti
• L’interazione tra le parti non è definita
staticamente, ma si crea autonomamente sulla base delle regole definite per i singoli agenti e per l’ambiente
• Si assiste spesso all’emergenza di
comportamento complesso, cioè non
derivabile semplicemente come somma delle parti in gioco e non definibile a priori dal programmatore, bensì come risultato dell’interazione spontanea tra le parti
• Si tratta del corrispettivo degli esperimenti condotti in laboratorio per scienze quali la chimica e la fisica: ovviamente l'economia, la sociologia o altre scienze sociali non
possono essere sperimentate in
laboratorio, dunque l’idea è quella di far ricorso al modello simulato (società
artificiali)
“LA SIMULAZIONE AL COMPUTER PUO’ ESSERE CONSIDERATA COME UNA TERZA VIA PER
RAPPRESENTARE MODELLI SOCIALI”
(Ostrom, 1998)
Alternativa ad altri due sistemi simbolici:
1.Linguaggio naturale (altamente
descrittivo, difficilmente computabile)
2.Formalizzazione matematica (altamente computabile, non sempre
sufficientemente descrittiva)
• La simulazione al computer può essere utilizzata per riprodurre sistemi dal punto di vista quantitativo e qualitativo. In
particolare è valida per modellare processi e, sebbene le relazioni non lineari possano generare problemi metodologichi, esse
possono comunque essere rappresentate in un programma
Sciami di Agenti
• Una tecnica molto utile per riprodurre sistemi complessi che ha origine diretta nel paradigma di programmazione ad oggetti
• Una moltitudine di agenti, generalmente semplici, che interagiscono tra loro e con l’ambiente in cui operano
Parte 2: ESEMPI
Tre Esempi
1) HeatBugs (www.swarm.org/examples- heatbugs.html)
2) SUM (http://web.econ.unito.it/terna/sum) 3) jES (http://web.econ.unito.it/terna/jes)
HeatBugs (Swarm)
• E’ una dimostrazione di come regole semplici e locali possano generare l’emergenza di un comportamento globale complesso. Tutti gli agenti in gioco hanno uguali proprietà:
1) Generano una limitata quantità di calore 2) Possiedono una funzione di “felicità”
3) Più sono al caldo, più sono felici
4) Possono muoversi liberamente per cercare maggior calore
HeatBugs (2)
• L’ambiente in cui gli agenti agiscono ha a sua volta alcune proprietà:
1) Consente mobilità degli agenti su celle 2) Gestisce la diffusione calore prodotto
(che aumenta quando più agenti sono in celle contigue)
3) Gestisce l’evaporazione del calore in funzione al tempo trascorso
HeatBugs (3)
calore calore
calore calore
calore calore
più calore AGENTE
più calore calore
AGENTE calore
più calore AGENTE
più calore calore
calore calore
calore calore
calore
HeatBugs (4)
• Gli agenti (verdi) si muovono al fine di
cercare zone con maggior calore (rosse):
HeatBugs (5)
• La simulazione può essere intesa come la risoluzione sperimentale ad un problema di ottimizzazione: ogni agente cerca di
massimizzare la propria “felicità”
HeatBugs (6)
• In brevissimo tempo l’“infelicità” media del sistema raggiunge un minimo locale
• Emergenza di comportamento
complesso: si osserva la formazione di
“stormi” di agenti che si muovono
all’unisono, al fine di rimanere all’interno della zona calda da essi generata
SUM (Pietro Terna)
• SUM = Surprising (Un)realistic Market
• Si intende creare un modello di un mercato di borsa
• Non si vuole simulare il mercato di borsa reale, ma crearne uno virtuale, con tutte le proprietà di quello vero
SUM (2)
• Gli agenti impiegati sono “no minded”, cioè agiscono sulla base di semplici regole e
non vi è apprendimento
• La struttura dell’ambiente in cui operano è costruita con precisione e dovizia di regole
SUM (3)
• Gli agenti inviano i loro ordini (di acquisto o vendita) al book, con i relativi prezzi limite
• Il book esegue immediatamente gli ordini se trova una controparte adatta all'interno del proprio log
• Altrimenti registra separatamente gli ordini di
acquisto o vendita, al fine di accoppiarli con altri ordini futuri
SUM (4)
Gli agenti:
• Conoscono solamente l'ultimo prezzo eseguito
• Scelgono a caso, in modo bilanciato, se vendere o acquistare
• Fissano il loro limite di prezzo moltiplicando l'ultimo prezzo eseguito per un coefficiente casuale
SUM (5)
• Già con queste semplicissime regole si
assiste alla formazione di “bolle” e “crash”, e la struttura globale del mercato è
sorprendentemente realistica. Questo può significare che sono le regole del mercato la causa principale per la creazione di un determinato trend, qualunque sia il
comportamento degli agenti coinvolti
SUM (6)
• Un esempio grafico del trend
autonomamente
generato dagli agenti operanti nel mercato artificiale:
SUM (7)
• SUM è attualmente molto più evoluto rispetto a quanto detto qui; vi è stata
l’introduzione di agenti in grado di imitare il comportamento di altri, utilizzare tecniche evolute (quali stop-loss) e altre
caratteristiche
jES (Pietro Terna)
• jES: Java Enterprise Simulator
• Software basato su Swarm per la modellazione e simulazione di due realtà: imprese reali ed
imprese virtuali
• Imprese reali: quelle esistenti (rappresentazione del comportamento ed ottimizzazione)
• Imprese virtuali: quelle concettuali (come hanno origine e come interagiscono con il contesto
sociale circostante)
jES (2)
Agenti utilizzati nella simulazione:
• Ordini da produrre
• Unità produttive
• Nodi di decisione (basati su regole)
• Avatar di utenti umani
3
2 1
3
1 5
3
1,3,4
Rappresentazione:
Unità produttive, imprese e
distretti industriali
jES (3)
jES (4)
# Recipes ;
recipeA 101 1 s 1 p 1 10 2 s 1 3 s 1 ;
recipeB 100 1 s 3 \ 3 2 s 1 3 s 3 \ 2 e 10 ;
• Ricette: un potente formalismo per
rappresentare gli ordini ed il loro stato di completamento
jES (5)
• Struttura decentralizzata: gli ordini
contengono tutte le informazioni per la loro produzione
• Gli ordini possono essere generati a caso oppure obbedire a particolari sequenze (nel caso si desiderino simulare imprese reali)
• Vi è capacità di contabilità
jES (6)
• Con jES è possibile simulare diverse situazioni all’interno di imprese
(introduzione di nuovi macchinari, gestione magazzini, outsourcing...)
• Si può simulare l’emergenza di
innovazione (nuovi # all’interno delle ricette)
jES (7)
• jES è attualmente in una fase molto
avanzata del proprio sviluppo ed è stato applicato con successo a realtà aziendali esistenti. Quanto detto qui è solamente un’introduzione alla sua struttura formale di base.
Parte 3: ABPS
Due Metodologie Simulative
• E' possibile identificare due metodologie diverse per la simulazione di impresa.
Entrambe permettono la creazione di un modello computazionale, partendo da
punti di vista molto diversi tra loro
Simulazione di Impresa
Sia la Simulazione di Processo, sia quella basata su Multi-Agenti sono metodologie efficaci per creare modelli di imprese e sistemi
complessi, ma hanno alcune pecche
Process Simulation
• Il sistema che si intende simulare può essere diviso in parti elementari
• Utile come supporto alle decisioni e per analisi “what-if”
• I modelli che ne risultano sono piuttosto statici (no emergenza
Agent Based Simulation
• Deriva dalla teoria del Caos
• Adatta a sistemi in cui la somma delle parti non determina necessariamente il comportamento aggregato
• I modelli risultanti sono dinamici (emergenza di
Simulazione di processo
• Solitamente utilizzata per sistemi le cui singole parti possono essere rappresentate con modelli logico-matematici (es. Fluidodinamica,
Meccanica, Aeronautica, ecc.)
• Le singole parti sono rappresentate da blocchi con proprietà locali, attraverso le quali vi è un flusso e si produce un insieme di output dato un insieme di input
• Una simulazione di processo può essere
dunque vista come una funzione da Rn in Rm
≥
Agent Based Process Simulation: Metodologia pensata per situazioni in cui nessuna delle tecniche precedentemente esaminate non possono essere applicate con risultati soddisfacenti
1) Molti sistemi di un’impresa possono essere descritti attraverso la simulazione basata su processo. L’interazione tra questi sistemi, tuttavia, è spesso molto complessa e generalmente richiede una partecipazione umana (e comunque non strettamente deterministica)
2) In un singolo macchinario molto complesso, non tutte le parti sono strettamente deterministiche o stocastiche, nel senso che esse potrebbero essere condizionate da qualche influenza imprevista proveniente dall’ambiente
3) L’organizzazione di un’impresa può essere simulata attraverso l’uso del paradigma “multi-agente”. Tuttavia, questo non permette di scendere nel dettaglio dei macchinari utilizzati o delle strutture
Esempi
• Un macchinario in cui una o più parti
possono essere influenzate dall'ambiente (danneggiate dall'umidità, dal fuoco,
oppure migliorate dalla presenza di altri macchinari, lubrificanti o altro)
• In un’impresa, alcuni macchinari possono essere controllati da uomini, che dunque possono ammalarsi o fare sciopero
AGENTE COME PARTE DI UN MACCHINARIO
INPUT “a” OUTPUT “a”
p p p
p p p
AGENT
ENVIRONMENT
OUTPUT
”a + delta”
AGENTI COME CONNESSIONE TRA PROCESSI
Unit 1a Unit 2a Unit 3a Unit 4a Unit 5a
AGENTS Unit 1b
Unit 2b Unit 3b Unit 4b Unit 5b
PROCESS BASED PROCESS BASED
1) Simbolico: agenti strutturati, la cui struttura è definita secondo strutture derivate dalla Logica. Questo formalismo è adatto a situazioni in cui vi è un singolo agente che interagisce con l’ambiente, oppure pochi agenti con struttura ben definita
2) Sub-simbolico: agenti con struttura molto semplice. Un contesto multi-agente di questo tipo permette l’emergenza di comportamento complesso e auto organizzazione. Il comportamento “intelligente” è spesso frutto dell’interazione tra agenti ed ambiente e tra molti comportamenti semplici
VARI PARADIGMI AD AGENTI
3) Architetture Ibride: a basso livello troviamo agenti reattivi, mentre ai livelli più alti agiscono agenti più complessi e strutturati. In questo modo è possibile combinare capacità reattive e pianificazione
AGENTI SIMBOLICI RAPPRESENTANO I PROCESSI
Formalizzazione
• Poiché i processi possono solitamente essere modellati come flussi deterministici o stocastici, la mia proposta consiste nell'utilizzare logica
proposizionale o modale per descrivere la loro struttura
• Per modellare un processo semplice, la logica proposizionale è sufficiente, poiché permette di creare tavole di verità per i singoli sub-processi e dunque per l'intero processo da essi composto
• Un sub-processo produce output_1 quando la formula è True oppure Output_2 quando è
False; uno dei due output può essere "void"
2
N
A and B
A B
C 1
D
D or N
C and E
1
E F
2
F F 1
2
1
1 2
AGENTI SUB-SIMBOLICI DI TIPO MINDED RAPPRESENTANO IL “FATTORE
UMANO”
Metodi Evolutivi
• Gli Algoritmi Genetici sono la
trasposizione computabile della teoria evolutiva di Darwin, spesso definita
“sopravvivenza del più adatto”
• I Classifier System derivano dagli AG, nel senso che usano stringhe di caratteri per codificare regole per condizioni e azioni conseguenti
Applicazione ad ABPS
• Le tecnologie evolutive possono essere incorporate in sciami di agenti sub-
simbolici, tra essi interagenti, per
massimizzare localmente alcune funzioni
• Per esempio agenti basati su AG
potrebbero eseguire azioni macchinari modellati con logica proposizionale per ottenere il miglior set-up
Local Output (to maximize)
10011000 01111001 10000110 11110100
………….
A & B
GLOBAL OUTPUT
C & E
D v N F
G L O B A L I N P U T
Conclusioni
• La simulazione nel campo delle scienze complesse
permette di osservare il sistema come se lo si studiasse in laboratorio
• Le applicazioni al campo aziendale esistono e sono efficaci, e sono basate generalmente su processi o su sciami di agenti (solitamente no-minded)
• Per le situazioni che non possono essere simulate con nessuno dei due approcci esistenti, si propone l’uso di ABPS
• Grazie ai metodi evolutivi applicati ad essa, è possibile ricercare la struttura ottimale dell’impresa o parti della stessa
