Ottimizzazione e modelli ad agentivirgo.unive.it/paolop/papers/flaminio_vittorio_2011.pdf ·...
23
Applicazioni della matematica Pellizzari Paolo Introduzione Ottimizzazione Idee ES TSP Sistemi complessi Modelli ad agenti Conclusioni Ottimizzazione e modelli ad agenti Paolo Pellizzari Dipartimento di Economia Ca’ Foscari - Venezia Vittorio Veneto, 24 Maggio 2011
Transcript of Ottimizzazione e modelli ad agentivirgo.unive.it/paolop/papers/flaminio_vittorio_2011.pdf ·...
Applicazionidella
matematica
PellizzariPaolo
Introduzione
Ottimizzazione
Idee
ES
TSP
Sistemicomplessi
Modelli adagenti
Conclusioni
Ottimizzazione e modelli ad agenti
Paolo Pellizzari
Dipartimento di EconomiaCa’ Foscari - Venezia
Vittorio Veneto, 24 Maggio 2011
Applicazionidella
matematica
PellizzariPaolo
Introduzione
Ottimizzazione
Idee
ES
TSP
Sistemicomplessi
Modelli adagenti
Conclusioni
Introduzione
Metodi moderni per l’ottimizzazione.1 Esempi e definizione del problema.2 Grandi problemi, grandi idee. . .3 Strategie evolutive.
Il problema del commesso viaggiatore (TSP, Travellingsalesman problem).Modelli ad agenti, microsimulazione e sistemicomplessi.
1 Cos’è un sistema complesso?2 Idee.3 Esempi.
Il fil rouge è l’uso di tecniche computazionali.
Applicazionidella
matematica
PellizzariPaolo
Introduzione
Ottimizzazione
Idee
ES
TSP
Sistemicomplessi
Modelli adagenti
Conclusioni
Ottimizzazione
Minimizzare il costo di produzione, massimizzare ilprofitto di una campagna di vendite, massimizzare ilnumero di voti ricevuti con pubblicità elettorali mirate,minimizzare la resistenza aerodinamica di un’alad’areo. . .Trovare il minimo è (-)equivalente a determinare ilmassimo. Oggi parleremo di funzioni di costo.Il problema: trovare la configurazione x in un dominiodato D che minimizzi il costo f (x). In formule,
minx∈D⊆RN
f (x).
Applicazionidella
matematica
PellizzariPaolo
Introduzione
Ottimizzazione
Idee
ES
TSP
Sistemicomplessi
Modelli adagenti
Conclusioni
Un caso semplice
In qualche caso ci sono problemi semplici, risolvibilicon una metafora “gravitazionale”.
−1 0 1 2 3 4 5
−1
01
23
45
6
x
f(x)
●
Applicazionidella
matematica
PellizzariPaolo
Introduzione
Ottimizzazione
Idee
ES
TSP
Sistemicomplessi
Modelli adagenti
Conclusioni
Uno difficile. . .
Ma le cose si possono complicare: minimi locali multiplie non-derivabilità del costo f .
−1 0 1 2 3 4 5
−1
01
23
45
6
x
f(x)
●
Applicazionidella
matematica
PellizzariPaolo
Introduzione
Ottimizzazione
Idee
ES
TSP
Sistemicomplessi
Modelli adagenti
Conclusioni
. . . e uno più difficile!
Ma le cose si possono complicare: minimi locali multiplie non-derivabilità del costo f .
−1 0 1 2 3 4 5
−1
01
23
45
6
x
f(x)
●
Applicazionidella
matematica
PellizzariPaolo
Introduzione
Ottimizzazione
Idee
ES
TSP
Sistemicomplessi
Modelli adagenti
Conclusioni
Funzioni di più variabili
La dimensione del problema è importante (“fardellodella dimensionalità”).
x
−4
−2
0
2
4
y
−4
−2
0
2
4
19.0
19.2
19.4
19.6
19.8
Applicazionidella
matematica
PellizzariPaolo
Introduzione
Ottimizzazione
Idee
ES
TSP
Sistemicomplessi
Modelli adagenti
Conclusioni
Funzioni di più variabili
La dimensione del problema è importante (“fardellodella dimensionalità”).
x
−4−2
0
2
4
y
−4
−2
0
2
4
0
5
10
Applicazionidella
matematica
PellizzariPaolo
Introduzione
Ottimizzazione
Idee
ES
TSP
Sistemicomplessi
Modelli adagenti
Conclusioni
Funzioni di più variabili
La dimensione del problema è importante (“fardellodella dimensionalità”).
0
2
4
6
8
10
12
14
−4 −2 0 2 4
−4
−2
0
2
4
Applicazionidella
matematica
PellizzariPaolo
Introduzione
Ottimizzazione
Idee
ES
TSP
Sistemicomplessi
Modelli adagenti
Conclusioni
Grandi problemi, grandi idee
I metodi tradizionali non riescono a determinare lasoluzione di minimo costo x .L’evoluzione è un modo brillante per risolvere problemidifficili.
Darwin e l’ottimizzazione
1 Le soluzioni evolvono, in base al caso (mutazione) eall’imitazione (incrocio).
2 Il più adatto sopravvive (ma non sempre).
3 Esplorazione e sfruttamento.
Applicazionidella
matematica
PellizzariPaolo
Introduzione
Ottimizzazione
Idee
ES
TSP
Sistemicomplessi
Modelli adagenti
Conclusioni
Grandi problemi, grandi idee
Schumpeter: sviluppo, dinamismo, innovazione. . .L’economia e la natura sprecano risorse in grandequantità e possiamo applicare la stessa “distruzionecreativa” all’ottimizzazione:
Produzione significa combinare [soluzioni] e[ipotesi] in maniera diversa.
Evolution strategies: algoritmo d’ottimizzazione iterativobasato su quattro fasi:
1 Inizializzazione casuale2 Mutazione3 Ricombinazione4 Selezione
Applicazionidella
matematica
PellizzariPaolo
Introduzione
Ottimizzazione
Idee
ES
TSP
Sistemicomplessi
Modelli adagenti
Conclusioni
Evolution strategies
ES in azione.Ideati da Rechemberg (1973) e Schwefel (1994),competono scientificamente con i più famosi algoritmigenetici.Algoritmi population-based, stocastici, a ricerca diretta,adatti al calcolo parallelo, robusti.“Evolution strategies: a comprehensive introduction”,HG Beyer e HP Schwefel, Natural Computing, 1, 3–52,2002.Ottimizzazione di strategie di trading: 760 variabili.Auto-organizzazione: meccanismo per bilanciareautomaticamente esplorazione e sfruttamento.
Applicazionidella
matematica
PellizzariPaolo
Introduzione
Ottimizzazione
Idee
ES
TSP
Sistemicomplessi
Modelli adagenti
Conclusioni
Evolution strategies
ES in azione.Ideati da Rechemberg (1973) e Schwefel (1994),competono scientificamente con i più famosi algoritmigenetici.Algoritmi population-based, stocastici, a ricerca diretta,adatti al calcolo parallelo, robusti.“Evolution strategies: a comprehensive introduction”,HG Beyer e HP Schwefel, Natural Computing, 1, 3–52,2002.Ottimizzazione di strategie di trading: 760 variabili.Auto-organizzazione: meccanismo per bilanciareautomaticamente esplorazione e sfruttamento.
Applicazionidella
matematica
PellizzariPaolo
Introduzione
Ottimizzazione
Idee
ES
TSP
Sistemicomplessi
Modelli adagenti
Conclusioni
Il commessio viaggiatore
Date n città, determinare un tour che le visiti tutte e cheabbia lunghezza minima.Si tratta, in sostanza, scegliere in che ordine visitare lecittà.Questione pratica di enorme rilevanza per la logisticadistributiva, ma anche esempio di problema teoricocomplesso.Problema NP-hard: nessuno sa se si può risolvereefficacemente.Il TSP in diretta. . .100.000 città e Mona Lisa.
Applicazionidella
matematica
PellizzariPaolo
Introduzione
Ottimizzazione
Idee
ES
TSP
Sistemicomplessi
Modelli adagenti
Conclusioni
Il commessio viaggiatore
Date n città, determinare un tour che le visiti tutte e cheabbia lunghezza minima.Si tratta, in sostanza, scegliere in che ordine visitare lecittà.Questione pratica di enorme rilevanza per la logisticadistributiva, ma anche esempio di problema teoricocomplesso.Problema NP-hard: nessuno sa se si può risolvereefficacemente.Il TSP in diretta. . .100.000 città e Mona Lisa.
Applicazionidella
matematica
PellizzariPaolo
Introduzione
Ottimizzazione
Idee
ES
TSP
Sistemicomplessi
Modelli adagenti
Conclusioni
Modelli ad agenti e sistemi complessi
Grande numero di agenti (cellule, consumatori, votanti,automobili, porzioni di fluidi).Interazioni non lineari e diversità di scala.Emergenza (“il tutto è più della somma delle parti”)Agente rappresentativo: i modelli “semplici” tendono anon catturare fenomeni macroscopici.
Applicazionidella
matematica
PellizzariPaolo
Introduzione
Ottimizzazione
Idee
ES
TSP
Sistemicomplessi
Modelli adagenti
Conclusioni
Esempi di sistemi complessi
Mercati finanziari.1 Enorme masse di capitali e agenti.2 Interazioni guidate da imitazione, asimmetrie
informative e, talvolta, panico.3 Effetti sistemici sull’economia reale.
Cancro.1 Grande numero di cellule coinvolte.2 Interazioni chimiche e fisiche, sia dirette che mediate,
fra tumore, sistema immunitario e farmaci.3 Costi umani e sociali enormi.
Foresta.
Applicazionidella
matematica
PellizzariPaolo
Introduzione
Ottimizzazione
Idee
ES
TSP
Sistemicomplessi
Modelli adagenti
Conclusioni
Modello ad agenti
Microfondato, computazionale, tiene contodell’eterogeneità degli agenti coinvolti.
Modello ad agentiRiproduce le azioni simultanee e le interazioni di agentimultipli, tentando di replicare e prevedere il comportamentodi sistemi complessi.
Utile a fini esplicativi, previsivi e per la generazione discenari a supporto delle decisioni.Esperimenti in vivo e in silico.
Applicazionidella
matematica
PellizzariPaolo
Introduzione
Ottimizzazione
Idee
ES
TSP
Sistemicomplessi
Modelli adagenti
Conclusioni
Modello ad agenti
Microfondato, computazionale, tiene contodell’eterogeneità degli agenti coinvolti.
Modello ad agentiRiproduce le azioni simultanee e le interazioni di agentimultipli, tentando di replicare e prevedere il comportamentodi sistemi complessi.
Utile a fini esplicativi, previsivi e per la generazione discenari a supporto delle decisioni.Esperimenti in vivo e in silico.
Applicazionidella
matematica
PellizzariPaolo
Introduzione
Ottimizzazione
Idee
ES
TSP
Sistemicomplessi
Modelli adagenti
Conclusioni
Modello ad agenti
Microfondato, computazionale, tiene contodell’eterogeneità degli agenti coinvolti.
Modello ad agentiRiproduce le azioni simultanee e le interazioni di agentimultipli, tentando di replicare e prevedere il comportamentodi sistemi complessi.
Utile a fini esplicativi, previsivi e per la generazione discenari a supporto delle decisioni.Esperimenti in vivo e in silico.
Applicazionidella
matematica
PellizzariPaolo
Introduzione
Ottimizzazione
Idee
ES
TSP
Sistemicomplessi
Modelli adagenti
Conclusioni
Netlogo live
Flocking: semplici regole individuali possono generarecomplessità aggregata. Sciami, branchi, stormi (CraigReynolds, 1986).Forest: incendi e densità degli alberi.Grand Canyon: modello idrografico accurato di partedel Grand Canyon. Controllo dei flussi e dei tempinecessari alle precipitazioni per spostarsi a valle.Tumor: stem cells, replicazione e metastasi.
Applicazionidella
matematica
PellizzariPaolo
Introduzione
Ottimizzazione
Idee
ES
TSP
Sistemicomplessi
Modelli adagenti
Conclusioni
Conclusioni
Algoritmi moderni possono risolvere problemid’ottimizzazione difficili, su grande scala e nonattaccabili da metodi convenzionali.Computazionalmente intensi, non richiedono regolaritàdella funzione di costo e determinano la soluzione inmodo robusto.I modelli ad agenti consentono di svolgere esperimentiin silico su sistemi complessi.L’uso di strumenti computazionali ha permesso losviluppo di queste idee e dei modi per visualizzarle.
Applicazionidella
matematica
PellizzariPaolo
Introduzione
Ottimizzazione
Idee
ES
TSP
Sistemicomplessi
Modelli adagenti
Conclusioni
Grazie
[email protected]://virgo.unive.it/paolop
